時變公交網絡的數學規劃模型與算法

徐 勇，李 杰，安利平，王 平，CHU Chao－Hsien

（1.河北工業大學理學院，天津300401；2.北京大學軟件與微電子學院無錫基地，江蘇 無錫214125；3.南開大學商學院，天津300072；4.北京大學軟件與微電子學院，北京100260；5.新加坡管理大學信息系統學院，新加坡178902）

0 引言

在中國，隨著經濟的快速發展，各種車輛的保有量呈現幾何數量遞增趨勢，很多城市交通道路的發展不能滿足車輛出行需求，城市交通擁堵日益嚴重。交通擁堵問題不僅對城市的機動性產生負面影響，而且使城市的宜居性下降。一些城市不得不采用交通路段分時限行、車輛限號出行、車輛購買限量等措施，這些措施在緩解交通擁堵的同時，給出行者帶來極大的不便。事實上，平衡多種交通方式實現城市宜居是大多數國家的城市領導者和交通運輸專家采取的長期目標。因此政府大力倡導乘坐公交車出行，盡量減少交通壓力。為了達到出行從小汽車到公共交通的轉變，把出行流量盡量吸引到公共交通系統中來，需要建立發達完善的公共交通系統。

在公共交通系統規劃設計中，公交線路網絡構建［1－6］、公交出行客流分配［7－12］、公交出行查詢算法［13－24］等受到廣泛關注。公交構建和客流分配是設計層面需要解決的問題，公交網絡構建必須考慮公交網絡的覆蓋性、可達性，公交配流必須考慮出行路徑最優原則。公交出行查詢是面向出行的應用層面的問題。公交路徑最優選擇算法不僅是建立公交網絡信息查詢系統的核心算法，也是公交網絡構建、調整的重要算法，同時是公交配流的重要算法之一。各界學者也開始對這些問題進行思考并且提出各自的解決方案。基于最小換乘次數的公交網絡的最短路優化問題對解決上述3類問題具有重要意義，例如文獻［6］考慮了最小換乘條件下的公交網絡構建算法。文獻［7］在最小換乘的基礎上進行公交流量分配，從公交OD（Origin Destination）矩陣出發，最終得到每條公交線路上的OD矩陣。公交出行查詢問題的解決通常需要考慮換乘次數、路程、公交發車頻率、線路擁塞、等車時間等諸多因素，如果將這些因素按確定性來分，則換乘次數最小、和路程最短是查詢問題中的確定因素，是絕大多數公交網絡路徑選擇算法優先考慮的因素。公交發車頻率、線路擁塞、等車時間這些因素則是不確定因素，現有的查詢算法往往不涉及不確定因素，或對不確定因素保守確定化。查詢算法要想實用化、精確化，就必須考慮查詢中的不確定因素，為出行者不僅要提供少換乘次數、換乘線路，還要提供短乘車距離和乘車時間。

綜合考慮多種因素的公交網絡最優路徑選擇問題是NP問題［13］。目前在公交最優路徑選擇方面得到應用的算法主要有3類［13－24］。第1類是基于最短路徑搜索技術的算法，如：Dijkstra算法、A＊算法、Floyd算法等，這些算法運算效率較高，但不能處理換乘問題，得到的最短路徑換乘次數太多可能無法應用；第2類是基于智能技術包括遺傳算法、螞蟻算法、禁忌算法的查詢算法；第3類是基于數據庫技術或集合運算的查詢算法。第2，3類算法在計算過程中容易搜索大量不合理的路徑，容易產生維數爆炸問題，難以用于大規模公交網絡。這些算法考慮不確定因素的還不多見，但不確定性客觀存在。實際上，公交線路有運行時間區間的，公交出行查詢時必須考慮公交線路的運行時間區間，否則，查詢結果可能無法應用。以天津市區2013年的公交線路圖為例，天津市有公交線路341條，站點2 000個以上，部分公交線路的運行時區為 （括號內為線路）：

可以看出，在7：00～17：00時間段的出行，可以不用考慮公交網絡的時變性，但在4：00～7：00，17：00～23：30時區內出行必須考慮公交網絡的時變性，否則可能出現要換乘的線路還未運行或已經不再運行的窘境。本文在文獻［16］基礎上討論時變公交網絡的查詢問題。

1 時變公交網絡的高維數組表示

公交網絡是由若干公交線路相互耦合而成的復雜網絡。公交網絡中的公交站點可以被若干不同的公交線路經過，公交線路經過若干不同站點。公交網絡不同于一般的交通網絡，表現在3個方面：1）不變性。在一定時期內，每條公交線路的走向、覆蓋站點是固定不變的，決定了出行者不能隨機選擇出行路線。2）任意性。有些出行者在不能直達的情況下必須換乘，換乘節點以及換乘路線不唯一，這是由整個公交網絡系統的連通性決定的。3）時變性。公交網絡中的線路運行是與一定的時間區間段對應的，在不同的時間查詢出行路線可能不一樣。這樣，出行者在哪個時間段出行，在哪個節點換乘，換乘哪路公交車，即換乘規則如何確定更接近實際，是一個復雜的優化問題。

公交站點通過公交線路鄰接，公交線路又通過相交的站點發生關聯。本文考慮有m條公交線路、n個公交站點的公交線路選擇問題。記公交線路集合為l＝｛L1，L2，…，Lm｝，公交站點的集合為s＝｛S1，S2，…，Sn｝。由于公交車的運行是有時間區間的，而且在公交網絡中，每條公交線路都有相對應的起始點，在此設為Si站點在線路Lk中的相對該線路的起始點的距離，一般地可以認為是距離初始站點的站數。任意的公交線路Lk都有自己的運營時間段表示運營開始時間，表示運營結束時間。用（t）表示在時刻t時線路Lk中站點Si和站點Sj之間的距離，即

根據公交線路與經過的公交站點相關聯的關系以及公交站點在公交線路上的鄰接關系，建立反映公交網絡站點相鄰關系和站點與線路關聯關系的三維數組W ＝［wkij（t）］n×n×m，其中i，j為公交網絡中公交站點Si與Sj，k為公交網絡中公交線路Lk，wkij（t）為站點Si到Sj在線路Lk上在時刻t的距離，wkij（t）≠0實際上表示在時刻t公交線路Lk中站點Si和站點Sj之間存在著一條直達路徑，而不需要換乘。三維數組記錄了公交網絡的全部信息，從而可以基于該三維數組進行公交網絡的查詢。

2 時變公交網絡的換乘查詢優化模型

從站點Si出發，若經過線路Lk1，Lk2，Lk3，…，Lkv＋1，換乘站點分別為Sr1，Sr2，Sr3，…，Srv到達終點站Sj，則經過最小換乘次數條件下最短距離問題可以用數學規劃模型（2）描述：

該規劃問題對公交網絡構建、公交配流、公交出行查詢信息系統的建立具有重要作用。為了求解上述規劃問題，將該問題分解為先求最小換乘次數，再求換乘站點與乘車距離。

3 基于影射網絡數學規劃求解算法

首先不考慮時間因素，在公交線路影射網絡圖上給出最小換乘次數的計算方法：

第1步，基于站點與線路的關聯關系確定途徑出發站點Si的線路集合，終止站點Sj的線路集合

第2步，在已給出頂點集合l1，l2，…，lk的情況下給出lk＋1：任給在線路影射網絡圖中的結點集若lk＋1∩ le≠ Φ，則lk＋1＝ ：lk＋1∩ le，記以l1，l2，…，lk＋1為剖分集的公交線路影射網絡圖的生成子圖為G＝ ｛l1，l2，…，lk＋1，E｝，該多部圖G的邊集E只包含線路影射網絡圖中結點分別在lp與lq（p≠q）中的邊，轉第3步；否則，令k＝k＋1，轉第2步。

最小換乘次數算法實質是線路影射網絡圖上的最短路線算法，從而是一種多項式時間算法。時不變公交網絡中的最小換乘次數即為換乘次數搜索算法搜索得到的k，對于時變公交網絡來說，由于時變原因，換乘次數存在v≥k的情況。以上算法確定的多部圖是求解換乘站點、換乘線路和乘車距離的基礎。

3.1 基于線路影射網絡的最小換乘次數算法

為了確定從站點Si出發到站點Sj的換乘次數，建立公交線路影射網絡圖。公交線路影射網絡圖定義為將公交線路看作結點，若兩條公交線路有公共公交站點則在公交網絡影射圖中對應的兩個線路結點之間有邊相連，若兩條公交線路有多個公共公交站點，則對應的線路結點間只能取一條邊。

3.2 基于站點影射網絡圖的最短路線算法

在多部圖G＝｛l1，l2，…，lk＋1，E｝的基礎上求解最小換乘條件下的最短路，并給出乘車線路、換乘站點以及每一線路的乘車站數。若出行者在t時刻進行查詢，則數學規劃問題（2）轉化為求解優化問題（3）。

優化問題（3）與優化問題（2）相比，沒有最小換乘次數的限制，而且縮小了換乘線路的搜索范圍，搜索過程只在lq，q＝1，2，…，v中進行。搜索的公交線路數量大大減少，從而公交線路的搜索范圍大大縮小了。優化問題（3）的求解可以轉化為時變多階段決策問題，從而優化問題（3）可以采用傳統的最短路線算法解決，而且最短路線問題存在多項式算法，如經典的Dijkstra算法。

根據模型（3）建立出行的多階段決策圖G0。初始階段的頂點集為N0＝｛Si｝，第1階段的頂點集為從站點Si出發乘坐的線路Lk1∈l1到達的換乘站點Sr1組成的集合N1，邊SiSr1的權值為；第2階段的頂點集合為在Sr1轉乘線路Lk2∈l2到達的站點Sr2組成的集合N2，邊Sr1Sr2的權值為ξk2），依次類推，最后一階段的頂點集合為 Ne＝ ｛ Sj｝，邊Srk＋1Sj的權值為ξkk＋1）。

在圖G0上采用最短路線算法得到最優出行路徑。假設查詢的最優出行路徑為

4 算例

為了說明本文給出的時變公交網絡系統的查詢算法，以如圖1所示的含有12條公交線路以及他們之間的10個交叉公交站點的公交網絡為例，公交網絡中各站點到公交線路始點距離（括號內數字）：L1：S1（2），S2（5），L2：S1（5），S3（8）；L3：S1（4），S4（7）；L4：S3（6），S5（8）；L5：S3（10），S6（13）；L6：S2（4），S7（10）；L7：S5（4），S8（7）；L8：S6（5），S8（9）；L9：S4（6），S9（13）；L10：S7（2），S10（10）；L11：S8（6），S10（10）；L12：S9（4），S10（10）。

假設各條公交線路的運行時間區間：L1：6∶00－22∶00；L2：4∶50－23∶00；L3：5∶30－22∶40；L4：5∶15－19∶15；L5：5∶15－22∶30；L6：5∶00－17∶00；L7：5∶10－21∶40；L8：5∶05－18∶00；L9：5∶30－18∶00；L10：7∶00－23∶00；L11：5∶30－18∶40；L12：5∶45－19∶00。

在不同的時間點查詢從站點S1到S10的換乘次數、乘車距離和乘車時間。首先建立該公交網絡系統的線路網絡影射圖（圖2）。

由換乘次數算法第1步得：s1到s10的l1＝ ｛ L1，L2，L3｝，le＝｛L10，L11，L12｝，通過第2步搜索過程得到l2＝｛L6，L4，L5，L9｝，l3＝ ｛ L10，L7，L8，L12｝，因l3∩ le≠ Φ，得l3：＝ ｛ L10，L12｝生成的多部圖G＝ （l1，l2，l3，E），如圖3所示。

根據換乘次數算法的第3步約簡后的多部圖如圖4所示。

若查詢時間為10∶00點，且給出L1，L6，L10的發車頻率為每小時3，4，5班，L3，L9，L12發車頻率為每小時4，5，4班，則有ξ1～ U［0，20］，ξ6～ U［0，15］，ξ10～ U［0，12］，ξ3～ U［0，15］，ξ9～ U［0，12］，ξ12～ U［0，15］，假設每兩站之間運營時間均為3分鐘，對應的優化問題（3）為

圖1 含有12條公交線路及交叉站點的公交網絡圖Fig.1 A Public transit network with 12lines and cross stations

圖2 圖1的公交線路影射網絡圖Fig.2 Line mapping network for fig 1.

圖3 查詢線路第2步生成的多部圖Fig.3 Query line multipartite graph based on the second step

圖4 查詢線路第3步生成的約簡多部圖Fig.4 Query line reduction multipartite graph based on the third step

進一步可得到S1到S10的最優換乘為

從S1到S10乘車距離為w112＋w627＋w170，10＝3＋4＋8＝15。從S1到S10花費時間在［45，92］分鐘之間，平均為68.5min。到達時刻在［10∶45，11∶32］之間，平均到達時刻為11∶8.5。

5 結語

本文綜合考慮了公交網絡的時變性與不確定性，給出了公交網絡出行基于最小換乘次數條件下的最短路線的數學規劃模型，并將該規劃模型求解問題分解為線路影射網絡圖的最短路線問題和站點影射網絡圖的多階段決策問題，兩類問題都可用傳統的最短路算法解決。該規劃模型可以求出換乘站點、換乘線路以及乘車時間。如果將最短路優化改為最小換乘時間優化目標，利用該算法很容易實現。本文給出的數學規劃模型與算法基于公交線路與公交站點的關聯三維數組上，便于理解，容易推廣到大城市的實際公交網絡信息查詢上。

［1］ Ernesto C，Stefano G，Marco P.Transit network design：aprocedure and an application to a large urban area［J］.Transportation Research Part C，2012，20（1）：3－14.

［2］ Antonio M，María E U.A route set construction algorithm for the transit network design problem ［J］.Computers ＆ Operations Research，2009，36（8）：2440－2449.

［3］ Ceder A，Wilson N.Bus network design［J］.Transportation Research Part B，1986，20（4）：331－344.

［4］ Baaj M H，Mahmassani H.An AI－based approach for transit route system planning and design［J］.Journal of Advanced Transportation，1991，25（2）：187－210.

［5］ Tong C O，Wong S C.A stochastic transit assignment model using a dynamic schedule－based network［J］.Transportation Research Part B，1998，33（2）：107－121.

［6］Zhao F，Ubaka I.Optimization of transit network to minimize transfers and optimize route directness［J］.Journal of Public Transportation.2004，7（1）：63－82.

［7］ 邸振.基于最少換乘的公交系統網絡配流模型及算法［J］.系統科學學報，2011，19（3）：78－81.Di Zhen.An assignment model for transit network based on the least transfer［J］.Journal of Systems Science.2011，9（3）：78－81.

［8］ 四兵鋒，高自友.城市公交網絡均衡配流模型及算法的研究［J］.公路交通科技，1998，9（3）：41－44.Si Bingfeng，Gao Ziyou.A study on the equilibrium assignment model and algorithm for urban transit network［J］.Journal of Highway and Transportation Research and Development，1998，9（3）：41－44.

［9］ 宋一凡，高自友.擁擠條件下的公交平衡配流 ［J］.中國公路學報，1999，12（4）：88－95.Song Yifan，Gao Ziyou.Transit equilibrium assignment for congested public transport systems［J］.China Journal of Highway and Transport，1999，12（4）：88－95.

［10］ 高自友，宋一凡，四兵鋒，等.公交網絡中基于彈性需求和能力限制條件下的SUE配流模型及算法（Ⅰ）［J］.北方交通大學學報，2000，24（6）：1－7.Gao Ziyou，Song Yifan，Si Binfeng，et al.A SUE Assignment model and solution algorithm with elastic transit demand and bottlenecks for public transport networks（I）［J］.Journal of Northern Jiaotong University，2000，24（6）：1－7.

［11］ 高自友，宋一凡，四兵鋒，等.公交網絡中基于彈性需求和能力限制條件下的SUE配流模型及算法（Ⅱ）［J］.北方交通大學學報，2000，24（6）：8－13.Gao Ziyou，Song Yifan，Si Binfeng，et al.a SUE assignment model and solution algorithm with elastic transit demand and bottlenecks for public transport networks（II）［J］.Journal of Northern Jiaotong University，2000，24（6）：8－13.

［12］ 錢臻，陸化普.一種公交網絡客流分配方法及其實用性研究［J］.清華大學學報（自然科學版），2005，45（9）：1170－1174.Qian Zhen，Lu Huapu.An assignment method for transit network and its practical application［J］.Journal of Tsinghua University（Science and Technology），2005，45（9）：1170－1174.

［13］ 伍雁鵬，彭小奇，黃同成.基于路徑集合運算的公交網絡尋徑算法研究［J］.計算機科學，2009，36（6）：239－272.Wu Yanpeng，Peng Xiaoqi，Huang Tongcheng.Research on path set operation based algorithm for path searching in public transit network［J］.Computer Science，2009，36（6）：239－272.

［14］ 蘇愛華，施法中.公交網絡換乘問題的一種實現［J］.工程圖學學報，2005，（4）：55－59.Su Aihua，Shi Fazhong.Optimal route choice of public traffic network based on shortest path searching［J］.Journal of Engineering Graphics，2005，（4）：55－59.

［15］ 姚春龍，李旭，沈嵐.公交出行最優路徑搜索的有向賦權圖模型［J］.計算機應用研究，2013，30（4）：1058－1063.Yao Chunlong，Li Xu，Shen Lan.Weighted directed graph model for searching optimal travel routes by public transport［J］.Application Research of Computers，2013，30（4）：1058－1063.

［16］ 徐勇，李杰，張軍芳，等.新型公交網絡模型與最優線路選擇算法［J］.系統工程理論與實踐，2011，31（11）：2234－2240.Xu Yong，Li Jie，Zhang Junfang，et al.New urban transit network models and optimal path searching algorithm ［J］.Systems Engineering－Theory and Practice，2011，31（11）：2234－2240.

［17］ 溫金輝，劉偉銘.用于最短路算法的公交網絡模型構建［J］.交通標準化，2011，8（243）：177－178.Wen Jinhui，Liu Weiming.Public transit network modeling for shortest path algorithm［J］.Transport Standardization，2011，8（243）：177－178.

［18］ 周媛，鄧衛，胡啟洲.基于遺傳禁忌算法的城市公交線網優化研究［J］.武漢理工大學學報（交通科學與工程版），2011，35（01）：42－45.Zhou Yuan，Deng Wei，Hu Qizhou.Study on the optimization of public transit network based on genetic algorithm and tabu search algorithm［J］.Journal o f Wuhan University of Technology（Transportation Science ＆ Engineering），2011，35（1）：42－45.

［19］ 許倫輝，林泉.基于 GBAS的公交出行最優路徑選擇算法［J］.公路交通科技，2010，27（3）：154－158.Xu Lunhui，Lin Quan.Transit trip optimal route choice algorithm based on GBAS［J］.Journal of Highway and Transportation Research and Development，2010，27（3）：154－158.

［20］ 周文峰，李珍萍，劉洪偉，等.最優公交線路選擇問題的數學模型及算法［J］.運籌與管理，2008，17（5）：80－84.Zhou Wenfeng，Li Zhenping，Liu Hongwei，et al.Mathematical models and algorithms of optimal public transportation line choice problem［J］.Operations Research and Management Science，2008，17（5）：80－84.

［21］ 伍雁鵬，彭小奇，楊恒伏.改進的基于關系數據庫技術的公交查詢算法［J］.中南大學學報（自然科學版），2009，4（3）：763－766.Wu Yanpeng，Peng Xiaoqi，Yang Hengfu.Improved algorithm based on relational database technology for querying transit network［J］.Journal of Central South University（Science and Technology）.2009，4（3）：763－766.

［22］ 張淑娟，浮寸萍，金淑英.最短路徑算法用于城市公交出行路徑最優化［J］.現代測繪，2006，4：37－44.Zhang Shujuan，Fu Cunping，Jin Shuying.The application of the shortest path algorithm in the research of the best way of city bus［J］.Modern Surveying and Mapping，2006，4：37－44.

［23］ 喬梁，黃加翼，李云霄.基于 A＊算法城市急救救援最有路徑決策［J］.國防科技，2011，3：8－10.Qiao Liang，Huang Jiayi，Li Yunxiao.The path decision based on A＊for city emergency rescue［J］.Journal of National Defense Science and Technology，2011，3：8－10.

［24］ Li S G，Su Y M.Optimal transit path finding algorithm based on geographic information system ［C］.2003IEEE Proceedings of Intelligent Transportation Systems，2003，2：1670－1673.