城市公交最優路線查詢系統模型與算法設計

曹建莉， 劉媛媛

(河南工業大學 理學院, 河南 鄭州 450001)

城市公交最優路線查詢系統模型與算法設計

曹建莉， 劉媛媛

(河南工業大學 理學院, 河南 鄭州 450001)

以開發城市公交查詢系統為目的,結合公交系統特點,應用圖論和規劃中的相關理論,以換乘次數最少為主要考慮因素,依據北京市公交系統相關信息,建立了最優路線查詢系統的數學模型與算法設計,給出了不同需求下的最優乘車路線方案。

公交查詢系統；Dijkstra算法； 最短路徑； 多目標規劃

公共交通在城市中具有舉足輕重的作用,為了滿足不同出行者的各種需求,有必要建立公交線路查詢系統[1-4],使查詢者可以在最短時間內獲知公交線上任意兩站點間的最優乘車路線及換乘方案。在選擇路線時,換乘次數、出行費用和出行總時間影響最大。本文針對公共汽車和地鐵的不同情況建立了3個模型,其中包含多目標規劃模型[5-7]、Dijkstra算法改進模型及由“輻線”求“輻點”模型[8-10]。

1 僅考慮公共汽車線路的模型方案

1.1 多目標規劃模型

在僅考慮公共汽車線路的前提下,如何解決線路的轉乘問題,需要綜合考慮乘客的不同需求。在諸多因素中,換乘次數是大部分公交乘客在選擇出行路線時首先考慮的因素,其次是出行耗時和距離長短[1],而出行耗時與換乘次數、步行時間以及距離的長短密切相關,因此站點的換乘問題需重點考慮。在設計乘車方案時,假定乘客的基本需求分為3種:換乘次數(用n表示)最少,乘車費用(用S表示)最小與乘車時間(用t表示)最短。其他綜合需求可加入3種基本需求的權重(w1,w2,w3)來進行考慮,數學模型如下：

f=min(w1t+w2n+w3S),其中t=5n+3Mn

(1)

考慮加權函數的最小值問題,對(1)式進行化簡得

(2)

表1 轉乘1次的最短出行時間和費用表

1.2 Dijkstra改進模型

無論是考慮最少換乘次數、最少路費，還是最短時間,其核心都是最短路徑問題。Dijkstra算法是經典的最短路徑算法,理論上來說,Dijkstra算法采用對賦權圖進行標號,相交各個中間點(站點)上標號,從開始的臨時標號到后來的終點標號,逐個搜索從起始點到終點站之間的中間站,根據“整體最優,局部最優”的結論,可以找到一條最短路徑。Dijkstra算法復雜性是O(n2),對無向賦權圖和有向賦權圖均適用,但是對于交通線路來說,通過增加附加的費用或時間以及轉乘車次數對某些點賦權時,不能用一般的最短路徑方法求解,需要對原圖作適當的修正。

下面以圖1為例對一般的線路選擇問題進行分析。如果給出任意兩點,要求出在所有從節點1到節點9的路線中的最短路徑,則需知道從1到9的直達矩陣t,此時t=(tij)9×9,其中tij為節點i→j直達線路時間,于是求得:

圖1 公交網絡圖

1.3 輻點模型

首先定義“輻射線”的概念,即由某一個站點A0向外尋找所有經過該站點的行車線Li,這些所有經過該站點的行車線Li就組成了過該站點的輻射線。對該站點的所有行車線Li上的其他站點Ak再尋找一次所有經過Ak的所有行車線Lj,這樣的一個過程稱為對A0的一次輻射,這樣的過程反復進行下去,將會形成很多輻射線,這些輻射線交叉形成一片錯綜復雜的網線。通過不同站點的各條輻射線相交形成的節點稱為輻射線節點,簡稱輻點。輻點模型的思路如下:

(1) 先做出起始站點的輻射線,如果這些輻射線中有若干條經過終點站,即說明有經過起始站到終點站的直達線路,如果沒有轉入下一步；

(2) 分別做出過起始站和終點站的一次輻射,若這些輻射線中有一個交點,說明通過一次轉乘可達,所得節點即為從起始站到終點站的中轉站,否則轉入第3步；

(3) 分別做出過起始站和終點站的二次輻射,尋找輻點,如果有,說明從起始站到終點站有2次轉乘。如此循環下去,找到最終的中轉節點。上述過程的流程圖見圖2。

圖2 輻點模型流程圖

1.4 模型評價

模型一:以最小換乘次數為主要依據,對不同的起始站點到終點站進行搜索,同時以最小耗時為第2考慮因素,選取最佳行車路線,適用于換乘次數較少情形。對于多次換乘來說,搜索起來比較繁瑣,但這種簡單的規劃模型可以作為選擇路線的一般數學模型,由此直接搜索出最佳的行車路線。

模型二:基于經典的Dijkstra算法,這種模型是解決最短路線的一般數學模型,適用于所給站點,基于一次換乘所形成的節點,因而這種算法所得的最佳路線是一種一次換乘的最佳路線。

模型三:通過引進輻點作為中轉站,考慮多次換乘所得到的一般路線選擇,進而根據不同乘客的需求做出相應的選擇,能夠解決較復雜情形下的問題。

2 同時考慮公汽與地鐵線路的選擇方案

在僅考慮公共汽車線路的基礎上,對地鐵T的換乘做出考慮。以最小換乘為前提,采用第1.4節中的模型三,對各個地鐵站附近的公共汽車站進行一次輻射,看是否有經過所要選擇的起始站和終點站的輻射線,這種情況可以看成通過一次轉換地鐵到達目的地的選擇方案,如圖3所示。

圖3 公共汽車與地鐵交叉路線圖

圖中S1到S2的選擇路線為S1-T2-S2,也可通過多次轉換地鐵或公共汽車來實現,但由于所經過的站點數過多,其他方案會使轉乘次數增加很多,因而以至多轉乘一次地鐵來考慮最優出行方案。

3 考慮站點之間的步行時間

假設n1、n2、n3,n4分別為汽車換乘汽車、汽車換乘地鐵、地鐵換乘汽車、地鐵換乘地鐵的總次數,Wt為站點之間步行總時間,n為換乘總次數,t1為步行總時間,F為總費用,Fn1i為汽車換乘汽車時第i次換乘的那段時間內所花費的總費用,同樣對Fn2i、Fn3i和Fn4i有相似的定義,Mn1i表示汽車換乘汽車時第i次換乘的那段時間內所經過的站點總數,同理可得Mn2i,Mn3i,Mn4i,Mn=∑∑Mni,這里轉乘次數:n=n1+n2+n3+n4,步行總時間t1=Wt+2(n1+n3)+4(n2+n4),其中n1+n2+n3+n4≤6,n1、n2、n3、n4≤2。

對總費用、行車時間和站點間的步行時間的約束條件為：

(3)

上述規劃模型(3)式考慮了一般出行情況,第1種求解方法是類似于(2)式進行計算的多目標規劃法,第1種求解方法是采取在最壞情況下爭取最好結果的策略,即極大極小法，有

(4)

第2種求解方法是用評價函數max{w1n,w2t,w3F},但在實際計算中不便直接求解上述目標函數,為此需要引入xn+1,設xn+1為w1n,w2t,w3F在D上的一個公共上界,則可構造如下等價問題：

(5)

4 結論

本文運用不同方法對公交線路選擇問題進行了算法設計和建模,建立的數學模型具有可推廣性。由于數據的海量性,對于復雜的公交線路查詢不能一味采用Dijkstra算法,一方面公交線路網絡拓撲很難用現有數據加以完整表示。另一方面,以Dijkstra算法來計算公交線路最短路徑在大數據量情形下,不僅計算速度過慢,而且手工篩選也使問題十分復雜,需要建立更簡單的計算方法和便捷的計算機程序以減小問題的復雜性。

)

[1] 楊新苗,王煒,馬文騰,基于GIS的公交乘客出行路徑選擇模型[J].東南大學學報,2000,30(6):88-91.

[2] 梁虹,袁小群,劉蕊,一種新的公交數據模型與公交查詢系統實現[J].計算機工程與應用,2007,43(3):234-238.

[3] 陳志明,梁虹,肖琦,等,基于ArcIMS和JSP的公交查詢系統設計與實現[J].云南大學學報:自然科學版,2008,30(2):219-222.

[4] 李天文,湯國安,栗向鋒,等,基于ComGIS的城市公交查詢系統[J].西北大學學報:自然科學版,2006,36(3):493-496.

[5] 張鴻艷,諸秉政,徐晶,等,奧運公交線路選擇的數學模型[J].哈爾濱師范大學自然科學學報,2008,24(3):36-38.

[6] 謝波,姜宏彬,城市公交系統的多目標規劃模型[J].山東輕工業學院學報:自然科學版,2008,22(3):57-60.

[7] 馮小輝,張威,梅偉,公交線路選擇的優化設計[J].四川文理學院學報,2008,18(2):122-124.

[8] 陳簫楓,蔡秀云,唐德強,最短路徑算法分析及其在公交查詢的應用[J].工程圖學學報,2001(3):20-24.

[9] 韓慧玲,胡紅萍,Dijkstra算法在公交換乘最短路徑中的應用[J].硅谷,2011(21):111,126.

[10] 王防修.Dijkstra算法在智能公交查詢系統中的應用[J].武漢工業學院學報,2010,29(2):59-70.

Designofoptimalurbanpublictransportroutequerysystemmodelandalgorithm

Cao Jianli, Liu Yuanyuan

(College of Science,Henan University of Technology, Zhengzhou 450001, China)

Starting from the research and development of urban public transport inquiry system,combining the characteristics of public transport system and related theory in graph theory and programming,the minimum of transferring frequency is mainly considered.According to the public transportation information in Beijing,the mathematical model and algorithm design of optimal route query system are established.Meanwhile,the optimal route schemes under different demands are given.

public transport query system; Dijkstra algorithm; shortest path; multi-objective planning

2015- 03- 20

國家社會科學基金項目(14GBL153)；河南省教育科學“十二五”規劃項目([2012]-JKGHAB-0027)；河南工業大學優培工程項目和教研項目(2014GJYJ-B30)資助

曹建莉(1971—),女，河南鞏義，博士，副教授，研究方向為孤立子與數學模型.

U

A

1002-4956(2015)8- 0075- 04