Maximal Flow在京津冀公路交通網(wǎng)絡(luò)管理中的應(yīng)用

王佳

(燕山大學(xué) 經(jīng)濟(jì)管理學(xué)院，河北秦皇島 066004)

0 引言

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

1 京津冀經(jīng)濟(jì)圈公路交通網(wǎng)絡(luò)的通行能力

1.1 超飽和狀態(tài)

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

表1 京津冀公路國(guó)道網(wǎng)年交通通行情況表 （當(dāng)量標(biāo)準(zhǔn)小客車）

1.2 節(jié)點(diǎn)間連通狀態(tài)差

公路網(wǎng)絡(luò)中節(jié)點(diǎn)間連通狀態(tài)用平均徑路長(zhǎng)來(lái)衡量，也是統(tǒng)計(jì)節(jié)點(diǎn)間聯(lián)系難易程度的主要方法。其基本思路是：網(wǎng)絡(luò)節(jié)點(diǎn)間如存在直接連線，記為1，沒(méi)有直接連線記為0，一對(duì)節(jié)點(diǎn)間的距離用沿最短路徑所介入的連線數(shù)表示，任何一個(gè)節(jié)點(diǎn)的行總數(shù)是根據(jù)距離量度而得出的其通達(dá)度量度，本交通網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的平均徑路長(zhǎng)是由行總數(shù)除以行內(nèi)正值節(jié)點(diǎn)數(shù)計(jì)算得出的。行總數(shù)值或平均徑路長(zhǎng)值越小，表明本節(jié)點(diǎn)的連通狀態(tài)越好，反之連通狀態(tài)越差。繼而得出行總數(shù)值或平均徑路長(zhǎng)值最小的節(jié)點(diǎn)就是本交通網(wǎng)絡(luò)的中心點(diǎn)。

表2 京津冀公路交通網(wǎng)絡(luò)節(jié)點(diǎn)代碼

表3 京津冀公路交通網(wǎng)絡(luò)節(jié)點(diǎn)連通狀態(tài)矩陣

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

2 Maximal Flow理論

2.1 基本思想

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

定義1：設(shè)有向連通圖G(V,E)，在V中指定一點(diǎn)稱為發(fā)點(diǎn)s，和另一點(diǎn)稱為收點(diǎn)t，其余的稱為中間點(diǎn)?；?arc)集E中每條弧(i,j)上有非負(fù)數(shù)cij稱為這弧的容量，記容量集為c={cij},稱這樣的圖為一個(gè)網(wǎng)絡(luò)。記為G=(V,E,c)。（注：當(dāng)(i,j)不是弧時(shí)cij=0)

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

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

（2）平衡條件：對(duì)所有的中間點(diǎn)，流入的流量和等于流出的流量和，即；發(fā)點(diǎn)流出的總流量F等于流進(jìn)收點(diǎn)的總流量F。最大流問(wèn)題就是求總流量最大的可行流，是一個(gè)特殊的線性規(guī)劃問(wèn)題。它密切了圖論和運(yùn)籌學(xué)，開辟了圖論應(yīng)用的新途徑。

定義3：容量網(wǎng)絡(luò)G，若存在μ為網(wǎng)絡(luò)中從s到t的一條鏈，給μ定向?yàn)閺膕到t，μ上的邊凡與μ同向稱為正向邊，凡與μ反向稱為反向邊，其集合用μ+和μ-表示，f是一個(gè)可行流，如果滿足條件則稱μ為從s到t的一條可增廣鏈。（注：可增廣鏈?zhǔn)菍?shí)際意義：沿著這條鏈從s到t輸送的流量，還有潛力可挖，只需經(jīng)過(guò)適當(dāng)?shù)恼{(diào)整，就可以把流量提高，調(diào)整后的流，仍為一新的可行流，其流量比原可行流要大，重復(fù)這個(gè)過(guò)程，直到不存在關(guān)于該流的可增廣鏈時(shí)就得到了最大流，也就尋到了最佳的流量圖網(wǎng)絡(luò)。）

2.2 解決方法

解決最大流問(wèn)題的主要方法是Ford-Fulkerson標(biāo)號(hào)法。可分為兩步：第一步是標(biāo)號(hào)過(guò)程，即通過(guò)標(biāo)號(hào)來(lái)尋找可增廣鏈；第二步是調(diào)整過(guò)程，即沿可增廣鏈調(diào)整fij以增加流量。

2.2.1 標(biāo)號(hào)過(guò)程

（1）給發(fā)點(diǎn)s以標(biāo)號(hào)（▽，+∞）。

（2）選擇一個(gè)已標(biāo)號(hào)的頂點(diǎn)vi,對(duì)于vi的所有未給標(biāo)號(hào)的鄰接點(diǎn)vj按下列規(guī)則處理：若邊（vi,vj）∈ E,且fij＞0，由則令δj=min(fij,δi),并給vj以標(biāo)號(hào)（-vi,δj）；若邊（vi,vj）∈E,且fij＜ cij時(shí)，令δj=min(cij-fij,δi),并給vj以標(biāo)號(hào)（+vi,δj）。

（3）重復(fù)（2）直到收點(diǎn)t被標(biāo)號(hào)或不再有頂點(diǎn)可標(biāo)號(hào)時(shí)為止。（注：若t得到標(biāo)號(hào)，就說(shuō)明存在一條可增廣鏈，轉(zhuǎn)第2步調(diào)整過(guò)程。若t未得到標(biāo)號(hào)，標(biāo)號(hào)過(guò)程已無(wú)法進(jìn)行時(shí)，說(shuō)明fij已是最大流量。

2.2.1 調(diào)整過(guò)程

（2）去掉所有標(biāo)號(hào)，回到第1步，對(duì)可行流f'ij重新標(biāo)號(hào)。

3 實(shí)證分析

京津冀經(jīng)濟(jì)區(qū)交通網(wǎng)絡(luò)雖然很暢通，但是每個(gè)節(jié)點(diǎn)間的通行能力已遠(yuǎn)遠(yuǎn)不能滿足現(xiàn)代經(jīng)濟(jì)的快速發(fā)展，如何利用現(xiàn)有的配置能力擴(kuò)大流通量，這將是本文運(yùn)用Maximal Flow（最大流）的基本思想重點(diǎn)解決的問(wèn)題。（京津冀經(jīng)濟(jì)區(qū)13個(gè)城市節(jié)點(diǎn)間的連通網(wǎng)絡(luò)圖如圖1所示）

截取京津冀交通網(wǎng)絡(luò)中的v1—v6部分（因這段是本經(jīng)濟(jì)區(qū)中交通最繁忙的段落，也是京津冀經(jīng)濟(jì)圈中旅游最發(fā)達(dá)的段落。研究此段交通的最大流問(wèn)題對(duì)京津冀交通網(wǎng)絡(luò)中其他段最具有借鑒意義。）下面用Maximal Flow（最大流）問(wèn)題的Ford-Fulkerson標(biāo)號(hào)法解決此問(wèn)題。（說(shuō)明：每條弧上括號(hào)里的第一個(gè)數(shù)字為cij容量，fij為現(xiàn)通行流量。滿足0≤fij≤cij）

首先給v1點(diǎn)標(biāo)號(hào)（▽，+∞）。

檢查v1的鄰接點(diǎn)v2,v3,v5，發(fā)現(xiàn)此三點(diǎn)均滿足（vi,vj）∈ E。給v2以標(biāo)號(hào)（+v1,3），v3以標(biāo)號(hào)（+v1,2），v5以標(biāo)號(hào)（+v1,5）。

檢查v2點(diǎn)的鄰接點(diǎn)v4,v6，發(fā)現(xiàn)此二點(diǎn)均滿足（vi,vj）∈E。給v4以標(biāo)號(hào)（+v2,2），給v6以標(biāo)號(hào)（+v2,5）。

V4的接點(diǎn)v6為最終點(diǎn)，得以標(biāo)號(hào)（+v4,3）。

由于v6得以標(biāo)號(hào)，說(shuō)明存在一條可增廣鏈：v1-v2-v4-v6（圖3中粗線條邊），所以此標(biāo)號(hào)過(guò)程結(jié)束。進(jìn)入調(diào)整過(guò)程，根據(jù)Maximal Flow中的定義，可知δt=2，從v6點(diǎn)開始按此條可增廣鏈反向調(diào)整。調(diào)整后的可行流見圖4。

圖1 京津冀公路交通網(wǎng)絡(luò)圖

圖2 京津冀公路交通網(wǎng)絡(luò)截圖：v1-v6

重新開始標(biāo)號(hào)過(guò)程，重復(fù)以上步驟。直到標(biāo)號(hào)過(guò)程無(wú)法繼續(xù)，而此時(shí)v6點(diǎn)并未得到標(biāo)號(hào)，這時(shí)得到最大流F=42。算法結(jié)束。

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

圖3 v1-v6的標(biāo)號(hào)過(guò)程及增廣鏈圖

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

4 結(jié)語(yǔ)

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

[1] 2005～2009年度中國(guó)交通統(tǒng)計(jì)公報(bào)，中國(guó)交通統(tǒng)計(jì)信息網(wǎng).

[2] 王恒，李悅錚.大連市旅游交通空間結(jié)構(gòu)分析與優(yōu)化[J].海洋開發(fā)與管理，2009,(9）.

[3] 胡運(yùn)權(quán).運(yùn)籌學(xué)教程（第三版）[M].北京:清華大學(xué)出版社,2007.

[4] 海軍，高輝蘭，侯遠(yuǎn)達(dá).動(dòng)態(tài)交通網(wǎng)絡(luò)最大能力路徑問(wèn)題算法研究[J].軍事交通學(xué)院學(xué)報(bào)，2008,(9）.

[5] 劉瓊英，全華.網(wǎng)絡(luò)最大流模型在旅游管理中的應(yīng)用[J].中南林業(yè)科技大學(xué)學(xué)報(bào)，2010,(6）.