頡棟棟

?

基于乘客滿意度的公交時(shí)刻表設(shè)計(jì)優(yōu)化

頡棟棟

摘要：針對(duì)公交乘客對(duì)出行舒適度的要求，在考慮動(dòng)態(tài)需求的環(huán)境下，提出了乘客滿意度出行函數(shù)。通過分析不同的擁擠現(xiàn)象，建立了非線性優(yōu)化模型，同時(shí)設(shè)計(jì)遺傳算法對(duì)所建模型進(jìn)行求解。最后，通過算例驗(yàn)證了模型與算法的實(shí)效性。

關(guān)鍵詞：乘客滿意度;動(dòng)態(tài)需求

一、引言

隨著我國社會(huì)經(jīng)濟(jì)的快速發(fā)展、城市規(guī)模的不斷擴(kuò)大，城市交通擁堵現(xiàn)象日趨嚴(yán)重。優(yōu)先發(fā)展城市公共交通是解決城市交通問題的主要出路，所以提高公交系統(tǒng)對(duì)乘客的吸引力便成為迫在眉睫的問題，而這個(gè)吸引力的體現(xiàn)就是公交系統(tǒng)的服務(wù)水平，而公交時(shí)刻表就是衡量服務(wù)水平最直接的指標(biāo)之一。

對(duì)公交時(shí)刻表的研究已有許多文獻(xiàn)，[1]根據(jù)線路斷面乘客量給出了時(shí)刻表設(shè)計(jì)的方法；Palma以乘客總延誤時(shí)間為目標(biāo)研究理想狀態(tài)下的時(shí)刻表。[2]基于西安市的公交客流調(diào)查數(shù)據(jù)，討論了四種不同情況下發(fā)車的間隔。這四種情況分別為：在客流需求給定的情況下，可以提供發(fā)車間隔來滿足乘客出行；當(dāng)車輛的數(shù)量有限的情況下，也相應(yīng)的改變發(fā)車間隔，提高服務(wù)質(zhì)量；若在相鄰時(shí)段內(nèi)，發(fā)車間隔的確定應(yīng)采用平滑法；發(fā)車時(shí)刻表的確定，應(yīng)考慮不同的時(shí)間采用不同的發(fā)車間隔。[3]通過對(duì)公交列車化現(xiàn)象的分析，以公交運(yùn)營成本最小和乘客收益最大為目標(biāo)建立模型，確定最小發(fā)車間隔。并利用算例驗(yàn)證模型了模型的可行，結(jié)果表明：最小間隔的確定必須滿足車輛在運(yùn)行時(shí)不能串行的同時(shí)也要滿足乘客的利益。

在考慮公交的運(yùn)行隨機(jī)性的方面，[4]考慮在實(shí)際運(yùn)營中乘客需求具有隨機(jī)性，固定需求下優(yōu)化的公交時(shí)刻表不適應(yīng)運(yùn)營的要求，隨機(jī)需求下的期望值模型忽略了不利可能事件對(duì)運(yùn)營的負(fù)面影響，針對(duì)此情況研究隨機(jī)需求下公交時(shí)刻表設(shè)計(jì)的魯棒性優(yōu)化。[5]針對(duì)需求隨機(jī)變動(dòng)條件下公交運(yùn)營設(shè)計(jì)的綜合優(yōu)化問題，首先將公交運(yùn)行情況抽象到三維網(wǎng)絡(luò)中，給出公交車輛運(yùn)營服務(wù)的時(shí)空網(wǎng)絡(luò)圖，由此構(gòu)造基于隨機(jī)期望值規(guī)劃的公交時(shí)刻表設(shè)計(jì)與車輛運(yùn)用綜合優(yōu)化模型，該模型綜合考慮了公交企業(yè)的經(jīng)濟(jì)效益和公交乘客所得到的公交服務(wù)水平的優(yōu)化，并給出公交服務(wù)頻次和車輛分配協(xié)調(diào)的啟發(fā)式算法。[6]研究了車輛隨機(jī)行駛時(shí)間情況下的單線路公交時(shí)刻表設(shè)計(jì)問題?？紤]了公交運(yùn)營者主觀偏好對(duì)最優(yōu)時(shí)刻表設(shè)計(jì)的影響，建立了以車輛到站時(shí)刻偏差和車輛超時(shí)行駛時(shí)間的權(quán)重之和最小為優(yōu)化目標(biāo)的隨機(jī)期望值模型。

在求解算法方面，文獻(xiàn)[7]提出了一種利用遺傳算法計(jì)算城市公交時(shí)刻表的方法。通過對(duì)城市公交時(shí)刻表和客流的特征分析，以車輛和乘客到站為約束條件，以乘客等待時(shí)間為目標(biāo)函數(shù)，建立模型，并根據(jù)其的獨(dú)特性，設(shè)計(jì)一種特殊編碼的遺傳算法，最后利用實(shí)例對(duì)模型進(jìn)行了驗(yàn)證。[8]文獻(xiàn)[13]通過對(duì)車站、車輛和出行者的關(guān)系，建立了以乘客在站的等待時(shí)間和列車載客量為指標(biāo)的模型，目的是充分使用車底數(shù)，提高運(yùn)營效率。最后給出了遺傳算法的求解步驟，以及利用算例進(jìn)行驗(yàn)證。

本文在已有文獻(xiàn)的基礎(chǔ)上，基于動(dòng)態(tài)需求，以乘客出行滿意度為目標(biāo)建立模型。并結(jié)合上述文獻(xiàn)設(shè)計(jì)遺傳算法對(duì)模型進(jìn)行求解。在文章組織過程中，第1節(jié)對(duì)問題進(jìn)行了分析和定義，第2節(jié)建立非線性模型，第3節(jié)設(shè)計(jì)求解算法，第4節(jié)利用算例驗(yàn)證模型和算法，最后給出了本文結(jié)論。

二、問題分析

本文將研究一條由郊區(qū)發(fā)往工作區(qū)的公交線路，該線路包含有多個(gè)乘客上車站，一個(gè)共同的目的地車站，如圖1所示，共有n個(gè)車站，從車站O1到車站On-1全為上車站，車站D為下車站。

圖1線路示意圖

三、模型建立

(一)目標(biāo)函數(shù)

圖2　車內(nèi)乘客舒適度分析

(1)

(2)

(3)

(二)約束條件

(1)車輛k在車站i的到達(dá)與出發(fā)時(shí)刻。

(4)

(5)

確保最后一輛車在T時(shí)刻發(fā)車：

(6)

(2)相鄰兩車輛之間須滿足最小安全追蹤間隔Ic。

(7)

四、算法設(shè)計(jì)

本文采用遺傳算法對(duì)上述模型進(jìn)行求解。首先，對(duì)其進(jìn)行編碼時(shí)，本文將研究時(shí)間段等間隔劃分，采用0-1編碼方式對(duì)染色體進(jìn)行編碼染色體每個(gè)基因位都對(duì)應(yīng)這研究時(shí)段內(nèi)的某一時(shí)刻，其中“1”表示在該基因位對(duì)應(yīng)的時(shí)刻車輛在始發(fā)站發(fā)車，“0”表示不發(fā)車。其次，在遺傳算法中將通過適應(yīng)度的來衡量種群中的個(gè)體是否達(dá)到或者接近于最優(yōu)解。適應(yīng)度值大的將被遺傳到下一代的概率大，反之，適應(yīng)度小的被遺傳到下一代的概率小。由于本文的目標(biāo)函數(shù)是最小值優(yōu)化問題，所以將其通過公式(8)進(jìn)行轉(zhuǎn)換。

(8)

遺傳操作包含選擇操作、交叉操作和變異操作，通過遺傳操作產(chǎn)生了新的一代種群，下面將結(jié)合染色體的編碼形式對(duì)其進(jìn)行闡述。

(一)選擇操作

選擇操作是對(duì)種群個(gè)體進(jìn)行優(yōu)勝劣汰的操作，其核心是：將個(gè)體適應(yīng)度函數(shù)值大的遺傳到下一代中，而將適應(yīng)度小的淘汰掉。本文將采用輪盤賭選擇法。其中，輪盤賭選擇的概率與其適應(yīng)度值的大小成正比，如公式(9)所示。

(9)

式中：fi表示個(gè)體i適應(yīng)度的值，pi表示被遺傳到下一種群中的概率。

(二)交叉操作

本文采用單點(diǎn)交叉，單點(diǎn)交叉是隨機(jī)選取種群中的兩個(gè)染色體，隨機(jī)產(chǎn)生交叉點(diǎn)，根據(jù)交叉概率Pc將其從交叉點(diǎn)處將其斷開，并相互交換。

(三)變異操作

本文采用基本位變異，對(duì)染色體隨機(jī)產(chǎn)生變異點(diǎn)，根據(jù)變異概率Pm將其變異成其它等位基因，如圖3所示。

圖3　染色體變異前

由于在上述模型中，兩車輛之間必須滿足最小安全追蹤間隔，而由于染色體的初始化以及交叉變異操作的都是隨機(jī)進(jìn)行的，所以在染色體初始化和交叉變異操作之后須對(duì)染色體進(jìn)行調(diào)整。將染色體中不滿足最小安全追蹤間隔的基因進(jìn)行調(diào)整，將第一車輛固定，找到第二車輛，若兩者之間不滿足安全追蹤間隔，則使第二車輛的基因變?yōu)?，將下一個(gè)基因變?yōu)?，再判斷在當(dāng)前基因?qū)?yīng)的時(shí)刻發(fā)車是否滿足安全追蹤間隔的約束，若不滿足，則繼續(xù)向后推移。

以上算法的步驟如下所示，其中g(shù)表示迭代次數(shù)，Gen表示程序終止代數(shù)，M表示種群大小，P(g)表示第g代的種群，i表示個(gè)體，f(g，i)種群P(g)中個(gè)體i的適應(yīng)度。

Step1：初始化種群P(0)，且置g=0；

Step2：如果g>Gen，算法終止，輸出相關(guān)計(jì)算結(jié)果；否則，轉(zhuǎn)下一步；

Step3：計(jì)算種群P(g)中所有個(gè)體的適應(yīng)度；

Step3.1：置i=1；

Step3.2：計(jì)算個(gè)體i的適應(yīng)度f(g，i)；

Step3.3：如果i≤M，置i=i++，轉(zhuǎn)Step3.1；否則，轉(zhuǎn)Step4；

Step4：根據(jù)Step3計(jì)算出的適應(yīng)度對(duì)種群P(g)進(jìn)行選擇操作；

Step5：對(duì)種群P(g)進(jìn)行單點(diǎn)交叉操作；

Step6：對(duì)種群P(g)進(jìn)行變異操作；

Step7：將M個(gè)種群進(jìn)行賦值，P(g+1)=P(g)；

Step8：置g=g+1，轉(zhuǎn)Step2。

五、算例

本算例設(shè)計(jì)一條如圖4所示多對(duì)一的城際鐵路，假設(shè)其研究時(shí)段為[7:00-8:00]，車輛在每站的停車時(shí)間均為1min，1站到2站、2站到3站和3站到4站的運(yùn)行時(shí)間分別為10min、5min和15min。在研究時(shí)段內(nèi)可用車輛數(shù)為10列，車輛最小安全追蹤間隔為5min，車輛的額定容量為400人。

圖4　線路結(jié)構(gòu)示意圖

算法參數(shù)選?。悍N群規(guī)模80，迭代次數(shù)500，交叉概率0.98，變異概率0.1，擁擠因子M=30。利用以上參數(shù)得到車輛的發(fā)車時(shí)刻表如表1所示，其總目標(biāo)值為33951.00min，乘客總等待時(shí)間為13615.00min。

表1　車輛在首站的發(fā)車時(shí)刻表

通過上述計(jì)算結(jié)果可知，在時(shí)間段7:20-7:40之間車輛密度較大，而此時(shí)段為客流高峰期，所以滿足大客流需要高密度的車輛服務(wù)的規(guī)律，結(jié)果合理。

六、結(jié)論

本文主要針對(duì)存在多個(gè)上車站和一個(gè)下車站的特殊情況，在考慮乘客出行滿意度的條件下，研究了單線路車輛時(shí)刻表優(yōu)化問題，同時(shí)設(shè)計(jì)了有效的遺傳算法進(jìn)行求解。最后從算例的結(jié)果可知，該模型與算法能夠有效的求解出質(zhì)量較高的時(shí)刻表。然而，由于該問題的特殊性，導(dǎo)致所建模型與算法不能推廣至一般問題，這也是進(jìn)一步所需要研究的內(nèi)容。(作者單位：蘭州交通大學(xué)鐵道技術(shù)學(xué)院)

2011年甘肅省第十二批科技計(jì)劃(自然科學(xué)基金計(jì)劃第二批)(項(xiàng)目編號(hào):1112RJZA049)

參考文獻(xiàn)：

[1]CederA.Methodsforcreatingbustimetables[J].TransportationResearchPartAGeneral，1987，21(1):59-83.

[2]孫芙靈.公交調(diào)度中發(fā)車間隔的確定方法的探討[J].西安公路交通大學(xué)學(xué)報(bào).1997，17(2B):44-48.

[3]周嘉男，羅霞，黃啟樂，魏強(qiáng).基于緩解公交車輛化現(xiàn)象的最小發(fā)車間隔研究[J].重慶交通大學(xué)學(xué)報(bào)(自然科學(xué)版).2012，31(4):836-841.

[4]孫楊，宋瑞，何世偉.隨機(jī)需求下公交時(shí)刻表設(shè)計(jì)的魯棒性優(yōu)化[J].系統(tǒng)工程理論與實(shí)踐，2011，31(5):986-992.

[5]宋瑞，何世偉，楊永凱，等.公交時(shí)刻表設(shè)計(jì)與車輛運(yùn)用綜合優(yōu)化模型[J].中國公路學(xué)報(bào)，2006，19(3):70-76.

[6]吳影輝，唐加福，宮俊.考慮隨機(jī)行駛時(shí)間的單線路公交時(shí)刻表設(shè)計(jì)優(yōu)化模型[J].東北大學(xué)學(xué)報(bào):自然科學(xué)版，2015(10):1393-1397.

[7]張明輝，牛惠民.一種用于計(jì)算城市公交時(shí)刻表的復(fù)合遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用.2011，47(20):210-213.

[8]徐永實(shí)，徐瑞華.遺傳算法在軌道交通車輛發(fā)車時(shí)刻優(yōu)化中的應(yīng)用[J].城市公用事業(yè).2011(2):27-29.