王玲玲

（廣西工學(xué)院 汽車工程系，廣西 柳州 545006）

1 概述

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

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

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

2 建立模型

2.1 問題的假設(shè)條件

（1）物資的流向都是從應(yīng)急物流中心流向受災(zāi)點，物資可以混裝。

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

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

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

（5）應(yīng)急物流中心與各受災(zāi)地點的位置已知。

2.2 模型的數(shù)學(xué)描述

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

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

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

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

建立應(yīng)急配送車輛調(diào)度的數(shù)學(xué)模型如下。

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

3 模型求解

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

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

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

（2）確定個體適應(yīng)度的量化評價方法，即確定出由目標(biāo)函數(shù)值到個體適應(yīng)度的轉(zhuǎn)換規(guī)則。

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

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

4 實例分析

4.1 實例數(shù)據(jù)

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

表1 各應(yīng)急物流中心坐標(biāo)及儲備參數(shù)

4.2 實例求解

計算應(yīng)急配送網(wǎng)絡(luò)中各受災(zāi)點間和應(yīng)急物流中心間的距離dij。

4.2.1 第一階段——直送調(diào)度方案

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

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

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

4.2.2 第二階段——分送調(diào)度方案

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

表2 各受災(zāi)點坐標(biāo)及需求參數(shù)

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

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

表3 應(yīng)急調(diào)度方案

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

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

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

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

運用 C 語言編制程序?qū)崿F(xiàn)上述算法。經(jīng)過計算機運算得到最優(yōu)解：最小運輸距離為378km；車輛數(shù)為12輛。對應(yīng)染色體個體為(0，13，17，8，19，6，20，0，10，12，15，21，18，0，4，11，9，22，14，0)。

采用兩階段啟發(fā)式算法得到最優(yōu)應(yīng)急調(diào)度方案，如表3所示。

5 結(jié)束語

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

：

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

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

[3] 唐偉勤，張 敏，張 隱. 大規(guī)模突發(fā)事件應(yīng)急物資調(diào)度的過程模型[J]. 中國安全科學(xué)學(xué)報，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]陳明華，李迎秋，羅耀琪. 應(yīng)急物流車輛調(diào)配問題的研究[J]. 計算機工程與應(yīng)用，2009，45(24)：194-197，245.

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

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

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

[9]胡運權(quán). 運籌學(xué)教程[M]. 北京：清華大學(xué)出版社，1998.

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