應急救援物資與傷員協調轉運的兩階段調度優化模型研究＊

易宣齊 胡志華

（上海海事大學物流研究中心1） 上海 201306） （同濟大學經濟與管理學院2） 上海 200331）

災害事件給人們的生命、財產、安全造成巨大的傷害，為了減少這些災害事件對人類所產生的影響，越來越多的研究人員對此進行研究［1－3］.應急物流是為了滿足應急情形下受災群體緊急需求，對從供給點到需求點的救援物資、信息及服務進行計劃、管理與控制的過程［4］.由于災害事件發生的時間和地點，以及受災程度難以預測，因此，應急物流的主要挑戰有［5］：運輸與需求的不確定性；復雜的溝通和協調；難以實現高效及時的交貨；有限資源無法滿足大規模的需求.由于應急物流的特殊性，應急物流更強調物流效率與社會效益，而非經濟效益.

多供應點多需求點的運輸問題可以按需求量大小分為兩類：一類是每個點需求量較小，車輛每次要經過多個點，主要考慮怎樣安排每輛車對需求點的訪問順序以及由此構成的訪問路線，屬于車輛路徑問題［6］；另一類是由于供需點的供應量和需求量都很大，一般要往返多次才能完成，車輛每次都從供應點直達需求點，主要關注各供應點向各個需求點分配貨物的比例問題，成為多點運輸問題［7］.

應急物流運輸優化的目標主要分2類：配送時間或配送成本的最小化［8－9］；未滿足需求最小化，如最小化所有救援物資需求和傷員轉運需求的未滿足率［10］.為了避免有些災點在全局優化中被忽略，徐志宇，彭嘉臻等則在總的成本最小、需求未滿足率最低的基礎上加上了失衡度最小這一目標［11］.

在應急物流管理中，受災點的需求有2大類：救援物資需求；傷員轉運需求.如果按照救援方向來分，則可分為正向救援和逆向救援.正向救援滿足受災點的物資需求，而逆向救援滿足傷員的轉運需求.本文基于直運的方式，以最小化運輸時間為目標，通過對物資傷員的協調轉運，可以大大減少救援的時間以及救援成本，達到很好的救援效果.

1 問題定義

受災點的需求可以劃分為救援物資需求和傷員轉運需求.它們代表2個方向的資源流動，物資是從救援中心到受災點，而傷員是從受災點到受災點.因為在實際救援中，受災點對各種物資的需求量以及傷員的轉運量是巨大的、不均勻的且具有動態性，本文把受災點的兩種需求單元化，即需求的量以車為單位.車輛的運輸方式是直運，因此，節點之間的物流運輸情況有圖1所示的4種類型.流向1中，車輛從救援中心搭載物資到受災點，然后載傷員返回；流向2中，車輛從救援中心搭載物資到受災點，然后空車返回；流向3中，車輛從救援中心空車前往受災點搭載傷員然后返回救援中心；流向4中，車輛從救援中心搭載物資到受災點，然后空車趕往最近的受災點搭載傷員返回救援中心.

圖1 物資和傷員轉運流向圖

應急救援過程中，時間和運輸車輛都是稀缺資源.時間成本和運輸資源成本是評價調運方案的主要指標.短時間內要在各個節點之間充分利用物流資源，進行應急資源和傷員人員的協調調運，那么協調調運模型和算法的有效性成為應急物流的關鍵.本文就是基于直運的方式以及上述的4種轉運流向，在所有的可行路中選出物資和傷員的轉運最優路線，完成車輛的調度優化.

2 模 型

2.1 兩階段方法

應急物流模型主要分成2階段：在第一階段，基于物資和傷員轉運的4種流向，生成所有的可行路線；在第二階段，選擇部分路線，覆蓋所有需求，且最小化總路線的數量和總的運輸時間.由此可看出，第二階段選擇的最優路線是第一階段生成的可行路線的子集，見圖2.為了方便和有效研究本文的2階段問題，問題通過以下條件進一步界定：（1）救援中心的物資供應充足，能夠滿足所有受災點的需求；（2）救援中心有足夠的車輛，且所有的車輛的出發點和終點都是救援中心；（3）所有救援車輛的速度是相同的，且救援能力也一致；（4）所有的節點之間能夠相通；（5）車輛在節點的滯留等待時間不計；（6）通過單元化運輸滿足需求.

圖2 2階段方法

2.2 可行路線生成算法

路線生成算法主要是根據直運的規則以及物資和傷員轉運的4種流向，生成所有的可行路線的一種算法.以下簡要說明2階段方法中各符號所代表的含義.

1）集合

定義C＝｛1，2，…，NC｝為所有節點的集合.其中：NC 為節點數量，包括受災點和救援中心.CS∈C，表示救援中心.

定義D＝｛1，2，…，ND｝為所有需求的集合，共有ND 個需求.需求的類型有2 種，包括救援物資轉運需求和傷員轉運需求.其中1為物資轉運類需求；2為傷員轉運類需求.

CD?C，表示受災節點的集合.物資轉運類需求的節點構成集合M，傷員轉運類集合的節點構成集合W.

定義R＝｛1，2，…，NR｝為所有可行路線的集合，一共有NR 條.

2）參數 v為車輛的速度；RTk（k∈R）為第k條路線的時間.

3）決策變量

xi∈｛0，1｝ 其中i∈M.當xi＝1表示滿足第i個物資轉運需求，否則xi＝0.

yi∈｛0，1｝ 其中j∈W.當yj＝1表示滿足第j個傷員轉運需求，否則yj＝0.

可行路線生成算法見算法1.

算法1 （可行路線生成）

輸入 C，CD，CS，D，M，W；v

輸出 R；RT

處理

步驟2 由xi＋yj＝1，?i∈M，j∈W，可得到圖1中流向為（2）、（3）的滿足一個需求的轉運路線ND 條.

步驟3 由xi＋yj＝2，?i∈M，j∈W，可得到圖1中流向為（1）（4）的滿足兩個需求的轉運路線m·（ND－m）條.其中n為物資轉運需求的數量.至此，得到了路線集合R，一共有NR 條路線，且NR＝ND＋m·（ND－m）.

步驟4 根據公式t＝d／v，求出車輛在每條路線上的轉運時間，于是可得參數RTk，k∈R.

2.3 最優路線組合優化模型

1）決策變量 路線選擇的依據是要使所有的轉運需求都能夠得到滿足，且使總的車輛在途時間最短.在第二階段，新增以下兩個決策變量.

（1）RDk，j∈｛0，1｝：當RDk，j＝1 時表示第j∈D個需求安排在路線k∈R 中，否則RDk，j＝0.

（2）zk∈｛0，1｝：當zk＝1 時表示路線k∈R被選擇作為最優路線之一，否則zk＝0.

2）目標函數 本文應急救援物資與傷員轉運的目標是所有車輛的運輸時間最小化.而總的車輛運輸時間是每條路線的運輸時間之和.這是一個選擇路線的過程，從所有的路線中選擇部分的路線能夠滿足所有的需求，且總的運輸時間最少.

3）約束條件

式（2）表示每一個需求都必須得到滿足.通過最優路線組合優化模型，選擇出了最優路線集合，在應急物流救援中，能夠以最少的車輛在途時間完成所有的需求.

3 案 例

3.1 參數設置

為了驗證模型的正確性和有效性，采用圖3所示的網絡配置模擬研究.在該受災區域有50個節點，每個節點的坐標隨機生成，取值范圍為（0，500），km.其中節點5為救援中心，其他節點為潛在受災節點.

圖3 網絡節點圖

在這一受災區域中，總共有100個單位需求，各個節點所對應的需求以及需求的類型見表1.其中節點類型1表示物資轉運類需求，2 表示傷員轉運類需求.由表1可知，100單位需求中有46單位物資轉運類需求，54 單位傷員轉運類需求.車速為v＝60km／h.

3.2 結果及分析

通過數學規劃軟件Gurobi 4.61求解最優路線組合優化模型，可得100個轉運需求可通過54條路線的組合予以滿足，總的運輸時間為373.2 h，路線集合以及表2數據.

由表1和表2可知：路線5只滿足了一種類型的需求，車輛從5號救援中心空車到34號節點然后搭載傷員返回5號救援中心；路線9滿足了兩種類型的需求，車輛從5號救援中心搭載物資到39號節點，然后空車感到9 號節點，最后從9號節點搭載傷員返回5號救援中心；路線11也滿足了兩種類型的需求，車輛從5號救援中心搭載物資到22號節點，然后從22號節點搭載傷員返回5號救援中心.示意圖見圖4.

表1 節點的需求

圖4 路線示意圖

表2 路線及時間

通過對表2數據分析可得以下結論：（1）滿足100個目標需求，需要54條路線；（2）所有路線中，滿足2種需求且2種需求在同一節點的有28條.滿足2種需求但這2種需求不在同一節點的路線有18條.只滿足一種需求且需求為傷員的路線有8條，只滿足一種需求且需求為物資的路線為0條.由此可知為了滿足車輛在途中的總時間最小化，每條路線會盡量滿足2種需求；（3）所有路線中，最少的運輸時間為1.9h，最大為13.8 h.如果車輛較多，則可派54輛車來完成這100單位需求.如果車輛不足，且兩種需求不緊急，則可派少于54輛車來運輸，因為車輛返回后可以繼續作業來滿足其他需求.

通過多次取隨機數值實驗可得表3數據，其中實驗1～4采用原來的節點網絡布局，而實驗5～8則采用新的節點網絡布局.通過表中數據可知，在節點與道路較為均勻分布的物流網絡中，轉運路線的數量主要取決于兩類需求中轉運量較大的需求.根據實驗3和實驗4，可以發現取不同的節點作為救援中心時，總的運輸時間會有較大的差異.通過上文的模型，對所有候選節點進行模擬計算，以總時間最短為目標，可以解決救援中心的選址問題或者災區的救援分區問題.

表3 隨機試驗結果

4 結束語

本文討論了應急救援物資與傷員協調轉運問題.基于直運的方式，研究了一個救援中心，多個受災點多單位需求的轉運問題，提出了一種2階段的求解方法.第一階段根據直運的要求以及4種轉運流向生成所有的可行路線；第二階段在滿足所有的需求約束下，通過最小化總車輛運輸時間選擇最優路線集合.在案例研究部分，對隨機生成的50個節點和100個需求，得到54條路線構成的最優運輸方案，驗證了模型的正確性和有效性.在未來的研究中，可以進一步優化應急救援中各種資源的整合調度.多個救援中心，則涉及分區優化問題；基于直運與帶時間窗的VRP 相結合，更能有效地實施救援；物資與傷員的轉運與優先級相結合等方面進行拓展研究.

［1］?ZDAMAR L，EKINCI E，Kü?üKYAZICI B.Emergency logistics planning in natural disasters［J］.Annals of Operations Research，2004，129（1－4）：217－245.

［2］ALTAY N，GREEN W G.OR／MS research in dis－aster operations management［J］.European Journal of Operational Research，2006，175（1）：475－493.

［3］CAUNHYE A M，NIE X，POKHAREL S.Optimization models in emergency logistics：A literature review［J］.Socio－Economic Planning Sciences，2011，46（1）：1－10.

［4］SHEU J B.Challenges of emergency logistics management［J］.Transportation Research Part E：Logistics and Transportation Review，2007，43（6）：655－659.

［5］BALCIK B，BEAMON B M.Facility location in humanitarian relief［J］.International Journal of Logistics：Research and Applications，2008，11（2）：101－121.

［6］SHEN Z，DESSOUKY M M，ORDóEZ F.A twostage vehicle routing model for large－scale bioterrorism emergencies［J］.Networks，2009，54（4）：255－269.

［7］QIANG G，RAJAN B.Allocation and reallocation of ambulances to casualty clusters in a disaster relief operation［J］.IIE Transactions，2007，39（1）：27－39.

［8］CAMPBELL A M，VANDENBUSSCHE D，H W.Routing for relief efforts［J］.Transportation Science，2008，42（2）：127－145.

［9］BALCIK B，BEAMON B，SMILOWITZ K.Last mile distribution in humanitarian relief［J］.Journal of Intelligent Transportation Systems，2008，12（2）：51－63.

［10］YI W，KUMAR A.Ant colony optimization for disaster relief operations［J］.Transportation Research Part E：Logistics and Transportation Review，2007，43（6）：660－672.

［11］徐志宇，彭嘉臻，許維勝.應急物流的分批配送規劃及蟻群優化求解［J］.計算機工程與應用，2011，47（24）：1－3.