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

(武漢輕工大學 數學與計算機學院,湖北 武漢 430023)

?

基于多目標VRP的離散型螢火蟲算法研究

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

(武漢輕工大學 數學與計算機學院,湖北 武漢 430023)

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

關鍵詞：離散型螢火蟲算法；車輛路徑問題；多目標；變鄰域搜索；精英策略

1引言

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

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

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

2VRP和GSO

2.1VRP數學模型

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

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

用cij代表客戶i到客戶j的路程距離[20]。最后可對車輛路徑問題進行數學建模為：

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

2.2標準GSO及其數學模型

標準GSO包括以下5個步驟：

Step1：將函數目標值J(xi(t))用公式(1)轉化為相應的熒光素值li(t)；

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

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

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

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

(1)

(2)

(3)

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

(4)

其中

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

t—當前迭代次數；

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

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

rs—螢火蟲個體的最大鄰域半徑；

β—鄰域半徑更新率；

nt—螢火蟲個體鄰域集內包含的螢火蟲數目的閥值；

s為螢火蟲每次飛行的前進步長[17-18]。

3離散型螢火蟲算法的設計

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

3.1路徑編碼、解碼和構造初始螢火蟲群的設計說明

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

初始螢火蟲群采用N個顧客結點隨機排列的方式來產生。若螢火蟲群規(guī)模過大則計算量增加，影響算法收斂的時間；若螢火蟲群數量過少，則智能搜索算法的搜索性能下降，所以將問題規(guī)模和螢火蟲群規(guī)模相關聯，動態(tài)確定螢火蟲群規(guī)模。

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

兩個編碼的差異性是編碼對應的顧客點之間的差異性累積而成的，因此，如何刻畫兩個編碼對應的顧客點之間的差異性就是設計螢火蟲個體間距離的核心問題。由于兩個顧客點之間的實際差異就是這兩個顧客點之間的實際路程長度，因此，為了更好地刻畫并反映螢火蟲個體之間真實的位置距離，對兩個顧客點之間的實際差異選擇了兩個顧客點的弧距離，由此設計了新的螢火蟲距離。

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

(5)

其中dij(t)為個體i,j在第t次迭代每一維上的弧距離；M為權矩陣中每一行的最大值之和。所以δij(t)∈[0, 1]；因為權矩陣在數學形式上是對稱的，所以δij(t)也是對稱的，即δij(t)=δji(t)。

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

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

(6)

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

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

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

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

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

temp=x[rk]；

x[rk]=y[rk]；

x[y[rk]]=temp.

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

3.4引入變鄰域搜索技術

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

鄰域操作：

(1)交換：對隨機產生的兩個不同的數，交換這兩個數代表的編碼。

(2)反轉：對隨機產生的兩個不同的數，將這兩個隨機數之間的編碼反轉。

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

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

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

Step2：對于螢火蟲個體i，計算螢火蟲個體i路徑編碼代表路徑的目標函數值，根據式(1)將目標函數值轉化為螢火蟲熒光索值；

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

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

Step6：對新得到的螢火蟲個體編碼用變鄰域搜索算法進行局部優(yōu)化；

Step7：根據螢火蟲鄰居密度的大小和公式(4)動態(tài)調整螢火蟲個體i的鄰域半徑的大??；

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

4仿真實驗與分析

為了測試本算法的正確性和有效性，且使測試結果更具可比性和說服力，使用公開的標準測試算例(benchmark instances)對所提出的算法進行測試。數據來源于國際上公認的VRP數據庫(http://www.branchandcut.org/)。采用VC++6.0進行編程，實驗環(huán)境為：

4.1DGSO算法參數的選取

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

參數組1：ρ=0.5,γ=0.5,β=0.09,nt=6,

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

參數組2：ρ=0.3,γ=0.7,β=0.08,nt=10,

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

表1參數組對比實驗結果

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

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

4.2實驗對比與分析

4.2.1與現有算法的對比實驗

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

表2實例1的對比實驗結果

計算次序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可以看出，本算法對實例1求解10次，每次均得到較高質量的解，其求得的車輛行駛距離平均值為109.7 km，平均使用車輛數為3。車輛對應的配送路徑具體為:

路徑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)。

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

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

表3各種算法對實例1計算結果的對比

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

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

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

4.2.2Solomon算例對比實驗

本算法采用標準數據庫(http://www.branchandcut.org)中的VRP算例。并和人工蜂群算法(ABC)做了對比。其計算結果見表4。

表4Solomon算例的計算對比結果

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

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

5結束語

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

今后的研究工作主要是一方面進行更多的數值實驗來優(yōu)化和驗證本算法的性能，并對多目標車輛路徑問題做進一步研究；另一方面研究本算法在其他領域的可行性，以期擴大本算法的應用范圍。

參考文獻：

[1]李雪竹.基于免疫螢火蟲算法的RFID倉儲車輛動態(tài)調度[J].計算機工程與應用,2014(6):235-239.

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

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

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

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

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

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

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

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

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

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

[12]胡大偉，朱志強，胡勇.車輛路徑問題的模擬退火算法[J].中國公路學報,2006,19(4):123-126.

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

[14]郎茂祥,胡思繼.車輛路徑問題的禁忌搜索算法研究[J].管理工程學報,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]周永權,黃正新,劉洪霞，等.求解TSP問題的離散型螢火蟲群優(yōu)化算法[J].電子學報,2012,40(6):1164-1170.

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

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

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

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

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

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

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

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

[26]黃正新,周永權.自適應步長螢火蟲群多模態(tài)函數優(yōu)化算法[J].計算機科學,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，Fu 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.

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

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

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

DOI:10.3969/j.issn.2095-7386.2016.02.013

中圖分類號：TP 391.9

文獻標識碼：A