劉香菊 楊夏青 喬 石 房 麗

（齊魯理工學(xué)院 山東濟(jì)南 250200）

?

城市公共交通系統(tǒng)中的最佳路徑問題

劉香菊 楊夏青 喬 石 房 麗

（齊魯理工學(xué)院 山東濟(jì)南 250200）

摘 要：通過分析城市公共交通系統(tǒng)網(wǎng)絡(luò)圖的特點(diǎn)，采用改進(jìn)的Dijkstra 算法的最短路徑問題構(gòu)造公共交通網(wǎng)絡(luò)模型。最佳乘車路線的獲得，需要在滿足換乘次數(shù)要求的基礎(chǔ)上，提出換乘的實(shí)現(xiàn)算法，并在此過程中采用用換乘矩陣的形式描述最短路徑中的站點(diǎn)及線路。

關(guān)鍵詞：公共交通系統(tǒng) 最佳路徑 最短路 最小換乘

一、引言

研究公交換乘的問題，首先要解決的問題是合理地表述公共交通網(wǎng)絡(luò)模型；其次還需要對(duì)公交換乘問題思想做準(zhǔn)確描述［2］。本文將解決換乘算法的實(shí)現(xiàn)問題，在此過程中還需綜合考慮換乘次數(shù)的因素，距離因素的影響。

二、城市公共交通系統(tǒng)的特點(diǎn)［3］

與道路網(wǎng)絡(luò)有所不同，城市公共交通系統(tǒng)有其自身特點(diǎn)，公交網(wǎng)絡(luò)不能直接采用與道路網(wǎng)絡(luò)相同的模型。

1.結(jié)點(diǎn)性質(zhì)

在模擬不同公交線可換乘情況［4］時(shí)，需要考慮空間上比較接近的不同線路但同名的公交站點(diǎn)的抽象問題。

2.弧段性質(zhì)

由于弧段與屬性之間的一對(duì)多的關(guān)系，那么就會(huì)導(dǎo)致需重復(fù)記錄在公共交通系統(tǒng)中，每條公交線路通過的弧段，這必然導(dǎo)致數(shù)據(jù)冗余問題的出現(xiàn)。

3.有向線性質(zhì)

由于邊的有向性不能體現(xiàn)公交系統(tǒng)圖有向性特點(diǎn)，因此需要考慮另外的解決方法，即通過引入有向線路集的方法來解決。

三、建立城市公交系統(tǒng)模型

距離最短路段及最少換乘公交線路的集合構(gòu)成了最優(yōu)出行路徑。

本文將交通網(wǎng)絡(luò)模型采用“結(jié)點(diǎn)―弧段（可有多條弧段）―有向線”的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)網(wǎng)絡(luò)圖。公交網(wǎng)絡(luò)如圖1所示。

四、公交換乘問題的解決思想

為解決公交換乘問題，我們需要做下面一些具體工作：

1.求解最短路徑及其上的各個(gè)站點(diǎn)。

2.為獲得換乘方案，需先構(gòu)造最短路徑站點(diǎn)及線路對(duì)應(yīng)的換乘矩陣，并求解。

五、最短路徑求解

1.經(jīng)典最短路徑算法概述

（1）Dijkstra算法

（2）Bellman-Ford-Moore算法

（3）Floyd算法

（4）啟發(fā)式搜索算法——A*算法

A*算法提高了搜索過程的效率。引入已知的全局信息作為選擇下一個(gè)被檢查的結(jié)點(diǎn)的條件，為合理評(píng)價(jià)可能性的量度（該結(jié)點(diǎn)處于最優(yōu)路線上的）需對(duì)當(dāng)前結(jié)點(diǎn)距終點(diǎn)的距離作出估計(jì)。

2.公交線路查詢不適合采用傳統(tǒng)的Dijkstra算法

但是對(duì)公交網(wǎng)絡(luò)來說，由于如下幾方面原因，公交線路的查詢采用Dijkstra算法是不適合的：

（1）數(shù)據(jù)結(jié)構(gòu)復(fù)雜。

導(dǎo)致公交線路網(wǎng)絡(luò)圖的數(shù)據(jù)結(jié)構(gòu)模型復(fù)雜的原因主要是公交網(wǎng)絡(luò)節(jié)點(diǎn)與連通性的特殊性。

（2）算法時(shí)間長。

使用基于網(wǎng)絡(luò)的權(quán)矩陣及Dijkstra 算法求解最短路徑問題，在存儲(chǔ)圖形數(shù)據(jù)和進(jìn)行運(yùn)算時(shí)，需定義由網(wǎng)絡(luò)的結(jié)點(diǎn)數(shù)構(gòu)造的數(shù)組，當(dāng)網(wǎng)絡(luò)的結(jié)點(diǎn)數(shù)較大時(shí)大數(shù)組運(yùn)算浪費(fèi)時(shí)間。

3.基于改進(jìn) Dijkstra 算法的最短路徑求解

由于存在上述的缺陷，采用基于點(diǎn)邊拓?fù)潢P(guān)系的最短路徑算法。主要步驟如下：

（1）將目標(biāo)結(jié)點(diǎn)作為已到達(dá)結(jié)點(diǎn)，標(biāo)志為已到達(dá)結(jié)點(diǎn)。

（2）若已到達(dá)結(jié)點(diǎn)和起始結(jié)點(diǎn)相同，則執(zhí)行第（6）步，否則執(zhí)行第（3）步。

（3）如果存在未搜索結(jié)點(diǎn)則繼續(xù)第（4）步，否則執(zhí)行第（6）步。

（4）掃描標(biāo)志為已到達(dá)結(jié)點(diǎn)的結(jié)點(diǎn)的關(guān)聯(lián)結(jié)點(diǎn)，這些關(guān)聯(lián)結(jié)點(diǎn)不包括在已搜索節(jié)點(diǎn)表中已經(jīng)存在的結(jié)點(diǎn)。

（5）重復(fù)執(zhí)行第（2）步至第（4）步。

（6）為找出最短路徑，需從起始結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)對(duì)所有的已到達(dá)結(jié)點(diǎn)對(duì)進(jìn)行追蹤。

六、實(shí)現(xiàn)公交換乘的數(shù)學(xué)描述

圖 2：矩陣（1）

1.換乘矩陣存儲(chǔ)方式的改進(jìn)

若公交線路比較復(fù)雜，將導(dǎo)致矩陣（1）規(guī)模很大。公交線路矩陣表也可以作些改進(jìn)。方法如下：

若最短路徑上剛好包含了某條線路所經(jīng)全部站點(diǎn)，則在該條線路的關(guān)聯(lián)站點(diǎn)數(shù)組中將保存該這條路徑上站點(diǎn)的序號(hào)（該站點(diǎn)在矩陣中的位置號(hào)）。

如矩陣（1）中線路關(guān)聯(lián)站點(diǎn)數(shù)組，空間浪費(fèi)會(huì)有效減少。

2.多次換乘的實(shí)現(xiàn)流程

實(shí)現(xiàn)矩陣（1）中任意兩站點(diǎn)之間的換乘的問題的實(shí)現(xiàn)方法，可以采用用遞歸方法。具體流程圖如圖3。其中，起始站點(diǎn)在矩陣中的位置號(hào)用來表示；目標(biāo)站點(diǎn)在矩陣中的位置號(hào)用來表示；中轉(zhuǎn)次數(shù)為。求解與間的直達(dá)線路問題的方法，用來實(shí)現(xiàn)。

3.換乘方案的確定

表1 直達(dá)數(shù)據(jù)塊列表

最簡單的情形就是0次換乘，通過圖3流程求解出來的直達(dá)數(shù)據(jù)塊只有1個(gè)，如從起始點(diǎn)A至目標(biāo)點(diǎn)B，不用換乘。如果直達(dá)數(shù)據(jù)塊是不存在的，需要1次換乘的搜索。一次及以上的換乘的情況，得到的直達(dá)數(shù)據(jù)塊可能很多。這樣，在直達(dá)數(shù)據(jù)塊列表中就存儲(chǔ)了3個(gè)直達(dá)數(shù)據(jù)塊，如表1所示。

從表1中可以看出，要確定A站點(diǎn)到B站點(diǎn)的換乘方案，次數(shù)更多的方法依此類推。

七、結(jié)論

本文研究乘車路線問題采用的主要理論是最短路徑理論。首先獲得構(gòu)成最短路徑的站點(diǎn)；最佳乘車線路的獲得需要由這些站點(diǎn)及公交線路并采用換乘矩陣的方法。

參考文獻(xiàn)

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

［2］楊新苗， 王煒， 馬文騰. 基于城市道路網(wǎng)的最短路徑分析解決方案［J］. 小型微型計(jì)算機(jī)系統(tǒng)， 2003，24（7），1390-1393；

［3］陳立潮，劉玉樹，張永梅，潘廣貞. 城市交通智能咨詢系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)［J］. 計(jì)算機(jī)工程， 2003，29（1），32-34；

［4］夏春林 ，蔣瑞波 ，宋偉東. 道路網(wǎng)絡(luò)中最短路徑的算法與實(shí)現(xiàn)［J］. 遼寧工程技術(shù)大學(xué)學(xué)報(bào)， 2003，22（2）.180-181；

［5］張國強(qiáng)，晏克非. 城市道路網(wǎng)絡(luò)交通特性仿真模型及最短路徑算法［J］. 交通運(yùn)輸工程學(xué)報(bào).2002，2（3），60-62；