摘要：人們在出行前常會規(guī)劃出行線路，將距離、時間及線路等作為主要的考慮因素，其路徑檢索模型是一種集距離、目標(biāo)和交通模式為一體的復(fù)雜檢索模型。該文基于有向網(wǎng)構(gòu)建一種新的檢索模型，該模型不僅能通過加權(quán)策略來滿足出行者多目標(biāo)檢索的需求，且能通過改變速度來實(shí)現(xiàn)多種交通工具的換乘。最后，以真實(shí)數(shù)據(jù)建模驗(yàn)證了該模型的有效性和實(shí)用性。

關(guān)鍵詞：公共交通；有向網(wǎng)；最短路徑檢索

中圖分類號：TP18 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）05-1010-04

Optimal bus Route Retrieval Model Based on Weighted Strategy

HU Ying-chun

（Computer and Information Science， Southwest University， Chongqing 400715， China）

Abstract： People will look for travelling routes before travelling， taking distance 、time and lines into consideration. It is a complex model which concludes trip distance、goals and traffic mode. The paper has built a new search model based on the directed network， which not only has a good ability to satisfy the demands of multi-criteria for travelers through assignment strategy， but also come true transportation transfer by setting vehicle speed. Lastly it verifies the effectiveness and practicality based on the example of Hangzhou traffic data.

Key words： public transport； directed network； shortest path route retrieval

1 概述

隨著公共交通運(yùn)輸?shù)牟粩喟l(fā)展，人們的出行由省內(nèi)逐漸擴(kuò)展到省外甚至是國外，可供使用的交通工具有公交車以及軌道交通等。同時道路交通也由過去的單一雙行模式轉(zhuǎn)變?yōu)楝F(xiàn)在的單行、多行、環(huán)行等形式。這種道路交通有可能給乘客帶來一些麻煩，比如在時間開銷上，乘車?yán)@行高于步行。因此，如何利用計(jì)算機(jī)檢索技術(shù)合理、快速的為出行者提供乘車信息以及最優(yōu)的出行方案已成為重要的研究課題。

目前，王波等人[1]以無權(quán)網(wǎng)絡(luò)得到最少換乘方案，之后在此基礎(chǔ)上提出了復(fù)雜帶權(quán)網(wǎng)絡(luò)建模的方案。閆小勇等人[2]針對普通帶權(quán)值有向圖難以處理頂點(diǎn)帶權(quán)值問題，提出了二部圖模型。姚春龍等人[3]針對這類問題在有向網(wǎng)的基礎(chǔ)上，先后提出了基于賦權(quán)策略的三級和四級目標(biāo)檢索的新型有向賦權(quán)圖模型。但隨著出行方式不斷增多，這些模型已不能滿足出行者多種交通工具換乘的需求。

針對上述問題，該文結(jié)合出行者遠(yuǎn)距離、多目標(biāo)和多交通模式的需求，構(gòu)建一種動態(tài)有向網(wǎng)模型。該模型不僅能基于靈活的加權(quán)策略利用[Dijkstra]算法滿足人們個性化出行的需要，還能設(shè)定不同車速，動態(tài)調(diào)整權(quán)值，從而實(shí)現(xiàn)多種交通工具之間的換乘。

2 相關(guān)術(shù)語

2.1基本概念

2.1.1公交站點(diǎn)

公交站點(diǎn)是供公共交通車輛?？亢统鲂姓呱舷萝嚨恼军c(diǎn)。為了便于描述，將任意公交站點(diǎn)[S（station）]抽象為一個五元組：

[S=（id，name，x，y，vehicleType）]

其中，[id]為唯一標(biāo)識一個站點(diǎn)的編號，[name]為站點(diǎn)名稱，x和y分別表示站點(diǎn)所在位置的經(jīng)度和緯度，[vehicleType]表示站點(diǎn)允許?？抗步煌üぞ叩念愋?。

2.1.2公交線路

公交線路是由任意一輛公共交通車在運(yùn)行方向上經(jīng)過的公交站點(diǎn)有序序列構(gòu)成的。公交線路分為無向線路、雙向線路和環(huán)形線路，如圖1所示。

圖1 線路圖

2.1.3公交線路建模

用公共交通車所經(jīng)過所有的站點(diǎn)集合和站點(diǎn)間的后繼關(guān)系構(gòu)建公交線路模型。對于任意一條公共線路，記[Station（l）]為線路[l（line）]途徑的站點(diǎn)集合，[si]表示第i個線路站點(diǎn)，n為線路l的?？靠偞螖?shù)，起始站?？看涡?yàn)?。因?yàn)榇嬖谕粋€站點(diǎn)車輛?？慷啻蔚那闆r，所以站點(diǎn)個數(shù)不大于車輛停靠次數(shù)，即：[i≤j]。

[Sequence（l）={si|si∈Station（l），i=1，2，3，…，n}]

記[Next（l）]為非環(huán)線線路l的第j次?？康恼军c(diǎn)[si]和第[j+1]次?？康恼军c(diǎn)[si+1]構(gòu)成的有序數(shù)對。

[Next（l）={，|（si，j），（si+1，j+1）∈Station（l），i=1，2，…，n，j=1，2，…，m}]

[NextCycle（l）]代表環(huán)線線路[l（cycleline）]當(dāng)前站點(diǎn)及其后繼站點(diǎn)的集合，在非環(huán)線線路的基礎(chǔ)上，將終點(diǎn)站點(diǎn)的后繼設(shè)置為始發(fā)站點(diǎn)。

[NextCycle（l）=Next（l）?{，|（sn，n），（s1，1）∈Sequence（l）}]

[Successor（l）]為線路l每一個當(dāng)前結(jié)點(diǎn)和它的后繼結(jié)點(diǎn)關(guān)系的集合。則[Successor（l）]定義為：

[Successor（l）=Next（l），l?cycle lineNextCycle（l），l∈cycle line]

如圖2，用有向圖來描述公共交通線路，以杭州16路公共汽車線路為例，用站點(diǎn)編號表示站點(diǎn)：

圖2 杭州16路公交線路有向圖

上行：[s001-s002-s003-s004-s005-s006-s007-s008-s009]

下行s：[s009-s008-s007-s006-s005-s004-s003-s002-s001]

則有：

[Station（l）={s001，s002，s003，s004，s005，s006，s007，s008，s009，s010}]

[Successor（l）={<（s001，01），（s002，02）>，<（s002，02），（s003，03）>，<（s003，03），（s004，04）>， <（s004，04），（s005，05）>，<（s005，05），（s006，06）>，<（s006，06），（s007，07）>， <（s007，07），（s008，08）>，<（s008，08），（s009，09）>，<（s009，09），（s008，10）>， <（s008，10），（s007，11）>，<（s007，11），（s006，12）>，<（s006，12），（s005，13）>， <（s005，13），（s010，14）>，<（s010，14），（s002，15）>，<（s002，15），（s001，01）>}]

2.2乘車檢索方案模型

乘車檢索方案是指根據(jù)出行者指定的起點(diǎn)和終點(diǎn)，為出行者提供滿足其需求的最優(yōu)乘車方案。出行者的起止點(diǎn)多數(shù)情況下并不是公交站點(diǎn)，因此，用它們的經(jīng)、緯度值的有序數(shù)對描述位置信息，對點(diǎn)[P（point）]，[P.x]和[P.y]分別表示它的經(jīng)度值和緯度值。

定義1 令L為公共交通線路的集合，對于給定起點(diǎn)[S（start）]和終點(diǎn)[E（end）]，關(guān)于S和E的檢索圖[（searchinggraph）]，記為：[SG（S，E，L）]。其中：

1） 頂點(diǎn)集合[（Vertex）V=VN?VP]。其中，[VP={S，E}]代表出行者的起點(diǎn)和終點(diǎn)；[VN=vv=1，si]，其中[（1，si）]是一個二元組，滿足：線路[l∈L]且[si∈Sequences（l）]。[?v∈VN]，[v.station]、[v.line]和[v.sequence]分別表示p對應(yīng)的站點(diǎn)、線路和?？看涡?。[?uv∈V]，[dist（u，v）]表示頂點(diǎn)u和頂點(diǎn)v間的距離；[?v∈VN]，[dist（S，v）]≤可接受最大步行距離（The Acceptable Longest Walking Distance 簡記為 ALWD）[4]則v為出發(fā)乘車頂點(diǎn)，將所有從起點(diǎn)能步行到達(dá)的頂點(diǎn)集合記作[startVertex（S）]，[startVertex（S）={v|v∈V，dist（S，v）≤ALMD}]； [?u∈VN]，[dist（u，E）≤ALMD]，則u為到站下車頂點(diǎn)，將步行到達(dá)終點(diǎn)的頂點(diǎn)集合記作[endVertex（S）]，[endVertex（E）={u|u∈V，dist（u，E）≤ALMD}]。

2） 弧的集合[E=EL?ES?ET?EE]，其中，[EL]、[ES]、[ET]和[EE]別代表同線弧、出發(fā)弧、換乘弧和到達(dá)弧的集合。它們的定義分別記作：

[ EL={|u，v∈VN，u.line=v.line?（u.station，u.sequence），（v.station，v.sequence）∈Succeessor（u.line）}]

[ES={|v∈startVertex（S）?v=E?dist（S，E）≤ALMD}]

[ ET={|u，v∈VN，u.line≠v.line，u.station=v.station?dist（u，v）≤ALMD，u?startVertex（S）?v?startVertex（S），u?endVertex（E）?v?endVertex（E）}]

[ EE={|u∈endVertex（E）?u=S?dist（S，E）≤ALMD}]

3） W是E到R的映射，[?e∈E]，[W（e）]是e的權(quán)值。

如圖3所示是一個檢索圖[SG（S，E，L）]，共4條公共線路[LS={L1，L2，L3，L4}]。[<5，2>]和[<5，9>]是出發(fā)弧。[<3，7>]、[<7，3>]，[<6，11>]和[<11，6>]是換乘弧。[<8，17>]、[<16，17>]是到達(dá)弧。其余的均為同線弧。

圖3 檢索圖

3 加權(quán)策略

檢索圖將每一條從起點(diǎn)到終點(diǎn)的路徑均定義為一條出行路徑，當(dāng)出行者提出檢索需求時僅需靈活地設(shè)置權(quán)值，就將最優(yōu)路徑檢索問題轉(zhuǎn)換為最短路徑問題，進(jìn)而用最短路徑算法解決問題。檢索圖的弧不僅可以表示站點(diǎn)間的運(yùn)行時間、運(yùn)行距離和車輛種類，還可以表示換乘耗時、距離、票價等，因此檢索圖能適用于多目標(biāo)檢索。本模型路徑檢索的優(yōu)先條件設(shè)定為：1、最少換乘；2、三類交通工具優(yōu)先級的設(shè)定，軌道或快速交通≥公交車≥公共自行車；3、步行距離最短；4、途經(jīng)的站點(diǎn)最少。

定理1 對于給定的檢索圖[SG（S，E，L）]，如果按照如下原則設(shè)置弧的權(quán)值，則由起點(diǎn)S到終點(diǎn)E的一條最短路徑一定也滿足模型設(shè)置的優(yōu)先條件。

1）每一條同線弧的權(quán)值設(shè)置為正常數(shù)d；

2）每一條到達(dá)弧[]的權(quán)值設(shè)置為[dist（u，v）]；

3）每一條出發(fā)弧當(dāng)成換乘??；

4）每一條換乘弧[]，其中[Wr+dist（u，v）]、[Wb+dist（u，v）]、[Wp+dist（u，v）]分別表示v對應(yīng)的線路為軌道或快速交通線路、公交車、自行車時的權(quán)值設(shè)置情況；

5）對于n次換乘，同時滿足如下條件：

[（n+1）×Wb+（n+2）×ALMD+（n+1）×Smax×d<（n+2）×Wr] （1）

[（n+1）×Wp+（n+2）×ALMD+（n+1）×Smax×d<（n+2）×Wb] （2）

[Wr+（n+2）×ALMD+（n+1）×Smax×d

[Wb+（n+2）×ALMD+（n+1）×Smax×d

[（n+1）×Smax×d

其中，[Smax]是線路L中最長線路（?？看螖?shù)最多）途經(jīng)的站點(diǎn)數(shù)；[Ad]是距離的表示精度（通常為10米）。

證明：設(shè)檢索圖[SG（S，E，L）]由起點(diǎn)S到終點(diǎn)E的一條最短路徑i對應(yīng)的出行路徑并非最優(yōu)路徑，則一定存在一條最優(yōu)出行路徑j(luò)，則j的路徑長度[D（j）]大于i的路徑長度[nj]，路徑j(luò)的換乘次數(shù)[nj]小于等于路徑i的換乘次數(shù)[bi]。

n次換乘的結(jié)果為：

[D（i）=（ni+1-bi-ri）×Wp+bi×Wb+ri×Wr+wdi+Si×d]

[D（j）=（nj+1-bj-rj）×Wp+bj×Wb+rj×Wr+wdj+Sj×d]

其中，[ni]、[nj]、[bi]、[rj]、[wdi]、[rj]、[wdi]、[Si]、[Si]、[bj≥bi] 分別表示路徑i、j中的換乘弧數(shù)、換乘公汽弧數(shù)、換乘軌道交通弧數(shù)、車外距離總和、同線弧數(shù)（途經(jīng)站點(diǎn)數(shù)減1）。由（1）和（2）式可知：[Wr

情況1：當(dāng)[njD（j）]，與假設(shè)的[D（i）

情況2：當(dāng)[nj=ni]、[rj>ri]時，令[W=（nj+1-bj-rj）×Wp+bj+Wb]，

則[D（j）=W+wdj+Sj×d][D（i）=W+（bj-bi）×（WP-Wb）+（rj-ri）×（WP-Wr）+wdi+Si×d]。當(dāng)[bj≥bi]時[D（i）>D（j）]，由[Wp>Wb]和（4）得[D（i）≥W+（ni+2）×ALMD+（ni+1）×Smax×d]。所以，[D（i）>D（j）]，與假設(shè)的[D（i）

同理可得，當(dāng)[nj=ni]、[rj=ri]、[W=nj+1-bj-rj×Wp+bj×Wb]時，令[W=nj+1-bj-rj×Wp+bj×Wb]，由（4）式得[D（i）>D（j）]，與假設(shè)的[D（i）D（j）]，與假設(shè)的[D（i）

上述考慮到了所有最短路徑i對應(yīng)非最優(yōu)路徑j(luò)的情況，因此檢索圖SG（S，E，L）的最短路徑一定是最優(yōu)路徑。

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

為驗(yàn)證模型的有效性，以杭州市真實(shí)的公交數(shù)據(jù)為背景，實(shí)現(xiàn)了一個簡單的公交檢索系統(tǒng)。系統(tǒng)以最少換乘、三類交通車輛優(yōu)先次序、步行距離最少和途徑站點(diǎn)最少作為檢索目標(biāo)。

4.1 確定權(quán)值

系統(tǒng)在實(shí)現(xiàn)最優(yōu)路徑檢索時，首先要建立檢索圖，然后根據(jù)定理1對檢索圖中的弧的權(quán)值進(jìn)行設(shè)置。對于任意[n≥0]，令[fn=n+2ALMD+n+1×Smax×d]。設(shè)軌道或快速列車、公交車和公共自行車的速度分別為[vr]、[vb]和[vp]，它們的相對速度為：[v'r]、[v'b]和[v'p]令[v'r>v'b>v'p>1]。

[v'r=mvrvr+vb+vp]、[v'b=mvbvr+vb+vp]、[v'p=mvpvr+vb+vp]

由式（1）和式（3）可得：

[Wr+f（n）

于是：[Wr>（n+2）f（n）]，令

[Wr=v'r（n+2）f（n）] （7）

根據(jù)式（6）可得：

[Wb<（n+2）2n+1v'rf（n）-f（n）n+1 Wb>v'r（n+2）f（n）+f（n）]

令：

[ Wb=[v'r（n+2）+v'b]f（n）] （8）

經(jīng)驗(yàn)證得滿足公式（6）。

由式（2）和式（4）可得：

[Wb+f（n）

于是：

[Wp>[v'r（n+2）+v'b+1]f（n）]

令

[Wp=[v'r（n+2）+v'b+v'p]f（n）] （10）

經(jīng)驗(yàn)證得滿足公式（9）。

由式（5）可得：

[d

則可令：

[d=Ad2（n+1）×Smax] （11）

根據(jù)文獻(xiàn)[6]剪枝原理可以將換乘次數(shù)n設(shè)置為6，超過六次換乘的解無實(shí)際意義。出行者可以根據(jù)自身的需求設(shè)置n，僅需[n≥0]；[vr]、[vb]、[vp]和[Smax]已知，設(shè)置m時需滿足[v'r>v'b>v'p>1]；ALMD和[Ad]可根據(jù)要求進(jìn)行設(shè)置，由式（7）、（8）、（10）和（11）就可以確定[Wr]、[Wb]和d的值，從而實(shí)現(xiàn)對檢索圖的權(quán)值設(shè)定。

4.2 實(shí)驗(yàn)結(jié)果

圖4 系統(tǒng)檢索頁面 （下轉(zhuǎn)第1026頁）

（上接第1013頁）

如圖4所示，實(shí)驗(yàn)系統(tǒng)用JAVA實(shí)現(xiàn)；換乘次數(shù)n設(shè)置為6；采用[Dijkstra]算法作為最短路徑算法。通過系統(tǒng)得到從西南大學(xué)到浙江大學(xué)紫金港校區(qū)的行車路線，調(diào)用百度地圖的[api]將檢索結(jié)果實(shí)現(xiàn)可視化。實(shí)驗(yàn)數(shù)據(jù)表明，提出的檢索模型實(shí)現(xiàn)了最少換乘、三類交通車輛優(yōu)先次序、步行距離最少和途徑站點(diǎn)最少四級優(yōu)先目標(biāo)路徑檢索，其檢索結(jié)果正確可靠。

5 結(jié)論

本文建立了一種新型的公交檢索模型。該模型不僅實(shí)現(xiàn)了將多種交通混合模式轉(zhuǎn)化為單一車輛問題，而且還根據(jù)弧的加權(quán)策略和迪杰斯拉算法實(shí)現(xiàn)了最優(yōu)檢索路徑，完成了出行者的多目標(biāo)檢索需求。實(shí)驗(yàn)表明該模型有效、實(shí)用，且能夠較好的滿足遠(yuǎn)距離、多目標(biāo)和多交通模式的檢索。

參考文獻(xiàn)：

[1] 王波，王萬良.一種基于加權(quán)復(fù)雜網(wǎng)絡(luò)的最優(yōu)公交換乘算法[J].武漢理工大學(xué)學(xué)報：交通科學(xué)與工程版，2008，32（06）：39-42.

[2] 閆小勇，尚艷亮.基于二部圖模型的公交網(wǎng)絡(luò)路徑搜索算法[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（05），246-248.

[3] 姚春龍，王昱.基于權(quán)值設(shè)定策略的公交出行路徑查詢模型[J].計(jì)算機(jī)工程與應(yīng)用， 2009， 45（11）： 241-244.

[4] 秦?zé)?，關(guān)宏志.停車換乘設(shè)施使用者調(diào)查[J].城市交通， 2012，10（01）：80-83.

[5] 楊雅君，高宏.多維代價圖模型上最優(yōu)路徑查詢問題的研究[J]計(jì)算機(jī)學(xué)報，2012， 35（10）： 2147-2158.

[6] 趙晶璐，何國斌.LC-檢索在城市公交線路查詢中的應(yīng)用研究[J].西南師范大學(xué)學(xué)報：自然科學(xué)版，2008，33（6）.

[7] 王強(qiáng).最短路徑問題的若干算法的編程[J] .計(jì)算機(jī)科學(xué)，2004，31（B07）：94-95.

[8] 孫凌宇，冷明等.賦權(quán)有向圖的最小生成樹算法[J].計(jì)算機(jī)工程，2010，36（02）：61-63.

[9] HERTEL O， HVIDBERG M et al. A proper choice of route significantly reduces air pollution exposure—a study on bicycle and bus trips in urban streets [J]. Science of the total environment， 2008， 389（1）： 58-70.