一種公交網(wǎng)絡(luò)最優(yōu)路徑新算法

摘 要:從出行者的實(shí)際情況出發(fā)，提出步行愿望系數(shù)，綜合考慮最小換乘次數(shù)、最短時間以及最小費(fèi)用等因素，提出了一種公交網(wǎng)絡(luò)最優(yōu)路徑新算法，應(yīng)用于廣州市大學(xué)城內(nèi)公交線路查詢，實(shí)現(xiàn)相應(yīng)的仿真系統(tǒng)。

關(guān)鍵詞:最優(yōu)路徑; 步行愿望系數(shù); 公交線路查詢

中圖分類號:U491 文獻(xiàn)標(biāo)志碼:A

文章編號:1001-3695(2010)03-0907-02

doi:10.3969/j.issn.1001-3695.2010.03.027

Novel optimal route algorithm for public transportation

CAI Nian， CAI Cai-yan

(School of Information Engineering， Guangdong University of Technology， Guangzhou 510006， China)

Abstract:According to the traveler’s desirability， this paper proposed a novel optimal route algorithm for public transportation based on some factors， such as the desire-to-walk coefficient， the smallest transferring number， the least time cost， and the least economic cost. Applied the algorithm to bus route query in the Guangzhou Higher Education Mega Center and also established a simulated system for bus route query.

Key words:optimal route; desire-to-walk coefficient; bus route query

城市公共交通運(yùn)輸以其覆蓋面廣、經(jīng)濟(jì)快捷的特點(diǎn)，目前仍然是絕大多數(shù)出行者的首選方式。同時，高效、合理地使用公共交通系統(tǒng)能夠有效地緩解日益嚴(yán)重的城市道路交通緊張狀況，因此眾多學(xué)者提倡公共交通系統(tǒng)優(yōu)先理念，并得到了各地政府的大力支持。

最優(yōu)路徑方法對評價和優(yōu)化公交網(wǎng)絡(luò)以及公交線路查詢具有非常重要的實(shí)際意義[1~8]。傳統(tǒng)的最優(yōu)路徑問題往往就是最短路徑問題，即只需找出兩點(diǎn)之間路徑距離最短。Dijkstra算法由于其穩(wěn)定性、能適應(yīng)網(wǎng)絡(luò)拓?fù)涞淖兓瑫r占用較少的系統(tǒng)內(nèi)存空間，是一種應(yīng)用最為廣泛的最短路徑算法。可是在公交網(wǎng)絡(luò)中，考慮到乘客出行心理，最短路徑不一定就是最優(yōu)路徑[3]。因此，目前絕大多數(shù)的公交網(wǎng)絡(luò)最優(yōu)路徑算法都考慮了換乘次數(shù)。楊新苗等人[3]提出以換乘次數(shù)最少為首要目標(biāo)、出行距離最短為第二目標(biāo)的給予GIS的最優(yōu)路徑選擇方法。廖楚江等人[4]將圖算法部署到空間網(wǎng)絡(luò)數(shù)據(jù)庫中，結(jié)合最少換乘思想，實(shí)現(xiàn)一種高效穩(wěn)定的公交網(wǎng)絡(luò)最優(yōu)路徑算法。王建林[5]提出在杭州市三次以內(nèi)的轉(zhuǎn)車是合理的，從而提出一種基于三次轉(zhuǎn)車方案的最優(yōu)路徑算法。侯剛等人[6]提出空間數(shù)據(jù)到拓?fù)淠Ｐ驮俚剿阉髂Ｐ偷墓浑p層建模方案，改進(jìn)了傳統(tǒng)的Dijkstra算法，有效地實(shí)現(xiàn)了大連市公交網(wǎng)絡(luò)最優(yōu)路徑的選擇。梁虹等人[7]基于ISO FDF導(dǎo)航數(shù)據(jù)庫，提出一種改進(jìn)的A*算法較好地解決了公交線路的實(shí)時查詢。孫燕等人[8]采用廣義路阻定義，提出了一種基于混沌神經(jīng)網(wǎng)絡(luò)的最優(yōu)路徑選擇算法。在實(shí)際生活中，有時兩個換乘站之間或者換乘站到目的地之間的步行距離不是很遠(yuǎn)，等車時間有時甚至遠(yuǎn)遠(yuǎn)超過步行時間;而且，某些出行者愿意承擔(dān)少許的步行時間代價以換取更少的換乘次數(shù)或更少的乘車費(fèi)用。

1 最優(yōu)路徑算法

1.1 路徑選擇算法

根據(jù)公交線路的實(shí)際情況和大眾心理分析，在廣州市內(nèi)，換乘次數(shù)小于等于兩次是比較合理的[9]。因此，本文不考慮換乘次數(shù)超過兩次的方案，這樣最多只需進(jìn)行三次搜索，從而簡化算法模型，降低程序運(yùn)行時間復(fù)雜度，提高整體查詢效率。

采用啟發(fā)式算法中改進(jìn)策略的思想[10]，即首先從直達(dá)方案出發(fā)，然后對所求某條路徑Ki的質(zhì)量進(jìn)行評價，不滿意則采用啟發(fā)式方法設(shè)計改進(jìn)規(guī)則，增加換乘次數(shù)，逐步改進(jìn)Ki，直至得出滿意的Ki為止。

設(shè)起點(diǎn)為A，終點(diǎn)為B，路徑選擇策略如下:

a)考慮直達(dá)情況。搜索經(jīng)過A的所有路徑，如果在該路徑中出現(xiàn)了B，且A→B為該路線的行駛方向，那么該路徑為其中一個解。采用該方法遍歷所有經(jīng)過A的路徑求解，直到結(jié)束。

b)若步驟a)無解，則考慮一次轉(zhuǎn)乘的情況。搜索經(jīng)過A的所有路徑，同時搜索經(jīng)過B的所有路徑，如果這兩條路徑有交點(diǎn)且不為A或B，那么該交點(diǎn)為轉(zhuǎn)乘站，遍歷所有經(jīng)過A和B的路徑，可求得所有轉(zhuǎn)乘站，即得到所有一次轉(zhuǎn)乘的路徑方案。

c)若步驟b)仍無解，則考慮二次轉(zhuǎn)乘的情況。在一次轉(zhuǎn)乘的基礎(chǔ)上，搜索經(jīng)過A的任意下一站C(即存在A→C的路徑)，然后搜索所有經(jīng)過B的任意前一站D(即存在D→B的路徑)，如果C、D存在直達(dá)路徑且不是重復(fù)站，則存在A→C→D→B的二次轉(zhuǎn)乘路徑，當(dāng)遍歷完所有C點(diǎn)和D點(diǎn)，就能得到所有二次轉(zhuǎn)乘的路徑方案。

d)若步驟c)無解，則認(rèn)為不存在令查詢者較為滿意的公交路徑，可以考慮步行至相鄰車站搭乘公交車等方案。

將以上所得路徑Ki按查詢者要求排序篩選，如時間TAB優(yōu)先、費(fèi)用MAB優(yōu)先、換乘次數(shù)NAB優(yōu)先，或者時間、費(fèi)用、換乘次數(shù)三者的綜合因素，即質(zhì)量因子P=αTAB+βMAB+γNAB等(α+β+γ=1)。取排序靠前的若干路徑方案作為Ki的子集K′i，即為所求最優(yōu)路徑選擇方案。

1.2 步行愿望系數(shù)

當(dāng)采用以上算法查詢結(jié)果為空或不理想時，甚至是出行者愿意承擔(dān)少許的時間代價以換取更少的換乘次數(shù)或更少的乘車費(fèi)用時，可以建議出行者進(jìn)行短距離的步行，即在路徑選擇方案中考慮步行因素。假定知道所有站點(diǎn)之間的步行時間，則當(dāng)兩站點(diǎn)間無相應(yīng)方向可通路徑時，引入步行邊，從而將系統(tǒng)構(gòu)建為一個完全有向連通圖。

設(shè)任意兩站點(diǎn)A、B間的步行時間為aAB，算法所得公交路徑最短時間為tAB，則存在以下兩種情況:

a)若算法可求得兩站點(diǎn)間的可行路徑，但事實(shí)上出現(xiàn)嚴(yán)重繞行現(xiàn)象，則認(rèn)為查詢結(jié)果不理想，可考慮是否選擇步行到達(dá)。

b)若算法求得兩站點(diǎn)間不存在任何路徑時，令tAB為∞，則由A站到達(dá)B站只能選擇步行。

設(shè)查詢者的步行愿望系數(shù)為λ(0≤λ≤1)，乘車愿望系數(shù)為1-λ(影響λ的因素有天氣狀況、經(jīng)濟(jì)狀況、心情及體力等)，則:

a)當(dāng)λ×tAB≥(1-λ)×aAB時，選擇步行;否則λ×tAB<(1-λ)×aAB，選擇乘車。

b)當(dāng)tAB→∞時，對任意給定λ(0<λ≤1)，有λ×tAB>(1-λ)×aAB，選擇步行。

c)當(dāng)λ=0，tAB→∞時，即既不愿意步行，也不存在乘車路線。但一般不會出現(xiàn)該情況，即不會同時出現(xiàn)λ=0且tAB→∞。

由此驗(yàn)證了通過對比λ×tAB與(1-λ)×aAB可確定選擇乘車或步行。令y表示步行方案，則

y=1 當(dāng)λ/aAB≥(1-λ)/tAB0 當(dāng)λ/aAB<(1-λ)/tAB(1)

顯然，當(dāng)y=1時，出行者愿意選擇適當(dāng)?shù)牟叫?當(dāng)y=0時，出行者不愿意選擇步行。λ體現(xiàn)了不同人在不同時間、不同情況下步行的愿望程度。λ的引入使得公交網(wǎng)絡(luò)路徑選擇方案更加人性化，可將該模型運(yùn)用于公交路徑選擇查詢系統(tǒng)。λ的具體數(shù)值可以根據(jù)社會調(diào)查進(jìn)行統(tǒng)計確定或者可以由出行者自己根據(jù)需求進(jìn)行選擇。

2 公交查詢仿真系統(tǒng)

采用Visual Studio 2005作為開發(fā)環(huán)境，SQL Server 2000作為信息數(shù)據(jù)庫管理系統(tǒng)，將所提出的公交網(wǎng)絡(luò)最優(yōu)路徑算法應(yīng)用于廣州市大學(xué)城公交網(wǎng)絡(luò)，構(gòu)建廣州市大學(xué)城公交網(wǎng)絡(luò)查詢仿真系統(tǒng)(圖1)。該仿真系統(tǒng)主要實(shí)現(xiàn)了以下四個功能:

a)地圖顯示。主要包括兩個重要功能:地圖顯示放大縮小功能以及在地圖上對查詢數(shù)據(jù)的顯示輸出，給乘客一種直觀形象的指示。

b)公交線路查詢。系統(tǒng)可以查詢?nèi)我庖粭l廣州市大學(xué)城內(nèi)的公交線路信息，如公交線路經(jīng)過的站點(diǎn)、各站點(diǎn)之間的時間差等，同時在地圖上高亮顯示相關(guān)公交線路經(jīng)過的路線。

c)公交站點(diǎn)查詢。系統(tǒng)可以查詢公交站點(diǎn)的相關(guān)詳細(xì)信息，如在地圖顯示所在的位置、經(jīng)過該站點(diǎn)的公交線路等。

d)公交換乘查詢。系統(tǒng)可以查詢廣州市大學(xué)城內(nèi)任意兩個地點(diǎn)的公交換乘方案。如果兩個地點(diǎn)經(jīng)過兩次以下的換乘即可到達(dá)，那么就直接給出公交線路及其換乘查詢結(jié)果;如果兩個地點(diǎn)需要兩次以上換乘才可達(dá)到或者行人綜合考慮一些其他因素(如票價、時間、換乘次數(shù)等)，那么就考慮步行愿望系數(shù)，根據(jù)質(zhì)量因子P依次排列給行人選擇，同時顯示相關(guān)信息(如步行距離、時間、票價、時間等)。

為了測試算法的準(zhǔn)確率，選擇兩個地圖數(shù)據(jù)中有的地點(diǎn)進(jìn)行查詢，查詢從“華南理工大學(xué)體育館”到“北亭村南面”的最優(yōu)路徑。系統(tǒng)給出查詢提示(圖2)，明確指示行人需要步行才能到達(dá)附近的公交站點(diǎn)，同時給出相應(yīng)的公交線路選擇。

3 結(jié)束語

最優(yōu)路徑選擇問題是公交查詢系統(tǒng)中的一個關(guān)鍵問題。傳統(tǒng)最優(yōu)路徑選擇算法較少考慮到步行因素，在考慮實(shí)際生活中某些出行者愿意承擔(dān)少許的步行時間代價以換取更少的換乘次數(shù)或更少的乘車費(fèi)，本文提出步行愿望系數(shù)，綜合考慮最小換乘次數(shù)、最短時間以及最小費(fèi)用等因素，提出了一種公交網(wǎng)絡(luò)最優(yōu)路徑新算法，有效地完成廣州市大學(xué)城內(nèi)兩個地點(diǎn)之間的最優(yōu)路徑選擇問題，并提示路徑的相關(guān)信息。因此，本文提出的公交網(wǎng)絡(luò)最優(yōu)路徑算法將對現(xiàn)代公交網(wǎng)絡(luò)查詢系統(tǒng)具有非常重要的意義。

參考文獻(xiàn):

[1]ZHANG F B， NOON C E. Shortest path algorithms: an evaluation using real road networks[J]. Transportation Science， 1998，32(1):65-73.

[2]WU Qiu-jin， HARTLEY J. Using k-shortest paths algorithms to accommodate user preferences in the optimization of public transport travel[C]//Proc of the 8th International Conference on Applications of Advanced Technologies in Transportation Engineering. 2004:181-186.

[3]楊新苗， 王煒， 馬文騰. 基于GIS的公交乘客出行路徑選擇模型[J]. 東南大學(xué)學(xué)報:自然科學(xué)版，2000，30(6):87-91.

[4]廖楚江， 蔡忠亮， 杜清運(yùn)，等. 基于最少換乘的公交最優(yōu)路徑算法的設(shè)計與實(shí)現(xiàn)[J]. 武漢大學(xué)學(xué)報:信息科學(xué)版，2006， 31(10):904-907.

[5]王建林. 基于換乘次數(shù)最少的城市公交網(wǎng)絡(luò)最優(yōu)路徑算法[J]. 經(jīng)濟(jì)地理， 2005，25(5):673-676.

[6]侯剛， 周寬久. 基于換乘次數(shù)最少的公交網(wǎng)絡(luò)最優(yōu)路徑模型研究[J]. 計算機(jī)技術(shù)與發(fā)展， 2008，18(1):44-47.

[7]梁虹， 袁小群， 劉蕊. 一種新的公交數(shù)據(jù)模型與公交查詢系統(tǒng)實(shí)現(xiàn)[J]. 計算機(jī)工程與應(yīng)用， 2007，43(3): 234-238.

[8]孫燕， 孫錚. 基于混沌神經(jīng)網(wǎng)絡(luò)的最優(yōu)路徑選擇算法[J]. 公路交通科技， 2008，25(4):117-121.

[9]陳簫楓， 蔡秀云， 唐德強(qiáng). 最短路徑算法分析及其在公交查詢的應(yīng)用[J]. 工程圖學(xué)學(xué)報， 2001(3):20-24.

[10]胡運(yùn)權(quán). 運(yùn)籌學(xué)教程[M]. 北京: 清華大學(xué)出版社， 2003.