基于改進(jìn)網(wǎng)絡(luò)最大流的道路通行能力優(yōu)化研究

廖 曄，王順意

(1.永州職業(yè)技術(shù)學(xué)院 建筑工程系，湖南 永州 422500；2.西南交通大學(xué) 土木工程學(xué)院，四川 成都 610031)

近年來，隨著城市化進(jìn)程的不斷加快，城市路網(wǎng)結(jié)構(gòu)愈趨復(fù)雜，對(duì)城市路網(wǎng)結(jié)構(gòu)的定量研究及優(yōu)化改造具有重要意義[1]，與此同時(shí)，網(wǎng)絡(luò)最大流理論被廣泛應(yīng)用于軍事運(yùn)輸、物資調(diào)度路徑優(yōu)化等諸多行業(yè)領(lǐng)域[2-4]。

當(dāng)前，國(guó)內(nèi)外學(xué)者基于網(wǎng)絡(luò)最大流理論展開了一定的研究，部分學(xué)者建立了相關(guān)優(yōu)化模型。卜祥濤[5]從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)最大流、網(wǎng)絡(luò)巧撲結(jié)構(gòu)和網(wǎng)絡(luò)交通流相結(jié)合2個(gè)角度，提出路網(wǎng)新增路段對(duì)交通網(wǎng)絡(luò)性能影響的度量指標(biāo)。郭波等[6]以兩源單匯網(wǎng)絡(luò)為例，在資源到達(dá)終點(diǎn)所需時(shí)間最短約束下，研究、計(jì)算最短傳輸時(shí)間的上下界。詹雯[7]基于改進(jìn)標(biāo)號(hào)算法建立網(wǎng)絡(luò)增廣鏈的最優(yōu)路徑選擇模型。高明霞等[8]通過尋找網(wǎng)絡(luò)最大流增流關(guān)鍵邊、次關(guān)鍵邊等，確定路網(wǎng)中實(shí)行逆向車道管理的備選路段。李運(yùn)等[9]結(jié)合設(shè)置優(yōu)先通行規(guī)則與最小費(fèi)用最大流算法，實(shí)現(xiàn)有交通沖突情況下的交通流分配。

另有部分學(xué)者設(shè)計(jì)了新的計(jì)算方法。栗雪娟[10]系統(tǒng)分析和研究圖論中求解路網(wǎng)最大流的各種算法、適用條件和優(yōu)缺點(diǎn)。李玉蘭等[11]借助圖論中最大流最小割定理，給出了路網(wǎng)容量的計(jì)算方法。楊曉萍等[12]以網(wǎng)絡(luò)極大流為基礎(chǔ)，建立了理性條件下城市道路網(wǎng)容量的計(jì)算模型。孫同江等[13]采用Petri網(wǎng)論法和計(jì)算機(jī)圖形仿真法相結(jié)合的方法求解了運(yùn)輸網(wǎng)絡(luò)最大流。蘇鎮(zhèn)洪等[14]采用圖論的多端最大流算法和衍生割集算法，研究了道路網(wǎng)絡(luò)容量的計(jì)算方法。何家莉等[15]建立了道路最大平均流量的計(jì)算方法，并采用小生境混合遺傳算法進(jìn)行了求解。胡適軍等[16]針對(duì)網(wǎng)絡(luò)流割樹法的局限性，結(jié)合船舶流特點(diǎn)，給出了水網(wǎng)航道交通容量的計(jì)算方法。李冬梅等[17]探討了道路路段的通行能力和交叉口的通行能力的計(jì)算方法。羅文等[18]針對(duì)多約束變?nèi)萘織l件下的應(yīng)急物資調(diào)度問題，構(gòu)建了基于幾何代數(shù)的條件約束最大流分析模型；

上述研究成果針對(duì)路網(wǎng)容量、路徑優(yōu)化進(jìn)行了初步研究，但是鮮少全面考慮道路通行能力及其優(yōu)化改造。本文建立了一種改進(jìn)的網(wǎng)絡(luò)最大流模型。首先，基于最基本的網(wǎng)絡(luò)最大流模型計(jì)算道路最大通行能力；然后，考慮通行的道路選擇性，建立最短路模型，計(jì)算各個(gè)單源到各個(gè)單匯的最短路徑并通過A*算法篩選出有效路徑；進(jìn)而，利用最短路模型結(jié)果加強(qiáng)原模型中的約束條件，利用單純形法求解實(shí)際最大通行能力；最后，建立以道路擴(kuò)寬成本最低為目標(biāo)函數(shù)的線性規(guī)劃模型對(duì)道路進(jìn)行改造。

1 問題背景

某校園占地約3000畝，按照“一軸二帶三環(huán)六區(qū)”的規(guī)劃骨架，由南至北，逐步展開。該校區(qū)一共有5萬人，早上從宿舍區(qū)趕往各教學(xué)樓、實(shí)驗(yàn)樓及圖書館的人絡(luò)繹不絕。那么，現(xiàn)有校園道路設(shè)計(jì)規(guī)劃的最大通行能力多大，能否滿足學(xué)生及時(shí)趕往教學(xué)區(qū)，如果要將通行能力增加30%，應(yīng)如何改造校園道路。

現(xiàn)已有校園平面圖，通過對(duì)該校園的道路狀況進(jìn)行簡(jiǎn)化、標(biāo)記等處理，將某一集中區(qū)域簡(jiǎn)化為一點(diǎn)，道路簡(jiǎn)化為一條線，并且根據(jù)網(wǎng)絡(luò)地圖測(cè)距測(cè)量出各點(diǎn)距離與道路寬度，簡(jiǎn)化圖如圖1所示。圖1中，△代 表源，□代表匯，○代表路中支點(diǎn)，線上數(shù)字代表道路長(zhǎng)度，單位為m。各道路寬度d如表1所示。

圖1 道路簡(jiǎn)化圖Figure 1 Road simplification map

表1 道路寬度表Table 1 Road width table m

明顯的，問題中的道路最大通行能力屬于多起點(diǎn)(O點(diǎn))、多終點(diǎn)(D點(diǎn))網(wǎng)絡(luò)最大流問題。首先可以考慮建立一個(gè)基本的網(wǎng)絡(luò)最大流規(guī)劃模型，利用標(biāo)號(hào)法進(jìn)行求解；由于行人往往會(huì)選擇較短路徑進(jìn)行通行，并且在出發(fā)前已有固定的目的，于是可以將每個(gè)單源到單匯分開考慮，利用最短路模型選擇出兩者間較短的有效路徑；最后在初始模型的基礎(chǔ)上再次增加約束條件，利用單純形法進(jìn)行求解。

2 改進(jìn)網(wǎng)絡(luò)最大流模型建立

2.1 道路飽和流量計(jì)算

由于已知校園內(nèi)道路分布簡(jiǎn)化圖，設(shè)各道路飽和流量為Cij，則有

其中，dij為每條道路的寬度，v為學(xué)生行駛的平均速度，S0為每人占地的平均面積。

由于南北區(qū)離每一教學(xué)區(qū)的距離各不相同，學(xué)生采取的行駛方式也會(huì)有異，一般采取騎自行車與步行2種行駛方式。查找資料可知，正常步行速度為1 m/s，正常的自行車行駛速度為3 m/s，再根據(jù)假設(shè)，步行與騎自行車的學(xué)生人數(shù)相同，可得

即可得各道路飽和流量為

可知各道路飽和流量如表2所示。

表2 道路飽和流量Table 2 Road saturation flowmeter 人/s

2.2 基于網(wǎng)絡(luò)最大流的線性規(guī)劃模型

對(duì)于基本的網(wǎng)絡(luò)最大流問題，一般可以通過線性規(guī)劃求解。因此，首先建立起基于網(wǎng)絡(luò)最大流的線性規(guī)劃模型。

由于規(guī)劃設(shè)計(jì)圖中的交通網(wǎng)絡(luò)較為復(fù)雜，為了方便與合理分配流量，此處將整個(gè)交通體系利用網(wǎng)絡(luò)流原理進(jìn)行求解。即交通網(wǎng)絡(luò)有向流為：

其中，X是頂點(diǎn)集，A為 有向弧集，C為有向管道容量集，即C={cij}。網(wǎng)絡(luò)上的流，是指定義在弧集合A上 的一個(gè)函數(shù)f={f(vi,vj)}，并稱fij為弧(vi,vj)上的流量。

1) 目標(biāo)函數(shù)。

整個(gè)區(qū)域的流量取決于所有出發(fā)點(diǎn)的通行人數(shù)總和，即所求的網(wǎng)絡(luò)流f的流值。

為求得最大通行能力，即要求得最大流值，因而可以確定目標(biāo)函數(shù)為

2) 約束分析。

① 人流量守恒約束。

對(duì)于整個(gè)區(qū)域來說，出行人數(shù)在通行中不會(huì)增加或減少，即人流量始終滿足于一個(gè)動(dòng)態(tài)守恒狀態(tài)。因此，出發(fā)處人流量始終等于匯集處人流量。據(jù)此，可得約束條件

② 節(jié)點(diǎn)平衡約束。

對(duì)于任意中間點(diǎn)，流入量等于流出量，即對(duì)于每一個(gè)i(is,t)有

③ 道路通行容量約束。

受道路寬度限制，每條道路的通行容量是有限度的，且不同道路的通行容量存在著差別。因此，在實(shí)際中，每條道路的通行容量不能大于其最大容量。因此，對(duì)于每一條弧 (vi,vj)∈A，可得約束條件為0 ≤fij≤cij。

3) 模型確定。

綜上目標(biāo)函數(shù)和約束條件的分析可以得到基于網(wǎng)路最大流的線性規(guī)劃模型為

2.3 最短路模型

給定一個(gè)賦權(quán)有向圖，即給定了一個(gè)有向圖D=(X;A;C)，對(duì)于每一個(gè)弧a=(vi,vj) ，相應(yīng)地有權(quán)w(a)=wij，又給定D中的2個(gè)頂點(diǎn)vs,vt。 設(shè)P是D中從vs到vt的一條路，定義路P的權(quán)是P中所有弧的權(quán)之和，記為w(P)。 最短路問題就是要在所有從vs到vt的路中，求一條權(quán)最小的路，即其求一條從vs到vt的路P0，使

當(dāng)然，在通行過程中，并不會(huì)每人都選擇最短的路，因此假設(shè)從某源到某匯的過程中，學(xué)生只會(huì)選擇與最短路徑相差30%的路，即可行路徑滿足

2.4 道路最大通行能力改進(jìn)模型

一般情況下，學(xué)生去教學(xué)區(qū)并不是漫無目的的出發(fā)，而是身在第k個(gè)源的學(xué)生只想到達(dá)第l個(gè)匯。假設(shè)在交通流中，從第k個(gè)源到第l個(gè)匯的人數(shù)與總?cè)藬?shù)的比例是一個(gè)確定值Ckl，則有

則目標(biāo)函數(shù)為

在實(shí)際交通流中，由于源與匯的數(shù)量較多，某些道路會(huì)出現(xiàn)雙向通行的情況，對(duì)此，本文在原模型的基礎(chǔ)上，采取分別討論各源到各匯的通行情況的方法，對(duì)原模型中的約束條件進(jìn)行了改進(jìn)。

由于道路可通行的雙向性，每條道路的流量為雙向通行流量之和，即有

則約束條件為

3 改進(jìn)網(wǎng)絡(luò)最大流模型求解

此模型為基于網(wǎng)絡(luò)最大流的線性規(guī)劃模型，查閱相關(guān)資料可知，常用的網(wǎng)絡(luò)最大流法有Ford-Fulkerson算法、Edmonds-Karp修正算法、dinic算法幾種。本文采用最常用的Ford-Fulkerson經(jīng)典算法。

Ford-Fulkerson算法采用深度優(yōu)先，其實(shí)質(zhì)是判斷是否有增廣鏈存在，并設(shè)法把增廣鏈找出來，即從一個(gè)可行流出發(fā)，不斷地經(jīng)歷標(biāo)號(hào)過程與調(diào)整過程。任意設(shè)定一初始可行流，結(jié)合該算法，并通過Matlab求解，可得到最大流如圖2所示。

根據(jù)圖2可以得到，在基于網(wǎng)絡(luò)最大流的線性規(guī)劃模型下，校園道路的最大通行能力為14+4+16+12=46人/s。

典型的最短路模型采用的算法為 Dijkstra 方法，其基本思想是用給節(jié)點(diǎn)記標(biāo)號(hào)來逐步形成起點(diǎn)到各點(diǎn)的最短路徑及其距離值。執(zhí)行過程中，與每個(gè)點(diǎn)對(duì)應(yīng)，記錄下一個(gè)數(shù)(稱為這個(gè)點(diǎn)的標(biāo)號(hào))，它表示從vs到該點(diǎn)的最短路的權(quán)(稱為P標(biāo)號(hào))，或者表示從vs到該點(diǎn)的最短路的權(quán)的上界(稱為T標(biāo)號(hào))，方法的每一步是去修改T標(biāo)號(hào)，并且把某一個(gè)具T標(biāo)號(hào)的點(diǎn)改變?yōu)榫逷標(biāo)號(hào)的點(diǎn)，從而使D中具P標(biāo)號(hào)的頂點(diǎn)數(shù)多一個(gè)，由此，至多經(jīng)過P-1步，即可求得從vs到各點(diǎn)的最短路。

對(duì)于可選擇路徑的篩選，為了增加求解效率，本文依次求出s到t的第k短的路徑，再與最短路徑的1.3倍作比較，直至第k短路超過路徑的1.3倍，停止循環(huán)。并通過A*算法依次求解出第k短路。

設(shè)起點(diǎn)為s；終點(diǎn)為t；對(duì)于一個(gè)點(diǎn)v，dt(v)表示從v走到t的最短路徑的長(zhǎng)度。一個(gè)狀態(tài)x表示的是從s走到某個(gè)點(diǎn)的一條路徑，把這個(gè)點(diǎn)記作x.v，把這條路徑的長(zhǎng)度記作x.len。接著，可以使用以下啟發(fā)函數(shù)

初始狀態(tài)中，x.v=s；x.len=0，每次讓優(yōu)先隊(duì)列中f(x)值最小的狀態(tài)x出隊(duì)，再根據(jù)圖2中所有從x.v出發(fā)的點(diǎn)發(fā)展下一層狀態(tài)，讓它們進(jìn)隊(duì)列。在每次出隊(duì)列的狀態(tài)x中，第一次遇到x.v=t時(shí)，就找到了從s到t的第一短的路徑，其長(zhǎng)度就是f(x)，第k次遇到x.v=t時(shí)，就找到了從s到t的第k短的路徑。

Dijkstra算法的具體流程框圖如圖3所示，根據(jù)其流程圖在Matlab環(huán)境中編寫程序，可得到各源到各匯的最短路徑與最短路長(zhǎng)，源2到匯18的最短路結(jié)果如圖4所示，粗實(shí)線代表可通行道路。

本文采取矩陣計(jì)算單純形法，在Matlab環(huán)境中求得在新的限制條件(只走較短路程)下的最大通行量，此時(shí)各道路的通行量如圖5所示。

在圖5中，各道路上的負(fù)數(shù)代表向相反方向通行的流量，單位為人/min。由此可得到，考慮到最短路徑以及雙向性后，最大通行能力為1380 人/min，即23人/s。

圖2 最大流通行示意圖Figure 2 Maximum flow chart

圖3 Dijkstra算法流程Figure 3 Dijkstraalgorithm flow chart

圖4 源2-匯18可通行道路Figure 4 Accessible road from source2 to collection18

圖5 道路通行量示意圖Figure 5 Road traffic flow diagram

此結(jié)果與原模型的結(jié)果相比通行量減少，這是由于“人們會(huì)選擇較短路徑”以及“出發(fā)前已具有特定的目的地”，說明本模型的建立較為成功，更加符合實(shí)際性。

該校區(qū)一共有5萬人，若5萬人都在外通行，在最大通行能力下，所需時(shí)間為36 min，屬于正常通行時(shí)間。即可知顯示道路設(shè)計(jì)能滿足學(xué)生及時(shí)通往教學(xué)區(qū)。

4 道路通行優(yōu)化改造

提高道路通行能力的方法有很多，可以增設(shè)道路、擴(kuò)寬道路寬度、改變學(xué)生出行方式與形式等。由于增設(shè)道路工程過于復(fù)雜，學(xué)生量過大導(dǎo)致改變學(xué)生出行方式的方法也不可取，所以本文主要考慮擴(kuò)寬道路寬度來提高通行能力。

問題要求改造校園道路使道路通行能力提高30%，要求在滿足道路通行能力提高的條件下，給出改造校園道路的最優(yōu)方案。為此，本文再次建立線性規(guī)劃模型，目標(biāo)函數(shù)及約束條件如下。

1) 目標(biāo)函數(shù)。

在通行能力提高量一定的情況下，道路的寬度也不能一味的擴(kuò)寬，所以此時(shí)的目標(biāo)為成本最低，在道路成本單價(jià)一定的情況下，將設(shè)為各條道路擴(kuò)寬道路后的面積之和，即

其中，yij為第i-j條道路的增加的寬度，lij為第ij條道路的長(zhǎng)度。

2) 約束分析。

與上述模型相似，約束條件存在節(jié)點(diǎn)平衡約束、源匯點(diǎn)平衡約束、道路容量限制，除此之外，還應(yīng)增加道路通行能力限制。根據(jù)上述模型求得最大通行能力為46人/s，即有

為滿足實(shí)際情況，可知在每個(gè)源處，流出量始終是大于流入量的，即

3) 模型確定。

綜上目標(biāo)和約束條件的分析可以得到基于網(wǎng)路最大流的線性規(guī)劃模型為

假設(shè)各道路通行方向?yàn)樯鲜瞿Ｐ椭蟹较?若最終流量為負(fù)，則改變通行方向)，運(yùn)用LINGO軟件求解以上線性規(guī)劃模型，解得在道路通行能力提高30%并且改變道路最小的情況下，只需將7-12號(hào)道路擴(kuò)寬2 m，將6-15號(hào)道路擴(kuò)寬5 m。結(jié)合道路通行量示意圖可知，適當(dāng)擴(kuò)寬路網(wǎng)中的關(guān)鍵道路，可以提高道路通行能力且道路改造成本較低。

5 結(jié)論與討論

基于圖論網(wǎng)絡(luò)最大流理論基礎(chǔ)，建立了一種改進(jìn)的網(wǎng)絡(luò)最大流模型，設(shè)計(jì)了優(yōu)化求解算法，并結(jié)合實(shí)例對(duì)道路通行能力進(jìn)行了定量研究及優(yōu)化改造，主要得到以下結(jié)論。

1) 基于基本的網(wǎng)絡(luò)最大流的線性規(guī)劃模型下，校園道路的最大通行能力為46 人/s，考慮到最短路徑以及雙向性后，最大通行能力為23 人/s。

2) 在道路通行能力提高30%并且改變道路最小的情況下，只需將7-12號(hào)道路擴(kuò)寬2 m，將6-15號(hào)道路擴(kuò)寬5 m，具有較高的可行性。

3) 模型考慮了學(xué)生通行的道路選擇性，排除了與最短距離相差較大的路徑，與實(shí)際情況更加符合；改進(jìn)模型進(jìn)一步考慮了道路雙向性，加強(qiáng)了原模型的約束條件。

4) 最大通行能力的減少是由于“人們會(huì)選擇較短路徑”以及“出發(fā)前已具有特定的目的地”，表明本模型的建立較為成功，更加符合實(shí)際性。研究成果可為城市道路路徑優(yōu)化、設(shè)計(jì)改造提供參考。