宋爽+張維石

摘要：分析公共交通網(wǎng)絡(luò)結(jié)構(gòu)的特征，基于圖論的方法，明確公交網(wǎng)絡(luò)中最短路徑的意義。根據(jù)對公交乘客出行心理的調(diào)查，發(fā)現(xiàn)換乘次數(shù)最少是首要考慮的因素。從節(jié)省存儲空間、提高運(yùn)算速度出發(fā)，將最少換乘次數(shù)問題轉(zhuǎn)化為最短路徑問題，設(shè)計并實現(xiàn)了一個基于最少換乘算法的公交查詢系統(tǒng)。以大連市具體的公共交通情況為例，證明系統(tǒng)是實用有效的。

關(guān)鍵詞：公交查詢；公交網(wǎng)絡(luò)；最少換乘；最優(yōu)路徑；Dijstra算法

中圖分類號：TP319 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）01-0096-03

Abstract： Analysing the characteristics of public transport network structure，and using method Based on graph theory，the significance of the shortest path in the public transport network is defined. According to the survey of bus passengers' travel psychology， it is found that the least number of transfers is the primary consideration. Starting from saving storage space and improving operation speed， the minimum transfer number problem is transformed into the shortest path problem，a bus inquiry system Based on least transfer algorithm is designed and implemented. Taking the specific public traffic in Dalian as an example， it is proved that the system is practical and effective.

Key words： public transport query； public transport network； least tranfer； optimal path；Dijstra algorithm

1 背景

在城市化水平不斷提高的當(dāng)代中國，各個城市的公共交通也隨之快速發(fā)展。隨著“低碳生活，綠色出行”概念的提出，以及大連市內(nèi)各種私家車限行政策和公交車優(yōu)惠政策的實行，使得人們更愿意選擇公交車作為出行必要的交通工具。公共交通已經(jīng)成為城市化發(fā)展和全面提高城市化水平的首要問題，是人們出行的首要選擇，越來越多的公交路線被提供，給人們出行帶來便利的同時，也給人們的選擇帶來了更大的困擾。在綜合考慮時間、距離、票價等因素的基礎(chǔ)上，人們更傾向于選擇以換乘次數(shù)最少為第一基準(zhǔn)、時間最短為第二基準(zhǔn)的路線作為出行路線。以大連市現(xiàn)有的公共交通情況為例，基于Android平臺，使用開源的、與操作系統(tǒng)無關(guān)的SQLite數(shù)據(jù)庫，通過對百度地圖API的調(diào)用，設(shè)計并實現(xiàn)了最少換乘算法下的移動公交查詢系統(tǒng)。

2 系統(tǒng)設(shè)計與實現(xiàn)

2.1 系統(tǒng)總體設(shè)計

系統(tǒng)采用結(jié)構(gòu)化的方法進(jìn)行總體設(shè)計，即把一個復(fù)雜系統(tǒng)的功能實現(xiàn)過程分解成各個子模塊的功能實現(xiàn)過程，這種分解過程是自頂向下、逐層分解，使得每個子模塊實現(xiàn)的功能都控制在人們?nèi)菀桌斫夂吞幚淼姆秶鷥?nèi)，并能夠保持子模塊功能的獨立性。系統(tǒng)主要分為兩大功能模塊，一是服務(wù)端后臺管理模塊，面向公交管理人員，主要實現(xiàn)了公交基本信息的管理，系統(tǒng)公告的管理、交互信息的管理等功能；二是客戶端用戶查詢模塊，面向普通用戶，主要實現(xiàn)了公交信息基本查詢、換乘查詢、熱點搜索、留言板等功能。

服務(wù)端后臺管理模塊中的公交基本信息管理主要用于添加、刪除或修改正在營運(yùn)的公交線路、站點、運(yùn)行時間、票價等基礎(chǔ)信息數(shù)據(jù)。系統(tǒng)公告管理主要用于發(fā)布重要事項和通知，例如線路站點臨時變更信息、線路暫時停運(yùn)信息等。交互信息管理主要用于對用戶的意見建議進(jìn)行反饋，提供人性化管理給用戶。

客戶端用戶查詢模塊中的公交信息基本查詢主要用于進(jìn)行線路、站點、運(yùn)行時間以及票價等的查詢。換乘查詢主要用于為用戶提供起始站和目的站間最合適的路徑規(guī)劃。熱點搜索主要用于搜索當(dāng)前位置周邊的KTV、飯店、商場等信息并在地圖上顯示給用戶。留言板主要用于普通用戶進(jìn)行意見反饋、分享實時公交信息等。

2.2 數(shù)據(jù)庫設(shè)計

客戶端采用Android自帶的輕量級關(guān)系型數(shù)據(jù)庫，占用資源低，在嵌入式系統(tǒng)中，大概只需要幾百K的內(nèi)存，能夠支持主流的操作系統(tǒng)，同時能夠跟很多程序語言相結(jié)合，比起Mysql、PostgreSQL這兩大開源的數(shù)據(jù)庫，處理速度更快。

服務(wù)端采用SQL Server關(guān)系型數(shù)據(jù)庫，具有使用方便、與相關(guān)軟件集成度高等優(yōu)點，已逐漸成為Windows平臺下進(jìn)行數(shù)據(jù)庫應(yīng)用開發(fā)較為理想的選擇之一。而且，由于其易操作性及友好的界面，贏得了廣大用戶的青睞，尤其SQL Server與其他數(shù)據(jù)庫如Access有良好的ODBC接口，可以將其轉(zhuǎn)成SQL Server數(shù)據(jù)庫。服務(wù)端主要設(shè)計三個數(shù)據(jù)表來存儲公交信息，分別是線路表、站點表以及線路-站點表，其數(shù)據(jù)字典如表1、表2以及表3所示。

2.3 查詢功能設(shè)計

公交查詢系統(tǒng)中最主要的功能就是公交基本信息和換乘路徑的查詢，以下分別簡單介紹線路查詢模塊、站點查詢模塊、換乘查詢模塊和到站時間預(yù)測模塊。

2.3.1 線路查詢模塊

系統(tǒng)根據(jù)用戶輸入的線路在本地數(shù)據(jù)庫進(jìn)行查詢，如果該線路存在，則直接顯示查詢結(jié)果；如果不存在，則聯(lián)網(wǎng)進(jìn)行查詢，首先判斷線路輸入是否為空或不合法，如果是則彈出錯誤提示，否則在后臺數(shù)據(jù)庫中查詢線路的所有信息，包括公交名稱、始末車時間、站點總數(shù)和票價。如果存在查詢結(jié)果，則將其顯示，否則提示線路不存在。endprint

2.3.2 站點查詢模塊

系統(tǒng)根據(jù)用戶輸入的站點訪問本地數(shù)據(jù)庫，如果站點存在，則返回途經(jīng)該站點的線路列表，用戶選擇一條指定線路后，返回途徑該站點的線路列表；如果不存在，則進(jìn)行聯(lián)網(wǎng)查詢，首先判斷站點輸入是否為空或不合法，如果是則彈出錯誤提示，否則在后臺數(shù)據(jù)庫中查詢該站點，找到途經(jīng)的所有線路。如果存在查詢結(jié)果，則將其結(jié)果顯示，否則提示站點不存在。

2.3.3 換乘查詢模塊

換乘查詢功能是系統(tǒng)最重要的模塊，用戶輸入起始站和目的站，系統(tǒng)查詢數(shù)據(jù)庫數(shù)據(jù)并根據(jù)最少換乘算法，設(shè)計合適的出行路線。系統(tǒng)首先訪問本地數(shù)據(jù)庫，判斷起始站是否存在，如果起始站存在，則再次訪本地數(shù)據(jù)庫，判斷目的站是否存在，如果目的站存在，則返回?fù)Q乘路線供用戶選擇。用戶選擇其中一個路線，可顯示該路線的具體方案。

2.3.4 到站時間預(yù)測模塊

公交車輛到達(dá)時間預(yù)測主要利用GPS定位系統(tǒng)、乘客手機(jī)GPS定位系統(tǒng)來獲取乘客和待乘公交車之間的距離，再根據(jù)公交車輛當(dāng)前的速度，和具體道路交通狀況，從而估算出公交差到乘客所在位置大致需要的時間，提前5-10分鐘提醒乘客。

3 核心算法分析與實現(xiàn)

3.1 公交網(wǎng)絡(luò)及最短路徑

公交網(wǎng)絡(luò)是由線路和站點組成的，一條公交線路需要經(jīng)過若干個站點，一個公交站點又會有若干條公交線路經(jīng)過，公交線路與線路之間通過共有的站點產(chǎn)生聯(lián)系，而公交站點與站點之間則通過線路產(chǎn)生聯(lián)系。將公交站點用有窮非空的點集合V來表示，公交線路用有向帶權(quán)的邊集合E來表示，構(gòu)成的二元組G=（V， E）則可以表示一個公交網(wǎng)絡(luò)數(shù)據(jù)模型。

最短路徑問題是圖論中研究的一個經(jīng)典算法問題，旨在尋找圖中任意兩頂點之間的最短路徑。公交網(wǎng)絡(luò)中最短路徑問題可以描述為從起始站點S出發(fā)到達(dá)目的站點E，其中S和E之間可行的線路往往不只一條，而是有很多條，那么這么多可行的線路中哪一條是最短的呢？這里的“最短”可以是指實際經(jīng)過的路程最短，也可以拓展為許多方面的最高效率問題，比如時間最短、費(fèi)用最少、線路利用率最高等標(biāo)準(zhǔn)。

3.2 傳統(tǒng)的Dijkstra算法

經(jīng)典的圖論與計算機(jī)算法的有效結(jié)合，使得新的最短路徑算法不斷涌現(xiàn)。目前提出的最短路徑算法中，使用最多、計算速度比較快，又比較適合于計算兩點之間的最短路徑問題的數(shù)學(xué)模型就是經(jīng)典的Dijkstra算法。

Dijkstra算法是典型的單源最短路徑算法，用于計算從一個頂點到其余各頂點的最短路徑，由Dijkstra EW于1959年提出，適用于所有弧的權(quán)均為非負(fù)的情況，主要特點是以起始點為中心向外層層擴(kuò)展，直到擴(kuò)展到終點為止。該算法的基本思想是：設(shè)G=（V， E）是一個帶權(quán)有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以后每求得一條最短路徑 ， 就將加入到集合S中，直到全部頂點都加入到S中，算法結(jié)束），第二組為其余尚未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應(yīng)一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離是從v到此頂點只包括S中的頂點為中間頂點的當(dāng)前最短路徑長度。

Dijkstra算法存在的局限性：實現(xiàn)Dijkstra算法的核心步驟是從未標(biāo)記的點中選擇一個權(quán)值最小的弧段，這是一個循環(huán)比較的過程，必須把所有的點都掃描一遍。在大數(shù)據(jù)量的情況下，由于傳統(tǒng)的Dijkstra算法求解最短路徑問題運(yùn)用了關(guān)聯(lián)矩陣、鄰接矩陣和距離矩陣，在存儲圖形數(shù)據(jù)和進(jìn)行運(yùn)算時，需定義N×N的數(shù)組，其中N為網(wǎng)絡(luò)的結(jié)點數(shù)，當(dāng)網(wǎng)絡(luò)的結(jié)點數(shù)較大時，將占用大量的計算機(jī)內(nèi)存，同時大數(shù)組運(yùn)算起來是很浪費(fèi)時間的。

3.3 基于最少換乘的最優(yōu)路徑選擇算法

最少換乘算法的一個明顯缺陷是隨著換乘次數(shù)的增加，搜索速度會越來越慢，因此根據(jù)大連市公交線路的實際情況，本文認(rèn)為三次及以內(nèi)的轉(zhuǎn)車是比較合理的，超過三次的轉(zhuǎn)車情況在這里不予考慮。算法具體步驟如下：

1） 直達(dá)：設(shè)經(jīng)過起點S或其附近的線路為集合Ls，對應(yīng)的經(jīng)過終點E或其附近的線路為集合Le，尋找Ls與Le的交集，如果有則存在從起點S到終點E的直達(dá)線路，輸出結(jié)果，結(jié)束運(yùn)算，如果沒有則進(jìn)行下一步。

2） 一次換乘：設(shè)起點S乘車能直達(dá)的站點為集合Ms，Ms中的站點及其鄰近站點所經(jīng)過的路線為集合Lms，尋找Lms與Le的交集，如果有則存在從起點S到終點E的一次換乘線路，輸出結(jié)果，結(jié)束運(yùn)算，如果沒有則進(jìn)行下一步。當(dāng)搜索到的方案數(shù)目達(dá)到設(shè)定的最大方案數(shù)目maxCase時，結(jié)束搜索。

3） 二次換乘：設(shè)能夠直達(dá)終點E的站點為集合Me，Me中的站點及其鄰近站點所經(jīng)過的路線為集合Lme，求Lms與Lme的交集，如果有則存在從起點S到終點E的二次換乘線路，輸出結(jié)果，結(jié)束運(yùn)算，如果沒有則進(jìn)行下一步。當(dāng)搜索到的方案數(shù)目達(dá)到設(shè)定的最大方案數(shù)目maxCase時，結(jié)束搜索。

4） 三次換乘：設(shè)起點S通過一次換乘所能到達(dá)的站點為集合Mms，Mms中的站點及其鄰近站點所經(jīng)過的路線為集合Lm，求Lm 與Lme的交集，如果有則存在從起點S到終點E的三次換乘線路，輸出結(jié)果，結(jié)束運(yùn)算，如果沒有則進(jìn)行下一步。當(dāng)搜索到的方案數(shù)目達(dá)到設(shè)定的最大方案數(shù)目maxCase時，結(jié)束搜索。

4 結(jié)束語

根據(jù)城市公交運(yùn)行的實際情況以及人們出行的具體需求，以大連市為例，基于Android平臺，利用Java和JSP編程語言，設(shè)計開發(fā)了基于百度地圖的移動公交查詢系統(tǒng)，實現(xiàn)了對公交的線路信息、站點信息、換乘信息的查詢以及個性化定制服務(wù)，例如：語音搜索、到站提醒等功能，為用戶出行選擇高效快速的乘車路線提供了幫助。

參考文獻(xiàn)：

[1] 崔琳. 城市公交線路查詢系統(tǒng)的設(shè)計與實現(xiàn)[J]. 宿州學(xué)院學(xué)報， 2011， 26（8）：46-48.

[2] 文斌. 基于Android的移動公交輔助導(dǎo)航系統(tǒng)設(shè)計與實現(xiàn)[J]. 成都信息工程學(xué)院學(xué)報， 2012， 27（5）：437-442.

[3] 何苑， 郝夢巖. 基于百度地圖的移動公交查詢系統(tǒng)的設(shè)計與實現(xiàn)[J]. 山西電子技術(shù)， 2015（5）：45-47.

[4] 程璐瑤， 馬宏琳. 城市公交線路信息查詢系統(tǒng)的設(shè)計與實現(xiàn)[J]. 科技創(chuàng)新與應(yīng)用， 2017（27）：110-111.

[5] 王進(jìn). 實時公交查詢系統(tǒng)的優(yōu)化設(shè)計和實現(xiàn)[D]. 北京： 北京郵電大學(xué)， 2013： 32-38.

[6] 羅在文. 基于移動智能平臺的公交查詢系統(tǒng)[D]. 重慶： 電子科技大學(xué)， 2015.

[7] 劉茂華， 韓卯， 王巖， 等. 移動GIS公交查詢系統(tǒng)的實現(xiàn)分析[J]. 遼寧工程技術(shù)大學(xué)學(xué)報：自然科學(xué)版， 2015（3）.

[8] 石巖.公交車自助線路查詢系統(tǒng)的開發(fā)與測試[D]. 北京： 北京郵電大學(xué)， 2010.

[9] 陶佩楓. 城市公交查詢系統(tǒng)的設(shè)計與實現(xiàn)[D]. 長沙： 中南大學(xué)， 2008.

[10] 鮑江宏， 關(guān)毅璋. 基于矩陣運(yùn)算的公交查詢高效算法[J]. 計算機(jī)工程與應(yīng)用， 2008， 44（10）：198-200.endprint