車輛調(diào)度問題的全局
—局部最優(yōu)信息比粒子群算法研究

朱婷婷,單小紅

(桂林電子科技大學(xué)　商學(xué)院,廣西　桂林　541004)

車輛調(diào)度問題的全局
—局部最優(yōu)信息比粒子群算法研究

朱婷婷,單小紅

(桂林電子科技大學(xué)商學(xué)院,廣西桂林541004)

[摘要]文章提出了一種新的改進(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)的性能,是求解車輛調(diào)度問題的一種較好方法。

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

[DOI]10.13939/j.cnki.zgsc.2016.10.145

1引言

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

2車輛調(diào)度問題(VRP)的描述及數(shù)學(xué)模型

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

定義變量如下：

(1)

(2)

cij是配送點(diǎn)之間的距離,則VRP的數(shù)學(xué)模型表示為：

(3)

(4)

(5)

(6)

(7)

xijk=0或1， i, j=1, 2, …, N; k=1, 2, …, K

(8)

yik=0或1， i, j=1, 2, …, N; k=1, 2, …, K

(9)

X=(xijk)∈S

(10)

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

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

3.1粒子群算法

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

粒子在t+1時(shí)刻的位置通過下式進(jìn)行更新：

(11)

(12)

c1和c2代表學(xué)習(xí)因子；r1和r2為均勻分布在(0,1)區(qū)間的隨機(jī)數(shù)；第d維的位置取值范圍為[-xmax,xmax],速度的取值范圍為[-vmax, vmax]；w代表慣性權(quán)重,令w=初始w-當(dāng)前迭代次數(shù)(初始w-終止w)/最大迭代次數(shù),最后得到的gbes就是粒子群算法的最優(yōu)解。

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

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

(13)

(14)

受到GLBest-PSO的啟發(fā),本文構(gòu)造了全局-局部最優(yōu)信息比粒子群算法(Global-LocalOptimalInformationRatioParticleSwarmOptimization,GLIR-PSO),原速度更新公式(11)改進(jìn)為：

(15)

4車輛調(diào)度問題的GLIR-PSO算法

4.1問題的編碼與解碼

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

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

表1　粒子編碼過程

將表1粒子的狀態(tài)對(duì)應(yīng)為配送方案[4]為：

車輛1:0→1→0

車輛2:0→4→5→3→2→0

車輛3:0→7→6→0

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

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

粒子群算法的具體實(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,如果超過邊界值則取邊界值；

②用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è)所有車輛的最大裝載量為1t,需求量矩陣為P=[0.89,0.14,0.28,0.33,0.21,0.41,0.57],距離矩陣如表2所示。

表2　距離矩陣

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

表3　車輛最優(yōu)調(diào)度方案

本文將 GLIR-PSO算法與BPSO和GLBest-PSO進(jìn)行仿真實(shí)驗(yàn),并對(duì)優(yōu)化結(jié)果進(jìn)行比較。每種算法依次運(yùn)行20次,其中,GLIR-PSO有13次搜索到最優(yōu)解,而BPSO和GLBest-PSO分別只有11次和10次,并且GLIR-PSO的20次實(shí)驗(yàn)平均路徑252.73km優(yōu)于BPSO和GLBest-PSO算法所得結(jié)果(304.96km和276.44km),說明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中顯示：

表4　優(yōu)化結(jié)果對(duì)比

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

6結(jié)論

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

參考文獻(xiàn):

[1]李軍,郭耀煌.物流配送車輛優(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í)間窗車輛路徑問題的粒子群算法[J].系統(tǒng)工程理論與實(shí)踐,2004,4(4): 130-135.

[基金項(xiàng)目]國(guó)家自然科學(xué)基金資助項(xiàng)目(項(xiàng)目編號(hào)：71162017);廣西自然科學(xué)基金資助項(xiàng)目(項(xiàng)目編號(hào)：2011GXNSFB018061);桂林電子科技大學(xué)研究生教育創(chuàng)新計(jì)劃資助項(xiàng)目(項(xiàng)目編號(hào)：GDYCSZ201438)。

[作者簡(jiǎn)介]朱婷婷(1987—),女,河南信陽人,桂林電子科技大學(xué)碩士研究生。研究方向：物流管理與運(yùn)作；單小紅(1989—),女,江西上饒人,桂林電子科技大學(xué)碩士研究生。研究方向：物流管理與運(yùn)作。