徐熾

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

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

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

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

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

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

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

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

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

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

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

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

公交換乘的特性：

（1）換乘的必要性。

（2）換乘的有效性。

（3）換乘的多功能性。

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

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

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

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

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

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

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

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

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

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

算法的步驟如下：

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

公交換乘的特性：

（1）換乘的必要性。

（2）換乘的有效性。

（3）換乘的多功能性。

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

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

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

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

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

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

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

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

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

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

算法的步驟如下：

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

公交換乘的特性：

（1）換乘的必要性。

（2）換乘的有效性。

（3）換乘的多功能性。

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

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

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

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

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

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

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

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

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

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

算法的步驟如下：

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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