Floyd算法在公交線(xiàn)路優(yōu)化中的應(yīng)用

王防修，周 康，同小軍

(武漢工業(yè)學(xué)院數(shù)理科學(xué)系，湖北武漢430023)

Floyd算法在公交線(xiàn)路優(yōu)化中的應(yīng)用

王防修，周 康，同小軍

(武漢工業(yè)學(xué)院數(shù)理科學(xué)系，湖北武漢430023)

以城市交通優(yōu)化問(wèn)題為例，研究了網(wǎng)絡(luò)交通優(yōu)化問(wèn)題的數(shù)學(xué)模型。在已有Floyd算法的基礎(chǔ)上提出了改進(jìn)的Floyd算法，該算法能夠有效地解決多權(quán)網(wǎng)絡(luò)交通優(yōu)化問(wèn)題。以北京市公交為例，建立了多權(quán)交通網(wǎng)，討論了從出發(fā)點(diǎn)A站到目的地B站的最優(yōu)路線(xiàn)查詢(xún)問(wèn)題，運(yùn)用Floyd算法建立該問(wèn)題的數(shù)學(xué)模型。通過(guò)實(shí)例應(yīng)用，進(jìn)一步證明了該算法和模型的可行性和合理性。

最優(yōu)線(xiàn)路;賦權(quán)有向圖;Floyd算法;多權(quán)交通網(wǎng);交通優(yōu)化

隨著社會(huì)的發(fā)展，最優(yōu)線(xiàn)路問(wèn)題成為研究交通問(wèn)題中的一個(gè)重要問(wèn)題，在解決公交最佳出行線(xiàn)路、城市援救最佳線(xiàn)路、物流配送、高速公路聯(lián)網(wǎng)收費(fèi)等與人們?nèi)粘Ｉ蠲芮邢嚓P(guān)問(wèn)題中發(fā)揮著重要的作用。這些年來(lái)，城市的交通系統(tǒng)有了很大發(fā)展，為公眾的出行以及進(jìn)行各項(xiàng)日常活動(dòng)帶來(lái)了很大的便利，但同時(shí)也面臨著多條線(xiàn)路的選擇問(wèn)題。所以建立交通中最優(yōu)線(xiàn)路問(wèn)題的數(shù)學(xué)模型，為人們進(jìn)行日?；顒?dòng)提供參考有很大的價(jià)值，是一個(gè)值得研究的課題。

建立交通中最優(yōu)線(xiàn)路問(wèn)題數(shù)學(xué)模型的目的就是尋找最優(yōu)路徑，為公眾做出出行決策提供參考。目前關(guān)于最佳出行線(xiàn)路問(wèn)題的研究主要是一些傳統(tǒng)算法和根據(jù)問(wèn)題的特點(diǎn)對(duì)傳統(tǒng)算法進(jìn)行改造。具有代表性的有 Dijkstra算法、Floyd算法、Bellman算法［1］;Angelica Lozano［2］研究了標(biāo)號(hào)修正技術(shù)在綜合運(yùn)輸網(wǎng)絡(luò)中求解起點(diǎn)到終點(diǎn)的最短可行路徑;Paola Modesti等［3］針對(duì)最小出行時(shí)間研究了求解綜合運(yùn)輸網(wǎng)絡(luò)最短路徑問(wèn)題，使用多標(biāo)記圖構(gòu)建運(yùn)輸網(wǎng)絡(luò)和對(duì)應(yīng)的數(shù)據(jù)，并提出了求解算法。但這些已有的算法都不能解決出行線(xiàn)路雙向選擇、環(huán)形出行線(xiàn)路和多權(quán)問(wèn)題，因此需要一種新的算法來(lái)建立交通中最優(yōu)線(xiàn)路問(wèn)題的數(shù)學(xué)模型。

1 最優(yōu)線(xiàn)路的定義及評(píng)價(jià)指標(biāo)

所謂最優(yōu)線(xiàn)路是指從起始位置到目的地的最優(yōu)行走路徑或方案［4］。

最優(yōu)線(xiàn)路的評(píng)價(jià)指標(biāo)［5］有很多，其中主要有最短距離法、最短時(shí)間法以及某些特定要求(如沿途風(fēng)景足夠多等)。針對(duì)不同的人群及要求，所選擇的評(píng)價(jià)指標(biāo)包括如下幾種。

1.1 最短路徑

所謂最短路徑是指在起始站點(diǎn)到目的地的所有可能線(xiàn)路中尋求距離最短的一條線(xiàn)路作為最優(yōu)出行線(xiàn)路。

1.2 最少換乘車(chē)次

換乘車(chē)次是指乘客完成一次出行過(guò)程所需的換乘次數(shù)，次數(shù)的多少是衡量出行線(xiàn)路的最優(yōu)與否的又一關(guān)鍵因素，若換乘次數(shù)較多，出行者會(huì)放棄對(duì)公交的選擇，轉(zhuǎn)向其他更快捷的方式。此外在同一票價(jià)的公交運(yùn)營(yíng)體制下，換乘次數(shù)的增加也意味著票價(jià)消費(fèi)的增加，理想的出行線(xiàn)路應(yīng)該保證在最少的換乘次數(shù)的前提下達(dá)到目的地。大量實(shí)際調(diào)研表明，最優(yōu)出行換乘次數(shù)不應(yīng)超過(guò)3次［6］。

1.3 最低票價(jià)消費(fèi)

一般來(lái)說(shuō)，乘客從起始站點(diǎn)到達(dá)目的地可選擇的交通工具有多種，途徑也不是唯一的，最低票價(jià)消費(fèi)即要求滿(mǎn)足保證乘客到達(dá)目的地條件下所有票價(jià)總和最小。

2 最優(yōu)線(xiàn)路評(píng)價(jià)指標(biāo)的量化

2.1 最短出行線(xiàn)路的量化

記Si為出行的起始點(diǎn)，Sj為所要到達(dá)的目的地，Dij表示從Si到Sj所有可能路線(xiàn)的距離，dij為從起始站Si到終點(diǎn)站Sj的第k條線(xiàn)路上相鄰兩站點(diǎn)的距離，則按照第k條線(xiàn)路行駛的總距離為：

而最短路徑即為所有可能行駛線(xiàn)路距離的最小值，即：

其中，k0為從Si到Sj所有可能線(xiàn)路中按最短距離所選的最優(yōu)線(xiàn)路。

2.2 最少換乘次數(shù)的量化

對(duì)乘客而言，從起始點(diǎn)Si到目的地Sj可乘坐的主要交通工具是公汽，而公汽又包括一票制和分段計(jì)價(jià)兩種不同方式。設(shè)從起始站Si到目的地Sj所有的可能線(xiàn)路有k條;用I、II表示乘坐單一票價(jià)、分段計(jì)價(jià)(1元票價(jià)、2元票價(jià)、3元票價(jià))這兩類(lèi)公交;Ekj表示第k條線(xiàn)路上公交之間的轉(zhuǎn)換次數(shù);δi為標(biāo)識(shí)函數(shù)，定義如下：

則從起始點(diǎn)Si到終點(diǎn)站Sj按第k條線(xiàn)路出行的換乘次數(shù)為：

最少換乘次數(shù)為：

其中，k0為起始點(diǎn)Si到終點(diǎn)站Sj所有可能線(xiàn)路中按最少換乘次數(shù)所選的最優(yōu)線(xiàn)路。

2.3 最低票價(jià)的量化

記Mij為從起始點(diǎn)Si到終點(diǎn)站Sj的票價(jià)消費(fèi)，由于從起始點(diǎn)到終點(diǎn)站的可選擇出行方式及線(xiàn)路有多種，如單一票價(jià)、分段計(jì)價(jià)，記cki為沿k號(hào)線(xiàn)路乘坐以上幾種公交的次數(shù)，δi為標(biāo)識(shí)函數(shù)(i=1，2，…，5)，且

則沿第k條線(xiàn)路出行的票價(jià)消費(fèi)為：

最低票價(jià)即為：

其中，k0為從起始點(diǎn)Si到終點(diǎn)站Sj的所有可能線(xiàn)路中按最少票價(jià)消費(fèi)所選的最優(yōu)線(xiàn)路。

3 Floyd算法

Floyd(弗洛伊德)算法［7-8］是一種矩陣(表格)迭代方法，對(duì)于求任意兩點(diǎn)間的最短路、混合圖的最短路、有負(fù)權(quán)圖的最短路等一般網(wǎng)絡(luò)問(wèn)題來(lái)說(shuō)均比較有效。

Floyd算法通過(guò)對(duì)表示有向圖的鄰接矩陣作疊代計(jì)算來(lái)解決有向圖任意一對(duì)頂點(diǎn)之間的最短路徑間題。Floyd算法不僅是建立在簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之上，而且就解決問(wèn)題的徹底性而言也是最完滿(mǎn)的。迄今為止，它僅僅是作為解決有向圖的最短路徑問(wèn)題的一個(gè)重要方法而被提及。實(shí)際上，F(xiàn)loyd算法與圖的許多重要性質(zhì)以及與圖論中其它一些重要問(wèn)題的解決有著密切的聯(lián)系。

3.1 Floyd算法的基本原理

Floyd算法的主要思想是從代表任意2個(gè)頂點(diǎn)vi到vj的距離的帶權(quán)鄰接矩陣開(kāi)始，每次插入一個(gè)頂點(diǎn)vk，然后將vi到vj間的已知最短路徑與插入頂點(diǎn)vk作為中間頂點(diǎn)(一條路徑中除始點(diǎn)和終點(diǎn)外的其他頂點(diǎn))時(shí)可能產(chǎn)生的vi到vj路徑距離比較，取較小值以得到新的距離矩陣。如此循環(huán)迭代下去，依次構(gòu)造出 n個(gè)矩陣 D(1)，D(2)，……D(n)，當(dāng)所有的頂點(diǎn)均作為任意2個(gè)頂點(diǎn)vi到vj中間頂點(diǎn)時(shí)得到的最后的帶權(quán)鄰接矩陣D(n)就反映了所有頂點(diǎn)對(duì)之間的最短距離信息，成為有n個(gè)頂點(diǎn)的圖G的距離矩陣。最后對(duì)G中各行元素求和并比較大小，決定最優(yōu)的路線(xiàn)。

3.2 Floyd算法構(gòu)造距離矩陣的原理

對(duì)一個(gè)有n個(gè)頂點(diǎn)的圖G，將頂點(diǎn)用n個(gè)整數(shù)(從1到n)進(jìn)行編號(hào)［9］。把G的帶權(quán)鄰接矩陣W作為距離矩陣的初值，即從圖的帶權(quán)鄰接矩陣W開(kāi)始，遞歸地進(jìn)行n次更新，即由矩陣D(0)=W，按一個(gè)公式構(gòu)造出矩陣D(1);又用同樣的公式由D(1)構(gòu)造出矩陣D(2);……最后又用同樣的公式由D(n－1)構(gòu)造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號(hào)頂點(diǎn)到j(luò)號(hào)頂點(diǎn)的最短路徑長(zhǎng)度，稱(chēng)D(n)為圖的距離矩陣，同時(shí)還可以引入一個(gè)路由矩陣path來(lái)記錄兩點(diǎn)間的最短路徑。

3.2.1 Floyd 算法步驟

d(i，j) ：d(k)ij.

path(i，j) ：對(duì)應(yīng)于 d(k)ij的路徑上i的后繼點(diǎn)，最終的取值為i到j(luò)的最短路徑上i的后繼點(diǎn)。

Step1：賦權(quán)值，對(duì)所有 i，j，d(i，j)=a(i，j);當(dāng)a(i，j)= μ時(shí)，path(i，j)=0 ，否則 path(i，j)=j;k=1。

Step2：更新 d(i，j) ，path(i，j) 對(duì)所有 i，j若d(i，k)+d(k，j) ≥ d(i，j) ，則轉(zhuǎn)入 step3，否則 d(i，j)=d(i，k)+d(k，j)，path(i，j)=path(i，k)，k=k+1;繼續(xù)執(zhí)行step3。

Step3：重復(fù)step2直到k=n+1。

迭代結(jié)束后得到最終的距離矩陣D(n)和路由矩陣path，根據(jù)距離矩陣D(n)可得任意兩點(diǎn)間的最短路長(zhǎng)度，根據(jù)路由矩陣path可得任意兩點(diǎn)間取最短路徑。

3.2.2 回溯法求最短路徑

已知路由矩陣P=(pij)n×n，利用回溯法求解點(diǎn)i與點(diǎn)j取最短路徑，若已知pij=k1，分別從點(diǎn)i和點(diǎn)j開(kāi)始回溯。

(a)從點(diǎn)i開(kāi)始回溯

pik1=k2，pik2=k3，…，pikr=kr.

(b)從點(diǎn)j開(kāi)始回溯

pk1j=q1，pq1j=q2，…，pqmj=j.

則從點(diǎn) i到點(diǎn) j的最短路徑為：i，kr，kr－1，…，k2，k1，q1，q2，…，qm，j。

3.3 Floyd 算法改進(jìn)

3.3.1 改進(jìn)Floyd算法原理

在原有的Floyd算法中，矩陣D(k)給出網(wǎng)絡(luò)中任意兩點(diǎn)直接到達(dá)，經(jīng)過(guò)一個(gè)、兩個(gè)、……到(2k－1)個(gè)中間點(diǎn)時(shí)比較得到的最短距離。一般地在計(jì)算過(guò)程中，由于 D(k)其中從1到n取值。當(dāng)n較大時(shí)，τ從1到n取值，比較之間的值取其最小，計(jì)算量大。

3.3.2 改進(jìn)Floyd算法的計(jì)算步驟

4 Floyd算法實(shí)例應(yīng)用

給出任意兩公汽站點(diǎn)之間線(xiàn)路選擇問(wèn)題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)［18］，利用我們的模型與算法，求出以下6對(duì)起始站→終到站之間的最佳路線(xiàn)(要有清晰的評(píng)價(jià)說(shuō)明)：S3359→S1828、S1557→S0481、S0971→S0485、S0008→S0073、S0148→S0485、S0087→S3676。

公汽換乘公汽平均耗時(shí)：5min(其中步行時(shí)間2 min)。

公汽票價(jià)：分為單一票價(jià)與分段計(jì)價(jià)兩種，標(biāo)記于線(xiàn)路后;其中分段計(jì)價(jià)的票價(jià)為：0—20站1元;21—40站2元;40站以上3元

該問(wèn)題是一個(gè)多目標(biāo)最優(yōu)模型，可以根據(jù)對(duì)時(shí)間、轉(zhuǎn)乘次數(shù)和車(chē)費(fèi)的不同要求來(lái)選擇最優(yōu)線(xiàn)路。根據(jù)實(shí)際情況知，轉(zhuǎn)車(chē)次數(shù)越多，所經(jīng)過(guò)的站點(diǎn)數(shù)越多，相應(yīng)的耗時(shí)也會(huì)越長(zhǎng)，根據(jù)對(duì)乘客出行心里調(diào)查知，大多數(shù)乘客將轉(zhuǎn)乘次數(shù)最少作為首要考慮因素，因此在本問(wèn)題中求解出了轉(zhuǎn)乘次數(shù)為一次和兩次的情況，并記錄每條線(xiàn)路所經(jīng)過(guò)的總站點(diǎn)數(shù)，在根據(jù)不同的要求選擇一條最優(yōu)線(xiàn)路。

從表1可知，從S3359→S1828站中間換乘一次的乘車(chē)方式有9種，首先考慮費(fèi)用最少，最少費(fèi)用的乘車(chē)方案總共有8條，在該8條乘車(chē)線(xiàn)路中再考慮所經(jīng)過(guò)的總站點(diǎn)數(shù)，選擇一條最優(yōu)線(xiàn)路。最優(yōu)線(xiàn)路為：由S3359乘坐L469車(chē)次上行線(xiàn)路經(jīng)29站到達(dá)S0304，再轉(zhuǎn)乘 L167車(chē)次下行線(xiàn)路經(jīng) 1站到達(dá)S1828，費(fèi)用為3元，總共經(jīng)過(guò)32站到達(dá)。其它線(xiàn)路依次類(lèi)推。

表1 S3359→S1828中轉(zhuǎn)一站的乘車(chē)路線(xiàn)

從S1557→S0481站中間換乘兩次的乘車(chē)方式總共有128種，表2中列出了其中的10種乘車(chē)方式，綜合考慮乘車(chē)費(fèi)用最少且經(jīng)過(guò)的總站數(shù)少，從中選擇一條最優(yōu)線(xiàn)路。最優(yōu)線(xiàn)路為：由S1557乘坐L084車(chē)次下行線(xiàn)路經(jīng)12站到達(dá) S1919，再轉(zhuǎn)乘L189車(chē)次下行線(xiàn)路經(jīng)3站到達(dá)S3186，再轉(zhuǎn)乘L460車(chē)次環(huán)形線(xiàn)路經(jīng)17站到達(dá)S0481，總費(fèi)用為3元，總共經(jīng)過(guò)32站到達(dá)。其它線(xiàn)路依次類(lèi)推。

表2 S1557→S0481中轉(zhuǎn)兩站的乘車(chē)線(xiàn)路(部分路線(xiàn))

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

本文主要利用Floyd算法解決一個(gè)實(shí)際問(wèn)題。首先提出問(wèn)題，在利用前面講到的Floyd算法對(duì)提出的問(wèn)題求解，做到了將理論應(yīng)用于解決實(shí)際問(wèn)題，為人們的方便出行帶來(lái)參考。

［1］ 王杰.基于分層網(wǎng)絡(luò)模型的單一訖(不同)點(diǎn)物流運(yùn)送路徑優(yōu)化研究［D］.北京：北京交通大學(xué)，2002.

［2］ Angelica Lozano，Giovanni Storchi.Shortest viable path algorithm in multimodal networks［J］.Transportation Research.Part A 2001，35：225-241.

［3］ Paola Modesti，Anna Sciomachen.A utility measure for finding multimodal transportation networks［J］.European Journal of Operational Research.1998，111：495-508.

［4］ 許谷聲，陳逸群，王解先，等.結(jié)合最優(yōu)信息的路徑搜索［J］.測(cè)繪工程，1998(4)：44-47.

［5］ 魏峰，夏小剛，張守剛，等.公交最優(yōu)出行線(xiàn)路的一個(gè)模型及算法［J］.交通標(biāo)準(zhǔn)化，2008(6)：155-157.

［6］ 朱德通.最優(yōu)化模型與實(shí)驗(yàn)［M］.上海：同濟(jì)大學(xué)出版社，2003.

［7］ 米涅卡，李家瀅，趙關(guān)旗.網(wǎng)絡(luò)和圖的最優(yōu)化算法［M］.北京：中國(guó)鐵道出版社，1984.

［8］ 錢(qián)項(xiàng)迪，運(yùn)籌學(xué)［M］.北京：清華大學(xué)出版社，1990.

［9］ 趙靜，但琦.數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)［M］.北京：高等教育出版社，2000.

Applying Floyd algorithm to optimize bus lines

WANG Fang-xiu，ZHOU Kang，TONG Xiao-jun
(Department of Mathematics and Physics，Wuhan Polytechnic University，Wuhan 430023，China)

Urban traffic optimization problem is put forward and the network traffic optimization mathematical model is studied.The paper proposes the improvement on Floyd algorithm.The algorithm can effectively solve the network traffic optimization problem.Finally，with Beijing traffic as an example，this paper sets up a multi－ weight traffic network.The optimal route is discussed from the point station A to the destination station B.At the same time，it establishs the mathematical model of the problem through Floyd algorithm.Further，it proves the feasibility and rationality of the model and the algorithm by an application example.

best routes;empowering directed graph;Floyd algorithm;multi－weight traffic network;traffic optimization

TP 301.6

A

1009-4881(2011)03-0037-06

10.3969/j.issn.1009-4881.2011.03.010

2011-01-13

王防修(1973－)，男，碩士，講師，E －mail：wfx323@126.com.

國(guó)家自然科學(xué)基金資助項(xiàng)目(60574041).