魏 明,孫 博,靳文舟
(1.南通大學(xué)交通學(xué)院,江蘇南通226019;2.華南理工大學(xué)土木與交通學(xué)院,廣州510640)
不確定性區(qū)域公交車調(diào)度問題的雙層規(guī)劃模型
魏 明*1,孫 博1,靳文舟2
(1.南通大學(xué)交通學(xué)院,江蘇南通226019;2.華南理工大學(xué)土木與交通學(xué)院,廣州510640)
區(qū)域公交調(diào)度是未來城市公共交通的發(fā)展趨勢,主要解決如何合理統(tǒng)一安排最初分布于不同車場的車輛完成所有線路固定時(shí)刻表對應(yīng)班次任務(wù),從而減少車隊(duì)規(guī)模和降低營運(yùn)成本.考慮現(xiàn)實(shí)中許多突發(fā)事件干擾車輛按時(shí)完成班次,借助雙層規(guī)劃模型,本文探討區(qū)域公交車輛調(diào)度和購車計(jì)劃之間的有機(jī)聯(lián)系,在滿足多車型、車場容量限制、燃料限制等現(xiàn)實(shí)因素基礎(chǔ)上,設(shè)計(jì)求解上下層模型的遺傳算法,引入滿意解的概念,將下層規(guī)劃產(chǎn)生的一組滿意解供上層規(guī)劃比選,進(jìn)而生成最佳公交車調(diào)度方案,以及與之對應(yīng)的購車計(jì)劃.最后給出了一個(gè)實(shí)例,驗(yàn)證模型和算法的正確性和有效性.
城市交通;區(qū)域公交車輛調(diào)度問題;購車計(jì)劃;雙層規(guī)劃;不確定性
區(qū)域公交車輛調(diào)度(RBSP)是當(dāng)今城市公共交通發(fā)展趨勢之一,根據(jù)某區(qū)域內(nèi)多條線路(上下行)在不同時(shí)段發(fā)車頻率的不均衡,考慮多車型[1-3]、燃料[3-6]、站場容量[1-4,7-9]等約束因素,通過車場內(nèi)或插入空駛班次實(shí)現(xiàn)車輛跨線調(diào)度,合理安排車輛完成不同線路時(shí)刻表的班次任務(wù),可以有效提高車輛利用效率.Bertossi等已證明RBSP為NP-hard問題[10].
上述RBSP研究僅保證車輛成本最優(yōu),整個(gè)公交系統(tǒng)涉及行車時(shí)刻表、車輛調(diào)度、駕駛員排班和購車計(jì)劃等眾多影響因素,各部分之間相互影響,各部分最優(yōu)未必可以保證系統(tǒng)最優(yōu).購車計(jì)劃是購買一定數(shù)量不同車型的公交車滿足公交企業(yè)日常運(yùn)營的用車需求,考慮不同車型污染氣體排放量等因素,顯然它影響公交車輛調(diào)度方案的生成過程.目前,國內(nèi)外學(xué)者鮮少探討公交車輛調(diào)度和車輛采購計(jì)劃之間存在著有機(jī)聯(lián)系,僅文獻(xiàn)[3,9]中探討了在購車預(yù)算和污染物排放量限制等約束條件下如何制定車輛調(diào)度方案使?fàn)I運(yùn)費(fèi)用最小;文獻(xiàn)[11]研究了一種區(qū)域公交車調(diào)度及購車計(jì)劃的雙層規(guī)劃模型,但其目標(biāo)函數(shù)涉及追求車輛數(shù)、空駛和等待時(shí)間最小,權(quán)重系數(shù)難以界定導(dǎo)致該模型無法在實(shí)際中應(yīng)用.此外,沒有考慮不確定因素干擾的RBSP,與實(shí)際應(yīng)用有一定差距,亟待研究編制一個(gè)公交方案適應(yīng)不斷變化的交通環(huán)境,具有重要的現(xiàn)實(shí)和理論價(jià)值.
因此,考慮交通擁堵、車輛事故等不確定因素引起的旅行時(shí)間變化,本文借鑒雙層規(guī)劃模型探討區(qū)域公交車輛調(diào)度和購車計(jì)劃之間的有機(jī)聯(lián)系,其中:在上層規(guī)劃中,考慮每車型至少有一輛車、污染氣體排放限制等因素,編制一個(gè)購車費(fèi)用最少的購車計(jì)劃;在下層規(guī)劃中,在滿足車場容量和補(bǔ)充燃料等約束因素下,制定一組較低營運(yùn)費(fèi)用的車輛調(diào)度方案,將它們供上層規(guī)劃比選,進(jìn)而生成最佳公交車調(diào)度方案及與之對應(yīng)的購車計(jì)劃.
2.1 購車計(jì)劃問題的上層規(guī)劃模型
2.1.1 假設(shè)
(1)相關(guān)政府部門制定污染氣體排放標(biāo)準(zhǔn),即每種污染氣體的排放總量限制在一定范圍內(nèi).
(2)在單位時(shí)間內(nèi)不同公交車型的各種污染氣體排放量恒定,可查閱車輛技術(shù)文件找到它們的相關(guān)值.
(3)任意類型公交車的污染氣體排放量僅與它的實(shí)際工作(行駛)時(shí)間相關(guān).
2.1.2 決策變量
xij為車輛i是否為車型j.
2.1.3 參數(shù)
M為車輛集合; N為車型集合;
O為污染氣體集合;
wi為車輛i的實(shí)際工作時(shí)間;
cj為車型j的車輛價(jià)格;
Uo為某污染氣體o∈O的排放量上限;
eoj為第j類型車輛在單位小時(shí)排放某污染氣體o∈O的排放量.
2.1.4 目標(biāo)函數(shù)
2.1.5 約束條件
當(dāng)下層規(guī)劃問題編制車輛調(diào)度方案的用車需求可知時(shí),在上層規(guī)劃(U)模型中,式(1)是U的目標(biāo)函數(shù),表示購買公交車輛的費(fèi)用最少,其中映射S(T)→M將L的決策變量和轉(zhuǎn)化為U的輸入和任意車輛?i∈M的工作時(shí)間;式(2)-式(4)是問題的約束條件,其中:式(2)表示每輛車僅對應(yīng)一類車型,式(3)每車型至少有一輛車,式(4)表示所有公交車嚴(yán)格要求某污染氣體排放量不超過它的上限.
2.2 區(qū)域公交車輛調(diào)度問題的下層規(guī)劃模型
2.2.1 假設(shè)
(1)所有班次要求全部車輛準(zhǔn)時(shí)從相應(yīng)車場出發(fā)開始任務(wù),通過分析相關(guān)歷史數(shù)據(jù)可獲取車輛完成它們的延誤時(shí)間的均值和方差.
(2)全部車輛從車場加滿油開始它們的首班次任務(wù),其燃料消耗與駕駛員行為習(xí)慣和交通擁堵沒有聯(lián)系,僅與里程數(shù)相關(guān).
2.2.3 參數(shù)
T={T1,T2,…,T|T|}表示不同線路的固定時(shí)刻表的班次集合T={T1,T2,…,T|T|},對?Ti∈T要求車輛在時(shí)間stTi從某車場spTi出發(fā)和在終止時(shí)刻etTi到達(dá)車場dpTi.
D和K分別表示車場和車輛類型集合, capacityd為車場?d∈D的容量限制,為車場?d∈D出發(fā)的車型?k∈K的車輛集合.
若dis(dpxi-1,spxi)≠0,車輛從的終點(diǎn)車場空車駛向的始發(fā)車場情況為空駛班次(Deadhead Trip,DH Trip).
STk和DDk分別表示車型?k∈K的車輛補(bǔ)充燃料花費(fèi)時(shí)間和最大行駛里程.
|x|表示集合x的元素?cái)?shù)量.
2.2.4 目標(biāo)函數(shù)
2.2.5 約束條件
在下層規(guī)劃(L)模型中,式(5)是下層規(guī)劃問題的目標(biāo)函數(shù),表示極小化營運(yùn)成本,前三項(xiàng)分別為車輛、空駛里程及固定里程費(fèi)用,其中映射f2(T)→S(T)為L合理安排車輛完成T的一個(gè)可行解,即Vkd和Tld;式(6)-式(11)是問題的約束條件,其中:式(6)表示任意一輛車僅屬于一個(gè)車場,式(7)確保所有班次都被車輛執(zhí)行,式(8)表示任意一輛車同時(shí)只能執(zhí)行一個(gè)班次,一個(gè)班次只能被一輛車執(zhí)行,式(9)保證任意時(shí)刻車輛入車場滿足其容量限制,式(10)保證車輛有足夠的燃料(相應(yīng)車場補(bǔ)充燃料)繼續(xù)完成任務(wù),式(11)確保某車輛可正常依次完成兩班次的概率不小于置信水平α.
式(11)等價(jià)于Pr(-μxi-1/δxi-1≤ΔT′xi-1≤DT)≥α,對應(yīng)確定性表達(dá)式如下:
式中 ΔT′xi-1服從標(biāo)準(zhǔn)正態(tài)分布;φ-1(x)可通過查找正態(tài)分布表獲取.
由上可知,U的xij和M和wi與L的和之間是有機(jī)聯(lián)系,即受約束條件(4)限制的M直接和間接影響和,當(dāng)被確定后計(jì)算M和任意車輛?i∈M的工作時(shí)間wi,確定xij,從而決定.
根據(jù)問題特征,將該問題轉(zhuǎn)化為不同車輛數(shù)下的上下層模型求解,設(shè)計(jì)求解它們的遺傳算法,算法的基本思路為:初始化參數(shù),先從L著手生成一系列符合滿意度指標(biāo)的可行解,比較L的每個(gè)解對應(yīng)U的目標(biāo)值,從而找到該雙層規(guī)劃的最優(yōu)解.
3.1 染色體結(jié)構(gòu)設(shè)計(jì)
該雙層規(guī)劃問題的一個(gè)潛在解的染色可用二維向量X=(XU,XL)表示,其中:XU=(x1,x2,…, x|M|)表示U的一個(gè)潛在解,其元素xi(取值為1~|N|之間的整數(shù))表示第i車的采購車型;XL=(x1,x2,···,x|T|)表示L的一個(gè)潛在解,元素xi(取值為1~|M|之間的整數(shù))表示完成第i班次的車輛編號,各班次在同一車輛的服務(wù)順序由它們的發(fā)車時(shí)刻決定.
例如:3種車型、5輛車和10個(gè)班次的U和L的一個(gè)解分別為XU=[1 2 3 1 2]和XL=[1 2 1 1 3 4 2 1 5],它們蘊(yùn)含為車輛1完成第1、3、4、6和8班次,車輛2完成第2和7班次,車輛3、4和5分別執(zhí)行第5、6和9班次,其中車1和4的車型為1,車2和5的車型為2,車3的車型為3.
3.2 適應(yīng)度函數(shù)設(shè)計(jì)
因?yàn)長的決策變量Tld影響U的xij,而U蘊(yùn)含的決策變量xij又決定f2,故將相互關(guān)聯(lián)的L的f1和U的f2作為一個(gè)整體,構(gòu)造L和U相應(yīng)的適應(yīng)度函數(shù)如下:
根據(jù)算法思路,當(dāng)先生成一系列L的解時(shí),因 XL沒確定車輛類型,令和DDk=滿足約束(10)和(11),且式(14)取決于公交調(diào)度方案的總空駛里程.
定義1 L的方案集合X=(X1,X2,…,Xn)的標(biāo)準(zhǔn)差為,記r(X)= 1-σ(X)為最優(yōu)方案X*∈X附近的任意方案?Xi∈X的滿意度,其中favg是所有方案的均值.
根據(jù)定義1,L的r(X)越高越減少X的多樣性,從而各種次優(yōu)方案?Xi∈X不斷逼近X*,作為二層規(guī)劃算法的過濾器,這就在不增加計(jì)算量的前提下,進(jìn)一步保證了模型結(jié)果的整體最優(yōu)性.
3.3 產(chǎn)生初始種群
對于上層規(guī)劃,在不遵守式(4)情形下隨機(jī)產(chǎn)生的XU是一個(gè)不可行解,設(shè)計(jì)啟發(fā)式算法生成可行個(gè)體,組成求解該問題的遺傳算法初始種群.啟發(fā)式算法的具體步驟如下:
步驟1設(shè)置M=XU,N={1,2,…,|N|}及任意污染氣體?o∈O的排放量Uo′=Uo.
步驟2查找任意車輛?i∈M的可行車型集合N′?N(令N′=?,對?o∈O,若?u∈N且?v∈N滿足,則N′=N′∪{u}).隨機(jī)選擇某車型?k∈N′,對應(yīng)可行解向量XU的元素xi=k,令?o∈O的Uo′=Uo′-eokti及M=M-{i}.
步驟3若M≠?,轉(zhuǎn)至步驟2;否則,算法終止并輸出結(jié)果.
對于下層規(guī)劃,RBSP涉及的眾多因素是強(qiáng)約束,隨機(jī)產(chǎn)生的XL是一個(gè)可行個(gè)體的概率很低,設(shè)計(jì)啟發(fā)式算法求得不同可行個(gè)體,組成求解該問題的遺傳算法初始種群.啟發(fā)式算法的具體步驟如下:
步驟1對班次集合T根據(jù)?Ti∈T的stTi進(jìn)行升序排序,獲取T′={T′1,T′2,…,T′|T|}.
步驟2設(shè)置完成所有班次T′的車輛集合M ={1,2,...,|M|},令i=1.
步驟3查找可以完成T′i的車輛集合uV(詳細(xì)過程如操作步驟3.1-3.2所示),若uV≠?,從中隨機(jī)選擇車輛?k∈uV完成T′i,對應(yīng)可行解向量XL的元素xT′i=k,轉(zhuǎn)至步驟4;否則,轉(zhuǎn)至步驟2.
步驟3.1查找當(dāng)前每輛車?k∈M完成的最后一個(gè)班次lT(k),設(shè)置uV=?.
步驟3.2對每輛車?k∈M是否能完成T′,遵從式(9)-式(11)約束,若滿足lT(k)=?或φ-1(α′)≤ψ(lT(k),T′i),則uV=uV∪{k}.
步驟4令i=i+1,若i≤|T|,轉(zhuǎn)至步驟3;否則,算法終止輸出結(jié)果.
3.4 遺傳操作
遺傳操作[13]包括選擇、交叉和變異三種基本運(yùn)算,本文采用輪盤賭選擇法和精英保留法組合的選擇策略,從當(dāng)前父代群體中選出優(yōu)良的個(gè)體繁殖下一代;對交叉運(yùn)算以一定概率根據(jù)單點(diǎn)交叉算子從一組父輩個(gè)體染色體對應(yīng)基因段的交換產(chǎn)生一組新個(gè)體;對變異運(yùn)算根據(jù)基本位變異算子對個(gè)體的每一個(gè)基因做依據(jù)變異概率判斷是否為變異點(diǎn),對變異點(diǎn)做相關(guān)運(yùn)算產(chǎn)生出新個(gè)體,避免由于選擇和交叉運(yùn)算而造成的某些信息損失,從而維持群體多樣性.
顯然,對個(gè)體進(jìn)行交叉和變異操作可能破壞U和L的可行解結(jié)構(gòu),產(chǎn)生的這些不可行個(gè)體被舍棄.
3.5 終止規(guī)則
當(dāng)遺傳算法求解U和L時(shí),若種群完成預(yù)先給定的進(jìn)化代數(shù),算法終止.
某公司在同一區(qū)域內(nèi)的3個(gè)車場經(jīng)營5條線路(capacityd=15,d=1,2,3),擬采購一定數(shù)量的3種車型公交車完成所有公交班次,使污染氣體NOx、CO、HC及CO2的排放量分別限制在范圍0~195 kg、0~335 kg、0~35 kg及0~4 200 kg.已知:不同車型信息如表1所示,每條公交線路及固定時(shí)刻表如表2和表3所示,各車場之間空駛信息如表4所示,部分車輛完成某班次產(chǎn)生的隨機(jī)延誤時(shí)間如表5所示,相關(guān)參數(shù)和.設(shè)定方案的滿意度評價(jià)指標(biāo)r(X)=0.85.
表1 公交車輛信息Table 1 Vehicles information
表2 公交線路信息Table 2 Routes information
表3 行車時(shí)刻表Table 3 Timetable of routes information
本小節(jié)采用Sheffield的遺傳算法matlab工具箱函數(shù)編寫求解上下層規(guī)劃的程序,設(shè)置相關(guān)參數(shù)如下:最大迭代次數(shù)為10 000,染色體數(shù)為100,交叉率為0.7,變異率為0.05,在α取0.9情形下對車輛數(shù)為23(無解)、24、25、26、27及28每種情形下均運(yùn)行50次,計(jì)算它們各自的上下層規(guī)劃的最佳方案.結(jié)果如表6和表7所示,從中可知:
(1)隨著車輛數(shù)增加,不同下層方案的所有車輛的總等待時(shí)間增多,空駛時(shí)間的稍微減少,使總行駛時(shí)間差別不大.因不同車型的各種污染氣體排放量是矛盾的,所以上層方案需購買一定數(shù)量的V3才滿足各種污染氣體最大排放量限制,導(dǎo)致購車費(fèi)用逐漸變多.
(2)此外,隨著車輛數(shù)增加,不同下層方案的空駛里程減少,但車輛固定成本增加幅度大于燃料消耗費(fèi)用,從而它們的營運(yùn)費(fèi)用也逐漸變大.
表4 空駛信息一覽表Table 4 Deadhead information
表5 部分車輛完成某班次的隨機(jī)延誤時(shí)間Table 5 Some of stochastic delay time of a vehicle completing a trip
表6 不同車輛數(shù)下層規(guī)劃的最佳方案Table 6 The optimal solution to lower level plan under different number of vehicles circumstances
表7 不同車輛數(shù)上層規(guī)劃的最佳方案Table 7 The optimal solution to upper level plan under different number of vehicles circumstances
表8 最佳車輛調(diào)度方案Table 8 Results of vehicles arrangements
因此,隨著車輛數(shù)增加,模型總費(fèi)用逐漸變大,從而方案1是問題最佳解.方案1為模型最優(yōu)解,對應(yīng)車輛調(diào)度方案如表8所示,總共需派遣24輛車(從車場A、B和C初始出發(fā)的車輛數(shù)為6、11和7),經(jīng)加油27次(車場A加油7次、車場B加油10次和車場C加油10次)和空駛98次(A空駛至B為33次,A空駛至C為33次,B空駛至A為6次, B空駛至C為5次,C空駛至A為6次,C空駛至B為20次),可以完成211個(gè)班次,所有車輛的總行駛、等待及空駛時(shí)間分別為14 445 min、3 340 min和1 950 min,不同污染氣體NOx、CO、HC及CO2的總排放量分別為94.0 kg、255.9 kg、34.9 kg和4 199.9 kg.
借鑒不確定雙層規(guī)劃理論,考慮車場容量、燃料限制及各種污染氣體最大排放量等約束因素,本文探討區(qū)域公交車輛調(diào)度和購車計(jì)劃之間的有機(jī)聯(lián)系,將該問題轉(zhuǎn)化為不同車輛數(shù)下的上下層模型求解,嘗試解決如何生成最佳公交車調(diào)度方案及與之對應(yīng)的購車計(jì)劃,使之適應(yīng)不斷變化的交通環(huán)境,從而更容易在實(shí)際中應(yīng)用.仿真表明:隨著車輛數(shù)增加,不同下層方案的營運(yùn)費(fèi)用也逐漸變大,因它們的總車輛行駛時(shí)間差別不大,導(dǎo)致上層方案需購買一定數(shù)量的V3才滿足各種污染氣體最大排放量限制,從而上層方案購車費(fèi)用也逐漸變多.
但是整個(gè)公交系統(tǒng)涉及因素眾多,僅尋求區(qū)域公交車輛調(diào)度和購車計(jì)劃之間的最佳關(guān)聯(lián),也未必保證從系統(tǒng)的角度公交行車計(jì)劃是最優(yōu)的.此外,當(dāng)突發(fā)事件致使公交車調(diào)度方案失效時(shí),如何亟待尋求實(shí)時(shí)調(diào)整一個(gè)可行的公交車輛調(diào)度方案以適應(yīng)不斷變化環(huán)境,據(jù)此編制一個(gè)整體最優(yōu)的公交行車計(jì)劃將是今后進(jìn)一步研究的方向.
[1] Natalia K,Taieb M,Leena S.A time-space network based exact optimization model for multi-depot bus scheduling[J].European Journal ofOperational Research,2006,175:1616-1627.
[2] Vitali G,Natalia K,Leena S.Solving large multipledepot multiple-vehicle-type bus scheduling problems in practice[J].OR Spectrum,2005,27:507-523.
[3] Wei M,Jin,W Z,Fu W W,et al.Improved ant colony algorithm for multiple depot bus scheduling problem with route time constraints[C].8th World Congress on Intelligent Control and Automation,2010:4050-4053.
[4] 劉志剛,申金生.區(qū)域公交時(shí)刻表及車輛調(diào)度雙層規(guī)劃模型[J].系統(tǒng)工程理論與實(shí)踐,2007,27 (11):135-141.[LIU Z G,SHEN J S.Regional bus operationbi-levelprogrammingmodelintegrating timetabling andvehiclescheduling[J].System Engineering Theory&Practice,2007,27(11):135-141.]
[5] Haghani A,Banihashemi M.Heuristic approaches for solving large-scalebustransitvehiclescheduling problemwithroutetimeconstraints[J]. Transportation Research,2002,36:309-333.
[6] Wang H,Shen J.Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints[J].Applied Mathematics and Computation,2007,190:1237-1249.
[7] Li J Q,Mirchandani P B,Borenstein D.A Heuristic for the real-time vehicle rescheduling problem[J]. Transportation ResearchPartE,2009,45(3): 419-433.
[8] Dennis H,Albert P M.A solution approach for dynamic vehicle and crew scheduling[J].European Journal of Operational Research,2006,172:453-471. [9] Li J Q,Head K L.Sustainability provisions in the busscheduling problem[J].Transportation Research Part D,2009,12:50-60.
[10] Bertoss A A,Carraresi P,Gallo G.On some matching problems arising in vehicle scheduling models[J]. NetWorks,1987,17(3):271-281.
[11] 魏明,靳文舟,孫博.區(qū)域公交車輛調(diào)度問題的可靠性.華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,42 (2):46-53.[WEI M,JIN W Z,SUN B.Reliability study in regional bus scheduling problem[J].Journal of South China University of Technology(Natural Science Edition),2012,42(2):46-53.]
[12] Liu BD.Theory and practice of uncertain programming [M].UTLAB,2008.
[13] 雷英杰,等.Matlab遺傳算法工具箱及應(yīng)用[M].西安電子科技大學(xué)出版社,2005.[LEI Y J,ZHANG S W.Genetic algorithmtoolboxandapplicationof MATLAB[M].Xidian University Press,2005.]
A Bi-level Programming Model for Uncertain Regional Bus Scheduling Problems
WEI Ming1,SUN Bo1,JIN Wen-zhou2
(1.School of Transportation,Nantong University,Nantong 226019,Jiangsu,China; 2.School of Civil Engineering and Transportation,South China University of Technology,Guangzhou 510640,China)
Regional bus scheduling is the future trend in public transportation which deals with allocating trips belonged to several routes to buses located at different depots to reduce the size of bus fleets and operating costs.Considering many emergency events which may affect on-time vehicle arrivals,a bi-level programming model is applied to address the relationship between bus scheduling and its procurement scheme from an overall perspective.The model takes into consideration several constraints such as depot capacities, fueling,and emissions of polluting gases.Solutions to different situations of the upper and lower model are obtained by using a genetic algorithm.Based on some established criteria for a satisfactory solution,the lower solutions meeting the established criteria are generated for the upper model.Thereby,the best lower and the corresponding upper solutions are generated.Finally,an example is illustrated to prove the accuracy and effectiveness of our model and its algorithm.
urban traffic;regional bus scheduling problem;bus procurement scheme;bi-level programming model;uncertainty
TP301.6;U116.2Document code: A
TP301.6;U116.2
A
1009-6744(2013)04-0106-08
2012-09-17
2012-11-24錄用日期:2012-12-13
國家“863”高技術(shù)計(jì)劃資助項(xiàng)目(2007AA11Z201);國家自然科學(xué)基金資助項(xiàng)目(61174188);華南理工大學(xué)中央高校基本科研業(yè)務(wù)費(fèi)資助項(xiàng)目(2012ZM0092).
魏明(1984-),男,安徽蕪湖人,講師,工學(xué)博士.
*通訊作者:mingtian911@163.com