王 慶，潘榮英

(蘇州市職業(yè)大學(xué) 數(shù)理部，江蘇 蘇州 215104)

城市公交最優(yōu)路徑選擇的數(shù)學(xué)模型及其算法

王 慶，潘榮英

(蘇州市職業(yè)大學(xué) 數(shù)理部，江蘇 蘇州 215104)

通過對(duì)城市公交路徑選擇問題的分析，在常用的Dijkstra最短路徑算法基礎(chǔ)上進(jìn)行改進(jìn)，根據(jù)乘客的不同需求給出出行總距離最短、出行總費(fèi)用最少、出行總時(shí)間最短的最優(yōu)路徑選擇模型.綜合考慮距離、時(shí)間、費(fèi)用等多種因素給出的出行滿意度最大的最優(yōu)路徑模型，同時(shí)以算例驗(yàn)證了模型和算法的合理性和實(shí)用性.

公交；Dijkstra算法；最優(yōu)路徑

隨著蘇州市經(jīng)濟(jì)的快速發(fā)展，城市的規(guī)模不斷擴(kuò)張，隨之而來的是城市道路交通擁堵問題越發(fā)嚴(yán)重[1].為了緩解城市道路交通擁堵，蘇州市近年以“公交優(yōu)先”為戰(zhàn)略，新開辟了很多的公交線路，但公眾出行還面臨著諸如公交網(wǎng)絡(luò)重復(fù)度高、公交線路過長、換乘不便等問題.因此，從蘇州市的實(shí)際出發(fā)，結(jié)合公眾實(shí)際出行的情況，建立城市公交最優(yōu)路徑選擇的數(shù)學(xué)模型有重要意義，不僅提高了公眾的出行效率，還節(jié)約了社會(huì)成本，促進(jìn)社會(huì)的可持續(xù)發(fā)展.

20世紀(jì)70年代初國外開始有關(guān)城市公交最優(yōu)路徑選擇的研究，80年代國內(nèi)學(xué)者開始關(guān)注，提出了各種相關(guān)算法，而且得到具體應(yīng)用[2].本文通過對(duì)常見的迪杰斯特拉(Dijkstra)最短路徑及其算法的分析，指出其實(shí)現(xiàn)公交最優(yōu)路徑選擇的缺點(diǎn)，根據(jù)蘇州市公交線路的實(shí)際，提出更適合公交查詢的改進(jìn)的Dijkstra最短路徑算法.通過引入蘇州市各條公交線路直達(dá)時(shí)的最短距離矩陣，構(gòu)造了公交網(wǎng)絡(luò)直達(dá)關(guān)系圖.根據(jù)公眾不同的出行需求，通過改進(jìn)的Dijkstra最短路徑算法，可以分別求得出行總距離最短、出行總費(fèi)用最少和出行總時(shí)間最少的公交線路.綜合考慮距離、時(shí)間、費(fèi)用等因素，建立公眾滿意度最大的最優(yōu)路徑選擇數(shù)學(xué)模型.

1 Dijkstra算法及其修正

圖1上兩點(diǎn)間的最短路徑的算法很多，1959年提出的Dijkstra最短路徑算法，目前應(yīng)用最為廣泛.它能夠得到起點(diǎn)到終點(diǎn)、起點(diǎn)到所有頂點(diǎn)的最短路徑，算法如下:

第1步，初始化.圖1中所有頂點(diǎn)組成的集合記為V={1，2，…，n}，起點(diǎn)O到任一頂點(diǎn)i的最短路徑距離為L[i]=min（D[i，1]）(其中D[i，1]是起點(diǎn)O到頂點(diǎn)i的距離)，最短路徑中在頂點(diǎn)O之前的最近頂點(diǎn)記為Y[i].

第2步，在V-S集合中搜尋使L[t]最小的頂點(diǎn)t，放入到S集合中，當(dāng)V-S是空集合時(shí)，停止搜尋.

第3步，改變Y，D中的值，即對(duì)V-S集合中頂點(diǎn)t的鄰接頂點(diǎn)i，如果L[i]>L[t]+D[i，t]，那么令Y[i]=t，L[i]=L[t]+D[i，t].

繼續(xù)執(zhí)行第2步.

由于公交線路形成的網(wǎng)絡(luò)拓?fù)浞浅?fù)雜，因而導(dǎo)致Dijkstra 最短路徑算法的數(shù)據(jù)結(jié)構(gòu)復(fù)雜、算法時(shí)間長.將公交站點(diǎn)看作網(wǎng)絡(luò)上的頂點(diǎn)，相鄰站點(diǎn)間的路段看作邊，Dijkstra 算法計(jì)算最短路徑時(shí)要求乘客每到一個(gè)公交站點(diǎn)都可以轉(zhuǎn)車，從而最短路徑可能需要很多次轉(zhuǎn)車，這樣的計(jì)算結(jié)果可行但沒有意義.考慮蘇州市的城市特點(diǎn)和公交線路的實(shí)際，認(rèn)為轉(zhuǎn)車不超過2次是符合實(shí)際的.為此，對(duì)Dijkstra 最短路徑算法[3]進(jìn)行修正.

第1步，輸入起點(diǎn)和終點(diǎn).

第2步，求過起點(diǎn)或其周邊的路線s(i)(i=1，2，…，m)，過終點(diǎn)或其周邊的路線t(j)(j=1，2，…，n).

第3步，搜尋s(i)=t(j)的路線，若有，輸出路線:起點(diǎn)到終點(diǎn)的直達(dá)路線為s(i)也即t(j)；若沒有，往下執(zhí)行.第4步，求路線s(i)上的站點(diǎn)E(i，x)(x=1，2，…，p)，路線t(j)上的站點(diǎn)F(i，y)(y=1，2，…，q).

第5步，搜尋E(i，x)=F(j，y)，若有，輸出路線:滿足此條件的路線s(i)，t(j)(可能有多條)就是換乘1次的公交路線，算出各種換乘1次的乘車路程，得到換乘1次的最短路線，再求換乘站點(diǎn)；若沒有，往下執(zhí)行.

第6步，求經(jīng)過E(i，x)的路線r(z)(z=1，2，…，k)，求路線r(z)的站點(diǎn)G(z，r)(r=1，2，…，h).

第7步，搜尋G(z，r)=F(j，y)，若有，輸出路線:滿足此條件的路線s(i)，t(j)，r(z)(可能有多條)，就是換乘2次的公交路線，算出各種換乘2次的乘車路程，得到換乘2次的最短路線，再求換乘地點(diǎn)；若沒有，表明換乘2次不可行，結(jié)束搜尋.

圖1 路徑

2 城市公交最優(yōu)路徑選擇模型

2.1 出行總距離最短的最優(yōu)路徑選擇模型

第1步，給出公交線路各站點(diǎn)直達(dá)時(shí)的距離矩陣.將公交站點(diǎn)作為頂點(diǎn)，依照公交車的行駛方向:雙向的站點(diǎn)之間用邊連接；單向的站點(diǎn)之間用弧連接，在公交線路站點(diǎn)的鄰接關(guān)系圖上運(yùn)用修正的Dijkstra算法，可以求出任意兩點(diǎn)之間的最短路徑，建立該線路的最短距離直達(dá)矩陣.

第2步，構(gòu)造公交系統(tǒng)總的各站點(diǎn)直達(dá)時(shí)的距離矩陣.將所有公交線路各站點(diǎn)直達(dá)時(shí)的距離矩陣用Λ ：aΛ b =min{a, b}合成，得到公交系統(tǒng)總的各站點(diǎn)直達(dá)時(shí)的距離矩陣 B= B1ΛB2Λ…ΛBn.

第3步，對(duì)矩陣B使用修正的Dijkstra算法，可以得到連接任意兩點(diǎn)出行總距離最短的最優(yōu)路徑.

2.2 出行總費(fèi)用最少的最優(yōu)路徑選擇模型

由于公交線路的收費(fèi)都與乘車距離成正比，先將各條公交線路的直達(dá)距離矩陣轉(zhuǎn)換為直達(dá)票價(jià)矩陣；再將直達(dá)票價(jià)矩陣?yán)眠\(yùn)算Λ合成為總的直達(dá)票價(jià)矩陣；最后對(duì)該直達(dá)票價(jià)矩陣?yán)酶倪M(jìn)的Dijkstra算法，可以得到連接任意兩點(diǎn)出行總費(fèi)用最少的最優(yōu)路徑.

2.3 出行總時(shí)間最少的最優(yōu)路徑選擇模型

出行總時(shí)間由公交運(yùn)行時(shí)間、換乘、等車的時(shí)間組成，而公交運(yùn)行時(shí)間與路程有關(guān).為了求出出行總時(shí)間最少的最優(yōu)路徑，規(guī)定公交路線上相鄰站點(diǎn)間的運(yùn)行時(shí)間與乘客的換乘時(shí)間大致相同，將各條公交線路的直達(dá)距離矩陣轉(zhuǎn)變?yōu)橹边_(dá)時(shí)間矩陣，再將直達(dá)時(shí)間矩陣?yán)眠\(yùn)算Λ合成為總的時(shí)間矩陣，最后按照下列算法計(jì)算任意兩站點(diǎn)之間的最短時(shí)間[4].

第3步，給出至多換乘k-1(k≥2)次就能到達(dá)的最短時(shí)間矩陣當(dāng)Tk=Tk?1時(shí)，得到任意兩個(gè)站點(diǎn)之間的最短通行時(shí)間矩陣.

2.4 出行滿意度最大的最優(yōu)路徑選擇模型

以上給出了只考慮一種因素(距離、時(shí)間、費(fèi)用等)時(shí)最優(yōu)路徑的選擇模型及算法.然而現(xiàn)實(shí)中，公眾出行選擇公交時(shí)，會(huì)綜合考慮距離、時(shí)間、費(fèi)用等因素來選擇滿意度最大的乘車路徑.為此，首先根據(jù)公眾出行的偏好來確定各因素的權(quán)重，將各條公交線路對(duì)應(yīng)的直達(dá)距離矩陣、直達(dá)時(shí)間矩陣、直達(dá)費(fèi)用矩陣標(biāo)準(zhǔn)化處理后加權(quán)平均，得到直達(dá)綜合滿意度矩陣；再對(duì)各條公交線路的直達(dá)綜合滿意度矩陣?yán)眠\(yùn)算Λ合成為總的直達(dá)綜合滿意度矩陣，利用修正的Dijkstra算法可以求出綜合滿意度最大的乘車線路.

3 具體算例

圖2是由6個(gè)站點(diǎn)(編號(hào)為a-f)，2條公交線路(實(shí)線為1號(hào)線、虛線為2號(hào)線，雙向且來回站點(diǎn)相同，用無向圖表示)構(gòu)成的公交網(wǎng).

圖2 6個(gè)站點(diǎn)構(gòu)成的公交網(wǎng)

首先，給出圖2中公交線路的直達(dá)關(guān)系矩陣

其次，利用Dijkstra算法得到每條線路的最短直達(dá)距離矩陣Bk=，其中表示第k號(hào)線第i站到第j 站的最短距離，

進(jìn)一步，給出圖中公交系統(tǒng)總的直達(dá)距離矩陣

其中bij(k)表示第i站到第j站乘坐k號(hào)線的最短路徑的距離.

最后，對(duì)總的直達(dá)距離矩陣使用修正的Dijkstra算法，給出任意兩站之間最短路徑的距離矩陣

依據(jù)最短路徑的距離矩陣就能得到經(jīng)過站點(diǎn)最少的乘車路徑.

進(jìn)一步，把任意站點(diǎn)之間的實(shí)際距離代入到各條公交線路對(duì)應(yīng)的直達(dá)關(guān)系矩陣，則可以得到任意兩站之間的出行總距離最短的最優(yōu)路徑；把任意站點(diǎn)之間的乘車費(fèi)用代入到各條公交線路對(duì)應(yīng)的直達(dá)關(guān)系矩陣，則可以得到任意兩站之間的出行總費(fèi)用最少的最優(yōu)路徑；把任意站點(diǎn)之間的出行時(shí)間代入到各條公交線路對(duì)應(yīng)的直達(dá)關(guān)系矩陣，則可以得到任意兩站之間的出行總時(shí)間最短的最優(yōu)路徑；將距離、時(shí)間、費(fèi)用等因素賦予權(quán)重，則可以得到任意兩站之間的出行滿意度最大的最優(yōu)路徑.

4 結(jié)論

利用改進(jìn)的Dijkstra最短路徑算法，根據(jù)乘客的不同需求給出出行總距離最短、出行總費(fèi)用最少、出行總時(shí)間最短的最優(yōu)路徑模型，綜合考慮距離、時(shí)間、費(fèi)用等多種因素給出出行滿意度最大的最優(yōu)路徑模型，同時(shí)以算例驗(yàn)證了模型和算法，說明模型和算法的合理性和實(shí)用性.

[1] 戴泉華，黃劍. 蘇州公交發(fā)展中的矛盾及解決方案[J]. 江蘇交通，2002(5):11- 13.

[2] 王建林. 基于換乘次數(shù)最少的城市公交網(wǎng)絡(luò)最優(yōu)路徑算法[J]. 經(jīng)濟(jì)地理，2005，25(5):673-676.

[3] 王振軍，王寧寧，李鴻. 基于鄰接矩陣的公交換乘算法的研究[J]. 徐州工程學(xué)院學(xué)報(bào)，2006，20(3):74-77.

[4] 許軍林，蔣年德. 一種改進(jìn)的公交換乘算法的實(shí)現(xiàn)[J]. 電腦知識(shí)與技術(shù)，2007，14(2):517-518.

(責(zé)任編輯:沈鳳英)

On the Mathematical Models and Algorithms of Optimal Public Transport Lines

WANG Qing，PAN Rong-ying
(Department of Mathematics and Physics，Suzhou Vocational University，Suzhou 215104，China)

Through the analysis of city bus routes，this paper intends to improve the practice over the approach of Dijkstra by putting forward a mode in determining the shortest or optimal route in terms of distance，expenditure and time allowing for different requirements from the passengers. This mode and algorithm is proved to be rational and practical by numerical examples.

public transport；Dijkstra algorithms；optimal route

O141.4

A

1008-5475(2014)04-0058-04

2014-08-20；

2014-09-18

蘇州市職業(yè)大學(xué)研究性課題(SZDYKC-140901)

王 慶(1979-)，男，江蘇揚(yáng)州人，副教授，碩士，主要從事應(yīng)用數(shù)學(xué)研究.