一種改進的最短路徑算法在公交查詢系統中的應用研究

【摘 要】提出查詢算法HCCS，并將其運用在公交查詢系統的設計中。算法能求解多點間的以最少換乘次數為第一目標、最少出行時間為第二目標的公交出行方案。

【關鍵詞】最短路徑算法；換乘次數算法；公交查詢系統

【Abstract】This paper propose the inquiry algorithm HCCS， and use it in the transportation design. It can solve transport problems in multi-point at the minimum number of change for the first goal， and the least time at the second.

【Key words】The shortest path algorithm；The transfer times algorithm；Inquiry system of public transportation

0 引言

最短路徑問題是數據結構中圖論研究的經典問題，用來求解圖中任意兩點間的最短路徑，常應用于交通網絡中求兩點間的最短路徑。目前，求解最短路徑問題最成熟的算法是荷蘭數學家E.W.Dijkstra在1959年提出的Dijkstra算法。

一般意義上，完整的出行問題主要是解決從出發點到達目的地的路徑選優問題。隨著城市規模的擴大，人們的活動范圍變得更廣，選擇公交出行變得不再一車直達，可能需多次換乘才能到達目的地。基于此，如何選擇最優公交出行線路，即如何選擇換乘的次數及方式，越來越成為人們出行首要考慮的問題。

本文主要探討一種改進的Dijkstra算法，同時利用幾何圖形對搜索范圍加以限制，可用于解決多點間的最短路徑問題，并將其應用于公交查詢系統的設計中，可提高公交出行效率。

1 幾何圖形限制搜索線路范圍

1.1 橢圓限制算法

在一個網絡中給定起點和終點，即決定了最短路徑所對應的大致極限距離MP，據此可構造一個圓，以起點為圓心，以MP為半徑。以起點為原點，由極限距離所決定的地理服務范圍內的結點集合是圓內結點集合的真子集。圓外的點已超出了所估的極限距離，因此可在算法中不予考慮。設網絡中的一個點N到起點S和終點E的直線距離分別為|SN|、|EN|，限制條件可以寫為|SN|+|EN|≤MP。顯然，這正好形成了一個以S和E為焦點，以MP為長軸的橢圓。

橢圓限制算法使搜索規模大大減少，但計算過程中對每個結點都需判斷其是否在橢圓內部，大量非線性運算降低了算法效率。在最小包含多邊形中，三角形面積最大，隨著多邊形邊數的增加，多邊形的面積逐漸減少，直至逼近橢圓的面積，但是隨著最小包含多邊形邊數增多，多邊形限制的計算量將成倍增加。通過比較，找到最優的多邊形邊數為4。

1.2 平行四邊形限制分析

3 換乘次數查詢算法的設計

綜合選取最短路徑算法Dijkstra算法、換乘次數算法及平行四邊形限制路徑范圍的算法，設計公交系統的查詢算法——換乘次數算法。算法設計綜合了居民出行的多種影響因素，如：出行距離、出行時間、換乘次數、出行花費、出行舒適度等，形成以最少換乘次數為第一目標，以最短出行時間為第二目標的公交出行線路查詢解決方案。

3.1 算法思想

算法的主要設計思想：以換乘次數最少作為最優路徑算法的第一約束目標，以出行耗時最少為第二約束條件。選擇從A站到B站的出行線路，首先查找經過A站的車是否有直達B站的，若有，選擇直達車，若存在多條直達線路，再選擇距離最近的乘車方案；若無直達車，則考慮換一次車的方案：即判斷經過A站的車與經過B站的車是否有公共站C，若有，則可在公共站C轉車；若沒有換一次車的方案，則需考慮乘坐經過A點的車到某站C下車，判斷經過C站的車與經過B站的車是否有公共D，若有則到D轉車，即兩次轉車可到達B；若無，則需轉乘三次或以上才可到達目的地。在上述情況中，若存在多種選擇方案，則再根據乘車距離，選擇出行時間最短的乘車方案。

3.2 算法應用

以長春市公交網絡數據為例，在基于移動設備的公交查詢系統設計中應用了換乘次數查詢算法，查詢子系統中有三個主要功能：

（1）查詢站點A至站點B的公交路線；

（2）查詢經過站點A的公交路線；

（3）查詢公交車路線經過站點。

4 結論

本文基于對經典的最短路徑求解算法Dijkstra算法，及目前的幾種改進算法的比較研究，運用可提高路徑搜索效率的幾何圖形限制搜索范圍算法，提出了最優路徑查詢算法——換乘次數算法，并將其應用于公交查詢系統的設計中，經過測試，可實現查詢兩點間的換乘次數最少的乘車路線，提高了查詢效率，為公交出行提供了優質高效的線路方案，具有一定實際推廣應用價值。

【參考文獻】

[1]高嵐.公交查詢系統中查詢算法HCCS的研究與設計[D].吉林大學，2008，12.

[2]張三群.最短路徑算法在公交網絡中的應用[J].軟件導刊，2009（9）.

[3]馬東嶺.城市公交網絡的最短路徑算法研究[J].科技信息，2008（26）.

[責任編輯：劉展]