城市公交換乘查詢系統(tǒng)的優(yōu)化枚舉算法研究與應(yīng)用

徐熾

摘 要：該文針對目前我國城市公交查詢系統(tǒng)存在的不足，提出了一種便于乘客進(jìn)行路線選擇的優(yōu)化枚舉算法，并探討了以換乘次數(shù)最少為目標(biāo)的公交查詢方案。對n次公交換乘算法進(jìn)行改進(jìn)，引入緊鄰站點和站站快表，提高公交查詢系統(tǒng)的實用性和查詢效率，從而吸引出行者優(yōu)先選擇公交車出行方式。

關(guān)鍵詞：公交查詢 優(yōu)化枚舉算法 Java Applet 最少換乘

中圖法分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：1674-098X（2014）09（b）-0195-02

隨著我國社會經(jīng)濟(jì)的發(fā)展，人民出行頻率不斷增加，交通問題日益突出，而城市公共交通具有運量大、人均占有道路少等優(yōu)點。城市道路基礎(chǔ)建設(shè)規(guī)模擴(kuò)大的同時，道路的延伸后，隨之滿足人民需要的公交線路也在不斷地增加。為市民提供便捷的查詢系統(tǒng)，為方便地提供給人們出行時選擇最優(yōu)的公交換乘方案。在多種交通出行方式的復(fù)雜情況下，如果通過換乘進(jìn)行協(xié)調(diào)配合，那么將會提高公共交通的利用率，從而有效減少重復(fù)投資建設(shè)的現(xiàn)象。

由于我國在公共交通管理方面還處于較低水平，推行公共交通換乘方面沒有加強，因此，在公交換乘系統(tǒng)的開發(fā)方面，也處于起步階段。然而，隨著信息技術(shù)的快速發(fā)展，公交換乘查詢系統(tǒng)的開發(fā)及推廣也勢在必行。目前，我國公交換乘查詢系統(tǒng)仍存在一些問題[1]。

（1）公交線網(wǎng)管理混亂，沒有建成換乘樞紐。

（2）公交信息查詢系統(tǒng)終端沒有普及。

（3）公交查詢信息單一，不能滿足出行者需求。

（4）查詢信息陳舊，沒有數(shù)據(jù)維護(hù)管理員。

1 公交換乘理論基礎(chǔ)

公交換乘從換乘交通工具的一致性來講，主要分為多方式換乘和普通換乘。多方式換乘是指換乘前后所采用的交通方式不同；而普通換乘則是指換乘前后的交通方式是一樣的。本系統(tǒng)所要設(shè)計的換乘系統(tǒng)主要指的是普通換乘，主要針對公交這種特定的交通方式進(jìn)行設(shè)計。

公共交通線路網(wǎng)的結(jié)構(gòu)可按三種不同的線路網(wǎng)組成，分別是：放射形線路網(wǎng)、主干線和駁運線相結(jié)合的線路網(wǎng)、帶有環(huán)線或切線狀線路的放射形線路網(wǎng)[2-3]。

公交換乘的特性：

（1）換乘的必要性。

（2）換乘的有效性。

（3）換乘的多功能性。

2 優(yōu)化枚舉快速算法研究

基于距離最短的換乘方式，人們考慮更多的是減少換乘次數(shù)，避免換乘頻繁帶來的麻煩。因此，換乘理論中，基于換乘次數(shù)最少的方式，與實際換乘系統(tǒng)的應(yīng)用聯(lián)系更為緊密?；趽Q乘次數(shù)最少的換乘算法的算法思想核心是，根據(jù)調(diào)查顯示[4]，出行者出行時對于公交線路的選擇時，多數(shù)優(yōu)先考慮是否有直達(dá)車，如圖1（a）所示。如果沒有直達(dá)車，則考慮一次換乘的方案，然后考慮中間站的位置，如圖1（b）所示。如果沒有一次換乘的方案，則考慮多次換乘，二次換乘如圖1（c）所示，三次換乘如圖1（d）所示。

基于優(yōu)化枚舉快速算法，通常情況下搜索得出的換乘次數(shù)要比實際公交換乘次數(shù)多。原因是算法理論搜索得出的是只考慮在原地?fù)Q乘的結(jié)果；而在實際生活中，同一區(qū)域站點設(shè)置有一定的短距離，出行者會通過步行轉(zhuǎn)到換乘點。因此，出現(xiàn)了查詢換乘次數(shù)較多的現(xiàn)象。所以，在后續(xù)設(shè)計換乘查詢模塊時，應(yīng)考慮到同一區(qū)域范圍內(nèi)的所有站點情況。

基于優(yōu)化枚舉快速算法的基本思想：如果確定起始站點Q、終點站Z出發(fā)，與數(shù)據(jù)庫中各個線路中的站點相比較，尋找可換乘車站，得出可能的路徑。

設(shè)S（I）（I=1，2，…，m）為經(jīng)過起始站Q 的線路集合。

T（J）（J=1，2，…，p）為線路S（I）上的所有站點的集合。

F（J，V）（V=1，2，…，g）為線路T（J）上的所有站點集合。

R（K）（K=1，2，…，g）為經(jīng)過站點 E（I，U）的線路集合。

Y（O）（O=1，2，…Z）為經(jīng)過 F（J，V）的線路集合。

G（K，W）（W=1，2，…i）為線路 R（K）上的站點集合。

算法的步驟如下：

根據(jù)出行目的確定起始站Q和終點站 Z。

分別求經(jīng)過起始站Q的所有線路集 S（I），以及經(jīng)過終點站Z的所有線路集 T（J）。

經(jīng)過判斷條件S（I）與T（J）是否相等。如果相等，即存在直達(dá)線路，輸出結(jié)果T（J）；如果沒有則進(jìn)行下一步。

求線路S（I）上的站點E（I，U）以及線路 T（J）上的站點F（J，V）。

分別求經(jīng)過E（I，U）的線路集 R（K），和經(jīng)過 F（J，V）的線路集Y（O）。

經(jīng)過判斷條件R（K）=Y（O）是否相等。如果相等，則得出兩次換乘的一條可行路徑 S（I），R（K），T（J），經(jīng)過的中間換乘站點為 E（I，U）和 F（J，V），輸出結(jié)果，結(jié)束運算。

3 查詢系統(tǒng)的實現(xiàn)

本公交查詢系統(tǒng)的功能主要包括：電子地圖繪制和操作、公交線路查詢、公交站點查詢以及公交換乘的查詢等。其公交查詢的頁面如圖2所示。

優(yōu)化枚舉快速算法算法的算法思想核心是，根據(jù)調(diào)查顯示，出行者出行時對于公交線路的選擇時，多數(shù)優(yōu)先考慮是否有直達(dá)車，如果沒有直達(dá)車，則考慮一次換乘的方案，然后考慮中間站的位置，如果沒有一次換乘的方案，則考慮多次換乘。通常情況下搜索得出的換乘次數(shù)要比實際公交換乘次數(shù)多。原因是算法理論搜索得出的是只考慮在原地?fù)Q乘的結(jié)果；而在實際生活中，同一區(qū)域站點設(shè)置有一定的短距離，出行者會通過步行轉(zhuǎn)到換乘點。因此，出現(xiàn)了查詢換乘次數(shù)較多的現(xiàn)象。

換乘查詢模塊，進(jìn)入路徑查詢時，共有兩種選擇，一是直達(dá)，另一個是換乘一次。進(jìn)入界面后先在起點站和終點站輸入框中點擊選擇站點，或者輸入起點站和終點站的名稱，點擊“查詢”按鈕，查詢結(jié)果顯示在下面的列表框中，列表框中結(jié)果包括這兩點之間的所有路線。查詢用戶根據(jù)出行行為傾向選擇其中任一結(jié)果，點擊顯示詳細(xì)信息。若查詢的起終點之間存在直達(dá)線路，則系統(tǒng)優(yōu)先得出直達(dá)的查詢結(jié)果，即顯示出經(jīng)過這兩個站點的所有直達(dá)線路的所有站點及其詳細(xì)路徑。若查詢的起終點之間不存在直達(dá)線路，則系統(tǒng)自動進(jìn)入一次換乘，需要通過輸入中間站點名稱來得出用戶想要經(jīng)過的中間地點。若查詢的起終點之間沒有換乘方案，則系統(tǒng)顯示出沒有查詢結(jié)果，并且提示用戶進(jìn)行二次換乘，繼續(xù)輸入二次換乘的中間站點名稱，或者修改查詢的起終點名稱。

試驗結(jié)果表明，用戶輸入需要查詢的公交線路，系統(tǒng)通過相應(yīng)的線路路段中相應(yīng)的字段或者車次號，獲取該車次所經(jīng)過的所有站點；也可以根據(jù)給出的一個站點，查詢出經(jīng)過該站點的所有公交車，從而為用戶提供更多的公交信息。

4 結(jié)語

該論文在分析和總結(jié)公交站點、公交線路等公交數(shù)據(jù)的特點基礎(chǔ)之上，改進(jìn)了公交換乘的算法，引入了緊鄰站點和站站快表，使算法更符合生活中人們的實際需求和提高了查詢的效率。系統(tǒng)實現(xiàn)多種換乘查詢的方式，不僅能滿足不同乘客的不同需求，在換乘查詢過程中，得出的結(jié)論也更為合理。因此算法具有很強的實用性和通用性，在公交網(wǎng)絡(luò)中可以廣泛采用。

參考文獻(xiàn)

[1] 王建聰，高利平，陳紹寬，等.城市公共交通樞紐換乘組織仿真研究[J].交通運輸系統(tǒng)工程與信息，2006，6（6）：68-69.

[2] 趙巧霞，馬志強，張發(fā).以最小換乘次數(shù)和站數(shù)為目標(biāo)的公交出行算法[J].計算機(jī)應(yīng)用，2004，24（12）：90-92.

[3] 文洪建.小城市公交換乘優(yōu)化算法設(shè)計[J].中國科技信息，2010（13）：11-13.

[4] 胡云峰.公交換乘系統(tǒng)的數(shù)據(jù)庫結(jié)構(gòu)及算法優(yōu)化[J].文山學(xué)院學(xué)報，2010（2）：22-25.endprint

摘 要：該文針對目前我國城市公交查詢系統(tǒng)存在的不足，提出了一種便于乘客進(jìn)行路線選擇的優(yōu)化枚舉算法，并探討了以換乘次數(shù)最少為目標(biāo)的公交查詢方案。對n次公交換乘算法進(jìn)行改進(jìn)，引入緊鄰站點和站站快表，提高公交查詢系統(tǒng)的實用性和查詢效率，從而吸引出行者優(yōu)先選擇公交車出行方式。

關(guān)鍵詞：公交查詢 優(yōu)化枚舉算法 Java Applet 最少換乘

中圖法分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：1674-098X（2014）09（b）-0195-02

隨著我國社會經(jīng)濟(jì)的發(fā)展，人民出行頻率不斷增加，交通問題日益突出，而城市公共交通具有運量大、人均占有道路少等優(yōu)點。城市道路基礎(chǔ)建設(shè)規(guī)模擴(kuò)大的同時，道路的延伸后，隨之滿足人民需要的公交線路也在不斷地增加。為市民提供便捷的查詢系統(tǒng)，為方便地提供給人們出行時選擇最優(yōu)的公交換乘方案。在多種交通出行方式的復(fù)雜情況下，如果通過換乘進(jìn)行協(xié)調(diào)配合，那么將會提高公共交通的利用率，從而有效減少重復(fù)投資建設(shè)的現(xiàn)象。

由于我國在公共交通管理方面還處于較低水平，推行公共交通換乘方面沒有加強，因此，在公交換乘系統(tǒng)的開發(fā)方面，也處于起步階段。然而，隨著信息技術(shù)的快速發(fā)展，公交換乘查詢系統(tǒng)的開發(fā)及推廣也勢在必行。目前，我國公交換乘查詢系統(tǒng)仍存在一些問題[1]。

（1）公交線網(wǎng)管理混亂，沒有建成換乘樞紐。

（2）公交信息查詢系統(tǒng)終端沒有普及。

（3）公交查詢信息單一，不能滿足出行者需求。

（4）查詢信息陳舊，沒有數(shù)據(jù)維護(hù)管理員。

1 公交換乘理論基礎(chǔ)

公交換乘從換乘交通工具的一致性來講，主要分為多方式換乘和普通換乘。多方式換乘是指換乘前后所采用的交通方式不同；而普通換乘則是指換乘前后的交通方式是一樣的。本系統(tǒng)所要設(shè)計的換乘系統(tǒng)主要指的是普通換乘，主要針對公交這種特定的交通方式進(jìn)行設(shè)計。

公共交通線路網(wǎng)的結(jié)構(gòu)可按三種不同的線路網(wǎng)組成，分別是：放射形線路網(wǎng)、主干線和駁運線相結(jié)合的線路網(wǎng)、帶有環(huán)線或切線狀線路的放射形線路網(wǎng)[2-3]。

公交換乘的特性：

（1）換乘的必要性。

（2）換乘的有效性。

（3）換乘的多功能性。

2 優(yōu)化枚舉快速算法研究

基于距離最短的換乘方式，人們考慮更多的是減少換乘次數(shù)，避免換乘頻繁帶來的麻煩。因此，換乘理論中，基于換乘次數(shù)最少的方式，與實際換乘系統(tǒng)的應(yīng)用聯(lián)系更為緊密?；趽Q乘次數(shù)最少的換乘算法的算法思想核心是，根據(jù)調(diào)查顯示[4]，出行者出行時對于公交線路的選擇時，多數(shù)優(yōu)先考慮是否有直達(dá)車，如圖1（a）所示。如果沒有直達(dá)車，則考慮一次換乘的方案，然后考慮中間站的位置，如圖1（b）所示。如果沒有一次換乘的方案，則考慮多次換乘，二次換乘如圖1（c）所示，三次換乘如圖1（d）所示。

基于優(yōu)化枚舉快速算法，通常情況下搜索得出的換乘次數(shù)要比實際公交換乘次數(shù)多。原因是算法理論搜索得出的是只考慮在原地?fù)Q乘的結(jié)果；而在實際生活中，同一區(qū)域站點設(shè)置有一定的短距離，出行者會通過步行轉(zhuǎn)到換乘點。因此，出現(xiàn)了查詢換乘次數(shù)較多的現(xiàn)象。所以，在后續(xù)設(shè)計換乘查詢模塊時，應(yīng)考慮到同一區(qū)域范圍內(nèi)的所有站點情況。

基于優(yōu)化枚舉快速算法的基本思想：如果確定起始站點Q、終點站Z出發(fā)，與數(shù)據(jù)庫中各個線路中的站點相比較，尋找可換乘車站，得出可能的路徑。

設(shè)S（I）（I=1，2，…，m）為經(jīng)過起始站Q 的線路集合。

T（J）（J=1，2，…，p）為線路S（I）上的所有站點的集合。

F（J，V）（V=1，2，…，g）為線路T（J）上的所有站點集合。

R（K）（K=1，2，…，g）為經(jīng)過站點 E（I，U）的線路集合。

Y（O）（O=1，2，…Z）為經(jīng)過 F（J，V）的線路集合。

G（K，W）（W=1，2，…i）為線路 R（K）上的站點集合。

算法的步驟如下：

根據(jù)出行目的確定起始站Q和終點站 Z。

分別求經(jīng)過起始站Q的所有線路集 S（I），以及經(jīng)過終點站Z的所有線路集 T（J）。

經(jīng)過判斷條件S（I）與T（J）是否相等。如果相等，即存在直達(dá)線路，輸出結(jié)果T（J）；如果沒有則進(jìn)行下一步。

求線路S（I）上的站點E（I，U）以及線路 T（J）上的站點F（J，V）。

分別求經(jīng)過E（I，U）的線路集 R（K），和經(jīng)過 F（J，V）的線路集Y（O）。

經(jīng)過判斷條件R（K）=Y（O）是否相等。如果相等，則得出兩次換乘的一條可行路徑 S（I），R（K），T（J），經(jīng)過的中間換乘站點為 E（I，U）和 F（J，V），輸出結(jié)果，結(jié)束運算。

3 查詢系統(tǒng)的實現(xiàn)

本公交查詢系統(tǒng)的功能主要包括：電子地圖繪制和操作、公交線路查詢、公交站點查詢以及公交換乘的查詢等。其公交查詢的頁面如圖2所示。

優(yōu)化枚舉快速算法算法的算法思想核心是，根據(jù)調(diào)查顯示，出行者出行時對于公交線路的選擇時，多數(shù)優(yōu)先考慮是否有直達(dá)車，如果沒有直達(dá)車，則考慮一次換乘的方案，然后考慮中間站的位置，如果沒有一次換乘的方案，則考慮多次換乘。通常情況下搜索得出的換乘次數(shù)要比實際公交換乘次數(shù)多。原因是算法理論搜索得出的是只考慮在原地?fù)Q乘的結(jié)果；而在實際生活中，同一區(qū)域站點設(shè)置有一定的短距離，出行者會通過步行轉(zhuǎn)到換乘點。因此，出現(xiàn)了查詢換乘次數(shù)較多的現(xiàn)象。

換乘查詢模塊，進(jìn)入路徑查詢時，共有兩種選擇，一是直達(dá)，另一個是換乘一次。進(jìn)入界面后先在起點站和終點站輸入框中點擊選擇站點，或者輸入起點站和終點站的名稱，點擊“查詢”按鈕，查詢結(jié)果顯示在下面的列表框中，列表框中結(jié)果包括這兩點之間的所有路線。查詢用戶根據(jù)出行行為傾向選擇其中任一結(jié)果，點擊顯示詳細(xì)信息。若查詢的起終點之間存在直達(dá)線路，則系統(tǒng)優(yōu)先得出直達(dá)的查詢結(jié)果，即顯示出經(jīng)過這兩個站點的所有直達(dá)線路的所有站點及其詳細(xì)路徑。若查詢的起終點之間不存在直達(dá)線路，則系統(tǒng)自動進(jìn)入一次換乘，需要通過輸入中間站點名稱來得出用戶想要經(jīng)過的中間地點。若查詢的起終點之間沒有換乘方案，則系統(tǒng)顯示出沒有查詢結(jié)果，并且提示用戶進(jìn)行二次換乘，繼續(xù)輸入二次換乘的中間站點名稱，或者修改查詢的起終點名稱。

試驗結(jié)果表明，用戶輸入需要查詢的公交線路，系統(tǒng)通過相應(yīng)的線路路段中相應(yīng)的字段或者車次號，獲取該車次所經(jīng)過的所有站點；也可以根據(jù)給出的一個站點，查詢出經(jīng)過該站點的所有公交車，從而為用戶提供更多的公交信息。

4 結(jié)語

該論文在分析和總結(jié)公交站點、公交線路等公交數(shù)據(jù)的特點基礎(chǔ)之上，改進(jìn)了公交換乘的算法，引入了緊鄰站點和站站快表，使算法更符合生活中人們的實際需求和提高了查詢的效率。系統(tǒng)實現(xiàn)多種換乘查詢的方式，不僅能滿足不同乘客的不同需求，在換乘查詢過程中，得出的結(jié)論也更為合理。因此算法具有很強的實用性和通用性，在公交網(wǎng)絡(luò)中可以廣泛采用。

參考文獻(xiàn)

[1] 王建聰，高利平，陳紹寬，等.城市公共交通樞紐換乘組織仿真研究[J].交通運輸系統(tǒng)工程與信息，2006，6（6）：68-69.

[2] 趙巧霞，馬志強，張發(fā).以最小換乘次數(shù)和站數(shù)為目標(biāo)的公交出行算法[J].計算機(jī)應(yīng)用，2004，24（12）：90-92.

[3] 文洪建.小城市公交換乘優(yōu)化算法設(shè)計[J].中國科技信息，2010（13）：11-13.

[4] 胡云峰.公交換乘系統(tǒng)的數(shù)據(jù)庫結(jié)構(gòu)及算法優(yōu)化[J].文山學(xué)院學(xué)報，2010（2）：22-25.endprint

摘 要：該文針對目前我國城市公交查詢系統(tǒng)存在的不足，提出了一種便于乘客進(jìn)行路線選擇的優(yōu)化枚舉算法，并探討了以換乘次數(shù)最少為目標(biāo)的公交查詢方案。對n次公交換乘算法進(jìn)行改進(jìn)，引入緊鄰站點和站站快表，提高公交查詢系統(tǒng)的實用性和查詢效率，從而吸引出行者優(yōu)先選擇公交車出行方式。

關(guān)鍵詞：公交查詢 優(yōu)化枚舉算法 Java Applet 最少換乘

中圖法分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：1674-098X（2014）09（b）-0195-02

隨著我國社會經(jīng)濟(jì)的發(fā)展，人民出行頻率不斷增加，交通問題日益突出，而城市公共交通具有運量大、人均占有道路少等優(yōu)點。城市道路基礎(chǔ)建設(shè)規(guī)模擴(kuò)大的同時，道路的延伸后，隨之滿足人民需要的公交線路也在不斷地增加。為市民提供便捷的查詢系統(tǒng)，為方便地提供給人們出行時選擇最優(yōu)的公交換乘方案。在多種交通出行方式的復(fù)雜情況下，如果通過換乘進(jìn)行協(xié)調(diào)配合，那么將會提高公共交通的利用率，從而有效減少重復(fù)投資建設(shè)的現(xiàn)象。

由于我國在公共交通管理方面還處于較低水平，推行公共交通換乘方面沒有加強，因此，在公交換乘系統(tǒng)的開發(fā)方面，也處于起步階段。然而，隨著信息技術(shù)的快速發(fā)展，公交換乘查詢系統(tǒng)的開發(fā)及推廣也勢在必行。目前，我國公交換乘查詢系統(tǒng)仍存在一些問題[1]。

（1）公交線網(wǎng)管理混亂，沒有建成換乘樞紐。

（2）公交信息查詢系統(tǒng)終端沒有普及。

（3）公交查詢信息單一，不能滿足出行者需求。

（4）查詢信息陳舊，沒有數(shù)據(jù)維護(hù)管理員。

1 公交換乘理論基礎(chǔ)

公交換乘從換乘交通工具的一致性來講，主要分為多方式換乘和普通換乘。多方式換乘是指換乘前后所采用的交通方式不同；而普通換乘則是指換乘前后的交通方式是一樣的。本系統(tǒng)所要設(shè)計的換乘系統(tǒng)主要指的是普通換乘，主要針對公交這種特定的交通方式進(jìn)行設(shè)計。

公共交通線路網(wǎng)的結(jié)構(gòu)可按三種不同的線路網(wǎng)組成，分別是：放射形線路網(wǎng)、主干線和駁運線相結(jié)合的線路網(wǎng)、帶有環(huán)線或切線狀線路的放射形線路網(wǎng)[2-3]。

公交換乘的特性：

（1）換乘的必要性。

（2）換乘的有效性。

（3）換乘的多功能性。

2 優(yōu)化枚舉快速算法研究

基于距離最短的換乘方式，人們考慮更多的是減少換乘次數(shù)，避免換乘頻繁帶來的麻煩。因此，換乘理論中，基于換乘次數(shù)最少的方式，與實際換乘系統(tǒng)的應(yīng)用聯(lián)系更為緊密?；趽Q乘次數(shù)最少的換乘算法的算法思想核心是，根據(jù)調(diào)查顯示[4]，出行者出行時對于公交線路的選擇時，多數(shù)優(yōu)先考慮是否有直達(dá)車，如圖1（a）所示。如果沒有直達(dá)車，則考慮一次換乘的方案，然后考慮中間站的位置，如圖1（b）所示。如果沒有一次換乘的方案，則考慮多次換乘，二次換乘如圖1（c）所示，三次換乘如圖1（d）所示。

基于優(yōu)化枚舉快速算法，通常情況下搜索得出的換乘次數(shù)要比實際公交換乘次數(shù)多。原因是算法理論搜索得出的是只考慮在原地?fù)Q乘的結(jié)果；而在實際生活中，同一區(qū)域站點設(shè)置有一定的短距離，出行者會通過步行轉(zhuǎn)到換乘點。因此，出現(xiàn)了查詢換乘次數(shù)較多的現(xiàn)象。所以，在后續(xù)設(shè)計換乘查詢模塊時，應(yīng)考慮到同一區(qū)域范圍內(nèi)的所有站點情況。

基于優(yōu)化枚舉快速算法的基本思想：如果確定起始站點Q、終點站Z出發(fā)，與數(shù)據(jù)庫中各個線路中的站點相比較，尋找可換乘車站，得出可能的路徑。

設(shè)S（I）（I=1，2，…，m）為經(jīng)過起始站Q 的線路集合。

T（J）（J=1，2，…，p）為線路S（I）上的所有站點的集合。

F（J，V）（V=1，2，…，g）為線路T（J）上的所有站點集合。

R（K）（K=1，2，…，g）為經(jīng)過站點 E（I，U）的線路集合。

Y（O）（O=1，2，…Z）為經(jīng)過 F（J，V）的線路集合。

G（K，W）（W=1，2，…i）為線路 R（K）上的站點集合。

算法的步驟如下：

根據(jù)出行目的確定起始站Q和終點站 Z。

分別求經(jīng)過起始站Q的所有線路集 S（I），以及經(jīng)過終點站Z的所有線路集 T（J）。

經(jīng)過判斷條件S（I）與T（J）是否相等。如果相等，即存在直達(dá)線路，輸出結(jié)果T（J）；如果沒有則進(jìn)行下一步。

求線路S（I）上的站點E（I，U）以及線路 T（J）上的站點F（J，V）。

分別求經(jīng)過E（I，U）的線路集 R（K），和經(jīng)過 F（J，V）的線路集Y（O）。

經(jīng)過判斷條件R（K）=Y（O）是否相等。如果相等，則得出兩次換乘的一條可行路徑 S（I），R（K），T（J），經(jīng)過的中間換乘站點為 E（I，U）和 F（J，V），輸出結(jié)果，結(jié)束運算。

3 查詢系統(tǒng)的實現(xiàn)

本公交查詢系統(tǒng)的功能主要包括：電子地圖繪制和操作、公交線路查詢、公交站點查詢以及公交換乘的查詢等。其公交查詢的頁面如圖2所示。

優(yōu)化枚舉快速算法算法的算法思想核心是，根據(jù)調(diào)查顯示，出行者出行時對于公交線路的選擇時，多數(shù)優(yōu)先考慮是否有直達(dá)車，如果沒有直達(dá)車，則考慮一次換乘的方案，然后考慮中間站的位置，如果沒有一次換乘的方案，則考慮多次換乘。通常情況下搜索得出的換乘次數(shù)要比實際公交換乘次數(shù)多。原因是算法理論搜索得出的是只考慮在原地?fù)Q乘的結(jié)果；而在實際生活中，同一區(qū)域站點設(shè)置有一定的短距離，出行者會通過步行轉(zhuǎn)到換乘點。因此，出現(xiàn)了查詢換乘次數(shù)較多的現(xiàn)象。

換乘查詢模塊，進(jìn)入路徑查詢時，共有兩種選擇，一是直達(dá)，另一個是換乘一次。進(jìn)入界面后先在起點站和終點站輸入框中點擊選擇站點，或者輸入起點站和終點站的名稱，點擊“查詢”按鈕，查詢結(jié)果顯示在下面的列表框中，列表框中結(jié)果包括這兩點之間的所有路線。查詢用戶根據(jù)出行行為傾向選擇其中任一結(jié)果，點擊顯示詳細(xì)信息。若查詢的起終點之間存在直達(dá)線路，則系統(tǒng)優(yōu)先得出直達(dá)的查詢結(jié)果，即顯示出經(jīng)過這兩個站點的所有直達(dá)線路的所有站點及其詳細(xì)路徑。若查詢的起終點之間不存在直達(dá)線路，則系統(tǒng)自動進(jìn)入一次換乘，需要通過輸入中間站點名稱來得出用戶想要經(jīng)過的中間地點。若查詢的起終點之間沒有換乘方案，則系統(tǒng)顯示出沒有查詢結(jié)果，并且提示用戶進(jìn)行二次換乘，繼續(xù)輸入二次換乘的中間站點名稱，或者修改查詢的起終點名稱。

試驗結(jié)果表明，用戶輸入需要查詢的公交線路，系統(tǒng)通過相應(yīng)的線路路段中相應(yīng)的字段或者車次號，獲取該車次所經(jīng)過的所有站點；也可以根據(jù)給出的一個站點，查詢出經(jīng)過該站點的所有公交車，從而為用戶提供更多的公交信息。

4 結(jié)語

該論文在分析和總結(jié)公交站點、公交線路等公交數(shù)據(jù)的特點基礎(chǔ)之上，改進(jìn)了公交換乘的算法，引入了緊鄰站點和站站快表，使算法更符合生活中人們的實際需求和提高了查詢的效率。系統(tǒng)實現(xiàn)多種換乘查詢的方式，不僅能滿足不同乘客的不同需求，在換乘查詢過程中，得出的結(jié)論也更為合理。因此算法具有很強的實用性和通用性，在公交網(wǎng)絡(luò)中可以廣泛采用。

參考文獻(xiàn)

[1] 王建聰，高利平，陳紹寬，等.城市公共交通樞紐換乘組織仿真研究[J].交通運輸系統(tǒng)工程與信息，2006，6（6）：68-69.

[2] 趙巧霞，馬志強，張發(fā).以最小換乘次數(shù)和站數(shù)為目標(biāo)的公交出行算法[J].計算機(jī)應(yīng)用，2004，24（12）：90-92.

[3] 文洪建.小城市公交換乘優(yōu)化算法設(shè)計[J].中國科技信息，2010（13）：11-13.

[4] 胡云峰.公交換乘系統(tǒng)的數(shù)據(jù)庫結(jié)構(gòu)及算法優(yōu)化[J].文山學(xué)院學(xué)報，2010（2）：22-25.endprint