時變公交網(wǎng)絡的數(shù)學規(guī)劃模型與算法

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

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

0 引言

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

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

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

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

1 時變公交網(wǎng)絡的高維數(shù)組表示

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

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

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

2 時變公交網(wǎng)絡的換乘查詢優(yōu)化模型

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

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

3 基于影射網(wǎng)絡數(shù)學規(guī)劃求解算法

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

第1步，基于站點與線路的關聯(lián)關系確定途徑出發(fā)站點Si的線路集合，終止站點Sj的線路集合

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

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

3.1 基于線路影射網(wǎng)絡的最小換乘次數(shù)算法

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

3.2 基于站點影射網(wǎng)絡圖的最短路線算法

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

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

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

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

4 算例

為了說明本文給出的時變公交網(wǎng)絡系統(tǒng)的查詢算法，以如圖1所示的含有12條公交線路以及他們之間的10個交叉公交站點的公交網(wǎng)絡為例，公交網(wǎng)絡中各站點到公交線路始點距離（括號內(nèi)數(shù)字）：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）。

假設各條公交線路的運行時間區(qū)間：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的換乘次數(shù)、乘車距離和乘車時間。首先建立該公交網(wǎng)絡系統(tǒng)的線路網(wǎng)絡影射圖（圖2）。

由換乘次數(shù)算法第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所示。

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

若查詢時間為10∶00點，且給出L1，L6，L10的發(fā)車頻率為每小時3，4，5班，L3，L9，L12發(fā)車頻率為每小時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分鐘，對應的優(yōu)化問題（3）為

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

圖2 圖1的公交線路影射網(wǎng)絡圖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的最優(yōu)換乘為

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

5 結語

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

［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］ 邸振.基于最少換乘的公交系統(tǒng)網(wǎng)絡配流模型及算法［J］.系統(tǒng)科學學報，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］ 四兵鋒，高自友.城市公交網(wǎng)絡均衡配流模型及算法的研究［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］ 高自友，宋一凡，四兵鋒，等.公交網(wǎng)絡中基于彈性需求和能力限制條件下的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］ 高自友，宋一凡，四兵鋒，等.公交網(wǎng)絡中基于彈性需求和能力限制條件下的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］ 錢臻，陸化普.一種公交網(wǎng)絡客流分配方法及其實用性研究［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］ 伍雁鵬，彭小奇，黃同成.基于路徑集合運算的公交網(wǎng)絡尋徑算法研究［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］ 蘇愛華，施法中.公交網(wǎng)絡換乘問題的一種實現(xiàn)［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］ 姚春龍，李旭，沈嵐.公交出行最優(yōu)路徑搜索的有向賦權圖模型［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］ 徐勇，李杰，張軍芳，等.新型公交網(wǎng)絡模型與最優(yōu)線路選擇算法［J］.系統(tǒng)工程理論與實踐，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］ 溫金輝，劉偉銘.用于最短路算法的公交網(wǎng)絡模型構建［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］ 周媛，鄧衛(wèi)，胡啟洲.基于遺傳禁忌算法的城市公交線網(wǎng)優(yōu)化研究［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的公交出行最優(yōu)路徑選擇算法［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］ 周文峰，李珍萍，劉洪偉，等.最優(yōu)公交線路選擇問題的數(shù)學模型及算法［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］ 伍雁鵬，彭小奇，楊恒伏.改進的基于關系數(shù)據(jù)庫技術的公交查詢算法［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］ 張淑娟，浮寸萍，金淑英.最短路徑算法用于城市公交出行路徑最優(yōu)化［J］.現(xiàn)代測繪，2006，4：37－44.Zhang Shujuan，F(xiàn)u 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īng)Q策［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.