基于軟計(jì)算的救災(zāi)物資多配送中心調(diào)度問(wèn)題研究

張延良

[摘要]自然災(zāi)害的發(fā)生不可避免，但災(zāi)難發(fā)生后對(duì)應(yīng)急物資的合理調(diào)度可以有效降低災(zāi)難造成的生命和財(cái)產(chǎn)損失?；趯?duì)救災(zāi)物資調(diào)配特點(diǎn)的分析，建立救災(zāi)物資多配送中心調(diào)度問(wèn)題的數(shù)學(xué)模型，給出基于軟計(jì)算的求解方法，得出可在災(zāi)難發(fā)生后根據(jù)每種物資需求的緊急程度確定配送線路和配送時(shí)間，同時(shí)引入多配送中心更符合災(zāi)后物資調(diào)運(yùn)實(shí)際情況的結(jié)論，希望能為應(yīng)急物資調(diào)度問(wèn)題的相關(guān)研究提供一定借鑒。

[關(guān)鍵詞]軟計(jì)算；救災(zāi)物資；配送中心；調(diào)度

[中圖分類號(hào)]F259.21[文獻(xiàn)標(biāo)識(shí)碼]A[文章編號(hào)]

2095-3283（2015）12-0119-03

我國(guó)地域廣闊，地質(zhì)構(gòu)造復(fù)雜，各種自然災(zāi)害頻發(fā)，如2002年蔓延全國(guó)的“非典”、2008年南方極端寒冷天氣、2008年5月12日汶川大地震、2010年4月14日玉樹(shù)地震，2013年4月20日廬山地震等重大自然災(zāi)害時(shí)有發(fā)生。一些重大災(zāi)難的發(fā)生都是隨機(jī)和不可預(yù)見(jiàn)的，會(huì)造成大量的人員傷亡和財(cái)產(chǎn)損失。在災(zāi)害發(fā)生后，如何有效降低災(zāi)難造成的人員傷亡和財(cái)產(chǎn)損失攸關(guān)重要，特別是如何將醫(yī)藥用品、糧食和帳篷等必要的應(yīng)急物資及時(shí)調(diào)配到位是避免災(zāi)難進(jìn)一步擴(kuò)大的重要保證。

一、救災(zāi)物資調(diào)配的特點(diǎn)

救災(zāi)物資調(diào)配與傳統(tǒng)物資調(diào)配比較存在很大差異，在災(zāi)難發(fā)生和發(fā)展的不同階段，對(duì)于不同救災(zāi)物資的需求也是各不相同?？傮w來(lái)看，救災(zāi)物資的調(diào)配具有以下特點(diǎn)：

1.突發(fā)性。災(zāi)難的發(fā)生往往都是突發(fā)事件，其發(fā)生時(shí)間和發(fā)生地點(diǎn)大多不可預(yù)測(cè)，這決定了救災(zāi)物資調(diào)配最主要的特點(diǎn)就是突發(fā)性。

2.不確定性。災(zāi)難發(fā)生的突發(fā)性導(dǎo)致短時(shí)間內(nèi)災(zāi)區(qū)情況不能確定，從而使救災(zāi)物資的需求地點(diǎn)、需求數(shù)量和需求種類等具有不確定性。

3.時(shí)限性。在災(zāi)難發(fā)生的不同時(shí)期，對(duì)物資配送的時(shí)限要求也完全不同。例如，災(zāi)難發(fā)生前期對(duì)應(yīng)急醫(yī)療用品需求最大，中后期對(duì)糧食和日用品的需求增大，所以救災(zāi)物資的配送就必須在一定時(shí)間內(nèi)到達(dá)，才能使物資的效用達(dá)到最大，有些物資需要快速運(yùn)到，而有些物資的配送要求既不能提前也不能推后。

4.弱經(jīng)濟(jì)性。災(zāi)難發(fā)生后，救災(zāi)物資配送的主要目標(biāo)是以最快速度把災(zāi)區(qū)需要的物資運(yùn)送到需要的地點(diǎn)，盡可能地減少人員傷亡和損失，而物資配送的經(jīng)濟(jì)性不是主要考慮的目標(biāo)。

5.復(fù)雜性。災(zāi)難發(fā)生后往往會(huì)對(duì)災(zāi)區(qū)的道路橋梁等造成破壞，同時(shí)通信設(shè)施也可能遭到破壞，這就使救災(zāi)物資配送面臨的情況更加復(fù)雜。

6.協(xié)調(diào)性。救災(zāi)物資配送往往需要多部門(mén)和多方式協(xié)調(diào)完成，這就需要相關(guān)部門(mén)之間加強(qiáng)合作與協(xié)調(diào)，才能使高效完成救災(zāi)物資的配送任務(wù)。

由此可見(jiàn)，救災(zāi)物資的運(yùn)輸調(diào)度問(wèn)題是一個(gè)NP問(wèn)題（Non-deterministic Polynomial，即多項(xiàng)式復(fù)雜程度的非確定性問(wèn)題），傳統(tǒng)方法難以有效解決，因此本文采用軟計(jì)算方法對(duì)此問(wèn)題進(jìn)行建模并求解。

二、救災(zāi)物資多配送中心調(diào)度問(wèn)題的數(shù)學(xué)模型

救災(zāi)物資多配送中心物流調(diào)度問(wèn)題，是在經(jīng)典多配送中心物流調(diào)度問(wèn)題的基礎(chǔ)上，考慮了配送服務(wù)需求點(diǎn)對(duì)服務(wù)時(shí)間的要求，即配送服務(wù)必須在客戶要求的時(shí)間窗內(nèi)完成。其數(shù)學(xué)模型定義在圖G=（V，E）上，其中V={v1，…，vn，vn+1，…，vn+m}，E=（vi，vj）；{v1，…，vn}表示有N（n=1，…，N）個(gè)待服務(wù)的客戶點(diǎn)；{vn+1，…，vn+m}表示有M（m=1，…，M）個(gè)配送中心，每個(gè)配送中心擁有Km（m=1，…，M）輛載重量均為Q的車(chē)輛（相同車(chē)型），每輛車(chē)一次配送的最大行駛距離為D。每個(gè)客戶點(diǎn)的需求量分別為qi（i=1，…，N）。Cij是弧，表示線路（vi，vj）∈E的費(fèi)用，或距離，或其他定義。（ETi，LTi）表示客戶要求的服務(wù)時(shí)間窗，Si表示車(chē)輛到達(dá)用戶i的時(shí)間，TEi表示在ETi之前到達(dá)客戶i時(shí)需要等待的時(shí)間（TEi=ETi-Si），提前到達(dá)的單位懲罰因子是PE，TLi表示在LTi之后到達(dá)客戶i的延遲時(shí)間（TLi= Si-LTi），延遲到達(dá)的單位懲罰因子是PL，tij表示配送車(chē)輛由客戶i行駛到客戶j的時(shí)間，Ti表示在客戶點(diǎn)i卸貨的時(shí)間。為了合理求解，模型假設(shè)如下：（1）車(chē)輛載重量應(yīng)能夠滿足配送路徑上各客戶的需求量之和；（2）車(chē)輛的最大行駛距離應(yīng)能滿足每條配送路徑的長(zhǎng)度；（3）每個(gè)客戶的需求必須滿足，且只能由一臺(tái)車(chē)輛送貨；（4）要求在規(guī)定時(shí)間內(nèi)完成配送服務(wù)，否則將根據(jù)違反時(shí)間窗的程度給予一定的懲罰。

若以配送總里程最短為目標(biāo)函數(shù)，則可建立數(shù)學(xué)模型如下：

變量定義：Xijkm=

1 配送中心 m 的車(chē)輛 k 從客戶 i 行駛到客戶 j ；0 否則.

Yikm=1 客戶 i由配送中心 m的第 k輛完成；0 否則.

Min Z=∑Mm=1{∑Kmk=1[∑n+mi=1∑n+mj=1（Cij+max（0，PE×TEj）+

max（0，PL×TLj））×Xijkm]}（1）

S.T.∑iqiYikm≤Q（2）

∑i∑jCijXijkm=D（3）

∑m∑kYikm=1（4）

∑i∑k∑mXijkm=1（5）

ETi≤Sk（i-1）+T（i-1）+t（i-1）i≤LTi（6）

Xijkm=1 or 0（7）

Yikm=1 or 0（8）

上述模型中，目標(biāo)函數(shù)式（1）即要求配送總里程最短（各條配送路徑之和最短）。同時(shí)對(duì)于違反時(shí)間約束的路徑，按照設(shè)定的懲罰因子，適當(dāng)增大目標(biāo)函數(shù)，這將把違約成本考慮到目標(biāo)函數(shù)中；式（2）保證車(chē)輛的載重量大于等于每條路徑上各客戶的貨物需求量之和；式（3）保證車(chē)輛一次配送的最大行駛距離應(yīng)大于等于每條配送路徑的長(zhǎng)度；式（4）保證每個(gè)客戶都得到配送服務(wù)，不會(huì)遺漏；式（5）保證限制每個(gè)客戶僅能由一臺(tái)車(chē)輛提供服務(wù)；式（6）是時(shí)間約束，車(chē)輛到達(dá)客戶i的時(shí)間=車(chē)輛到達(dá)路徑排列中位于i之前的客戶的時(shí)間+在前一客戶的卸貨時(shí)間+從前一客戶到客戶i的運(yùn)行時(shí)間，到達(dá)客戶i的時(shí)間滿足客戶i的配送時(shí)間約束，如果違反時(shí)間約束，將增大目標(biāo)函數(shù)值；式（7）和式（8）是變量取值約束。

三、基于軟計(jì)算的救災(zāi)物資多配送中心調(diào)度問(wèn)題求解

1.構(gòu)建虛擬配送中心

首先確定一個(gè)可以包含所有配送中心的圓，然后再隨機(jī)取得圓的一個(gè)內(nèi)點(diǎn)作為虛擬配送中心的坐標(biāo)。事實(shí)上，虛擬配送中心所處的位置并沒(méi)有太多的實(shí)際意義，只是從方便分析問(wèn)題進(jìn)而構(gòu)建完整的配送網(wǎng)絡(luò)圖而言，最好將虛擬配送中心確定在多個(gè)配送中心所形成的網(wǎng)絡(luò)圖的中心。

各配送中心之間、各客戶點(diǎn)之間、各配送中心與客戶點(diǎn)之間的距離（或成本，或其它度量標(biāo)準(zhǔn)）仍采用公式D（Ci，Dj）=（Xci-XDj）2+（Yci-YDj）2進(jìn)行計(jì)算。

由于采用虛擬配送中心的求解思路，就將問(wèn)題轉(zhuǎn)換成虛擬配送中心0向（N+M）個(gè)客戶配送的問(wèn)題。設(shè)多個(gè)配送中心和客戶點(diǎn)編號(hào)為（1，2，…N，N+1，…，N+M；其中N+1，…，N+M為實(shí)際配送中心，虛擬配送中心編號(hào)為0）。各個(gè)客戶點(diǎn)的配送量是qi（1，2，…N，N+1，…，N+M），其中實(shí)際配送中心的需求量qi為0。虛擬配送中心的車(chē)輛總數(shù)為K0（各實(shí)際配送中心車(chē)輛的總和）?？蛻酎c(diǎn)i到j(luò)的運(yùn)距為Cij（i，j=1，2，…N，N+1，…，N+M）；虛擬配送中心到實(shí)際配送中心的運(yùn)距為d0j=dj0=0（j= N+1，…，N+M），表示沒(méi)有距離，但其與各客戶點(diǎn)的距離d0j=dj0=∞（j=1，…，N），表示沒(méi)有通路。t0j=tj0=0表示虛擬配送中心到實(shí)際配送中心的時(shí)間為0，Ti=0（i=N+1，…，N+M）表示在實(shí)際配送中心的服務(wù)時(shí)間為0。

2.遺傳算法的設(shè)計(jì)

（1）染色體編碼。由于多配送中心物流調(diào)度問(wèn)題的特殊性，即采用不同的車(chē)輛數(shù)，個(gè)體的長(zhǎng)度會(huì)有所變化，因此本文采用的個(gè)體（染色體）編碼為可變長(zhǎng)度的十進(jìn)制實(shí)數(shù)編碼。

（2）初始化種群。在設(shè)定個(gè)體數(shù)量即種群規(guī)模（Num）的情況下，可以進(jìn)行種群初始化。首先，通過(guò)隨機(jī)方式產(chǎn)生互不重復(fù)的N個(gè)由1≤x≤N之間的隨機(jī)整數(shù)組成的串，作為客戶排列基因串，構(gòu)成一個(gè)個(gè)體，重復(fù)Num次就能得到整個(gè)種群的客戶排列基因串。但此時(shí)只是客戶點(diǎn)的全排列，而沒(méi)有實(shí)際配送中心。假定各個(gè)實(shí)際配送中心有足夠的貨物和車(chē)輛可以滿足配送需求，則車(chē)輛從虛擬配送中心出發(fā)選擇第一個(gè)可選客戶（即各個(gè)實(shí)際配送中心）的概率是相同的，均是1/（可作為車(chē)輛第一個(gè)配送客戶的實(shí)際配送中心的數(shù)量）。這時(shí)可以通過(guò)常用的輪盤(pán)賭法來(lái)選擇此車(chē)輛的第一個(gè)配送客戶，再在已產(chǎn)生的多個(gè)客戶基因串中隨機(jī)選擇一個(gè)串，將選定的第一個(gè)配送客戶插入到客戶串的最前端，然后根據(jù)車(chē)輛載重限制及客戶需求時(shí)間窗約束，為此車(chē)輛分配將要服務(wù)的客戶，當(dāng)達(dá)到載重限制或時(shí)間約束時(shí)，就將第一個(gè)配送客戶插入，就能完成第一輛車(chē)的配送路徑初始化。重復(fù)輪盤(pán)賭法產(chǎn)生新的子路徑的第一個(gè)客戶，再按上面的方法構(gòu)造第二臺(tái)車(chē)的配送路徑，直到將全部客戶都分配到相應(yīng)的路徑中。重復(fù)上面的步驟Num次，就可以將種群初始化完成。需要說(shuō)明的是，實(shí)際配送中心的編號(hào)在基因串中必須成對(duì)出現(xiàn)，構(gòu)成一個(gè)循環(huán)的運(yùn)行路徑。

（3）適應(yīng)度函數(shù)。給定一個(gè)個(gè)體x，該個(gè)體對(duì)應(yīng)一個(gè)配送方案，即對(duì)應(yīng)著數(shù)學(xué)模型的一個(gè)解Z（x）。由于目標(biāo)函數(shù)是求極小值，因此使Z（x）越小的個(gè)體，其適應(yīng)性越強(qiáng)。目標(biāo)函數(shù)值不會(huì)出現(xiàn)負(fù)值，因此可以用Z（x）的倒數(shù)形式作為對(duì)應(yīng)的適應(yīng)度函數(shù)，即Z′（x）=1/Z（x）。當(dāng)Z（x）越小時(shí)，Z′（x）越大，則個(gè)體的適應(yīng)值越大。對(duì)于違反約束的個(gè)體，可以在其適應(yīng)值基礎(chǔ)上增加一個(gè)合適的為負(fù)值的懲罰函數(shù)M（x），這樣就能減小相應(yīng)個(gè)體的適應(yīng)值，最終影響個(gè)體進(jìn)入下一代的機(jī)會(huì)，同時(shí)適應(yīng)值越大的個(gè)體越能在遺傳操作中進(jìn)入下一代種群。

（4）選擇算子。使用最佳保留策略進(jìn)行優(yōu)勝劣汰操作，即找出當(dāng)前群體中適應(yīng)度最高的個(gè)體不參與交叉和變異操作，而用它替換掉本代群體中經(jīng)過(guò)交叉、變異等操作后所產(chǎn)生的適應(yīng)度最低的個(gè)體。

（5）交叉算子。對(duì)新產(chǎn)生的子個(gè)體需要進(jìn)行插入配送中心操作，以產(chǎn)生完整的子代。首先，隨機(jī)選擇一個(gè)配送中心將其插入C1的第一位基因前面，然后根據(jù)車(chē)輛容量約束將此配送中心標(biāo)識(shí)插入滿足約束的最后一位基因的后面，這樣就形成了一條路徑，即某配送中心某輛車(chē)的運(yùn)行路線。再隨機(jī)選擇一個(gè)配送中心重復(fù)上面的操作，直到完成對(duì)C1的劃分。在此特別指出的是，對(duì)于車(chē)輛滿載率不足β的某條路徑，在時(shí)間約束上可以適當(dāng)放寬，因?yàn)闀r(shí)間約束已在目標(biāo)函數(shù)中進(jìn)行了轉(zhuǎn)換處理，違反時(shí)間約束越嚴(yán)重的子代個(gè)體，其適應(yīng)值越低，越容易被淘汰。此時(shí)考慮車(chē)輛運(yùn)行的滿載率，將更好地降低車(chē)輛的運(yùn)行成本，提高規(guī)模效益。對(duì)子代個(gè)體C2也采取同樣的方法進(jìn)行調(diào)整。

（6）變異算子。變異操作是在群體中隨機(jī)選擇一個(gè)個(gè)體，對(duì)其以一定的概率隨機(jī)改變個(gè)體中某位或某幾位基因的值或排列順序。本文采用局部搜索機(jī)制來(lái)完成個(gè)體變異操作。對(duì)當(dāng)前選中的個(gè)體隨機(jī)選擇S個(gè)基因?qū)Γ╥，j； 其中i，j=1，…，s），對(duì)每一對(duì)基因進(jìn)行換位操作，檢查基因換位后個(gè)體的適應(yīng)值是否提高。如果個(gè)體的適應(yīng)值有所提高，則保存基因換位操作后的個(gè)體，并退出局部搜索。如果在對(duì)S個(gè)基因進(jìn)行檢查后，個(gè)體的適應(yīng)值都沒(méi)有提高，則根據(jù)Metropolis準(zhǔn)則選擇一對(duì)基因進(jìn)行交換后替換父?jìng)€(gè)體而生成新的個(gè)體。

四、結(jié)論

自然災(zāi)害的發(fā)生不可避免，但災(zāi)難發(fā)生后對(duì)應(yīng)急物資進(jìn)行合理調(diào)配，可以有效降低災(zāi)難造成的生命和財(cái)產(chǎn)損失。根據(jù)救災(zāi)物資多配送中心調(diào)度問(wèn)題的數(shù)學(xué)模型及基于軟計(jì)算的求解方法，得出結(jié)論：有效解決突發(fā)性自然災(zāi)害導(dǎo)致物質(zhì)需求的不確定性與物資需求的緊急性之間的矛盾，可以在災(zāi)難發(fā)生后根據(jù)每種物資需求的緊急程度確定配送線路和配送時(shí)間；同時(shí)，引入多配送中心更符合災(zāi)后物資調(diào)運(yùn)的實(shí)際情況。

[參考文獻(xiàn)]

[1]郎茂祥.多配送中心車(chē)輛調(diào)度問(wèn)題的模型與算法研究[J].交通運(yùn)輸系統(tǒng)工程與信息，2006，10（5）：65-39.

[2]鐘石泉，賀國(guó)光.多車(chē)場(chǎng)車(chē)輛調(diào)度智能優(yōu)化研究[J].華東交通大學(xué)學(xué)報(bào)，2004，21（6）：26-29.

[3]鄒彤，李寧，孫德寶.多車(chē)場(chǎng)車(chē)輛路徑問(wèn)題的遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用，2004（21）：82-83.

[4]李臻，雷定猷.多車(chē)場(chǎng)車(chē)輛優(yōu)化調(diào)度模型及算法[J].交通運(yùn)輸工程學(xué)報(bào)，2004，4（1）：83-86.

[5]李妍峰，李軍，趙達(dá).基于迭代局域搜索的智能優(yōu)化算法求解車(chē)輛調(diào)度問(wèn)題研究[J].系統(tǒng)工程理論與實(shí)踐，2007，5（5）：75-82.

[6]陳火根，丁紅鋼，程耀東.物流配送中心車(chē)輛調(diào)度模型與遺傳算法設(shè)計(jì)[J].浙江大學(xué)學(xué)報(bào)，2003，37（5）：512-517.

（責(zé)任編輯：?jiǎn)毯纾?