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

戈 軍，周蓮英

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

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

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

戈 軍1，周蓮英2

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

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

1 引言

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

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

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

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

變量定義如下：

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

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

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

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

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

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

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

式（10）表示其他約束。

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

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

圖1 IVNS算法流程圖

3.1 初始解

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

3.2 抖動(dòng)過程

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

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

3.3 局部搜索過程

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

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]適合求解帶時(shí)間窗旅行商問題和車輛路徑問題。其算法流程為：

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

步驟2分別對(duì)優(yōu)化路徑r中的第k個(gè)客戶節(jié)點(diǎn)執(zhí)行解串和成串操作，從而得到優(yōu)化路徑r′和評(píng)價(jià)函數(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)該接受哪一個(gè)解進(jìn)入下一次迭代。若x*優(yōu)于當(dāng)前解x，則x*替代x進(jìn)入下一次迭代；反之，利用模擬退火算法[11]的解接受準(zhǔn)則選擇進(jìn)入下一次迭代解。為了避免VNS過早陷入局部最優(yōu)，模擬退火算法的接受準(zhǔn)則能夠以式（11）的概率接受一定條件下的較劣解，這主要取決于VNS實(shí)際解成本差異及溫度T。每迭代nT次溫度T以數(shù)量進(jìn)行更新，其中q0為[0，1]中的一個(gè)隨機(jī)數(shù)，δmax為VNS算法的總迭代次數(shù)，初始溫度值T0=10：

4 實(shí)驗(yàn)仿真及測(cè)試比較

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

4.1 四種算法的測(cè)試比較

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

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

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

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

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

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

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

4.2 VRPTW測(cè)試范例比較

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

4.3 擴(kuò)展測(cè)試比較

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

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

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

5 結(jié)論

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

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

改進(jìn)變鄰域搜索；抖動(dòng)；模擬退火；后優(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)新專項(xiàng)基金資助項(xiàng)目（No.Z201211）。

戈軍（1977—），男，副教授，研究方向?yàn)橛?jì)算機(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