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

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

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

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

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

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

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

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

1.1 基于Flord的最小換乘算法

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

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

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

若存在一點(diǎn) 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 時(shí)，搜索停止。

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

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

1)初始化?；谧钚Q乘矩陣B，路徑矩陣DT與節(jié)點(diǎn)個(gè)數(shù)矩陣CT，通過Flord算法找出任意一條符合條件的最小換乘路徑(當(dāng)cNK+1，N0>1時(shí)，m=1)，同時(shí)初始化，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 基于最小換乘路徑的站點(diǎn)線路搜索法

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

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

2 算例

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

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

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

表1 各線路票價(jià)Tab.1 Fare table of each line

表2 各線路時(shí)刻Tab.2 Timetable of each line

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

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

同時(shí)得到其它兩條路徑:

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

表4 各方案線路、站點(diǎn)及費(fèi)用Tab.4 Line，station，fare of programs

3 結(jié)論

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

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

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

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

［4］蘇嘯，曾子維.基于關(guān)聯(lián)的城市公交換乘查詢算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，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é)報(bào):自然科學(xué)版，2004，32(4):264 －267.

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

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