面向動態(tài)車輛路徑的改進(jìn)變鄰域搜索算法

戈 軍，周蓮英

1.宿遷學(xué)院 計算機(jī)科學(xué)系，江蘇 宿遷 223800

2.江蘇大學(xué) 計算機(jī)科學(xué)與通信工程學(xué)院，江蘇 鎮(zhèn)江 212013

面向動態(tài)車輛路徑的改進(jìn)變鄰域搜索算法

戈 軍1，周蓮英2

1.宿遷學(xué)院 計算機(jī)科學(xué)系，江蘇 宿遷 223800

2.江蘇大學(xué) 計算機(jī)科學(xué)與通信工程學(xué)院，江蘇 鎮(zhèn)江 212013

1 引言

近年來，隨著生產(chǎn)、生活的實時通信需要，動態(tài)車輛路徑問題（DVRP）已成為當(dāng)前研究熱點。由于DVRP是一個NP難題，且DVRP的絕大多數(shù)信息動態(tài)且不可預(yù)測，還可能出現(xiàn)新信息或現(xiàn)有信息發(fā)生變化等情況，因此，在采取分配及新請求調(diào)度決定時，必須綜合考慮許多不同因素約束。變鄰域搜索（VNS）作為一種有效手段可解決DVRP動態(tài)問題及路徑規(guī)劃優(yōu)化問題。文獻(xiàn)[1]最初提出VNS用以求解組合和全局優(yōu)化問題。其中抖動和局部優(yōu)化是VNS的最核心內(nèi)容。

目前國內(nèi)外學(xué)者主要關(guān)注于不同調(diào)度模型構(gòu)建和簡單高效啟發(fā)式算法設(shè)計。文獻(xiàn)[2]研究了基于混合兩階段搜索算法，第一階段采用演化策略使車輛數(shù)最小，第二階段利用禁忌搜索法使總距離最小。文獻(xiàn)[3]研究了帶時間窗的DVRP，并分析了次優(yōu)解模型算法。文獻(xiàn)[4]設(shè)計出求解帶時間窗多車場車輛路徑問題（MDVRPTW）的VNS算法，其采用兩種類型鄰域結(jié)構(gòu)實現(xiàn)當(dāng)前解的抖動：交換和交叉，局部搜索采用約束型3-opt算子，并利用TA（閾值接受法）思想接收部分非優(yōu)解，從而避免算法陷入局部最優(yōu)。文獻(xiàn)[5]引入RVNS求解基本VRP問題。文獻(xiàn)[6]給出了周期性VRP問題的VNS算法，采用初始解結(jié)構(gòu)的節(jié)約里程法，設(shè)計出移動和交叉鄰域，局部搜索策略使用3-opt算子。文獻(xiàn)[7]利用VNS算法求解開環(huán)VRP問題。

綜上，雖然國內(nèi)外在DVRP問題研究上取得了一定進(jìn)展，但目前DVRP的處理質(zhì)量和效率還遠(yuǎn)無法滿足實際需要。許多問題還需要深入研究。本文提出一種求解DVRP問題的改進(jìn)型變鄰域搜索算法（IVNSA），將局部搜索算子、后優(yōu)化過程和模擬退火算法思想融合VNS算法框架中。并與其他算法進(jìn)行比較，結(jié)果表明IVNSA可獲得較為理想的求解結(jié)果。

2 DVRP問題的數(shù)學(xué)描述

變量定義如下：

帶時間窗動態(tài)車輛路徑問題可轉(zhuǎn)化為混合整數(shù)線性規(guī)劃問題。目標(biāo)是最小化總成本，其目標(biāo)函數(shù)為：

問題約束包括車輛約束、需求約束、路徑約束和其他約束等。

式（3）為節(jié)點到車輛的分配約束：確保各客戶只有一次車輛服務(wù)，且車輛不能返回車場。

式（4）表示車輛與車場間的關(guān)系約束：確保從車場離開的車輛數(shù)不超過車輛配送中心的車輛最大數(shù)K。

式（5）為車輛與路線間的關(guān)系約束：確保同一路線上節(jié)點都由同一車輛交付。

式（6）表示節(jié)點到車輛間的分配約束：表明每一節(jié)點必須由單一車輛提供服務(wù)。

式（7）為容量約束：表明車輛交付的整體負(fù)載不應(yīng)超過其容量。

式（10）表示其他約束。

3 改進(jìn)變鄰域搜索算法

VNS基本思想：首先在搜索過程中通過系統(tǒng)改變當(dāng)前解的鄰域結(jié)構(gòu)集以拓展搜索范圍，接著采用局部搜索算法求解局部最優(yōu)解，然后基于此局部最優(yōu)解重復(fù)上述過程，經(jīng)過多次迭代后最終實現(xiàn)收斂目的。圖1給出IVNS算法流程。

圖1 IVNS算法流程圖

3.1 初始解

IVNS算法利用變鄰域搜索算法生成一個或多個初始可行解；分簇算法主要完成客戶分配和路徑規(guī)劃。為了獲得初始解，各客戶需指派一個隨機(jī)組合，利用文獻(xiàn)[8]的節(jié)約算法構(gòu)建每日車輛行駛路徑。當(dāng)不存在可合并兩條路徑時，終止算法。因此，路徑數(shù)可能超過可用車輛數(shù)。這時需確定一條最少客戶路徑，并將該路徑上的客戶遷移至其他路徑。需要注意的是，這可能導(dǎo)致無法再滿足路徑持續(xù)時間或容量約束，從而導(dǎo)致初始解不可行。因此VNS需要整合相關(guān)技術(shù)以獲得可行解?？赏ㄟ^如下算法求得初始解，這樣基本上可以滿足后續(xù)需要。

3.2 抖動過程

抖動過程是變鄰域搜索算法設(shè)計關(guān)鍵。擴(kuò)展當(dāng)前解搜索空間是抖動過程的主要目的，減少算法陷入局部最優(yōu)解概率，從而使算法求得較好解。抖動過程的鄰域結(jié)構(gòu)集是VNS設(shè)計核心。而所面臨的主要挑戰(zhàn)是如何準(zhǔn)確找出避免陷入局部最優(yōu)可能性與有效性間的平衡點。抖動過程首先從當(dāng)前解 x的鄰域結(jié)構(gòu)集中選取一個鄰域結(jié)構(gòu)Nk，然后根據(jù)Nk對x做出相應(yīng)改變從而生成一個新解x*。

抖動過程采用兩種鄰域結(jié)構(gòu)：插入和交換。插入是將某段連續(xù)節(jié)點從當(dāng)前路徑遷移至另一條路徑；交換是從兩條不同路徑中分別選取一段連續(xù)節(jié)點，并將兩者位置互換，如圖2所示。各鄰域的插入算子以概率 pinsert進(jìn)一步加大兩條路徑的干擾程度；交換算子概率為1-pinsert。IVNS隨機(jī)選擇一種交換算子實現(xiàn)每次抖動路徑的更改。抖動過程類似于遺傳算法的交叉操作。當(dāng)抖動過程結(jié)束后，只存在兩條路徑的交換信息；當(dāng)前解的大部分特征被保留下來，這在某種程度上加快了算法的收斂速度。

3.3 局部搜索過程

為了獲得VNS算法的局部最優(yōu)解，局部搜索過程將對抖動過程中所生成的兩條新路徑分別進(jìn)行局部搜索，并求出各自局部最優(yōu)解。局部搜索過程是整個VNS算法框架中最耗時部分，這在很大程度上決定了VNS算法的最終解質(zhì)量，因此必須充分考慮局部搜索算法設(shè)計的求解效率。本文的局部搜索算法設(shè)計主要考慮了局部搜索算子和搜索策略。為了求得短時間內(nèi)質(zhì)量較好的局部最優(yōu)解，本文選取兩種常用局部搜索算子：2-opt和3-opt，如圖3所示。每次局部搜索過程只采用一種算子，并通過隨機(jī)方式選擇算子，2-opt的選擇概率為 p2-opt；而3-opt的選擇概率為1-p2-opt。采用這種混合算子可充分發(fā)揮兩種算子特點，從而擴(kuò)大算法解空間。

圖2 插入和交換算子示意圖

圖3 2-opt和3-opt策略

搜索策略主要包括首次改進(jìn)和最佳改進(jìn)。前者是指求解過程中依次訪問當(dāng)前解x的鄰域解，若當(dāng)前所訪問的鄰域解xn優(yōu)于x，則x=xn并更新其鄰域解。重復(fù)上述步驟直到訪問完x的所有鄰域解。最后，將求得的x作為局部最優(yōu)解。后者是指求解過程中遍歷當(dāng)前解x的所有鄰域解，并從中選擇最優(yōu)鄰域解xn作為局部最優(yōu)解。兩者相比，前者求解質(zhì)量優(yōu)于后者，而后者耗時更短。本文采用最佳改進(jìn)策略，從而較好地平衡了求解質(zhì)量和運行時間。

3.4 后期優(yōu)化過程

為了加快收斂速度和提高解質(zhì)量，本文提出一種IVNS算法后優(yōu)化過程。完成局部搜索后，如果所求得局部最優(yōu)解 xl優(yōu)于全局最優(yōu)解 xb，即則繼續(xù)執(zhí)行后優(yōu)化過程以求得全局最優(yōu)解[9]。后優(yōu)化過程算法[10]適合求解帶時間窗旅行商問題和車輛路徑問題。其算法流程為：

步驟1假設(shè)待優(yōu)化路徑為r，長度為n，評價函數(shù)值為c。最終優(yōu)化路徑為r*，評價函數(shù)值為c*，并令r*=r，c*=c，k=1。

步驟2分別對優(yōu)化路徑r中的第k個客戶節(jié)點執(zhí)行解串和成串操作，從而得到優(yōu)化路徑r′和評價函數(shù)值c′。

步驟3若c′＜c*，則r*=r′，c*=c′，c=c′，然后跳轉(zhuǎn)至步驟2；否則k=k+1，算法停止。

3.5 解接受準(zhǔn)則

解接受準(zhǔn)則用于判定應(yīng)該接受哪一個解進(jìn)入下一次迭代。若x*優(yōu)于當(dāng)前解x，則x*替代x進(jìn)入下一次迭代；反之，利用模擬退火算法[11]的解接受準(zhǔn)則選擇進(jìn)入下一次迭代解。為了避免VNS過早陷入局部最優(yōu)，模擬退火算法的接受準(zhǔn)則能夠以式（11）的概率接受一定條件下的較劣解，這主要取決于VNS實際解成本差異及溫度T。每迭代nT次溫度T以數(shù)量進(jìn)行更新，其中q0為[0，1]中的一個隨機(jī)數(shù)，δmax為VNS算法的總迭代次數(shù)，初始溫度值T0=10：

4 實驗仿真及測試比較

為了評估IVNS的DVRP性能，分析算法的解質(zhì)量和效率，本文從三個不同測試角度對DVRP進(jìn)行實驗仿真，并與其他相關(guān)算法進(jìn)行比較。

4.1 四種算法的測試比較

為了比較不同算法的測試性能，此時采用文獻(xiàn)[12]的數(shù)據(jù)集來評估IVNS的DVRP性能。

IVNS算法的各種參數(shù)初始值設(shè)置如下：

（1）模擬退火算法的參數(shù)設(shè)置：初始溫度T0=10，每迭代生成溫度的變化值

（2）抖動過程參數(shù)值設(shè)置：pinsert=0.2，pcross=0.15，和picross=0.1。

表1給出IVNS、遺傳算法（GA）、禁忌搜索（TS）、兩階段算法（TPA）的比較測試結(jié)果。

表1 不同算法的測試結(jié)果

從表1中可以看出，四種算法都可找出最優(yōu)解，但最劣值和平均值存在明顯差異，搜索成功率和迭代次數(shù)也存在差異。四種算法搜索成功率從小到大依次為禁忌搜索算法、兩階段算法、遺傳算法和IVNS；最劣值、平均值從小到大依次為IVNS、兩階段算法、遺傳算法和禁忌搜索算法；這說明IVNS的全局搜索能力最強。四種算法的迭代次數(shù)從小到大順序依次為IVNS、禁忌搜索算法、兩階段算法和遺傳算法，這說明IVNS的收斂速度最快，因此某種程度上IVNS更合適求解動態(tài)車輛路徑問題。

4.2 VRPTW測試范例比較

測試用例采用Solomon編制的100節(jié)點VRPTW問題的計算范例。各范例包含100個節(jié)點，分布于100×100歐氏平面。范例分為6類：R1、R2、C1、C2、RC1和RC2。DVRPTW采用Lackner動態(tài)測試數(shù)據(jù)集。Solomon范例的每個問題，測試數(shù)據(jù)分別用五種動態(tài)度（90%，70%，50%，30%和10%）進(jìn)行描述。從IVNS和Lackner算法的測試結(jié)果可得出如下結(jié)論：（1）總行駛距離除了RC1，R1和C2外，IVNS的求解都優(yōu)于Lackner；（2）IVNS平均計算時間少于Lackner，且不超過90 s，這完全滿足實時調(diào)度需求。從而說明IVNS搜索能力更強。

4.3 擴(kuò)展測試比較

為了評估變鄰域搜索算法求解大規(guī)模動態(tài)車輛路徑問題的有效性，本文將文獻(xiàn)[2]測試實例擴(kuò)展至1 000個客戶。測試結(jié)果如表2所示。

表2 文獻(xiàn)[2]和IVNS算法的測試結(jié)果

從表2中可以看出，IVNS的平均運行時間少于Gehring，車輛數(shù)從62降至61，目標(biāo)值從40 045減小至39 926。因此IVNS算法在某種程度上可求解大規(guī)模動態(tài)VRP。

5 結(jié)論

針對動態(tài)車輛路徑問題，本文提出一種改進(jìn)變鄰域搜索算法。初始解利用節(jié)約算法求解每日車輛路徑問題的路線構(gòu)建。抖動過程采用插入和交換這兩種鄰域結(jié)構(gòu)。選取2-opt和3-opt作為局部搜索算子從而獲得短時間內(nèi)的較好局部最優(yōu)解，給出IVNS算法的后優(yōu)化過程以加快收斂速度和提高解質(zhì)量，采用三種不同測試用例驗證改進(jìn)變鄰域搜索算法性能，并與其他算法進(jìn)行了比較。比較結(jié)果表明，IVNS模型和算法可有效求解短時間內(nèi)的DVRP問題。

[1]Hansen P，Mladenovi? N，Perez-Britos D.Variable neighborhood decomposition search[J].Journal of Heuristics，2001，7（4）：335-350.

[2]Gehring H，Homberger J.Parallelization of a two-phased metaheuristic for routing problems with time windows[J]. Asia-Paeific Journal of Operational Research，2001，18（1）：35-47.

[3]Müller J.Approximative solutions to the bicriterion vehicle routing problem with time windows[J].European Journal of Operational Research，2010，202（1）：223-231.

[4]Polacek M，Hartl R F，Doerner K，et al.A variable neighborhood search for the multi depot vehicle routing problem with time windows[J].Journal of Heuristics，2004，10（6）：613-627.

[5]Goel A，Gruhn V.A general vehicle routing problem[J].European Journal of Operational Research，2008，191（3）：650-660.

[6]Hemmelmayr V C，Doerner K F，Hartl R F.A variable neighborhood search heuristic for periodic routing problems[J]. European Journal of Operational Research，2009，195（3）：791-802.

[7]Fleszar K，Osman I H，Hindi K S.A variable neighbourhood search algorithm for the open vehicle routing problem[J]. European Journal of Operational Research，2009，195（3）：803-809.

[8]Clarke G，Wright J W.Scheduling of vehicles from a central depot to a number of delivery points[J].Operations Research，1964，12（4）：568-581.

[9]王征，張俊，王旭坪.多車場帶時間窗車輛路徑問題的變鄰域搜索算法[J].中國管理科學(xué)，2011，19（2）：99-108.

[10]Gendreau M，Hertz A，Laporte G，et al.A generalized insertion heuristic forthe traveling salesman problem with time windows[J].Operations Research，1998，46（3）：330-335.

[11]王凌.智能優(yōu)化算法及其應(yīng)用[M].北京：清華大學(xué)出版社，2004.

[12]王旭，葛顯龍，代應(yīng).基于兩階段求解算法的動態(tài)車輛調(diào)度問題研究[J].控制與決策，2012，27（2）：175-181.

GE Jun1,ZHOU Lianying2

1.Department of Computer Science,Suqian College,Suqian,Jiangsu 223800,China
2.College of Computer Science and Communication Engineering,Jiangsu University,Zhenjiang,Jiangsu 212013,China

In order to effectively solve the dynamic vehicle routing problem with time windows,an improved variable neighborhood search algorithm is proposed and the corresponding mathematical model is established.The algorithm uses the clustering method to complete customer allocation and route planning for the construction of initial solution.Hybrid operators of insert-exchange are used to achieve the shaking process,the later optimization process is presented to improve the solution space,and the best improvement strategy is adopted,which achieves the algorithm a better balance in the solution quality and run-time.The idea of simulated annealing is introduced to control the acceptance of new solutions and the distribution of geographical location,etc, and the route selection is analyzed.Through comparison of experimental results with other algorithms it shows that the algorithm is feasible and efficient.

improved variable neighborhood search;shaking;simulated annealing;later optimization process;metaheuristic

為了切實求解帶時間窗的車輛動態(tài)路徑問題，提出一種改進(jìn)變鄰域搜索算法，并建立了相應(yīng)數(shù)學(xué)模型。算法運用聚類方法完成客戶分配和路線規(guī)劃的初始解構(gòu)建。插入-交換混合算子實現(xiàn)抖動過程，提出后優(yōu)化過程改進(jìn)解空間，并采用最佳改進(jìn)策略實現(xiàn)算法在求解質(zhì)量和運行時間上的最佳平衡，引入模擬退火思想控制新解接受、地理位置分布等，并對路徑選擇進(jìn)行了分析。通過與其他算法的實驗結(jié)果比較表明該算法的可行性和高效性。

改進(jìn)變鄰域搜索；抖動；模擬退火；后優(yōu)化；元啟發(fā)式

A

TP393；TP391.9

10.3778/j.issn.1002-8331.1308-0220

GE Jun,ZHOU Lianying.Improved variable neighborhood search algorithm for dynamic vehicle routing.Computer Engineering and Applications,2013,49（23）：71-74.

江蘇省宿遷市科技創(chuàng)新專項基金資助項目（No.Z201211）。

戈軍（1977—），男，副教授，研究方向為計算機(jī)網(wǎng)絡(luò)安全、無線傳感器網(wǎng)絡(luò)、車輛管理等；周蓮英（1964—），女，博士，教授。E-mail：gjun@sqc.edu.cn

2013-08-16

2013-10-08

1002-8331（2013）23-0071-04