基于Floyd算法的中小城鎮(zhèn)環(huán)境公交線網(wǎng)優(yōu)化

陳 彥, 胡曉軍，盧 川，何帥龍

(1.合肥學(xué)院生物與環(huán)境工程系，安徽 合肥 230601；2.合肥學(xué)院建筑工程系，安徽 合肥 230601；3.安徽省交通規(guī)劃設(shè)計(jì)研究院規(guī)劃分院，安徽 合肥 230088)

公交線網(wǎng)布局方法大體是對(duì)城市開展的，對(duì)中小城鎮(zhèn)關(guān)注的較少。又中小城鎮(zhèn)具有公交線路少，長(zhǎng)度短，乘客出行量小的交通環(huán)境[1]。若線路布設(shè)不恰當(dāng)，便會(huì)降低路網(wǎng)的運(yùn)載能力，損失客流。所以，對(duì)中小城鎮(zhèn)公交線網(wǎng)優(yōu)化布局研究有較強(qiáng)的現(xiàn)實(shí)作用。

在公交線網(wǎng)優(yōu)化研究上，文獻(xiàn)[2-3]均是以改進(jìn) Dijkstra 算法為手段，來確定備選線路的最佳走向；文獻(xiàn)[4]提出了以直達(dá)客流最大為目標(biāo)的公交優(yōu)化模型；文獻(xiàn)[5]以乘客時(shí)間與企業(yè)成本之和最低為目標(biāo)，運(yùn)用改進(jìn)的模擬退火算法，消除不同線路的站點(diǎn)重復(fù)；文獻(xiàn)[6]建立了規(guī)劃階段公交線網(wǎng)空間可達(dá)性的優(yōu)化模型，并用遺傳算法求解；文獻(xiàn)[7]考慮首末站布局位置為約束，基于遺傳算法求解可達(dá)性與可達(dá)強(qiáng)度的優(yōu)化模型；文獻(xiàn)[8]同步優(yōu)化線網(wǎng)與發(fā)車頻率，建立混合整數(shù)規(guī)劃模型，比較換乘比與設(shè)定的下界值，設(shè)計(jì)改進(jìn)遺傳算法求解；文獻(xiàn)[9]基于公交客流時(shí)空的不均衡性，建立以人均舒適度最大為目標(biāo)的公交線網(wǎng)優(yōu)化模型；文獻(xiàn)[10]以尋求客運(yùn)成本最低為目標(biāo)，建立了啟發(fā)式方法優(yōu)化網(wǎng)絡(luò)；文獻(xiàn)[11]基于遺傳算法，通過最小化的改變路網(wǎng)走向，來運(yùn)輸系統(tǒng)中的交通量；文獻(xiàn)[12]運(yùn)用累積前景理論對(duì)城市公交網(wǎng)絡(luò)進(jìn)行優(yōu)化。文獻(xiàn)[13]提出了“逐條布設(shè)、優(yōu)化成網(wǎng)”的方法，即用最短路徑確定線路走向，以直達(dá)客流量最大為目標(biāo)，逐條增設(shè)線路到網(wǎng)絡(luò)中的一種線網(wǎng)布設(shè)方法。

通過上述對(duì)公交線網(wǎng)的相關(guān)研究，可以發(fā)現(xiàn)研究基于不同的優(yōu)化目標(biāo)，目標(biāo)可分為乘客、企業(yè)層次的優(yōu)化及二者并重的雙目標(biāo)優(yōu)化，選取不同的約束條件(公交線網(wǎng)覆蓋率、線路重復(fù)系數(shù)、換乘比例、線網(wǎng)長(zhǎng)度等)，建立不同的模型目標(biāo)函數(shù)，最后采用不同的算法，得出與模型設(shè)定相吻合的最優(yōu)解，很難實(shí)現(xiàn)全局最優(yōu)。

針對(duì)中小城鎮(zhèn)的公交線網(wǎng)的規(guī)劃布局中，從選定起訖點(diǎn)到布線，均是在站點(diǎn)與站點(diǎn)之間的布設(shè)。本文考慮在站點(diǎn)之間設(shè)立一個(gè)新的插入點(diǎn)，結(jié)合路網(wǎng)的公交乘客出行OD(起終點(diǎn)間的交通出行量)，以直達(dá)乘客最大化為目標(biāo)，基于Floyd算法確定公交線路具體走向，優(yōu)化了線網(wǎng)布局，提高了公交對(duì)客流的運(yùn)輸效果，方法簡(jiǎn)單實(shí)用，可操作性強(qiáng)。

1 Floyd算法

Floyd算法是一種用于尋找給定的加權(quán)圖中任意兩個(gè)頂點(diǎn)間最短路徑的算法[14]，邊權(quán)可正可負(fù)。

設(shè)立權(quán)矩陣D，其中

算法步驟：

1)輸入權(quán)矩陣D(0)=D；

假設(shè)各節(jié)點(diǎn)間的公交行駛時(shí)間如圖1所示。

圖1 某道路節(jié)點(diǎn)間行駛時(shí)間圖

由上述可得到其相應(yīng)的鄰接矩陣D如下

矩陣D中元素dij(i，j=1，2，…，7)為節(jié)點(diǎn)vi到vj的距離，其中dij=∞為節(jié)點(diǎn)間無路徑。此處直接編程計(jì)算分析。輸入鄰接矩陣D，可輸出各節(jié)點(diǎn)之間最短路徑值矩陣D1和最短路徑矩陣D2。

由輸出的矩陣D1和D2可得任一點(diǎn)的最短路徑值和最短路徑，比如V1到V7的最短路徑值為13，最短路徑為V1→V2→V3→V5→V6→V7。文章基于逐條布設(shè)、優(yōu)化成網(wǎng)方法，并假設(shè)在本次所選取的小城鎮(zhèn)中，各斷面流量均小于斷面運(yùn)載能力。考慮工程實(shí)際情況，線網(wǎng)中存在尚未運(yùn)輸客流，通過插入節(jié)點(diǎn)法，來提高線網(wǎng)的直達(dá)乘客量，從而增大了線網(wǎng)的不換乘比，對(duì)中小城鎮(zhèn)線網(wǎng)如何優(yōu)化布設(shè)有一定參考。

2 案例分析

圖2為某小城鎮(zhèn)的交通分區(qū)及道路網(wǎng)絡(luò)，路網(wǎng)數(shù)據(jù)為公交車行駛時(shí)間，乘客O-D量如表1所示。

圖2 某中小城鎮(zhèn)交通分區(qū)與路網(wǎng)示意圖

起點(diǎn)終點(diǎn)ABCDEFGHISUM A85352706246189465938421 721 B38633480204104544544701 350 C54450282502112687446601 930 D65850648636180584256822 022 E1881201241362468768042816 F38561011066818765432517 G1207886886265267053595 I426863353637466218389 SUM2 1171 7682 1731 4138034404644734499 651

由表1可知，以A、B、C、D為起訖點(diǎn)，擬設(shè)2條雙向線路。其余E、F、G、H、I為重要節(jié)點(diǎn)。

2.1 備選線路的最佳走向及直達(dá)乘客量

由于是第一條線路，故不對(duì)行駛時(shí)間復(fù)線修正。線路按最短行駛時(shí)間布設(shè)。輸入相應(yīng)的鄰接矩陣D，由軟件生成結(jié)果，采用反向追蹤法，同時(shí)，對(duì)直達(dá)乘客量矩陣修正?？傻酶鱾溥x路線起終點(diǎn)間的公交線路情況，如表2所示。

表2 各備選路線起終點(diǎn)間的公交線路

2.2 優(yōu)化線路的布設(shè)及乘客O-D量修正

直達(dá)乘客量矩陣修正后，得出備選線路的最大直達(dá)乘客量Zij+Zji值，取直達(dá)乘客最大化線路為公交網(wǎng)絡(luò)中的線路，按最短路線布線。

在選中的區(qū)域中，ZBC+ZCB=2 015，為各備選線路中的最大直達(dá)乘客量，故取B→C、C→B為公交線路，并按其最短線路5→4→9→14→13→12→17→16→21布線。

根據(jù)[Zij+Zji]max來設(shè)置公交線路[i，j]后，基于前述假設(shè)，線路上客流均被全部輸送，則在原乘客O-D矩陣中，去除該線路運(yùn)載的O-D量，對(duì)其進(jìn)行第一次修正。

2.3 復(fù)線系數(shù)

公交線路布設(shè)后，對(duì)行駛時(shí)間進(jìn)行修正[15]，即乘以復(fù)線系數(shù)K0。本次擬用復(fù)線系數(shù)以50%的比例求解。即若復(fù)線條數(shù)為1，則復(fù)線系數(shù)取1.5；復(fù)線條數(shù)為2時(shí)，取2.25，以此類推。具體復(fù)線系數(shù)取值，可結(jié)合具體工程項(xiàng)目作調(diào)整。

此時(shí)，只剩下A→D、D→A兩對(duì)起終點(diǎn)，故設(shè)線路A→D、D→A為公交線路，具體的線路走向?yàn)?→6→7→8→13→18→19→24→25。

線路直達(dá)乘客量ZAD+ZDA=550+892=1 442。各斷面流量均由該線路全部運(yùn)送，可得相應(yīng)的第二次修正的乘客O-D矩陣如表3所示。

表3 第二次修正的乘客O-D矩陣

2.4 路線布設(shè)方案對(duì)比

顯然，由表3可以看出，乘客O-D矩陣中存在潛在的客流量，此處增設(shè)兩條線路：第三條線路A→E、E→A，第四條線路B→C、C→B。在已設(shè)有線路的路段上，對(duì)其行駛時(shí)間進(jìn)行修正，且各斷面的流量均小于運(yùn)載能力，全部被運(yùn)送。對(duì)修正后的公交車行駛時(shí)間矩陣，運(yùn)用Floyd算法，編程計(jì)算分析，輸出各點(diǎn)之間的最短路徑值和最短路徑。為方便乘客的出行，追求運(yùn)送人流量最大化。此處，對(duì)比以下兩種方案。方案一：以最短路徑進(jìn)行布設(shè)線路；方案二：在起終點(diǎn)間添加合理節(jié)點(diǎn)，對(duì)線路稍作調(diào)整，以起點(diǎn)→插入點(diǎn)，插入點(diǎn)→終點(diǎn)之間最短路徑布線。

1)以各節(jié)點(diǎn)之間為最短路徑為備選路線

由軟件運(yùn)行結(jié)果可得， A→E(或E→A)的最短路徑值為356， 最短路徑為1-2-7-12-17-22-23。得出， 線路直達(dá)乘客量ZAE+ZEA=399+377=776。B→C(或C→B)的最短路徑值為470，最短路徑為5→10→15→20→19→18→23→21。該線路直達(dá)乘客量ZBC+ZCB=228+232=460。

2)對(duì)線路稍作調(diào)整作為備選路線

綜上所述，將兩種方式的結(jié)果進(jìn)行對(duì)比，如表4所示。

表4 兩種方案結(jié)果對(duì)比匯總

顯然，在合理的范圍內(nèi)，對(duì)線路進(jìn)行調(diào)整，對(duì)運(yùn)送人流量的最大化有影響，方案二對(duì)路線稍作調(diào)整，提高公交車的實(shí)際運(yùn)載量，不換乘比增大，達(dá)到優(yōu)化線網(wǎng)的作用。所以，在實(shí)際項(xiàng)目工程中，不能局限于嚴(yán)格的按照最短路徑來選取備選線路，可稍作調(diào)整線路，避免損失客流，出現(xiàn)車輛運(yùn)載效用不高，居民出行得不到改善等情況。最終得出公交路線的走向，如圖3所示。

圖3 公交網(wǎng)絡(luò)優(yōu)化圖

3 結(jié)論

(1)本文在選取最短路徑為備選方案時(shí)，引入了Floyd算法，并使用MATLAB R2016a進(jìn)行編程求解，最終得到公交優(yōu)化方案，在追求直達(dá)客流最大的目標(biāo)下，盡可能的采取最短路徑，提高實(shí)際直達(dá)乘客量、減小乘客的換乘比例。

(2)在實(shí)際的中小城鎮(zhèn)公交線網(wǎng)優(yōu)化的過程中，可打破以往站點(diǎn)與站點(diǎn)之間的布設(shè)線路，避免一味的追求最短路徑，在點(diǎn)與點(diǎn)中插入一個(gè)節(jié)點(diǎn)來調(diào)整線路走向，使得線路走向與客流走向更加相一致，優(yōu)化公交線網(wǎng)布局，為推進(jìn)中小城鎮(zhèn)公交線網(wǎng)優(yōu)化提供有益參考。