城市公交換乘查詢系統的優化枚舉算法研究與應用

徐熾

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

關鍵詞：公交查詢 優化枚舉算法 Java Applet 最少換乘

中圖法分類號：TP391 文獻標識碼：A 文章編號：1674-098X（2014）09（b）-0195-02

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

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

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

（2）公交信息查詢系統終端沒有普及。

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

（4）查詢信息陳舊，沒有數據維護管理員。

1 公交換乘理論基礎

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

公共交通線路網的結構可按三種不同的線路網組成，分別是：放射形線路網、主干線和駁運線相結合的線路網、帶有環線或切線狀線路的放射形線路網[2-3]。

公交換乘的特性：

（1）換乘的必要性。

（2）換乘的有效性。

（3）換乘的多功能性。

2 優化枚舉快速算法研究

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

基于優化枚舉快速算法，通常情況下搜索得出的換乘次數要比實際公交換乘次數多。原因是算法理論搜索得出的是只考慮在原地換乘的結果；而在實際生活中，同一區域站點設置有一定的短距離，出行者會通過步行轉到換乘點。因此，出現了查詢換乘次數較多的現象。所以，在后續設計換乘查詢模塊時，應考慮到同一區域范圍內的所有站點情況。

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

設S（I）（I=1，2，…，m）為經過起始站Q 的線路集合。

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

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

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

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

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

算法的步驟如下：

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

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

經過判斷條件S（I）與T（J）是否相等。如果相等，即存在直達線路，輸出結果T（J）；如果沒有則進行下一步。

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

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

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

3 查詢系統的實現

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

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

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

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

4 結語

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

參考文獻

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

[2] 趙巧霞，馬志強，張發.以最小換乘次數和站數為目標的公交出行算法[J].計算機應用，2004，24（12）：90-92.

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

[4] 胡云峰.公交換乘系統的數據庫結構及算法優化[J].文山學院學報，2010（2）：22-25.endprint

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

關鍵詞：公交查詢 優化枚舉算法 Java Applet 最少換乘

中圖法分類號：TP391 文獻標識碼：A 文章編號：1674-098X（2014）09（b）-0195-02

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

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

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

（2）公交信息查詢系統終端沒有普及。

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

（4）查詢信息陳舊，沒有數據維護管理員。

1 公交換乘理論基礎

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

公共交通線路網的結構可按三種不同的線路網組成，分別是：放射形線路網、主干線和駁運線相結合的線路網、帶有環線或切線狀線路的放射形線路網[2-3]。

公交換乘的特性：

（1）換乘的必要性。

（2）換乘的有效性。

（3）換乘的多功能性。

2 優化枚舉快速算法研究

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

基于優化枚舉快速算法，通常情況下搜索得出的換乘次數要比實際公交換乘次數多。原因是算法理論搜索得出的是只考慮在原地換乘的結果；而在實際生活中，同一區域站點設置有一定的短距離，出行者會通過步行轉到換乘點。因此，出現了查詢換乘次數較多的現象。所以，在后續設計換乘查詢模塊時，應考慮到同一區域范圍內的所有站點情況。

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

設S（I）（I=1，2，…，m）為經過起始站Q 的線路集合。

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

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

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

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

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

算法的步驟如下：

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

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

經過判斷條件S（I）與T（J）是否相等。如果相等，即存在直達線路，輸出結果T（J）；如果沒有則進行下一步。

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

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

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

3 查詢系統的實現

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

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

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

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

4 結語

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

參考文獻

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

[2] 趙巧霞，馬志強，張發.以最小換乘次數和站數為目標的公交出行算法[J].計算機應用，2004，24（12）：90-92.

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

[4] 胡云峰.公交換乘系統的數據庫結構及算法優化[J].文山學院學報，2010（2）：22-25.endprint

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

關鍵詞：公交查詢 優化枚舉算法 Java Applet 最少換乘

中圖法分類號：TP391 文獻標識碼：A 文章編號：1674-098X（2014）09（b）-0195-02

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

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

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

（2）公交信息查詢系統終端沒有普及。

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

（4）查詢信息陳舊，沒有數據維護管理員。

1 公交換乘理論基礎

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

公共交通線路網的結構可按三種不同的線路網組成，分別是：放射形線路網、主干線和駁運線相結合的線路網、帶有環線或切線狀線路的放射形線路網[2-3]。

公交換乘的特性：

（1）換乘的必要性。

（2）換乘的有效性。

（3）換乘的多功能性。

2 優化枚舉快速算法研究

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

基于優化枚舉快速算法，通常情況下搜索得出的換乘次數要比實際公交換乘次數多。原因是算法理論搜索得出的是只考慮在原地換乘的結果；而在實際生活中，同一區域站點設置有一定的短距離，出行者會通過步行轉到換乘點。因此，出現了查詢換乘次數較多的現象。所以，在后續設計換乘查詢模塊時，應考慮到同一區域范圍內的所有站點情況。

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

設S（I）（I=1，2，…，m）為經過起始站Q 的線路集合。

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

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

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

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

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

算法的步驟如下：

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

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

經過判斷條件S（I）與T（J）是否相等。如果相等，即存在直達線路，輸出結果T（J）；如果沒有則進行下一步。

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

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

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

3 查詢系統的實現

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

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

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

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

4 結語

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

參考文獻

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

[2] 趙巧霞，馬志強，張發.以最小換乘次數和站數為目標的公交出行算法[J].計算機應用，2004，24（12）：90-92.

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

[4] 胡云峰.公交換乘系統的數據庫結構及算法優化[J].文山學院學報，2010（2）：22-25.endprint