基于最短時間的公交乘車路徑查詢模型

夏 伯 男, 吳 雪 瑩, 姚 春 龍

( 大連工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院, 遼寧 大連 116034 )

0 引 言

一個公交查詢系統(tǒng)的核心問題就是解決出行者的出行路線問題,通過出行者提供的起始點和目的地,從換乘次數(shù)、距離、時間等多個方面分析途徑的站點,最后給出符合出行者要求的最佳路線。據(jù)在北京市做的一個公交乘客出行心理調(diào)查統(tǒng)計結(jié)果,在換乘次數(shù)、出行距離、出行耗時3個因素中,有56.8 %的乘客在選擇出行路徑時首先考慮的是換乘最少,其次考慮時間最短。因此,目前提出的公交查詢模型和算法通常將換乘次數(shù)作為首要因素。首要考慮換乘次數(shù)的乘車路徑算法已經(jīng)有很多,比如最小換乘算法[1]及其改進算法[2]、分層規(guī)劃算法[3]、螞蟻算法[4]等。最小換乘算法基本思想是：先判斷是否有直達線路,如果沒有再判斷是否有1次換乘到達路線,如果沒有再繼續(xù)增大換乘次數(shù)繼續(xù)判斷直至存在到達路線[5]。在上述情況中如果存在不止一種的選擇方案,則再考慮乘車距離,選擇路程最短的乘車方案[6-7]。

上述算法各自有各自的優(yōu)點,但缺陷也很明顯。如當(dāng)考慮時間權(quán)值時,這些算法沒有考慮到換乘時換站點所花費的時間和在站點等待的時間,這樣算出的時間最短路徑不一定是最快的路線。本研究討論的模型把換乘和等待的時間都以特定的方式賦予不同權(quán)值后參與到時間權(quán)值小的路徑查詢中,這樣得出的路徑更直觀、具體、準確。

1 系統(tǒng)模型

系統(tǒng)是基于一種帶權(quán)有向圖的公交查詢系統(tǒng)。當(dāng)人們查詢的是一個城市內(nèi)部公交路線的時候,用帶權(quán)有向圖給出符合用戶要求的最佳路徑及推薦路徑。

1.1 公交線路

城市內(nèi)部錯綜復(fù)雜的公交線路組合在一起形成了一個完善的城市公交網(wǎng),而每條公交線路都包括了數(shù)個公交站點,排除起始站和終點站,每個站點都有自己的前續(xù)站點和后續(xù)站點,根據(jù)這個特點去描述公交線路的結(jié)構(gòu)。

對于任一公交模型E,記S為所有站點的集合,W為相鄰站點i和j的關(guān)系的集合。用站點編號來表示站點：

下行方向：1—2—3—4—5—6,

上行方向：6—7—4—3—2—1,

則有：

S={S1,S2,S3,S4,S5,S6,S7},

W={w1,2,w2,3,w3,4,w4,5,w5,6,w6,7,w7,4,w4,3,w3,2,w2,1}。

實際上,線路模型E與圖1所示的有向圖相對應(yīng)。從圖中可以明顯看到,線路的上行和下行方向所經(jīng)過的站點不完全相同。

圖1 線路E對應(yīng)的有向圖

1.2 公交查詢模型

公交查詢模型,就是根據(jù)出行者給出的起始站點、目的站點和出行者選擇的優(yōu)先條件選出最優(yōu)乘車路線。出行者不同,考慮的優(yōu)先條件往往不盡相同,因此,公交查詢模型的設(shè)計要充分考慮到這些需求。下面給出一種通過查詢圖來定義一個乘車方案的查詢模型。

設(shè)E是一個這種新的公交網(wǎng)絡(luò)中所有公交線路的集合。對于指定的出發(fā)站點Si和目的站點Sj,有i和j的查詢圖,記作Eij,它是一個有向帶權(quán)圖。其中：

(1)設(shè)頂點集合為S={v|v=(s,l),它是一個二元組,滿足對于任意線路l∈E且站點s∈S}∪{Sa,Sb}。Sa和Sb分別為出發(fā)頂點和目的頂點,用于表示出發(fā)站點和目的站點這兩個特殊頂點。在本模型中,出發(fā)站點和目的站點的時間權(quán)值設(shè)為0。

(2)設(shè)弧的集合為W={WN,WM,WL,WS}。WL,WS分別是同線弧、換乘弧的集合。

WN={〈u,v〉|〈u,v〉是出發(fā)弧。即u,v∈S；u為始發(fā)站}；

WM={〈u,v〉|〈u,v〉是結(jié)束弧。即u,v∈S；u為終點站}；

WL={〈u,v〉|〈u,v〉是同線弧。即u,v∈S；u,v為相鄰站點且u≠v}；

WS={〈u,v〉|〈u,v〉是換乘弧。即u,v∈S；u,v為相同站點且u≠v}。

由此可見,查詢圖中有四類弧：出發(fā)弧、結(jié)束弧、同線弧、換乘弧。同線弧是連接同一線路上站點相鄰的頂點間弧,換乘弧為連接線路不同但站點相同(出發(fā)和目的站點除外)的頂點的弧,這些頂點實際上描述了換乘站信息。

圖2描述了一個簡單的城市公交帶權(quán)查詢圖。可以很清晰地看出從出發(fā)的站點1到目的站點12之間經(jīng)過的所有站點和分支。其中,相連的同線弧看作一條乘車路線,換乘弧相連的兩個站點看作換乘站點。

圖2 公交換乘查詢圖

2 查詢圖的權(quán)值設(shè)定策略

大部分用戶在選擇乘坐公交路線的時候,都以換乘次數(shù)最少或者路徑最短和時間最短等為最優(yōu)選擇條件。在此基礎(chǔ)上再考慮乘車舒適度等其他因素。這些在各大中城市中是很常見的乘車需求,這就需要公交查詢系統(tǒng)能夠提供不同的優(yōu)先條件選擇,如路程最短、時間最短、換乘最少等。以時間最短為優(yōu)先條件,通過查詢圖的權(quán)值設(shè)定策略來實現(xiàn)上述三級優(yōu)先查詢的目標(biāo)。以圖2為例：

wij記做換乘弧和同線弧,如果wij為出發(fā)弧或結(jié)束弧時,wij=0。

wij為換乘弧,則查詢路徑經(jīng)過wij時,需要考慮兩部分的時間權(quán)值,一部分是,如果兩路公交車的換乘站在不同位置,要考慮兩站之間的步行時間的權(quán)值,記作cij；另一部分是到達目的站點后,在站臺等待公交車的時間作為權(quán)值,記作dij；則在公式中wij=cij+dij。在公交換乘地鐵的站點,由于地鐵站上下行需要經(jīng)過樓梯,所以cij≠0；但是,公交站換乘站點在相同情況下,cij可能為0。站臺等待時間dij為到達站點后,到上車時間的等待時間權(quán)值,由于是隨機情況,可能的權(quán)值在0至發(fā)車間隔的時間,為了方便計算,一般把等待時間權(quán)值估算為發(fā)車時間的1/2,但是在不同時間段,公交車的發(fā)車間隔可能不同。

wij為同線弧,同線弧是某條公交線路經(jīng)過2個站點之間所花費的時間。如圖2所示,一條公交線路經(jīng)過5,6,7,12四個站點,則該公交線路的同線弧時間權(quán)值分別為w5,6,w6,7,w7,12。在實際過程中,需要測量在不塞車狀態(tài)下,公交車經(jīng)過站點的時間作為同線弧的時間權(quán)值。為了計算方便,一般可以使用全程運行時間/(站點數(shù)目-1)的結(jié)果,估算出同線弧的時間權(quán)值。

如圖2所示,公交系統(tǒng)包含3條公交線路。經(jīng)過的站點分別為{1,2,3,4},{5,6,7,12},{8,9,10,11}。

出發(fā)弧：w1,2,w1,9；

結(jié)束弧：w7,12,w10,12；

換乘弧：w3,6,w6,3,w7,9,w9,7；

同線弧：w1,2,w2,3,w3,4,w5,6,w6,7,w7,12,w8,9,w9,10,w10,11。

通過上面的集合可以得出公交系統(tǒng)E起于節(jié)點1結(jié)束于終點12的通路是：

P1={1,2,3,6,7,12}；

P2={1,9,7,12}；

P3={1,9,10,12}。

(1)記通路的時間權(quán)值為Qi,以P1為例,Q1=w1,2+w2,3+w3,6+w6,7+w7,12,其中w1,2是出發(fā)弧,w7,12是結(jié)束弧；w3,6是換乘弧。

所以,可以求得3條通路的時間權(quán)值分別為

Q1=w1,2+w2,3+w3,6+w6,7+w7,12；

Q2=w1,9+w9,7+w7,12；

Q3=w1,9+w9,10+w10,12。

一條通路的時間權(quán)值之和越少,代表這條通路花費的時間越短。因此,Qmin就是需要的那條通路,即最優(yōu)解。

(2)實際中,對于一個復(fù)雜的城市公交系統(tǒng),如果查詢所有情況,會使得到結(jié)果的時間過長,而且大部分是無用的。如果查詢到了一條線路,在沒有到達終點之前,時間的權(quán)值已經(jīng)大于已經(jīng)獲得結(jié)果的線路,那么這條查詢路徑就舍掉。使用算法實現(xiàn)時,當(dāng)有多條線路同時能夠到達某一目標(biāo)點,則只保留時間權(quán)值最小的路徑,這樣在有N個站點的城市公交系統(tǒng)中,程序中保留的站點最多不超過N-2個。

(3)當(dāng)Qmin有多個解的時候(包括中間的站點),要舍掉部分多余的結(jié)果。本系統(tǒng)在基于時間權(quán)值相同的情況下考慮換乘最少,然后考慮公交線路的始點站。

求解出的最優(yōu)解Qmin滿足路程時間權(quán)值最短、最少換乘、優(yōu)先始發(fā)站的三級優(yōu)先查詢要求的查詢。在實際應(yīng)用中,由于城市的不同,導(dǎo)致站點和公交線路的復(fù)雜程度區(qū)別很大。在效率要求較高的系統(tǒng)中,如果到達某一站點的時間權(quán)值相同時有多個解,酌情減少在中間站點中保存的線路數(shù)目,能夠顯著提高搜索效率。

3 模型實現(xiàn)

為了驗證和測試提出的模型,以大連市內(nèi)的公交網(wǎng)為背景,用C#語言實現(xiàn)了一個簡單的城市公交查詢系統(tǒng)。大連有部分公交線路的上行和下行方向所經(jīng)過的站點不相同,不同車型還有其自身的線路,例如：快速公交、有軌電車、輕軌等。各種公交線路共計140多條,形成了由市區(qū)線路、旅游觀光線路、支線公交、郊區(qū)線路構(gòu)成的城市公交主干體系。

首先取得公交線路的同線弧長度W,假設(shè)該公交線路駛完全程的時間為D,公交站點個數(shù)為a,則該線路的同線弧時間權(quán)值為W=D/(a-1)。

換乘弧的時間權(quán)值記作WS,包括兩部分時間：兩站之間的步行時間的權(quán)值C和在站臺等待公交車的時間D。C的時間權(quán)值需要GIS數(shù)據(jù)采集。為了敘述簡便,將需要走路換乘的站點的C設(shè)置為TC,站臺等待時間假設(shè)為公交發(fā)車頻率的1/2,將公交車的發(fā)車頻率記為TD。要注意一點就是不同時間區(qū)間,同一班公交車的發(fā)車頻率可能不同。y站點的換乘弧WS=TC+TD/2。

為了說明方便,將始發(fā)站和終點站的換乘弧權(quán)值WN,WM設(shè)置為0。

在實現(xiàn)中,以從[西南路]到[興工街]的線路查詢?yōu)槔?敘述時間查詢最短模型實現(xiàn)方法。如圖3所示,在最佳乘車方案中,公交線路經(jīng)過7個車站。從始點到終點依次為：[西南路]-[凈水廠]-[臺山村]-[南沙街]-[漢陽街]-[解放廣場]-[興工街],程序中使用的是螞蟻拓撲算法計算時間權(quán)值的方法。

在始點[西南路]站,始點站W(wǎng)N=0,經(jīng)過該站的公交車有32路和32路加車,與該站點相連的同線弧站點分別為：[凈水廠][西南橋],通過公式W=D/(a-1)得到WL=5。在查詢站點結(jié)果列表中,保存這2個站點的時間權(quán)值和路徑信息,然后以權(quán)值最小的站點開始,遍歷站點。先遍歷列表中的[凈水廠]站點,經(jīng)過[凈水廠]站點的公交車有10路、32路和32路加車。在換乘站點,10路與32路車在同一位置,記C=0,10路公交車發(fā)車間隔為6 min,由公式得出D=3。

[西南路]遍歷到[解放廣場]站,此時從[解放廣場]遍歷到周圍站點時,要到達[興工街]站,需要換乘。在[解放廣場]換乘時,需要加上換乘弧的權(quán)值,202路站點和32路站點在不同位置,設(shè)202路的步行時間權(quán)值C=5,等待時間權(quán)值為D=3,則WL=C+D=8。

圖3 時間最短查詢

如圖4所示,由于優(yōu)先條件為路程最短,那么求最優(yōu)解的過程就基本和以時間權(quán)值為優(yōu)先條件的求解過程相同。不同的是需要求出每條線路在通路中的經(jīng)過多少同線弧的數(shù)量和各自路程權(quán)值的乘積而不是時間權(quán)值,另外不同的是路程最短需要考慮換乘時從一個線路的A站,走到另一個線路的A站的路程,而不考慮時間,等待時間也不考慮。

圖4 路程最短查詢

4 結(jié)束語

分析了公交查詢模型的最優(yōu)算法,在比較現(xiàn)有算法研究的基礎(chǔ)上,提出了一種基于時間最短的層次搜索查詢算法。雖然理論研究和算法實現(xiàn)取得了一些研究成果,但是在具體的過程中存在一些不足,有幾個問題要進一步改進和研究：第一,沒有考慮到公交線路上,不同時間的路況的情況,比如在上下班高峰期,公交車的行車速度會減慢,這樣就會導(dǎo)致時間權(quán)值的增加,但地鐵、快速公交等線路,不受此影響。第二,在獲得換乘線路等待時間的權(quán)值時,是以發(fā)車間隔的1/2作為權(quán)值計算的,這只是一個估算,不能精確地得到等待時間的權(quán)值。

[1] 陸忠,錢翔東,張登榮. 基于最短路徑查詢的城市公交網(wǎng)絡(luò)拓撲建模研究[J]. 遙感信息, 2002(1):11-14,46.

[2] 王玉琨,吳鋒. 嵌入式GIS最短路徑分析中Dijkstra算法的改進[J]. 計算機工程與應(yīng)用, 2008, 44(28):128-129.

[3] 陳洪仁,馮樹民. 分層限制的公交線網(wǎng)優(yōu)化模型[J]. 哈爾濱建筑大學(xué)學(xué)報, 2001, 34(5):113-115.

[4] 高為民. 基于螞蟻算法的公交網(wǎng)絡(luò)最短路徑問題研究[J]. 交通與計算機, 2007, 25(1):94-95,105.

[5] 傅冬綿. 交通系統(tǒng)中最少換乘算法及其實現(xiàn)[J]. 華僑大學(xué)學(xué)報:自然科學(xué)版, 2001, 22(4):348-350.

[6] 翁敏,毋河海,杜清運,等. 基于公交網(wǎng)絡(luò)模型的最優(yōu)出行路徑選擇的研究[J]. 武漢大學(xué)學(xué)報:信息科學(xué)版, 2004, 29(6):500-503.

[7] 蘇瑩,王英杰,余卓淵. 一種建立公交網(wǎng)絡(luò)的最短路徑改進算法[J]. 地球信息科學(xué), 2005, 7(2):99-104.