基于多目標(biāo)VRP的離散型螢火蟲算法研究

董文波,周　康,劉　朔,高全勝

(武漢輕工大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院,湖北 武漢 430023)

?

基于多目標(biāo)VRP的離散型螢火蟲算法研究

董文波,周康,劉朔,高全勝

(武漢輕工大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院,湖北 武漢 430023)

摘要：以車輛路徑問(wèn)題為準(zhǔn)，對(duì)螢火蟲算法進(jìn)行研究。建立了以最小化車輛數(shù)量和行駛路程為目標(biāo)的多目標(biāo)規(guī)劃數(shù)學(xué)模型，提出一種結(jié)合變鄰域搜索算法的離散型螢火蟲算法。該離散型螢火蟲算法的特色之處在于：重新定義了個(gè)體的生成方式和距離移動(dòng)方式；采用變鄰域搜索技術(shù)以增強(qiáng)算法的鄰域搜索能力；在搜索過(guò)程中采用隨機(jī)個(gè)體替代種群中的重復(fù)個(gè)體以維持種群的多樣性；采取精英策略記錄迭代過(guò)程中的最優(yōu)解。通過(guò)不同規(guī)模的Solomon算例進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明所提算法無(wú)論是在車輛數(shù)量還是行駛路程的求解質(zhì)量都取得了很好的效果。

關(guān)鍵詞：離散型螢火蟲算法；車輛路徑問(wèn)題；多目標(biāo)；變鄰域搜索；精英策略

1引言

隨著現(xiàn)代經(jīng)濟(jì)一體化和計(jì)算機(jī)與通信技術(shù)的不斷進(jìn)步，網(wǎng)上購(gòu)物成為流行趨勢(shì)，使得物流業(yè)得到了蓬勃發(fā)展。在現(xiàn)代社會(huì)經(jīng)濟(jì)中，物流承擔(dān)著企業(yè)價(jià)值鏈的基礎(chǔ)活動(dòng)，其支出費(fèi)用占生產(chǎn)成本的比重逐漸增加，縮減物流部分的支出費(fèi)用，能夠讓企業(yè)在行業(yè)競(jìng)爭(zhēng)中占得優(yōu)勢(shì)地位。所以現(xiàn)在許多生產(chǎn)企業(yè)已經(jīng)把目光轉(zhuǎn)向了物流配送供應(yīng)鏈問(wèn)題上。而車輛路徑問(wèn)題(Vehicle Routing Problem,VRP)是物流配送研究的重要內(nèi)容[1]，對(duì)它進(jìn)行合理的調(diào)度和優(yōu)化，能夠改善企業(yè)在物流經(jīng)濟(jì)方面的支出[2]。VRP的內(nèi)容是對(duì)于一些地理位置分散的客戶[3]，配送中心負(fù)責(zé)安排車隊(duì)，組織合理的行駛路線向這些客戶分送貨物[4]，以滿足這些客戶不同單位的貨物需求。在規(guī)定的約束限制下，取得運(yùn)輸成本最小。由于在實(shí)際生產(chǎn)和生活中，郵局投遞安排、公交車路線安排、電力調(diào)度問(wèn)題、快件的收發(fā)、航空和鐵路時(shí)間表制定以及廢品收集等很多實(shí)際生活問(wèn)題都可以抽象映射成為VRP。由此可見(jiàn)，VRP在現(xiàn)實(shí)研究中具有非常重要的意義[5]。所以車輛路徑問(wèn)題被提出后，很快便引起了包括數(shù)學(xué)、計(jì)算機(jī)學(xué)科等在內(nèi)的眾多學(xué)科和相關(guān)領(lǐng)域的專家極大重視，至今仍然是研究的熱點(diǎn)問(wèn)題之一[6-8]。

由于VRP已經(jīng)被證明是NP-Hard問(wèn)題，所以求解VRP的算法需要在合理的時(shí)間內(nèi)得到盡可能優(yōu)的解，這樣就必須充分利用問(wèn)題本身的限制來(lái)改進(jìn)算法。復(fù)雜的VRP限制條件造成VRP分支眾多，其中某一分支的研究成果可對(duì)其他分支的解決提供借鑒，能促進(jìn)各個(gè)分支的共同發(fā)展。因此VRP在理論研究和學(xué)術(shù)研究中具有重要意義和價(jià)值。近些年來(lái)學(xué)者們對(duì)其進(jìn)行實(shí)驗(yàn)研究，各種類型的求解算法層出不窮。目前這些算法大體上可分為包括分支定界法、整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃等在內(nèi)的確定性型算法和包括構(gòu)造法、兩階段法及改進(jìn)型算法等在內(nèi)的啟發(fā)式算法這兩大類[9]。其中，確定型算法能夠準(zhǔn)確的求出問(wèn)題的解，但是這些算法的缺點(diǎn)是只能解決小規(guī)模問(wèn)題，并且消耗的時(shí)間比較長(zhǎng)；啟發(fā)式算法雖然可以求得問(wèn)題的解，但是求解精度不高。另外，還有一類就是這二十年內(nèi)新發(fā)展起來(lái)的群智能優(yōu)化算法，例如：基于“優(yōu)勝劣汰”規(guī)則的遺傳算法[10]、模仿螞蟻行為的人工蟻群算法[11]、基于物理現(xiàn)象的模擬退火算法[12]、模仿鳥類飛行的粒子群優(yōu)化算法[13]以及禁忌搜索算法[14]等，這些方法在某些文獻(xiàn)分類中亦被叫做亞啟發(fā)式算法。

螢火蟲群優(yōu)化算法(Glowworm Swarm Optimization, GSO)是一種新型群智能仿生優(yōu)化算法，由印度兩位學(xué)者Ghose和Krishnanand提出[15-16]。GSO算法的仿生原理是：自然界中的螢火蟲通過(guò)尾部的熒光素發(fā)出亮光，以此來(lái)吸引同伴向自己移動(dòng)，以達(dá)到求偶或覓食的目的。螢火蟲算法的特色之處在于每一只螢火蟲本身都攜帶不同單位數(shù)量的熒光素[17]，在螢火蟲種群中飛行的過(guò)程中能夠進(jìn)行實(shí)時(shí)的更新，并可利用自身的感知范圍來(lái)決定搜索范圍及路徑。GSO算法的特點(diǎn)是仿生計(jì)算模式簡(jiǎn)潔、算法的穩(wěn)健性較強(qiáng)、可調(diào)參數(shù)較少。目前，GSO算法已經(jīng)成功應(yīng)用于信號(hào)源定位、復(fù)雜多目標(biāo)函數(shù)優(yōu)化、感應(yīng)器噪音處理、數(shù)值優(yōu)化計(jì)算、有害氣體泄漏檢測(cè)、聚類分析和多模態(tài)函數(shù)優(yōu)化等方面，并表現(xiàn)出了良好的性能。

2VRP和GSO

2.1VRP數(shù)學(xué)模型

假設(shè)存在一個(gè)配送中心倉(cāng)庫(kù)對(duì)車輛進(jìn)行調(diào)配任務(wù)，其中有V輛車可提供配送服務(wù)，容量分別為qv(v=1, 2,…,V)[18]；現(xiàn)需對(duì)L個(gè)客戶進(jìn)行配送任務(wù)，客戶分別以序號(hào)1, 2, …, L來(lái)表示，若第i個(gè)客戶的貨物需求量為Ni(i=1,2,3,…,L)，且客戶最大貨物需求量小于當(dāng)前配送車輛的載重量，求最少需要安排的車輛數(shù)和最短車輛行駛距離。

為便區(qū)別，以編號(hào)0代表配送中心，客戶則分別以編號(hào)1,2,3,…,L數(shù)字表示[19]，任務(wù)及配送中心均以點(diǎn)i(i=0,1,2,…,L)來(lái)表示。定義變量如下：

用cij代表客戶i到客戶j的路程距離[20]。最后可對(duì)車輛路徑問(wèn)題進(jìn)行數(shù)學(xué)建模為：

在該數(shù)學(xué)模型中，數(shù)學(xué)表達(dá)式表示的約束條件的含義為：被配送的客戶都能夠得到車輛的配送服務(wù)，但是每個(gè)客戶只能在配送路徑中出現(xiàn)一次[21]。同時(shí)每輛車的最大載重量要能夠滿足該車服務(wù)的所有客戶的總需求量。規(guī)劃目標(biāo)是找出盡可能少的車輛數(shù)參加配送任務(wù)，使得運(yùn)輸代價(jià)最小，即盡可能使所有車輛路徑之和Z和車輛數(shù)V達(dá)到最小。

2.2標(biāo)準(zhǔn)GSO及其數(shù)學(xué)模型

標(biāo)準(zhǔn)GSO包括以下5個(gè)步驟：

Step1：將函數(shù)目標(biāo)值J(xi(t))用公式(1)轉(zhuǎn)化為相應(yīng)的熒光素值li(t)；

Step3：計(jì)算路徑選擇概率，確定螢火蟲的飛行路徑。用公式(2)計(jì)算螢火蟲個(gè)體i對(duì)于自身鄰域集合內(nèi)其他螢火蟲的路徑選擇概率pij(t)；

Step4：向目標(biāo)螢火蟲飛行。對(duì)于螢火蟲i，在其鄰域集中選擇移動(dòng)對(duì)象j，向之方向飛行，根據(jù)公式(3)刷新飛行過(guò)后螢火蟲i所處的位置；

Step5：根據(jù)螢火蟲鄰居密度的影響，由公式(4)調(diào)整螢火蟲i的鄰域半徑的值。

li(t)=(1-ρ)li(t-1)+γJ(xi(t)).

(1)

(2)

(3)

β(nt-|Ni(t)|)}}.

(4)

其中

ρ∈[0,1]—熒光素?fù)]發(fā)因子；

t—當(dāng)前迭代次數(shù)；

xi(t)—第i只螢火蟲在時(shí)刻t所處的位置；

γ∈[0,1]—熒光素更新率；

rs—螢火蟲個(gè)體的最大鄰域半徑；

β—鄰域半徑更新率；

nt—螢火蟲個(gè)體鄰域集內(nèi)包含的螢火蟲數(shù)目的閥值；

s為螢火蟲每次飛行的前進(jìn)步長(zhǎng)[17-18]。

3離散型螢火蟲算法的設(shè)計(jì)

標(biāo)準(zhǔn)GSO只能解決連續(xù)論域中的函數(shù)優(yōu)化問(wèn)題，為解決VRP，要離散化GSO，所以下面提出離散型螢火蟲算法(DGSO)。在DGSO算法中，螢火蟲個(gè)體i被編碼后表示一條可行路徑的編碼，則螢火蟲在向目標(biāo)螢火蟲飛行的過(guò)程中，每一步的飛行，其飛行動(dòng)作對(duì)應(yīng)于相應(yīng)該編碼的一種變換操作[10]。

3.1路徑編碼、解碼和構(gòu)造初始螢火蟲群的設(shè)計(jì)說(shuō)明

設(shè)定位置編碼采用自然數(shù)編碼機(jī)制(c1,c2, …,cn)，其中c1,c2,…,cn是自然數(shù)1到n的自然排列，坐標(biāo)ci代表一個(gè)顧客點(diǎn)，坐標(biāo)位的順序表示車輛訪問(wèn)顧客點(diǎn)的次序。解碼時(shí)，按照位置編碼順序依次將顧客點(diǎn)插入到路徑中；若插入的顧客點(diǎn)違反車輛最大載重量約束，則重新使用一輛車來(lái)服務(wù)該顧客點(diǎn)；直到所有的顧客被服務(wù)。

初始螢火蟲群采用N個(gè)顧客結(jié)點(diǎn)隨機(jī)排列的方式來(lái)產(chǎn)生。若螢火蟲群規(guī)模過(guò)大則計(jì)算量增加，影響算法收斂的時(shí)間；若螢火蟲群數(shù)量過(guò)少，則智能搜索算法的搜索性能下降，所以將問(wèn)題規(guī)模和螢火蟲群規(guī)模相關(guān)聯(lián)，動(dòng)態(tài)確定螢火蟲群規(guī)模。

3.2螢火蟲個(gè)體間距離的創(chuàng)新

兩個(gè)編碼的差異性是編碼對(duì)應(yīng)的顧客點(diǎn)之間的差異性累積而成的，因此，如何刻畫兩個(gè)編碼對(duì)應(yīng)的顧客點(diǎn)之間的差異性就是設(shè)計(jì)螢火蟲個(gè)體間距離的核心問(wèn)題。由于兩個(gè)顧客點(diǎn)之間的實(shí)際差異就是這兩個(gè)顧客點(diǎn)之間的實(shí)際路程長(zhǎng)度，因此，為了更好地刻畫并反映螢火蟲個(gè)體之間真實(shí)的位置距離，對(duì)兩個(gè)顧客點(diǎn)之間的實(shí)際差異選擇了兩個(gè)顧客點(diǎn)的弧距離，由此設(shè)計(jì)了新的螢火蟲距離。

設(shè)螢火蟲個(gè)體i和j在t的編碼分別為：xi(t)=(xi1,xi2,…,xi3)和xj(t)=(xj1,xj2,…,xj3)，則螢火蟲個(gè)體i,j在t時(shí)刻的編碼差異度可以按如下形式進(jìn)行定義：

(5)

其中dij(t)為個(gè)體i,j在第t次迭代每一維上的弧距離；M為權(quán)矩陣中每一行的最大值之和。所以δij(t)∈[0, 1]；因?yàn)闄?quán)矩陣在數(shù)學(xué)形式上是對(duì)稱的，所以δij(t)也是對(duì)稱的，即δij(t)=δji(t)。

基于上面定義的針對(duì)兩只螢火蟲編碼的差異度，可以設(shè)計(jì)螢火蟲個(gè)體i與螢火蟲個(gè)體j在t時(shí)刻的距離計(jì)算公式Distij(t)為：

Distij(t)=c×δij(t).

(6)

其中c為一個(gè)常數(shù)，δij(t)為螢火蟲個(gè)體i和j編碼的差異度。

該距離既反映了螢火蟲編碼實(shí)際的差異性，也為下面的螢火蟲位置更新規(guī)則的設(shè)計(jì)奠定了基礎(chǔ)。

3.3螢火蟲位置更新規(guī)則的創(chuàng)新

為了在離散化螢火蟲算法過(guò)程中繼承連續(xù)螢火蟲算法的位置更新思想，在此基于螢火蟲個(gè)體間距離的概念設(shè)計(jì)了移動(dòng)步長(zhǎng)s，給出了向移動(dòng)對(duì)象移動(dòng)s步的更新規(guī)則。

在移動(dòng)階段，首先產(chǎn)生一個(gè)s維的隨機(jī)數(shù)r(s)=(r1,r2, …,rs)，其中ri≠rj(i,j∈[1,n])。對(duì)于顧客數(shù)為n的VRP，位置編碼是一個(gè)n維序列，對(duì)螢火蟲位置編碼x=(x1,x2, …,xn)，移動(dòng)目標(biāo)y=(y1,y2, …,yn)和s維的隨機(jī)數(shù)rk，位置編碼更新如下：

temp=x[rk]；

x[rk]=y[rk]；

x[y[rk]]=temp.

其中k∈[1,s]。該編碼更新方式繼承了標(biāo)準(zhǔn)GSO的位置更新公式。根據(jù)3.2小節(jié)求出螢火蟲x和螢火蟲y之間的距離，螢火蟲x在每次迭代過(guò)程中向螢火蟲y飛行s步長(zhǎng)的距離，x和y編碼的差異性會(huì)相應(yīng)減少s個(gè)單位，經(jīng)過(guò)一定的迭代過(guò)程，x和y的編碼會(huì)趨于一致性，即螢火蟲x飛到螢火蟲y所在的位置上。

3.4引入變鄰域搜索技術(shù)

引入變鄰域搜索技術(shù)可以增強(qiáng)DGSO算法的鄰域?qū)?yōu)能力。變鄰域搜索的具體操作步驟是：將更新后的螢火蟲編碼個(gè)體作為初始解，隨機(jī)選擇以下兩種鄰域操作中的一種操作進(jìn)行鄰域搜索，如果當(dāng)前解得到優(yōu)化，但在優(yōu)化后期一直保持不變，則說(shuō)明達(dá)到了局部最優(yōu)解，結(jié)束鄰域搜索過(guò)程，進(jìn)行精英比較；如果當(dāng)前解在算法所規(guī)定的迭代次數(shù)內(nèi)仍沒(méi)有得到優(yōu)化時(shí)，則結(jié)束鄰域搜索過(guò)程。由于算法不斷迭代，螢火蟲群中的螢火蟲個(gè)體會(huì)飛于相同的位置，即表現(xiàn)為螢火蟲個(gè)體的編碼會(huì)逐漸相同，因此在算法每次迭代過(guò)程中，隨機(jī)產(chǎn)生一組螢火蟲個(gè)體編碼，代替重復(fù)編碼個(gè)體，維持螢火蟲種群的多樣化，使得螢火蟲有更廣闊的空間以飛行。

鄰域操作：

(1)交換：對(duì)隨機(jī)產(chǎn)生的兩個(gè)不同的數(shù)，交換這兩個(gè)數(shù)代表的編碼。

(2)反轉(zhuǎn)：對(duì)隨機(jī)產(chǎn)生的兩個(gè)不同的數(shù)，將這兩個(gè)隨機(jī)數(shù)之間的編碼反轉(zhuǎn)。

在標(biāo)準(zhǔn)螢火蟲算法中，迭代過(guò)程中產(chǎn)生的最好的狀態(tài)的解隨著迭代的進(jìn)行，在迭代后期可能不會(huì)再出現(xiàn)，造成該次迭代運(yùn)算的計(jì)算精度下降。為了克服以上缺陷，需要引入精英策略來(lái)記錄解的最優(yōu)狀態(tài)。在算法每次迭代中，將當(dāng)代最優(yōu)位置的螢火蟲和精英螢火蟲對(duì)比，如果當(dāng)代最優(yōu)位置的螢火蟲比精英螢火蟲所處位置更好，則更新精英螢火蟲，否則保持精英螢火蟲位置不變。

3.5基于變鄰域搜索的DGSO算法

基于變鄰域搜索的DGSO算法(以下簡(jiǎn)稱“本算法”)的具體步驟如下：

Step2：對(duì)于螢火蟲個(gè)體i，計(jì)算螢火蟲個(gè)體i路徑編碼代表路徑的目標(biāo)函數(shù)值，根據(jù)式(1)將目標(biāo)函數(shù)值轉(zhuǎn)化為螢火蟲熒光索值；

Step4：計(jì)算路徑選擇概率，確定螢火蟲的飛行路徑。根據(jù)公式(2)計(jì)算螢火蟲個(gè)體i對(duì)于自身鄰域集合內(nèi)其他螢火蟲的路徑選擇概率pij(t)[19]。根據(jù)概率機(jī)制(輪盤賭方法)選定目標(biāo)螢火蟲；若鄰域集為空，則說(shuō)明該螢火蟲是一個(gè)局部最亮螢火蟲，編碼表示是問(wèn)題的一個(gè)局部最優(yōu)值，則轉(zhuǎn)到Step6進(jìn)行鄰域優(yōu)化；

Step5：產(chǎn)生一個(gè)s維序列r=(r1,r2, …,rs)，其中ri≠rj(i,j∈[1,n])。根據(jù)3.3節(jié)更新螢火蟲個(gè)體i編碼xi(t)上的每一維數(shù)據(jù)；

Step6：對(duì)新得到的螢火蟲個(gè)體編碼用變鄰域搜索算法進(jìn)行局部?jī)?yōu)化；

Step7：根據(jù)螢火蟲鄰居密度的大小和公式(4)動(dòng)態(tài)調(diào)整螢火蟲個(gè)體i的鄰域半徑的大?。?/p>

Step8：判斷當(dāng)前迭代次數(shù)是否達(dá)到了最大迭代次數(shù)或者違反算法結(jié)束條件，如果未達(dá)到結(jié)束條件，返回到Step2，賦值i=i+1，按步驟順序繼續(xù)迭代；否則，程序終止，輸出最優(yōu)螢火蟲代表的全局最優(yōu)解和全局最優(yōu)路徑。

4仿真實(shí)驗(yàn)與分析

為了測(cè)試本算法的正確性和有效性，且使測(cè)試結(jié)果更具可比性和說(shuō)服力，使用公開的標(biāo)準(zhǔn)測(cè)試算例(benchmark instances)對(duì)所提出的算法進(jìn)行測(cè)試。數(shù)據(jù)來(lái)源于國(guó)際上公認(rèn)的VRP數(shù)據(jù)庫(kù)(http://www.branchandcut.org/)。采用VC++6.0進(jìn)行編程，實(shí)驗(yàn)環(huán)境為：

4.1DGSO算法參數(shù)的選取

本算法的參數(shù)取值可分為固定參數(shù)和可調(diào)參數(shù)[27-28]。其中迭代次數(shù)對(duì)算法收斂性能的影響比較復(fù)雜，其取值不能過(guò)小，否則難以得到滿意的結(jié)果，但也并不是值越大越好，迭代次數(shù)過(guò)大，運(yùn)算時(shí)間就會(huì)加長(zhǎng)。其實(shí)際取值需要根據(jù)問(wèn)題的規(guī)模n而設(shè)定。如果想要獲得或接近最優(yōu)解就需要將迭代次數(shù)取值大些。根據(jù)不同的問(wèn)題規(guī)模，設(shè)置不同的迭代次數(shù)做多次運(yùn)行。參數(shù)調(diào)優(yōu)的參考文獻(xiàn)[27]和文獻(xiàn)[28]，并根據(jù)VRP問(wèn)題做了不同的調(diào)整。我們分別取了兩組參數(shù)，并對(duì)這兩組參數(shù)進(jìn)行了算法對(duì)比實(shí)驗(yàn)，對(duì)于每組實(shí)驗(yàn)參數(shù)，程序分別執(zhí)行20次。具體結(jié)果見(jiàn)表1。

參數(shù)組1：ρ=0.5,γ=0.5,β=0.09,nt=6,

s=3,l0=5, 種群150；

參數(shù)組2：ρ=0.3,γ=0.7,β=0.08,nt=10,

s=3,l0=5, 種群200。

表1參數(shù)組對(duì)比實(shí)驗(yàn)結(jié)果

算例出現(xiàn)的最優(yōu)解出現(xiàn)最優(yōu)解次數(shù)平均值參數(shù)組1參數(shù)組2參數(shù)組1參數(shù)組2參數(shù)組1參數(shù)組2An55k91074.961074.4624301075.761074.46Bn45k5753.96753.96615756.62755.67En51k5524.61524.61830534.94524.61Fn72k4244.91242.441021250.34245.36Pn50k7560.03559.861525561.52560.87

從表1可以看出，從出現(xiàn)的最優(yōu)解來(lái)看，在算例Bn45k5求解結(jié)果相同，而在其余算例上，參數(shù)組2出現(xiàn)的最優(yōu)解要優(yōu)于參數(shù)組1出現(xiàn)的最優(yōu)解；從出現(xiàn)最優(yōu)解次數(shù)來(lái)看，參數(shù)組2出現(xiàn)最優(yōu)解的次數(shù)要多于參數(shù)組1，這說(shuō)明參數(shù)組2在解空間中的搜索能力要強(qiáng)于1。所以采取參數(shù)組2作為算法在接下來(lái)的仿真實(shí)驗(yàn)中的參數(shù)。

4.2實(shí)驗(yàn)對(duì)比與分析

4.2.1與現(xiàn)有算法的對(duì)比實(shí)驗(yàn)

首先，根據(jù)文獻(xiàn)[14]中的實(shí)例1，對(duì)其做了仿真實(shí)驗(yàn)，并與文獻(xiàn)[14]中提出的禁忌搜索算法做了對(duì)比。具體對(duì)比結(jié)果見(jiàn)表2(注：“/”表示“DGSO/禁忌搜索算法”；“C”表示配送總距離；“V”表示使用的車輛數(shù)；“T”表示程序運(yùn)行的時(shí)間)。

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

計(jì)算次序12345678910平均C109/106109/107109/103109/104109/112109/108109/107109/110109/104109/109109/107V3/43/43/43/43/43/43/43/33/43/33/3.8T22222222222

從表2可以看出，本算法對(duì)實(shí)例1求解10次，每次均得到較高質(zhì)量的解，其求得的車輛行駛距離平均值為109.7 km，平均使用車輛數(shù)為3。車輛對(duì)應(yīng)的配送路徑具體為:

路徑1：(0-18-17-3-4-14-0)；路徑2：(0-20-11-6-19-7-1-5-0)；

路徑3：(0-10-2-12-9-15-16-13-8-0)。

與文獻(xiàn)[14]中提出的禁忌搜索算法相比，本文算法求出的車輛數(shù)要少于禁忌搜索算法；在車輛數(shù)相同時(shí)，本算法求出的車輛行駛路徑更短，即總體優(yōu)于禁忌搜索算法。從平均值可以得出本算法的求解結(jié)果更穩(wěn)定，即算法魯棒性較強(qiáng)。從計(jì)算時(shí)間來(lái)看，本算法求解此規(guī)模問(wèn)題僅需2秒，計(jì)算效率較高。

為了進(jìn)一步說(shuō)明本算法的優(yōu)勢(shì)，下面分別與爬山算法、遺傳算法和模擬退火算法三種算法做對(duì)比實(shí)驗(yàn)。具體對(duì)比結(jié)果見(jiàn)表3。

表3各種算法對(duì)實(shí)例1計(jì)算結(jié)果的對(duì)比

算法類型爬山算法模擬退火算法遺傳算法本算法平均配送總距離128.0109.5140.1109.7平均使用車輛數(shù)3.93.943首次搜索到最終解的平均搜索次數(shù)893.51201211812500

在表3中，從求解結(jié)果看，本算法的尋優(yōu)能力明顯優(yōu)于爬山算法和遺傳算法，雖車輛行駛距離值略高于模擬退火算法，但是本算法求出的平均車輛數(shù)低于模擬退火算法；從首次搜索到最終解的平均搜索次數(shù)來(lái)看，本算法的計(jì)算效率較高，在較短的迭代次數(shù)內(nèi)就可以搜索到滿意解；從算法的穩(wěn)健性來(lái)看，本算法無(wú)論從車輛數(shù)還是距離值，求出的結(jié)果都更穩(wěn)定，優(yōu)于這三種算法。

根據(jù)以上實(shí)驗(yàn)對(duì)比與分析，可以歸納本算法具有以下特點(diǎn)：(1)對(duì)于VRP，在問(wèn)題規(guī)模一定的情況下，求得問(wèn)題解的質(zhì)量較高；(2)本算法尋優(yōu)效果強(qiáng)，可以在很短時(shí)間內(nèi)收斂到問(wèn)題的解，計(jì)算效率較高；(3)從平均值可以看出，本算法所求得的問(wèn)題結(jié)果很穩(wěn)定，說(shuō)明本算法求解性能比較穩(wěn)定。

4.2.2Solomon算例對(duì)比實(shí)驗(yàn)

本算法采用標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)(http://www.branchandcut.org)中的VRP算例。并和人工蜂群算法(ABC)做了對(duì)比。其計(jì)算結(jié)果見(jiàn)表4。

表4Solomon算例的計(jì)算對(duì)比結(jié)果

算例ABC本算法最優(yōu)解平均相對(duì)偏差/%An33k56756626610.15An33k67507427420An34k57907827780.51An37k69809499490Bn31k56806766720.60Bn34k57997887880Bn38k68148058050Bn39k55655535490.73Bn41k68578378290.97En22k43753753750En33k48448358350Pn23k85315295290

在表4中，ABC與本算法求解VRP的結(jié)果進(jìn)行了對(duì)比，我們選取了每種類型的部分算例。實(shí)驗(yàn)共計(jì)算了14個(gè)算例，通過(guò)ABC與本算法的最優(yōu)值對(duì)比發(fā)現(xiàn)除了在算例En22k4和算例Pn23k8中取得相同的最優(yōu)值，其他12個(gè)算例中，本算法比ABC的最優(yōu)值更好。對(duì)比中還發(fā)現(xiàn)，隨著求解問(wèn)題的規(guī)模增大，本算法的尋優(yōu)能力有了明顯提升。本算法的相對(duì)誤差率僅在1%以下。針對(duì)多目標(biāo)VRP的數(shù)學(xué)模型，應(yīng)該得出的是一個(gè)最優(yōu)解集。但是，因本文算例的特殊性，使得實(shí)驗(yàn)過(guò)程中車輛數(shù)量和車輛路徑同時(shí)達(dá)到了最優(yōu)，沒(méi)有表現(xiàn)出解的多樣性，所以表4中只是給出了對(duì)應(yīng)問(wèn)題的最優(yōu)解。

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

筆者對(duì)VRP和螢火蟲算法進(jìn)行研究，建立了以最小化車輛數(shù)量和車輛行駛距離為目標(biāo)的多目標(biāo)數(shù)學(xué)模型，提出一種結(jié)合變鄰域搜索算法的離散型螢火蟲算法。通過(guò)對(duì)不同規(guī)模的Solomon算例進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明，算法無(wú)論是在車輛數(shù)量還是行駛路程的求解質(zhì)量都取得了很好的效果。從實(shí)驗(yàn)分析和實(shí)驗(yàn)對(duì)比的結(jié)果來(lái)看，本算法具有下面幾項(xiàng)優(yōu)點(diǎn)：(1)求解問(wèn)題相同，所求得的問(wèn)題解的質(zhì)量較高。與其他算法相比，本文算法可以求得更少的配送車輛數(shù)；在求得車輛數(shù)相同的情況下，本算法求得的車輛行駛距離更短；(2)本文算法在解空間中的尋優(yōu)能力比較強(qiáng)，收斂速度也較快，可以在較短的時(shí)間內(nèi)收斂到問(wèn)題的最優(yōu)解或者滿意解，計(jì)算效率較高；(3)本算法求得的結(jié)果很穩(wěn)定，穩(wěn)健性較強(qiáng)。

今后的研究工作主要是一方面進(jìn)行更多的數(shù)值實(shí)驗(yàn)來(lái)優(yōu)化和驗(yàn)證本算法的性能，并對(duì)多目標(biāo)車輛路徑問(wèn)題做進(jìn)一步研究；另一方面研究本算法在其他領(lǐng)域的可行性，以期擴(kuò)大本算法的應(yīng)用范圍。

參考文獻(xiàn)：

[1]李雪竹.基于免疫螢火蟲算法的RFID倉(cāng)儲(chǔ)車輛動(dòng)態(tài)調(diào)度[J].計(jì)算機(jī)工程與應(yīng)用,2014(6):235-239.

[2]劉燁.物流系統(tǒng)中智能優(yōu)化技術(shù)的應(yīng)用研究[D].合肥：合肥工業(yè)大學(xué),2007.

[3]王柏根,汪勛,張子臻，等.遺傳算法在電力維護(hù)人員調(diào)度問(wèn)題中的應(yīng)用[J].現(xiàn)代計(jì)算機(jī)(專業(yè)版),2015(8):3-8.

[4]顧坤坤.不確定環(huán)境下物流配送有關(guān)問(wèn)題的研究[D].長(zhǎng)沙：中南大學(xué),2009.

[5]王剛.遺傳算法在VRP中的應(yīng)用與研究[D].重慶：重慶交通大學(xué),2011.

[6]賈楠,呂永波,付蓬勃，等.物流配送問(wèn)題中VRP的數(shù)學(xué)模型及其求解算法[J].物流技術(shù),2007,26(4):54-56.

[7]劉云忠,宣慧玉.車輛路徑問(wèn)題的模型及算法研究綜述[J].管理工程學(xué)報(bào),2005,19(1):124-130.

[8]符卓,陳斯衛(wèi).車輛路徑問(wèn)題的研究現(xiàn)狀與發(fā)展趨勢(shì)[C]//中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集下卷.2004:997-1002.

[9]崔雪麗,馬良,范炳全，等.車輛路徑問(wèn)題(VRP)的螞蟻搜索算法[J].系統(tǒng)工程學(xué)報(bào),2004,19(4):418-422.

[10]張麗萍,柴躍廷.車輛路徑問(wèn)題的改進(jìn)遺傳算法[J].系統(tǒng)工程理論與實(shí)踐,2002,22(8):79-84.

[11]崔雪麗,馬良,范炳全，等.車輛路徑問(wèn)題(VRP)的螞蟻搜索算法[J].系統(tǒng)工程學(xué)報(bào),2004,19(4):418-422.

[12]胡大偉，朱志強(qiáng)，胡勇.車輛路徑問(wèn)題的模擬退火算法[J].中國(guó)公路學(xué)報(bào),2006,19(4):123-126.

[13]李寧,鄒彤,孫德寶，等.車輛路徑問(wèn)題的粒子群算法研究[J].系統(tǒng)工程學(xué)報(bào),2004,19(6):596-600.

[14]郎茂祥,胡思繼.車輛路徑問(wèn)題的禁忌搜索算法研究[J].管理工程學(xué)報(bào),2004,18(1):81-84.

[15]Krishnand K N, Ghose D. Detection of multiple source locations using a glowworm metaphor with applications to collective robotics[C]// Proceedings of IEEE Swarm Intelligence Symposium. Pisatway. Pasadena Califomia: IEEE Press,2005：84-91.

[16]Krishnand K N,Ghose D. Glowworm swarm based optimization algorithm for multimodal functions with collective robotics applications[J]. Multiagent and Grid Systems, 2006, 2(3):209-222.

[17]周永權(quán),黃正新,劉洪霞，等.求解TSP問(wèn)題的離散型螢火蟲群優(yōu)化算法[J].電子學(xué)報(bào),2012,40(6):1164-1170.

[18]何文玲,倪郁東,汪婷婷，等.基于混合行為蟻群算法的車輛路徑問(wèn)題[J].合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2014(7):883-887.

[19]陳則輝,劉誠(chéng),呂品，等.不確定環(huán)境下應(yīng)急物資配送問(wèn)題研究[J].鐵道科學(xué)與工程學(xué)報(bào),2014(5):82-89.

[20]劉誠(chéng),陳治亞.含裝卸工調(diào)配的物流車輛配送路徑問(wèn)題的研究[J].鐵道科學(xué)與工程學(xué)報(bào),2006,3(4):79-83.

[21]陳昌敏,謝維成,范頌頌，等.自適應(yīng)和最大最小蟻群算法的物流車輛路徑優(yōu)化比較[J].西華大學(xué)學(xué)報(bào)(自然科學(xué)版),2011,30(3):5-8.

[22]歐陽(yáng)喆,周永權(quán).自適應(yīng)步長(zhǎng)螢火蟲優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用,2011,31(7):1804-1807.

[23]駱東松,李雄偉,趙小強(qiáng)，等.基于人工螢火蟲的模糊聚類算法研究[J].工業(yè)儀表與自動(dòng)化裝置,2013(2):3-6.

[24]黃正新.人工螢火蟲群優(yōu)化算法分析改進(jìn)及應(yīng)用研究[D].南寧：廣西民族大學(xué),2011.

[25]張軍麗.一種用Powell方法局部?jī)?yōu)化的人工螢火蟲算法[J].模式識(shí)別與人工智能,2011,24(5):680-684.

[26]黃正新,周永權(quán).自適應(yīng)步長(zhǎng)螢火蟲群多模態(tài)函數(shù)優(yōu)化算法[J].計(jì)算機(jī)科學(xué),2011,38(7):220-224.

[27]Krishnand K N,Ghose D. Glowworm swam optimisation: a new method for optimizing multi-modal functions[J]. Int J Computational Intelligence Studies, 2009, 1(1): 93-119.

[28]Dong Wenbo,Zhou Kang，F(xiàn)u Qinhong,et al. Adaptive Neighborhood Search’s DGSO Applied to Travelling Saleman Problem[J].Communications in Computer and Information Science,2015,562:125-137.

Multi-objective vehicle routing problem based on discrete glowworm swarm optimization algorithm

DONGWen-bo,ZHOUKang,LIUShuo,GAOQuan-sheng

(School of Mathematics and Computer Science,Wuhan Polytechnic University,Wuhan 430023,China)

Abstract：In this paper, the multi-objective mathematical model is established in order to minimize the number of vehicles and driving distance in vehicle routing problem, and a discrete glowworm swarm optimization algorithm(DGSO) combined with variable neighborhood search is proposed. The characteristic of DGSO algorithm is that individual generation and movement mode are redefined; variable neighborhood search technique is adopted to balance the global search ability and local development ability of the algorithm; random individuals take place of repeated individuals in order to maintain the diversity of the population in the search process; the elite strategy records the optimal solution in the iterative process. Simulation results for different scale Solomon cases show that DGSO algorithm both in the number of vehicles and driving distance have achieved good results.

Key words：discrete glowworm swarm optimization algorithm; vehicle routing problem; multi-objective optimization; variable neighborhood search; elite strategy

收稿日期:2015-4-8.

作者簡(jiǎn)介:董文波(1992-),男,碩士研究生,E-mail:1623572531@qq.com. 通信作者:周康(1965-),男,教授,E-mail:zhoukang_wh@163.com.

基金項(xiàng)目:國(guó)家自然科學(xué)基金項(xiàng)目資助課題(61179032);糧食公益性行業(yè)科研專項(xiàng)(201513004-3);武漢輕工大學(xué)研究生教育教學(xué)改革研究與實(shí)踐重點(diǎn)項(xiàng)目(YZ2015002).

文章編號(hào)：2095-7386(2016)02-0072-07

DOI:10.3969/j.issn.2095-7386.2016.02.013

中圖分類號(hào)：TP 391.9

文獻(xiàn)標(biāo)識(shí)碼：A