城際公共交通系統(tǒng)最短路算法

黃遠(yuǎn)春，胥耀方，潘海澤

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

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

1 城際網(wǎng)絡(luò)概況

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

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

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

1.1 基于Flord的最小換乘算法

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

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

2)更新矩陣H，D。對p=1…T，進(jìn)行如下的搜索:對于所有的 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。當(dāng) p=T 時，搜索停止。

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

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

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

2)比較mk與。若，轉(zhuǎn)3);若 mk，轉(zhuǎn)7);

7)結(jié)束判斷。若 k>1，k=k－1，轉(zhuǎn)2);若 k=1，結(jié)束。

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

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

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

2 算例

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

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

圖1 城際交通路網(wǎng)圖Fig.1 Intercity road network map

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

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

表3 各矩陣中的數(shù)據(jù)值Tab.3 Timetable of each line

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

同時得到其它兩條路徑:

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

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

3 結(jié)論

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

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

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

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

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

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

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

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

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