廖 曄，王順意

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

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

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

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

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

1 問題背景

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

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

圖1 道路簡化圖Figure 1 Road simplification map

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

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

2 改進網(wǎng)絡最大流模型建立

2.1 道路飽和流量計算

由于已知校園內道路分布簡化圖，設各道路飽和流量為Cij，則有

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

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

即可得各道路飽和流量為

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

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

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

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

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

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

1) 目標函數(shù)。

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

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

2) 約束分析。

① 人流量守恒約束。

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

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

對于任意中間點，流入量等于流出量，即對于每一個i(is,t)有

③ 道路通行容量約束。

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

3) 模型確定。

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

2.3 最短路模型

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

當然，在通行過程中，并不會每人都選擇最短的路，因此假設從某源到某匯的過程中，學生只會選擇與最短路徑相差30%的路，即可行路徑滿足

2.4 道路最大通行能力改進模型

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

則目標函數(shù)為

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

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

則約束條件為

3 改進網(wǎng)絡最大流模型求解

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

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

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

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

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

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

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

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

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

在圖5中，各道路上的負數(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

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

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

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

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

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

1) 目標函數(shù)。

在通行能力提高量一定的情況下，道路的寬度也不能一味的擴寬，所以此時的目標為成本最低，在道路成本單價一定的情況下，將設為各條道路擴寬道路后的面積之和，即

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

2) 約束分析。

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

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

3) 模型確定。

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

假設各道路通行方向為上述模型中方向(若最終流量為負，則改變通行方向)，運用LINGO軟件求解以上線性規(guī)劃模型，解得在道路通行能力提高30%并且改變道路最小的情況下，只需將7-12號道路擴寬2 m，將6-15號道路擴寬5 m。結合道路通行量示意圖可知，適當擴寬路網(wǎng)中的關鍵道路，可以提高道路通行能力且道路改造成本較低。

5 結論與討論

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

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

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

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

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