多出救點應急調度研究

王玲玲

（廣西工學院 汽車工程系，廣西 柳州 545006）

1 概述

近幾年來，我國先后爆發了非典、禽流感、雪災及地震等突發公共事件。面對時有發生的各類突發事件，積極開展應急物流調度研究，在短時間內高效地調集相關物資，并將其快速運送、及時發放，對于提高應急響應能力、減少災害影響、降低生命財產損失具有重要的意義。應急物資大致可分為滿足搶救需求、滿足災民生活需求、滿足災后初期重建需求等3類。應急物流是以提供應急物資為目的，以追求時間效益最大化和災害損失最小化為目標的特殊物流活動。應急物流具有突發性、非常規性和不確定性等特點。目前，國內外對應急物流系統的研究主要有應急車輛數的配置[1]、應急資源調配[2]和應急配送車輛調度[3-8]等。

應急配送車輛的調度方案對提高應急物流服務水平有著重要的影響。在應急物流調度中受災點數目不確定，各點的地理條件比較復雜，分布不均勻，應急物資需求存在差異，而且對時間都有一定的限制期限。在現有的研究成果中，針對單個出救點-多個受災點問題，建立了以運輸里程最短為目標函數的數學模型[5]，以及運輸距離最短與車輛數最少的優化調度模型[6]；針對多個出救點-單個受災點問題，建立了在應急時間最早的前提下出救點數目最少和限制期限時間內出救點最少的應急模型[7]，以及以應急出救點數最少、應急開始時間最早的兩層優化數學模型[8]。上述模型大多都假設應急物流中心倉庫存放的貨物數量充足，或者默認其能夠完全滿足受災點對物資的需求，而對于多個出救點-多個受災點應急物流配送問題的研究較少。但是，在實際中可能會發生由于應急庫存量不足，單個應急中心無法滿足應急點貨物需求數量的情況。

現結合實際情況，針對應急系統中多出救點-多受災點、多種物資應急配送問題，建立模型使運輸車輛數最少、總運輸距離最短，最大程度地節省物流資源。按照受災點物資需求量，對應急物資采用多種方式配送，分兩階段基于遺傳算法求解調度方案，力求得到可操作的行車路線近似最優解。

2 建立模型

2.1 問題的假設條件

（1）物資的流向都是從應急物流中心流向受災點，物資可以混裝。

（2）應急物流中心有多個，儲備的各類物資數量及配送車輛數一定。

（3）每輛車僅屬于一個物流中心，完成任務后返回其所屬應急物流中心。

（4）采用同一車型運輸，車輛的容積和額定載重量一定。

（5）應急物流中心與各受災地點的位置已知。

2.2 模型的數學描述

N＝(A，B，E，K，T，D)代表應急物流調度的網絡模型。其中，A 代表應急物流中心節點集合{1,2,…，m}；B 代表受災點節點集合{m+1，…，m+n }；E 代表網絡的弧集合{(i，j)｜i，j∈C＝A∪B，i≠j }；K 表示各應急物流中心運輸車輛集合{K1，…，Kp，…，Km}，其中Kp表示應急物流中心 p 的可用車輛數集合，k 表示應急運輸車輛，且k∈Kp∈K；T 代表網絡中各弧上運輸時間集合{t?｜(i，j)∈E}；D 代表運輸距離集合{dij｜(i，j)∈E }。

L 表示應急物資的種類集合{1，2，…，h}，l表示應急物資，且有l∈L；表示受災點 j 對應急物資 l 的需求量；表示應急物流中心 i 對應急物資l 的供應量；W 表示運輸車輛的額定裝載量；Fl表示應急物資 l 的重量(體積)系數。

m 個應急物流中心將儲備的應急物資向服務區域內的 n 個受災點運送，所有物資在接到運輸指令后 T 時間內必須送達，求滿足運輸需求的條件下，使運輸成本最低、車輛數最少的配送方案。

為建立調度模型，將模型中涉及的二進制決策變量定義如下。

建立應急配送車輛調度的數學模型如下。

上述模型中，公式⑴表示目標函數為求最短應急運輸距離；公式⑵表示目標函數為使用最少的運輸車輛；約束條件⑶表示如果受災點 j 由車輛 k 配送，則車輛 k 至少要訪問受災點 j 一次；約束條件⑷表示每個應急物流中心可用車輛數的限制；約束條件⑸表示每輛車裝貨不超過其額定載重；約束條件⑹表示車輛配送的物資總量不超過庫存量；約束條件⑺表示每輛車運輸時間不超過T，即所有貨物都在時間 T 內送達；約束條件⑻表示車輛從所屬應急物流中心出發返回該物流中心。

3 模型求解

該問題的求解主要包括以下3個方面。首先，劃分各應急物流中心的配送范圍，即確定每個應急物流中心需要配送的受災點。其次，分配應急車輛的配送任務。最后，制定各車輛的運輸線路，使行程最短。這樣由 m 個應急物流中心與 n 個受災點組成的應急運輸調度方案，屬于混合整數規劃問題。隨著規模的擴大，不僅模型解的搜索空間急劇擴大，而且需要兩兩比較解的運輸距離及運輸車輛數，所以目標函數計算過程比較復雜。針對模型的特點，設計兩階段算法如下。

第二階段：對于物資需求量較小或有剩余物資的受災點，采用分送式配送。用遺傳算法求解獲得分送式配送的應急調度方案。遺傳算法的基本步驟如下[10]。

（1）確定表示可行解的染色體編碼方法及搜索空間。

（2）確定個體適應度的量化評價方法，即確定出由目標函數值到個體適應度的轉換規則。

（3）設計遺傳算子，確定出選擇運算、交叉運算、變異運算等遺傳算子的具體操作方法。

（4）確定有關運行參數，包括群體規模N、交叉概率Pc、變異概率Pm和終止進化代數等。

4 實例分析

4.1 實例數據

柳州市7月連降大雨，河流沿線多處受災，急需從柳南、柳北、魚峰的3個應急物流中心調運儲備的2類應急物資。2類物資的重量系數分別為F1＝0.2t/件，F2＝0.3t/件。對3個物流中心和19個受災地點以城市應急物流指揮中心為原點，得到其相對坐標位置，對各物流中心和受災點順序編號。3個應急物流中心相關坐標及儲備參數如表1所示，19個受災點坐標及需求參數如表2所示。每個物流中心的車輛數均為8輛。要求所有物資在2h內必須送達，車輛平均速度為50km/h。運送車輛的載重量為10t。試制定一個應急調度方案，使參與運輸車輛數最少，總行程最短。

表1 各應急物流中心坐標及儲備參數

4.2 實例求解

計算應急配送網絡中各受災點間和應急物流中心間的距離dij。

4.2.1 第一階段——直送調度方案

（2）尋找受災點中符合條件1≥βj≥β 的點記為R1，采用整車直送配送。經過計算 Q5＝9.0t，Q7＝9.6t，Q16＝9.5t；由β5＝0.90，β7＝0.96，β16＝0.95可知，受災點5、7、16符合此條件，采用整車直送。

（3）判斷 βj＞1＞β 的受災點記為R2，將該受災點的物資總重表示為Qj＝QZj＋QSj。按照車輛額定載重將QZj采用整車直接運送，剩余物資QSj采用分送方式配送。算例中受災點9、14、18超重，先采用整車直接運送部分物資到這些受災點，剩余物資QS9＝0.5t，QS14＝5.5t，QS18＝4.2t，轉入第二階段配送。

（4）確定各直送受災點對應的應急物流中心。若直送受災點共有 R 個，則 R＝R1＋R2。對 R 個受災點，依次尋找符合供給量和運輸時間條件的最近應急物流中心。應用Dijkstra算法計算各直送受災點與所服務的應急物流中心之間的最短路徑。經計算，實例中應急物流中心1派1輛車為受災點7配送，應急物流中心2派2輛車為受災點5、18運送物資，應急物流中心3派3輛車為受災點9、14、16運送物資。

4.2.2 第二階段——分送調度方案

（1）染色體編碼方式。結合模型，m 個應急物流中心 n 個受災點中分送的受災點為n－R1個。采用受災點序號，以自然數進行編碼，代碼串的長度為m＋1＋n－R1。對于每個應急物流中心的配送點范圍，順序地用多個“0……0”隔開表示，即編碼中有m＋1個“0”，其他數字為n－R1個受災點的序號。主要考慮車輛的載重約束和線路運輸時間約束，根據編碼中受災點序號的順序，分配各應急物流中心的配送任務和車輛對受災點的配送順序。這種編碼方式線路內是有序的，若交換其中任何兩個位置，都會使配送的范圍和順序發生改變，從而使目標函數值發生改變。實例中3個應急物流中心、19個受災點中采用分送的有16個點，因此染色體長度為20。初始種群隨機生成，例如(0，4，6，8，9，10，0，11，12，13，14，15，0，17，18，19，20，21，22，0)表示物流中心1為受災點4、6、8、9、10配送，物流中心2為受災點11、12、13、14、15配送，物流中心3為受災點17、18、19、20、21、22配送。

表2 各受災點坐標及需求參數

（2）約束條件的處理。采用罰函數的方法來處理約束條件，以確保那些符合約束條件而較優的個體有較大的生存機會。把各種約束條件加入目標函數中得到公式⑼。

（3）適應度函數。該目標函數是極小值問題，公式⑼表明如果應急物流中心與受災點之間運輸時間或需求量不滿足，則賦予其一個很大的 M 值。該過程已經包括判斷各種節點組合的運輸車輛的時間約束與載重約束條件，所以該函數可以很好地代替各染色體的適應度。設Vg為染色體，Fg為染色體Vg對應的適應度。Z′為群體中最好染色體的目標值(按公式⑼計算得到的目標函數值)，Zg為染色體Vg對應的目標值。由于Z值是非負，適應度函數表示為：Fg＝Z′/Zg。經過處理，染色體越優對應的適應度值越大。

表3 應急調度方案

（4）采用隨機取值的方法，在解空間里隨機取C個個體作為初始群體。

（5）遺傳算子。①選擇算子。采用指數排序選擇方法，其基本思想是將染色體根據其適應值大小從好到壞排序，按照它們在順序中的位置而不是原適應值指定選擇概率。與常用的轉輪式選擇相比可使染色體之間保持合理的差距。設群體大小為N，q 表示最好染色體的選擇概率，r 為染色體在排序中的位置，最好染色體的序數為1；種群中排在第 r 位的染色體選擇概率 Pr為：Pr＝q′(1－q)r-1。式中：r＝1，2，…，N；q′＝q/{1－(1－q)N}。②交叉算子。采用部分匹配交叉算子。變異算子：采用連續多次對換作為變異算子。

（6）運行參數。取群體規模50、Pc交叉概率0.55、Pm變異概率0.006、終止進化代數取500。

（7）終止條件。①若算法迭代到第500代，算法終止；②若有連續10代最佳染色體相同，算法終止。

運用 C 語言編制程序實現上述算法。經過計算機運算得到最優解：最小運輸距離為378km；車輛數為12輛。對應染色體個體為(0，13，17，8，19，6，20，0，10，12，15，21，18，0，4，11，9，22，14，0)。

采用兩階段啟發式算法得到最優應急調度方案，如表3所示。

5 結束語

在分析應急配送車輛調度問題特點的基礎上，建立雙目標數學模型，考慮運輸車輛載重和運輸時間的限制，將受災點物資需求數量與應急物流中心儲備的物資數量作為應急調度的影響因素對問題進行求解。根據受災點的物資需求量大小，將受災點按配送方式分為整車直送和分送兩類：對于整車直送受災點，找到符合條件的最近應急物流中心，并求解出最短路徑即可確定直送調度方案；對于分送配送受災點，采用遺傳算法求解分送調度方案。最后運用 C 語言編制程序完成模型的求解。

：

[1]劉 楊，馬 立，云美萍，等. 基于隨機過程的城市應急車輛數量配置模型[J]. 中國安全科學學報，2008，18(5)：46-48.

[2]記國君，朱彩虹. 突發事件應急物流中資源配送優化問題研究[J]. 中國流通經濟，2007，21(3)：18-21.

[3] 唐偉勤，張 敏，張 隱. 大規模突發事件應急物資調度的過程模型[J]. 中國安全科學學報，2009，19(1)：33-37.

[4]Ozdamar L. Emergency logistics planning in natural disasters[J]. Annals of Operation Research，2004，129(3)：218-219.

[5]陳明華，李迎秋，羅耀琪. 應急物流車輛調配問題的研究[J]. 計算機工程與應用，2009，45(24)：194-197，245.

[6]張裕華，潘 郁. 基于蟻群算法的應急物流配送車輛調度研究[J]. 物流科技，2009，32(5)：47-50.

[7]劉春林，何建敏，施建軍. 一類應急物資調度的優化模型研究[J]. 中國管理科學，2001，9(3)：29-36.

[8]李連宏，王永軍，李俊峰，等. 多資源非恒定消耗應急調度優化模型研究[J]. 北京理工大學學報，2006，26(z1)：157-160.

[9]胡運權. 運籌學教程[M]. 北京：清華大學出版社，1998.

[10]陳國良，王煦法，莊鎮泉，等. 遺傳算法及其應用[M]. 北京：人民郵電出版社，2001.