最大容量路的擴張問題研究

劉 耕

（中國地質大學 經濟管理學院，湖北 武漢 430074）

1 問題概述

我們生活在一個網絡世界中：公路網、鐵路網為我們出行和運輸物資提供了方便；電力網為我們提供了能源；電信網為我們傳遞信息。隨著人口的增加、技術的發展，對網絡的要求也不斷提高，網絡容量也在不斷擴張。2018年末，全國公路總里程達到485萬km，是1949年的60倍；根據《電力發展“十三五”規劃》，預計2020年全社會用電量6.8-7.2萬億kw·h，年均增長3.6%-4.8%，全國發電裝機容量20億kw，年均增長5.5%。每年要花費巨資對網絡進行建設和改造。如何制定最科學的方案，將網絡容量擴張到指定值，是我們不得不考慮的問題。

路是網絡中比較基本的概念，其有效算法可以在其它網絡優化問題中作為子算法調用。在現實中，對網絡的擴張往往是從路的改造開始的。在發生緊急情況時，我們往往更關注某些節點之間的路的容量問題。比如，連接起點與終點間的路的容量問題，通常要求這兩點間路的容量盡可能大，以便運輸盡可能多的物資，這也是本文所研究的主要內容。

方華提出了改造牽引種類、提高牽引質量、增建二線等的鐵路擴能改造方案[1]；王蓉將道路網抽象為網絡，尋找擴容關鍵邊，并將其與產生的逆向車道備選路段相結合，得到交通疏散逆向車道最優路段選擇方案[2]；高明霞等研究了在交通疏散中，通過對最大流增流關鍵邊所對應路段進行逆向管理擴容，能夠有效壓縮疏散時間[3]；侯志偉等使用最大流和堵塞流的相關理論，得到關內外道路合理擴容的方案[4]；劉耕研究了多階段情形下的容量擴張問題[5]。

上述作者研究的網絡改造問題，主要是通過弧改進的方式進行，而現實中存在多種調整方式。

定義：對于一對節點vs,vt,定義Ls-t為從vs到vt路的集合{l1,l2,…,ln}，定義路lk的容量為路lk上的弧的容量最小值，定義節點對vs-vt之間的路的容量為{l1,l2,…,ln}中容量的最大值，即最大容量路L(vs,vt)的容量，則有：

網絡容量的擴張有如下幾種方式：

（1）弧改進。在這種情形下，通過對弧(vi,vj)上的容量cij進行改造，使得網絡容量提高；弧(vi,vj)上增加的容量記為αij，單位改進費用記為 βij；這是一種常見的方式，日常生活中，道路的加寬、管道的加粗都屬于這種情形。

（2）點改進。在這種情形下，通過對節點vi進行改造，使得從節點vi上發出的弧(vi,vj)上的容量都提高相同的數值αi，單位改進費用為 βi。日常生活中，天然氣管網中增壓泵的安裝，可看作是點擴張的例子。

（3）弧改進與點改進相結合。即在網絡改造中，既有弧改進，也有點改進，二者可同時進行。如在供熱管網的改造過程中，既需要管段的擴建，也需要增設加壓泵站。

2 問題的一般模型和求解

現在討論節點對vs-vt的容量擴張問題，即將從vs-vt的最大容量路L(vs,vt)的容量擴張到給定值R0，要求擴張費用D最小。

針對此問題，我們分別按照網絡容量擴張的三種方式展開討論。

（1）弧改進情形下的網絡擴張問題。此時的網絡容量擴張是通過對弧的改造而實現的，問題表述如下：

目標函數式（1）表示弧改進成本最小化，式（2）表示擴張后新的最大容量路L(vs,vt)的容量約束。

（2）點改進情形下的網絡擴張問題。此時的網絡容量擴張是通過對節點的改造而實現的，問題表述如下：

目標函數式（3）表示點改進的成本最小化，式（4）同式（2）。

（3）弧改進和點改進相結合下的網絡容量擴張問題。此時的網絡容量擴張方式既有弧改進，也有點改進，問題表述如下：

目標函數式（5）表示總的改進成本最小化，式（6）同式（2）。

對于上述問題，我們可以把它們轉化為最短路問題。構建輔助網絡G（V，A，W），V，A定義如G（V，A，C），W的分量 ωij定義如下：

（1）弧改進情形下

（2）點改進情形下

（3）弧改進和點改進相結合

可以看出，單獨的弧擴張或點改進是其中的一種特殊情形。

原問題轉化為網絡G（V，A，W）中的vs-vt最短路問題，可以采用Dijkstra算法求解.

3 算例分析

在如圖1給定的有向網絡G（V，A，C）中，弧旁的數字表示網絡的容量，表1表示弧的單位容量改進成本，表2表示節點的單位容量改進成本。現在要求將路1-6的容量擴張到4，使擴張費用最低。

圖1 網絡圖

表1 弧的單位容量改進成本

表2 節點的單位容量改進成本

如前所示，建立輔助網絡G（V，A，W），針對網絡擴張的三種情形進行討論。

在弧改進的情形下：從節點1到節點6的最大容量路為：1-3-4-6。此時的改進方案為：弧（3，4）提高3個單位，其它弧不變；改進費用為9。

在點改進的情形下：此時的最大容量路為：1-2-4-6。此時的改進方案為：節點1改進1個單位，節點2改進1個單位，其它節點不變；改進費用為6。

在弧改進和點改進相結合的情況下：此時的最大容量路為1-2-4-6。改進方案為：弧（1,2）改進1個單位，節點2改進2個單位，其它弧和節點不變。此時的改進費用為4。

可以看出，在弧改進和點改進共同作用的情況下，擴張費用最低。

4 結語

本文研究了有向網絡中最大容量路的擴張問題。現實生活中，網絡的擴張往往是通過對路的擴張進行的。在發生緊急情況網絡被破壞時，前方急需物資，此時比較明智的做法是對原有網絡進行改造，從起點到終點找到一條最大容量路，保證其通暢。本文所建立的數學模型具有較大的實用價值。我們將進一步考慮：在網絡擴張過程中，限制擴張的弧的數量時，如何提高網絡容量。