夏 伯 男, 吳 雪 瑩, 姚 春 龍

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

0 引 言

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

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

1 系統(tǒng)模型

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

1.1 公交線路

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

對于任一公交模型E,記S為所有站點(diǎn)的集合,W為相鄰站點(diǎn)i和j的關(guān)系的集合。用站點(diǎn)編號來表示站點(diǎ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}。

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

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

1.2 公交查詢模型

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

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

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

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

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

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

圖2描述了一個(gè)簡單的城市公交帶權(quán)查詢圖?？梢院芮逦乜闯鰪某霭l(fā)的站點(diǎn)1到目的站點(diǎn)12之間經(jīng)過的所有站點(diǎn)和分支。其中,相連的同線弧看作一條乘車路線,換乘弧相連的兩個(gè)站點(diǎn)看作換乘站點(diǎn)。

圖2 公交換乘查詢圖

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

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

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

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

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

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

出發(fā)?。簑1,2,w1,9；

結(jié)束?。簑7,12,w10,12；

換乘?。簑3,6,w6,3,w7,9,w9,7；

同線?。簑1,2,w2,3,w3,4,w5,6,w6,7,w7,12,w8,9,w9,10,w10,11。

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

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

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

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

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

所以,可以求得3條通路的時(shí)間權(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。

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

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

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

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

3 模型實(shí)現(xiàn)

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

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

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

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

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

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

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

圖3 時(shí)間最短查詢

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

圖4 路程最短查詢

4 結(jié)束語

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

[1] 陸忠,錢翔東,張登榮. 基于最短路徑查詢的城市公交網(wǎng)絡(luò)拓?fù)浣Ｑ芯縖J]. 遙感信息, 2002(1):11-14,46.

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

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

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

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

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

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