魏 明,孫 博,靳文舟

(1.南通大學交通學院,江蘇南通226019;2.華南理工大學土木與交通學院,廣州510640)

不確定性區(qū)域公交車調度問題的雙層規(guī)劃模型

魏 明*1,孫 博1,靳文舟2

(1.南通大學交通學院,江蘇南通226019;2.華南理工大學土木與交通學院,廣州510640)

區(qū)域公交調度是未來城市公共交通的發(fā)展趨勢,主要解決如何合理統(tǒng)一安排最初分布于不同車場的車輛完成所有線路固定時刻表對應班次任務,從而減少車隊規(guī)模和降低營運成本.考慮現實中許多突發(fā)事件干擾車輛按時完成班次,借助雙層規(guī)劃模型,本文探討區(qū)域公交車輛調度和購車計劃之間的有機聯(lián)系,在滿足多車型、車場容量限制、燃料限制等現實因素基礎上,設計求解上下層模型的遺傳算法,引入滿意解的概念,將下層規(guī)劃產生的一組滿意解供上層規(guī)劃比選,進而生成最佳公交車調度方案,以及與之對應的購車計劃.最后給出了一個實例,驗證模型和算法的正確性和有效性.

城市交通;區(qū)域公交車輛調度問題;購車計劃;雙層規(guī)劃;不確定性

1 引 言

區(qū)域公交車輛調度(RBSP)是當今城市公共交通發(fā)展趨勢之一,根據某區(qū)域內多條線路(上下行)在不同時段發(fā)車頻率的不均衡,考慮多車型[1-3]、燃料[3-6]、站場容量[1-4,7-9]等約束因素,通過車場內或插入空駛班次實現車輛跨線調度,合理安排車輛完成不同線路時刻表的班次任務,可以有效提高車輛利用效率.Bertossi等已證明RBSP為NP-hard問題[10].

上述RBSP研究僅保證車輛成本最優(yōu),整個公交系統(tǒng)涉及行車時刻表、車輛調度、駕駛員排班和購車計劃等眾多影響因素,各部分之間相互影響,各部分最優(yōu)未必可以保證系統(tǒng)最優(yōu).購車計劃是購買一定數量不同車型的公交車滿足公交企業(yè)日常運營的用車需求,考慮不同車型污染氣體排放量等因素,顯然它影響公交車輛調度方案的生成過程.目前,國內外學者鮮少探討公交車輛調度和車輛采購計劃之間存在著有機聯(lián)系,僅文獻[3,9]中探討了在購車預算和污染物排放量限制等約束條件下如何制定車輛調度方案使營運費用最小;文獻[11]研究了一種區(qū)域公交車調度及購車計劃的雙層規(guī)劃模型,但其目標函數涉及追求車輛數、空駛和等待時間最小,權重系數難以界定導致該模型無法在實際中應用.此外,沒有考慮不確定因素干擾的RBSP,與實際應用有一定差距,亟待研究編制一個公交方案適應不斷變化的交通環(huán)境,具有重要的現實和理論價值.

因此,考慮交通擁堵、車輛事故等不確定因素引起的旅行時間變化,本文借鑒雙層規(guī)劃模型探討區(qū)域公交車輛調度和購車計劃之間的有機聯(lián)系,其中:在上層規(guī)劃中,考慮每車型至少有一輛車、污染氣體排放限制等因素,編制一個購車費用最少的購車計劃;在下層規(guī)劃中,在滿足車場容量和補充燃料等約束因素下,制定一組較低營運費用的車輛調度方案,將它們供上層規(guī)劃比選,進而生成最佳公交車調度方案及與之對應的購車計劃.

2 問題描述及數學模型

2.1 購車計劃問題的上層規(guī)劃模型

2.1.1 假設

(1)相關政府部門制定污染氣體排放標準,即每種污染氣體的排放總量限制在一定范圍內.

(2)在單位時間內不同公交車型的各種污染氣體排放量恒定,可查閱車輛技術文件找到它們的相關值.

(3)任意類型公交車的污染氣體排放量僅與它的實際工作(行駛)時間相關.

2.1.2 決策變量

xij為車輛i是否為車型j.

2.1.3 參數

M為車輛集合; N為車型集合;

O為污染氣體集合;

wi為車輛i的實際工作時間;

cj為車型j的車輛價格;

Uo為某污染氣體o∈O的排放量上限;

eoj為第j類型車輛在單位小時排放某污染氣體o∈O的排放量.

2.1.4 目標函數

2.1.5 約束條件

當下層規(guī)劃問題編制車輛調度方案的用車需求可知時,在上層規(guī)劃(U)模型中,式(1)是U的目標函數,表示購買公交車輛的費用最少,其中映射S(T)→M將L的決策變量和轉化為U的輸入和任意車輛?i∈M的工作時間;式(2)-式(4)是問題的約束條件,其中:式(2)表示每輛車僅對應一類車型,式(3)每車型至少有一輛車,式(4)表示所有公交車嚴格要求某污染氣體排放量不超過它的上限.

2.2 區(qū)域公交車輛調度問題的下層規(guī)劃模型

2.2.1 假設

(1)所有班次要求全部車輛準時從相應車場出發(fā)開始任務,通過分析相關歷史數據可獲取車輛完成它們的延誤時間的均值和方差.

(2)全部車輛從車場加滿油開始它們的首班次任務,其燃料消耗與駕駛員行為習慣和交通擁堵沒有聯(lián)系,僅與里程數相關.

2.2.3 參數

T={T1,T2,…,T|T|}表示不同線路的固定時刻表的班次集合T={T1,T2,…,T|T|},對?Ti∈T要求車輛在時間stTi從某車場spTi出發(fā)和在終止時刻etTi到達車場dpTi.

D和K分別表示車場和車輛類型集合, capacityd為車場?d∈D的容量限制,為車場?d∈D出發(fā)的車型?k∈K的車輛集合.

若dis(dpxi-1,spxi)≠0,車輛從的終點車場空車駛向的始發(fā)車場情況為空駛班次(Deadhead Trip,DH Trip).

STk和DDk分別表示車型?k∈K的車輛補充燃料花費時間和最大行駛里程.

|x|表示集合x的元素數量.

2.2.4 目標函數

2.2.5 約束條件

在下層規(guī)劃(L)模型中,式(5)是下層規(guī)劃問題的目標函數,表示極小化營運成本,前三項分別為車輛、空駛里程及固定里程費用,其中映射f2(T)→S(T)為L合理安排車輛完成T的一個可行解,即Vkd和Tld;式(6)-式(11)是問題的約束條件,其中:式(6)表示任意一輛車僅屬于一個車場,式(7)確保所有班次都被車輛執(zhí)行,式(8)表示任意一輛車同時只能執(zhí)行一個班次,一個班次只能被一輛車執(zhí)行,式(9)保證任意時刻車輛入車場滿足其容量限制,式(10)保證車輛有足夠的燃料(相應車場補充燃料)繼續(xù)完成任務,式(11)確保某車輛可正常依次完成兩班次的概率不小于置信水平α.

式(11)等價于Pr(-μxi-1/δxi-1≤ΔT′xi-1≤DT)≥α,對應確定性表達式如下:

式中 ΔT′xi-1服從標準正態(tài)分布;φ-1(x)可通過查找正態(tài)分布表獲取.

3 算法設計

由上可知,U的xij和M和wi與L的和之間是有機聯(lián)系,即受約束條件(4)限制的M直接和間接影響和,當被確定后計算M和任意車輛?i∈M的工作時間wi,確定xij,從而決定.

根據問題特征,將該問題轉化為不同車輛數下的上下層模型求解,設計求解它們的遺傳算法,算法的基本思路為:初始化參數,先從L著手生成一系列符合滿意度指標的可行解,比較L的每個解對應U的目標值,從而找到該雙層規(guī)劃的最優(yōu)解.

3.1 染色體結構設計

該雙層規(guī)劃問題的一個潛在解的染色可用二維向量X=(XU,XL)表示,其中:XU=(x1,x2,…, x|M|)表示U的一個潛在解,其元素xi(取值為1～|N|之間的整數)表示第i車的采購車型;XL=(x1,x2,···,x|T|)表示L的一個潛在解,元素xi(取值為1～|M|之間的整數)表示完成第i班次的車輛編號,各班次在同一車輛的服務順序由它們的發(fā)車時刻決定.

例如:3種車型、5輛車和10個班次的U和L的一個解分別為XU=[1 2 3 1 2]和XL=[1 2 1 1 3 4 2 1 5],它們蘊含為車輛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 適應度函數設計

因為L的決策變量Tld影響U的xij,而U蘊含的決策變量xij又決定f2,故將相互關聯(lián)的L的f1和U的f2作為一個整體,構造L和U相應的適應度函數如下:

根據算法思路,當先生成一系列L的解時,因 XL沒確定車輛類型,令和DDk=滿足約束(10)和(11),且式(14)取決于公交調度方案的總空駛里程.

定義1 L的方案集合X=(X1,X2,…,Xn)的標準差為,記r(X)= 1-σ(X)為最優(yōu)方案X*∈X附近的任意方案?Xi∈X的滿意度,其中favg是所有方案的均值.

根據定義1,L的r(X)越高越減少X的多樣性,從而各種次優(yōu)方案?Xi∈X不斷逼近X*,作為二層規(guī)劃算法的過濾器,這就在不增加計算量的前提下,進一步保證了模型結果的整體最優(yōu)性.

3.3 產生初始種群

對于上層規(guī)劃,在不遵守式(4)情形下隨機產生的XU是一個不可行解,設計啟發(fā)式算法生成可行個體,組成求解該問題的遺傳算法初始種群.啟發(fā)式算法的具體步驟如下:

步驟1設置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}).隨機選擇某車型?k∈N′,對應可行解向量XU的元素xi=k,令?o∈O的Uo′=Uo′-eokti及M=M-{i}.

步驟3若M≠?,轉至步驟2;否則,算法終止并輸出結果.

對于下層規(guī)劃,RBSP涉及的眾多因素是強約束,隨機產生的XL是一個可行個體的概率很低,設計啟發(fā)式算法求得不同可行個體,組成求解該問題的遺傳算法初始種群.啟發(fā)式算法的具體步驟如下:

步驟1對班次集合T根據?Ti∈T的stTi進行升序排序,獲取T′={T′1,T′2,…,T′|T|}.

步驟2設置完成所有班次T′的車輛集合M ={1,2,...,|M|},令i=1.

步驟3查找可以完成T′i的車輛集合uV(詳細過程如操作步驟3.1-3.2所示),若uV≠?,從中隨機選擇車輛?k∈uV完成T′i,對應可行解向量XL的元素xT′i=k,轉至步驟4;否則,轉至步驟2.

步驟3.1查找當前每輛車?k∈M完成的最后一個班次lT(k),設置uV=?.

步驟3.2對每輛車?k∈M是否能完成T′,遵從式(9)-式(11)約束,若滿足lT(k)=?或φ-1(α′)≤ψ(lT(k),T′i),則uV=uV∪{k}.

步驟4令i=i+1,若i≤|T|,轉至步驟3;否則,算法終止輸出結果.

3.4 遺傳操作

遺傳操作[13]包括選擇、交叉和變異三種基本運算,本文采用輪盤賭選擇法和精英保留法組合的選擇策略,從當前父代群體中選出優(yōu)良的個體繁殖下一代;對交叉運算以一定概率根據單點交叉算子從一組父輩個體染色體對應基因段的交換產生一組新個體;對變異運算根據基本位變異算子對個體的每一個基因做依據變異概率判斷是否為變異點,對變異點做相關運算產生出新個體,避免由于選擇和交叉運算而造成的某些信息損失,從而維持群體多樣性.

顯然,對個體進行交叉和變異操作可能破壞U和L的可行解結構,產生的這些不可行個體被舍棄.

3.5 終止規(guī)則

當遺傳算法求解U和L時,若種群完成預先給定的進化代數,算法終止.

4 算例分析

某公司在同一區(qū)域內的3個車場經營5條線路(capacityd=15,d=1,2,3),擬采購一定數量的3種車型公交車完成所有公交班次,使污染氣體NOx、CO、HC及CO2的排放量分別限制在范圍0～195 kg、0～335 kg、0～35 kg及0～4 200 kg.已知:不同車型信息如表1所示,每條公交線路及固定時刻表如表2和表3所示,各車場之間空駛信息如表4所示,部分車輛完成某班次產生的隨機延誤時間如表5所示,相關參數和.設定方案的滿意度評價指標r(X)=0.85.

表1 公交車輛信息Table 1 Vehicles information

表2 公交線路信息Table 2 Routes information

表3 行車時刻表Table 3 Timetable of routes information

本小節(jié)采用Sheffield的遺傳算法matlab工具箱函數編寫求解上下層規(guī)劃的程序,設置相關參數如下:最大迭代次數為10 000,染色體數為100,交叉率為0.7,變異率為0.05,在α取0.9情形下對車輛數為23(無解)、24、25、26、27及28每種情形下均運行50次,計算它們各自的上下層規(guī)劃的最佳方案.結果如表6和表7所示,從中可知:

(1)隨著車輛數增加,不同下層方案的所有車輛的總等待時間增多,空駛時間的稍微減少,使總行駛時間差別不大.因不同車型的各種污染氣體排放量是矛盾的,所以上層方案需購買一定數量的V3才滿足各種污染氣體最大排放量限制,導致購車費用逐漸變多.

(2)此外,隨著車輛數增加,不同下層方案的空駛里程減少,但車輛固定成本增加幅度大于燃料消耗費用,從而它們的營運費用也逐漸變大.

表4 空駛信息一覽表Table 4 Deadhead information

表5 部分車輛完成某班次的隨機延誤時間Table 5 Some of stochastic delay time of a vehicle completing a trip

表6 不同車輛數下層規(guī)劃的最佳方案Table 6 The optimal solution to lower level plan under different number of vehicles circumstances

表7 不同車輛數上層規(guī)劃的最佳方案Table 7 The optimal solution to upper level plan under different number of vehicles circumstances

表8 最佳車輛調度方案Table 8 Results of vehicles arrangements

因此,隨著車輛數增加,模型總費用逐漸變大,從而方案1是問題最佳解.方案1為模型最優(yōu)解,對應車輛調度方案如表8所示,總共需派遣24輛車(從車場A、B和C初始出發(fā)的車輛數為6、11和7),經加油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個班次,所有車輛的總行駛、等待及空駛時間分別為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.

5 研究結論

借鑒不確定雙層規(guī)劃理論,考慮車場容量、燃料限制及各種污染氣體最大排放量等約束因素,本文探討區(qū)域公交車輛調度和購車計劃之間的有機聯(lián)系,將該問題轉化為不同車輛數下的上下層模型求解,嘗試解決如何生成最佳公交車調度方案及與之對應的購車計劃,使之適應不斷變化的交通環(huán)境,從而更容易在實際中應用.仿真表明:隨著車輛數增加,不同下層方案的營運費用也逐漸變大,因它們的總車輛行駛時間差別不大,導致上層方案需購買一定數量的V3才滿足各種污染氣體最大排放量限制,從而上層方案購車費用也逐漸變多.

但是整個公交系統(tǒng)涉及因素眾多,僅尋求區(qū)域公交車輛調度和購車計劃之間的最佳關聯(lián),也未必保證從系統(tǒng)的角度公交行車計劃是最優(yōu)的.此外,當突發(fā)事件致使公交車調度方案失效時,如何亟待尋求實時調整一個可行的公交車輛調度方案以適應不斷變化環(huán)境,據此編制一個整體最優(yōu)的公交行車計劃將是今后進一步研究的方向.

[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ū)域公交時刻表及車輛調度雙層規(guī)劃模型[J].系統(tǒng)工程理論與實踐,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ū)域公交車輛調度問題的可靠性.華南理工大學學報(自然科學版),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遺傳算法工具箱及應用[M].西安電子科技大學出版社,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”高技術計劃資助項目(2007AA11Z201);國家自然科學基金資助項目(61174188);華南理工大學中央高?；究蒲袠I(yè)務費資助項目(2012ZM0092).

魏明(1984-),男,安徽蕪湖人,講師,工學博士.

*通訊作者:mingtian911@163.com