城市公共交通系統中的最佳路徑問題

劉香菊 楊夏青 喬 石 房 麗

（齊魯理工學院 山東濟南 250200）

?

城市公共交通系統中的最佳路徑問題

劉香菊 楊夏青 喬 石 房 麗

（齊魯理工學院 山東濟南 250200）

摘 要：通過分析城市公共交通系統網絡圖的特點，采用改進的Dijkstra 算法的最短路徑問題構造公共交通網絡模型。最佳乘車路線的獲得，需要在滿足換乘次數要求的基礎上，提出換乘的實現算法，并在此過程中采用用換乘矩陣的形式描述最短路徑中的站點及線路。

關鍵詞：公共交通系統 最佳路徑 最短路 最小換乘

一、引言

研究公交換乘的問題，首先要解決的問題是合理地表述公共交通網絡模型；其次還需要對公交換乘問題思想做準確描述［2］。本文將解決換乘算法的實現問題，在此過程中還需綜合考慮換乘次數的因素，距離因素的影響。

二、城市公共交通系統的特點［3］

與道路網絡有所不同，城市公共交通系統有其自身特點，公交網絡不能直接采用與道路網絡相同的模型。

1.結點性質

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

2.弧段性質

由于弧段與屬性之間的一對多的關系，那么就會導致需重復記錄在公共交通系統中，每條公交線路通過的弧段，這必然導致數據冗余問題的出現。

3.有向線性質

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

三、建立城市公交系統模型

距離最短路段及最少換乘公交線路的集合構成了最優出行路徑。

本文將交通網絡模型采用“結點―弧段（可有多條弧段）―有向線”的數據結構來存儲網絡圖。公交網絡如圖1所示。

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

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

1.求解最短路徑及其上的各個站點。

2.為獲得換乘方案，需先構造最短路徑站點及線路對應的換乘矩陣，并求解。

五、最短路徑求解

1.經典最短路徑算法概述

（1）Dijkstra算法

（2）Bellman-Ford-Moore算法

（3）Floyd算法

（4）啟發式搜索算法——A*算法

A*算法提高了搜索過程的效率。引入已知的全局信息作為選擇下一個被檢查的結點的條件，為合理評價可能性的量度（該結點處于最優路線上的）需對當前結點距終點的距離作出估計。

2.公交線路查詢不適合采用傳統的Dijkstra算法

但是對公交網絡來說，由于如下幾方面原因，公交線路的查詢采用Dijkstra算法是不適合的：

（1）數據結構復雜。

導致公交線路網絡圖的數據結構模型復雜的原因主要是公交網絡節點與連通性的特殊性。

（2）算法時間長。

使用基于網絡的權矩陣及Dijkstra 算法求解最短路徑問題，在存儲圖形數據和進行運算時，需定義由網絡的結點數構造的數組，當網絡的結點數較大時大數組運算浪費時間。

3.基于改進 Dijkstra 算法的最短路徑求解

由于存在上述的缺陷，采用基于點邊拓撲關系的最短路徑算法。主要步驟如下：

（1）將目標結點作為已到達結點，標志為已到達結點。

（2）若已到達結點和起始結點相同，則執行第（6）步，否則執行第（3）步。

（3）如果存在未搜索結點則繼續第（4）步，否則執行第（6）步。

（4）掃描標志為已到達結點的結點的關聯結點，這些關聯結點不包括在已搜索節點表中已經存在的結點。

（5）重復執行第（2）步至第（4）步。

（6）為找出最短路徑，需從起始結點到目標結點對所有的已到達結點對進行追蹤。

六、實現公交換乘的數學描述

圖 2：矩陣（1）

1.換乘矩陣存儲方式的改進

若公交線路比較復雜，將導致矩陣（1）規模很大。公交線路矩陣表也可以作些改進。方法如下：

若最短路徑上剛好包含了某條線路所經全部站點，則在該條線路的關聯站點數組中將保存該這條路徑上站點的序號（該站點在矩陣中的位置號）。

如矩陣（1）中線路關聯站點數組，空間浪費會有效減少。

2.多次換乘的實現流程

實現矩陣（1）中任意兩站點之間的換乘的問題的實現方法，可以采用用遞歸方法。具體流程圖如圖3。其中，起始站點在矩陣中的位置號用來表示；目標站點在矩陣中的位置號用來表示；中轉次數為。求解與間的直達線路問題的方法，用來實現。

3.換乘方案的確定

表1 直達數據塊列表

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

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

七、結論

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

參考文獻

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

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

［3］陳立潮，劉玉樹，張永梅，潘廣貞. 城市交通智能咨詢系統的設計與實現［J］. 計算機工程， 2003，29（1），32-34；

［4］夏春林 ，蔣瑞波 ，宋偉東. 道路網絡中最短路徑的算法與實現［J］. 遼寧工程技術大學學報， 2003，22（2）.180-181；

［5］張國強，晏克非. 城市道路網絡交通特性仿真模型及最短路徑算法［J］. 交通運輸工程學報.2002，2（3），60-62；