劉萬峰，李 霞

1)深圳大學信息工程學院，深圳 518060; 2)深圳市現(xiàn)代通信與信息處理重點實驗室，深圳 518060

【電子與信息科學 / Electronics and Information Science】

車輛路徑問題的快速多鄰域迭代局部搜索算法

劉萬峰1，2，李 霞1，2

1)深圳大學信息工程學院，深圳 518060; 2)深圳市現(xiàn)代通信與信息處理重點實驗室，深圳 518060

對于容量約束的車輛路徑問題 (capacitated vehicle routing problem，CVRP)以及容量和最大行駛距離約束的車輛問題(capacitated and distance constrained vehicle routing problem，CDVRP) ，鄰域解的評估包含了適應值計算及合法性評估．設計一種可變長編碼的可行解表示，提出用于CVRP/CDVRP問題的鄰域解合法性快速評估策略．該策略針對交換、插入、2-opt和2-opt*四種常用的局部搜索算子，通過引入前載重、后載重、前向距離和后向距離的概念，實現(xiàn)了鄰域解合法性的快速評估．將改進后的局部搜索算子與迭代局部搜索(iterated local search, ILS)算法相結(jié)合，提出用于車輛路徑問題的快速多鄰域迭代局部搜索(fast multi-neighborhood ILS，F(xiàn)MNILS)算法．該快速評估策略將評估一個鄰域解的時間復雜度由O(N)降至O(1)，算法仿真結(jié)果表明，F(xiàn)MNILS算法運算能力的提高大致與配送路線所服務的客戶數(shù)成正比；對客戶數(shù)介于200～500的容量/最大距離約束VRP問題，該算法能在短時間內(nèi)獲得較滿意解，平均求解精度1.2%以內(nèi)，平均耗時約96s，僅為對比算法的6%或更少．

人工智能；啟發(fā)式算法；車輛路徑問題；多鄰域；迭代局部搜索；可變長編碼

1959年，Laporte等[1]提出車輛路徑問題(vehicle routing problem，VRP)．由于其重要的實際意義和難于求解，VRP問題一直是運籌學與組合優(yōu)化領域的研究熱點．VRP的研究目標是對給定的客戶設計適當?shù)呐渌吐肪€，在滿足車輛容量、最大行駛距離和時間窗等約束條件下，實現(xiàn)使用車輛數(shù)最少、運輸成本最小等優(yōu)化目標． VRP是NP-完全(NP-complete)問題，即使是最簡單的容量約束車輛路徑問題(capacitated VRP，CVRP)，現(xiàn)有文獻也只給出了客戶數(shù)約為100時的CVRP問題的精確求解[2]．因此，設計一個能在可接受時間內(nèi)獲得較好解的啟發(fā)式算法是該問題的主要研究方向之一．

近年來，許多學者對啟發(fā)式算法求解CVRP問題進行了研究，并提出很多優(yōu)秀的算法．迭代局部搜索(iterated local search, ILS)算法結(jié)構(gòu)簡單且有效；可變鄰域方法(variable neighborhood)易于發(fā)現(xiàn)當前解鄰域范圍內(nèi)的更好解，這兩種方法通常結(jié)合在一起，用于CVRP問題的求解．Chen等[3]提出一種基于多種局部優(yōu)化算子的迭代變鄰域下降算法(iterated variable neighborhood descent，IVND)；Subramanian等[4-5]將集合劃分(set partitioning，SP)、RVND(variable neighborhood descent with random neighborhood ordering)和ILS相結(jié)合設計了ILS-RVND-SP算法．Li等[6]在RTR(record-to-record)算法中采用了可變長度的鄰域列表，用于指導算法的搜索方向．相比單一算法，混合算法往往能獲得更好的結(jié)果．駱劍平等[7]將冪律極值動力學優(yōu)化(power law extremal optimization，τ-EO)融合于混合蛙跳算法(shuffled frog leaping algorithm，SFLA)，針對CVRP 對τ-EO 過程進行重新設計，提出新穎的組元適應度計算方法并根據(jù)冪律概率分布來挑選需要變異的組元．Wink等[8]提出了一種結(jié)合了CVRP特定知識和啟發(fā)式算法的混合遺傳算法，并在算法的參數(shù)優(yōu)化中也采用了遺傳算法．為減少VRP問題求解算法的計算復雜度，Zachariadis等[9]將當前解和其所有鄰域解的差異保存在SMD(static move descriptor)的數(shù)據(jù)結(jié)構(gòu)中，從而避免了適應值差異的重復計算并提高了算法的運行效率．隨著計算機硬件的快速發(fā)展，近年涌現(xiàn)了許多求解CVRP問題的并行算法．Chrisgro?r等[10]提出一種結(jié)合啟發(fā)式局部搜索和整數(shù)規(guī)劃的并行算法；Jin等[11]提出一種多鄰域的并行禁忌搜索算法．

以上算法在求解VRP問題時均需要反復對解個體進行評估，對解個體的評估包括合法性評估和適應值計算，該評估占用了算法的大部分運行時間．對于規(guī)模為N的VRP問題，解個體評估的計算復雜度為O(N)，隨著問題規(guī)模的增加，計算復雜度線性增加．在一些組合優(yōu)化問題中，局部搜索算法對鄰域解的評估只需要計算其與當前解的差異，從而極大地減少了適應值的計算復雜度[12]．例如，在TSP問題中，計算鄰域解和當前解的適應值差異的復雜度為O(1)，而解的適應值的計算復雜度為O(N)[12]． 由于VRP問題中常存在車輛容量、最大行駛距離等約束條件，采用局部搜索算法獲得的鄰域解多出現(xiàn)非法解，僅通過計算鄰域解的適應值差異并不能實現(xiàn)對鄰域解的正確評估．本研究通過引入前載重、后載重、前向距離和后向距離的概念，將當前解與車輛容量、最大行駛距離約束相關的信息分解到各客戶節(jié)點，依據(jù)客戶節(jié)點的約束信息對多種常用的局部搜索算子實現(xiàn)鄰域解合法性的快速評估，將鄰域解評估(包括合法性評估及適應值計算)的計算復雜度由O(N)減小為O(1)．基于此，本研究提出一種快速多鄰域迭代局部搜索算法(fastmulti-neighborhoodILS，F(xiàn)MNILS)．該算法中設計了一種新穎的可變長編碼的可行解表示，使算法在優(yōu)化過程中可同時實現(xiàn)對車輛數(shù)和運輸成本的優(yōu)化.為克服單一鄰域?qū)?yōu)能力的不足，使用4種不同的鄰域結(jié)構(gòu)，設計了和局部搜索算法相適應的擾動策略，使算法易于跳出局部最優(yōu)．通過與相關文獻算法比較，該算法在CVRP和CDVRP基準測試問題上能在很短的時間內(nèi)找到較好解．

1 車輛路徑問題及可行解編碼

VRP的研究目標是對給定的客戶設計適當?shù)呐渌吐肪€，在滿足車輛容量、最大行駛距離、時間窗等約束條件下，實現(xiàn)使用車輛數(shù)最少、運輸成本最小(本研究針對的VRP問題的運輸成本以車輛的行駛距離來表示)等優(yōu)化目標．VRP問題可描述為：給定一個完全圖G=(V，E)，其中，V={v0,v1, …,vi, …,vN}是節(jié)點集合，N為客戶總數(shù)，v0表示倉庫，vi(i=1, 2, …,N) 是第i個客戶節(jié)點，其配送需求為di；E={vi，vj|vi，vj∈V)是連接各節(jié)點的弧的集合，從節(jié)點vi到節(jié)點vj的運輸成本cij>0． 配送車輛從倉庫出發(fā)并最終返回倉庫，每個客戶須由且只能由一輛配送車進行服務．不失一般性，在CVRP和CDVRP問題中，假設每輛車所能運載的最大載重相等，均用Q表示，即車輛容量約束；此外，每條配送路線的最大行駛距離也相同，均用D表示，即最大行駛距離約束．

在本研究中，VRP問題的解采用可變長編碼方式(variablelengthcoding，VLC)．對于有N個客戶的VRP問題，其可行解可表示為

S=(s1,s2,…,si,…,sM),

(1)

1)配送路線R(1)：0，1，3，6，8，0；

2)配送路線R(2)：0，4，5，7，2，0；

3)配送路線R(3)：0，0.

由于路線3未對任何客戶服務，是多余的配送路線．在本研究提出的算法中，可行解在優(yōu)化過程中若出現(xiàn)連續(xù)0的情況，則用單個0進行替代，從而改變了可行解編碼長度并減少了車輛數(shù)．由于采用了可變長的編碼方式，本算法在優(yōu)化過程中可同時實現(xiàn)對車輛數(shù)和運輸成本的優(yōu)化．

2 快速多鄰域迭代局部搜索算法

自從1986年Baum[13]提出迭代局部搜索算法(iteratedlocalsearch，ILS)以來，該算法已廣泛用于求解組合優(yōu)化問題．迭代局部搜索的主要思想是：從某個隨機起始點出發(fā)，局部搜索和變異交替進行，在此過程中只保留最好的解．迭代局部搜索結(jié)構(gòu)簡單，易于找到問題的較好解，亦為本算法所用．圖1給出FMNILS算法的偽代碼．

圖1 FMNILS算法的偽代碼

Fig.1 Pseudo-code for FMNILS

2.1 構(gòu)造初始解

在FMNILS算法中采用隨機生成的方法來獲得CVRP問題的初始解．假設CVRP問題中客戶節(jié)點的集合為{1，2，…，N}，則初始解的生成可描述為

1)生成隨機序列X=(x1，x2，…，xi，…，xN)，其中xi=1，2，…，N，且xi≠xj(i≠j)，并在序列X頭部插入倉庫節(jié)點0．

2)從節(jié)點x1開始向后尋找這樣的節(jié)點xk，若滿足配送路線(0，x1，x2,…，xk，0)為合法解(即滿足所有約束條件)，配送路線(0，x1，x2,…，xk+1，0)為非法解，則在xk和xk+1之間插入倉庫節(jié)點0，構(gòu)造新的合法配送路線．再從xk+1開始按同樣方法繼續(xù)構(gòu)造新的配送路線，直至所有分段路線均滿足約束條件，并在末端插入倉庫節(jié)點0．由此得到的新序列S即為VRP問題的初始解．

2.2 局部搜索算法

在求解VRP問題的局部搜索算法中，采用多種鄰域結(jié)構(gòu)有利于算法找到更好解．因此，本研究在局部算法中采用了4種常見的局部搜索算子(插入、交換、2-opt和2-opt*)，分別對應4種鄰域結(jié)構(gòu)．給定解S=(s1，s2，…，si，…，sM)和節(jié)點對si，sj(i≠j)，用si-1和sj-1表示si和sj在解S中的直接前驅(qū)節(jié)點，si+1和sj+1表示si和sj在解S中的直接后繼節(jié)點，則以上4種局部搜索算子可描述為

1)插入(insert)：刪除弧(si-1，si)、(si，si+1)和(sj，sj+1)，連接弧(si-1，si+1)、(sj，si)和(si，sj+1)．

2)交換(exchange)：刪除弧(si-1，si)、(si，si+1)、(sj-1，sj)和(sj，sj+1)，連接弧(si-1，sj)、(sj，si+1)、(sj-1，si)和(si，sj+1)．

3)2-opt：刪除弧(si，si+1)和(sj，sj+1)，添加弧(sj，si)和(si+1，sj+1)．

4)2-opt*：刪除弧(si，si+1)和(sj，sj+1)，添加弧(si，sj+1)和(sj，si+1)，2-opt*只能在節(jié)點si和sj分屬不同配送路線的條件下進行．

在局部搜索算法中鄰域解的評估需要反復進行，因此，減小鄰域解評估的計算復雜度能極大提高算法的運行效率．由于鄰域解和當前解的差異較小，可通過計算兩者的差異獲得鄰域解的適應值及合法性評估．為此，本研究將當前解中與車輛容量、最大行駛距離等約束條件相關的信息分解到各客戶節(jié)點，依據(jù)客戶節(jié)點的約束信息在4種常用的局部搜索算子(插入、交換、2-opt和2-opt*)中尋求鄰域解合法性的快速評估方法．

2.2.1 客戶節(jié)點的約束信息

(2)

(3)

(4)

(5)

由此可知，客戶節(jié)點約束信息的計算是一個累加過程，計算1條配送路線所有客戶節(jié)點約束信息的計算復雜度為O(l)，這里l為該配送路線服務的客戶數(shù)，每個客戶節(jié)點約束信息的計算復雜度為O(1)．

2.2.2 鄰域解的快速評估策略

(6)

(7)

由此可得，解S′是否滿足容量約束的判斷條件為

(2-opt*) (8)

其中，Q為車輛容量約束．

圖2 2-opt*局部算子示意圖Fig.2 Two-opt* local operator

類似可推導出其他3種局部算子所得鄰域解是否滿足容量約束的條件為

(insert) (9)

(exchange) (10)

(2-opt) (11)

同樣可推導出4種局部算子所得近鄰解是否滿足最大行駛距離的判定條件為

(2-opt*) (12)

(insert) (13)

(exchange)(14)

(2-opt)(15)

在本算法執(zhí)行過程中，只對合法解進行局部操作．合法解中的所有配送路線都滿足容量約束和最大行駛距離約束．對于同一路線內(nèi)的2個客戶進行插入、交換和2-opt操作，并不改變配送路線內(nèi)所服務的客戶，改變的只是服務順序.因此，該路線的配送貨物總重量不發(fā)生改變，自然滿足容量約束，無需進行容量約束判斷；對于最大行駛距離約束，該路線的行駛距離變化和適應值的變化一致，在本節(jié)所述的局部搜索算法中只接受適應值得到改善的鄰域解，即被接受的鄰域解在該路線上的行駛距離較當前解更短，自然就滿足最大行駛距離約束．而不被接受的鄰域解是否滿足最大行駛距離約束并不重要，所以也可以不進行最大行駛距離約束判斷.

對CVRP和CDVRP的鄰域解可通過計算適應值的差異來實現(xiàn)其適應值評估，其計算復雜度為O(1)．從式(8)至式(15)可見，各式的計算復雜度均為O(1)．因此，采用以上方法后，鄰域解適應值評估的計算復雜度由O(N)降低為O(1)．

圖3 4-opt局部算子示意圖Fig.3 Four-opt local operator

客戶節(jié)點約束信息的引入使得路徑的配送需求和行駛距離可以快速獲得，該信息可用于多種不同局部搜索算法所獲鄰域解的快速評估．除了本研究采用的4種局部搜索算子，客戶節(jié)點的約束信息也可用于r-opt所獲鄰域解的快速地評估．例如對于圖3的4-opt操作，對于鄰域解中的新路線1′是否滿足容量約束，只需要計算路徑(0，1)、(7，8，9)和(5，0)的配送需求之和是否小于配送車輛的最大載重．路徑(0，1)和(5，0)的配送需求分別為節(jié)點2的前載重和節(jié)點4的后載重，路徑(7，8，9)的配送需求可以由節(jié)點10的前載重減去節(jié)點7的前載重獲得．同樣，可用相同的方法判斷配送路線2′是否滿足容量約束．當r取不同值時，也可以設計相應的合法性快速評估方法．對于最大行駛距離的約束，也可采用類似的方法．目前求解TSP問題的算法中許多是基于邊交換(r-opt)操作的，由于鄰域解合法性評估占用了大量的運算時間，使這些算法用于CVRP/CDVRP受到限制．因此，客戶節(jié)點約束信息的引入使這些算法可方便地用于求解CVRP/CDVRP問題．

2.3 接受準則

在基本的ILS算法中采用最優(yōu)接受準則，即只接受比當前解更好的解．此類接受準則容易使算法陷入局部最優(yōu)，因此在求解CVRP問題的算法中常采用不同的接受準則．例如，IVND算法[3]采用類似模擬退火的接受準則；RTR算法[6]只接受對當前解的改變小于某一偏差的局部變換；FMNILS算法只接受適應值優(yōu)于αf(S)的解，其中，α(α≥1)為接受因子，f(S)為當前解的適應值．FMNILS算法采用的接受準則，使當前解既有較大的機會跳出局部最優(yōu)，又保證算法可集中在當前最優(yōu)解附近區(qū)域進行搜索．

2.4 擾動

對VRP問題，由于約束條件的存在，設計相應擾動算法時需考慮所獲解的合法性．通常是在擾動算法中加入約束條件，以保證所獲解的合法性，或者設計相應的算法對擾動后的解進行合法化，以上方法都會增加算法設計的復雜度．由于FMNILS算法采用了可變長編碼，車輛數(shù)在優(yōu)化過程中可增可減．因此，在FMNILS算法中對擾動所獲的非法解，只需在適當位置加入倉庫節(jié)點(增加車輛數(shù))就可實現(xiàn)解的合法化．

圖4 3-opt擾動示意圖Fig.4 Three-opt perturbation

在迭代局部搜索算法中采用的擾動方法對算法的求解精度和求解效率有較大影響．擾動范圍不能太大，且需避免出現(xiàn)對當前解進行擾動、局部搜索后獲得的解和當前解相同的情況[14]．本研究采用3-opt變換方法對當前解進行擾動，該方法對當前解的改變較小，且對擾動后的解進行插入、交換、2-opt和2-opt*這4種局部操作不易使其回到當前解．擾動方法為：首先隨機選擇3條邊，然后進行如圖4的3-opt變換．若變換后所得解不滿足約束條件，則對不滿足約束條件的配送路線在變換處增加1個倉庫節(jié)點，使約束條件得以滿足．

3 實驗仿真及分析

本研究的實驗平臺為IntelE7500 2.93GHzCPU，操作系統(tǒng)為Windows7，編程語言采用C++．CVRP和CDVRP的測試問題采用Christofides等[15]提出的14個基準測試問題(記為C1～C14)和Golden等[16]提出的20個較大規(guī)模的測試問題(記為P1～P20)．在這2個測試集中，C1～C5、C11～C12和P8～P20為CVRP問題，其他的則是CDVRP問題．

為評估快速評估策略對局部搜索算法運行效率的影響，本研究使用FMNILS算法和未采用快速評估策略的多鄰域迭代局部搜索算法(multi-neighborhoodILS，MNILS)求解不同規(guī)模的CVRP/CDVRP問題．實驗中兩個算法采用相同的參數(shù)和停止準則，其中設α=1.02； 若連續(xù)500代未能找到更好解，則算法停止．兩個算法的差別僅在適應值的計算方法上，因此，在隨機數(shù)發(fā)生器采用相同初始值的條件下，可保證兩個算法能得到相同的解，所不同的是運行時間差異．實驗結(jié)果如圖5．

圖5 FMNILS算法運行速度提高度與配送路線平均服務客戶數(shù)的關系圖Fig.5 Relationship between the average number of customers in a route and the improvement level of running speed by FMNILS

由圖5可見，F(xiàn)MNILS在運行速度上的提高程度(以MNILS算法的平均運行時間和FMNILS算法平均運行時間的比值來衡量)，與配送路線的平均服務客戶數(shù)大致服從線性關系．這是因為，MNILS算法中只對鄰域解改變的路線進行合法性評估，其算法復雜度為O(l)，所以MNILS算法的運行時間和l相關，而l可近似等效為配送路線的平均服務客戶數(shù)(即N/K)． 從圖5可見，對于CDVRP問題，F(xiàn)MNILS算法用時更少，這是因為除了容量約束判斷，在最大行駛距離約束判斷上，F(xiàn)MNILS算法也節(jié)省了運算時間．

FMNILS算法整體性能的評估實驗也是在Christofides和Golden測試集上進行的．實驗設α=1.02； 若連續(xù)1 000代未能找到更好解，則算法停止．表1和表2給出FMNILS算法整體性能評估實驗結(jié)果．

表1 Christofides測試集求解結(jié)果

1)文獻[3]未給出平均偏差和單個實例平均運行時間的數(shù)據(jù)

在表1和表2中，已知最優(yōu)解采用文獻[3]的結(jié)果，最新結(jié)果可參考文獻[4]；最小偏差和平均偏差分別為10次運行中的最好結(jié)果、平均結(jié)果與目前已知最優(yōu)解之間的差異；運行時間為10次運行的平均時間．表1和表2還給出了另外2種基于ILS的算法(IVND[3]算法和ILS-RVND-SP[4]算法)求解CVRP問題的結(jié)果．IVND算法的實驗平臺是Pentium IV 2.93 GHz；ILS-RVND-SP算法的實驗平臺為Intel CoreTM i7 2.93 GHz.圖6給出了4種不同算法在求解精度和時間上的比較(其中，F(xiàn)IVND是結(jié)合了本研究提出的快速評估策略的IVND算法)，圖6(a)給出的是各算法求解單個問題的平均運行時間，為便于比較，圖中給出各算法運行時間與FMNILS算法運行時間的比值；圖6(b)給出各算法10次求解的最好結(jié)果與目前已知最優(yōu)解的差異．從圖6可見，F(xiàn)MNILS算法使用了遠少于IVND算法的運行時間，但獲得和IVND算法求解精度大致相當?shù)慕Y(jié)果(在Christofides測試集上FMNILS略差于IVND，在Golden測試集上FMNILS略優(yōu)于IVND)；ILS-RVND-SP算法在ILS-RVND的基礎上結(jié)合了集合劃分的方法，其在兩個測試集上的求解精度都優(yōu)于FMNILS，然而其付出了更多的運算時間．從圖6可知，結(jié)合了快速評估策略的FIVND算法在不影響求解精度的情況下，極大地減少了算法的運行時間．這說明快速評估策略可用于鄰域解的評估，并不影響算法求解精度，因而它可以與基于鄰域搜索的CVRP問題求解算法相結(jié)合，以期在獲得相同精度解的情況下減少算法的運行時間．

表2 Golden測試集求解結(jié)果

1)文獻[3]未給出平均偏差和單個實例平均運行時間的數(shù)據(jù)

圖6 FMNILS、IVND、FIVND和ILS-RVND-SP算法時間和求解精度比較Fig.6 Comparisons of rumming time and average deviation among FMNILS, FIVND, IVND and ILS-RVND-SP

結(jié) 語

VRP問題屬于帶有約束條件的組合優(yōu)化問題，因而在局部搜索算法中對鄰域解的評估不能直接通過當前解和鄰域解的差異來實現(xiàn)．為此，本研究引入前載重、后載重、前向距離和后向距離的概念，提出一種鄰域解合法性的快速評估策略．該策略實質(zhì)上是將當前解與約束條件相關的信息分解到各客戶節(jié)點，使鄰域解的合法性評估可通過客戶節(jié)點的約束信息來快速獲得，避免了算法后續(xù)的局部搜索過程中對相關信息進行反復計算，大幅提高了局部搜索算法的運行效率．此外，本研究將采用了快速評估策略的局部搜索算子和迭代局部搜索算法相結(jié)合，設計應用于車輛路徑問題的快速迭代局部搜索算法．實驗仿真結(jié)果表明，該算法能夠在較短時間內(nèi)求得較大規(guī)模CVRP問題的滿意解．

/ References：

[1] Laporte G，Toth P，Vigo D．Vehicle routing：historical perspective and recent contributions[J]．EURO Journal on Transportation and Logistics，2013，2(1/2)：1-4．

[2] Baldacci R，Mingozzi A，Roberti R．Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints[J]．European Journal of Operational Research，2012，218(1)：1-6．

[3] Chen Ping,Huang Houkuan,Dong Xieye.Iterated variable neighborhood descent algorithm for the capacitated vehicle routing problem[J]．Expert Systems with Applications, 2010，37(2)：1620-1627．

[4] Subramanian A，Uchoa E，Satoru Ochi L．A hybrid algorithm for a class of vehicle routing problems[J]．Computers & Operations Research，2013，40(10)：2519-2531．

[5] Subramanian A．Heuristic, exact and hybrid approaches for vehicle routing problems[D]．Niterói(Brazil)：Universidade Federal Fluminense，2012．

[6] Li Feiyue，Golden B，Wasil E．Very large-scale vehicle routing: new test problems, algorithms, and results[J]．Computers & Operations Research，2005，32(5)：1165-1179．

[7] Luo Jianping，Li Xia, Chen Minrong. Improved shuffled frog leaping algorithm for solving CVRP[J]．Journal of Electronics & Information Technology，2011，33(2)：429-434．(in Chinese) 駱劍平，李 霞，陳泯融．基于改進混合蛙跳算法的CVRP求解[J]. 電子與信息學報，2011，33(2)：429-434．

[8] Wink S，Back T，Emmerich M．A meta-genetic algorithm for solving the capacitated vehicle routing problem[C]// IEEE Congress on Evolutionary Computation(CEC). Brisbane(Australia)： IEEE Press，2012：1-8．

[9] Zachariadis E E，Kiranoudis C T．A strategy for reducing the computational complexity of local search-based methods for the vehicle routing problem[J]．Computers & Operations Research, 2010, 37(12)：2089-2105．

[10] ChrisGro?r C，Golden B，Wasil E．A parallel algorithm for the vehicle routing problem[J]．INFORMS Journal on Computing，2011，23(2)：315-330．

[11] Jin J，Crainic T G，L?kketangen A．A parallel multi-neighborhood cooperative tabu search for capacitated vehicle routing problems[J]．European Journal of Operational Research，2012，222(3)：441-451．

[12] Ishibuchi H，Yoshida T，Murata T．Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling[J]．IEEE Transactions on Evolutionary Computation，2003，7(2)：204-223．

[13] Baum E B．Towards practical ‘neural’ computation for combinatorial optimization problems [C]// AIP Conference Proceedings 151 on Neural Networks for Computing．Snowbird Utah(USA)：AIP Publishing LLC，1986：53-58．

[14] Nguyen H D，Yoshihara I，Yamamori K，et al．Implementation of an effective hybrid GA for large-scale traveling salesman problems[J]．IEEE Transactions on Systems，Man，and Cybernetics，Part B：Cybernetics，2007，37(1)：92-99．

[15] Christofides N，Eilon S．An algorithm for the vehicle-dispatching problem[J]．Operational Research Society，1969，20(3)：309-318．

[16] Crainic T G，Laporte G．Fleet management and logistics[M]．Berlin：Springer，1998．

【中文責編：英 子；英文責編：雨 辰】

A fast multi-neighborhood iterated local search algorithm for vehicle routing problem

Liu Wanfeng1, 2and Li Xia1, 2?

1)College of Information Engineering, Shenzhen University, Shenzhen 518060, P.R.China 2) Shenzhen Key Lab of Communication and Information Processing, Shenzhen 518060, P.R.China

For capacitated vehicle routing problems without/with maximum traveling distance constraint (CVRP/CDVRP), the evaluation of neighborhood solutions involves fitness calculation and feasibility assessment. This paper proposes a fast feasibility assessment strategy in which variable length coding is used to represent feasible solutions of vehicle routing problem. We introduce the concepts of pre-load, post-load, pre-distance and post-distance to obtain fast feasibility assessments for neighborhood solutions achieved by four widely used local search operations (insert, exchange, 2-opt, and 2-opt*). By combining the improved local search operations and iterated local search (ILS), we propose a fast multi-neighborhood iterated local search (FMNILS) for CVRP. The feasibility assessment strategy can reduce computational complexity of the neighborhood solution assessment fromO(N)toO(1).Experimentalresultsshowthattheimprovementinspeedisapproximatelylinearlyproportionaltotheaveragecustomernumberinaroute.ForCVRP/CDVRPproblemswith200—500customers,thealgorithmcangivesatisfactorysolutionswithanaveragedeviationoflessthan1.2%.Theaveragerunningtimeis96seconds,whichis6%ofthetimerequiredforthecounterpartalgorithms,orevenless.

artificial intelligence; heuristic algorithms; vehicle routing problem; multi-neighborhood; iterated local search; variable length coding

：Liu Wanfeng，Li Xia．A fast multi-neighborhood iterated local search algorithm for vehicle routing problem[J]. Journal of Shenzhen University Science and Engineering, 2015, 32(2): 196-204.(in Chinese)

TP

A

10.3724/SP.J.1249.2015.02196

國家自然科學基金資助項目( 61171124)，深圳市基礎研究計劃資助項目(JC201105170613A)

劉萬峰(1974—)，男(漢族)，廣東省興寧市人，深圳大學博士研究生．E-mail：liuwf@163.com

Received：2014-06-11；Revised：2015-02-06；Accepted：2015-02-28

Foundation：National Natural Science Foundation of China (61171124); Shenzhen Key Project for Foundation Research (JC201105170613A)

? Corresponding author：Professor Li Xia. E-mail: lixia@szu.edu.cn

引 文：劉萬峰，李 霞．車輛路徑問題的快速多鄰域迭代局部搜索算法[J]. 深圳大學學報理工版，2015，32(2)：196-204.