基于用戶需求的城市公交調度算法研究

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

關鍵詞：智能公交； 需求調度； 最短路徑； 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

引言

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

1 需求響應與常規公交的區別

從公交服務模式的角度看，城市公共交通系統可被分為常規公交系統與需求響應型公交系統，常規公交系統具有固定的運行線路、停靠站點及發車間隔，適合人口密度較高的大城市[2]，但可調性差、服務質量較低。基于用戶需求響應公交調度是依托“移動互聯網+智能公交”的基礎，在對市民乘車差異化需求廣泛調查的基礎上[3]，為乘客量身打造的一種新型的出行方式。與常規公交相比，系統沒有固定的發車時刻表、服務范圍、固定站點。與出租車相比，享有路權優先、經濟實惠和低碳環保等優點。公交個性化按需調度將是一個創新的按需增值服務，公交企業可推出一系列基于按需分配的定制服務，乘客享受“一人一座”、“一站到達”、“一路通行”等服務，從而擴大市民出行的公交使用率，提高乘客滿意度。

2 需求響應公交調度模型

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

3 系統特點及算法設計

3.1 系統特點

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

3.2 算法設計

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

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

參考文獻

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

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

[3] 過秀成，嚴亞丹. 地面公共交通運行可靠性分析與調度控制[M]. 南京：東南大學出版社，2013.

[4] 雷德明，嚴新平. 多目標智能優化算法及其應用[M]. 北京：科學出版社，2009.

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

[6] 易星. 改進的A*算法在物流配送中的車輛調度方法[J]. 金陵科技學院學報，2017，33（4）：31-34.