改進變鄰域搜索算法在求解VRPMT的應用*

宋 強 杜暖男

(廣東理工學院信息工程系1) 526100 肇慶) (平頂山工業職業技術學院計算機與軟件工程學院2) 平頂山 467001)

改進變鄰域搜索算法在求解VRPMT的應用*

宋 強1)杜暖男2)

(廣東理工學院信息工程系1)526100 肇慶) (平頂山工業職業技術學院計算機與軟件工程學院2)平頂山 467001)

多行程車輛路徑問題是標準車輛路徑問題的一個變體，每個車輛在運行期間可以使用不止一次.對于這種NP-HARD問題，提出了1個改進變鄰域搜索算法并設計了4個鄰域結構用于求解和制定多行程路徑問題的調度規劃.該算法測試了1組標準實例問題，獲得的解決方法與文獻中提出的5種算法進行比較，并得到了較好的結果.

車輛路徑問題；多行程；變鄰域搜索；抖動

0 引 言

標準的車輛路徑問題(vehicle routing problem，VRP)指的是具有一定容量的相同車輛訪問或者交付貨物給若干客戶.其目的是對車輛行程進行規劃，以最小化總成本 (如行駛時間、行駛距離等)來服務和滿足所有客戶需求.每個客戶必須只能被訪問1次，每個行程必須開始和結束于倉庫.每輛車的交付貨物的數量不得超過車輛的容量，行駛距離不得超過預先定義的范圍.

文中主要研究了多行程車輛路徑問題(vehicle routing problem with multiple trips，VRPMT)，這是標準VRP的一個變種，特點是每輛車在工作期間可以使用不止1次.

針對多行程車輛路徑問題的研究，國內研究文獻較少.宋強等[1]為了同時解決多行程車輛路徑問題和配送中心定位問題，采用模擬退火的邏輯和交換算法來獲得最優路線，并改善了模擬退火算法中當前溫度控制的位置.張媛媛等[2]研究了多行程帶時間窗口的車輛調度問題，設計了計算路線時間窗口的具體數學模型，并且通過數學推導證明了該時間窗口是等待費用最小的服務時間窗口.許爭爭等[3]考慮車輛容量和繞行時間限制等因素提出了1種基于協作的3階段算法，通過案例分析證明了該方法可以更好的提供車輛調度方案.在國外，Fleischmann[4]首先對這個VRPMT進行了研究，他針對著名的節約算法提出了1個修改方法和一個裝箱啟發式算法.之后許多文獻都提出了啟發式算法解決問題，如3段論啟發式算法、禁忌搜索算法、1個多階段構建的啟發式算法、基于自適應記憶過程修改的啟發式算法及一個混合遺傳算法[5-9].但是，以上文獻中沒有研究人員采用改進變鄰域算法對這個問題進行相應的研究.

變鄰域搜索算法主要由鄰域轉換機制(抖動)和局部搜索算法組成[10].變鄰域算法的特點是容易找到當前解域范圍內的最優解.其中局部搜索算法構造了只接受更優解作為下1次操作的個體，是1種功能強大的局部探索過程，而抖動不考慮解的優劣，只要滿足條件即可，很容易產生更多未探索過的新解.兩者結合達到某種平衡就能找到所有問題的全局最優解.

基于此，很多研究采用變鄰域算法來求解各種問題.張曉楠等[11]采用變鄰域分散搜索算法來求解同時配集貨的定位-路線問題，在保留組合策略的全局搜索能力的基礎上，再運用變鄰域搜索算法進行局部開發來提高可行解質量.潘全科等[12]為了解決作業車間調度問題，充分利用了粒子群算法和變鄰域搜索算法的互補性能，提出1種新的粒子群-變鄰域搜索的混合算法.戈軍等[13]采用聚類方法完成客戶分配和路線規劃的初始解構建，設計了最佳改進策略實現算法以獲得在求解質量和運行時間上的最佳平衡.

文中提出了1種改進變鄰域搜索算法(variable neighborhood search，VNS)來解決VRPMT，在該算法中，采用4個不同的鄰域結構，其中2個用于最小化行程總長度和超時，另外2個用于最小化超時.在抖動步驟中，在概率分布的基礎上采用了3種類型的鄰域，通過比較研究，結果說明提出的算法優越于其他研究方法.

1 用于VRPMT的變鄰域搜索

1.1 符號定義

車輛i的超時由下列表達式給出

max(0,DTi-T)

(1)

最長行駛比率(LTR)用于提供現有方案中的最長(最差的)超時.

(2)

1.2 方案展示

1.3 初始解

1.4 評價函數

提出的目標函數類似于文獻[8]提出的函數.它是采用1個由總行駛時間、超時和超容量懲罰的相關計算得到的1個動態的函數.

α和β參數以動態的方式進行調整，以較小的步驟進行鄰域擴展，并增加插入和交換的移動能力.

(4)

1.5 變鄰域下降算法

該變鄰域下降算法采用4個鄰域結構(N1，N2，N3和N4)尋找每輛車每個行程的最佳客戶配置.鄰域算符N1包括4種插入位移.從位置i移動1個客戶插入到位置j: ①在同1行程；②在相同車輛的另1個行程；③在另1輛車的另1個行程；④第4次移動，從位置i移除1個客戶，并將它插入到相同車輛或另1個車輛新創建的行程中.第2個鄰域結構N2從車輛i中移除1個行程k并把它插入車輛j.第3和第4鄰域結構(N3，N4)交換移動過程.鄰域結構N3采用3次移動交換，分別是：①2個客戶在同1個行程內的位置交換；②相同車輛的2個不同行程的客戶交換；③來自2個不同車輛的2個行程內的2個客戶交換.第4鄰域N4互換2個不同車輛的2個行程.領域結構N1和N3用于最小化多個行程和超時時間的總長度.而鄰域結構N2和N4用于最小化超時時間.提出的可變鄰域下降算法的步驟見算法1.

算法1 變鄰域下降算法(VND)

Input：鄰域集合Nh，h=1,2，…,hmax=4

Initialization：找一個初始解s；

Repeat

h←1;

Whileh≤hmaxdo

s′←s的最佳鄰域， s′∈Nh(s)

Iff(s′)

s←s′;

h←1;

else

h←h+1

endif

endwhile

until不能獲得任何改進為止

returns;

1.6 抖動

給定1個鄰域結構N，Nm表示在鄰域N中的第m個連續的移動.在抖動步驟中，將m次移動應用到鄰域(N1,N3和N4).對于每1個從1到m的i 的取值，我們將選擇1個基于概率Pk分布的鄰域結構Nk(k∈{1,3,4})，進行隨機的移動.

1.7 變鄰域搜索

該變鄰域搜索算法的主要步驟是：初始化，抖動，用變鄰域下降(variableneighborhooddescent，VND)算法進行局部搜索和評估，這些步驟見算法2.

算法2 變鄰域下降算法(VND)

Input: 鄰域集合Nh，h=1,2，…,hmax，

Initialization: 找一個初始解s;

Repeat

h←1;

Whileh≤hmaxdo

s′←對s進行抖動，

s″←VND(s′)

Iff(s″)

s←s″;

h←1;

else

h←h+1

endif

endwhile

until符合終止條件A

returns;

首先從初始解決方案s開始，接下來，通過對方案s執行抖動步驟設計1個解決方案s′，該解決方案將作為VND算法尋找1個局部最優s″的基礎.在評價步驟中，如果f(s″)

2 計算結果

該改進VNS算法采用來自Christofides改編的VRP數據集進行測試.相關的算法采用C++語言編寫，并在戴爾筆記本電腦T2130@1.86GHz，1GRAM上運行.采用了由文獻[5-9]等發現的標準進行比較研究，采用發明人的姓名縮寫分別簡稱為TG，BM，PS1，OV和PS2，并結合最長行駛比(LTR)對結果進行比較.在程序運行的基礎上，設定以下參數用于生成計算結果，α∈(0.001,0.999)，ε1=0.001，β∈[1，100]，ε2=0.01.在抖動過程中，在鄰域(N1，N3和N4)執行hmax=3的移動，并分別選擇概率為0.6，0.4和0.2.

通過表1看到，VNS算法能夠在104個樣例中的99個樣例中找出可行的解決方案，包括任意1個早期工作都無法解決的實例.對于算法PS1，TG，BM和PS2，幾乎所有的算法在解決帶時間T1的標準樣例時都遇到了一些困難，解決方案的成功率低于73%.而算法VNS和OV的成功率明顯優于其他算法，分別為90.38%和88.46%.

表1 通過改進VNS算法和其他標準找到的可行解的數量

在表2展示了提出的算法，以及上面提到的其他文獻中都不能找到可行解的標準樣例的數量. 表2利用LTR比率說明了比較結果，其中在每個標準樣例中該VNS算法都無法找到可行解.從這些結果我們注意到從5個未解決的標準樣例中該改進VNS算法提供了4個樣例的最佳解決方案，其次是OV算法也提供了和VNS算法相同的結果，CMT1實例稍差些.BM算法提供的F71實例也獲得了最佳結果.

表2 用于不可行解決方案的最長行駛比(LTR)的比較

表3給出了針對每個實例的5次比較的平均CPU時間.表4為當NV=7和T=154時CMT4新的可行解.結果表明，該VNS算法在解決這些標準實例時相對較快.

表3 平均CPU時間 s

表4 當NV=7和T=154時CMT4新的可行解

最后，基于以上提供的不同結果，考慮到能夠找到可行解的標準實例的數量，求解的質量以及尋找分配的CPU時間，該算法相比其他算法是很有競爭力的，它可以歸類為解決VRPMT問題的最佳算法.

3 結 束 語

提出1種改進變鄰域搜索算法(VNS)來解決帶多行程的車輛路徑問題.采用4個不同的鄰域結構，其中2個用于最小化行程總長度和超時，另外2個用于最小化超時.在抖動步驟中，在概率分布的基礎上采用了3種類型的鄰域.比較研究表明，該算法與其他文獻中的結果相比提供了較高質量的求解結果，說明本文提出的算法優越于其他研究方法.在未來的工作中，該算法可以擴展到求解混合車輛的車隊問題或帶多車廂的車輛路徑問題.

[1]宋強,劉凌霞.多行程車輛路徑問題和配送中心定位問題的研究[J].數學的實踐與認識,2016,46(7):103-113.

[2]張媛媛,曾曉燕.多行程帶時間窗的車輛調度問題研究[J].數學的實踐與認識,2015,45(7):1-7.

[3]許爭爭,唐加福.基于協作的三階段啟發式算法求解多行程車輛行程問題[J].南開大學學報(自然科學版),2015,48(5):51-59.

[4]FLEISCHMANN B. The vehicle routing problem with multiple use of vehicles[J].Working Paper, Fachbereich Wirschaftswissenschaften,1990(1):55-58.

[5]TAILLARD E, LAPORTEV G,GENDREAU M. Vehicle routing problem with multiple use of vehicles[J]. Journal of the Operational Research Society,1996,47(8):1065-1070.

[6]BRANDAO J, MERCER A. The multi-trip vehicle routing problem[J].Journal of the Operational Research Society,1998,49(8):799-805.

[7]PETCH R J, SALHI S. A multi-phase constructive heuristic for the vehicle routing problems with multiple trips[J]. Discrete Applied Mathematics,2003,133(1):69-92.

[8]OLIVERA A, VIERA O. Adaptive memory programming for the vehicle routing problem with multiple trips[J]. Computers & Operations Research,2007,34(1):28-47.

[9]SALHI S, PETCH R J.A GA based heuristic for the vehicle routing problem with multiple trips[J]. Journal of Mathematical Modeling and Algorithms,2007,6(4):591-613.

[10]JARBOUI B, DERBEL H S, HANAFI, et al. Variable neighborhood search for location routing[J]. Computers & Operations Research,2013,40(1):47-57.

[11]張曉楠,范厚明,李劍鋒.同時配集貨定位—路線問題的變鄰域分散搜索算法[J].計算機集成制造系統,2015,21(9)：2535-2548.

[12]潘全科,王文宏,朱劍英.基于粒子群優化和變鄰域搜索的混合調度算法[J].計算機集成制造系統,2007,13(2):323-328.

[13]戈軍,周蓮英.面向動態車輛路徑的改進變鄰域搜索算法[J].計算機工程與應用,2013,49(23):71-74.

Application of Improved Variable Neighborhood Search Algorithm for VRPMT

SONG Qiang1)DU Nuannan2)

(DepartmentofInformationEngineering,GuangdongPolytechnicCollege,Zhaoqing526100,China)1)(SchoolofComputerandSoftwareEngineering,PingdingshanIndustrialCollegeofTechnology,Pingdingshan467001,China)2)

The vehicle routing problem with multiple paths is a variant of the standard VRP, where each vehicle can be used more than once during the working period. For this NP-Hard problem, this paper proposes an improved variable neighborhood search algorithm in which four neighborhood structure are designed to find the planning of paths. The algorithm is tested on a set of benchmark problems and the obtained solutions are compared with five previously proposed algorithms. Encouraging results are obtained.

vehicle routing; multipath; variable neighborhood search; shaking

2016-10-26

*河南省科技攻關基金項目資助(142102210231)

TP301.6

10.3963/j.issn.2095-3844.2017.01.006

宋強(1971—)：男，副教授，博士生，主要研究領域為計算機控制技術與算法優化