基于PSO算法的應急物流車輛調度

袁世軍，梁瑞偉

（湖南現代物流職業技術學院，湖南 長沙 410131）

1 引言

應急物流的主要目標是應對嚴重自然災害、突發性公共衛生事件、公共安全事件及軍事沖突等突發事件而對物資、人員和資金等提供物流保障，但如何使應急物流在滿足需求的前提下做到成本最低，一直是物流管理重要的研究領域。

本文將PSO（粒子群優化算法）引入應急物流車輛調度問題中，其基本原理是將應急物流中多個供應點與多個需求點作為粒子群中的不同粒子，依靠不同粒子間的相互作用尋找最佳供應點、最優配送車輛以及配送線路在整個尋優空間里的最優位置，也即問題的最優解。在此粒子群中的每一個粒子都將賦予一個適應度值，每個粒子具有2個屬性，即速度與位置。算法運行過程中，所有粒子趨向當前時刻的最優粒子的位置，并試圖在可能空間中搜索全局最優解。本文對應急物流車輛調度問題做了一定的假設，使得問題更加清晰簡潔。在假設的基礎上構建了改進應急物流車輛調度模型，目標函數為使因物資需求延遲滿足而引起的損失最小。

2 問題描述

為了建模方便，將應急物流車輛調度問題抽象為：在n個應急貨物供應點s1,s2,...,sn，儲備了p種應急貨物a1,a2,...,ap，其單位貨物的重量為wa，單位貨物體積為va，在t時間范圍內，應急貨物供應點s貨物a的供給量為Xtsa；在所有供應點S，可使用的車輛總數為q，車輛表示為l1,l2,...,lq，車輛的最大載重量為Kl，最大容積為Vl，負責對m個物資需求點d1,d2,...,dn運輸應急貨物。在t時段內，需求點d對物品a的需求量為Wtda。

將整個運輸周期T劃分成N個時段，表示為t1,t2,...,tN，則在t時段需求點d對物品a未被滿足的數量為disstda，因此而引起的損失為Pa·disstda，Pa表示單位a物品未滿足而造成的損失。若某需求點對某物品在該時段內未得到滿足而在往后的時段內得到滿足，則之前因未滿足引起的損失可以相應的部分抵消，如需求點d對a物品在t時段未被滿足而在t+j時段內滿足的數量comt,t+j,da，則挽救的損失為(Pa-kj)×comt,t+j,da，(Pa-kj)表示單位a物品延后j時段挽救的損失與Pa之間的線性關系。此外，為了將整個運輸周期的損失降到最低，應急貨物允許提前運送到需求點。

本文研究的目的是設計針對應急貨物調配的最佳車輛調度方案，通過調度各應急物流貨運車輛共同參與且依次完成其運輸任務，使得應急貨物需求得到滿足且損失最小。

3 模型建立的假設

根據應急物流的特點，便于模型建立，特作以下假設：

（1）假設各應急中心在整個運輸周期內對物品的需求量服從正態分布N(μda，σda)，其中μda表示需求點d對物品a的平均周期，σda表示需求點d對物品a時間的方差，則第t時段需求點d對物品a的需求量為（T0為每個時段長度）：

（2）假設單位物品a在t時段未被滿足而在t+j時段內滿足的損失減少量P減少滿足P減少=Pa-kj的一元線性關系（也可假設為滿足其他關系，本文僅以滿足一元線性關系進行研究），k為系數，且k≤Pa/N。

（3）車輛完成一次運輸任務后可以隨機選擇運輸網絡中任一個供應點作為下一個任務的起始點而不是只能回到原出發點。

（4）在應急事件發生的情況下，受災點對各種應急貨物需求量非常大，因此只考慮滿載運輸方式。

（5）運輸時間都以時段數來衡量，不足1時段的以1時段計算。

（6）模型中的參數：

T：整個運輸周期；

N：計劃期的總時段數；

L：車輛集合；

D：需求點集合；

S：供應點集合；

A：應急貨物種類集合；

Kl：車輛l的最大載重；

Cla：車輛l運輸a物品的最大數量Cla=min(Kl/wa，Vl/va)；

Pa：單位a物品未滿足的懲罰系數；

Zlks：車輛l執行第k個任務所在的供應點為s；

Zlkd：車輛l執行第k個任務所在的需求點為d；

Zlka：車輛l執行第k個任務所運輸的物品為a；

Wtda：t時段需求點d對a物品的需求量；

Mtda：t時段需求點d對a物品的滿足量；

Xtsa：t時段從供應點s運出a物品的數量；

Ytda：t時段運輸到需求點d的a物品的數量；

SYtda：t時段末需求點d物品a的剩余量；

SYtsa：t時段末需求點s物品a的剩余量；

disstda：t時段需求點d對a物品未滿足的數量；

comt,t+j,da：需求點d對a物品在t時段未被滿足而在t+j時段內滿足的數量。

4 模型建立

基于PSO應急物流車輛調度模型的目標：在整個時間范圍內，所有應急物流需求節點、所有應急貨物雖因延遲滿足但其引起的損失從系統的角度來看是最小的。

式（2）表示模型的目標函數，其中第一項表示應急點需求沒有得到滿足產生的損失，第二項表示在延遲滿足的情況下，其損失的減少量。

式（3）表示在t時段需求點d對a物品未滿足的數量等于該時段該需求點對該物品的需求量減去滿足量。

式（4）表示t時段應急貨物需求點d對a物品的滿足量的關系。當t-1時段末應急貨物需求點d應急物品a的庫存與t時段運輸到該點d的a物品的數量之和小于t時段需求點d對a物品的需求量時，Mtda=SYt-1,da+Ytda，否則，當t-1時段末需求點d物品a的剩余量與t時段運輸到需求點d的a物品的數量之和大于t時段需求點d對a物品的需求量時，Mtda=Wtda。

式（5）表示t時段末需求點s物品a的剩余量的關系，當SYt-1,da＞0，即上一個時段末的剩余量大于0時，則SYtda=max(SYt-1,da+Ytda-Wtda,0)，即該時段末的剩余量等于上一時段末的剩余量加上該時段運送到的物品量減去該時段的需求量與0的最大值；當SYt-1,da=0時，則，即該時段末的剩余量等于該時段運送到的物品量減去該時段的需求量減去1到t-1時段的未滿足量再加上1到t-2時段的未被滿足需求在1到t-1時段得到的補充量與0的最大值。

式（6）表示需求點d對a物品在t時段未被滿足而在t+j時段內滿足的數量的關系，當=0時，即t時段需求點d對a物品未滿足的數量減去t時段的需求在1到t+j-1時段內得到滿足的數量之差等于0時，說明此時段的需求全部已滿足，所以comt,t+j,da=0；當時，即此時段仍有未滿足量，則即t時段未被滿足而在t+j時段內滿足的數量等于t+j時段到達的運輸量減去1到t-1時段在t+j時段得到的滿足量，與t時段的未滿足量減去t時段在1到t+j-1時段內得到的滿足量中的最小值，這里假定時段靠前的未被滿足量優先得到補充。

式（7）表示t時段末需求點s物品a的剩余量等于上一個時段末的剩余量減去該時段從該供應點運送出去的量。

式（8）表示車輛l從供應點s運出a物品的數量等于車輛l運輸a物品的最大數量，且不得大于車輛l的最大載重。

式（9）表示Wtda，Mtda，disstda，comt,t+j,da，SYtda，SYtsa和Zlks，Zlkd，Zlka的取值范圍。

式（10）表示車輛執行每個運輸任務都只能有一個供應點、一個需求點和運輸一種物品。

式（11）表示Zlks，Zlkd，Zlka的取值范圍。

在整個運輸計劃中，各應急中心可能隨時提出新的需求，物資儲備中心也可能從外界接收新的物品數量以增加對應急中心的供應量，也可能征集到新的車輛或民間組織或個人的車輛加入進來，對于這些實時信息的處理方法如下：對于新加入運輸計劃的供應量，則此時段的供應量等于上一時段該供應點的剩余量加上新加入的供應量；對于新加入運輸計劃的需求量，則此時段需求點的需求量等于原有的需求量加上新加入的需求量再減去已滿足的需求量；對于新加入運輸計劃的車輛，在保持原有車輛的運輸任務不變的情況下，對新加入的車輛安排新的運輸任務。通過對系統輸入參數的更新，運用模型進行求解，即可得到系統更新后的輸出參數。

5 求解應急物流車輛調度模型

5.1 粒子編碼方式

為了求解應急物流車輛調度問題，本文設計了一種適合求解本文模型的編碼方式，即符號編碼。符號集可以由字母組成，也可以由數字組成，也可以是由字母或數字混合組成的代碼表，如{A1,A2,A3,……}。具體的粒子編碼步驟如下：

（1）將供應點表示為{S1,S2,...,Sn}，需求點表示為{D1,D2,...,Dn}，物品表示為{A1,A2,...,An}。

（2）每一個符號集代表一個運輸任務，如符號集{S1,A2,D3}表示該車輛從供應點S1運輸物品A2到需求點D3，車輛的所有符號集按照任務的完成順序依次排列組成，如{S1,A2,D3}{S3,A5,D1}{S2,A3,D1}表示該車輛從供應點S1運輸物品A2到需求點D3，再到供應點S3運輸物品A5到需求點D1，再到供應點S2運輸物品A3到需求點D1。

（3）所有車輛的第一個任務集按車輛的順序排列組成第一任務集，然后依次類推。最后得到所有車輛所有任務集，并按照第幾任務集按順序排列。

（4）每輛車完成的最大任務數由每種物品的庫存量和整個運輸周期確定。如對于某種物品，將涉及到這種物品的所有任務的裝載量進行累加，如累加第k個任務時的和大于此種物品的供給量，則第k個任務和之后的任務全部賦值為0，即清除這些任務；超過整個運輸周期的任務調整也用同樣的方法對任務集進行調整，最后得到符合條件的任務集。

5.2 適應值函數

對于車輛調度問題來說，在構造適應值函數時，往往會結合模型中的約束條件來構造，也就是說將在求解中難以處理的約束條件加入到目標函數中共同構造問題的適應值函數，如約束條件不滿足，則解空間中無對應解的粒子，則對此解給予一個罰函數，使之被淘汰，從而減少求解時的操作次數，即用下列公式對粒子進行調整：

式中：Z(X)表示原適應值；Z′(X)表示考慮罰函數之后的新適應值；P(X)表示罰函數[8-9]。

本文使用罰函數法對違反約束的情況進行懲罰，使式（7）構成的罰函數成為適應值函數的一部分，構成的適應值函數為：

其中，R表示懲罰系數，為了嚴格滿足庫存約束條件，R應趨于無窮大，但為了處理方便和計算簡單，R一般取一個適當的整數，如R=106。

5.3 數值仿真分析

為了對前面提出的模型和算法的有效性進行驗證和分析，本文構造了一個算例。算例如下：在春季的某個上午，某個地區發生了一次突發性地震災害，應急貨物儲備中心接到上級命令，需將所需的救援物資在6個小時內運輸到各應急中心，在三個地區的某小區、學校和開發區的綠化地、操場和廣場分別設立了3個應急中心，應急貨物儲備中心征集到了10輛車進行帳篷、食品和衣物三種應急貨物的配送工作。

整個運輸周期為6h，本文將運輸周期等分為12個時段，每個時段長為30min。為了簡化求解運算過程以及編程的復雜性，這里我們只考慮一個供應點進行供應的情況，假設供應點的現有物品數量在整個周期內不會產生變化，且車輛的規格一致。

5.3.1 基礎參數設置。系統輸入數據包括各災區的基本信息、應急貨物的儲備信息、各應急貨物的基本信息、車輛基本信息和應急貨物儲備中心到各應急中心的最短路徑信息。

（1）各災區的基本信息。各災區的基本信息見表1，各物品的需求量服從均值為10，方差為12的正態分布N(10,12)。

表1 各災區基本信息

這里取季節系數為0.9，根據前文各物品的需求計算公式可得到各應急中心對各物品的需求量，具體數據見表2。

表2 各應急中心需求量和儲備中心的供應量

根據表2、式（1）以及服從正態分布N（10,12），可得出各應急中心各個時段的需求量，具體數據見表3。

表3 各需求點在各個時段對各種物品的需求量

（2）各應急貨物的基本信息。各應急貨物的單位重量、體積、懲罰系數等基本信息見表4。

表4 各應急貨物的基本信息

（3）車輛基本信息。應急貨物儲備中心共征集到10輛車輛進行運輸，且車輛規格一致，車輛的基本信息見表5。

表5 車輛基本信息

（4）最短路徑。應急貨物儲備中心到各應急中心的最短路徑見表6。

表6 儲備中心到各應急中心的最短路徑（km）

5.3.2 構建模型并求解

（1）目標函數值。根據問題輸入、設定的初始參數，在windows XP，內存1G 的電腦環境下進行運算，得到本算例的目標函數值為：Z=4 482.96，趨勢圖如圖1所示。

圖1 目標函數值曲線圖

（2）車輛的運輸任務。車輛的運輸任務見表7。以應急物流配送車輛2為例，應急物流配送車輛2執行了四個應急配送任務，分別為：從應急物流中心配送衣物到學校，再從儲備中心運輸食品到小區，再從儲備中心運輸衣物到開發區，最后再從儲備中心運輸帳篷到小區。

表7 各車輛的運輸任務

（3）各應急中心在各時段內得到的應急貨物數量（以需求點小區，帳篷為例）見表8。

表8 各應急中心在各時段內得到的應急貨物數量

6 與其他算法的比較分析

6.1 模型改進前后比較分析

本文所建立的應急物流車輛調度模型是在前人的基礎成果上進行改進，為了體現改進后的模型的有效性，對改進前的模型和本文改進后的模型進行對比分析：

改進后模型：

算法參數按照上文最初的參數配置進行實驗，以改進前的模型和改進后的模型分別進行運行計算后得到的結果數據見表9，適應值趨勢圖如圖2所示。可以看出，改進后的模型不僅更符合實際情況，而且適應值遠小于改進前。

表9 模型改進前后的適應值比較

圖2 模型改進前后的適應值趨勢圖

而且，從模型改進前后的車輛任務分析可以看出，模型改進前得出的車輛任務更優先運輸衣物，這是因為改進前的模型不考慮延遲滿足帶來的損失挽回量，而由于衣服的需求量和車輛裝載量最大，優先安排更多的車輛運輸衣服可以減少整個運輸物資未滿足帶來的損失量。但我們知道，在發生自然災害的情況下，每種物資的需求量和重要性不一定匹配，也就是說需求量大的物資并不一定重要性就更大，比如藥品。所以，模型未改進的實驗結果與實際情況是有出入和偏差的，對于實際應用價值不大。

6.2 與隨機搜索算法的比較分析

隨機搜索算法是指在目標位置基本服從均勻分布的條件下，搜索軌跡隨機且均勻散布在目標分布區域內，經過多次循環和迭代后在約束可行域內求解的一種搜索方法[10]。

本文用前面的算例，算法參數按照上文最初的參數配置進行實驗，對隨機搜索算法和基本粒子群算法的求解結果進行比較分析，得出的實驗結果見表10，與隨機搜索算法的比較趨勢圖如圖3所示。

表10 與隨機搜索算法的結果比較

圖3 與隨機搜索算法的趨勢圖比較

從實驗數據和趨勢圖可以看出，在一定的條件下通過隨機搜索算法求得的結果遠差于我們采用的基本PSO 算法，而在運算時間上沒有太大的差別。隨著循環迭代次數的不斷增加，隨機搜索得出的結果可能會更好，但是耗費的時間也將會不斷增加，而且還不能保證可以得到較理想的結果。

隨機搜索算法盡管簡單易行，但是由于其效率低，難以找到最優結果。而基本PSO 算法卻能夠較快的、穩定的求得最優或較優的結果。

6.3 與窮舉法的比較分析

窮舉法是一種傳統的搜索方法，其基本原理就是在一個可行域內，依次列出所有的可能情況，并對所有可能的情況進行判別，判斷哪些是符合問題要求的，最后根據這些可能的情況找出問題的最優解[11]。

為了便于用窮舉法與本文算法進行比較，我們取運輸周期的前2個時段進行比較研究。這里，我們采用前面的算例，算法參數按照上文最初的參數配置進行實驗，兩種算法求出的實驗結果見表11。

表11 與窮舉法的結果比較

從實驗結果來看，雖然窮舉法得到的解稍優于本文PSO 算法的結果。但是，窮舉法是遍歷了問題的所有可能解后才得出最優的結果，而PSO 算法僅迭代95次后就收斂于最優解。且窮舉法所耗費的時間遠遠大于PSO算法，研究的問題規模越復雜、循環迭代次數越多，那么，窮舉法耗費的時間也將成幾何倍數增長，而PSO 算法卻能在較短的時間內收斂于最優解。對于應急物流來說，時間就是生命，必須在最短的時間內作出有效的決定，窮舉法顯然是不可能做到的，而本文用到的PSO算法因其簡單、收斂速度快、易于實現等優點，具有更強的實用性和現實性。而且隨著問題維數和復雜度的增加，PSO算法的優越性將更加明顯。

7 結語

本文首先給出問題的描述和建模思路，在合理假設的基礎上，以使在所有時段內、所有需求點、所有物品延遲滿足而引起的損失最小為目標，構建了應急物流車輛調度的改進數學模型。其次根據應急物流車輛調度的特殊情況，設計了適合求解應急貨物運輸調度模型的粒子群算法，包括粒子的編碼方法、適應度函數、參數控制和終止條件的確定等。然后通過一個算例對所建立的模型和算法進行數值模擬。然后比較分析了模型改進前后的實驗結果數據，與其他算法和改進的PSO算法進行了比較，證明該模型及其算法的有效性。此相關研究成果可以為政府及行業企業在突發應急事件時進行車輛的有效調度提供科學依據。