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

李 毅，陸百川，劉春旭

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

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

李 毅，陸百川，劉春旭

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

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

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

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

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

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

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

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

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

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

2 混沌粒子群算法

2.1 基本粒子群算法

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

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

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

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

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

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

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

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

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

CPSO計(jì)算過程可以用圖1來示意。

圖1 CPSO計(jì)算流程Fig.1 Flow chart of the CPSO

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

筆者用MATLAB7編寫了求解VPR問題的CPSO算法、PSO算法和GA算法的程序，并在同一Pentium(R)Dual E2180，1.00GB RAM，Win XP 操作系統(tǒng)的PC機(jī)上運(yùn)行，以此來比較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 仿真算例的描述

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

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

各發(fā)貨點(diǎn)及其對(duì)應(yīng)貨運(yùn)量如表1。

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

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

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

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

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

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

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

車1:0 2 3 4 5 0

車2:010

車3:0 7 6 0

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

5 結(jié)語

物流配送中，合理安排車輛和路線可以有效減少人力、物力的浪費(fèi)以及對(duì)環(huán)境的污染、提高經(jīng)濟(jì)效益。然而因?yàn)閂RP本身屬于NP難問題，大規(guī)模VRP問題的精確求解難以實(shí)現(xiàn)，可以預(yù)見亞啟發(fā)式算法優(yōu)化求解VRP問題是一種行之有效的方法。筆者將CPSO算法應(yīng)用到VRP問題中，并通過具體的實(shí)驗(yàn)與其他求解算法進(jìn)行比較，試驗(yàn)結(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é)報(bào)，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ìn)混合粒子群算法研究［J］.計(jì)算機(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］.計(jì)算機(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é)報(bào):自然科學(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)項(xiàng)目(2009AA6035)

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