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

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

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

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

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

1 模型構(gòu)建

1.1 模型的問(wèn)題假設(shè)

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

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

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

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

將模型中所涉及的二進(jìn)制變量定義如下：

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

目標(biāo)函數(shù)：

約束條件：

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

2 免疫粒子群算法求解

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

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

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

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

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

步驟二：計(jì)算每個(gè)粒子的適應(yīng)度函數(shù)（取式目標(biāo)函數(shù)的倒數(shù)），選擇適應(yīng)度函數(shù)最大的個(gè)體。

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

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

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

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

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

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

圖1 免疫粒子群算法求解過(guò)程圖

3 實(shí)例分析

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

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

表1 受災(zāi)節(jié)點(diǎn)的需求數(shù)據(jù)

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

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

表3 車輛行車路線表

4 結(jié) 論

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

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

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

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

[7] 張?jiān)ＨA，潘郁. 基于蟻群算法的應(yīng)急物流配送車輛調(diào)度研究[J]. 物流科技，2009(5):47-49.

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