基于NSGA算法的公交車輛調(diào)度優(yōu)化模型

宋曉鵬， 韓 印， 姚 佼

（上海理工大學(xué)管理學(xué)院，上海 200093）

基于NSGA算法的公交車輛調(diào)度優(yōu)化模型

宋曉鵬， 韓 印， 姚 佼

（上海理工大學(xué)管理學(xué)院，上海 200093）

公交車輛調(diào)度方案的優(yōu)化對于提高公交服務(wù)水平，促進(jìn)公交事業(yè)的快速發(fā)展至關(guān)重要.在乘客與公交公司利益博弈的基礎(chǔ)上，基于極小極大思想，考慮公交車車輛容量的限制及城市道路信號控制的干擾因素，建立公交發(fā)車間隔優(yōu)化模型，并利用非支配排序遺傳算法（NSGA）進(jìn)行模型的求解.以河南省焦作市的公交線路為例進(jìn)行驗證，優(yōu)化結(jié)果顯示乘客的平均等車時間相對減少48.3%，公交車的全日平均滿載率下降了3.8%，公交服務(wù)水平有所改善.

城市公交；發(fā)車間隔；等車時間；非支配排序遺傳算法

優(yōu)先發(fā)展城市公共交通是提高交通資源利用效率、緩解交通擁堵的重要手段.作為城市交通的主要通行方式，公共交通服務(wù)水平與居民出行需求和城市交通運行狀態(tài)息息相關(guān).優(yōu)化發(fā)車間隔是公交調(diào)度的主要技術(shù)手段.準(zhǔn)確和高效率的發(fā)車調(diào)度對提高公交線路的服務(wù)能力，減少居民的出行延誤，提高乘客滿意度有著重要意義.Huisman等［1］提出了用于描述多場站調(diào)度問題的動態(tài)模型，并應(yīng)用“聚類再生成”啟發(fā)式算法，基于數(shù)學(xué)規(guī)劃模型得出優(yōu)化的結(jié)果，但對公交車容量未作考慮.孫芙靈［2］根據(jù)乘客需求來確定發(fā)車間隔，用數(shù)學(xué)規(guī)劃的思想建立調(diào)度模型，并用時間步長法、等效法進(jìn)行求解，得出仿真結(jié)果，但對公交公司利益考慮不足.陳芳［3］根據(jù)客流變化規(guī)律，對發(fā)車間隔采用多時段處理思想，建立了以乘客與公交企業(yè)運營費用最小為目標(biāo)的公交車輛調(diào)度模型，對于信號控制的干擾沒有進(jìn)行考慮.劉志剛等［4］根據(jù)區(qū)域公交調(diào)度模型，把公交車容量作為理想狀態(tài)，不受信號控制的干擾，建立了公交調(diào)度系統(tǒng)雙層規(guī)劃模型.本文綜合考慮乘客與公交公司利益，并基于極小極大思想，考慮公交車車輛容量的限制及城市道路信號控制的干擾因素，建立公交發(fā)車間隔優(yōu)化模型，并利用非支配排序遺傳算法（NSGA）進(jìn)行模型的求解.

1 優(yōu)化模型的建立

1.1模型假設(shè)

公交車輛的運營受很多因素的影響，本文為建立公交調(diào)度優(yōu)化模型作出以下假設(shè)：

a.線路上的公交車輛為同一型號，公交車會按照調(diào)度表準(zhǔn)時到站和出站；

b.全程票價統(tǒng)一；

c.公交車輛行駛過程中不存在阻塞現(xiàn)象及突發(fā)情況，且公交車之間依次行進(jìn)，不存在超車及越站現(xiàn)象；

d.各站點乘客上下車的時間、公交車在各站點的停留時間均被考慮在公交車的平均速度之內(nèi)；

e.僅考慮沿線信號延誤干擾，沿線交叉口具有相同的信號延誤；

f.各交叉口有足夠大的通行能力，僅考慮單行方向公交車運行.

1.2 模型的構(gòu)建

公交車運行調(diào)度模型的建立是一個復(fù)雜過程，根據(jù)極小極大思想，為使服從相同規(guī)律的受控群體的性能指標(biāo)在總體上最小，其充分條件就是使群體中性能指標(biāo)值最大的個體值最小.作為乘客希望獲得便捷、舒適、車輛間隔小、等待時間短的公交服務(wù)，這樣勢必造成空駛率過高，公交公司的利益得不到保證而影響其服務(wù)質(zhì)量.而公交公司希望發(fā)車間隔增大，發(fā)車次數(shù)少且載客量大，以獲取更大利益，這與乘客的需求相違背.因此，綜合考慮公交公司與乘客的利益，使乘客最大廣義費用最小及公交公司最大廣義費用最小.

式中，M為公交車的最大發(fā)車間隔，為一正常數(shù)；f為發(fā)車間隔，f為整數(shù)，min；C（f）為在時間T內(nèi)，乘客的廣義費用，元；B（f）為在時間T內(nèi)，公交公司廣義費用，元.

在時間T內(nèi)出行者的廣義費用為

式中，δ為與乘客有關(guān)的時間費用轉(zhuǎn)化系數(shù)；FW（f）為乘客等車時間，min；γ1為相對于等車時間費用的在車時間費用權(quán)重系數(shù)；γ2為相對于等車時間費用的換乘懲罰費用權(quán)重系數(shù)；Fin為與在車時間相關(guān)的費用；FT為與換乘相關(guān)的懲罰費用.

關(guān)于乘客等車時間有

式中，F(xiàn)W（f）為所有出行者等待時間，min；n為所有等待的乘客數(shù)量，人次；S為乘客等待時間的均值，min.

對于某一站點，記W（t）為t時刻在節(jié)點等待的乘客數(shù)量.等待的乘客包含在下一輛車到達(dá)之前陸續(xù)來到站點作等待的乘客及在上一運次滯留的乘客.t時刻為某一公交車進(jìn)站時刻.并且設(shè)定公交車的容量為C，則在該站點乘客上車的數(shù)量為P（t）.

式中，O（t）為在某站點處，公交車上已有的乘客數(shù)量.

對于滯留的乘客，需要等待下一運次才能乘上公交車，假定不存在3次等車，而保證一定的服務(wù)標(biāo)準(zhǔn)，對于滯留的乘客需要再次等待一個ti時間才能上車.若對于上一時刻存在乘客滯留，則滯留人數(shù)為D（t-ti）.

式中，ti為相鄰運行公交的平均車頭時距，min；d為T時間段內(nèi)，公交車由于遇到交叉口信號控制的干擾引起的平均延誤，min；dj為公交車遇到某一交叉口j引起的平均延誤；I為公交車所沿該線路中交叉口數(shù)量，I為整數(shù).

由于公交車按照行車時刻表運營，因此，乘客到達(dá)公交站點會產(chǎn)生等車時間.根據(jù)Bowman等［5］提出的等車時間模型，乘客期望等待時間的均值為

式中，E（t）為乘客期望等車時間，min；H為平均車頭時距，min；CV為車頭時距協(xié)變參數(shù).

如果排除外界干擾，公交車平均車頭時距應(yīng)與發(fā)車間隔相等.由于公交車運行受交叉口信號控制的干擾，車頭時距發(fā)生波動，則平均車頭時距為ti.

而對于t時刻，等候車輛的總?cè)藬?shù)為n，引起乘客等待公交車的狀態(tài)有m種，分別為沒有滯留的乘客平均等待時間和滯留乘客平均等待時間這兩種方案，即m=2.根據(jù)熵權(quán)決策法原理［6］得出乘客等待時間的均值為

式中，w1為沒有滯留的乘客等待時間權(quán)重；w2為滯留乘客等待時間權(quán)重.

出行者等待時間

由于乘客在車時間只與路段的不同而不同，因此定義在車時間費用是只與路段相關(guān)的常數(shù).對于懲罰費用同樣與發(fā)車頻率無關(guān)，取決于路段，同樣可以作為常數(shù)處理［7］.對于在車時間費用與懲罰費用相應(yīng)權(quán)重可以通過實際調(diào)查統(tǒng)計得到［8］.在時間T內(nèi)，相應(yīng)公交車運營的廣義費用為

式中，γ3為公交公司所支出的固定費用的相應(yīng)權(quán)重；BF（f）為在時間T內(nèi)公交公司所支出的固定費用，元；θ為每公里運營費用（與百公里燃油有關(guān)），元／km；BV（f）為在時間T內(nèi)與發(fā)車間隔相關(guān)的公交車輛行駛里程，km.

其中固定費用主要包含公交車的保養(yǎng)維修費用、公交公司的管理費用及員工工資［9］，在T時段內(nèi)可得到的相應(yīng)固定費用為

式中，Bse為在T時段內(nèi)，平均每輛車的保養(yǎng)維修費用，元；Bm為在T時段內(nèi)平均每輛車的管理費用，元；Bw為在T時段內(nèi)相對于每輛車的人均工資費用，元.

在T時段內(nèi)運營了N輛車，則

式中，N為一整數(shù)，運算中中括號為取整運算，表示N為不超過T／f的最大整數(shù).

所有車輛行駛里程

式中，v為公交車的平均行程速度，在某條干線上為一常數(shù)，km／h.

公交車輛的運行勢必受到紅綠燈的干擾而影響正常運營，為保障公交車服務(wù)標(biāo)準(zhǔn)，相鄰運行中的公交車車頭時距因交叉口信號干擾需保持在一個發(fā)車間隔內(nèi).公交車遇到交叉口引起的延誤是隨機(jī)的［10］，因而根據(jù)Miller提出的隨機(jī)延誤理論得到

式中，d為T時段內(nèi)，公交車由于遇到交叉口信號控制的干擾引起的平均延誤，min；c為周期時長，min；g為有效綠燈時長，min；x為飽和度；q為到達(dá)率；QO為平均飽和排隊車輛數(shù)，輛.

公交車遇到交叉口引起的總的延誤滿足如下約束

基于公交公司與出行者綜合廣義費用最小，公交車發(fā)車間隔與信號控制之間存在相互影響，交通信號控制影響著車頭時距的波動程度，約束發(fā)車間隔的確定.發(fā)車間隔的合理性又反映了信號控制的優(yōu)化程度，信號控制得以優(yōu)化可減少公交車運行時由于交叉口的干擾引起的延誤，提高通行能力.根據(jù)以上分析，建立如下公交車運行調(diào)度模型

對于公共交通，當(dāng)交通需求增加時，提高發(fā)車頻率，可使乘客的等車時間減少［11］.為保證優(yōu)化結(jié)果較優(yōu)，相鄰運行公交車不發(fā)生超車或前后相接的現(xiàn)象.

2 模型的求解

乘客廣義費用和公交公司的廣義費用這些目標(biāo)并不是彼此獨立，二者耦合在一起，互為矛盾，互為競爭.某子目標(biāo)的改善可能引起其它子目標(biāo)性能的改變，而同時使所有子目標(biāo)達(dá)到最優(yōu)往往是不可能的.要找到這些目標(biāo)的最佳設(shè)計方案，就要解決多目標(biāo)與多約束的優(yōu)化問題，即多目標(biāo)優(yōu)化［12］.對于模型的求解引進(jìn)NSGA.

可以定義為在一組約束條件下，極小化這兩個目標(biāo)函數(shù)［13］，令［C（f）］max=u1（X），［B（f）］max= u2（X），形式如下：

式中，X=（f1，f2，…，fp）是一個p維向量，ui（X）是目標(biāo)函數(shù)，i=1，2.gj（X）和hk（X）為系統(tǒng)約束.

NSGA是基于對個體的幾層分級實現(xiàn)的.在選擇執(zhí)行前，群體根據(jù)支配與非支配關(guān)系來排序，所有非支配個體被排成一類，這些被分級的個體共享它們的虛擬適應(yīng)度值.然后忽略這組已分級的個體，對種群中的其它個體按照支配與非支配關(guān)系再進(jìn)行分級，該過程繼續(xù)直到群體中的所有個體被分級.在NSGA中對每個局部的Pareto曲面（線）上的所有個體分別采用適應(yīng)度共享策略，有利于保持群體多樣性，可以克服超級個體的多度繁殖，防止早熟收斂.根據(jù)關(guān)志華［14］對于非支配排序遺傳算法算子分析，參數(shù)選取分別為：交叉概率取0.8；共享半徑取0.05；變異概率取0.00.算法流程如圖1［13］所示.

圖1 NSGA算法流程圖Fig.1 NSGA flow chart

3 實例分析

由式（9）知乘客的平均等待時間與發(fā)車間隔具有一定的關(guān)聯(lián)性.此外，董強(qiáng)等［15］對公交車調(diào)度問題研究表明發(fā)車間隔與公交車的滿載率相關(guān).由于車次與發(fā)車時刻一一對應(yīng)，而車輛的隊列順序不發(fā)生改變，因而對所需車輛進(jìn)行統(tǒng)一標(biāo)號后，則每一車次與其對應(yīng)的車輛編號是確定的.直接對第k次車進(jìn)行考察，公交車全日平均滿載率為

式中，λS為公交車全日平均滿載率；μ為某一站臺；λ（k，μ）為第k次車離開第μ站時的全日平均滿載率；TN為一天單程所發(fā)的車次總數(shù)；μA為單程站臺總數(shù)；Tday為公交車全日運行時間.模型相關(guān)參數(shù)取值見表1.

選取河南省焦作市具有代表意義的5條公交線路，如圖2所示，分別為21路、9路、13路、17路、14路.乘客平均等待時間能夠直觀地反映乘客的出行利益，公交車輛全日平均滿載率能夠衡量車輛的利用程度，反映了公交公司的利益.因此，以乘客平均等待時間和全日平均滿載率作為評價指標(biāo)，進(jìn)行相關(guān)的調(diào)查分析.經(jīng)實地調(diào)查，上述模型相關(guān)參數(shù)選取如表1所示.

表1 模型相關(guān)參數(shù)取值Tab.1 Selection of model related parameter

在實際調(diào)查中，線路21路、9路由于客流量較大，滿載率較高，對乘客來說舒適性下降，不利于乘客利益；線路17路、14路，乘客等待時間太長，吸引客流較弱，不利于乘客利益，滿載率過低，車輛利用程度較低，影響公交公司利益.對于滿載率，各個城市都沒有形成統(tǒng)一的規(guī)范值.按照焦作市城市公交行業(yè)管理規(guī)范規(guī)定，為保持車輛利用程度，全日線路平均滿載率控制在60%～100%.線路13路滿載率維持在合理水平，乘客等待時間稍長，可適當(dāng)調(diào)節(jié)，維持乘客利益.通過Matlab對上述算法進(jìn)行實現(xiàn)，利用模型對21路、9路、13路、17路、14路公交線路發(fā)車間隔進(jìn)行優(yōu)化，優(yōu)化結(jié)果以乘客平均等待時間和公交車平均滿載率為衡量指標(biāo)，如圖3與圖4所示.

圖2 焦作市5條公交線路走向圖Fig.2 Five bus routes to figure in Jiaozuo

圖3 各線路優(yōu)化前后乘客平均等待時間比較Fig.3 Comparison between average passenger waiting times before and after optimization

圖4 各線路優(yōu)化前后全日平均滿載率比較Fig.4 Comparison between diurnal average load factors before and after optimization

根據(jù)本研究的優(yōu)化結(jié)果，各線路乘客平均等待時間及對應(yīng)的全日平均滿載率不僅滿足焦作市城市公交行業(yè)管理規(guī)范中的規(guī)定，且各線路總的平均滿載率減少了3.8%，舒適度增加，吸引了客流，保證了公交公司的相應(yīng)利益.同時，乘客平均等車時間相對于現(xiàn)狀平均等待時間減少48.3%，滿足乘客的利益.

4 總 結(jié)

兼顧公交公司與出行者的利益愿景，根據(jù)極小極大思想對公交車發(fā)車間隔進(jìn)行了優(yōu)化.運用非支配排序遺傳算法解決此類多目標(biāo)問題，并獲得最優(yōu)解組合集合，在集合中找到最優(yōu)解，規(guī)避了同時使所有子目標(biāo)均達(dá)到最優(yōu)的不實際現(xiàn)象.充分考慮了公交車容量限制產(chǎn)生的乘客滯留狀況和交叉口信號控制對公交車運行的影響.通過對發(fā)車間隔的優(yōu)化，不僅能滿足客流需求，同時規(guī)避了公交資源的浪費，具有現(xiàn)實適用性.

［1］ Huisman D，F(xiàn)reling R，Wagelmans AP M.A robust solution approach to the dynamic vehicle scheduling problem［J］. Transportation Science，2004，38（4）：447-458.

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

［3］ 陳芳.城市公交調(diào)度模型研究［J］.中南公路工程. 2005，30（2）：162-164.

［4］ 劉志剛，申金升.區(qū)域公交時刻表及車輛調(diào)度雙層規(guī)劃模型［J］.系統(tǒng)工程理論與實踐，2007，27（11）：135 -141.

［5］ Bowman L A，Tumquist M A.Service frequency：schedule reliability and passenger wait times at transit stops［J］. Transportation Research，1981，15（6）：465-471.

［6］ 閆文周，顧連勝.熵權(quán)決策法在工程評標(biāo)中的應(yīng)用［J］.西安建筑科技大學(xué)學(xué)報，2004，36（1）：98-100.

［7］ 高自友，任華玲.城市動態(tài)交通流分配模型與算法［M］.北京：人民交通出版社，2005.

［8］ 何勝學(xué).道路擁擠收費定價分析［J］.上海理工大學(xué)學(xué)報，2005，27（1）：87-90.

［9］ 陳國棟，李會芬.公交車的經(jīng)濟(jì)壽命和影響因素的研究［J］.廣西大學(xué)學(xué)報，2008，30（zl）：211-212.

［10］ 何勝學(xué)，范炳權(quán)，嚴(yán)凌.公交網(wǎng)絡(luò)最優(yōu)路徑的一種改進(jìn)求解算法［J］.上海理工大學(xué)學(xué)報，2006，28（1）：163-167.

［11］ Rea J C.Designing urban transit systems：an approach to the route technology selection problem［J］.Highway Research Record，1972（417）：48-59.

［12］ 付立，竇明罡，朱建凱，等.非支配排序遺傳算法的改進(jìn)［J］.計算機(jī)與數(shù)字工程，2011，39（2）：11-15.

［13］ 高媛，盧建剛.非支配排序遺傳算法（NSGA）的研究與應(yīng)用［D］.杭州：浙江大學(xué)，2006.

［14］ 關(guān)志華.非支配排序遺傳算法（NSGA）算子分析［J］.管理工程學(xué)報，2004，18（1）：57-60.

［15］ 董強(qiáng)，劉超慧，馬熠.公交車調(diào)度問題的研究［J］.工程數(shù)學(xué)學(xué)報，2002，19（2）：60-66.

（編輯：丁紅藝）

Bus Scheduling Optimization Model Based on NSGA Algorithm

SONGXiao-peng， HAN Yin， YAOJiao
（Business School，University of Shanghai for Science and Technology，Shanghai 200093，China）

Optimized buses scheduling scheme is essential to improve transit service levels and promote rapid development of public transport.Taking account of the interest game between passengers and bus company and considering the vehicle capacity constraint of buses and confounding factors of urban road signal control，a bus departure interval optimization model was built in the light of the minimax idea，and then the non-dominated sorting genetic algorithm（NSGA）was used to solve the model.The case of bus lines in Jiaozuo，Henan Province，was taken as an example to illustrate the improvement of transit service levels due to the optimization scheduling.The results show that the average waiting time of passengers is reduced by 48.3%and the average load factor of buses per full day is decreased by 3.8%.

urban public transport；departure interval；waiting time；non-dominated sorting genetic algorithm

U 491

A

2013-08-08

國家自然科學(xué)基金資助項目（51008196）；上海市一流學(xué)科建設(shè)資助項目（S1201YLXK）

宋曉鵬（1987-），男，碩士研究生.研究方向：智能交通、交通規(guī)劃與管理.E-mail：songxiaopeng208＠163.com

韓 ?。?964-），男，教授.研究方向：智能交通、交通規(guī)劃與管理.E-mail：hanyin2000＠sina.com

1007-6735（2014）04-0357-05

10.13255／j.cnki.jusst.2014.04.010