基于用戶需求的城市公交調(diào)度算法研究

摘 要：本文從中國城市地面公共交通現(xiàn)狀，分析居民出行需求的多樣性和復(fù)雜性，提出一種基于動態(tài)分配模型的公交調(diào)度系統(tǒng)。探討城市公交基于用戶需求響應(yīng)模式的理論意義和實(shí)際應(yīng)用價(jià)值，并構(gòu)建數(shù)學(xué)模型和系統(tǒng)工作流程。綜合考慮乘客出行時(shí)間、線路距離及容量約束，構(gòu)建以最短路徑和A*算法為乘客進(jìn)行個(gè)性化出行需求規(guī)劃線路和站點(diǎn)，建立適合中國國情的混合式公交運(yùn)行模式，是現(xiàn)代智能交通可持續(xù)發(fā)展新產(chǎn)物。

關(guān)鍵詞：智能公交； 需求調(diào)度； 最短路徑； A*算法

Abstract： In this paper， the present situation of urban public transportation in China is analyzed. A bus dispatching system based on dynamic distribution model is proposed. The theoretical significance and practical application value based on the user demand response model are discussed， the mathematical model and the system work flow are constructed， and the passenger travel time， line distance and capacity constraints are considered. The shortest path and A* algorithm are used to plan the route and site for passengers' personalized travel needs， and the establishment of a hybrid bus operation model suitable for China is a new product of the sustainable development of modern intelligent transportation.

Key words： intelligent public transport； demand scheduling； shortest path； A* algorithm

引言

公共交通是一個(gè)城市經(jīng)濟(jì)文化的標(biāo)志，中國城市地面公交基礎(chǔ)設(shè)施投入巨大，卻依舊不能滿足人們出行需求。公交車保持固定線路和班次的做法，顯然已經(jīng)不符合智慧城市發(fā)展條件。在計(jì)算機(jī)通訊技術(shù)迅猛發(fā)展的時(shí)代，應(yīng)制訂相應(yīng)發(fā)展目標(biāo)，滿足“公交優(yōu)先”原則。從“以人為本”的理念出發(fā)，降低運(yùn)行時(shí)間，提高可靠性和舒適度，實(shí)現(xiàn)以不斷擴(kuò)張公交線路網(wǎng)、增加公交車輛為特征的粗放型階段向“智能化”、“按需化”發(fā)展階段轉(zhuǎn)型，是實(shí)現(xiàn)經(jīng)濟(jì)效益、社會效益和環(huán)境效益統(tǒng)一的最佳方式[1]。

1 需求響應(yīng)與常規(guī)公交的區(qū)別

從公交服務(wù)模式的角度看，城市公共交通系統(tǒng)可被分為常規(guī)公交系統(tǒng)與需求響應(yīng)型公交系統(tǒng)，常規(guī)公交系統(tǒng)具有固定的運(yùn)行線路、停靠站點(diǎn)及發(fā)車間隔，適合人口密度較高的大城市[2]，但可調(diào)性差、服務(wù)質(zhì)量較低?；谟脩粜枨箜憫?yīng)公交調(diào)度是依托“移動互聯(lián)網(wǎng)+智能公交”的基礎(chǔ)，在對市民乘車差異化需求廣泛調(diào)查的基礎(chǔ)上[3]，為乘客量身打造的一種新型的出行方式。與常規(guī)公交相比，系統(tǒng)沒有固定的發(fā)車時(shí)刻表、服務(wù)范圍、固定站點(diǎn)。與出租車相比，享有路權(quán)優(yōu)先、經(jīng)濟(jì)實(shí)惠和低碳環(huán)保等優(yōu)點(diǎn)。公交個(gè)性化按需調(diào)度將是一個(gè)創(chuàng)新的按需增值服務(wù)，公交企業(yè)可推出一系列基于按需分配的定制服務(wù)，乘客享受“一人一座”、“一站到達(dá)”、“一路通行”等服務(wù)，從而擴(kuò)大市民出行的公交使用率，提高乘客滿意度。

2 需求響應(yīng)公交調(diào)度模型

基于用戶需求響應(yīng)的公交調(diào)度簡稱按需調(diào)度（On-Demand Bus Dispatching），是一個(gè)多目標(biāo)決策系統(tǒng)，可建立圖論模型描述交通道路。如定義有向加權(quán)圖G=（V，E），由節(jié)點(diǎn)V和路徑權(quán)值E組成，從邊到權(quán)值的映射W：E->R；定義乘客等待時(shí)間Tm；乘客響應(yīng)權(quán)值PPm；以Hijk表示乘客在第k輛車上從站i到站j之間的車上乘車時(shí)間總和，累計(jì)達(dá)到規(guī)定數(shù)值后公交行駛終點(diǎn)。

3 系統(tǒng)特點(diǎn)及算法設(shè)計(jì)

3.1 系統(tǒng)特點(diǎn)

目前，基于傳統(tǒng)公交模式的混合啟發(fā)式算法，或遺傳算法的單線公交車輛調(diào)度方案的研究較多，但少有動態(tài)分配模型的公交調(diào)度系統(tǒng)方面的研究。本調(diào)度算法的線路優(yōu)化是構(gòu)建模型的首要任務(wù)，動態(tài)調(diào)度系統(tǒng)需要對乘客請求進(jìn)行乘車點(diǎn)篩選，因此需要進(jìn)行線路規(guī)劃。乘客需向調(diào)度系統(tǒng)提交出行起始地和目的地，由系統(tǒng)調(diào)度附近公交為其服務(wù)。車輛在行駛過程中若出現(xiàn)請求服務(wù)，則相當(dāng)于在有向加權(quán)圖G的相鄰頂點(diǎn)（Vi、Vj）間插入一個(gè)新需求點(diǎn)（Vx）。公交車的行駛線路發(fā)生變化需通過公交選徑模塊判斷插入點(diǎn)V x是否滿足行程時(shí)間f（c）與行駛線路f（s）等約束條件，符合條件則接受請求，否則繼續(xù)通過路徑選擇模塊和公交分配模塊為其提供其它滿足條件的公交車。算法流程如圖1所示。

3.2 算法設(shè)計(jì)

對一個(gè)核心目標(biāo)求最優(yōu)解，對其他目標(biāo)以約束條件形式獲得可行解，或保留多個(gè)最優(yōu)解，進(jìn)行多目標(biāo)決策分析，如Christoph mandi（1979）提出的GF算法第一目標(biāo)是路線最短等[4]。A.N.Bansal（1981）通過理論分析證明了最短路線接近最優(yōu)解。

按需調(diào)度公交系統(tǒng)的出現(xiàn)可滿足城市公共交通出行多樣性需求，對低出行密度地區(qū)公交服務(wù)問題的解決能力十分突出[7]。首先，城郊居民出行具有高平峰差異，[JP1]較適合本調(diào)度系統(tǒng)靈活調(diào)度的特點(diǎn)。其次，可以解決用戶地鐵到家“最后一公里”的訴求，智能化，按需化公交能有效解決交通治理精細(xì)化的效率和準(zhǔn)確性。再次，本算法仍存在很多不足和需改進(jìn)的地方，比如沒有綜合考慮市民出行費(fèi)用及駕駛員費(fèi)用等。城市公共交通規(guī)劃者可通過常規(guī)公交和按需公交相結(jié)合的模式，提高公共交通服務(wù)水平和類型，有效滿足居民個(gè)性化出行需求。

參考文獻(xiàn)

[1] 張生瑞，嚴(yán)海. 城市公共交通規(guī)劃的理論與實(shí)踐[M]. 北京：中國鐵道出版社，2007.

[2] 王詩琪. 基于出行行為分析的靈活公交動態(tài)調(diào)度模型研究[D]. 北京：北京交通大學(xué)，2016.

[3] 過秀成，嚴(yán)亞丹. 地面公共交通運(yùn)行可靠性分析與調(diào)度控制[M]. 南京：東南大學(xué)出版社，2013.

[4] 雷德明，嚴(yán)新平. 多目標(biāo)智能優(yōu)化算法及其應(yīng)用[M]. 北京：科學(xué)出版社，2009.

[5] 任剛. 交通管理措施下的交通分配模型與算法[M]. 南京：東南大學(xué)出版社，2007.

[6] 易星. 改進(jìn)的A*算法在物流配送中的車輛調(diào)度方法[J]. 金陵科技學(xué)院學(xué)報(bào)，2017，33（4）：31-34.