基于鄰接矩陣的公交換乘查詢算法設(shè)計(jì)與實(shí)現(xiàn)

孫金華，孟昭睿，謝彥麒

(廈門理工學(xué)院計(jì)算機(jī)與信息工程學(xué)院，福建 廈門 361024)

?

基于鄰接矩陣的公交換乘查詢算法設(shè)計(jì)與實(shí)現(xiàn)

孫金華，孟昭睿，謝彥麒

(廈門理工學(xué)院計(jì)算機(jī)與信息工程學(xué)院，福建 廈門 361024)

摘要：針對公交網(wǎng)絡(luò)換乘問題，基于有向賦權(quán)圖構(gòu)造了公共交通換乘矩陣，設(shè)計(jì)并實(shí)現(xiàn)以換乘次數(shù)最少為目標(biāo)的公交換乘查詢算法。在此基礎(chǔ)上，構(gòu)建公交查詢系統(tǒng)，用以完成公交線路查詢、公交站點(diǎn)查詢、公交換乘方案查詢等功能。通過實(shí)際測試表明，系統(tǒng)能運(yùn)行于基于Android系統(tǒng)的移動設(shè)備，為用戶出行帶來方便。

關(guān)鍵詞：公交換乘算法；最小換乘；換乘矩陣；公共交通網(wǎng)絡(luò)

0引言

人們搭乘公交之前，希望能獲知指定線路有哪些站點(diǎn)，到目的站點(diǎn)該如何換乘等信息，所以研發(fā)公交查詢系統(tǒng)，特別是能運(yùn)行于智能手機(jī)等移動平臺的公交查詢系統(tǒng)勢在必行。公交查詢系統(tǒng)中，最核心的問題是公交換乘問題[1]。目前，對公交換乘問題求解方法主要基于經(jīng)典的最短路徑算法和智能搜索算法，前者如Dijkstra改進(jìn)算法、Floyd算法等，后者如蟻群算法、A*算法等[2-3]。這些算法要么計(jì)算復(fù)雜、要么耗時(shí)較高，為了適應(yīng)移動設(shè)備運(yùn)行的需求，本文以換乘次數(shù)最少作為設(shè)計(jì)的首要目標(biāo)，引入換乘矩陣簡化查詢過程，提出了基于矩陣運(yùn)算的公交換乘算法，提高了算法的效率。

1公交網(wǎng)絡(luò)的抽象

公交車按既定的站點(diǎn)和線路運(yùn)行?？浚溥\(yùn)行線路具有連通性、節(jié)點(diǎn)性和有向性，故可將其視為連通的有向賦權(quán)圖[4-5]。把公交站點(diǎn)視為“節(jié)點(diǎn)”，連接站點(diǎn)間的線路視為“邊”，這樣公交網(wǎng)絡(luò)可用有向抽象圖G(S，R，M)表示[5-6]。

圖1　公交網(wǎng)絡(luò)圖

其中，S={Si|i=1,2,…,p}，為公交站點(diǎn)的集合，包括公交網(wǎng)絡(luò)中的所有站點(diǎn)和可能的線路起止點(diǎn)，對各站點(diǎn)進(jìn)行唯一編號；R={Rj|i=1,2,…,q}為公交線路集合，各線路給予唯一編號。在此約定，如果是上下行線或往返線路，被當(dāng)成兩條不同的線路，如果是環(huán)線，則當(dāng)成是一條線路；M={Ri|S1,S2,…,Sd}(i=1,2,…,q；d=1,2,…，p),表示為線路/站點(diǎn)關(guān)系集合,其元素Ri表示第i條線路依次包含站點(diǎn)S1至Sd，即其運(yùn)行路線為從起點(diǎn)站S1出發(fā)到終點(diǎn)站Sd止。

在抽象圖G(S，R，M)中，M本質(zhì)上描述的是各條公交線路和站點(diǎn)間的關(guān)系，引入線路矩陣M′=(mi,j)，其元素mi,j表示Ri路的第j個(gè)結(jié)點(diǎn)對應(yīng)的站點(diǎn)序號。公交網(wǎng)絡(luò)示例如圖1所示。

2公交換乘模型

2.1　單條線路的換乘矩陣

假定某市總共有N個(gè)公交站點(diǎn)，則任意兩個(gè)站點(diǎn)之間可否乘坐Ri路公交車到達(dá)可由Wi進(jìn)行描述[7]：

(1)

圖1中包含3條公交線路，各自的行程和所經(jīng)站點(diǎn)如表1所示。將公交線路R1、R2和R3分別轉(zhuǎn)化為對應(yīng)的矩陣W1、W2和W3可得：

表1　公交線路示例

2.2　整個(gè)公交網(wǎng)絡(luò)的換乘矩陣

假設(shè)這個(gè)城市總共有T路公交車，則對所有線路的公交換乘矩陣求和，便可得到該城市整個(gè)公交網(wǎng)絡(luò)的換乘矩陣：

(2)

在整個(gè)公交網(wǎng)絡(luò)所對應(yīng)的換乘矩陣中，如果第m行n列元素δm,n>0，則說明從m站可乘公交車到達(dá)n站，其中δm,n值為可選線路數(shù)目[7]。

3換乘算法

概括起來，公交換乘問題主要需要解決3個(gè)問題： 1)站點(diǎn)間是否可達(dá)？2)有哪幾路車可達(dá)？3)在哪些站點(diǎn)可換乘？

3.1　換乘算法設(shè)計(jì)

公交換乘算法所涉基礎(chǔ)數(shù)據(jù)包括公交換乘矩陣W和線路矩陣M′，如前所述，這兩類矩陣可以根據(jù)站點(diǎn)編號和公交線路直接生成。根據(jù)前面的理論分析和模型，可設(shè)計(jì)換乘算法：

輸入：起屹站點(diǎn)編號i,j；

輸出：從站點(diǎn)i到j(luò)途經(jīng)的公交線路編號；

算法步驟：

Step1:

Flag=0;//Flag,是否找到換乘方案標(biāo)記

iF(δi,j>0)//δi,j為換乘矩陣W中i行j列元素

{Flag=1;

標(biāo)記i到終點(diǎn)站j之間可直達(dá)；

//Row(i)為線路矩陣M′中i所處的列序號

查找M′包含i和j且Row(i)

輸出Lij； //Lij即為線路編號

}

else

gotoStep2;

Step 2://查找一次換乘方案

Flag=0;

For(k=1;k<=N;k++)//N為站點(diǎn)總數(shù)

iF(δi,k>0 &&δk,j>0)

{標(biāo)記k為中轉(zhuǎn)站

Flag=1;

查找M′包含i和k且Row(i)

查找M′包含k和j且Row(k)

輸出Lik，Lkj；

}

iF(Flag==0)//沒找到一次換乘方案

gotoStep3;

Step 3://查找二次換乘方案

Flag=0;//Flag為是否找到換乘方案的標(biāo)記

For(k=1;k<=N;k++)

For(t=1;t<=N;t++)

iF(δi,k>0 &&δk,t>0&&δt,j>0)

{標(biāo)記k,t為中轉(zhuǎn)站

Flag=1;

查找M′包含i和k且Row(i)

查找M′包含k和t且Row(k)

查找M′包含t和j且Row(t)

輸出Lik,Lkt,Ltj；

}

iF(Flag==0)

輸出沒有找到線路的提示信息;

由于城市公交線路通常是經(jīng)過交通管理部門嚴(yán)格規(guī)劃的，對中小城市而言，換乘次數(shù)一般不會超過2次，因此，算法中只考慮了最多2次換乘的情況，若需3次以上的換乘，方法相似，在此不作詳述。

3.2　算法時(shí)間性能分析

換乘矩陣W和線路矩陣M′根據(jù)公交公司站點(diǎn)和線路直接生成，共中W的規(guī)模為n×n，M′的行數(shù)目為整個(gè)城市的公交線路總數(shù)，列數(shù)目所有線路中最長線路站點(diǎn)數(shù)。初始化完成后，以后的查詢無需重新計(jì)算。

如果不考慮前期的數(shù)據(jù)準(zhǔn)備和后面的數(shù)據(jù)輸出，算法的運(yùn)算主要集中在步驟2和步驟3，計(jì)算的操作主要是對換乘矩陣W和線路矩陣M′中元素的搜尋。算法步驟1可直接讀取判斷，時(shí)間復(fù)雜度為O(1)，步驟2的為O(n)，步驟3的為O(n2)，綜合的時(shí)間復(fù)雜度為O(n2)，其中n為站點(diǎn)數(shù)。

對實(shí)際應(yīng)用問題而言，一般城市公交線路數(shù)不會很大、站點(diǎn)數(shù)也不會非常多。以廈門市公交數(shù)據(jù)為例，該市現(xiàn)有公交線路297條，不同名公交站點(diǎn)883個(gè)。對歷史數(shù)據(jù)的統(tǒng)計(jì)表明各類換乘比例為：直達(dá)12.6%，1次換乘58.78%,2次換乘27.76%，其他情況0.86%，據(jù)此可得廈門市公交平均換乘次數(shù)約為1×58.78%+2×27.76%+3×0.86%=1.168 8次。這表明，前述算法實(shí)際應(yīng)用于具體城市數(shù)據(jù)時(shí)，可在接近O(n)的時(shí)間內(nèi)完成，且n值通常小于1 000。

4算法實(shí)現(xiàn)與應(yīng)用

基于前述公交換乘算法，實(shí)現(xiàn)了公交查詢系統(tǒng)。系統(tǒng)采用C/S結(jié)構(gòu)，其中，后臺服務(wù)器主要提供公交線路到矩陣轉(zhuǎn)換及相關(guān)運(yùn)算、數(shù)據(jù)更新等服務(wù)。查詢系統(tǒng)運(yùn)行于Android智能手機(jī)客戶端，核心部分采用離線模式，經(jīng)服務(wù)器處理的換乘矩陣數(shù)據(jù)存儲于手機(jī)端SQLite數(shù)據(jù)庫中，采用不定期的一次性從服務(wù)器上更新公交站點(diǎn)和線路數(shù)據(jù)到本地?cái)?shù)據(jù)庫方式更新。

把本文算法應(yīng)用于實(shí)際的廈門市公交網(wǎng)絡(luò)，在Android 3.2、CPU頻率1.1 GHz，內(nèi)存為512 MB的手機(jī)平臺下，測試結(jié)果顯示，查詢?nèi)我鈨蓚€(gè)站點(diǎn)間的換乘方案，響應(yīng)時(shí)間不超過0.6 s，表明換乘算法能夠?qū)崿F(xiàn)公交換乘方案的查詢，是有效的。

5結(jié)束語

本文通過對公交網(wǎng)絡(luò)特征的分析，引進(jìn)公交線路的鄰接矩陣，建立網(wǎng)絡(luò)的換乘矩陣，用數(shù)學(xué)的方法有效解決公交換乘問題。將算法實(shí)際應(yīng)用廈門市公交地理數(shù)據(jù)，可在保證換乘次數(shù)最少的情況下，選擇公交換乘方案，表明算法是可行有效的，可應(yīng)用于大多數(shù)城市。

參考文獻(xiàn)

[1] 楊新苗,王煒,馬文騰.基于GIS的公交乘客出行路徑選擇模型[J].東南大學(xué)學(xué)報(bào)(自然科學(xué)版),2000,30(6):87-91.

[2]李孟磊.公交網(wǎng)絡(luò)模型與出行換乘研究[D].上海：華東師范大學(xué),2011：25-26.

[3]Huang Y,Yi Q,Shi M.An Improved Dijkstra Shortest Path Algorithm[C]//Proceedings oF the 2nd International ConFerence on Computer Science and Electronics Engineering.Paris:Atlantis Press，2013:226-229.

[4]張存保,李華,嚴(yán)新平.基于Web GIS的城市公交問路系統(tǒng)[J].武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版),2004,28 (1):99-102.

[5]姚春龍,李旭,沈嵐.公交出行最優(yōu)路徑搜索的有向賦權(quán)圖模型[J].計(jì)算機(jī)應(yīng)用研究,2013，30(4):1058-1063.

[6]鄭朝暉.公交網(wǎng)絡(luò)中最優(yōu)路徑算法的探索[J].太原師范學(xué)院學(xué)報(bào)(自然科學(xué)版),2008,7(2):37-43.

[7]續(xù)婷,朱烽.基于換乘次數(shù)最少的公交查詢模型[J].西南民族大學(xué)學(xué)報(bào)(自然科學(xué)版)，2010,36 (1):58-62.

Design and Implementation oF Algorithm For Public Transit TransFer

Based on Adjacency Matrix

Sun Jinhua， Meng Zhaorui， Xie Yanqi

(SchooloFComputerandInFormationEngineer，XiamenUniversityoFTechnology，XiamenFujian， 361024)

Abstract:The transFer matrix oF public traFFic network with nodes representing stations and directed arcs showing traFFic routes is presented， transFer matrix and line matrix are introduced to discuss the path-planning problem and the least transFer algorithm is obtained. By applying the transFer matrix theory， we design and realize an urban public transportation query system， which helps to Finish the bus lines and site inquiries and travel line planning， and so on. Tests and applications results show that the system can run on mobile devices based on the Android system， and it is easy For users to travel．

Key words:public traFFic transFer algorithm; minimum transFer; transFer matrix; public traFFic network

中圖分類號：TP311

文獻(xiàn)標(biāo)識碼：A

文章編號：1001-9146(2015)03-0060-04

作者簡介：孫金華(1976-)，男，福建三明人，講師，計(jì)算機(jī)軟件.

基金項(xiàng)目：福建省教育廳科技計(jì)劃資助項(xiàng)目(JB12184)

收稿日期：2014-09-11

DOI:10.13954/j.cnki.hdu.2015.03.012