Maximal Flow在京津冀公路交通網絡管理中的應用

王佳

(燕山大學 經濟管理學院，河北秦皇島 066004)

0 引言

京津冀經濟圈是繼珠三角和長三角之后中國經濟增長的第三大引擎，經濟發展的活力日益增強。同時，京津冀經濟圈公路網絡運輸能力和服務水平的不斷提升，對增強北京、天津、河北等核心城市的輻射帶動作用，縮小地區與城鄉差別，促進區域經濟一體化發揮了重要作用。京津冀三地交通一體化已建立了良好的基礎，基本形成了六條跨省市綜合運輸大通道，即：以京滬高速公路為主干的京滬網絡體系；以京沈高速公路為主干的京沈網絡體系；以京珠高速公路為主干的京廣網絡體系；以京銀公路國道為主干的京蘭網絡體系；以京珠公路國道為主干的京九網絡體系；以石太高速公路為主干的石太網絡體系。但隨著京津冀經濟圈經濟的迅猛發展，本區域的公路交通系統已出現超飽和狀態，已不能滿足甚至滯后于經濟的發展，怎樣與區域經濟協調發展直至拉動經濟發展已成為經濟學者們共同關注的焦點問題。本文正是從這一角度出發，利用網絡Maximal Flow（最大流）定理研究如何充分利用京津冀公路交通系統的配置能力，以取得最大的通行能力，確保完成本區域經濟的暢通快速發展。

1 京津冀經濟圈公路交通網絡的通行能力

1.1 超飽和狀態

京津冀經濟圈出口公路通行能力不足的矛盾日益突出，京津冀核心城市間交通壓力不斷增大，連接主要城市、服務主要經濟發展走廊的干線公路通行能力嚴重不足，津冀60%以上的干線公路，北京市70%以上的干線公路常年處于擁擠狀態（見表1）。2005年全國年均交通擁擠程度為0.44，2006年降為0.4，2007年為0.42，2008年減為0.39，2009年減到0.37，而同一時間段內的京津冀經濟區單國道網交通擁擠度就已超過0.6，這種狀態一直到現在都沒有較大的改觀；交通京津塘高速公路最大客流量已超過13萬輛，已達設計車流量的2.6倍，路段常年處于超飽和狀態；旅游公路服務水平不高，休閑旅游勝地張家口和承德四級以下公路的比重分別占到61%和58%。京津冀經濟圈交通網絡通行能力的嚴重受阻，已對地區經濟發展產生了很大的負面影響。

表1 京津冀公路國道網年交通通行情況表 （當量標準小客車）

1.2 節點間連通狀態差

公路網絡中節點間連通狀態用平均徑路長來衡量，也是統計節點間聯系難易程度的主要方法。其基本思路是：網絡節點間如存在直接連線，記為1，沒有直接連線記為0，一對節點間的距離用沿最短路徑所介入的連線數表示，任何一個節點的行總數是根據距離量度而得出的其通達度量度，本交通網絡中每個節點的平均徑路長是由行總數除以行內正值節點數計算得出的。行總數值或平均徑路長值越小，表明本節點的連通狀態越好，反之連通狀態越差。繼而得出行總數值或平均徑路長值最小的節點就是本交通網絡的中心點。

表2 京津冀公路交通網絡節點代碼

表3 京津冀公路交通網絡節點連通狀態矩陣

從表3中可以看出，京津冀公路交通網絡各節點平均徑路長為2.08（注：理想的交通網絡里每個旅游交通節點平均徑路長為1），表明連通性不理想。其中V1點（北京）平均徑路長為1.58，是京津冀公路交通網絡中連通狀態最好的節點，成為該網絡的中心；V2（天津）、V7（石家莊）平均徑路長為1.83，是本交通網絡中連通狀態較好的節點；而V6（秦皇島）、V11（邢臺）、V13（邯鄲）節點連通狀態明顯較差。這就表明京津冀公路交通網絡體系通達度有待提高，在提高每個節點承載量與通行量的基礎上，急需擴大節點之間的連通性與聯貫性。

2 Maximal Flow理論

2.1 基本思想

1955年，T.E.哈里斯在研究鐵路最大通量時首先提出在一個給定的網絡上尋求兩點間最大運輸量的問題。1956年，L.R.Ford福特和D.R.Fulkerson富克遜等人給出了解決這類問題的算法，從而建立了網絡流理論。管道網絡中每邊的最大通過能力即容量是有限的，實際流量也并不一定等于容量，此問題就是要討論如何充分利用現有配置條件使網絡具有最大的流量能力，以取得最好的效果，這就是現今意義上的最大流問題。

定義1：設有向連通圖G(V,E)，在V中指定一點稱為發點s，和另一點稱為收點t，其余的稱為中間點。弧(arc)集E中每條弧(i,j)上有非負數cij稱為這弧的容量，記容量集為c={cij},稱這樣的圖為一個網絡。記為G=(V,E,c)。（注：當(i,j)不是弧時cij=0)

定義2：在弧集E上的弧(i,j)定義一非負數fij，稱為弧(i,j)上的流量，流量的集合f={fij}稱為網絡的一個流。稱滿足下列條件的流為可行流：

（1）容量限制條件：所有的弧的流量fij不大于弧的容量cij，即0≤fij≤cij；

（2）平衡條件：對所有的中間點，流入的流量和等于流出的流量和，即；發點流出的總流量F等于流進收點的總流量F。最大流問題就是求總流量最大的可行流，是一個特殊的線性規劃問題。它密切了圖論和運籌學，開辟了圖論應用的新途徑。

定義3：容量網絡G，若存在μ為網絡中從s到t的一條鏈，給μ定向為從s到t，μ上的邊凡與μ同向稱為正向邊，凡與μ反向稱為反向邊，其集合用μ+和μ-表示，f是一個可行流，如果滿足條件則稱μ為從s到t的一條可增廣鏈。（注：可增廣鏈是實際意義：沿著這條鏈從s到t輸送的流量，還有潛力可挖，只需經過適當的調整，就可以把流量提高，調整后的流，仍為一新的可行流，其流量比原可行流要大，重復這個過程，直到不存在關于該流的可增廣鏈時就得到了最大流，也就尋到了最佳的流量圖網絡。）

2.2 解決方法

解決最大流問題的主要方法是Ford-Fulkerson標號法。可分為兩步：第一步是標號過程，即通過標號來尋找可增廣鏈；第二步是調整過程，即沿可增廣鏈調整fij以增加流量。

2.2.1 標號過程

（1）給發點s以標號（▽，+∞）。

（2）選擇一個已標號的頂點vi,對于vi的所有未給標號的鄰接點vj按下列規則處理：若邊（vi,vj）∈ E,且fij＞0，由則令δj=min(fij,δi),并給vj以標號（-vi,δj）；若邊（vi,vj）∈E,且fij＜ cij時，令δj=min(cij-fij,δi),并給vj以標號（+vi,δj）。

（3）重復（2）直到收點t被標號或不再有頂點可標號時為止。（注：若t得到標號，就說明存在一條可增廣鏈，轉第2步調整過程。若t未得到標號，標號過程已無法進行時，說明fij已是最大流量。

2.2.1 調整過程

（2）去掉所有標號，回到第1步，對可行流f'ij重新標號。

3 實證分析

京津冀經濟區交通網絡雖然很暢通，但是每個節點間的通行能力已遠遠不能滿足現代經濟的快速發展，如何利用現有的配置能力擴大流通量，這將是本文運用Maximal Flow（最大流）的基本思想重點解決的問題。（京津冀經濟區13個城市節點間的連通網絡圖如圖1所示）

截取京津冀交通網絡中的v1—v6部分（因這段是本經濟區中交通最繁忙的段落，也是京津冀經濟圈中旅游最發達的段落。研究此段交通的最大流問題對京津冀交通網絡中其他段最具有借鑒意義。）下面用Maximal Flow（最大流）問題的Ford-Fulkerson標號法解決此問題。（說明：每條弧上括號里的第一個數字為cij容量，fij為現通行流量。滿足0≤fij≤cij）

首先給v1點標號（▽，+∞）。

檢查v1的鄰接點v2,v3,v5，發現此三點均滿足（vi,vj）∈ E。給v2以標號（+v1,3），v3以標號（+v1,2），v5以標號（+v1,5）。

檢查v2點的鄰接點v4,v6，發現此二點均滿足（vi,vj）∈E。給v4以標號（+v2,2），給v6以標號（+v2,5）。

V4的接點v6為最終點，得以標號（+v4,3）。

由于v6得以標號，說明存在一條可增廣鏈：v1-v2-v4-v6（圖3中粗線條邊），所以此標號過程結束。進入調整過程，根據Maximal Flow中的定義，可知δt=2，從v6點開始按此條可增廣鏈反向調整。調整后的可行流見圖4。

圖1 京津冀公路交通網絡圖

圖2 京津冀公路交通網絡截圖：v1-v6

重新開始標號過程，重復以上步驟。直到標號過程無法繼續，而此時v6點并未得到標號，這時得到最大流F=42。算法結束。

可以得出，從v1—v6路段中，最大的交通流量是42萬輛，分為4條線路，分別是v1-v5-v6， v1-v3-v4-v6，v1-v2-v4-v6，v1-v2-v6。其中v1-v5-v6段流通流量未達到飽和，可以在調控的技術條件下增加流量：首先需要調整流量的是v1—v5段，從北京到承德段是旅游季節交通擁堵最嚴重的路段，加強京承高速公路的指揮調控力度，可以緩解交通流通的壓力；其次需要調整的是v5—v6段，從承德到秦皇島路段是“京承秦金三角”旅游圈的必經之路，也是承建承秦高速公路的出發點所在，為促進京承秦三地的交通通暢奠定良好的基礎。

圖3 v1-v6的標號過程及增廣鏈圖

圖4 v1-v6的可行流示意圖

4 結語

網絡最大流理論的應用在不斷發展，已遍及通訊、運輸、電力、工程規劃、任務分派、設備更新以及計算機輔助設計等眾多領域。本文實例運用了Maximal Flow理論，以京津冀公路交通網絡中最典型的路網從發點（北京）v1到收點（秦皇島）v6為例，驗算了其路網的最大流量為42。同時，也找到了影響整體流量的關鍵路段，或者叫咽喉路段：v1-v5，v5-v6，它們決定了整個網絡的最大通行能力，要提高整個網絡的通行流量，必須首先改造關鍵路段的通行能力。可以得出，除了解決京津冀經濟圈公路交通網絡的通暢便達之外，為了使京津冀經濟圈的交通網絡更為合理有效，必須在遵循京津冀交通一體化的原則下，著力提高高速公路、鐵路、港口、民航保障能力，形成“快捷、高效、安全的現代綜合交通網絡”，積極籌建以京津為主軸，以石家莊、秦皇島為兩翼的區域快速路網，推動形成覆蓋京津冀地區主要城市的區域“2小時交通圈”，促進各城市之間經濟交流和社會的快速發展。

[1] 2005～2009年度中國交通統計公報，中國交通統計信息網.

[2] 王恒，李悅錚.大連市旅游交通空間結構分析與優化[J].海洋開發與管理，2009,(9）.

[3] 胡運權.運籌學教程（第三版）[M].北京:清華大學出版社,2007.

[4] 海軍，高輝蘭，侯遠達.動態交通網絡最大能力路徑問題算法研究[J].軍事交通學院學報，2008,(9）.

[5] 劉瓊英，全華.網絡最大流模型在旅游管理中的應用[J].中南林業科技大學學報，2010,(6）.