申 靜

(陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西 漢中 723000)

0 引言

隨著人們生活水平的提高和城市化進(jìn)程的推進(jìn)，城市規(guī)模不斷擴(kuò)大，城市公交系統(tǒng)也越來(lái)越發(fā)達(dá)。這就使得公交線路互連交匯、錯(cuò)綜復(fù)雜，給當(dāng)?shù)鼐用窈屯獾赜慰偷某鲂袔?lái)了諸多不便。為了解決如何獲取足夠的公交出行信息、如何最便捷地獲得到達(dá)某一目的地的最佳乘車線路等問(wèn)題，研究和開發(fā)一個(gè)便捷、快速、準(zhǔn)確的公交查詢系統(tǒng)迫在眉捷。公交查詢系統(tǒng)性能的好壞是一個(gè)城市現(xiàn)代化進(jìn)程的一個(gè)重要標(biāo)志，所以研發(fā)操作便捷、快速、準(zhǔn)確的城市公交查詢系統(tǒng)具有非常重要的意義。

對(duì)于公交查詢系統(tǒng)的開發(fā)和研究，前人已經(jīng)做了大量的工作，但大多數(shù)城市公交路線查詢系統(tǒng)存在以下幾個(gè)方面的不足［1－4］。

①查詢結(jié)果復(fù)雜多樣但有效線路十分有限:大部分查詢系統(tǒng)生成了復(fù)雜的查詢結(jié)果，例舉了很多可能的出行方案，但實(shí)際上有些換乘路線繞行了很多彎路，甚至是不可達(dá)的，這對(duì)查詢者很不利。

②查詢速度較慢:由于公交查詢運(yùn)算速度與換乘次數(shù)是呈幾何級(jí)數(shù)關(guān)系增長(zhǎng)的，所以公交查詢系統(tǒng)普遍存在查詢速度慢的問(wèn)題，這就導(dǎo)致現(xiàn)有查詢系統(tǒng)一般只提供兩次以內(nèi)的換乘查詢結(jié)果。

③與實(shí)際的查詢結(jié)果存在差距:大部分系統(tǒng)提供的填入式每站查詢和羅列式選擇查詢方式不具備區(qū)域查詢和模糊查詢功能。

本文針對(duì)實(shí)際情況，按照居民的出行習(xí)慣，一般以換乘次數(shù)最少的公交線路為最優(yōu)乘車方案，提出了一種最少換乘算法，并探討了以最少換乘次數(shù)為目標(biāo)的公交查詢系統(tǒng)的實(shí)現(xiàn)方案。

1 算法的設(shè)計(jì)與分析

1.1 算法假設(shè)

根據(jù)居民實(shí)際出行乘車交通的習(xí)慣，排除環(huán)境的外界干擾因素，對(duì)算法作了以下假設(shè)［5－8］。

①相鄰公汽站點(diǎn)之間的平均行駛時(shí)間不變，即若任意兩站點(diǎn)si和sj之間的路程長(zhǎng)度為Sij，公汽的平均行駛速度為vij，則其站點(diǎn)si和站點(diǎn)sj之間的平均行駛時(shí)間tij=Sij/vij保持不變。。

②交通情況良好，各種交通工具的換乘時(shí)間保持不變。

③公汽環(huán)形路線即公汽的始發(fā)站和終點(diǎn)站之間的站點(diǎn)與終點(diǎn)站到始發(fā)站之間的站點(diǎn)是對(duì)應(yīng)相同的，且公汽從終點(diǎn)站到始發(fā)站回行時(shí)按原路返回。

④優(yōu)先考慮出行方案的換乘次數(shù)，其次考慮路程和費(fèi)用等因素。

⑤根據(jù)實(shí)際情況，兩次以內(nèi)換乘較合理，超過(guò)兩次換乘不予考慮。

以上各假設(shè)兼顧了給居民生活帶來(lái)便利和確保系統(tǒng)高效運(yùn)行這兩方面的需求，從而保證了算法的可行性和有效性。

1.2 算法的理論基礎(chǔ)

根據(jù)公交網(wǎng)絡(luò)本身所具有的連通性、節(jié)點(diǎn)性以及有向性等特點(diǎn)，把車站各站點(diǎn)抽象為點(diǎn)，各公交線路抽象為線，公交網(wǎng)絡(luò)就可以轉(zhuǎn)化為一個(gè)由站點(diǎn)和線段組成的有向連通圖，記為G(V，E)，其中V、E分別為G的站點(diǎn)集合和線段集合，從而可以利用圖論理論對(duì)網(wǎng)絡(luò)換乘進(jìn)行分析［1，9－10］。

考慮到人們的乘車心理，大部分人把轉(zhuǎn)乘次數(shù)少作為首要因素，則公交換乘可以歸結(jié)為尋求圖中給定一個(gè)始點(diǎn)vi及終點(diǎn)vj之間的最短路徑問(wèn)題。

目前，關(guān)于最短路徑搜索算法的研究成果有很多。其中，1959年Dijkstra提出的單源問(wèn)題算法是使用最廣的、適合拓?fù)渚W(wǎng)絡(luò)中兩節(jié)點(diǎn)間最短路徑搜索的算法之一。它不僅能求解出從始點(diǎn)到終點(diǎn)的最短路徑，而且最后得到的路徑實(shí)際上也是始點(diǎn)到各頂點(diǎn)的最短路徑。該算法能適應(yīng)網(wǎng)絡(luò)拓?fù)涞淖兓?，同時(shí)對(duì)系統(tǒng)的內(nèi)存空間占用少，因而在計(jì)算機(jī)網(wǎng)絡(luò)拓?fù)渎窂竭x擇以及地理信息系統(tǒng)(geographic information system，GIS)中得到了廣泛的應(yīng)用［1，7－10］。

基于以上Dijkstra算法適應(yīng)網(wǎng)絡(luò)拓?fù)渥兓艺加孟到y(tǒng)空間較少的特點(diǎn)，系統(tǒng)中的最少換乘算法即以Dijkstra算法為理論基礎(chǔ)［2－3］，查詢系統(tǒng)通過(guò)關(guān)鍵字的匹配，查找出任意兩個(gè)相連通站點(diǎn)之間的最短路徑。站點(diǎn)查詢的速度較理想，且路線以動(dòng)態(tài)的方式顯示，完全能夠滿足查詢信息系統(tǒng)的實(shí)際需求。

1.3 算法實(shí)現(xiàn)

采用鄰接矩陣M表示帶權(quán)有向公交系統(tǒng)網(wǎng)絡(luò)圖G，以游客當(dāng)前所在站點(diǎn)為出發(fā)點(diǎn)，記為S。在算法中，首先產(chǎn)生從S到S自身的路徑，這條路徑的長(zhǎng)度為0，記為l=0;再依次產(chǎn)生從S到圖G中其余站點(diǎn)的最短路徑，并相互比較，找出其中最短路徑，記為lmin;依此類推，產(chǎn)生圖G中任意出發(fā)點(diǎn)si與可達(dá)的目標(biāo)地sj之間的最短路徑lmin(si，sj)，用初始換乘矩陣M0(即鄰接矩陣)表示交通網(wǎng)絡(luò)圖G，交通網(wǎng)絡(luò)模擬圖如圖1所示。

圖1 交通網(wǎng)絡(luò)模擬圖Fig.1 Simulation diagram of the transport network

在交通網(wǎng)絡(luò)模擬過(guò)程中，設(shè)置初始矩陣為M0。

在算法實(shí)現(xiàn)的過(guò)程中，還需考慮賦權(quán)問(wèn)題，即在公交系統(tǒng)網(wǎng)絡(luò)圖G中，將任意站點(diǎn)si與sj之間的道路集合記為{Li，j}，其中最短路徑為 lmin(si，sj)?？紤]賦權(quán)因素，w［si，sj］表示查詢站點(diǎn) si到達(dá)目標(biāo)站點(diǎn) sj的最短加權(quán)路徑。在算法描述中，用d［j］數(shù)組的每個(gè)分量表示。在尋求最短路徑的同時(shí)，考慮賦權(quán)因素對(duì)換乘矩陣進(jìn)行分析，即在一次選乘不成功的前提下，出行旅客就會(huì)考慮到換乘，這時(shí)對(duì)初始矩陣M0通過(guò)一定的變換規(guī)則進(jìn)行變換。根據(jù)圖1的交通網(wǎng)絡(luò)情況，可得到經(jīng)過(guò)一次換乘的矩陣M1;在一次換乘不成功的前提下，同理可得到經(jīng)過(guò)兩次換乘的矩陣M2;最終得到基于最少換乘算法的最短線路。各算法具體描述如下。

1.3.1 最短路徑算法

最短路徑算法的具體步驟如下。

① 初始狀態(tài) S={s0}，d［i］=w［s0，si］，vi∈V(G)。

② 選擇 sk，使 d［k］=Min{d［i］|si∈V－ S，si∈V(G)}，則站點(diǎn)sk是目前求得的一條從站點(diǎn)s0出發(fā)的最短路徑的終點(diǎn)，令S=S+{sk}。

③修改所有不在S中的站點(diǎn)的最短路徑長(zhǎng)度，即如果 d［sk］+w ［sk，si］＜ d［si］，則 d［si］=d［sk］+w［sk，si］。

④重復(fù)步驟②和③共(n－1)次，即可求得由查詢站點(diǎn)到其他站點(diǎn)之間的最短路徑。

1.3.2 最少換乘算法

最少換乘算法的具體步驟如下。

①在最短路徑算法的基礎(chǔ)上，設(shè)置初始矩陣為M0，并輸入所有n個(gè)站點(diǎn);對(duì)于任何兩站點(diǎn)si、sj，如果這兩站點(diǎn)之間可以直達(dá)，則 M0(i，j)=1;否則，M0(i，j)=0，計(jì)算出初始矩陣M0。

② 一次換乘矩陣M1:在M0中，如果M0(i，j)=1，則M1(i，j)=M0(i，j)，表示不需要換乘;如果 M1(i，j)=0，并且存在點(diǎn) k，使得 M0(i，k)=1、M0(k，j)=1，則M1(i，j)=2，表示從站點(diǎn) si到 sj需經(jīng)過(guò)1 次換乘;否則，M1(i，j)=0，如此計(jì)算即可得1次換乘矩陣M1。

③ 二次換乘矩陣M2:在M1中，如果M1(i，j)=1或2，則 M2(i，j)=M1(i，j);如果 M2(i，j)=0，且存在點(diǎn)k，使得 M1(i，k)=1、M1(k，j)=2，則 M2(i，j)=3，表示從站點(diǎn) si到 sj需經(jīng)過(guò)兩次換乘;否則，M2(i，j)=0。

④結(jié)合最短路徑算法，在可達(dá)的最短路徑的前提下，輸出最少換乘路線Li，j;否則，轉(zhuǎn)步驟⑤。

⑤無(wú)換乘路線，停止計(jì)算，輸出相應(yīng)的提示信息。

矩陣 M0、M1、M2的表達(dá)式如下。

以圖1所示的交通網(wǎng)絡(luò)模擬圖為例，圖1所對(duì)應(yīng)的站點(diǎn)初始矩陣如式(1)中的 M0矩陣，其中 s1、s2、s3、s4、s5、s6代表矩陣的6行6列的行號(hào)和列號(hào)，其行列交匯處的值代表兩個(gè)站點(diǎn)之間的直達(dá)信息。若M0為1，則說(shuō)明兩站點(diǎn)可以直達(dá);若M0為0，則兩個(gè)站點(diǎn)之間不可直達(dá)，需要換乘。根據(jù)最少換乘算法，對(duì)M0經(jīng)過(guò)1次換乘所得的矩陣為M1，對(duì)M1再經(jīng)過(guò)2次換乘所得矩陣為M2。

對(duì)式(1)中的矩陣元素可作如下解釋，M0(s1，s2)=1，說(shuō)明s1行和s2列相交匯處的值為1，代表s1和s2兩站點(diǎn)之間可直達(dá);而M0(s2，s3)=0，說(shuō)明s2行和s3列相交匯處的值為0，代表s2和s3兩站點(diǎn)不可直達(dá)。在M0中，所有不可直達(dá)的站點(diǎn)經(jīng)一次換乘后成為矩陣M1，依據(jù)最少換乘算法，如 M0(s3，s1)=1，M0(s1，s2)=1，則M1(s2，s3)=2，說(shuō)明s2和s3站點(diǎn)之間需要一次換乘。類似矩陣M2中有M2(s3，s4)=3，則說(shuō)明在站點(diǎn)s3和s4之間要經(jīng)過(guò)兩次換乘才能到達(dá)。

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

根據(jù)上述基于最少換乘算法的公交模型，以漢中市的公交系統(tǒng)為實(shí)例進(jìn)行試驗(yàn)，實(shí)現(xiàn)了漢中市公交線路查詢系統(tǒng)。該系統(tǒng)能查詢出該網(wǎng)絡(luò)任意兩公交點(diǎn)的換乘路線，如21路所經(jīng)過(guò)的站點(diǎn)為:“北街口—蓮湖路—北大商城—北門口—郵電大樓—火車站—三里村—石馬坡”，23路所經(jīng)過(guò)的站點(diǎn)為:“風(fēng)景路—南門—衛(wèi)校—鐘樓—北街口—北大商城—北門口—陳家營(yíng)—前進(jìn)路—黃家塘”，若乘客所在的位置為21路的站點(diǎn)“蓮湖路”，要乘車到目的地“前進(jìn)路”站點(diǎn)，雖然21路不能直達(dá)，但通過(guò)系統(tǒng)的搜索匹配，23路可到達(dá)“前進(jìn)路”站點(diǎn)，且23路和21路有相交匯的站點(diǎn)“北大商城”，則乘客可乘21路車到“北大商城”，再在“北大商城”站點(diǎn)處換乘23路到達(dá)“前進(jìn)路”站點(diǎn)，即可到達(dá)乘車目的地。

試驗(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)的所有公交車，從而為用戶提供更多的公交信息。

在系統(tǒng)運(yùn)行環(huán)境中，系統(tǒng)的數(shù)據(jù)流查詢是用戶通過(guò)各種不同的關(guān)鍵字向數(shù)據(jù)庫(kù)傳遞查詢請(qǐng)求。查詢時(shí)，后臺(tái)接收到用戶發(fā)出的請(qǐng)求，系統(tǒng)根據(jù)用戶的請(qǐng)求，以一定的策略在數(shù)據(jù)庫(kù)中找出用戶需要的信息進(jìn)行反饋，從而獲得所查車次的所有站點(diǎn)。以查詢的結(jié)果為例，在車次查詢界面輸入要查詢的車次102，根據(jù)系統(tǒng)所存儲(chǔ)的路徑情況，系統(tǒng)自動(dòng)調(diào)出該車次所經(jīng)的所有站點(diǎn)。若輸入不同的站點(diǎn)，系統(tǒng)會(huì)輸出所有包含該站點(diǎn)的路線信息，并在最少換乘算法的支持下，為用戶提供中轉(zhuǎn)查詢，且盡可能地在可達(dá)目的地的最短路徑的前提下獲得換乘次數(shù)最少的路線。

由于系統(tǒng)數(shù)據(jù)模型以公交站點(diǎn)及站點(diǎn)間的線段為基礎(chǔ)，當(dāng)已有的公交路線需要更改或增加新的公交路線時(shí)，只需要對(duì)相應(yīng)的公交站點(diǎn)和線段進(jìn)行修改，而無(wú)需對(duì)整個(gè)數(shù)據(jù)庫(kù)進(jìn)行修改，因而系統(tǒng)具有很好的擴(kuò)展性。系統(tǒng)的構(gòu)造模型對(duì)于類似公交站點(diǎn)之間的出行方式也同樣適用，因此系統(tǒng)具有很好的通用性。

3 結(jié)束語(yǔ)

根據(jù)實(shí)際生活中人們以最少換乘作為首要考慮因素，以Dijkstra算法為理論基礎(chǔ)的最少換乘算法，有效地解決了公交查詢系統(tǒng)中所遇到的問(wèn)題，并通過(guò)試驗(yàn)驗(yàn)證了算法的科學(xué)性與正確性。在實(shí)現(xiàn)環(huán)境中，通過(guò)對(duì)復(fù)雜語(yǔ)句的設(shè)置支持模糊查詢，以有利于對(duì)公交線路或站點(diǎn)不熟悉的乘客，使居民對(duì)城市公交信息的獲得不單單局限于靜態(tài)和單一的信息獲取，同時(shí)還提供了動(dòng)態(tài)的公交信息發(fā)布，為居民的出行提供了便利。針對(duì)大中型城市公交查詢系統(tǒng)，一般應(yīng)配置有一臺(tái)比較大型的服務(wù)器存放數(shù)據(jù)，以提供更為詳盡多樣的查詢方式，并利用合理的線路評(píng)價(jià)機(jī)制得出最優(yōu)線路。日后，這方面的工作還有待更進(jìn)一步的研究。

［1］常青.車輛導(dǎo)航定位方法及應(yīng)用［M］.北京:機(jī)械工業(yè)出版社，2005.

［2］倪華芳.GIS系統(tǒng)及其在化工企業(yè)管理中的應(yīng)用［J］.自動(dòng)化儀表，2005，26(3):64－66.

［3］Yang Yahong，Gao Jingchang.Application of design patterns for GIS platform software［J］.Journal of Jilin University:InformationScience Edition，2003，21(2):153－155.

［4］劉洪瑋，石紅瑞.遺傳算法在汽車巡航控制系統(tǒng)中的應(yīng)用［J］.自動(dòng)化儀表，2009，30(11):48－50.

［5］申靜，姚軍財(cái).基于多Agent協(xié)商的決策支持系統(tǒng)的研究［J］.微電子學(xué)與計(jì)算機(jī)，2009，26(5):76－79.

［6］于小平，楊國(guó)東，王鳳艷，等.城市公交查詢系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)［J］.吉林大學(xué)學(xué)報(bào):信息科學(xué)版，2005，23(6):675－678.

［7］張延林，佟德軍.BP神經(jīng)網(wǎng)絡(luò)的汽車故障診斷系統(tǒng)［J］.自動(dòng)化儀表，2009，30(4):11－13.

［8］陳簫楓，蔡秀云，唐德強(qiáng).最短路徑算法分析及其在公交查詢的應(yīng)用［J］.工程圖學(xué)學(xué)報(bào)，2001(3):20－24，788－793.

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

［10］李響，張睿智.公交查詢系統(tǒng)的數(shù)學(xué)模型［J］.黑龍江大學(xué)自然科學(xué)學(xué)報(bào)，2008，25(4):554－557.