朱婷婷　單小紅

[摘要]文章提出了一種新的改進(jìn)標(biāo)準(zhǔn)粒子群算法即全局—局部最優(yōu)信息比粒子群算法。該算法與標(biāo)準(zhǔn)粒子群算法和全局—局部最優(yōu)最小值粒子群優(yōu)化算法作了比較，仿真實(shí)驗(yàn)結(jié)果表明，該算法在收斂速度、解的質(zhì)量和魯棒性上都表現(xiàn)出了較優(yōu)的性能，是求解車(chē)輛調(diào)度問(wèn)題的一種較好方法。

[關(guān)鍵詞]車(chē)輛調(diào)度問(wèn)題；粒子群算法；全局—局部最優(yōu)信息比；數(shù)學(xué)模型

1 引 言

近年來(lái)，研究者們先后將一般啟發(fā)式算法和智能化啟發(fā)式算法用于車(chē)輛調(diào)度問(wèn)題，取得了一些較好的效果。[1]粒子群算法（Particle Swarm Optimization，PSO）是一種模擬鳥(niǎo)群飛行的仿生算法，有著個(gè)體數(shù)目少、計(jì)算簡(jiǎn)單、魯棒性好等優(yōu)點(diǎn)。[2]

2 車(chē)輛調(diào)度問(wèn)題（VRP）的描述及數(shù)學(xué)模型

VRP描述為：有一個(gè)配送中心0，配送車(chē)輛K輛和貨運(yùn)點(diǎn)個(gè)N，每輛車(chē)的載重量為qi，各個(gè)送貨點(diǎn)的需求量為gi，且maxqi≤maxgi，把貨物配送到N個(gè)送貨點(diǎn)，使車(chē)輛調(diào)度問(wèn)題的目標(biāo)函數(shù)達(dá)到最小。

式（3）為目標(biāo)函數(shù)：車(chē)輛行駛的總路徑最??；式（4）：每條線路上配送點(diǎn)需求量之和不超過(guò)最大載重量；式（5）：每個(gè)配送點(diǎn)僅被訪問(wèn)一次；式（6）（7）：每個(gè)送貨點(diǎn)的需求量只能由一輛車(chē)完成；式（8）（9）：變量取值范圍；式（10）：支路消去約束。該問(wèn)題在約束條件下，使所有車(chē)輛的總路徑最小。

3 粒子群算法及其改進(jìn)

3.1 粒子群算法

PSO算法初始化粒子群，在迭代過(guò)程中，粒子將跟蹤個(gè)體極值pbest和全局極值gbest來(lái)更新下一時(shí)刻的位置，設(shè)搜索空間為D維，總粒子數(shù)為n，粒子i在t時(shí)刻的位置為：

3.2 改進(jìn)的粒子群算法

粒子群算法參數(shù)的設(shè)置對(duì)算法的尋優(yōu)性能起著重要的作用。全局—局部最優(yōu)最小值粒子群算法（GLBest-PSO）對(duì)標(biāo)準(zhǔn)PSO進(jìn)行了改進(jìn)，即：

4 車(chē)輛調(diào)度問(wèn)題的GLIR-PSO算法

4.1 問(wèn)題的編碼與解碼

實(shí)現(xiàn)該算法的關(guān)鍵問(wèn)題之一是找到一種合適的表達(dá)方法，使粒子與解對(duì)應(yīng)。本文根據(jù)文獻(xiàn)[3]的思路，將車(chē)輛和對(duì)應(yīng)的送貨點(diǎn)的順序表示出來(lái)。對(duì)于N個(gè)送貨點(diǎn)的VRP問(wèn)題，每個(gè)送貨點(diǎn)對(duì)應(yīng)兩個(gè)屬性：完成該配送任務(wù)的車(chē)輛號(hào)k和在車(chē)輛中的配送順序r，每個(gè)粒子對(duì)應(yīng)的2N維向量被分解為兩個(gè)N維向量：Xk和Xr，其中Xk表示各配送點(diǎn)的車(chē)輛編號(hào)，Xr表示各配送點(diǎn)對(duì)應(yīng)的配送順序。速度向量V對(duì)應(yīng)的被分解為Vk和Vr。

假設(shè)有7個(gè)送貨點(diǎn)的VRP問(wèn)題，所需車(chē)輛數(shù)為3，編碼過(guò)程如表1所示。

這種編碼方式使得每個(gè)配送點(diǎn)都能得到服務(wù)并且每個(gè)送貨點(diǎn)的需求量只能由一輛車(chē)完成，粒子更新的方式簡(jiǎn)單、易懂，求解過(guò)程的計(jì)算量大大減少。

4.2 GLIR-PSO算法實(shí)現(xiàn)過(guò)程

粒子群算法的具體實(shí)現(xiàn)步驟如下：

步驟1：初始化粒子群。

①初始化種群規(guī)模P，粒子維數(shù)2N，w，c1，c2，最大迭代次數(shù)Loop count；

②初始化Xk和Xr，使其分別屬于1～K的隨機(jī)整數(shù)和1～L的隨機(jī)實(shí)數(shù)；初始化Vk和Vr的分量，使其分別屬于-（K-1）～（K-1）的隨機(jī)整數(shù)和-（L-1）～（L-1）的隨機(jī)實(shí)數(shù)；

③用評(píng)價(jià)函數(shù)Eval評(píng)價(jià)所有粒子的適應(yīng)度，若不滿足約束條件則令f=fmax，fmax是一個(gè)很大的數(shù)；

④初始評(píng)價(jià)值作為每個(gè)粒子的局部極值，最優(yōu)的初始評(píng)價(jià)值作為全局極值。

步驟2：更新位置、速度，并輸出優(yōu)化結(jié)果。

①按式（15）計(jì)算Vk和Vr，按式（12）計(jì)算Xk和Xr，如果超過(guò)邊界值則取邊界值；

②用Eval評(píng)價(jià)所有粒子的適應(yīng)度；

③更新局部極值和全局極值，若某粒子當(dāng)前的位置優(yōu)于pbest，則更新pbest，若粒子群的當(dāng)前位置優(yōu)于gbest，則更新gbest；

④若滿足終止條件，輸出gbest；否則返回①。

5 仿真實(shí)驗(yàn)結(jié)果與分析

現(xiàn)有一個(gè)配送中心，7個(gè)送貨點(diǎn)，設(shè)所有車(chē)輛的最大裝載量為1t，需求量矩陣為P=[0.89，0.14，0.28，0.33，0.21，0.41，0.57]，距離矩陣如表2所示。

使用Matlab7.0編程，參數(shù)設(shè)置：P=30，2N=14，wstar=0.9，wend=0.4，c1=c2=2，Loopcount=500，懲罰因子R=100000，最終由3輛車(chē)完成配送任務(wù)，并且最短總路徑為217.81。車(chē)輛最優(yōu)調(diào)度方案如表3所示。

本文將 GLIR-PSO算法與BPSO和GLBest-PSO進(jìn)行仿真實(shí)驗(yàn)，并對(duì)優(yōu)化結(jié)果進(jìn)行比較。每種算法依次運(yùn)行20次，其中，GLIR-PSO有13次搜索到最優(yōu)解，而B(niǎo)PSO和GLBest-PSO分別只有11次和10次，并且GLIR-PSO的20次實(shí)驗(yàn)平均路徑252.73km優(yōu)于BPSO和GLBest-PSO算法所得結(jié)果（304.96km和276.44km），說(shuō)明GLIR-PSO算法解的質(zhì)量在一定程度上得到了提高，收斂速度變快。

在20次實(shí)驗(yàn)中，GLIR-PSO的最短路徑的方差小于BPSO和GLBest-PSO算法所得結(jié)果（137.12645和86.28476），其最短路徑的方差為61.11745，比BPSO和GLBest-PSO算法的結(jié)果小55.4%和29.2%，所以GLIR-PSO算法在解的魯棒性上表現(xiàn)出了較優(yōu)的性能。以上結(jié)論在表4中顯示：

通過(guò)上述仿真實(shí)驗(yàn)有效地驗(yàn)證了這種新的改進(jìn)算法——GLIR-PSO算法，有效地避免了標(biāo)準(zhǔn)粒子群算法的“趨同性”，確保正確的搜索方向，且持續(xù)地找到全局最優(yōu)解。

6 結(jié) 論

目前，雖然車(chē)輛調(diào)度系統(tǒng)已在國(guó)內(nèi)一些領(lǐng)域得到初步應(yīng)用，但發(fā)展很不成熟，存在算法復(fù)雜和運(yùn)行不穩(wěn)定等缺陷，針對(duì)此現(xiàn)狀，本文提出一種新型的GLIR-PSO算法以有效提高車(chē)輛調(diào)度系統(tǒng)運(yùn)行的效率性和穩(wěn)定性，將全局和局部最優(yōu)信息比引入到算法的更新過(guò)程，來(lái)對(duì)標(biāo)準(zhǔn)粒子群算法進(jìn)行有效改進(jìn)，該新型算法有效克服了早熟收斂現(xiàn)象，在收斂速度、解的質(zhì)量和魯棒性上都表現(xiàn)出了較優(yōu)的性能。

參考文獻(xiàn)：

[1]李軍，郭耀煌.物流配送車(chē)輛優(yōu)化調(diào)度理論與方法[M].北京： 中國(guó)物資出版社，2001：76-77.

[2]Kennedy J，Eberhart R C.Particle swarm optimization[C]//Proc.IEEE international conference on neural networks，IV.Piscataway，NJ： IEEE service center，1995： 1942-1948.

[3]Salmen A，Ahmad I，Al-Madani S.Particle swarm optimization for task assignment problem[J].Microprocessors and microsystems，2002（26）： 367-371.

[4]李寧，鄒彤，孫德寶.帶時(shí)間窗車(chē)輛路徑問(wèn)題的粒子群算法[J].系統(tǒng)工程理論與實(shí)踐，2004，4（4）： 130-135.