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

劉萬(wàn)峰，李 霞

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

【電子與信息科學(xué) / Electronics and Information Science】

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

劉萬(wàn)峰1，2，李 霞1，2

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

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

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

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

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

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

1 車輛路徑問(wèn)題及可行解編碼

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

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

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

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

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

圖1 FMNILS算法的偽代碼

Fig.1 Pseudo-code for FMNILS

2.1 構(gòu)造初始解

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

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

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

2.2 局部搜索算法

在求解VRP問(wèn)題的局部搜索算法中，采用多種鄰域結(jié)構(gòu)有利于算法找到更好解．因此，本研究在局部算法中采用了4種常見(jiàn)的局部搜索算子(插入、交換、2-opt和2-opt*)，分別對(duì)應(yīng)4種鄰域結(jié)構(gòu)．給定解S=(s1，s2，…，si，…，sM)和節(jié)點(diǎn)對(duì)si，sj(i≠j)，用si-1和sj-1表示si和sj在解S中的直接前驅(qū)節(jié)點(diǎn)，si+1和sj+1表示si和sj在解S中的直接后繼節(jié)點(diǎn)，則以上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é)點(diǎn)si和sj分屬不同配送路線的條件下進(jìn)行．

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

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

(2)

(3)

(4)

(5)

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

2.2.2 鄰域解的快速評(píng)估策略

(6)

(7)

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

(2-opt*) (8)

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

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

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

(insert) (9)

(exchange) (10)

(2-opt) (11)

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

(2-opt*) (12)

(insert) (13)

(exchange)(14)

(2-opt)(15)

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

對(duì)CVRP和CDVRP的鄰域解可通過(guò)計(jì)算適應(yīng)值的差異來(lái)實(shí)現(xiàn)其適應(yīng)值評(píng)估，其計(jì)算復(fù)雜度為O(1)．從式(8)至式(15)可見(jiàn)，各式的計(jì)算復(fù)雜度均為O(1)．因此，采用以上方法后，鄰域解適應(yīng)值評(píng)估的計(jì)算復(fù)雜度由O(N)降低為O(1)．

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

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

2.3 接受準(zhǔn)則

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

2.4 擾動(dòng)

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

圖4 3-opt擾動(dòng)示意圖Fig.4 Three-opt perturbation

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

3 實(shí)驗(yàn)仿真及分析

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

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

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

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

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

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

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

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

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

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

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

結(jié) 語(yǔ)

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

/ 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) 駱劍平，李 霞，陳泯融．基于改進(jìn)混合蛙跳算法的CVRP求解[J]. 電子與信息學(xué)報(bào)，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．

【中文責(zé)編：英 子；英文責(zé)編：雨 辰】

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

國(guó)家自然科學(xué)基金資助項(xiàng)目( 61171124)，深圳市基礎(chǔ)研究計(jì)劃資助項(xiàng)目(JC201105170613A)

劉萬(wàn)峰(1974—)，男(漢族)，廣東省興寧市人，深圳大學(xué)博士研究生．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

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