基于軟計算的救災物資多配送中心調度問題研究

張延良

[摘要]自然災害的發生不可避免，但災難發生后對應急物資的合理調度可以有效降低災難造成的生命和財產損失。基于對救災物資調配特點的分析，建立救災物資多配送中心調度問題的數學模型，給出基于軟計算的求解方法，得出可在災難發生后根據每種物資需求的緊急程度確定配送線路和配送時間，同時引入多配送中心更符合災后物資調運實際情況的結論，希望能為應急物資調度問題的相關研究提供一定借鑒。

[關鍵詞]軟計算；救災物資；配送中心；調度

[中圖分類號]F259.21[文獻標識碼]A[文章編號]

2095-3283（2015）12-0119-03

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

一、救災物資調配的特點

救災物資調配與傳統物資調配比較存在很大差異，在災難發生和發展的不同階段，對于不同救災物資的需求也是各不相同。總體來看，救災物資的調配具有以下特點：

1.突發性。災難的發生往往都是突發事件，其發生時間和發生地點大多不可預測，這決定了救災物資調配最主要的特點就是突發性。

2.不確定性。災難發生的突發性導致短時間內災區情況不能確定，從而使救災物資的需求地點、需求數量和需求種類等具有不確定性。

3.時限性。在災難發生的不同時期，對物資配送的時限要求也完全不同。例如，災難發生前期對應急醫療用品需求最大，中后期對糧食和日用品的需求增大，所以救災物資的配送就必須在一定時間內到達，才能使物資的效用達到最大，有些物資需要快速運到，而有些物資的配送要求既不能提前也不能推后。

4.弱經濟性。災難發生后，救災物資配送的主要目標是以最快速度把災區需要的物資運送到需要的地點，盡可能地減少人員傷亡和損失，而物資配送的經濟性不是主要考慮的目標。

5.復雜性。災難發生后往往會對災區的道路橋梁等造成破壞，同時通信設施也可能遭到破壞，這就使救災物資配送面臨的情況更加復雜。

6.協調性。救災物資配送往往需要多部門和多方式協調完成，這就需要相關部門之間加強合作與協調，才能使高效完成救災物資的配送任務。

由此可見，救災物資的運輸調度問題是一個NP問題（Non-deterministic Polynomial，即多項式復雜程度的非確定性問題），傳統方法難以有效解決，因此本文采用軟計算方法對此問題進行建模并求解。

二、救災物資多配送中心調度問題的數學模型

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

若以配送總里程最短為目標函數，則可建立數學模型如下：

變量定義：Xijkm=

1 配送中心 m 的車輛 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）

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

三、基于軟計算的救災物資多配送中心調度問題求解

1.構建虛擬配送中心

首先確定一個可以包含所有配送中心的圓，然后再隨機取得圓的一個內點作為虛擬配送中心的坐標。事實上，虛擬配送中心所處的位置并沒有太多的實際意義，只是從方便分析問題進而構建完整的配送網絡圖而言，最好將虛擬配送中心確定在多個配送中心所形成的網絡圖的中心。

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

由于采用虛擬配送中心的求解思路，就將問題轉換成虛擬配送中心0向（N+M）個客戶配送的問題。設多個配送中心和客戶點編號為（1，2，…N，N+1，…，N+M；其中N+1，…，N+M為實際配送中心，虛擬配送中心編號為0）。各個客戶點的配送量是qi（1，2，…N，N+1，…，N+M），其中實際配送中心的需求量qi為0。虛擬配送中心的車輛總數為K0（各實際配送中心車輛的總和）。客戶點i到j的運距為Cij（i，j=1，2，…N，N+1，…，N+M）；虛擬配送中心到實際配送中心的運距為d0j=dj0=0（j= N+1，…，N+M），表示沒有距離，但其與各客戶點的距離d0j=dj0=∞（j=1，…，N），表示沒有通路。t0j=tj0=0表示虛擬配送中心到實際配送中心的時間為0，Ti=0（i=N+1，…，N+M）表示在實際配送中心的服務時間為0。

2.遺傳算法的設計

（1）染色體編碼。由于多配送中心物流調度問題的特殊性，即采用不同的車輛數，個體的長度會有所變化，因此本文采用的個體（染色體）編碼為可變長度的十進制實數編碼。

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

（3）適應度函數。給定一個個體x，該個體對應一個配送方案，即對應著數學模型的一個解Z（x）。由于目標函數是求極小值，因此使Z（x）越小的個體，其適應性越強。目標函數值不會出現負值，因此可以用Z（x）的倒數形式作為對應的適應度函數，即Z′（x）=1/Z（x）。當Z（x）越小時，Z′（x）越大，則個體的適應值越大。對于違反約束的個體，可以在其適應值基礎上增加一個合適的為負值的懲罰函數M（x），這樣就能減小相應個體的適應值，最終影響個體進入下一代的機會，同時適應值越大的個體越能在遺傳操作中進入下一代種群。

（4）選擇算子。使用最佳保留策略進行優勝劣汰操作，即找出當前群體中適應度最高的個體不參與交叉和變異操作，而用它替換掉本代群體中經過交叉、變異等操作后所產生的適應度最低的個體。

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

（6）變異算子。變異操作是在群體中隨機選擇一個個體，對其以一定的概率隨機改變個體中某位或某幾位基因的值或排列順序。本文采用局部搜索機制來完成個體變異操作。對當前選中的個體隨機選擇S個基因對（i，j； 其中i，j=1，…，s），對每一對基因進行換位操作，檢查基因換位后個體的適應值是否提高。如果個體的適應值有所提高，則保存基因換位操作后的個體，并退出局部搜索。如果在對S個基因進行檢查后，個體的適應值都沒有提高，則根據Metropolis準則選擇一對基因進行交換后替換父個體而生成新的個體。

四、結論

自然災害的發生不可避免，但災難發生后對應急物資進行合理調配，可以有效降低災難造成的生命和財產損失。根據救災物資多配送中心調度問題的數學模型及基于軟計算的求解方法，得出結論：有效解決突發性自然災害導致物質需求的不確定性與物資需求的緊急性之間的矛盾，可以在災難發生后根據每種物資需求的緊急程度確定配送線路和配送時間；同時，引入多配送中心更符合災后物資調運的實際情況。

[參考文獻]

[1]郎茂祥.多配送中心車輛調度問題的模型與算法研究[J].交通運輸系統工程與信息，2006，10（5）：65-39.

[2]鐘石泉，賀國光.多車場車輛調度智能優化研究[J].華東交通大學學報，2004，21（6）：26-29.

[3]鄒彤，李寧，孫德寶.多車場車輛路徑問題的遺傳算法[J].計算機工程與應用，2004（21）：82-83.

[4]李臻，雷定猷.多車場車輛優化調度模型及算法[J].交通運輸工程學報，2004，4（1）：83-86.

[5]李妍峰，李軍，趙達.基于迭代局域搜索的智能優化算法求解車輛調度問題研究[J].系統工程理論與實踐，2007，5（5）：75-82.

[6]陳火根，丁紅鋼，程耀東.物流配送中心車輛調度模型與遺傳算法設計[J].浙江大學學報，2003，37（5）：512-517.

（責任編輯：喬虹）