易宣齊 胡志華

（上海海事大學(xué)物流研究中心1） 上海 201306） （同濟大學(xué)經(jīng)濟與管理學(xué)院2） 上海 200331）

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

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

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

在應(yīng)急物流管理中，受災(zāi)點的需求有2大類：救援物資需求；傷員轉(zhuǎn)運需求.如果按照救援方向來分，則可分為正向救援和逆向救援.正向救援滿足受災(zāi)點的物資需求，而逆向救援滿足傷員的轉(zhuǎn)運需求.本文基于直運的方式，以最小化運輸時間為目標(biāo)，通過對物資傷員的協(xié)調(diào)轉(zhuǎn)運，可以大大減少救援的時間以及救援成本，達(dá)到很好的救援效果.

1 問題定義

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

圖1 物資和傷員轉(zhuǎn)運流向圖

應(yīng)急救援過程中，時間和運輸車輛都是稀缺資源.時間成本和運輸資源成本是評價調(diào)運方案的主要指標(biāo).短時間內(nèi)要在各個節(jié)點之間充分利用物流資源，進(jìn)行應(yīng)急資源和傷員人員的協(xié)調(diào)調(diào)運，那么協(xié)調(diào)調(diào)運模型和算法的有效性成為應(yīng)急物流的關(guān)鍵.本文就是基于直運的方式以及上述的4種轉(zhuǎn)運流向，在所有的可行路中選出物資和傷員的轉(zhuǎn)運最優(yōu)路線，完成車輛的調(diào)度優(yōu)化.

2 模 型

2.1 兩階段方法

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

圖2 2階段方法

2.2 可行路線生成算法

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

1）集合

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

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

CD?C，表示受災(zāi)節(jié)點的集合.物資轉(zhuǎn)運類需求的節(jié)點構(gòu)成集合M，傷員轉(zhuǎn)運類集合的節(jié)點構(gòu)成集合W.

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

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

3）決策變量

xi∈｛0，1｝ 其中i∈M.當(dāng)xi＝1表示滿足第i個物資轉(zhuǎn)運需求，否則xi＝0.

yi∈｛0，1｝ 其中j∈W.當(dāng)yj＝1表示滿足第j個傷員轉(zhuǎn)運需求，否則yj＝0.

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

算法1 （可行路線生成）

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

輸出 R；RT

處理

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

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

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

2.3 最優(yōu)路線組合優(yōu)化模型

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

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

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

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

3）約束條件

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

3 案 例

3.1 參數(shù)設(shè)置

為了驗證模型的正確性和有效性，采用圖3所示的網(wǎng)絡(luò)配置模擬研究.在該受災(zāi)區(qū)域有50個節(jié)點，每個節(jié)點的坐標(biāo)隨機生成，取值范圍為（0，500），km.其中節(jié)點5為救援中心，其他節(jié)點為潛在受災(zāi)節(jié)點.

圖3 網(wǎng)絡(luò)節(jié)點圖

在這一受災(zāi)區(qū)域中，總共有100個單位需求，各個節(jié)點所對應(yīng)的需求以及需求的類型見表1.其中節(jié)點類型1表示物資轉(zhuǎn)運類需求，2 表示傷員轉(zhuǎn)運類需求.由表1可知，100單位需求中有46單位物資轉(zhuǎn)運類需求，54 單位傷員轉(zhuǎn)運類需求.車速為v＝60km／h.

3.2 結(jié)果及分析

通過數(shù)學(xué)規(guī)劃軟件Gurobi 4.61求解最優(yōu)路線組合優(yōu)化模型，可得100個轉(zhuǎn)運需求可通過54條路線的組合予以滿足，總的運輸時間為373.2 h，路線集合以及表2數(shù)據(jù).

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

表1 節(jié)點的需求

圖4 路線示意圖

表2 路線及時間

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

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

表3 隨機試驗結(jié)果

4 結(jié)束語

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

［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］徐志宇，彭嘉臻，許維勝.應(yīng)急物流的分批配送規(guī)劃及蟻群優(yōu)化求解［J］.計算機工程與應(yīng)用，2011，47（24）：1－3.