多出救點(diǎn)應(yīng)急調(diào)度研究

王玲玲

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

1 概述

近幾年來，我國先后爆發(fā)了非典、禽流感、雪災(zāi)及地震等突發(fā)公共事件。面對時(shí)有發(fā)生的各類突發(fā)事件，積極開展應(yīng)急物流調(diào)度研究，在短時(shí)間內(nèi)高效地調(diào)集相關(guān)物資，并將其快速運(yùn)送、及時(shí)發(fā)放，對于提高應(yīng)急響應(yīng)能力、減少災(zāi)害影響、降低生命財(cái)產(chǎn)損失具有重要的意義。應(yīng)急物資大致可分為滿足搶救需求、滿足災(zāi)民生活需求、滿足災(zāi)后初期重建需求等3類。應(yīng)急物流是以提供應(yīng)急物資為目的，以追求時(shí)間效益最大化和災(zāi)害損失最小化為目標(biāo)的特殊物流活動(dòng)。應(yīng)急物流具有突發(fā)性、非常規(guī)性和不確定性等特點(diǎn)。目前，國內(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)點(diǎn)數(shù)目不確定，各點(diǎn)的地理?xiàng)l件比較復(fù)雜，分布不均勻，應(yīng)急物資需求存在差異，而且對時(shí)間都有一定的限制期限。在現(xiàn)有的研究成果中，針對單個(gè)出救點(diǎn)-多個(gè)受災(zāi)點(diǎn)問題，建立了以運(yùn)輸里程最短為目標(biāo)函數(shù)的數(shù)學(xué)模型[5]，以及運(yùn)輸距離最短與車輛數(shù)最少的優(yōu)化調(diào)度模型[6]；針對多個(gè)出救點(diǎn)-單個(gè)受災(zāi)點(diǎn)問題，建立了在應(yīng)急時(shí)間最早的前提下出救點(diǎn)數(shù)目最少和限制期限時(shí)間內(nèi)出救點(diǎn)最少的應(yīng)急模型[7]，以及以應(yīng)急出救點(diǎn)數(shù)最少、應(yīng)急開始時(shí)間最早的兩層優(yōu)化數(shù)學(xué)模型[8]。上述模型大多都假設(shè)應(yīng)急物流中心倉庫存放的貨物數(shù)量充足，或者默認(rèn)其能夠完全滿足受災(zāi)點(diǎn)對物資的需求，而對于多個(gè)出救點(diǎn)-多個(gè)受災(zāi)點(diǎn)應(yīng)急物流配送問題的研究較少。但是，在實(shí)際中可能會(huì)發(fā)生由于應(yīng)急庫存量不足，單個(gè)應(yīng)急中心無法滿足應(yīng)急點(diǎn)貨物需求數(shù)量的情況。

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

2 建立模型

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

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

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

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

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

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

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

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

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

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

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

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

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

3 模型求解

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

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

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

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

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

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

4 實(shí)例分析

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

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

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

4.2 實(shí)例求解

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

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

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

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

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

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

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

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

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

（3）適應(yīng)度函數(shù)。該目標(biāo)函數(shù)是極小值問題，公式⑼表明如果應(yīng)急物流中心與受災(zāi)點(diǎn)之間運(yùn)輸時(shí)間或需求量不滿足，則賦予其一個(gè)很大的 M 值。該過程已經(jīng)包括判斷各種節(jié)點(diǎn)組合的運(yùn)輸車輛的時(shí)間約束與載重約束條件，所以該函數(shù)可以很好地代替各染色體的適應(yīng)度。設(shè)Vg為染色體，F(xiàn)g為染色體Vg對應(yīng)的適應(yīng)度。Z′為群體中最好染色體的目標(biāo)值(按公式⑼計(jì)算得到的目標(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）采用隨機(jī)取值的方法，在解空間里隨機(jī)取C個(gè)個(gè)體作為初始群體。

（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）運(yùn)行參數(shù)。取群體規(guī)模50、Pc交叉概率0.55、Pm變異概率0.006、終止進(jìn)化代數(shù)取500。

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

運(yùn)用 C 語言編制程序?qū)崿F(xiàn)上述算法。經(jīng)過計(jì)算機(jī)運(yùn)算得到最優(yōu)解：最小運(yùn)輸距離為378km；車輛數(shù)為12輛。對應(yīng)染色體個(gè)體為(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)度問題特點(diǎn)的基礎(chǔ)上，建立雙目標(biāo)數(shù)學(xué)模型，考慮運(yùn)輸車輛載重和運(yùn)輸時(shí)間的限制，將受災(zāi)點(diǎn)物資需求數(shù)量與應(yīng)急物流中心儲(chǔ)備的物資數(shù)量作為應(yīng)急調(diào)度的影響因素對問題進(jìn)行求解。根據(jù)受災(zāi)點(diǎn)的物資需求量大小，將受災(zāi)點(diǎn)按配送方式分為整車直送和分送兩類：對于整車直送受災(zāi)點(diǎn)，找到符合條件的最近應(yīng)急物流中心，并求解出最短路徑即可確定直送調(diào)度方案；對于分送配送受災(zāi)點(diǎn)，采用遺傳算法求解分送調(diào)度方案。最后運(yùn)用 C 語言編制程序完成模型的求解。

：

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

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

[3] 唐偉勤，張 敏，張 隱. 大規(guī)模突發(fā)事件應(yīng)急物資調(diào)度的過程模型[J]. 中國安全科學(xué)學(xué)報(bào)，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]. 計(jì)算機(jī)工程與應(yīng)用，2009，45(24)：194-197，245.

[6]張?jiān)ＨA，潘 郁. 基于蟻群算法的應(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é)報(bào)，2006，26(z1)：157-160.

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

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