基于最少換乘算法的公交查詢系統(tǒng)

宋爽+張維石

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

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

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

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

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

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

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

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

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

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

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

2.3 查詢功能設(shè)計(jì)

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

2.3.1 線路查詢模塊

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

2.3.2 站點(diǎn)查詢模塊

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

2.3.3 換乘查詢模塊

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

2.3.4 到站時(shí)間預(yù)測(cè)模塊

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

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