城際公共交通系統最短路算法

黃遠春，胥耀方，潘海澤

(1.上海工程技術大學城市軌道交通學院，上海201620;2.北京交通大學交通運輸學院，北京100044)

隨著我國城市化建設與區域經濟發展，“城際通道”的結構也不斷調整與完善，逐漸形成了以鐵路交通為主，公路交通為輔的網絡模式。城際公共交通系統，包括鐵路系統和長途客運系統，是城際通道的重要組成部分，為出行者提供了多樣的出行路徑。在路徑選擇時，出行者總是根據個人偏好選擇出行路線(或希望出行費用最低，或希望換乘次數最少，或希望出行時間最少)，可稱為最短路徑因素。筆者針對城際公共交通網絡的特點，綜合考慮換乘、時間、票價等因素，提出一種基于Flord算法的最小換乘矩陣及對應路徑的獲取方法，并利用最小換乘路徑進行站線搜索與費用計算，獲取城際交通的最短路。

1 城際網絡概況

城際運輸網絡不同于城市道路網，其主要具有線路連通性［2－3］、站點差異性、班次固定性、線路差異性等特點。在城市道路網中，某一路徑的耗時為固定值，但在城際網絡中，由于交通方式或線路條件的差異，即使行駛相同的路徑，不同線路也會產生不同的耗時，從而形成不同的交通阻抗。

從城際網絡的特點中不難發現，線路及相關信息是城際運輸網絡最短路中的關鍵因素，而由于不可能在任何一對城市之間都開行直達線路，城際交通中必須充分考慮換乘問題，楊新苗等［3］研究也表明，換乘次數最少是乘客出行考慮的首要因素。雖然該研究側重于城市公交路網，但在城際運輸網絡中，如果換乘次數增加，則由此引起的不可預知的因素也會大大增加，如車輛到來的時間、路況，換乘時需要步行的距離等都會引起途中時間的延長［4］。因此，換乘導致的出行時間增加和旅行舒適性的降低，將會嚴重影響乘客對出行方式的選擇。所以，本算法將以換乘次數最小為首要目標，時間與票價綜合費用最小作為為第2目標，來獲取城際運輸的最短路。

很多學者研究了基于換乘次數最小的最短路算法，張林峰等［5］于2003年利用圖論對公交網絡進行分析，通過對換乘矩陣的迭代，獲取最小換乘矩陣;王莉等［6］于2004年引入直達矩陣和最小換乘矩陣的算法，討論公交網絡節點間換乘問題，得出最少換乘算法。以上2種方法通過建立最小換乘矩陣來獲取OD點之間的最小換乘次數，雖然能夠較快地獲取最小換乘矩陣，但必須重新搜索路徑，并且無法體現最小換乘次數受到已成生換乘次數的影響，導致最終換乘次數可能超過要求的最小換乘次數。針對此問題，翁敏等［7］于2004年采用結點－弧段－有向線的方法，以線路，站點為基礎，對公交網絡的數據重新組織，研究了以最小換乘次數為首要目標的出行路徑選擇模型;廖楚江等［8］利用武漢市數據對這種線路站點算法進行計算機實現，但對系統提出了較高要求。由此可見，以線路站點為基礎獲取最小換乘路徑的算法，雖然能夠準確地捕捉最短換乘路徑，但由于需要對所選線路上所有站點進行篩選而導致搜索時間較長，路網越大該缺點越為明顯，并且，該算法現多用于城市公交網絡，沒有考慮不同線路在站點的到發時間影響。為解決搜尋最短換乘路徑困難的現狀，筆者基于Flord算法建立最小換乘矩陣，同時獲取最小換乘路徑，然后在確定的換乘站點中，搜索通行線路，最后通過比選，得到最小換乘次數下，廣義費用最小的出行路徑。

1.1 基于Flord的最小換乘算法

本算法以不同站點之間的可達性為權重，建立初始的可達矩陣H0與路徑矩陣D0，然后通過Flord算法對H矩陣進行迭代，當發現不大于原路徑換乘次數的新路徑時，則更新Ht矩陣與Dt矩陣。需要說明的是，原有的Flord算法僅更新權重小于已存路徑的新路徑信息，該算法只能找出一條最短路，但由于城際交通網絡的復雜性，存在多條滿足最小換乘次數路徑，因此，本算法將記錄小于或等于已存路徑的新路徑信息，同時增加路徑矩陣Dt的維數，利用其記錄多個換乘次數最少的換乘站點，并通過矩陣Ct記錄站點個數，記錄最終獲得所有滿足最小換乘次數的路徑。具體步驟如下:

1)初始化矩陣 H0，D0。其中換乘節點個數c0i，j=0，最小換乘次數的連通站點數d0i，j，m=j

2)更新矩陣H，D。對p=1…T，進行如下的搜索:對于所有的 i，j，若存在一點 p(t≠i，j)，使hi，p+hp，j>hi，j，則 hi，j=hi，p+hp，j，ci，j=1。

若存在一點 p(p≠i，j)，使 hi，p+hp，j=hi，j，則ci，j=ci，j+1;di，j，m=p;m=ci，j。當 p=T 時，搜索停止。

3)最小換乘矩陣。經過T次迭代，得到可達矩陣HT，即可求取最小換乘矩陣B。

4)識別最小換乘路徑。對最小換乘矩陣B，可識別任意起點Ns與終點Ne之間的換乘次數，令其路徑可分為以下 3類:

1)初始化。基于最小換乘矩陣B，路徑矩陣DT與節點個數矩陣CT，通過Flord算法找出任意一條符合條件的最小換乘路徑(當cNK+1，N0>1時，m=1)，同時初始化，mk，即 u=1;初始路徑為:［1，K］;mk=1，k∈［1，K］;k=K;轉2);

2)比較mk與。若，轉3);若 mk，轉7);

7)結束判斷。若 k>1，k=k－1，轉2);若 k=1，結束。

1.2 基于最小換乘路徑的站點線路搜索法

由前面得到的u條最短換乘路徑，分別搜索各個換乘站之間的鐵路或公路線路，再將對于同一換乘路徑(即換乘站點固定)不同區段的線路排列組合，得到多種線路換乘方案，最后，比較不同換乘路徑不同線路換乘方案下的廣義費用，取最優組合。需要說明的是，本算法將換乘次數作為了首要選擇條件，第2目標選定了由票價和時間組成的廣義費用，票價的時間價值換算公式如下:

于是，廣義費用的目標函數如下，其中第1部分為線路運行區間票價的時間價值;第2部分為線路運行時間;第3部分為換乘需要消耗時間:

2 算例

以圖1路網為例，求取Ns=1，Ne=7之間的最佳路徑，各線路的票價表以及時刻表分別如表1、表2，為方便起見，假定本算例中必要換乘時間均為30 min。

易知T=7，根據不同站點之間的可達性建立D0，C0，H0，然后通過 2.1 的算法最小換乘矩陣 B，換乘節點個數矩陣CT，路徑存儲矩陣DT。根據本算例提取各矩陣中的數據分別如表3。

圖1 城際交通路網圖Fig.1 Intercity road network map

表1 各線路票價Tab.1 Fare table of each line

表2 各線路時刻Tab.2 Timetable of each line

表3 各矩陣中的數據值Tab.3 Timetable of each line

對矩陣進行最短路辨別，首先初始化，易知K=b1，7=2，令 m=1，u=1 使用原始的 Floyd 算法搜索在從表3中得到第一條最短換乘路徑:

同時得到其它兩條路徑:

得到所有最短換乘路徑之后，按照2.2的站點搜索法，得到各出行方案及廣義費用如表4，因此得到最短路徑為方案2。

表4 各方案線路、站點及費用Tab.4 Line，station，fare of programs

3 結論

在綜合考慮換乘、時間、票價等因素的基礎上，提出一種基于Floyd算法的最小換乘矩陣及對應路徑的算法，并利用最小換乘路徑進行站線搜索與費用計算，從而獲取城際交通的最短路。該算法不僅可以準確地捕捉最小換乘路徑，簡化了路徑搜索的過程，同時考慮了城際交通所特有的換乘時間因素，增強了算法的適用性，城際交通換乘的研究具有重要參考價值和借鑒意義。

［1］牛學勤，王煒.基于最短路搜索的多路徑公交客流分配模型研究［J］. 東南大學學報:自然科學版，2002，32(6):917－919.

［2］徐業昌，李樹詳.基于地理信息系統的最短路徑搜索算法［J］.中國圖像圖形學報，1998，3(1):39 －43.

［3］楊新苗，王煒，馬文騰.基于GIS的公交乘客出行路徑選擇模型［J］.東南大學學報:自然科學版，2000，30(6):87 －91.

［4］蘇嘯，曾子維.基于關聯的城市公交換乘查詢算法［J］.計算機工程與設計，2006，27(3):519－521.

［5］張林峰，范炳全，呂智林.公交網絡換乘矩陣的分析與算法［J］.系統工程，2003，21(6):92 －96.

［6］王莉，李文權.公共交通系統最佳路徑算法［J］.東南大學學報:自然科學版，2004，32(4):264 －267.

［7］翁敏，毋河海，杜清運，等.基于公交網絡模型的最優出行路徑選擇的研究［J］.武漢大學學報:信息科學版，2004，29(6):500－503.

［8］廖楚江，蔡忠亮，杜清運，等.基于最少換乘的公交最優路徑算法的設計與實現［J］.武漢大學學報:信息科學版，2006，31(10):904－907.