曹建莉， 劉媛媛

(河南工業(yè)大學(xué) 理學(xué)院, 河南 鄭州 450001)

城市公交最優(yōu)路線(xiàn)查詢(xún)系統(tǒng)模型與算法設(shè)計(jì)

曹建莉， 劉媛媛

(河南工業(yè)大學(xué) 理學(xué)院, 河南 鄭州 450001)

以開(kāi)發(fā)城市公交查詢(xún)系統(tǒng)為目的,結(jié)合公交系統(tǒng)特點(diǎn),應(yīng)用圖論和規(guī)劃中的相關(guān)理論,以換乘次數(shù)最少為主要考慮因素,依據(jù)北京市公交系統(tǒng)相關(guān)信息,建立了最優(yōu)路線(xiàn)查詢(xún)系統(tǒng)的數(shù)學(xué)模型與算法設(shè)計(jì),給出了不同需求下的最優(yōu)乘車(chē)路線(xiàn)方案。

公交查詢(xún)系統(tǒng)；Dijkstra算法； 最短路徑； 多目標(biāo)規(guī)劃

公共交通在城市中具有舉足輕重的作用,為了滿(mǎn)足不同出行者的各種需求,有必要建立公交線(xiàn)路查詢(xún)系統(tǒng)[1-4],使查詢(xún)者可以在最短時(shí)間內(nèi)獲知公交線(xiàn)上任意兩站點(diǎn)間的最優(yōu)乘車(chē)路線(xiàn)及換乘方案。在選擇路線(xiàn)時(shí),換乘次數(shù)、出行費(fèi)用和出行總時(shí)間影響最大。本文針對(duì)公共汽車(chē)和地鐵的不同情況建立了3個(gè)模型,其中包含多目標(biāo)規(guī)劃模型[5-7]、Dijkstra算法改進(jìn)模型及由“輻線(xiàn)”求“輻點(diǎn)”模型[8-10]。

1 僅考慮公共汽車(chē)線(xiàn)路的模型方案

1.1 多目標(biāo)規(guī)劃模型

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

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

(1)

考慮加權(quán)函數(shù)的最小值問(wèn)題,對(duì)(1)式進(jìn)行化簡(jiǎn)得

(2)

表1 轉(zhuǎn)乘1次的最短出行時(shí)間和費(fèi)用表

1.2 Dijkstra改進(jìn)模型

無(wú)論是考慮最少換乘次數(shù)、最少路費(fèi)，還是最短時(shí)間,其核心都是最短路徑問(wèn)題。Dijkstra算法是經(jīng)典的最短路徑算法,理論上來(lái)說(shuō),Dijkstra算法采用對(duì)賦權(quán)圖進(jìn)行標(biāo)號(hào),相交各個(gè)中間點(diǎn)(站點(diǎn))上標(biāo)號(hào),從開(kāi)始的臨時(shí)標(biāo)號(hào)到后來(lái)的終點(diǎn)標(biāo)號(hào),逐個(gè)搜索從起始點(diǎn)到終點(diǎn)站之間的中間站,根據(jù)“整體最優(yōu),局部最優(yōu)”的結(jié)論,可以找到一條最短路徑。Dijkstra算法復(fù)雜性是O(n2),對(duì)無(wú)向賦權(quán)圖和有向賦權(quán)圖均適用,但是對(duì)于交通線(xiàn)路來(lái)說(shuō),通過(guò)增加附加的費(fèi)用或時(shí)間以及轉(zhuǎn)乘車(chē)次數(shù)對(duì)某些點(diǎn)賦權(quán)時(shí),不能用一般的最短路徑方法求解,需要對(duì)原圖作適當(dāng)?shù)男拚?/p>

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

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

1.3 輻點(diǎn)模型

首先定義“輻射線(xiàn)”的概念,即由某一個(gè)站點(diǎn)A0向外尋找所有經(jīng)過(guò)該站點(diǎn)的行車(chē)線(xiàn)Li,這些所有經(jīng)過(guò)該站點(diǎn)的行車(chē)線(xiàn)Li就組成了過(guò)該站點(diǎn)的輻射線(xiàn)。對(duì)該站點(diǎn)的所有行車(chē)線(xiàn)Li上的其他站點(diǎn)Ak再尋找一次所有經(jīng)過(guò)Ak的所有行車(chē)線(xiàn)Lj,這樣的一個(gè)過(guò)程稱(chēng)為對(duì)A0的一次輻射,這樣的過(guò)程反復(fù)進(jìn)行下去,將會(huì)形成很多輻射線(xiàn),這些輻射線(xiàn)交叉形成一片錯(cuò)綜復(fù)雜的網(wǎng)線(xiàn)。通過(guò)不同站點(diǎn)的各條輻射線(xiàn)相交形成的節(jié)點(diǎn)稱(chēng)為輻射線(xiàn)節(jié)點(diǎn),簡(jiǎn)稱(chēng)輻點(diǎn)。輻點(diǎn)模型的思路如下:

(1) 先做出起始站點(diǎn)的輻射線(xiàn),如果這些輻射線(xiàn)中有若干條經(jīng)過(guò)終點(diǎn)站,即說(shuō)明有經(jīng)過(guò)起始站到終點(diǎn)站的直達(dá)線(xiàn)路,如果沒(méi)有轉(zhuǎn)入下一步；

(2) 分別做出過(guò)起始站和終點(diǎn)站的一次輻射,若這些輻射線(xiàn)中有一個(gè)交點(diǎn),說(shuō)明通過(guò)一次轉(zhuǎn)乘可達(dá),所得節(jié)點(diǎn)即為從起始站到終點(diǎn)站的中轉(zhuǎn)站,否則轉(zhuǎn)入第3步；

(3) 分別做出過(guò)起始站和終點(diǎn)站的二次輻射,尋找輻點(diǎn),如果有,說(shuō)明從起始站到終點(diǎn)站有2次轉(zhuǎn)乘。如此循環(huán)下去,找到最終的中轉(zhuǎn)節(jié)點(diǎn)。上述過(guò)程的流程圖見(jiàn)圖2。

圖2 輻點(diǎn)模型流程圖

1.4 模型評(píng)價(jià)

模型一:以最小換乘次數(shù)為主要依據(jù),對(duì)不同的起始站點(diǎn)到終點(diǎn)站進(jìn)行搜索,同時(shí)以最小耗時(shí)為第2考慮因素,選取最佳行車(chē)路線(xiàn),適用于換乘次數(shù)較少情形。對(duì)于多次換乘來(lái)說(shuō),搜索起來(lái)比較繁瑣,但這種簡(jiǎn)單的規(guī)劃模型可以作為選擇路線(xiàn)的一般數(shù)學(xué)模型,由此直接搜索出最佳的行車(chē)路線(xiàn)。

模型二:基于經(jīng)典的Dijkstra算法,這種模型是解決最短路線(xiàn)的一般數(shù)學(xué)模型,適用于所給站點(diǎn),基于一次換乘所形成的節(jié)點(diǎn),因而這種算法所得的最佳路線(xiàn)是一種一次換乘的最佳路線(xiàn)。

模型三:通過(guò)引進(jìn)輻點(diǎn)作為中轉(zhuǎn)站,考慮多次換乘所得到的一般路線(xiàn)選擇,進(jìn)而根據(jù)不同乘客的需求做出相應(yīng)的選擇,能夠解決較復(fù)雜情形下的問(wèn)題。

2 同時(shí)考慮公汽與地鐵線(xiàn)路的選擇方案

在僅考慮公共汽車(chē)線(xiàn)路的基礎(chǔ)上,對(duì)地鐵T的換乘做出考慮。以最小換乘為前提,采用第1.4節(jié)中的模型三,對(duì)各個(gè)地鐵站附近的公共汽車(chē)站進(jìn)行一次輻射,看是否有經(jīng)過(guò)所要選擇的起始站和終點(diǎn)站的輻射線(xiàn),這種情況可以看成通過(guò)一次轉(zhuǎn)換地鐵到達(dá)目的地的選擇方案,如圖3所示。

圖3 公共汽車(chē)與地鐵交叉路線(xiàn)圖

圖中S1到S2的選擇路線(xiàn)為S1-T2-S2,也可通過(guò)多次轉(zhuǎn)換地鐵或公共汽車(chē)來(lái)實(shí)現(xiàn),但由于所經(jīng)過(guò)的站點(diǎn)數(shù)過(guò)多,其他方案會(huì)使轉(zhuǎn)乘次數(shù)增加很多,因而以至多轉(zhuǎn)乘一次地鐵來(lái)考慮最優(yōu)出行方案。

3 考慮站點(diǎn)之間的步行時(shí)間

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

對(duì)總費(fèi)用、行車(chē)時(shí)間和站點(diǎn)間的步行時(shí)間的約束條件為：

(3)

上述規(guī)劃模型(3)式考慮了一般出行情況,第1種求解方法是類(lèi)似于(2)式進(jìn)行計(jì)算的多目標(biāo)規(guī)劃法,第1種求解方法是采取在最壞情況下?tīng)?zhēng)取最好結(jié)果的策略,即極大極小法，有

(4)

第2種求解方法是用評(píng)價(jià)函數(shù)max{w1n,w2t,w3F},但在實(shí)際計(jì)算中不便直接求解上述目標(biāo)函數(shù),為此需要引入xn+1,設(shè)xn+1為w1n,w2t,w3F在D上的一個(gè)公共上界,則可構(gòu)造如下等價(jià)問(wèn)題：

(5)

4 結(jié)論

本文運(yùn)用不同方法對(duì)公交線(xiàn)路選擇問(wèn)題進(jìn)行了算法設(shè)計(jì)和建模,建立的數(shù)學(xué)模型具有可推廣性。由于數(shù)據(jù)的海量性,對(duì)于復(fù)雜的公交線(xiàn)路查詢(xún)不能一味采用Dijkstra算法,一方面公交線(xiàn)路網(wǎng)絡(luò)拓?fù)浜茈y用現(xiàn)有數(shù)據(jù)加以完整表示。另一方面,以Dijkstra算法來(lái)計(jì)算公交線(xiàn)路最短路徑在大數(shù)據(jù)量情形下,不僅計(jì)算速度過(guò)慢,而且手工篩選也使問(wèn)題十分復(fù)雜,需要建立更簡(jiǎn)單的計(jì)算方法和便捷的計(jì)算機(jī)程序以減小問(wèn)題的復(fù)雜性。

)

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

[2] 梁虹,袁小群,劉蕊,一種新的公交數(shù)據(jù)模型與公交查詢(xún)系統(tǒng)實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(3):234-238.

[3] 陳志明,梁虹,肖琦,等,基于ArcIMS和JSP的公交查詢(xún)系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].云南大學(xué)學(xué)報(bào):自然科學(xué)版,2008,30(2):219-222.

[4] 李天文,湯國(guó)安,栗向鋒,等,基于ComGIS的城市公交查詢(xún)系統(tǒng)[J].西北大學(xué)學(xué)報(bào):自然科學(xué)版,2006,36(3):493-496.

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

[6] 謝波,姜宏彬,城市公交系統(tǒng)的多目標(biāo)規(guī)劃模型[J].山東輕工業(yè)學(xué)院學(xué)報(bào):自然科學(xué)版,2008,22(3):57-60.

[7] 馮小輝,張威,梅偉,公交線(xiàn)路選擇的優(yōu)化設(shè)計(jì)[J].四川文理學(xué)院學(xué)報(bào),2008,18(2):122-124.

[8] 陳簫楓,蔡秀云,唐德強(qiáng),最短路徑算法分析及其在公交查詢(xún)的應(yīng)用[J].工程圖學(xué)學(xué)報(bào),2001(3):20-24.

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

[10] 王防修.Dijkstra算法在智能公交查詢(xún)系統(tǒng)中的應(yīng)用[J].武漢工業(yè)學(xué)院學(xué)報(bào),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

國(guó)家社會(huì)科學(xué)基金項(xiàng)目(14GBL153)；河南省教育科學(xué)“十二五”規(guī)劃項(xiàng)目([2012]-JKGHAB-0027)；河南工業(yè)大學(xué)優(yōu)培工程項(xiàng)目和教研項(xiàng)目(2014GJYJ-B30)資助

曹建莉(1971—),女，河南鞏義，博士，副教授，研究方向?yàn)楣铝⒆优c數(shù)學(xué)模型.

U

A

1002-4956(2015)8- 0075- 04