車輛路徑問題的混沌粒子群算法研究

李 毅，陸百川，劉春旭

(重慶交通大學(xué)交通運輸學(xué)院，重慶 40007)

車輛路徑問題的混沌粒子群算法研究

李 毅，陸百川，劉春旭

(重慶交通大學(xué)交通運輸學(xué)院，重慶 40007)

針對車輛路徑問題中單倉庫非滿載這一基本類型的具體特性，設(shè)計了一種混沌粒子群算法;利用混沌系統(tǒng)的隨機性、規(guī)律性和遍歷性初始化粒子，大范圍覆蓋車輛路徑問題的解空間，加強算法最優(yōu)路徑的搜索能力;通過在求解過程中的次優(yōu)路徑處施加混沌擾動，使算法放棄當(dāng)前求解的路徑，避免結(jié)果為次優(yōu)解。并通過試驗驗證了該算法在車輛路徑問題中具有很強的尋優(yōu)能力。

車輛路徑問題;粒子群算法;混沌系統(tǒng)

車輛路徑問題(Vehicle Routing Problem，VRP)自Dantzing［1］于1959年首次提出后，迅速成為運籌學(xué)、應(yīng)用數(shù)學(xué)、網(wǎng)絡(luò)分析、計算機應(yīng)用及交通工程等學(xué)科交叉領(lǐng)域研究的熱點，受到眾多專家、學(xué)者的極大重視。時至今日，人們對VRP進行了大量的研究，設(shè)計了針對各種約束條件的算法。這些算法種類豐富，但大致可歸納為精確型算法和啟發(fā)式算法兩大類。數(shù)搜索法、動態(tài)規(guī)劃、分支定界法、網(wǎng)絡(luò)流算法等屬于精確型算法。精確型算法的計算量一般隨問題規(guī)模的增大而呈指數(shù)增長。而啟發(fā)式算法則是一種在可接受的計算時間或占用空間下得出待解決問題的滿意解，是一種基于直觀或經(jīng)驗構(gòu)造的算法，它包含構(gòu)造性算法、兩階段法、不完全優(yōu)化法等。在問題的規(guī)模上，啟發(fā)式算法相對于精確型算法已有些許進步。在近20年內(nèi)發(fā)展起來了一批智能優(yōu)化算法，如:禁忌搜索算法、遺傳算法、蟻群算法以及粒子群算法等一類亞啟發(fā)式算法，在大規(guī)模的VRP問題的求解中，得到了很好的研究與應(yīng)用。

粒子群算法(Particle Swarm Optimization，PSO)是Kennedy和Eberhart受鳥群覓食啟發(fā)，于1995年提出的一種群智能優(yōu)化算法，這種算法具有計算簡單、調(diào)控參數(shù)少、魯棒性好等優(yōu)點，已在各類多維連續(xù)空間優(yōu)化問題上取得了非常好的效果。迄今為止，不少研究者設(shè)計了基于粒子群的算法，嘗試解決車輛路徑問題，這些算法包括有基于基本粒子群算法，基于改進粒子群算法，基于混合粒子群算法等［2-5］。改進或是混合粒子群算法都試圖改善單純的基本粒子群算法容易早熟和后期粒子開掘能力差的缺點。筆者針對這缺點，設(shè)計了混沌粒子群算法。該算法是在基本粒子群算法中引入混沌的思想，利用混沌系統(tǒng)的規(guī)律性、隨機性和遍歷性來初始化粒子群，改善粒子在搜索全局上的分布，加強粒子的全局搜索能力，并且在粒子的局部極值點施加混沌擾動，幫助惰性粒子逃離局部極值點，改善基本粒子群算法早熟的缺點。

1 車輛路徑問題描述及數(shù)學(xué)模型

一般可以將基本的車輛路徑問題描述為:存在一個中心倉庫，擁有容量分別為qk(k=1，2，…，K)的K輛車，有L個發(fā)貨點運輸任務(wù)需要完成，以1，2，…，L表示，那么定義第 i個發(fā)貨點的貨運量為gi(i=1，2，…，L)，且有 maxgi≤ maxqk，目的是求滿足貨運需要的所有車輛行駛的最短總路徑。

筆者采用文獻［6］給出的數(shù)學(xué)模型:將中心倉庫編號為0，發(fā)貨點編號為1，2，…，L，任務(wù)及中心倉庫均以點i(i=0，1，…，L)來表示。定義變量如下:

定義Cij為從點i到j(luò)的運輸成本。這里的運輸成本可以是費用、時間、距離，亦或是它們的某種組合等。筆者研究的運輸成本代表的是距離。則車輛優(yōu)化調(diào)度數(shù)學(xué)模型如式(1):

從式(1)可以看出，此模型的每個發(fā)貨點都有車輛配送，并且每一發(fā)貨點只由一輛車來完成。問題的尋優(yōu)就是在保證每條路徑上各發(fā)貨點的總需求量不超過此配送路徑上車輛容量的前提下，完成對所有車輛的總路徑最短的搜尋。

2 混沌粒子群算法

2.1 基本粒子群算法

在PSO中的粒子代表著一個可能的解，多個粒子同時在解空間中飛行，搜尋最優(yōu)解。

PSO的數(shù)學(xué)模型如下:假設(shè)針對VRP問題構(gòu)造的解空間有D維，參與解空間搜索的粒子總數(shù)為n。第i個粒子的位置向量可以表示為 Xi=(xi1，xi2，…，xiD);第i個粒子自身的歷史最優(yōu)位置向量記為Pi=(pi1，pi2，…，piD);群體的歷史最優(yōu)位置向量Pg=(pg1，pg2，…，pgD)定義為所有的 Pi(i=1，2，…，n)中的最優(yōu);第i個粒子的速度向量可以表示為Vi=(vi1，vi2，…，viD)。則每個粒子的位置向量應(yīng)按式(2)、式(3)進行更新:

通過近些年的科學(xué)研究和工程實踐可以發(fā)現(xiàn)，PSO算法在高維空間多極值問題以及動態(tài)目標的尋優(yōu)方面有著搜索速度快，解質(zhì)量高，算法魯棒性好等諸多優(yōu)點。

2.2 引入混沌優(yōu)化的粒子群算法

混沌狀態(tài)廣泛存在于自然現(xiàn)象和社會現(xiàn)象中，其看似混沌，卻有著精致的內(nèi)在結(jié)構(gòu)，具有規(guī)律性、隨機性和遍歷性等獨特的性質(zhì)，它介于確定性和隨機性之間。混沌運動能在一定范圍內(nèi)按其自身“規(guī)律”不重復(fù)遍歷所有狀態(tài)，利用這種性質(zhì)來初始化粒子，可以優(yōu)化粒子群算法的粒子初始分布，加強算法的全局搜索能力。

一個典型的混沌系統(tǒng)是由Logistic方程產(chǎn)生:

高鷹，等［7］將混沌優(yōu)化思想引入到了PSO中，提出了混沌粒子群優(yōu)化算法(Chaos Particle Swarm Optimization，CPSO)。CPSO的思想主要表現(xiàn)在下面兩點:

1)利用混沌方程產(chǎn)生大量差異較大的點來初始化PSO粒子的位置和速度，以此提高PSO群體的遍歷性。在產(chǎn)生大量初始群體的基礎(chǔ)上，擇優(yōu)出粒子群算法的初始群體，加強算法的全局搜索能力。

2)在Pg處利用混沌方程產(chǎn)生大量混沌序列，根據(jù)適應(yīng)度函數(shù)的計算，將最優(yōu)點隨機替換原PSO中的粒子。此舉旨在次優(yōu)解處產(chǎn)生一個混沌擾動，借以幫助惰性粒子離開次優(yōu)解而繼續(xù)搜索。

CPSO計算過程可以用圖1來示意。

圖1 CPSO計算流程Fig.1 Flow chart of the CPSO

3 車輛路徑問題的混沌粒子群算法

借鑒文獻［8］的思路，構(gòu)造一個2L維的空間來對應(yīng)有L個發(fā)貨點任務(wù)的VRP問題。將每個粒子的2L維位置向量X分成兩個L維向量:表示各任務(wù)對應(yīng)車輛的Xv和表示各任務(wù)在對應(yīng)的車輛路徑中的執(zhí)行次序Xr。

例如，若一個VRP問題中有9個發(fā)貨點需要滿足發(fā)貨任務(wù)，車輛數(shù)為3，此時某一粒子的位置向量X若為:

粒子速度向量V則相應(yīng)表示為Vv和Vr。

該表示方法以增加粒子的維數(shù)為代價換取發(fā)貨點與單一配送車輛的對應(yīng)，使解空間的范圍大大縮小。后面的實驗結(jié)果表明維數(shù)的并沒有增加太大的計算復(fù)雜度。

3.1 車輛路徑問題的CPSO算法步驟

在實現(xiàn)CPSO算法求解VRP問題時，需要考慮將實數(shù)化的解空間轉(zhuǎn)換為整數(shù)解空間。因此，求解VRP問題的具體CPSO算法步驟如下:

步驟1:設(shè)置精度要求和最大迭代次數(shù)，以及慣性權(quán)重、學(xué)習(xí)因子。

步驟2:混沌初始化粒子的位置和速度。

1)隨機產(chǎn)生一個2L維的向量X1=(X1v，X1r)，其分量大小均在0～1之間的，L為發(fā)貨點數(shù)量，根據(jù)式(4)，得到 N 個向量 X1，X2，…，XN。

2)向量Xiv乘以K取整(意為取1～K之間的整數(shù))，向量Xir乘以L(意為取1～L之間的實數(shù))。

3)用適應(yīng)度函數(shù)Eval(后述)評價所有粒子，擇優(yōu)選出M個作為初始粒子的位置。

4)隨機產(chǎn)生M個粒子的初始速度V=(Vv，Vr)，Vv取值為 -(K-1)～(K-1)之間的整數(shù)，Vr取值為-(L-1)～(L-1)之間的實數(shù)。

步驟3:將初始適應(yīng)度值作為個體歷史最優(yōu)解Pi，并比較找出種群的最優(yōu)解Pg。

步驟4:重復(fù)執(zhí)行以下步驟，直到滿足精度要求或達到最大迭代次數(shù)。

1)根據(jù)式(2)、式(3)更新粒子的位置和速度，其中Xv向上取整;當(dāng)X、V超過其范圍時按邊界取值。

2)用適應(yīng)度函數(shù)Eval評價所有粒子。

3)更新單個粒子的歷史最優(yōu)值Pi，然后更新種群的全局最優(yōu)值Pg。

4)對全局最優(yōu)值Pg施加混沌擾動，用擾動產(chǎn)生

的最優(yōu)值隨機替代一個粒子。

3.2 CPSO算法中適應(yīng)度函數(shù)Eval定義與作用

CPSO算法具體步驟中的適應(yīng)度函數(shù)Eval有兩個作用:將實數(shù)化的解轉(zhuǎn)換為整數(shù)解和計算車輛的總路徑Z。

1)首先要將計算過程中得到的Xr按升冪排列，并進行整數(shù)化處理，方便行駛距離的計算和后續(xù)的迭代。例如，某一粒子的位置向量為:

則表示第 2、3、4、5、6 號任務(wù)由車 2 完成，這些任務(wù)點所對應(yīng)的 Xr值為(3.2，6.2，1.2，2.5，0.5)，將其值按升冪重新排列Xr。任務(wù)點6所對應(yīng)的值是0.5，最小，將其更新為1;任務(wù)點4對應(yīng)的值1.2次小，將其更新為2，以此類推。經(jīng)過整數(shù)化處理后得到的Xr為:1 4 5 2 3 1 3 1 2。

2)根據(jù)模型計算該粒子所代表方案的距離之和。對于計算過程中出現(xiàn)的不可行解，則此適應(yīng)度值設(shè)為一個可行解不可達到的最大值Tmax。

4 試驗結(jié)果及分析

筆者用MATLAB7編寫了求解VPR問題的CPSO算法、PSO算法和GA算法的程序，并在同一Pentium(R)Dual E2180，1.00GB RAM，Win XP 操作系統(tǒng)的PC機上運行，以此來比較3者之間的性能。

4.1 算法參數(shù)設(shè)定

GA算法參數(shù):種群規(guī)模n=20;參數(shù)ε=20，λ =0.95，X=5，Y=50;交叉概率Pc=0.5;變異概率Pm=0.1;輪盤賭法選擇子代，最大迭代數(shù)100。

PSO算法及CPSO算法參數(shù):粒子群m=20;w=0.729;c1=c2=1.494 45;最大迭代數(shù) 100。

4.2 仿真算例的描述

為了方便進行比較，采用文獻［6］中的例子:有一個7個發(fā)貨點任務(wù)的VRP問題。各任務(wù)的序號和對應(yīng)坐標如圖2。

圖2 各任務(wù)的序號以及對應(yīng)坐標Fig.2 Sequences and coordinates of freight-delivery points

各發(fā)貨點及其對應(yīng)貨運量如表1。

表1 各發(fā)貨點及貨運量Table 1 Freight-delivery points and their volumes

4.3 仿真試驗結(jié)果及分析

將GA、PSO以及CPSO等3種算法各運行50次，比較結(jié)果如表2。

表2 GA、CPSO、PSO算法結(jié)果對比Table 2 Result comparison of algorithm for GA，PSO，CPSO

在各自50次的運行中，3種算法成功尋優(yōu)時的迭代次數(shù)有顯著的差異，其差異表現(xiàn)如圖3。

圖3 GA，PSO，CPSO成功尋優(yōu)迭代次數(shù)比較Fig.3 Comparison of steps for GA，PSO，CPSO successful searching

CPSO方法每次達到最優(yōu)路徑的車輛路徑均為:

車1:0 2 3 4 5 0

車2:010

車3:0 7 6 0

試驗結(jié)果表明，從準確度的角度看，CPSO算法對該問題的搜索成功率為100%，高于PSO算法的92%，遠高于GA算法的64%;從運算時間的角度看，CPSO算法達到最優(yōu)路徑的速度略快于PSO算法，要比GA算法快10倍左右;從算法結(jié)果穩(wěn)定的角度看，CPSO算法的標準差最小，最穩(wěn)定，PSO算法對粒子的初始化依賴較高，穩(wěn)定性最差，GA算法本身成功尋優(yōu)時的迭代次數(shù)較高，沒有另外兩種算法快捷，穩(wěn)定性略高于PSO算法。綜上可知，在該問題上使用CPSO算法的效果要優(yōu)于PSO速度，遠遠優(yōu)于GA算法。

5 結(jié)語

物流配送中，合理安排車輛和路線可以有效減少人力、物力的浪費以及對環(huán)境的污染、提高經(jīng)濟效益。然而因為VRP本身屬于NP難問題，大規(guī)模VRP問題的精確求解難以實現(xiàn)，可以預(yù)見亞啟發(fā)式算法優(yōu)化求解VRP問題是一種行之有效的方法。筆者將CPSO算法應(yīng)用到VRP問題中，并通過具體的實驗與其他求解算法進行比較，試驗結(jié)果表明，本文CPSO算法性能穩(wěn)定，可以很快地找到問題的精確解，是求解車輛路徑問題的一種有效方法。

［1］Dantzing G，Ramser J.The truck dispatching problem［J］.Management Science，1959，10(6):10-80.

［2］李寧，鄒彤，孫德寶.車輛路徑問題的粒子群算法研究［J］.系統(tǒng)工程學(xué)報，2004，19(6):596-600.

Li Ning，Zou Tong，Sun Debao.Particle swarm optimization for vehicle problem［J］.Journal of Systems Engineering，2004，19(6):596-600.

［3］吳斌.車輛路徑問題的粒子群算法研究與應(yīng)用［D］.浙江:浙江工業(yè)大學(xué)，2008.

［4］李相勇.車輛路徑問題模型及算法研究［D］.上海:上海交通大學(xué)，2007.

［5］王正初.車輛路徑問題的改進混合粒子群算法研究［J］.計算機仿真，2008，25(4):267-270.

Wang Zhengchu.Research on improved hybrid particle swarm optimization for vehicle routing problem［J］.Computer Simulation，2008，25(4):267-270.

［6］李軍，郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法［M］.北京:中國地質(zhì)出版社，2001.

［7］高鷹，謝勝利.混沌粒子群算法［J］.計算機科學(xué)，2004，31(8):13-15.

Gao Ying，Xie Shengli.Chaos particle swarm optimization algorithm［J］.Computer Science，2004，31(8):13-15.

［8］Salmen A，Ahmad I，AI-Madani B.Particle swarm optimization for task assignment problem［J］.Microprocessors and Microsystems，2002，26:363-371.

［9］Maurice C，Kennedy J.The particle swarm-explosion，stability，and convergence in a multidimensional complex space［J］.IEEE Transactions on Evolutionary Computation，2002，6(1):58-73.

［10］黃美靈，陸百川.考慮交叉口延誤的城市道路最短路徑［J］.重慶交通大學(xué)學(xué)報:自然科學(xué)版，2009，28(6):1060-1063.

Huang Meiling，Lu Baichuan.Determination of the shortest path considering delays at intersections［J］.Journal of Chongqing Jiaotong University:Natural Science，2009，28(6):1060-1063.

Research on Chaos Particle Swarm Optimization Algorithm for Vehicle Routing Problem

Li Yi，Lu Baichuan，Liu Chunxu
(School of Traffic＆ Transportation，Chongqing Jiaotong University，Chongqing 400074，China)

According to characters of the vehicle routing problem，a novel chaos particle swarm optimization(CPSO)algorithm was proposed to solve the basic type of single depot and non-full load.After the chaos was introduced to the particle swarm optimization(PSO)，the random，regularity and ergodicity were used to initialize particles in order to cover the solution space of the vehicle routing problem in large range，enhance the ability for optimal route searching，and prevent the suboptimal solution of the PSO in the way of exerting chaos disturbance at the place of suboptimal solution to help algorithm to abandon the current searching route.Illustration results showed the CPSO had the strong ability to search the global optimal in the vehicle routing problem.

vehicle routing problem(VRP);particle swarm optimization(PSO);chaos system

U116.2

A

1674-0696(2012)04-0842-04

10.3969/j.issn.1674-0696.2012.04.26

2011-11-28;

2011-12-21

重慶市科技攻關(guān)項目(2009AA6035)

李 毅(1986—)，男，四川綿陽人，碩士研究生，主要從事交通信息工程及控制方面的研究。E-mail:460900012@qq.com。