基于改進(jìn)群搜索優(yōu)化算法的車輛路徑問題研究

楊文璐，寧玉富

（1、山東師范大學(xué)管理科學(xué)與工程學(xué)院，山東 濟(jì)南 250014；2、德州學(xué)院不確定系統(tǒng)實(shí)驗(yàn)室，山東 德州 253023）

0 引言

在物流配送活動中，如何確定車輛行駛路徑既能滿足所有客戶的配送需求，又能保證總配送成本最低的問題，被稱為是車輛路徑問題（Vehicle Routing Problem，VRP）。VRP一直以來都是物流配送商最為關(guān)心的問題，也是很多相關(guān)學(xué)者競相研究的焦點(diǎn)與熱點(diǎn)問題。這一問題最早是由Dantzing和Ramser二人在1959年提出的[1]，它的有效解決是減少物流費(fèi)用和提高物流效率的關(guān)鍵。由于VRP早被證明屬于NP-hard問題[2]，一般對于它的研究大多都集中在如何找到極優(yōu)解上。長期以來對于解決VRP的方法研究主要集中在啟發(fā)式算法上，如禁忌搜索算法、模擬退火算法、遺傳算法等。近年來隨著很多學(xué)者對群智能算法的聚焦和大量研究，粒子群算法、蟻群算法、蜂群算法、螢火蟲算法等群集智能算法也越來越多的應(yīng)用于VRP的解決中。

2006年由He和Wu二人提出的群搜索優(yōu)化(GSO)算法[3]也歸屬于眾多群智能算法之中，該算法是源于對群居動物覓食行為的模擬而演化產(chǎn)生，并且建立在PS(Producer-Scrounger)模型基礎(chǔ)之上，經(jīng)過實(shí)驗(yàn)驗(yàn)證表明，標(biāo)準(zhǔn)GSO算法在解決高維多模態(tài)問題上具有明顯的優(yōu)勢[4]，但算法本身存在早熟收斂、搜索精度不高、后期迭代效率不高并容易陷入局部極優(yōu)點(diǎn)的問題。本文針對標(biāo)準(zhǔn)GSO算法存在的問題進(jìn)行了改進(jìn)，并將改進(jìn)后的CMGSO算法應(yīng)用于VRP的研究，獲得了較好的效果。

1 VRP描述與建模

1.1 VRP描述

本文所研究的VRP可描述為：在已知可用配送車輛數(shù)量及其裝載容量、客戶數(shù)量及其需求量的情況下，要求承擔(dān)配送任務(wù)的每輛車只能向其所配送的客戶提供有且僅有一次服務(wù)，并最終回到配送中心，而所有參加配送的車輛不能對同一客戶提供服務(wù)且它們能夠滿足所有客戶的需求，但是最終卻能達(dá)到運(yùn)輸成本（如路程、時(shí)間、花費(fèi)等等）最低的目標(biāo)。

1.2 VRP數(shù)學(xué)建模

根據(jù)1.1的問題描述VRP數(shù)學(xué)模型可表述為：假設(shè)用0來標(biāo)識配送中心，共有n個(gè)客戶需要配送服務(wù)，有m（本文在這里將不對m進(jìn)行研究）輛車進(jìn)行配送活動，每輛車的最大載重量為q，客戶i對貨物的需求量為，第k輛車從客戶i到客戶j記為，客戶i由第k輛車負(fù)責(zé)配送記為，從客戶i到客戶j的運(yùn)輸成本記為，要求在滿足所有約束條件的情況下，達(dá)到運(yùn)輸成本最小（本文主要研究路徑最短的情形）的目標(biāo)。

在建立模型前，先定義如下兩個(gè)變量：

由此可以建立如下目標(biāo)函數(shù)：

問題的約束條件則為：

其中，約束式(4)和(5)共同保證了有且僅有一輛車為某位客戶提供配送服務(wù)，而約束式(6)則確保了每個(gè)客戶的配送需求只由一輛車來滿足，且所有客戶的配送需求由全部的m輛車來共同滿足，最后約束式(7)對每一輛進(jìn)行配送服務(wù)車的載重容量進(jìn)行了規(guī)定。

2 改進(jìn)的群搜索優(yōu)化算法

2.1 GSO算法

GSO算法根據(jù)動物覓食策略將群成員分為發(fā)現(xiàn)者(Producer)、加入者(Scrounger)和游蕩者(Ranger)3 種[5]，并利用生物學(xué)的視覺搜索原理對食物進(jìn)行搜索，其中所有成員都有初始化的位置與角度。在算法開始后的迭代計(jì)算過程中，都將會對所有個(gè)體的適應(yīng)值進(jìn)行計(jì)算比較,并從中搜索出擁有最佳適應(yīng)值的個(gè)體設(shè)置為原始發(fā)現(xiàn)者,之后原始發(fā)現(xiàn)者會在當(dāng)前位置上對周圍一切可行解區(qū)域進(jìn)行尋優(yōu)搜索,尋找是否存在比當(dāng)前位置更好的位置,如果發(fā)現(xiàn)更好位置便向新位置移動,否則保持原位置不變;而群體中的其它成員中80%作為Scrounger按搜索公式跟隨Producer進(jìn)行搜索,其余的20%作為Ranger按搜索方程在覓食區(qū)域內(nèi)進(jìn)行隨機(jī)地游弋[6]。在迭代過程中發(fā)現(xiàn)者始終保持最優(yōu)位置,加入者則向發(fā)現(xiàn)者靠攏,游蕩者起到了加大搜索范圍的作用,每個(gè)個(gè)體都可以在3種角色中切換,直至滿足結(jié)束條件時(shí),算法結(jié)束。算法流程見圖1。

圖1 GSO算法流程圖

2.2 CMGSO算法

在CMGSO算法中對于由交叉操作[7]更新所得到的新加入者來說,如何確定其能否成為替代原有個(gè)體,加入到本次迭代中,主要通過Metropolis準(zhǔn)則[8]的優(yōu)值增量計(jì)算來作為判定標(biāo)準(zhǔn)。上式中的f=（x）為所要滿足的目標(biāo)函數(shù)。將由交叉操作得到的的位置和搜索角度代入目標(biāo)函數(shù)中來計(jì)算,如果△f<0,則替換原有的成員,進(jìn)行下一步來判定是否用替換原有成員進(jìn)入第k次迭代,即公式(8)。這樣保存了較好的移動方向以便預(yù)測到更好的移動位置的同時(shí)又能達(dá)到概率性跳出局部最優(yōu)值的目的。的計(jì)算,否則通過Metropolis準(zhǔn)則中的概率exp(-△f/Maxlter)

其中，rand是[0,1]間的隨機(jī)數(shù)，Maxi-ter 是最大迭代次數(shù)。

對于群體中的Ranger來說，在第k次的迭代中,對于新產(chǎn)生的則不選擇更新，即否則，進(jìn)行更新。

在GSO算法的基礎(chǔ)上通過引入交叉因子和模擬退火算法[9]的思想改進(jìn)了原算法，并提高了該算法的收斂速率和優(yōu)化效率，CMGSO算法的步驟描述如下：

步驟1：選定GSO種群規(guī)模S；

步驟2：初始化每個(gè)群成員的位置和角度；

步驟3：對每個(gè)成員計(jì)算其適應(yīng)度值；

步驟4：比較各個(gè)成員的適應(yīng)度值，記錄自身最優(yōu)值和群體最優(yōu)成員Producer；

步驟5：根據(jù)公式(9)(10)(11)和公式(12)改變粒子的位置和搜索角度；

步驟6：執(zhí)行輪盤賭[10]選擇和交叉操作，生成新一代種群；

步驟8：檢查是否滿足GSO算法終止條件，否則，轉(zhuǎn)至步驟4，繼續(xù)；若是，則求出最優(yōu)解。

3 CMGSO算法在VRP研究中的實(shí)現(xiàn)

將改進(jìn)后的群搜索算法CMGSO應(yīng)用于VRP研究中的具體實(shí)現(xiàn)步驟如下：

1)編碼及初始化。本文在這里采用自然編碼的方法對物流車輛路徑問題中所涉及的配送中心、客戶和車輛進(jìn)行編碼，其中，配送中心編碼為 0，客戶依次編碼為 1，2，…，n,配送車輛則編碼為1，2，…，m。當(dāng)配送中心有k輛車參與配送服務(wù)時(shí)，那么就存在k條配送路徑。假設(shè)只有一個(gè)配送中心，且車輛的排序是給定已知的，則只需對客戶排序進(jìn)行初始化，在這里本文將采用隨機(jī)生成的方式來對所有需要配送的客戶進(jìn)行排序。例如：存在8位客戶需要由3輛車對其進(jìn)行服務(wù)，假設(shè)這8位客戶的隨機(jī)排序?yàn)?2568413，則將由1號車依次對其進(jìn)行配送活動，如果客戶7256的總需求量超過了1號車的最大載重量，而725的總需求量卻小于其最大載重量，則1號車將只對前三位客戶進(jìn)行配送服務(wù)。按照同樣的原則來初始化出2號、3號車的配送路徑。

2)參數(shù)設(shè)置。變量的個(gè)數(shù)設(shè)為Q，種群的規(guī)模設(shè)為S，交叉的概率設(shè)為P。其中P一般設(shè)置在[0.5，1]的區(qū)間上。

其中，F(xiàn)i代表第i個(gè)個(gè)體的適應(yīng)度；Zi為第i個(gè)個(gè)體的目標(biāo)函數(shù)值，即由公式(3)計(jì)算所得到的值；Ni為第i個(gè)個(gè)體的不可行配送路徑數(shù)，而其前的系數(shù)α是對于不可行路徑的損失系數(shù)。

在設(shè)置好適應(yīng)度函數(shù)后，便可以計(jì)算出各個(gè)個(gè)體的適應(yīng)度值并對其進(jìn)行比較排序，按照CMGSO算法的要求從中找出Producer、Scrounger和Ranger三種群成員。

4)尋優(yōu)搜索。在上一步中得到的Producer、Scrounger和Ranger三種群成員分別按照各自的尋優(yōu)搜索公式進(jìn)行計(jì)算，并最終決定這三類成員是否更新和角色變換。其尋優(yōu)搜索公式請分別參見本文的公式(8)、(9)、(10)、(11)及(12)。

5)選擇交叉。用輪盤賭的方式選出當(dāng)前Scrounger中優(yōu)良的個(gè)體作為交叉操作中的父代，并對其按公式(14)進(jìn)行交叉計(jì)算。交叉后的新個(gè)體增加了粒子的多樣性，便于跳出局部最優(yōu)，同時(shí)還可以加快算法的收斂速度。

其中，為交叉后得到的子代；fPi(x)(i=1，2)為參與交叉運(yùn)算的父代；p是D維均勻分布的隨機(jī)數(shù)向量，p的每個(gè)分量都在[0,1]取值。

6)模擬退火。將上一步中獲得的新個(gè)體進(jìn)行模擬退火的過程，利用Metropolis準(zhǔn)則判斷是否對其進(jìn)行保留。若通過驗(yàn)證，則將新個(gè)體保留并進(jìn)入到下一步的計(jì)算中；若未通過，則對其進(jìn)行舍棄操作。

7)輸出最優(yōu)路徑。當(dāng)計(jì)算出的最佳適應(yīng)度值與平均適應(yīng)度值小于所設(shè)定的允許誤差時(shí)，或迭代次數(shù)達(dá)到所設(shè)定的最大值時(shí)，輸出此時(shí)的最優(yōu)結(jié)果即為最優(yōu)車輛路徑；否則將跳入3)并重復(fù)3)-7)的計(jì)算，直至滿足終止條件，算法結(jié)束。

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

根據(jù)以上對于CMGSO算法在VRP中應(yīng)用實(shí)現(xiàn)的具體步驟的表述，采用MATLAB編程，并對文獻(xiàn)[11]中所列出的3輛車服務(wù)于8位客戶的物流VRP實(shí)例進(jìn)行實(shí)驗(yàn)。其中，種群規(guī)模,為100，運(yùn)行代數(shù)為300，交叉概率取0.9，不可行路徑的損失系數(shù)為10；每輛車的最大載重量設(shè)置為10t；1-8號客戶的配送需求量依次為 2.5t、2t、5t、3.5t、2t、4.5t、3t、3.5t；每位被服務(wù)的客戶之間的距離見表1，表中的距離單位為km。

3)適應(yīng)度函數(shù)。適應(yīng)度函數(shù)的選取直接影響到對每個(gè)個(gè)體好壞的判斷，并最終關(guān)系到最優(yōu)解的獲取情況，所以恰當(dāng)選擇適應(yīng)度函數(shù)是非常必要的。針對本文要解決的VRP，將適應(yīng)度函數(shù)設(shè)置為：

表1 客戶間的距離

在計(jì)算機(jī)30次的隨機(jī)求解中，有23次都可求得最優(yōu)解的路徑總長度為850km，與之相對應(yīng)的車輛路徑分別為0640，03120，08570，其中0640表示第一輛車從配送中心出發(fā)先后為6號和4號客戶服務(wù)再回到配送中心。將使用CMGSO算法得到的實(shí)驗(yàn)結(jié)果與使用標(biāo)準(zhǔn)GSO算法和PSO算法的結(jié)果進(jìn)行比較后（見表2），可知在同樣運(yùn)行環(huán)境中且種群規(guī)模相當(dāng)?shù)那闆r下，本文提出的CMGSO算法對于物流中的車輛路徑優(yōu)化問題的解決有著較好的尋優(yōu)效果和收斂效率。

表2 3種算法運(yùn)行結(jié)果的比較

5 結(jié)束語

本文提出了一種將改進(jìn)后的CMGSO算法應(yīng)用于VRP研究的策略，并通過對該算法的應(yīng)用實(shí)現(xiàn)及編程實(shí)驗(yàn)證明了它與標(biāo)準(zhǔn)GSO和PSO算法相比具有較好的尋優(yōu)效果及收斂效率。為VRP的研究和解決提供了一種新的方案和思路。該算法的改進(jìn)主要是在原有GSO的基礎(chǔ)上加入并融合了交叉因子和模擬退火的算子，這樣一來就很好的解決了標(biāo)準(zhǔn)GSO中存在的早熟收斂、搜索精度不高、后期迭代效率不高，以及在后期運(yùn)算中容易陷入局部極優(yōu)點(diǎn)等問題，并使其獲得了更好的最優(yōu)解。

[1]王永鋒，楊育，顧永明，吳彩明.求解帶時(shí)間窗車輛路徑問題的混沌遺傳算法[J].計(jì)算機(jī)應(yīng)用研究，2012,29（7）：2423-2426.

[2]陳迎欣.基于改進(jìn)蟻群算法的車輛路徑優(yōu)化問題研究[J].計(jì)算機(jī)應(yīng)用研究，2012,29（6）：2031-2034.

[3]HE S,WU Q H.A novel group search optimizer inspired by animal behavioral [C].2006 IEEE Congress on Evolutionary Computation,2006:4415-4421.

[4]HE S,WU Q H,SAUNDERS J R.Group search optimizer:an optimization algorithm inspired by animal searching behavior[J].IEEE Transactions on Evolutionary Computation,2009,13(5):973-990.

[5]ZHANG Wen-wen,TENG Shao-hua,LI Li-juan.Improved group search optimization algorithm [J]. Computer Engineering and Applications,2009,45(4):48-51.

[6]房娟艷,曾建潮,崔志華.混合群搜索優(yōu)化算法及其應(yīng)用研究[D].太原：太原科技大學(xué)，計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,2010.

[7]劉鯖潔，陳桂明，劉小方，楊慶.基于遺傳算法的SVM參數(shù)組合優(yōu)化[J].計(jì)算機(jī)應(yīng)用與軟件,2012,29(4):94-100.

[8]CHEN Xiao-juan,XHEN Jing.QoS routing algorithm based on genetic simulated anncaling algorithm [J].Application Research of Computers,2012,29(12):4680-4682.

[9]Metropolis N,Rosenbluth A.W,Rosenbluth M.N,et al.Equations of states calulations for fast computingmachines[J].Jchem Phys,1953,21:1087-1091.

[10]向萬里，馬壽峰.基于輪盤賭反向選擇機(jī)制的蜂群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究,2013,30(1):86-89.

[11]賓松，符卓.求解帶軟時(shí)間窗的車輛路徑問題的改進(jìn)遺傳算法[J].系統(tǒng)工程,2003,21(6):12-14.