基于最少換乘算法的公交查詢系統

宋爽+張維石

摘要：分析公共交通網絡結構的特征，基于圖論的方法，明確公交網絡中最短路徑的意義。根據對公交乘客出行心理的調查，發現換乘次數最少是首要考慮的因素。從節省存儲空間、提高運算速度出發，將最少換乘次數問題轉化為最短路徑問題，設計并實現了一個基于最少換乘算法的公交查詢系統。以大連市具體的公共交通情況為例，證明系統是實用有效的。

關鍵詞：公交查詢；公交網絡；最少換乘；最優路徑；Dijstra算法

中圖分類號：TP319 文獻標識碼：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 背景

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

2 系統設計與實現

2.1 系統總體設計

系統采用結構化的方法進行總體設計，即把一個復雜系統的功能實現過程分解成各個子模塊的功能實現過程，這種分解過程是自頂向下、逐層分解，使得每個子模塊實現的功能都控制在人們容易理解和處理的范圍內，并能夠保持子模塊功能的獨立性。系統主要分為兩大功能模塊，一是服務端后臺管理模塊，面向公交管理人員，主要實現了公交基本信息的管理，系統公告的管理、交互信息的管理等功能；二是客戶端用戶查詢模塊，面向普通用戶，主要實現了公交信息基本查詢、換乘查詢、熱點搜索、留言板等功能。

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

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

2.2 數據庫設計

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

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

2.3 查詢功能設計

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

2.3.1 線路查詢模塊

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

2.3.2 站點查詢模塊

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

2.3.3 換乘查詢模塊

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

2.3.4 到站時間預測模塊

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

3 核心算法分析與實現

3.1 公交網絡及最短路徑

公交網絡是由線路和站點組成的，一條公交線路需要經過若干個站點，一個公交站點又會有若干條公交線路經過，公交線路與線路之間通過共有的站點產生聯系，而公交站點與站點之間則通過線路產生聯系。將公交站點用有窮非空的點集合V來表示，公交線路用有向帶權的邊集合E來表示，構成的二元組G=（V， E）則可以表示一個公交網絡數據模型。

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

3.2 傳統的Dijkstra算法

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

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

Dijkstra算法存在的局限性：實現Dijkstra算法的核心步驟是從未標記的點中選擇一個權值最小的弧段，這是一個循環比較的過程，必須把所有的點都掃描一遍。在大數據量的情況下，由于傳統的Dijkstra算法求解最短路徑問題運用了關聯矩陣、鄰接矩陣和距離矩陣，在存儲圖形數據和進行運算時，需定義N×N的數組，其中N為網絡的結點數，當網絡的結點數較大時，將占用大量的計算機內存，同時大數組運算起來是很浪費時間的。

3.3 基于最少換乘的最優路徑選擇算法

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

1） 直達：設經過起點S或其附近的線路為集合Ls，對應的經過終點E或其附近的線路為集合Le，尋找Ls與Le的交集，如果有則存在從起點S到終點E的直達線路，輸出結果，結束運算，如果沒有則進行下一步。

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

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

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

4 結束語

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

參考文獻：

[1] 崔琳. 城市公交線路查詢系統的設計與實現[J]. 宿州學院學報， 2011， 26（8）：46-48.

[2] 文斌. 基于Android的移動公交輔助導航系統設計與實現[J]. 成都信息工程學院學報， 2012， 27（5）：437-442.

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

[4] 程璐瑤， 馬宏琳. 城市公交線路信息查詢系統的設計與實現[J]. 科技創新與應用， 2017（27）：110-111.

[5] 王進. 實時公交查詢系統的優化設計和實現[D]. 北京： 北京郵電大學， 2013： 32-38.

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

[7] 劉茂華， 韓卯， 王巖， 等. 移動GIS公交查詢系統的實現分析[J]. 遼寧工程技術大學學報：自然科學版， 2015（3）.

[8] 石巖.公交車自助線路查詢系統的開發與測試[D]. 北京： 北京郵電大學， 2010.

[9] 陶佩楓. 城市公交查詢系統的設計與實現[D]. 長沙： 中南大學， 2008.

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