基于免疫粒子群算法的應急物流配送車輛調度研究

曹慶奎，李良飛，任向陽 （河北工程大學 經濟管理學院，河北 邯鄲056038）

CAO Qing-kui, LI Liang-fei, REN Xiang-yang (School of Economics & Management, Hebei University of Engineering, Handan 056038, China)

近年來，地震、泥石流、旱澇等自然災害的頻頻發生，造成了巨大的人員傷亡和財產損失。在目前的科技水平下，這些自然災害事件是不可避免的，所造成的損失也是無法估量的[1-2]。因此自然災害發生時，科學合理的資源配置能對應急救援起到事半功倍的作用，然而應急物流配送車輛調度優化就是其中的關鍵環節，越來越多的人認識到應急物流配送車輛調度優化問題的重要性。

應急物流與普通物流相比，有很多相同的地方，不過也存在很多不同的地方，節約成本是普通物流主要考慮的因素，然而應急物流配送過程中要受到嚴格的時間約束，因此應急物流更體現了應急服務的時效性。目前國內外對應急物流系統的研究主要有應急車輛的配置、應急資源調配和應急配送車輛調度，在應急物流配送車輛調度模型以及算法上都有了一定的研究，Eqi等人建立以運輸成本最小為目標的調度模型[3]，宋遠清等在研究了需求隨機的車輛調度模型，但是沒有考慮運輸成本和運輸時間[4]；石玉峰等建立了最短運輸時間和最小運輸費用的多目標組合優化調度模型[5]；文仁強等通過蟻群算法對應急物資配送車輛調度優化問題進行了求解[6]；張裕華等在帶有時間窗的基礎上考慮運輸費用與距離構建應急物流配送車輛調度模型，并運用了蟻群算法進行求解[7]；陳明華建立了一般性非滿載應急物流車輛調度模型，采用人工免疫算法進行了求解[8]。綜上所述，在車輛調度問題中多注重時間方面的及時性，忽略了應急運輸車輛的體積和載重對配送調度的影響以及應急配送車輛資源的有限性，通過本文的研究，建立更符合實際的多目標應急配送車輛調度優化模型，運用針對該模型的混合算法求解模型得到的結果可以作為救災指揮中心制定車輛調配方案科學決策的依據。因此，本文所研究的問題具有重要的現實意義。

1 模型構建

1.1 模型的問題假設

（1） 所有受災點在物資數量方面和運輸時間方面的需求都能夠得到滿足，同時單個需求節點的需求量小于單車最大荷載；（2） 同種車型運輸，車輛的額定載重量和車輛的容積一定；（3） 各受災點均在救災點的配送范圍之內，運輸到受災點的時間不超過最遲到達時間；（4） 路網為完全網絡，即所有節點之間都有線路連通；（5） 救災點與各受災點、各受災點之間的運輸距離作為已知量；（6） 每輛車完成配送任務后回到配送中心。

1.2 模型的數學描述

有n個受災地區向救災指揮中心請求救災物資的配送，第i個受災節點對于救災物資的需求量為救災中心與各受災節點、各受災節點之間的廣義運輸距離為dij，運輸時間為tij（i,j=0,1,2,…,n，配送中心編號為0，受災節點編號為1,2,…,n）；卸貨時間為UTi，最遲允許車輛到達時間為LTi；G是一系列需要應急服務的受災點集合；K表示應急運輸車輛集合；vi和qi，分別表示受災點i應急物資的體積和重量；V和Q分別表示運輸車輛額定體積載重；可用車輛數為k；車輛不能超載且必須在規定時間之前把物資送到受災節點。要求指派運輸車輛，并確定每輛車運輸路線，使得總運輸距離最低，并且使運輸車輛最少。

把應急配送中心即救災點和受災節點統一看作是運輸網絡中的節點。設在同一線路上點i是點j前面的相鄰點，車輛到達點i的時間為RTi，到達j點的時間為RTj，則有：RTj=RTi+tij。

將模型中所涉及的二進制變量定義如下：

建立應急配送車輛調度的數學模型如下：

目標函數：

約束條件：

上述模型中，式（1） 表示目標函數為求最短的應急運輸距離；式（2） 表示目標函數為使用最少的運輸車輛數；式（3）表示每輛車裝貨不超過其額定容積；式（4） 表示車輛裝貨不超過其額定載重；式（5） 表示救災物資送到各個受災節點的時間必須在規定的時間窗范圍內；式（6） 表示每一個受災地區節點僅由一輛車提供卸載救災服務；式（7）、（8） 表示車輛k應離開已經駛入過的受災節點，并且只停靠于分配給其運輸任務的受災點；式（9） 中表示，如果車輛k有貨物，則該車執行任務，此時目標函數（2） 增加1。

2 免疫粒子群算法求解

粒子群優化算法（Particle Swarm Optimization, PSO） 是一種基于粒子群算法（PSO） 同遺傳算法類似，是一種基于迭代的優化工具，一種基于群體的隨機優化技術。它是Kennedy 和Eberhart 于1995 年提出的一種新的進化計算方法，它源于鳥群和魚群群體覓食運動行為研究結果的啟發[9-10]。

在PSO 算法中有兩個主要的操作，其中一個操作是利用適應性函數來計算適應值，并且依照適應值的比較結果來決定是否更新每個粒子本身的最佳經驗（pBest）以及所有粒子群體的最佳解（gBest）。第二個操作為每一個粒子的位置轉移，首先每個粒子會根據公式（10） 計算出新的速度，然后根據此新的速度依照公式（11） 產生出新的位置：

生物免疫系統是一個分布式、自組織和具有動態平衡力的適應性復雜系統。它面對外界入侵的抗原，能夠產生相應的抗體，其抗體上有特定的物質，可以結合或消除抗原，以維持免疫平衡。這樣的免疫原理可以應用到許多現有的智能信息處理的技術中，構成了許多更加有效的智能方法，如免疫神經網絡，免疫遺傳算法等。

在本文中我們將免疫機理和粒子群算法結合，構造了一個啟發式的免疫粒子群算法。在免疫粒子群算法中，定義抗體用來表示對問題的候選解，定義抗原代表問題及其約束。具有免疫優勢的抗體即為當前抗體種群中的有效解或非劣最優解[11]。在本文算法中，對于車輛k、n個受災點的車輛分配，首先將個體編碼為一個k*n大小的矩陣，用粒子來進行表示。求解該應急物流配送中的車輛調度問題的免疫粒子群算法步驟如下：

步驟一：初始化具有V個個體的粒子群。

步驟二：計算每個粒子的適應度函數（取式目標函數的倒數），選擇適應度函數最大的個體。

步驟三：判斷是否滿足停機條件，滿足條件退出，不滿足條件則繼續。

步驟四：按照公式（11）、（12） 計算粒子新的位置，取符號變為二進制的0,1。

步驟五：檢查個體的7 個約束是否滿足，滿足約束的粒子保留。

步驟六：對不滿足約束的個體注射疫苗：對個體按照對問題的先驗知識修改個體位置，執行注射疫苗的操作，對群體中注射了疫苗的粒子進行免疫檢測，滿足條件的保留。

步驟七：轉到步驟二。

免疫粒子群算法的流程如圖1 所示。

圖1 免疫粒子群算法求解過程圖

3 實例分析

為考察上述模型和算法的有效性，選用某地區所測算的原始數據為依據進行分析。具體描述如下：

某地區發生自然災害，所在地區的救災物資儲備中心需要向8 個受災節點進行救災物資配送。受災節點）的需求量為gi，卸貨時間為UTi，物資最晚送到時間為LTi，裝載容量為8 噸，運送車輛的容積為18m3，車速為60 公里/小時。車輛不能超載且必須在規定時間之前把物資送到受災節點。各節點的物資需求量及物資儲備中心與各需求點之間、各需求點相互之間的距離見表1 和表2。

表1 受災節點的需求數據

表2 各節點之間的距離

以Matlab7.4.0 為工具運用本文的免疫粒子群算法對上述問題進行求解，參數設置如下：c1=c2=2，c3=0.6。重復運行50 次，發現有39 次收斂到最優解，即找到最優解的概率是78%，得到最終車輛行駛路線見表3，在同樣條件下，運用粒子群算法求解，發現有32 次收斂到最優解，即找到最優解的概率是64%，而且運用本文中的算法最終結果優于粒子群算法。

表3 車輛行車路線表

4 結 論

本文針對應急物流配送車輛調度問題，在滿足時間約束的條件下，綜合考慮運輸車輛體積和載重條件，建立模型使運輸車輛數最少、總運輸線路最短，最大程度的節省物流資源，而不是把車輛調度的研究目的僅僅局限在應急時間最短或運輸成本最小。在求解模型時，運用免疫算法和粒子群算法的混合算法，快速求解應急物流配送車輛調度問題，有效提高尋優精度和響應速度。并對其進行實證研究，通過不同算法的比較，驗證本文模型和算法的可行性和有效性，為應急管理部門提供有效的輔助建議。

[1] 宋傳平. 我國應急物流系統的構建和保障條件[J]. 中國流通經濟，2011,25(4):21-24.

[2] Cauchemez S. Estimating the impact of school closure on influenza transmission from sentinel data[J]. Nature, 2008,452(10):750-754.

[3] Equi L, Gallo G, Marziale S, et a1. A combined transportation and scheduling problem[D]. Pisa: Pisa University, 1996:523-538.

[4] 宋遠清，李永生，梁慎清. 需求隨機車輛調度問題的遺傳算法研究[J]. 計算機技術與發展，2009,19(2):230-233.

[5] 石玉峰，王金偉，徐軍,等. 應急物流分配模型及算法研究[J]. 物流技術，2009,28(6):80-81,112.

[6] 文仁強，鐘少波，袁宏永,等. 應急資源多目標優化調度模型與多蟻群優化算法研究[J]. 計算機研究與發展，2013,50(7):1464-1472.

[7] 張裕華，潘郁. 基于蟻群算法的應急物流配送車輛調度研究[J]. 物流科技，2009(5):47-49.

[8] 陳明華，李迎秋，羅耀琪. 應急物流車輛調配問題的研究[J]. 計算機工程與應用，2009,45(24):194-197.

[9] Kennedy J, Eberhart R C. Particle Swarm OPtimization[C] // In: IEEE Int. Conf. on Neural Networks, Perth, Australia, 1995:1942-1948.

[10] Eberhart R C, Kennedy J. A new optimizer using particles warm theory[C]//In:Proc of the sixth international symposium on Micro Machine and Human Science, Nagoya, Japan, 1995:39-43.

[11] 席娜，徐術力. 基于免疫粒子群優化算法的物流配送車輛調度算法[J]. 物流技術，2012,31(12):312-313.