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

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

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

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

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

1 模型構建

1.1 模型的問題假設

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

1.2 模型的數(shù)學描述

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

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

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

建立應急配送車輛調(diào)度的數(shù)學模型如下：

目標函數(shù)：

約束條件：

上述模型中，式（1） 表示目標函數(shù)為求最短的應急運輸距離；式（2） 表示目標函數(shù)為使用最少的運輸車輛數(shù)；式（3）表示每輛車裝貨不超過其額定容積；式（4） 表示車輛裝貨不超過其額定載重；式（5） 表示救災物資送到各個受災節(jié)點的時間必須在規(guī)定的時間窗范圍內(nèi)；式（6） 表示每一個受災地區(qū)節(jié)點僅由一輛車提供卸載救災服務；式（7）、（8） 表示車輛k應離開已經(jīng)駛?cè)脒^的受災節(jié)點，并且只?？坑诜峙浣o其運輸任務的受災點；式（9） 中表示，如果車輛k有貨物，則該車執(zhí)行任務，此時目標函數(shù)（2） 增加1。

2 免疫粒子群算法求解

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

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

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

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

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

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

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

步驟四：按照公式（11）、（12） 計算粒子新的位置，取符號變?yōu)槎M制的0,1。

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

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

步驟七：轉(zhuǎn)到步驟二。

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

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

3 實例分析

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

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

表1 受災節(jié)點的需求數(shù)據(jù)

表2 各節(jié)點之間的距離

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

表3 車輛行車路線表

4 結(jié) 論

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

[1] 宋傳平. 我國應急物流系統(tǒng)的構建和保障條件[J]. 中國流通經(jīng)濟，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] 宋遠清，李永生，梁慎清. 需求隨機車輛調(diào)度問題的遺傳算法研究[J]. 計算機技術與發(fā)展，2009,19(2):230-233.

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

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

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

[8] 陳明華，李迎秋，羅耀琪. 應急物流車輛調(diào)配問題的研究[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] 席娜，徐術力. 基于免疫粒子群優(yōu)化算法的物流配送車輛調(diào)度算法[J]. 物流技術，2012,31(12):312-313.