基于輔助圖最短路算法的程序設(shè)計(jì)及應(yīng)用

高 燕

(河北省高速公路青銀管理處)

自1962年提出求解網(wǎng)絡(luò)最大流的第一算法—標(biāo)號(hào)法以來(lái)，不少學(xué)者開(kāi)始應(yīng)用數(shù)學(xué)網(wǎng)絡(luò)理論對(duì)路網(wǎng)系統(tǒng)進(jìn)行研究并提出計(jì)算路網(wǎng)容量的模擬方法和數(shù)學(xué)模型，近幾年，對(duì)于路網(wǎng)容量的研究得到很大進(jìn)展，最大流理論也有所應(yīng)用。但是以往應(yīng)用最大流理論對(duì)路網(wǎng)容量的計(jì)算方法在對(duì)路網(wǎng)簡(jiǎn)化和計(jì)算量上各有缺陷，不方便應(yīng)用到計(jì)算機(jī)程序設(shè)計(jì)中。因此從另一個(gè)角度入手，尋找一種更適合于編程計(jì)算的最大流最小割算法。利用基于輔助圖的最短路算法來(lái)代替最大流最小割算法就是一個(gè)很好的途徑，輔助圖最短路算法適應(yīng)于單起終點(diǎn)的無(wú)向網(wǎng)絡(luò)，可以應(yīng)用到可平面化的道路網(wǎng)絡(luò)中，不僅可以簡(jiǎn)單處理路網(wǎng)，而且該算法能夠輸出確定的網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間的流量值。

1 對(duì)路網(wǎng)的抽象簡(jiǎn)化

第一，路網(wǎng)應(yīng)該簡(jiǎn)化為無(wú)向網(wǎng)絡(luò)更為合理，因?yàn)樵诘缆肪W(wǎng)絡(luò)中，每個(gè)路段一般都是雙向的，即使有單向街道也往往在很接近的地方有對(duì)向的平行街道與之相匹配。以往的輔助圖最短路算法從理論上提出了路網(wǎng)應(yīng)該簡(jiǎn)化為無(wú)向網(wǎng)絡(luò)，但是在實(shí)例處理時(shí)體現(xiàn)不夠，即一般來(lái)講基于此，提出對(duì)無(wú)向網(wǎng)絡(luò)進(jìn)行測(cè)算的方法。

第二，無(wú)向圖的可行流，大多表現(xiàn)在多收發(fā)點(diǎn)的多種物流上。以往算法大都將其簡(jiǎn)化到確定的幾個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)上，即車(chē)站、碼頭和機(jī)場(chǎng)等重要的交通集散點(diǎn)。雖然這種簡(jiǎn)化有一定的合理性，但是這樣找到的最短路可能不是整個(gè)網(wǎng)絡(luò)中的最短路，即可能存在非收發(fā)點(diǎn)之間的最短路，其值小于收發(fā)點(diǎn)之間的最短路的值。通過(guò)對(duì)算法輸出進(jìn)行改進(jìn)，將輔助路網(wǎng)內(nèi)部任意兩個(gè)節(jié)點(diǎn)之間的最短路徑，即原路網(wǎng)任意兩個(gè)節(jié)點(diǎn)之間的最大流輸出并進(jìn)行分析。

2 對(duì)最短路算法的改進(jìn)

利用以上算法，首先將現(xiàn)狀路網(wǎng)轉(zhuǎn)化成可以利用最短路算法求解最小割的路網(wǎng)模式，包含收發(fā)點(diǎn)選取、邊權(quán)賦值、構(gòu)造輔助路網(wǎng)等，應(yīng)用Matlab 軟件，選取Dijkstra 算法對(duì)最短路徑部分進(jìn)行計(jì)算機(jī)編程。本算法不但應(yīng)用先進(jìn)的軟件工具進(jìn)行編程，而且對(duì)程序輸出顯示進(jìn)行改進(jìn)，可以輸出輔助路網(wǎng)中任意兩點(diǎn)的最短路徑和最大流量，程序的算法流程圖見(jiàn)圖1。

3 算法實(shí)例

如圖2 所示，該通道網(wǎng)絡(luò)的起點(diǎn)為v1，終點(diǎn)為v6，通道的通行能力用標(biāo)注在路線(xiàn)旁邊的數(shù)字表示。下面以圖2 為例，給出本算法的應(yīng)用過(guò)程。

圖1 算法流程圖

圖2 通道網(wǎng)絡(luò)簡(jiǎn)化圖

下面開(kāi)始構(gòu)造該網(wǎng)絡(luò)的輔助圖，如圖3 所示，G 中存在多少個(gè)內(nèi)面，G*就可以產(chǎn)生多少個(gè)中間點(diǎn)與之對(duì)應(yīng);另外，G*的起點(diǎn)和終點(diǎn)位于G 的上面和下面。輔助圖中各邊的權(quán)值與原路網(wǎng)中與之相交的G 中的邊權(quán)一一對(duì)應(yīng)。

圖3 輔助路網(wǎng)圖

根據(jù)以上兩圖寫(xiě)出輔助圖路網(wǎng)的路線(xiàn)權(quán)值矩陣，這個(gè)矩陣不但可以表示輔助圖當(dāng)中各個(gè)節(jié)點(diǎn)的連通狀況，而且能表示各條路線(xiàn)的通行能力。兩點(diǎn)之間沒(méi)有直接通路的路線(xiàn)權(quán)值應(yīng)該無(wú)限大，即無(wú)路可走，這里根據(jù)實(shí)際情況用一個(gè)較大的數(shù)表示，該路網(wǎng)選取100(遠(yuǎn)遠(yuǎn)大于有連接通路的其它節(jié)點(diǎn)之間的權(quán)值即可)。矩陣如下

將初始矩陣讀入計(jì)算機(jī)程序當(dāng)中，利用Matlab 軟件程序可以計(jì)算出路網(wǎng)最大流量矩陣和路網(wǎng)中任意兩點(diǎn)之間的最短路徑。

最大流量矩陣如下

從路網(wǎng)容量矩陣可以看出，原路網(wǎng)的最大流量為M16=9，即原通道網(wǎng)絡(luò)圖中從v1到v6的最大流量為9。另外該矩陣還輸出任意兩點(diǎn)之間的最大流Mij，除了始、終結(jié)點(diǎn)之間的容量外，其它內(nèi)部結(jié)點(diǎn)之間的路網(wǎng)容量雖然不符合路網(wǎng)容量的定義，但是能夠反映路網(wǎng)中內(nèi)部流量情況。

最短路矩陣Rij記錄從點(diǎn)到點(diǎn)的最短路徑的中間結(jié)點(diǎn)，該路網(wǎng)最短路矩陣具體如下

最短路徑確定方法為

由此可以看出，輔助圖G*的最短路是1.5.6，最短路的值為9。與之相對(duì)應(yīng)的原路網(wǎng)的最小割集是(v3v6、v5v6)，最小割集容量是9。

4 小 結(jié)

在已有算法的基礎(chǔ)上，通過(guò)改進(jìn)得到了求無(wú)向路網(wǎng)中所有最小割集的較為簡(jiǎn)便的算法，通過(guò)構(gòu)造輔助路網(wǎng)并求其最短路，利用Matlab 計(jì)算機(jī)語(yǔ)言程序?qū)崿F(xiàn)該算法，并且可以根據(jù)需求輸出輔助網(wǎng)絡(luò)中任意兩點(diǎn)間的最短路和原路網(wǎng)任意兩點(diǎn)的最大流，不但減少了計(jì)算量，而且提高了該算法應(yīng)用于計(jì)算機(jī)上的可靠性。將該算法應(yīng)用于可平面化的實(shí)際路網(wǎng)中，可以快速找到路網(wǎng)的關(guān)鍵斷面，即運(yùn)輸通道的瓶頸，為路網(wǎng)規(guī)劃和改建擴(kuò)建提供理論依據(jù)。

［1］楊濤，徐吉謙. 運(yùn)輸網(wǎng)絡(luò)極大流的一種新算法［J］. 土木工程學(xué)報(bào)，1991，24(2).

［2］陳春妹.路網(wǎng)容量研究［D］.北京工業(yè)大學(xué)，2002.

［3］楊曉萍.基于網(wǎng)絡(luò)最大流理論的城市道路網(wǎng)容量研究［D］. 哈爾濱工業(yè)大學(xué)，2004.