黃震

惠州學(xué)院計(jì)算機(jī)科學(xué)系，廣東惠州 516007

混合量子粒子群算法求解車(chē)輛路徑問(wèn)題

黃震

惠州學(xué)院計(jì)算機(jī)科學(xué)系，廣東惠州 516007

1 引言

車(chē)輛路徑問(wèn)題廣泛地應(yīng)用于交通和物流領(lǐng)域，已經(jīng)引起了國(guó)內(nèi)外學(xué)者對(duì)該問(wèn)題進(jìn)行深入的研究，產(chǎn)生了許多種經(jīng)典、智能的求解方法，其中粒子群算法在求解車(chē)輛路徑問(wèn)題上也成為了研究熱點(diǎn)。針對(duì)粒子群算法容易陷入局部最優(yōu)的缺點(diǎn)，很多學(xué)者利用改進(jìn)的粒子群算法對(duì)車(chē)輛路徑問(wèn)題進(jìn)行求解，馬慧民等[1]提出一種引入模擬退火機(jī)制的并行粒子群算法對(duì)車(chē)輛路徑問(wèn)題進(jìn)行求解，該算法可以提高進(jìn)化后期的收斂精度，具有良好的性能。陳嚴(yán)等[2]在基本粒子群算法的基礎(chǔ)上引入了雜交PSO模型和變異算子，并且運(yùn)用罰函數(shù)法將約束優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題，同時(shí)采用實(shí)數(shù)編碼方案，將離散的車(chē)輛路徑問(wèn)題轉(zhuǎn)化成準(zhǔn)連續(xù)優(yōu)化問(wèn)題。張思亮等[3]提出一種粒子群算法和蛙跳算法的混合算法求解車(chē)輛路徑問(wèn)題，采用粒子群算法產(chǎn)生階段最優(yōu)解，利用蛙跳算法對(duì)階段最優(yōu)解進(jìn)一步優(yōu)化，取得比較理想的效果。李婭等[4]提出一種改進(jìn)的混沌粒子群優(yōu)化算法求解車(chē)輛路徑問(wèn)題，在基本混沌粒子群優(yōu)化算法基礎(chǔ)上，引入邏輯斯特函數(shù)對(duì)慣性權(quán)重因子w進(jìn)行非線(xiàn)性調(diào)整，提高了算法的尋優(yōu)能力，有效避免了算法陷入局部最優(yōu)并防止過(guò)早收斂。李德富等[5]提出了掃描粒子群算法，運(yùn)用掃描算法對(duì)礦點(diǎn)進(jìn)行掃描，生成初始可行解鏈，將其作為粒子的初始位置代入到粒子群中搜索，得到粒子種群歷史最優(yōu)位置，將種群粒子最優(yōu)位置逆轉(zhuǎn)錄生成對(duì)應(yīng)的可行解鏈。

本文首先使用量子粒子群算法[6-7]求解車(chē)輛路徑問(wèn)題，實(shí)驗(yàn)結(jié)果表明該算法存在容易陷入局部最優(yōu)的缺點(diǎn)，于是參考了文獻(xiàn)[8]提出的將粒子群算法和遺傳算法相結(jié)合的思想，在基于量子粒子群算法更新了粒子位置之后再進(jìn)行交叉和變異操作，實(shí)驗(yàn)結(jié)果表明改進(jìn)后的算法不僅可以提高局部搜索能力，而且具有良好的全局尋優(yōu)能力和較快的收斂速度。

2 車(chē)輛路徑問(wèn)題的數(shù)學(xué)模型

車(chē)輛路徑問(wèn)題（Vehicle Routing Problem，VRP）是由Dantzig和Ramser于1959年首先提出的[9]，基本車(chē)輛路徑問(wèn)題的描述為某配送中心（編號(hào)為0）有K輛車(chē)，每輛車(chē)最大載重量為w，對(duì)N個(gè)客戶(hù)（編號(hào)為1，2，…，n）進(jìn)行貨物配送，每輛車(chē)從配送中心出發(fā)給若干客戶(hù)送貨，最后回到配送中心，設(shè)客戶(hù)i對(duì)貨物的需求量為qi(i=1,2,…,n)，cij表示客戶(hù)之間的距離。

根據(jù)基本車(chē)輛路徑問(wèn)題的描述，配送系統(tǒng)的變量和數(shù)學(xué)模型定義如下：

其中，式（1）、式（2）為變量的定義，式（3）是保證每輛車(chē)的運(yùn)載能力約束，式（4）是保證每個(gè)用戶(hù)被服務(wù)，式（5）、式（6）保證每個(gè)用戶(hù)有且僅被一輛車(chē)訪(fǎng)問(wèn)，式（7）是本配送系統(tǒng)的目標(biāo)函數(shù)。

3 改進(jìn)的量子粒子群算法求解車(chē)輛路徑問(wèn)題

3.1 量子粒子群算法

量子粒子群算法（QPSO）是指具有量子行為的粒子群算法，根據(jù)文獻(xiàn)[10]的描述，算法中粒子的狀態(tài)由波函數(shù)ψ(x,t)決定，通過(guò)Monte Carlo方法模擬得出粒子位置更新方程如下：

式（8）中p由式（9）給出，式（9）中α1和α2為[0，1]上的均勻分布的隨機(jī)數(shù)，best_l為粒子在第t次迭代的局部最優(yōu)值，best_g為粒子在第t次迭代的全局最優(yōu)值；式（8）中β表示慣性權(quán)值，其值隨著迭代動(dòng)態(tài)變化，一般按照式（10）求值，其中t表示當(dāng)前迭代次數(shù)，tmax表示最大迭代次數(shù)；式（8）中mbest由式（11）給出，表示第t次迭代時(shí)每個(gè)粒子在局部搜索到的最優(yōu)位置的平均值；式（8）中u指的是[0，1]上的均勻分布的隨機(jī)數(shù)，在迭代過(guò)程中當(dāng)u＞0.5時(shí)β前的符號(hào)取負(fù)號(hào)，否則取正號(hào)。

量子粒子群算法對(duì)比粒子群算法具有參數(shù)少、收斂速度快的優(yōu)點(diǎn)，但是由于只有一個(gè)參數(shù)β來(lái)控制粒子的更新，β是隨著迭代次數(shù)的增加而線(xiàn)性減少的，而解決實(shí)際問(wèn)題時(shí)搜索過(guò)程往往是比較復(fù)雜的、非線(xiàn)性的，所以在實(shí)際的優(yōu)化搜索過(guò)程中容易陷入局部最優(yōu)，出現(xiàn)早熟收斂現(xiàn)象。

3.2 改進(jìn)算法求解車(chē)輛路徑問(wèn)題

針對(duì)QPSO可能出現(xiàn)早熟收斂現(xiàn)象，本文對(duì)QPSO進(jìn)行了改進(jìn)，借鑒了遺傳算法的交叉和變異操作。改進(jìn)的算法流程如圖1所示。

圖1 改進(jìn)算法流程圖

3.2.1 初始化粒子群

利用粒子群算法求解實(shí)際問(wèn)題時(shí)，首先需要解決的是粒子的編碼問(wèn)題，本文參考了文獻(xiàn)[11]，采用整數(shù)編碼，具體方式如下：

（1）采用整數(shù)i表示配送中心和客戶(hù)，其中0表示配送中心（有K輛車(chē)），1，2，…，n表示客戶(hù)。

（2）每個(gè)粒子由一個(gè)n維整型向量[a1,a2,…,an]表示，ai∈[1,n]，每個(gè)ai對(duì)應(yīng)一個(gè)客戶(hù)號(hào)。

（3）每個(gè)粒子的解路徑由一個(gè)n+K+1維的整型向量[b1,b2,…,b(n+K+1)]表示，bj∈[0,n]，每個(gè)bj代表配送中心或客戶(hù)，粒子的解路徑按照如下方法求解：

①定義變量W，初始值為0，解路徑的第一維b1賦值為0（表示配送中心）。

②先將粒子向量的第一維a1對(duì)應(yīng)客戶(hù)的需求量與變量W相加，如果W沒(méi)超過(guò)車(chē)輛限重則將a1加入到解向量中，即將a1賦值給解路徑向量的第二維b2，按同樣的方法繼續(xù)計(jì)算后面的每一維，若W不超重則將粒子的當(dāng)前維ai加入到解路徑向量中，若W超重則結(jié)束，并且不把粒子的當(dāng)前維加入到解路徑向量，這樣之前加入到解路徑向量中的客戶(hù)就構(gòu)成了子路徑1。

③在解路徑向量中子路徑1的后面一維分量賦值為0（表示配送中心），然后按照步驟②的方法遍歷粒子向量剩下的維分量，可以求出所有子路徑。

例如某配送中心有2輛車(chē)，每輛車(chē)限重8噸，為8個(gè)客戶(hù)送貨，客戶(hù)的需求量分別是：1，2，1，2，1，4，2，2，設(shè)向量[4 2 8 5 3 1 6 7]為一個(gè)粒子，按照上述方法可以求出其解路徑為[0 4 2 8 5 0 3 1 6 7 0]，對(duì)應(yīng)的子路徑為：0-4-2-8-5-0和0-3-1-6-7-0，每個(gè)子路徑對(duì)應(yīng)一輛車(chē)。

按照上述的粒子編碼方式，本文的初始化粒子群的步驟如下：

（1）隨機(jī)產(chǎn)生1個(gè)粒子，計(jì)算其解路徑，如果解路徑非法則通過(guò)3.2.5節(jié)的方法進(jìn)行調(diào)整，如果調(diào)整不成功則重新產(chǎn)生一個(gè)粒子，按照這種方法產(chǎn)生40個(gè)粒子。

（2）計(jì)算40個(gè)粒子的適應(yīng)值，適應(yīng)值是指解路徑中各點(diǎn)之間的距離之和。

3.2.2 更新粒子位置

本文采用Matlab編寫(xiě)代碼，根據(jù)公式（8）對(duì)粒子位置更新，實(shí)現(xiàn)步驟如下：（1）計(jì)算每次迭代所有粒子局部最優(yōu)的平均值mbest。（2）使用unifrnd（0，1）產(chǎn)生2個(gè)隨機(jī)數(shù)α1和α2，根據(jù)公式（9）計(jì)算p。

（3）根據(jù)公式（10）計(jì)算慣性權(quán)值β，β的值隨著迭代次數(shù)t增加由1.0減至0.5。

（4）使用unifrnd（0，1）產(chǎn)生隨機(jī)數(shù)u，根據(jù)u的值來(lái)確定公式（8）的正負(fù)號(hào)。

（5）計(jì)算的結(jié)果會(huì)出現(xiàn)小數(shù)，本算法采用的是整數(shù)編碼，所以要對(duì)結(jié)果進(jìn)行規(guī)格化，才能得到合法的粒子，規(guī)格化方法如下：

①將更新后的粒子向量的每一維排序。

②將每一維分量的排名賦值給粒子向量。

例如粒子[8 2 7 4 3 6 5 1]按照上述步驟更新后得到向量[36.66 38.40 38.47 34.93 35.63 37.97 37.96 38.46]，規(guī)格化后的粒子向量為[3 6 8 1 2 5 4 7]。

3.2.3 交叉操作

本文加入了遺傳算法中的交叉操作，交叉是指將兩個(gè)父代個(gè)體的部分基因加以替換重組而生成新個(gè)體的操作，是產(chǎn)生新個(gè)體的主要方法，決定了遺傳算法的全局搜索能力，在遺傳算法中起關(guān)鍵作用[12]，本文采用了算術(shù)交叉算子，具體操作步驟如下：

（1）首先選擇進(jìn)行交叉的兩個(gè)父代個(gè)體，本文選擇當(dāng)前局部最優(yōu)的個(gè)體作為父代1，另外再選擇一個(gè)父代2即可，選擇的主要原則[13]是要有一定差異的兩個(gè)個(gè)體，這樣利于后代性狀進(jìn)化，可以在選擇前先設(shè)定某個(gè)閾值Y，嘗試在當(dāng)前所有粒子中隨機(jī)選擇一個(gè)作為父代2，將兩個(gè)父代的適應(yīng)值S1和S2代入公式（12）計(jì)算出d，當(dāng)d大于給定閾值時(shí)進(jìn)行交叉，否則重新選擇父代2，公式（12）中的Smax和Smin分別是當(dāng)前迭代次數(shù)的最大適應(yīng)值和最小適應(yīng)值：

（2）在父代1中隨機(jī)產(chǎn)生2個(gè)不同的交叉位作為交叉區(qū)域。

（3）將父代2中與父代1交叉區(qū)域中相同的客戶(hù)點(diǎn)逐一刪除，每刪除一個(gè)客戶(hù)點(diǎn)的同時(shí)將后續(xù)客戶(hù)點(diǎn)全部前移。

（4）將父代1交叉區(qū)域中的客戶(hù)點(diǎn)插入到父代2的末尾，構(gòu)成子代粒子。

（5）計(jì)算交叉后粒子的適應(yīng)值，如果更優(yōu)則保留子代粒子。

例如，父代1為粒子[8 7 4 2 6 5 3 1]，父代2為粒子[7 8 1 3 6 2 4 5]，隨機(jī)產(chǎn)生2個(gè)交叉位分別為2和5，取出父代1的第2至第5位[7 4 2 6]作為交叉區(qū)域，將父代2中與交叉區(qū)域相同的客戶(hù)點(diǎn)刪除并將交叉區(qū)域插入到末尾，得到子代粒子為[8 1 3 5 7 4 2 6]。

3.2.4 變異操作

變異操作是指將個(gè)體編碼中的某個(gè)基因值用其他等位基因來(lái)替換，從而形成一個(gè)新的個(gè)體，它是產(chǎn)生新個(gè)體的輔助方法，可以改善遺傳算法的局部搜索能力[12]。本文采用的是不同子路徑間單點(diǎn)變異，具體方法是在粒子解路徑的2個(gè)子路徑上分別產(chǎn)生1個(gè)變異位，嘗試將兩者位置交換，如果交換后適應(yīng)值更優(yōu)則保留變異后的粒子，否則不交換。

例如粒子[4 6 2 1 3 5 8 7]對(duì)應(yīng)的解路徑為[0 4 6 2 0 1 3 5 8 7 0]，對(duì)應(yīng)有2個(gè)子路徑：0-4-6-2-0和0-1-3-5-8-7-0，如圖2所示。

圖2 變異前的路徑圖

假設(shè)在子路徑1中產(chǎn)生變異位為7號(hào)客戶(hù)，在子路徑2產(chǎn)生變異位為2號(hào)客戶(hù)，將兩者位置交換完成變異操作，變異后的粒子為[4 6 7 1 3 5 8 2]，變異后的路徑如圖3所示。

圖3 變異后的路徑圖

3.2.5 非法解的調(diào)整

初始化粒子群或者在算法進(jìn)行過(guò)程中產(chǎn)生的粒子可能會(huì)出現(xiàn)非法的解路徑，例如存在一個(gè)粒子[2 8 5 3 6 7 1 4]，按照3.2.1節(jié)的方法可以求出其解路徑為[0 2 8 5 3 0 6 7 1 0 4]，對(duì)應(yīng)的子路徑為：0-2-8-5-3-0、0-6-7-1-0和0-4-0，需要3輛車(chē)才能完成配送任務(wù)，而配送中心只有2輛車(chē)，明顯這是個(gè)非法的解路徑。本文參考了文獻(xiàn)[14]的方法對(duì)非法解進(jìn)行調(diào)整，具體步驟如下：

（1）將最后兩條子路徑合并，合并后上述粒子的子路徑為：0-2-8-5-3-0、0-6-7-1-4-0，這樣就轉(zhuǎn)化為解決最后一條子路徑超重的問(wèn)題。

（2）針對(duì)最后一條子路徑，先取出第一個(gè)客戶(hù)號(hào)，嘗試放入之前的子路徑中是否超重，如果不超重則將第一個(gè)客戶(hù)加入到之前的子路徑中，然后再判斷最后一條子路徑是否超重，如果不超重則調(diào)整結(jié)束，得到合法解，否則取后續(xù)客戶(hù)號(hào)重復(fù)之前的操作。

（3）如果最后一條子路徑的每一個(gè)客戶(hù)號(hào)按照步驟（2）操作都不能得到合法解，則取第一個(gè)客戶(hù)號(hào)嘗試與之前子路徑的每一個(gè)客戶(hù)號(hào)交換位置，如果交換后之前的子路徑不超重且最后一條子路徑也不超重則進(jìn)行交換，此時(shí)調(diào)整結(jié)束得到合法解，否則取后續(xù)客戶(hù)號(hào)重復(fù)之前的操作。

（4）如果上述步驟都不能得到合法解，則舍棄該非法粒子。

按照上述方法調(diào)整非法解路徑[0 2 8 5 3 0 6 7 1 0 4]可以得到合法解路徑[0 7 2 8 5 3 0 6 1 4 0]。

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

4.1 實(shí)驗(yàn)1

實(shí)驗(yàn)1的數(shù)據(jù)采用文獻(xiàn)[4]中的數(shù)據(jù)，即有1個(gè)配送中心配有2輛車(chē)，每輛車(chē)限載重8噸，需要服務(wù)8個(gè)客戶(hù)，具體數(shù)據(jù)如表1所示，表1中第1行和第1列中的0表示配送中心，1～8表示各客戶(hù)號(hào)，最后一行表示各客戶(hù)的需求量（單位為t），表1中的其余數(shù)據(jù)表示配送中心與各客戶(hù)之間的距離（單位為km）。

本文使用Matlab7.0進(jìn)行編程，分別利用QPSO和本文算法對(duì)實(shí)驗(yàn)1的數(shù)據(jù)進(jìn)行仿真，兩種算法的粒子數(shù)設(shè)置為40，迭代次數(shù)設(shè)置為50，本文算法的交叉概率為0.55，變異概率為0.02，對(duì)兩種算法的仿真程序分別運(yùn)行20次，得到運(yùn)送貨物的總運(yùn)輸距離，結(jié)果如表2所示。為了說(shuō)明本文算法的有效性，表2中加入了文獻(xiàn)[4]的實(shí)驗(yàn)結(jié)果。

表1 各客戶(hù)間的距離及各客戶(hù)的需求量

表2 實(shí)驗(yàn)1結(jié)果對(duì)比1）

已知實(shí)驗(yàn)1的理想解為67.5，由表2的結(jié)果可知，QPSO僅獲得5次理想解，平均解為69.3；文獻(xiàn)[4]的算法獲得14次理想解，平均解為68.37；本文算法20次的運(yùn)行結(jié)果都獲得了理想解67.5，明顯優(yōu)于QPSO，也優(yōu)于文獻(xiàn)[4]的算法，實(shí)驗(yàn)結(jié)果說(shuō)明本文算法可以很好地解決小規(guī)模的車(chē)輛路徑問(wèn)題。

4.2 實(shí)驗(yàn)2

實(shí)驗(yàn)2使用的數(shù)據(jù)是中等規(guī)模實(shí)例VRPNC1，VRPNC1是通用的VRP測(cè)試數(shù)據(jù)[15]，VRPNC1中有1個(gè)配送中心，配5輛車(chē)，每輛車(chē)限量160，為50個(gè)客戶(hù)運(yùn)送貨物，已知VRPNC1實(shí)例的理想解為524.61。分別用QPSO、遺傳算法（GA）和本文算法進(jìn)行仿真實(shí)驗(yàn)，設(shè)置粒子數(shù)為40，迭代次數(shù)為400，本文算法的交叉概率為0.55，變異概率為0.02，閾值為0.2。三種算法各運(yùn)行20次，計(jì)算出運(yùn)送貨物的總運(yùn)輸距離，運(yùn)行結(jié)果如表3所示。

表3 實(shí)驗(yàn)2結(jié)果對(duì)比

由表3可知，QPSO和GA算法在20次運(yùn)行中得到的解與VRPNC1實(shí)例的理想解的誤差率都比較大。本文算法在運(yùn)行過(guò)程中獲得了VRPNC1實(shí)例的理想解524.61，最差解的誤差率為4.1%，平均解的誤差率僅為2.5%，取得了比較好的運(yùn)行結(jié)果。

圖4 三種算法的迭代過(guò)程

三種算法得到的最好解的迭代過(guò)程如圖4所示。

由圖4可知，本文算法的最終結(jié)果明顯優(yōu)于QPSO和GA算法，收斂性也更好，QPSO的收斂性較好，但是容易陷入局部最優(yōu)，本文算法很好地解決了這個(gè)問(wèn)題。

由于本文算法加入了交叉和變異操作以及每次產(chǎn)生新的粒子都需要檢測(cè)是否為非法解，需要對(duì)非法解進(jìn)行調(diào)整，所以運(yùn)行時(shí)間較長(zhǎng)。在迭代次數(shù)同為400次，運(yùn)行20次的情況下，QPSO的平均運(yùn)行時(shí)間是8.8 s，GA的平均運(yùn)行時(shí)間是8.3 s，本文算法的平均時(shí)間為23.2 s，這是本文算法需要改進(jìn)的地方。

5 結(jié)束語(yǔ)

本文將量子粒子群算法和遺傳算法相結(jié)合對(duì)車(chē)輛路徑問(wèn)題進(jìn)行求解，給出了具體的粒子位置更新方法、交叉和變異的方法以及對(duì)非法粒子的調(diào)整方法。分別對(duì)8個(gè)客戶(hù)的小規(guī)模實(shí)例和50個(gè)客戶(hù)的中等規(guī)模實(shí)例進(jìn)行仿真，實(shí)驗(yàn)結(jié)果表明小規(guī)模實(shí)例可以迅速得到理想解，中等規(guī)模實(shí)例可以得到理想解，而且平均解與理想解的誤差率也比較小，說(shuō)明本文算法可以有效求解車(chē)輛路徑問(wèn)題，但是本文算法的運(yùn)行時(shí)間較長(zhǎng)，需要在這方面進(jìn)行改進(jìn)。

[1]馬慧民，吳勇，葉春明.車(chē)輛路徑問(wèn)題的并行粒子群算法研究[J].上海理工大學(xué)學(xué)報(bào)，2007，29（5）：435-439.

[2]陳嚴(yán)，劉利民.改進(jìn)型PSO算法在VRP中的應(yīng)用[J].計(jì)算機(jī)工程，2011，37（1）：170-172.

[3]張思亮，葛洪偉.粒子群和蛙跳的混合算法求解車(chē)輛路徑問(wèn)題[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（21）：246-248.

[4]李婭，李丹，王東，等.改進(jìn)的混沌粒子群算法求解車(chē)輛路徑問(wèn)題[J].計(jì)算機(jī)應(yīng)用研究，2011，28（11）：4107-4110.

[5]李德富，郭海湘，劉龍輝，等.改進(jìn)型粒子群優(yōu)化算法求解車(chē)輛徑優(yōu)化問(wèn)題[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（20）：216-223.

[6]Sun Jun，F(xiàn)eng Bin，Xu Wenbo.Particle swarm optimization with particles having quantum behavior[C]//Proceedings of the 2004 Congress on Evolutionary Computation.Portland，OR：IEEE Press，2004：325-331.

[7]dos Santos Coelho L.A quantum particle swarm optimizer with chaotic mutation operator[J].Chaos，Soliton and Fractals，2008，37：1409-1418.

[8]黃為勇.一種采用完全Logistic混沌的PSO-GA優(yōu)化方法[J].計(jì)算機(jī)應(yīng)用研究，2012，29（9）：3236-3239.

[9]Dantzig G B，Ramser J H.The truck dispatching problem[J]. Management Science，1959，6（1）：80-91.

[10]靳雁霞，韓燮，周漢昌.具有量子行為的粒子群優(yōu)化算法的改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（35）：41-43.

[11]楊虎林.改進(jìn)粒子群優(yōu)化算法求解車(chē)輛路徑問(wèn)題的研究[D].南寧：廣西師范學(xué)院，2012.

[12]葛繼科，邱玉輝，吳春明，等.遺傳算法研究綜述[J].計(jì)算機(jī)應(yīng)用研究，2008，25（10）：2911-2916.

[13]周艷聰，孫曉晨，余偉翔.基于改進(jìn)遺傳算法的物流配送路徑優(yōu)化研究[J].計(jì)算機(jī)工程與科學(xué)，2012，34（10）：118-122.

[14]熊寧.基于粒子群優(yōu)化算法求解車(chē)輛調(diào)度問(wèn)題[D].廣州：華南理工大學(xué)，2012.

[15]戴樹(shù)貴，姜昌華，潘蔭榮，等.求解車(chē)輛路徑安排問(wèn)題的混合遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用，2007，43（21）：225-228.

HUANG Zhen

Department of Computer Science,Huizhou University,Huizhou,Guangdong 516007,China

Quantum Particles Swarm Optimization（QPSO）algorithm partly solves the shortcoming such that Particle Swarm Optimization algorithm rate of convergence is not fast enough,while in solving the Vehicle Routing Problem（VRP）.But there is still disadvantage.QPSO falls into local optimum easily.This paper proposes a hybrid Quantum Particle Swarm Optimization algorithm to solve the vehicle routing problem.It uses the QPSO to update particles of initial particle swarm;the crossover operating to particles can improve the global search ability;the mutation operating to particles can improve the local search ability. Applying Matlab as tool for simulation experiment,the experimental result shows that the improved algorithm had good performance to deal with VRP.It can avoid falling into local optimum,and it is better than QPSO and genetic algorithm.

Particles Swarm Optimization（PSO）algorithm;Quantum Particles Swarm Optimization（QPSO）algorithm;crossover;mutation;vehicle routing problem

量子粒子群算法在求解車(chē)輛路徑問(wèn)題時(shí)一定程度上解決了基本粒子群算法收斂速度不夠快的缺點(diǎn)，但是量子粒子群算法仍然存在容易陷入局部最優(yōu)的缺點(diǎn)。利用混合量子粒子群算法對(duì)車(chē)輛路徑問(wèn)題進(jìn)行求解，運(yùn)用量子粒子群算法對(duì)初始粒子群的粒子進(jìn)行更新，對(duì)粒子進(jìn)行交叉操作，可以提高算法的全局搜索能力，進(jìn)行變異操作，可以改善算法的局部搜索能力。以Matlab為工具進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明改進(jìn)后的算法在求解車(chē)輛路徑問(wèn)題時(shí)具有良好的性能，可以避免陷入局部最優(yōu)，對(duì)比量子粒子群算法和遺傳算法具有一定的優(yōu)勢(shì)。

粒子群算法；量子粒子群算法；交叉；變異；車(chē)輛路徑問(wèn)題

A

TP301.6

10.3778/j.issn.1002-8331.1306-0353

HUANG Zhen.Hybrid quantum Particle Swarm Optimization algorithm for vehicle routing problem.Computer Engineering and Applications,2013,49（24）：219-223.

廣東省惠州市科技計(jì)劃項(xiàng)目（No.2012-10）；廣東省惠州學(xué)院自然科學(xué)研究項(xiàng)目（No.2012QN11）。

黃震（1980—），男，講師，主要研究方向：智能算法。E-mail：195146501@qq.com

2013-07-01

2013-08-19

1002-8331（2013）24-0219-05

CNKI出版日期：2013-10-11http://www.cnki.net/kcms/detail/11.2127.TP.20131011.1653.008.html