面向動態車輛路徑的改進變鄰域搜索算法

戈 軍，周蓮英

1.宿遷學院 計算機科學系，江蘇 宿遷 223800

2.江蘇大學 計算機科學與通信工程學院，江蘇 鎮江 212013

面向動態車輛路徑的改進變鄰域搜索算法

戈 軍1，周蓮英2

1.宿遷學院 計算機科學系，江蘇 宿遷 223800

2.江蘇大學 計算機科學與通信工程學院，江蘇 鎮江 212013

1 引言

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

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

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

2 DVRP問題的數學描述

變量定義如下：

帶時間窗動態車輛路徑問題可轉化為混合整數線性規劃問題。目標是最小化總成本，其目標函數為：

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

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

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

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

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

式（7）為容量約束：表明車輛交付的整體負載不應超過其容量。

式（10）表示其他約束。

3 改進變鄰域搜索算法

VNS基本思想：首先在搜索過程中通過系統改變當前解的鄰域結構集以拓展搜索范圍，接著采用局部搜索算法求解局部最優解，然后基于此局部最優解重復上述過程，經過多次迭代后最終實現收斂目的。圖1給出IVNS算法流程。

圖1 IVNS算法流程圖

3.1 初始解

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

3.2 抖動過程

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

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

3.3 局部搜索過程

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

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

圖3 2-opt和3-opt策略

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

3.4 后期優化過程

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

步驟1假設待優化路徑為r，長度為n，評價函數值為c。最終優化路徑為r*，評價函數值為c*，并令r*=r，c*=c，k=1。

步驟2分別對優化路徑r中的第k個客戶節點執行解串和成串操作，從而得到優化路徑r′和評價函數值c′。

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

3.5 解接受準則

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

4 實驗仿真及測試比較

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

4.1 四種算法的測試比較

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

IVNS算法的各種參數初始值設置如下：

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

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

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

表1 不同算法的測試結果

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

4.2 VRPTW測試范例比較

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

4.3 擴展測試比較

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

表2 文獻[2]和IVNS算法的測試結果

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

5 結論

針對動態車輛路徑問題，本文提出一種改進變鄰域搜索算法。初始解利用節約算法求解每日車輛路徑問題的路線構建。抖動過程采用插入和交換這兩種鄰域結構。選取2-opt和3-opt作為局部搜索算子從而獲得短時間內的較好局部最優解，給出IVNS算法的后優化過程以加快收斂速度和提高解質量，采用三種不同測試用例驗證改進變鄰域搜索算法性能，并與其他算法進行了比較。比較結果表明，IVNS模型和算法可有效求解短時間內的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].中國管理科學，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]王凌.智能優化算法及其應用[M].北京：清華大學出版社，2004.

[12]王旭，葛顯龍，代應.基于兩階段求解算法的動態車輛調度問題研究[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

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

改進變鄰域搜索；抖動；模擬退火；后優化；元啟發式

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.

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

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

2013-08-16

2013-10-08

1002-8331（2013）23-0071-04