一類點權網絡的最小費用流問題＊

2012-04-12 08:02:14高明霞賀國光

武漢理工大學學報(交通科學與工程版) 2012年3期

高明霞賀國光

（蘭州交通大學交通運輸學院1）蘭州 730070）（天津大學管理學院2）天津 300072）

典型的最小費用流問題是指在一個給定的網絡中求一個從發點到收點的流值為某一給定常數的流，使其費用最小［1］.在這個網絡中，流量除了滿足節點的守恒條件之外，其調整和增加只受邊上容量的限制，對應費用也是由各邊費用得到，稱這類網絡為弧權網絡，平常所說的網絡皆是指這類弧權網絡.對弧權網絡中最小費用流問題的求解已經有負回路算法、最小費用路算法和原始對偶算法等有效算法［2］.

但有些情況下，網絡流量不但受邊上容量的限制，還取決于其所流經的節點的容量，稱這類網絡為點權網絡［3］，城市道路網就是一類典型的點權網絡.如果在城市道路網中進行目標為費用最小的物資輸送或車輛調派，除路段通行能力之外，交叉口尤其是信號交叉口的通行能力也是限制物資或車輛流量的重要因素，交叉口處產生的費用也不能忽略.以往考慮節點容量的最小費用流算法如最小點截割法［3］、連續時間網絡的最小費用流算法［4－5］等考慮的都是節點的總容量，即一個節點只有一個容量權重.而城市道路網中由于信號配時等原因，即使是同一個交叉口，在不同走向（如左轉、直行、右轉）的通行能力并不相同，經過交叉口j去往下一個交叉口k的車輛，在j處的延誤和通行能力限制如何，取決于該車是如何到達j的，上述算法不具有這樣的方向性.

本文將交叉口不同方向的延誤和通行能力作為節點權重，建立了包括節點分方向權重和弧權的點權網絡來表示城市道路網，并對普通網絡最小費用流問題的最小費用路算法做了改進，給出了一個時間復雜性為O（nmf0）的最小費用路算法.其中：n，m，f0分別為網絡中節點個數，邊的條數和給定起點的流值.求解這類點權網絡中的最小費用流問題，其中費用為時間.

1 算法

1.1 相關符號和變量

用網絡中的節點代表交叉口和特定起終點，用弧代表相鄰交叉口之間的路段，將城市道路網表示為有向網絡G＝（V，A，D，C，T，U）.式中：V＝｛vi，i＝1，2，…，n｝為頂點集合，｜V｜＝n；D＝｛dijk，i，j，k＝1，2，…，n｝為點權集合，表示由節點i經j至k時在j處產生的延誤；C＝｛cijk，i，j，k＝1，2，…，n｝為點權集合，表示由節點i經j至k時在j處的通行能力；A＝｛（i，j），i，j＝1，2…，n｝為弧集合，｜A｜＝m；T＝｛tij，i，j＝1，2，…，n｝為弧權集合，表示路段（i，j）的走行時間；U＝｛uij，i，j＝1，2，…，n｝為弧權集合，表示路段（i，j）的通行能力；節點1和n分別為起點和終點.

除上面的符號之外，定義以下符號和變量：fij為流經路段（i，j）的流量；fijk為流經節點j的流中來自i欲去往k的流量；f0為源點給定的待輸送流量；f，f＊為網絡當前的流及其流量大小；P為流的增廣路或最小費用路；p［i］為增廣路或最小費用路中節點i的前一個節點.

1.2 算法步驟

算法步驟如下.

步驟0 給網絡一個初始可行流f（如零流）.

步驟1 構造與當前流對應的殘量網絡

步驟2 在殘量網絡中尋找源點至終點走行時間最短的路徑P，若不存在這樣的路線，則計算結束，網絡中不存在流值為f0的可行流，否則轉步驟3.

步驟3 沿路徑P增廣θ個單位的流量，其中θ＝min（θ1，θ2，f0－f＊），θ1＝min（uij－fij，cijk－fijk），if（i，j）∈P＋and （j，k）∈P＋，θ2＝min（fjk，fkji）；if（i，j）∈P－and（j，k）∈P－.式中：P＋，P－分別代表路徑P上前向弧和后向弧的集合.

其中步驟2中最短路徑的求解采用標號修正算法逐步逼近最優解，定義為第k次檢查標號時起點1至節點i的最短走行時間，算法步驟如下：

1.3 算法時間復雜性分析

由以上步驟可知，算法的主要工作量在于連續地尋找最小費用路并增廣，由于每次增廣使得流值至少增加一個單位，所以步驟1～步驟3最多循環f0次，所以整個算法的復雜性等于O（f0）乘以最短路算法的復雜性.步驟2中最短路算法的主要工作量在于步驟2.2中方程的循環迭代，在第k次循環中，計算每個只需檢查節點j的所有入弧，故步驟2.2的工作量為O（m），總共最多循環n－1次，所以最短路算法的復雜性為O（nm）；因此整個算法的復雜性為O（nmf0）.

2 算例

在圖1所示的道路網中，節點1代表起點，節點14代表終點，其他節點代表城市道路網中的交叉口，假設所有交叉口皆為信號交叉口，所有路段皆為雙向通行.假設起點1處有一定數量的車流要派往終點14，要求車輛總走行時間最短，派送方案可以通過求解1至14的最小費用流確定.為簡便起見，算法中只考慮與節點1至節點14流量方向一致的走向，為避免殘量網絡中出現重復邊，對2個走向都與流量走行一致的路段，加入虛擬節點（圖2中15～20）代表該路段的中點，即路段兩端至虛擬節點的走行時間皆為路段走行時間的一半，則圖1表示的道路網絡圖簡化為圖2所示的有向網絡.節點分方向權重見表1，網絡中各弧權重見表2.

表1 交叉口分方向通行能力與延誤（以cijk和dijk表示）

表2 路段通行能力uij和走行時間tij

圖1 算例的道路網絡圖

圖2 由圖1簡化的有向網絡

假定節點1處待調派的車流量為150pcu／h，運用上述算法求解起終點間的最小費用流，得到派送路線及相應流量和走行時間如表3所列.

3 結論

如果在城市道路網中進行車輛調派或物資輸送，交叉口的通行能力是限制流量的重要因素，交叉口延誤占車輛整體走行時間的比重也很大，而且這兩項因素具有很強的方向性，以往的最小費用流算法不具有這樣的方向性.本文將交叉口不同方向的通行能力和延誤作為節點權重建立點權網絡，并給出了一個在這類點權網絡中求解最小費用流的最小費用路算法，算法復雜性為O（nmf0）.其中：f0是參數，通常認為f0可取到最大流流值，所以該算法不是多項式算法.不過在此基礎上通過一定的變尺度技術，可以得到該類問題的多項式算法，具體的變尺度方法可參考文獻［6］.其中交叉口延誤可以利用流量數據根據Webster公式等計算［7］，交叉口不同方向的通行能力可以根據飽和流率等模型計算［8］.