車輛調度問題的全局
—局部最優信息比粒子群算法研究

朱婷婷,單小紅

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

車輛調度問題的全局
—局部最優信息比粒子群算法研究

朱婷婷,單小紅

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

[摘要]文章提出了一種新的改進標準粒子群算法即全局—局部最優信息比粒子群算法。該算法與標準粒子群算法和全局—局部最優最小值粒子群優化算法作了比較,仿真實驗結果表明,該算法在收斂速度、解的質量和魯棒性上都表現出了較優的性能,是求解車輛調度問題的一種較好方法。

[關鍵詞]車輛調度問題；粒子群算法；全局—局部最優信息比；數學模型

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

1引言

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

2車輛調度問題(VRP)的描述及數學模型

VRP描述為：有一個配送中心0,配送車輛K輛和貨運點個N,每輛車的載重量為qi,各個送貨點的需求量為gi,且maxqi≤maxgi,把貨物配送到N個送貨點,使車輛調度問題的目標函數達到最小。

定義變量如下：

(1)

(2)

cij是配送點之間的距離,則VRP的數學模型表示為：

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

3粒子群算法及其改進

3.1粒子群算法

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

粒子在t+1時刻的位置通過下式進行更新：

(11)

(12)

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

3.2改進的粒子群算法

粒子群算法參數的設置對算法的尋優性能起著重要的作用。全局—局部最優最小值粒子群算法(GLBest-PSO)對標準PSO進行了改進,即：

(13)

(14)

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

(15)

4車輛調度問題的GLIR-PSO算法

4.1問題的編碼與解碼

實現該算法的關鍵問題之一是找到一種合適的表達方法,使粒子與解對應。本文根據文獻[3]的思路,將車輛和對應的送貨點的順序表示出來。對于N個送貨點的VRP問題,每個送貨點對應兩個屬性：完成該配送任務的車輛號k和在車輛中的配送順序r,每個粒子對應的2N維向量被分解為兩個N維向量：Xk和Xr,其中Xk表示各配送點的車輛編號,Xr表示各配送點對應的配送順序。速度向量V對應的被分解為Vk和Vr。

假設有7個送貨點的VRP問題,所需車輛數為3,編碼過程如表1所示。

表1　粒子編碼過程

將表1粒子的狀態對應為配送方案[4]為：

車輛1:0→1→0

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

車輛3:0→7→6→0

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

4.2GLIR-PSO算法實現過程

粒子群算法的具體實現步驟如下：

步驟1：初始化粒子群。

①初始化種群規模P,粒子維數2N,w,c1,c2,最大迭代次數Loop count；

②初始化Xk和Xr,使其分別屬于1～K的隨機整數和1～L的隨機實數；初始化Vk和Vr的分量,使其分別屬于-(K-1)～(K-1)的隨機整數和-(L-1)～(L-1)的隨機實數；

③用評價函數Eval評價所有粒子的適應度,若不滿足約束條件則令f=fmax,fmax是一個很大的數；

④初始評價值作為每個粒子的局部極值,最優的初始評價值作為全局極值。

步驟2:更新位置、速度,并輸出優化結果。

①按式(15)計算Vk和Vr,按式(12)計算Xk和Xr,如果超過邊界值則取邊界值；

②用Eval評價所有粒子的適應度；

③更新局部極值和全局極值,若某粒子當前的位置優于pbest,則更新pbest,若粒子群的當前位置優于gbest,則更新gbest；

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

5仿真實驗結果與分析

現有一個配送中心,7個送貨點,設所有車輛的最大裝載量為1t,需求量矩陣為P=[0.89,0.14,0.28,0.33,0.21,0.41,0.57],距離矩陣如表2所示。

表2　距離矩陣

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

表3　車輛最優調度方案

本文將 GLIR-PSO算法與BPSO和GLBest-PSO進行仿真實驗,并對優化結果進行比較。每種算法依次運行20次,其中,GLIR-PSO有13次搜索到最優解,而BPSO和GLBest-PSO分別只有11次和10次,并且GLIR-PSO的20次實驗平均路徑252.73km優于BPSO和GLBest-PSO算法所得結果(304.96km和276.44km),說明GLIR-PSO算法解的質量在一定程度上得到了提高,收斂速度變快。

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

表4　優化結果對比

通過上述仿真實驗有效地驗證了這種新的改進算法——GLIR-PSO算法,有效地避免了標準粒子群算法的“趨同性”,確保正確的搜索方向,且持續地找到全局最優解。

6結論

目前,雖然車輛調度系統已在國內一些領域得到初步應用,但發展很不成熟,存在算法復雜和運行不穩定等缺陷,針對此現狀,本文提出一種新型的GLIR-PSO算法以有效提高車輛調度系統運行的效率性和穩定性,將全局和局部最優信息比引入到算法的更新過程,來對標準粒子群算法進行有效改進,該新型算法有效克服了早熟收斂現象,在收斂速度、解的質量和魯棒性上都表現出了較優的性能。

參考文獻:

[1]李軍,郭耀煌.物流配送車輛優化調度理論與方法[M].北京: 中國物資出版社,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]李寧,鄒彤,孫德寶.帶時間窗車輛路徑問題的粒子群算法[J].系統工程理論與實踐,2004,4(4): 130-135.

[基金項目]國家自然科學基金資助項目(項目編號：71162017);廣西自然科學基金資助項目(項目編號：2011GXNSFB018061);桂林電子科技大學研究生教育創新計劃資助項目(項目編號：GDYCSZ201438)。

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