一種改進(jìn)的最短路徑算法在公交查詢系統(tǒng)中的應(yīng)用研究

【摘 要】提出查詢算法HCCS，并將其運(yùn)用在公交查詢系統(tǒng)的設(shè)計(jì)中。算法能求解多點(diǎn)間的以最少換乘次數(shù)為第一目標(biāo)、最少出行時(shí)間為第二目標(biāo)的公交出行方案。

【關(guān)鍵詞】最短路徑算法；換乘次數(shù)算法；公交查詢系統(tǒng)

【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 引言

最短路徑問題是數(shù)據(jù)結(jié)構(gòu)中圖論研究的經(jīng)典問題，用來求解圖中任意兩點(diǎn)間的最短路徑，常應(yīng)用于交通網(wǎng)絡(luò)中求兩點(diǎn)間的最短路徑。目前，求解最短路徑問題最成熟的算法是荷蘭數(shù)學(xué)家E.W.Dijkstra在1959年提出的Dijkstra算法。

一般意義上，完整的出行問題主要是解決從出發(fā)點(diǎn)到達(dá)目的地的路徑選優(yōu)問題。隨著城市規(guī)模的擴(kuò)大，人們的活動范圍變得更廣，選擇公交出行變得不再一車直達(dá)，可能需多次換乘才能到達(dá)目的地?；诖耍绾芜x擇最優(yōu)公交出行線路，即如何選擇換乘的次數(shù)及方式，越來越成為人們出行首要考慮的問題。

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

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

1.1 橢圓限制算法

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

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

1.2 平行四邊形限制分析

3 換乘次數(shù)查詢算法的設(shè)計(jì)

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

3.1 算法思想

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

3.2 算法應(yīng)用

以長春市公交網(wǎng)絡(luò)數(shù)據(jù)為例，在基于移動設(shè)備的公交查詢系統(tǒng)設(shè)計(jì)中應(yīng)用了換乘次數(shù)查詢算法，查詢子系統(tǒng)中有三個(gè)主要功能：

（1）查詢站點(diǎn)A至站點(diǎn)B的公交路線；

（2）查詢經(jīng)過站點(diǎn)A的公交路線；

（3）查詢公交車路線經(jīng)過站點(diǎn)。

4 結(jié)論

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

【參考文獻(xiàn)】

[1]高嵐.公交查詢系統(tǒng)中查詢算法HCCS的研究與設(shè)計(jì)[D].吉林大學(xué)，2008，12.

[2]張三群.最短路徑算法在公交網(wǎng)絡(luò)中的應(yīng)用[J].軟件導(dǎo)刊，2009（9）.

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

[責(zé)任編輯：劉展]