徐瑜婷,宋 瑞,鄭 鋰
(北京交通大學(xué)交通運(yùn)輸學(xué)院,北京 100044)
區(qū)域公交的多車場車輛調(diào)度優(yōu)化
徐瑜婷,宋 瑞,鄭 鋰
(北京交通大學(xué)交通運(yùn)輸學(xué)院,北京 100044)
在運(yùn)營企業(yè)費(fèi)用最少的基本模型基礎(chǔ)上,以乘客等待費(fèi)用最少為目標(biāo)函數(shù)討論多車場車輛調(diào)度問題,并建立相應(yīng)模型。基于逆差函數(shù)算法對模型求解,設(shè)計(jì)兩種方法進(jìn)行求解:一種是人工插入空駛車程,求解過程中加入乘客等待時間的限制;另一種是通過由逆差函數(shù)為基礎(chǔ)設(shè)計(jì)的PT-Manager仿真軟件進(jìn)行算法優(yōu)化,對實(shí)際案例進(jìn)行參數(shù)標(biāo)定以及求解。結(jié)果表明:該模型逆差函數(shù)算法求解過程簡單、結(jié)果直觀,PT-Manager仿真軟件能夠幫助公交調(diào)度人員進(jìn)行車輛調(diào)度及優(yōu)化,對現(xiàn)有的車輛調(diào)度以及多車場的發(fā)展有一定的指導(dǎo)意義。
多車場調(diào)度;逆差函數(shù);車輛調(diào)度;PT-Manager
解決現(xiàn)代城市交通擁堵問題的最主要方法之一是大力發(fā)展城市公共交通,而運(yùn)營調(diào)度規(guī)劃是公共交通的主要難點(diǎn)之一。而公共交通規(guī)劃的運(yùn)營調(diào)度分為客流需求預(yù)測、時刻表的編制、行車計(jì)劃、人員的配置等4個方面,由此可見,公交車輛調(diào)度是公交規(guī)劃及運(yùn)營管理中非常重要的環(huán)節(jié)。
公交車輛調(diào)度主要分為多車場車輛調(diào)度(Multiple Deport Vehicle Scheduling Problem,簡稱MDVSP)和單車場車輛調(diào)度。其中,單車場的車輛只能在固定的車場間運(yùn)行,多車場調(diào)度車輛可以在多個車場間被調(diào)用,并允許車輛分布于多個車場。單車場車輛調(diào)度具有簡單、便于管理的優(yōu)點(diǎn),多車場車輛調(diào)度則更有利于運(yùn)輸資源的合理和優(yōu)化調(diào)度,更符合社會可持續(xù)發(fā)展的要求。多車場車輛調(diào)度以一個區(qū)域內(nèi)的車場整體為研究對象,公交運(yùn)營組織和調(diào)度的區(qū)域大可包含整個城市的公交運(yùn)營線路,小可只包含2~3條單線模式的運(yùn)營線路,具體的每一個區(qū)域大小的確定主要是以整個區(qū)域的運(yùn)營效率為最高這個標(biāo)準(zhǔn)來確定的。研究表明,通過對區(qū)域內(nèi)公交車輛的統(tǒng)一管理,可以大大提高車輛利用率,降低運(yùn)營成本[1]。我國現(xiàn)有的車輛調(diào)度多為單車場調(diào)度問題,車場對車輛的規(guī)劃管理以每個車場為目標(biāo),為提高公交運(yùn)營效率減少道路擁堵程度,筆者以區(qū)域公交車輛調(diào)度為研究對象,探討適合我國實(shí)際情況的區(qū)域公交調(diào)度。
國內(nèi)外研究學(xué)者對多車場調(diào)度問題進(jìn)行了大量研究,Ceder,等[2-3]以公交網(wǎng)絡(luò)中兩輛公交車相遇的次數(shù)最大及乘客等待時間最少為目標(biāo),對公交區(qū)域同步換乘進(jìn)行了研究。在此基礎(chǔ)上,A.Haghani,等[4]引入站點(diǎn)換乘權(quán)重與線路換乘吸引度,以乘客總換乘等待時間最少為目標(biāo)建立了公交區(qū)域調(diào)度模型。此后,D.Huisman,等[5]提出了用插入最小空駛車程的逆差函數(shù)的方法來分析車輛的調(diào)度問題。鄒迎[6]在對北京公交區(qū)域運(yùn)營組織與調(diào)度系統(tǒng)初步探討中,提出了多線路車場調(diào)度問題。石琴,等[7]提出了基于換乘優(yōu)化的公交區(qū)域調(diào)度模型。此外,張欣偉,等[8]研究了在提供公共交通信息條件下公交換乘時間最短的調(diào)度問題,并提出了線性規(guī)劃模型。
車輛調(diào)度求解算法以智能算法居多。采用遺傳算法、禁忌搜索算法、蟻群算法等智能搜索算法解決車輛調(diào)度問題,能覆蓋大區(qū)域的車輛調(diào)度問題,通常能計(jì)算3個及以上車場數(shù)量的區(qū)域車輛調(diào)度問題,最終的最優(yōu)解通過計(jì)算機(jī)大規(guī)模計(jì)算得出,質(zhì)量較高且更符合實(shí)際情況。但就中國實(shí)際情況考慮,基于逆差函數(shù)算法的仿真軟件能得出簡單易懂的階躍函數(shù),能計(jì)算出各車場各個時刻的車輛數(shù)。在插入空駛車程,即當(dāng)運(yùn)營中插入擾動情況時,智能算法經(jīng)過復(fù)雜冗長計(jì)算才能得出結(jié)果,而逆差函數(shù)只需調(diào)度人員對圖形進(jìn)行插入,操作簡單,出錯率低。
筆者旨在建立以企業(yè)花費(fèi)最少、以乘客在各車場的等待時間最短以及等待費(fèi)用最少的目標(biāo)函數(shù)。在算法的運(yùn)用中,首先運(yùn)用遺傳算法、禁忌搜素、模擬退火等智能算法[9]得到初始解,然后采用逆差函數(shù)插入空駛車程減少車隊(duì)規(guī)模進(jìn)行解的優(yōu)化調(diào)整。這一過程中逆差函數(shù)算法搜索收斂性以及求解的優(yōu)質(zhì)性劣于直接采用智能算法得出最優(yōu)解,但是以模擬仿真為基礎(chǔ)的逆差函數(shù)便于實(shí)際仿真,能對實(shí)際情況優(yōu)化仿真,算法得出的結(jié)果易于處理,每插入空駛車程,都能對結(jié)果進(jìn)行動態(tài)輸出,簡單易懂,易于操作和理解。
公交時刻表提供了各公交班次信息,包括出發(fā)時間和到達(dá)時間等,如圖1。圖中,班次i的出發(fā)時間為Si,到達(dá)時間為ei,班次i結(jié)束時刻到班次j開始時刻之間的運(yùn)行時間為ti,j。目標(biāo)車輛在完成班次i后可繼續(xù)進(jìn)行班次j的必要條件為:ei+ti,j≤sj。如果車輛執(zhí)行上述的班次,則連接兩者之間的班次常常稱為空駛班次,此時的班次為不載乘客班次。安排空駛班次的目的是減少整個車隊(duì)的規(guī)模。反之,如果班次j的到達(dá)時刻加上i至j班次間的運(yùn)行時間小于班次i的出發(fā)時刻,則可以用班次j的車輛繼續(xù)完成班次i。
圖1 插入空駛車程示意Fig.1 Insert deadheading trips diagram
每輛車可以連續(xù)完成一系列的班次,形成車次鏈(圖2)。定義車輛從該車場駛出的第1班次為出場班次,與之相對應(yīng),當(dāng)車輛執(zhí)行完相應(yīng)的調(diào)度任務(wù),回歸車場所完成的最后一次運(yùn)輸稱為入場班次。一輛車的車次鏈包含出場班次、入場班次和一系列的空駛車次以及常規(guī)班次。而這些班次的對應(yīng)費(fèi)用稱為出場費(fèi)用、入場費(fèi)用,以及空駛費(fèi)用。
圖2 車次鏈形成Fig.2 Train chain diagram
在已知行車時刻表的基礎(chǔ)上,可用逆差函數(shù)求解多車場車輛調(diào)度問題。逆差函數(shù)是一個階躍函數(shù),用以表示的是每個車場當(dāng)前的車輛數(shù),當(dāng)車輛從車場出發(fā)執(zhí)行一個班次時,階躍函數(shù)的函數(shù)值增加1,當(dāng)車輛回到車場時,其函數(shù)值減少1。把所有車場的函數(shù)值相加,得到總的階躍函數(shù),即為該研究對象區(qū)域所需要的車隊(duì)規(guī)模的大小。在每個車場的階躍函數(shù)的構(gòu)建過程中,需要對應(yīng)線路的時刻表數(shù)據(jù),以橫軸表示時刻表的時間,縱軸表示車輛數(shù)量。某線路某時刻由車場出發(fā)的總班次數(shù)與總到達(dá)班次數(shù)之差見式(1):
式中:k為車場編號,k=1,2,3,…,K(K表示研究區(qū)域內(nèi)的車場總數(shù));t代表研究時刻;S代表研究時段內(nèi)對應(yīng)時刻表中所有班次的集合;d(k,t,S)表示從開始時刻到t時刻的車場k出發(fā)總班次數(shù)與總到達(dá)班次數(shù)之差;s(k,t,S)表示所有班次集合S中從開始時刻到t時刻之間的車場k到達(dá)的車輛總和;e(k,t,S)表示t時內(nèi)研究的所有的班次集合S中從開始時刻到t時刻之間的車場k內(nèi)到達(dá)的車輛總和。
設(shè)D(k,S)為研究時段t內(nèi)車場k的總班次之差d(k,t,S)的最大值,如式(2):
多個車場的逆差函數(shù)值之和就是總的車輛數(shù),設(shè)全局逆差函數(shù)(即t時內(nèi)的所有車場逆差函數(shù)之和)為g(t,S)。g(t,S)在t時內(nèi)的最大值用G(t,s)表示。插入空駛班次的條件為:當(dāng)研究區(qū)域達(dá)到最大值G(S)的時刻為t*,在t*之前執(zhí)行一個空駛班次DH1。如果這趟空駛班次在時刻由車場u發(fā)出,在時刻到達(dá)車場v,那么必須滿足條件。當(dāng)完成空駛車次的插入后,時刻表對應(yīng)的車次時間變?yōu)镾1=S+DH1。如果在sv1時刻,車場v達(dá)到其容量極值區(qū)間,則存在t*之前或是恰在t*達(dá)到極值區(qū)間的情況有[10]:
只有式(5)的情況是唯一可能減少需用車輛數(shù)量的情況。所以在車場v到達(dá)極值區(qū)間的時刻之前可在車場u,v之間插入第一個空駛車程,形成第一個空駛班次DH1。
在插入空駛班次DH1以后,為避免車場u在到達(dá)極值區(qū)間的時候車輛數(shù)量不夠的情況發(fā)生,也為了減少車隊(duì)規(guī)模,在車場u極值區(qū)間之前插入新的空駛班次以消除車場u的需用車輛數(shù)的變化。設(shè)定執(zhí)行這次空駛的班次為DH2,自車場q出發(fā)到達(dá)車場u,這里的車場q可以是車場v,也可以是其他車場,發(fā)車的到達(dá)區(qū)間為[,],其中,。
區(qū)域公交車輛調(diào)度模型的目標(biāo)函數(shù)多是企業(yè)花費(fèi)費(fèi)用最少。實(shí)際上,除了考慮企業(yè)的運(yùn)營效益外,還要考慮乘客的滿意度。筆者加入乘客等待時間費(fèi)用來體現(xiàn)對乘客滿意度的考慮。
模型具體形式如下:
式中:cq∈[x,y],q∈w;x,y為任意值,且滿足x>y;av,p表示路徑p是否包含點(diǎn)v∈B,若包含,則av,p=1,反之a(chǎn)v,p=0;yp表示與每條路徑相關(guān)聯(lián)的0-1變量,若有車次通過p,則yp=1,反之yp=0;cp表示包含弧的費(fèi)用;Ωk表示車站場k出發(fā),經(jīng)歷集合B中一些節(jié)點(diǎn)后返回相同車場的路徑集合;cq表示車場k的乘客q單位等待費(fèi)用;q表示在車場k等車的乘客;W表示各個車場等車乘客總體集合;dk表示車場k的車輛數(shù)容量;?q表示車場k的乘客等待的權(quán)重。
式(7)為目標(biāo)函數(shù),其中,cpyp表示企業(yè)的花費(fèi)費(fèi)用,cqyp?q表示乘客的等待費(fèi)用。約束條件中,式(8)保證每個班次j∈B只能由某一車場的1輛車完成;式(9)表示車場車輛數(shù)不超過車場的容量;式(10)限制車輛在路徑上運(yùn)行與否,取值只能是“0”或“1”;式(11)限制所有乘客在各車場的等待權(quán)重之和為1。
逆差函數(shù)算法是通過PT-Manager軟件來實(shí)現(xiàn)的。首先采用文獻(xiàn)[10]中的方法實(shí)行鄰域搜索得出初始解,然后用逆差函數(shù)算法對初始解進(jìn)行優(yōu)化,采用仿真軟件進(jìn)行仿真分析,在模型約束中加入乘客等待時間的容忍度進(jìn)行算法計(jì)算得出最終解。
逆差函數(shù)算法是采用圖形方法求解每個車場實(shí)時的車輛情況。通過插入空駛車程來減少整個研究區(qū)域的車隊(duì)規(guī)模,得到車隊(duì)規(guī)模下限。
用逆差函數(shù)求解多車場問題步驟如下:
1)根據(jù)固定行車計(jì)劃下確定的時刻表,得出任意車次的出發(fā)車場u、到達(dá)車場v以及兩車場之間的運(yùn)行時間t,分別得出任意車場k的逆差函數(shù)圖d(k,t,S)。
2)比較各車場的逆差函數(shù)圖,選擇容量極值區(qū)間最長的車場a為研究對象。
3)選擇最先有車到達(dá)即最先到達(dá)最大值的車場b,若該時刻車場b到達(dá)車場a的空駛時間大于車場a下一班次的發(fā)車時間,則插入空駛車程1,反之依次查看各車場是否能插入空駛車程到車場a。
4)重復(fù)上述第2)步直到a車場無法再插入空駛車程減少車隊(duì)規(guī)模為止。
5)若剩余各車場由于插入空駛車程到a,使得自車場的車隊(duì)規(guī)模增加,則選擇從別的車場間插入空駛車程保證該車場車隊(duì)規(guī)模不變,依次調(diào)整直到除了a車場以外其余車場車隊(duì)規(guī)模不變。
6)依次檢驗(yàn)所有車場是否能插入空駛車程,直到所有車場檢查完成后,轉(zhuǎn)到第7)步,否則轉(zhuǎn)到第3)步。
7)算法結(jié)束,得到插入空駛車程的解。
在PT-Manager仿真軟件上執(zhí)行上述逆差函數(shù)算法。PT-Manager仿真軟件是由Altdoit Software Solutions公司開發(fā)運(yùn)行的仿真軟件,針對逆差函數(shù)求解多車場車輛調(diào)度問題進(jìn)行仿真。通過直接輸入相關(guān)時刻表、車次信息得出各車場逆差函數(shù)d(k,t,S)以及全局逆差函數(shù)g(t,S),進(jìn)一步通過空駛信息輸入,得出空駛車次。具體步驟為:
1)根據(jù)時刻表輸入每個車次的運(yùn)行信息,包含車次名稱、出發(fā)車場、到達(dá)車場、出發(fā)到達(dá)時間等。
2)確認(rèn)輸入所有車次信息后,運(yùn)行程序,得出各個車場的逆差函數(shù)圖形。
3)選擇空駛車程的輸入。有兩種方式可供選擇,第1種方式是直接得出各車場間的空駛時間及空駛里程,輸入到軟件的空駛矩陣中,自動生成空駛車次,轉(zhuǎn)到第3)步;第2種方式是依據(jù)各車場的逆差函數(shù)手動輸入每一空駛車程車次名稱,出發(fā)車場、到達(dá)車場、兩車場間空駛時間,不斷調(diào)整,保證每個乘客在每個車場等待時間不超過模型建立中約束條件(11)以及乘客能容忍的在車場之間的等待時間的要求,直到不能再減少車隊(duì)規(guī)模時,轉(zhuǎn)到第5)步。
4)得到空駛矩陣進(jìn)行運(yùn)行,輸入乘客能容忍的最長等待時間,運(yùn)行得出空駛車次。
5)依據(jù)得出的空駛車次進(jìn)一步修改時刻表,優(yōu)化時刻表,減少整個研究范圍的車隊(duì)規(guī)模。
6)輸出插入的空駛車程和時刻表變化的情況,得出插入空駛車程前后的時刻表,比較優(yōu)化結(jié)果。
7)由實(shí)際情況得出各車場乘客等待權(quán)重,計(jì)算插入空駛車程前后的目標(biāo)函數(shù)值,比較分析空駛車程插入的合理與否。
選取北京市公交線路l1,l2,l3,l4,分別代表 320路、309路、運(yùn)通105路和103路,進(jìn)行多車場車輛調(diào)度的實(shí)例分析。這4條線包含3個車場A、B和C,公交線和車場布置如圖3。
圖3 區(qū)域車場間的位置信息及其線路信息Fig.3 Position and road information about multiple depot diagram
設(shè)定線路的單位運(yùn)行費(fèi)用c320=3,c65=6,c運(yùn)通105=4;在仿真軟件中,取各車場乘客的等待權(quán)重αq值相同,分別為αA=αB=αC=1/3;以及取值αA=0.25,αB=0.3,αC=0.45,同時cq=5,求解過程如圖4。圖4(a)代表A車場插入空駛車程前車場逆差函數(shù);當(dāng)1.2節(jié)模型中目標(biāo)函數(shù)的y取值為10 min時,運(yùn)行得出的空駛車次見圖4(b)。
圖4 A車場插入空駛車場前后逆差函數(shù)Fig.4 A depot’s DF before/after insert deadheading diagram
經(jīng)過求解得到插入空駛車程如表1。
表1 研究區(qū)域插入空駛車程的車次Table 1 Timetable after insert deadheading trips
在插入的空駛車程和時刻表變化的情況,得出插入空駛車程前后的時刻表,如表2。將參數(shù)值代入目標(biāo)函數(shù)(7)中,取3車場等待權(quán)重相同得出,插入空駛車程前目標(biāo)函數(shù)值為96.00;插入空駛車程后目標(biāo)函數(shù)為 59.33。而取值 αA=0.25,αB=0.3,αC=0.45,得出插入前后的目標(biāo)函數(shù)值分別為104.32及76.48。
表2 研究區(qū)域各車場優(yōu)化前后車隊(duì)規(guī)模Table 2 Vehicle quantity before and after inserting deadheading trips
從不同車場的取值權(quán)重可以看出,雖然目標(biāo)函數(shù)值變大,但是對于每個車場來說,對乘客的重要程度有一定改變,更符合實(shí)際情況,能充分考慮每個車場的乘客等待滿意程度。由于乘客的等待費(fèi)用的不同可能會導(dǎo)致不同車場的乘客要求不同,而造成不同車場權(quán)重的不同。
從相同取值權(quán)重的車場插入空駛車程前后可以看出,在原有的時刻表(固定行車計(jì)劃)的基礎(chǔ)上,得出的各個車場逆差函數(shù),在PT-Manager仿真軟件中,分別輸入各車次的運(yùn)行狀態(tài),加入乘客的等待時間的函數(shù)后,求出插入的空駛車程,發(fā)現(xiàn)車隊(duì)規(guī)模由原來的18輛減少為11輛,同時目標(biāo)函數(shù)降低38.2%。把上述插入空駛車程的結(jié)果帶回時刻表,可對時刻表進(jìn)行調(diào)整優(yōu)化。
以運(yùn)營企業(yè)成本費(fèi)用和乘客等待費(fèi)用之和最小為目標(biāo)函數(shù),建立了多車場車輛調(diào)度模型。利用人工和PT-Manager仿真軟件求解,詳細(xì)給出了求解步驟。結(jié)合北京實(shí)際運(yùn)營進(jìn)行算例分析,采用PTManager仿真軟件求解,考慮不同車場乘客等待權(quán)重不同即乘客的滿意程度不同,結(jié)果得到研究區(qū)域整體的車隊(duì)規(guī)模減少了7輛,降低企業(yè)的運(yùn)營成本,同時乘客在每個車場的等待時間不超過10 min,提高乘客滿意度,使得各車場之間車輛銜接更合理,證明了模型合理性。
(References):
[1] 劉志剛,申金升,楊威.基于禁忌搜索的公交區(qū)域調(diào)度配車模型研究[J].交通運(yùn)輸工程與信息學(xué)報,2007,5(4):63-67.
Liu Zhigang,Shen Jinsheng,Yang Wei.Study on multiple bus vehicle dispatching based on Taboo research[J].Transportation Engineering and Information Technology,2007,5(4):63-67.
[2] Ceder A.Methods for creating bus timetables[J].Transportation Rearch:Part A,1986,21(1):59-83.
[3] Ceder A,Golany B,Tal O.Creating bus time tables with maximal synchronization[J].Transportation Research:Part A,2001,35(10):913-928.
[4] Haghani A,Banihashemi M,Chiang K H.A comparative analysis of bus transit vehicle scheduling models[J].Transportation Research:Part B,2003,37(4):301-322.
[5] Huisman D,F(xiàn)reling R,Albert P M,et al.A robust solution approach to the dynamic vehicle scheduling problem[J].Transportation Science,2004,38(4):447-458.
[6] 鄒迎.公交區(qū)域調(diào)度行車計(jì)劃編制方法研究[J].交通運(yùn)輸系統(tǒng)工程與信息,2007,7(3):78-82.
Zou Ying.Study on bus regional scheduling travel plan organizing method[J].Journal of Transportation Systems Engineering and Information Technology,2007,7(3):78-82.
[7] 石琴,覃運(yùn)梅,黃志鵬.公交區(qū)域調(diào)度的最大同步換乘模型[J].中國公路學(xué)報,2007,20(6):90-94.
Shi Qin,Qin Yunmei,Huang Zhipeng.Maximal synchronous transfer model of bus regional dispatching[J].China Journal of Highway and Transport,2007,20(6):90-94.
[8] 張欣偉,張貴蘭.城市公交線網(wǎng)規(guī)劃體系研究[J].交通企業(yè)管理,2008,12(5):62-64
Zhang Xinwei,Zhang Guilan.Study on urban bus routes planning system[J].Transportation Enterprise Management,2008,12(5):62-64.
[9] Zhang Qiao,Xu Xu,Liang Yanchun.An improved artificial immune algorithm with a dynamic threshold[J].Journal of Bionic Engineering,2006,3(2):92-97.
[10]賽德爾,關(guān)偉.公共交通規(guī)劃與運(yùn)營理論、建模及應(yīng)用[M].北京:清華大學(xué)出版社,2010.
Ceder A,Guan Wei.Public Transport Planning and Operation of the Theory,Modeling and Application[M].Beijing:Tsinghua University Press,2010.
Optimization of Vehicles Dispatching Model for Multiple Depots in Regional Traffic
Xu Yuting,Song Rui,Zheng Li
(School of Traffic& Transportation,Beijing Jiaotong University,Beijing 100044,China)
On the base of the fundamental model whose objective was to minimize the company’s costs,multiple depot dispatching problem was discussed and then the corresponding model was established,in which minimizing passengers’waiting expense was considered in the objective function.Then deficit function was used to solve the objective function,which can be solved in two different ways:firstly,manual work was used to insert the deadheading trips to restrict the passengers’waiting time;secondly,PT-manager simulation software which was built on the base of deficit function was introduced to simulate and analyze.In order to make a statistic explore the actual data was introduced.The results proved that the using deficit function to solve the proposed model is simple and accurate.PT-manager simulation software could provide guide and optimization for bus dispatching staff,which also could provide referential significance to the current bus dispatching and the development of multiple depot dispatching.
multiple depot dispatching;deficit function;vehicle dispatching;PT-Manager
U280
A
1674-0696(2013)02-0258-05
10.3969/j.issn.1674-0696.2013.02.19
2012-05-31;
2012-09-21
中央高?;究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)基金項(xiàng)目(2009YJS044)
徐瑜婷(1988—),女,重慶忠縣人,碩士研究生,主要從事城市交通規(guī)劃與管理方面的研究。E-mail:11121015@bjtu.edu.cn。