基于乘客終端的公交查詢系統(tǒng)設(shè)計

趙靜

摘 要： 城市道路基礎(chǔ)建設(shè)規(guī)模擴(kuò)大的同時，道路的延伸后，隨之滿足人民需要的公共交通線路也在不斷地增加。本文通過研究了公交換乘理論及換乘算法，從乘客終端角度設(shè)計公交查詢系統(tǒng)，主要實(shí)現(xiàn)的是查詢功能，包括線路、站點(diǎn)查詢和換乘查詢。并實(shí)現(xiàn)了多種換乘查詢方式，分別從換乘次數(shù)最少和最短路徑兩種方式得出不同換乘查詢結(jié)果，以滿足不同需求用戶的使用。

關(guān)鍵詞：換乘系統(tǒng) 查詢 換乘次數(shù)最少 最短路徑

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1003-9082（2016）06-0007-02

一、前言

隨著我國社會經(jīng)濟(jì)的發(fā)展，城市化進(jìn)程逐漸加快，人民出行頻率不斷增加，道路交通容量日趨飽和，交通問題日益突出。而城市公共交通具有運(yùn)量大、人均占有道路少等優(yōu)點(diǎn)。城市公共交通的發(fā)展趨勢為對快速性、舒適性、便捷性、環(huán)保等方面的要求。

先進(jìn)的信息技術(shù)也促進(jìn)了公共交通技術(shù)的發(fā)展，公交換乘系統(tǒng)是城市公共交通系統(tǒng)的一個子系統(tǒng)，發(fā)揮著比較關(guān)鍵的作用。為市民提供便捷的查詢系統(tǒng)，逐漸滿足市民出行多樣化的交通需求，方便地提供給人們出行時選擇最優(yōu)的公交換乘方案，從而降低了乘客出行成本，改善了人們的出行狀況。對于推動公共交通事業(yè)發(fā)展，提高公交服務(wù)水平具有一定的積極意義。

二、公交換乘理論

交通換乘行為是指出行者從某起始地到目的地的出行過程中，需要經(jīng)過同種交通方式或者不同交通方式搭乘轉(zhuǎn)換的全過程。而公交換乘系統(tǒng)正是提供的這種交通服務(wù)的必備手段。

研究換乘方式其實(shí)就是為了在地理網(wǎng)絡(luò)中選出一個最優(yōu)路徑。在交通出行過程中，最優(yōu)路徑是從某種優(yōu)化條件出發(fā)，依據(jù)搜索算法而得出的優(yōu)化路線。

在本系統(tǒng)設(shè)計中，為實(shí)現(xiàn)系統(tǒng)換乘查詢模塊的功能，主要提供兩種換乘查詢方式。一種是基于最短路徑的換乘查詢方式，另一種是基于換乘次數(shù)最少的換乘查詢方式。

1.基于最短路徑的公交換乘算法

在本系統(tǒng)設(shè)計中，為實(shí)現(xiàn)系統(tǒng)換乘查詢模塊的功能，主要提供兩種換乘查詢方式。最短路徑是指在換乘行為過程中距離最短，經(jīng)典算法為Dijkstra （迪杰斯特拉） 算法。Dijkstra算法主要用于搜索某一個節(jié)點(diǎn)到路網(wǎng)其他所有節(jié)點(diǎn)的最短路徑。該算法的優(yōu)點(diǎn)是單源搜索最短，僅考慮起點(diǎn)站和終點(diǎn)站之間的最短距離，而不考慮其他節(jié)點(diǎn)。算法簡潔，查詢效率較高。搜索結(jié)束后自動立即終止。但是Dijkstra算法的缺陷是：只考慮距離上的最優(yōu)解，這種求解過程導(dǎo)致了頻繁換乘，因此給用戶帶來了不便和相應(yīng)交通費(fèi)用增加。

Dijkstra [2]算法的基本思想是：先設(shè)置起始點(diǎn)集合U，取屬于集合U中的一個頂點(diǎn)，令其從源到該頂點(diǎn)的最短路徑長度已知。初始時，U中僅含有源點(diǎn)。設(shè)U是G的某一個頂點(diǎn)，把從源點(diǎn)到u且中間只經(jīng)過U中頂點(diǎn)的路徑稱為從到源點(diǎn)u的特殊路徑，該路徑記錄在Path中，路徑長度記錄在數(shù)組dist中。Dijkstra算法每次從V-U中取出具有最短特殊路徑長度的頂點(diǎn)u，將u添加到U中，同時對數(shù)組dist中進(jìn)行必要的修改，相應(yīng)地，修改Path。算法結(jié)束時，Dist中記錄了源點(diǎn)到其它各點(diǎn)的最短路徑的長度，Path中記錄相應(yīng)的路徑，算法過程如下[2]：

假設(shè)G=（V，E）用鄰接矩陣d來表示，d[i][j]表示邊（vi，vj）上的權(quán)值，若（vi，vj）不存在，則置d[i][j]為∞。

（1）初始設(shè)置：U={v0}，Path[i][j]=“v0vi”，最短路徑長度的初值為：Dist[i]=d[v0][vj] vi∈V-U；

（2）選擇u=vj，使得Dist[vj]=Min{Dist[i]/vi∈V-U}，則vj就是當(dāng)前求得的一條從v0出發(fā)的最短路徑的終點(diǎn)。令U=U∪{j}；

（3）修改從v0出發(fā)到V-S集合上任意頂點(diǎn)vk得到的最短路徑長度。如果：Dist[j]+d[j][k]

（4）重復(fù)操作（2）和（3），直到求得所有最短路。

算法求得從v0到圖上其余各頂點(diǎn)的最短路徑是依路徑長度遞增的序列。在公交線路查詢時，查詢起始站點(diǎn)為源點(diǎn)依次生成源點(diǎn)到其它各點(diǎn)的最短路徑，在此過程中，若查詢終點(diǎn)站點(diǎn)出現(xiàn)，則算法結(jié)束，即求得最短路徑及長度。

在公交查詢系統(tǒng)中，應(yīng)用Dijkstra算法求解最短路徑，在數(shù)據(jù)處理上存在一定的困難，由于一個大中型城市的公交線路多達(dá)上百條，而每一條線路的公交站點(diǎn)數(shù)十個，因此，如果求每一個站點(diǎn)的最短距離會大大地增加時間復(fù)雜度，是不科學(xué)的，直接導(dǎo)致搜索效率降低。根據(jù)前面章節(jié)的分析，城市公交發(fā)展的一個方面是建立良好的換乘樞紐，因此，節(jié)點(diǎn)的選擇主要設(shè)置為換乘頻繁，客流較多的換乘站。

在實(shí)際交通查詢中應(yīng)用最短路徑算法策略時，檢索的起點(diǎn)和終不完全在交叉點(diǎn)上。由于Dijkstra算法主要應(yīng)用于路網(wǎng)節(jié)點(diǎn)，而實(shí)際換乘點(diǎn)又不在網(wǎng)絡(luò)節(jié)點(diǎn)上，解決方法是可以在路網(wǎng)上設(shè)置虛擬節(jié)點(diǎn)，選擇位置為距離交叉點(diǎn)較近處為宜，如圖2-1所示。

為了統(tǒng)一應(yīng)用Dijkstra算法求最短路徑，針對虛擬結(jié)點(diǎn)，應(yīng)修改鄰接矩陣，然后運(yùn)用Dijkstra算法求解。算法過程如下：

（1）如果要查詢的站點(diǎn)剛好位于路網(wǎng)的交叉點(diǎn)處，則將虛擬結(jié)點(diǎn)標(biāo)識設(shè)置為False，并轉(zhuǎn)到步驟（3）；

（2）在交叉結(jié)點(diǎn)表中，加入虛擬結(jié)點(diǎn)，在鄰接矩陣中增加行和列，填入相應(yīng)的權(quán)；

（3）應(yīng)用Dijkstra算法，所示求解出最短路徑；

（4）若虛擬結(jié)點(diǎn)標(biāo)識為False，算法結(jié)束，否則，還原交叉結(jié)點(diǎn)表及鄰接矩陣。

由于電子地圖定位節(jié)點(diǎn)的問題，VB在軟件設(shè)計實(shí)現(xiàn)過程中采用的方法是先用輸入起始站和目的地站的站名后，搜索出線路，然后得出時間，接著考人工判斷并進(jìn)行對有路徑的判斷，同樣，在最短路徑方面也是一樣，通過搜索出的線路，然后從數(shù)據(jù)庫里調(diào)出時間，然后也通過人工判斷，最終也得出最有路徑。

2.基于換乘次數(shù)最少的最優(yōu)路徑方法

基于上面距離最短的換乘方式，人們考慮更多的是減少換乘次數(shù)，避免換乘頻繁帶來的麻煩。因此，換乘理論中，基于換乘次數(shù)最少的方式，與實(shí)際換乘系統(tǒng)的應(yīng)用聯(lián)系更為緊密。

基于換乘次數(shù)最少的換乘算法的算法思想核心是，根據(jù)調(diào)查顯示，出行者出行時對于公交線路的選擇時，多數(shù)優(yōu)先考慮是否有直達(dá)車。如果沒有直達(dá)車，則考慮一次換乘的方案，然后考慮中間站的位置。如果沒有一次換乘的方案，則考慮多次換乘?；趽Q乘次數(shù)最少的換乘該算法的基本思想：如果確定起始站點(diǎn)Q、終點(diǎn)站Z出發(fā)，與數(shù)據(jù)庫中各個線路中的站點(diǎn)相比較，尋找可換乘車站，得出可能的路徑。

設(shè)S（I）（I=1，2，…，m）為經(jīng)過起始站Q的線路集合。

T（J）（J=1，2，…，p）為線路S（I）上的所有站點(diǎn)的集合。

F（J，V）（V=1，2，…，g）為線路T（J）上的所有站點(diǎn)集合。

R（K）（K=1，2，…，g）為經(jīng)過站點(diǎn)E（I，U）的線路集合。

Y（O）（O=1，2，…Z）為經(jīng)過F（J，V）的線路集合。

G（K，W）（W=1，2，…i）為線路R（K）上的站點(diǎn)集合。

算法的步驟如下：

（1）根據(jù)出行目的，確定起始站Q，和終點(diǎn)站Z；

（2）分別求經(jīng)過起始站Q的所有線路集S（I），以及經(jīng)過終點(diǎn)站Z的所有線路集T（J）；

（3）經(jīng)過判斷條件S（I）與 T（J）是否相等。如果相等，即存在直達(dá)線路，輸出結(jié)果T（J）；如果沒有則下一步。

（4）求線路S（I）上的站點(diǎn)E（I，U）以及線路T（J）上的站點(diǎn)F（J，V）；

（5）通過模糊查詢，判斷是否存在某一區(qū)域相同但是站點(diǎn)名稱不同的站點(diǎn)；或者某一區(qū)域距離較近，短距離步行即可到達(dá)的站點(diǎn)。也就是要判斷E（I，U）= F（J，V），即得出一次換乘的一條路徑S（I），T（J）， 其中E（I，U）是中轉(zhuǎn)站點(diǎn)。

（6）分別求經(jīng)過E（I，U）的線路集R（K），和經(jīng)過F（J，V）的線路集Y（O）；

（7）經(jīng)過判斷條件R（K）= Y（O）是否相等。如果相等，則得出兩次換乘的一條可行路徑S（I）， R（K），T（J），經(jīng)過的中間換乘站點(diǎn)為E（I，U）和F（J，V），輸出結(jié)果，結(jié)束運(yùn)算。

依據(jù)哈爾濱市公交管理部門現(xiàn)有公交線路及現(xiàn)有站點(diǎn)的基本數(shù)據(jù)，哈爾濱市的公交線路可達(dá)性較強(qiáng)，最多情況下?lián)Q乘2次即可到達(dá)出行目的地，因此，在本設(shè)計中，僅研究換乘兩次的換乘查詢形式。

算法的流程為：輸入起始站點(diǎn)和終點(diǎn)站，判斷數(shù)據(jù)庫中各線路是否經(jīng)過這兩點(diǎn)，即是否可以直達(dá)。如果不存在直達(dá)線路，會繼續(xù)搜索經(jīng)過中間換乘車站，實(shí)現(xiàn)換乘1次到達(dá)終點(diǎn)站的所有路徑。如果直達(dá)、換乘1次都不存在，算法會將換乘次數(shù)修改為2，實(shí)現(xiàn)經(jīng)過2個中間換乘站到達(dá)終點(diǎn)站的所有路徑。如果直達(dá)、換乘1次、換乘2次，都沒有搜索到從起始站到終點(diǎn)站的路徑，那么系統(tǒng)會給出查詢失敗的提示。搜索換乘次數(shù)的流程圖如圖2-2所示。

三、公交換乘系統(tǒng)設(shè)計

1.系統(tǒng)設(shè)計目標(biāo)與流程

系統(tǒng)設(shè)計目標(biāo)是建成一個方便、實(shí)用、穩(wěn)定、安全的公交查詢及換乘系統(tǒng)。從功能角度，不僅能夠?yàn)楣还芾聿块T提供詳實(shí)、準(zhǔn)確的管理系統(tǒng)，而且還能夠?yàn)槌鲂姓咛峁┳钚碌墓徊樵冃畔⒁约昂侠淼膿Q乘路線方案。系統(tǒng)的建設(shè)，同時要滿足這兩個方面的需求，起到公交管理與出行者的溝通服務(wù)的橋梁作用。

公交換乘查詢系統(tǒng)的設(shè)計與建立，主要能夠服務(wù)于全體城市公共交通出行者，幫助出行者提供準(zhǔn)確、安全、可靠以及最優(yōu)的出行信息，從而吸引哈爾濱公共交通出行，減少擁堵，節(jié)能減排。

2.系統(tǒng)功能設(shè)計

城市公交查詢系統(tǒng)能夠幫助出行快速地選擇出行路徑、換乘路線等，既提升了出行者得效率，又優(yōu)化了公交資源的配置，提高了交通運(yùn)輸?shù)男屎统鞘械男畔⒎?wù)水平。目前，國內(nèi)對交通查詢系統(tǒng)進(jìn)行的研究已經(jīng)有很多，本設(shè)計實(shí)現(xiàn)了一個通用的，能夠進(jìn)行基于換乘次數(shù)最少、基于最短路徑、站點(diǎn)起終點(diǎn)的查詢。系統(tǒng)各功能模塊設(shè)計結(jié)構(gòu)圖如圖3-2所示。

四、公交換乘系統(tǒng)實(shí)現(xiàn)

信息查詢模塊主要包括線路查詢與站點(diǎn)查詢兩個子模塊。用戶可以根據(jù)出行需要，可以查詢某條公交線路，也可以按某一個公交站點(diǎn)查詢經(jīng)過的線路。

選擇“換乘查詢”菜單項(xiàng)，界面主要開始進(jìn)行路線搜尋，按換乘次數(shù)最少查詢，或者選擇距離最短查詢。其優(yōu)點(diǎn)可提供：

（1）站點(diǎn)名稱模糊化查詢；

（2）換乘查詢方式的多樣化查詢；

（3）換乘中間站查詢；

（4）線路推優(yōu)方案。

五、結(jié)論

本文所研究的算法具有通用性，可移植性強(qiáng)，設(shè)計的系統(tǒng)應(yīng)用簡單便捷，方便出行乘客使用，并能夠?yàn)橛脩籼峁┳罴殉霈F(xiàn)路線，從而降低了乘客出行成本，改善了人們的出行狀況。

參考文獻(xiàn)

[1]龔翱.改進(jìn)的城市公交查詢算法研究[J].湖南大學(xué)計算機(jī)應(yīng)用技術(shù)，2008年6月.

[2]王建聰，高利平，陳紹寬，何宇強(qiáng).城市公共交通樞紐換乘組織仿真研究[J].第6卷第6期，2006.

[3]林徐勛.多方式換乘動態(tài)路徑選擇建模研究[N].上海交通大學(xué)2009年.