基于最小費用流的應急物資運輸問題研究

李廣興 何 珊

(華北電力大學，北京 102206)

1 引言

應急物資就是預防、應對災害過程中為保證各個環節的順利進行而儲存應急資源。應對災害需要有充足的應急物資，并能夠在最短的時間內將物資運輸到災害發生地，以最大程度減少人民生命財產損失。如何制定調運方案，將物資運往指定地點，而且實現運輸成本的最小化和運輸時間的最短，即為運輸問題。與一般線性規劃問題不同，它的約束方程組的系數矩陣具有特殊的結構，這就需要采用不同的甚至更為簡便的求解方法來解決這種在實際工作中經常遇到的問題。

1.1 應急物資運輸問題

從應急救援角度來看早在1984年Kembell Cook對索馬里旱災的救援行動就考慮了應急物流的問題。隨后，研究學者對應急物流問題提出了不同的線性規劃模型來研究這一問題，Knott Rathi等人將大規模應急物流描述為具有時間窗限制的多物品、多模式網絡流問題，并給出了求解方法。Haghani和Oh把大規模災害的救援物資運輸問題作為多物資多模式網絡流模型推導出單目標函數，它以時空網絡概念為基礎，在模型中時變的物資需求和運輸網絡中的載運工具的位移由路徑、運輸、供需執行三種類型連接起來，簡化了多物資多模式多需求導致的復雜網絡流問題。應急物流活動中，物資配送的關鍵是出救點到需求點之間的物流網絡中選擇最優路徑，從而使應急物流活動的耗時最短，成本最低。“應急物流”這一概念是由歐忠文在國內首先提出的，他給出了應急物流的定義，即“以提供突發性自然災害、突發性公共衛生事件等突發性事件所需應急物資為目的，以追求時間效益最大化和災害損失最小化為目標的特種物流活動”。孟參探討了應急物資的庫存控制及運輸配送。謝征等人提出求解各種最小費用流問題的算法。如果最小費用流問題中給定的流值為最大流，則為最小費用最大流問題。寇瑋華、董雪、呂林劍等人利用最小費用流算法，解決了交通運輸網絡中兩個結點之間有流量約束的最小費用最大流分配問題。

1.2 最小費用流的引入

一般情況下，運輸問題可利用以下幾種方法解決：表上作業法、最短線路法和智能搜索算法等。這些研究方法，都能解決運輸網絡的設計問題，但也都各有優缺點。本文試圖利用網絡流中的最小費用流問題的方法，來解決應急物資網絡運輸的問題。

(1)表上作業法。當已知某些物資從出發地運往不同目的地單位物資的運輸費用時，常采用表上作業法，求出使運輸費用最省、時間最短的物資合理調配方案。

然而有時會出現迭代次數較多，工作量繁瑣的情況。

(2)最短路線法。當已知某物資從出發地運往目的地，可有多條運輸路線供選擇，這時，可構造費用網絡圖，用求最短路線的方法，選擇最優的運輸方案，使運輸時間最短、費用最省。對于這類運輸問題，只需畫出各種運輸路線的線路圖及圖上每一條邊(或弧)上的距離或費用(也可以用鄰接矩陣表示)，然后用狄克斯特拉的標號法或鄰接矩陣法求最優運輸路線。

基于此，本文在應急物資運輸網絡問題中試圖尋找一種更加簡便有效的方法來進行求解，因此引入了最小費用流的方法。眾所周知，在一個網絡中每段路徑都有“容量”和“費用”兩個限制的條件下，此類問題的研究試圖尋找出：流量從A到B(A指出救點，B指需求點，出救點可以是多個地點)，如何選擇路徑、分配經過路徑的流量，可以在流量一定的前提下，達到所用的費用最小的要求。如n輛卡車要運送物品，從A地到B地。由于每條路段都有不同的路費要繳納，每條路能容納的車的數量有限制，最小費用流問題指如何分配卡車的出發路徑可以達到費用最低，物品又能全部送到。

因此，本文基于最小費用流的方法，設計使用與供應鏈網絡運輸問題的最小費用流算法，用以處理供應急物資運輸網絡模型，并利用具體例子來驗證該算法的有效性。

2 應急網絡運輸問題描述

應急運輸網絡一般有三級組成，即出救點、中轉中心和需求點。因此，中轉中心選址問題可描述為對于i個出救點經過j個的中轉中心，為k個需求點配送物品，使得在所選路線及路線的流量在滿足配送需求的前提下，使得總費用最低，其運輸網絡結構如圖1所示。

圖1 運輸問題網絡結構

在應急網絡運輸問題中，出救點的個數和需求點的數量和位置以及需求量是固定的，物流中轉中心的地點也是固定的但流經各中轉中心的流量不定，因此，該運輸問題的目標是在需求節點需求量得到滿足的前提下使得總費用最小。

為了方便說明問題并且提高本文算法的通用性，對運輸問題進行如下假設：

(1)從出救點到中轉中心、從中轉中心到需求點之間的運輸距離是已知的；

(2)各個需求點的需求量已知或可預測；

(3)物流經過中轉節點的相關成本已知；

(4)只考慮一種物資的運輸，運輸費用只和運輸量和距離有關且已知；

(5)一個中轉中心可由多個出救點配送物資，一個需求點的需求也可由多個中轉中心提供。

(6)各線路的容量已知。

基于上述的假設條件，接下來進行模型涉及的參數和變量進行定義：

i表示出救點，I為出救點的集合，則i∈I。

j表示中轉中心，J為中轉中心的集合，則j∈J。

k表示需求點，K為需求點的集合，則k∈K。

dij表示從出救點i向中轉中心j的運輸距離(單位：km)。

djk表示從中轉中心j向需求點k的運輸距離(單位：km)。

Qij表示從出救點i向中轉中心j的實際運輸量(單位：t)。

Qjk表示從中轉中心j向需求點k的實際運輸量(單位：t)。

cij表示從出救點i向中轉中心j的最大運輸量(單位：t)。

cjk表示從中轉中心j向需求點k的最大運輸量(單位：t)

Pij表示從出救點i向中轉中心j的單位運輸費率(單位：Yuan/(t·km))。

Pjk表示從中轉中心j向需求點k的單位運輸費率(單位：Yuan/(t·km))。

pj表示中轉中心j的庫存費用。

Mj為第j個中轉中心的最大容量(單位：t)。

Dk為第k個需求點的需求總量(單位：t)。

Ai為出救點i的供應能力(單位：t)。

3 算法設計

運輸問題的目的是要求一個目標函數F，使得總費用W(F)達到最小，本文算法的模型如下：

約束條件(1)為救援物資供應能力限制；

約束條件(2)是中轉中心的物資進出量平衡約束，即運往中轉中心j的物資總量，等于從中轉中心j運出的物資總量。

約束條件(3)為中轉中心的容量限制，即從出救點運往中轉中心j的運輸總量必須小于中轉中心j的最大容量。

約束條件(4)為滿足需求約束，即從所有選中的中轉中心向需求點k的運輸總量必須滿足需求點k的需求。

約束條件(5)和(6)為各線路的容量限制。

另外，本模型涉及的所有參量均為非負參量。

(1)

(2)

(3)

(4)

cjk≥Qjk

(5)

cij≥Qij

(6)

利用最小費用流算法處理該模型，在算法求解過程中，保持總流量保持不變(即出救節點發出的物流不變)，并逐步向最優性條件過渡，直到滿足最優性條件，算法步驟如下：

(1)初始化，根據實際情況構建運輸網絡圖(將各中轉節點當成一條有容量限制的弧)，并確定各供應節點的產量，各中轉中心的容量及各需求節點的需求量，并確定各路線的距離及單位運費率；

(2)在初始網絡中，找到一條滿足條件的可行流；

(3)若在網絡中存在可調整的負代價圈，則轉入(4)，若不存在則轉入(5)；

(4)增量構造新流(保持總流量不變)，轉至(3)；

(5)將當前流保存為最小費用流，輸出。

為使得算法更為迅捷，在第(4)步構造新流過程中，取增量θ=min{容量-正向弧流量；逆向弧流量}。

圖2 算法流程圖

4 算例分析

圖3為一個簡易的公路網絡，為簡便起見，下例只有一個出救節點S和一個需求節點T，并有兩個中轉節點(中轉點1和中轉點2，且1可以向2輸送物資)，且將各路線的距離轉化為單位物流費用表示。每條弧上的數據從左至右分別為單位物流費用、當前流量、容量。出救節點需要將8噸的物資經過兩個中轉節點送到需求節點。

圖3 公路網路線圖

構建應急物資運輸網絡時將中轉節點當成一條有流量限制的弧，該弧費用為該中轉節點的庫存費用，給各節點編號，并給出一個初始可行流：

圖4 初始可行流圖

該初始可行流的運輸總費用W(F)=20+9+4+3+5+18+15=74，尋找到的第一個可調整負代價圈是圈①④②，對該圈增加一個增量θ=2，得到新流如圖5。

圖5 第一次調整結果圖

該調整后的圖的運輸總費用W(F)=12+15+3+5+18+15=68，尋找到的第二個可調整負代價圈是圈③⑤⑥，對該圈增加一個增增量θ=2，得到新流如圖6。

圖6 第二次調整結果圖

該調整后的圖的運輸總費用W(F)=12+15+3+5+4+21+6=66，此時圖中不存在可調整的負代價圈，調整結束，得到最小費用流。相比與初始可行流，

費用由74減少到了68，調整結果較好。

5 結論

應急物資運輸問題的核心是運輸成本最小化，即尋找最佳的運輸方案使得總費用最低，不同的線路流量設計將導致不同的費用，這個過程可以抽象為一個有流量限制的最小費用流問題。本文首先將應急物資運輸網絡問題模型化，使其成為一個總量一定的最小費用流問題；其次，對已有的最小費用流算法進行相應調整，使其適用于應急物資運輸網絡問題；最后，利用具體算例，進行實例分析。利用最小費用流算法解決應急物資運輸網絡問題，能夠減少運輸成本，提高社會效益。本文考慮的情況較為簡單，后繼研究可以對應急物資運輸網絡問題的各項費用進行更精細的劃分，使得算法更符合實際情況。

[1] KemballCook，Stephenson R.LessoninlogisticsfromSomalia[J].Disaster，1984，(8)：57-66.

[2] RathiA.K.，ChurchR.L.，SolankiR.S..Allocating resources to support a multicommodity flow With time windows[J].Logisties and Trans Portation Review，1992，28(2)：167-188.

[3] HaghaniA.，OhS.-C.Formulation and solution of a multicommodity，multimodal network Flow model for disaster relief operations[J].Transportation Research Part A，1996，30(3)：231-250.

[4] 歐忠文，王會云，姜大立等.應急物流[J].重慶大學學報，2004，27(3)：164-166.

[5] 孟參等.應急物流系統運作流程分析及其管理[J].物流技術，2006，(9)：15-17.

[6] 謝政，湯澤瀅.帶模糊約束的最小費用流問題[J].模糊系統與數學，1999，13(2)：940-941.

[7] 寇瑋華，董雪，呂林劍.交通運輸網絡中兩個結點間有流量約束的最小費用最大流算法[J].蘭州交通大學學報，2009，28(6)：104-109.