Discrete Optimization
A parallel multi-neighborhood cooperative tabu arch for capacitated vehicle routing problems
Jianyong Jin a ,Teodor Gabriel Crainic b ,⇑,Arne Løkketangen a
李世民
a Molde University College,Specialized University in Logistics,N-6411,Molde,Norway
b
School of Management,UQAM &Interuniversity Rearch Centre on Enterpri Networks,Logistics and Transportation,Montréal,QC,Canadai54200
参差不齐读音a r t i c l e i n f o Article history:
Received 7December 2010Accepted 2May 2012
Available online 29May 2012Keywords:Routing
Parallel metaheuristics Multi-neighborhood Cooperative arch Solution pool
a b s t r a c t
This paper prents a parallel tabu arch algorithm that utilizes veral different neighborhood struc-tures for solving the capacitated vehicle routing problem.Single neighborhood or neighborhood combi-nations are encapsulated in tabu arch threads and they cooperate through a solution pool for the purpo of exploiting their joint power.The computational experiments on 32large scale benchmark instances show that the propod method is highly effective and competitive,providing new best solu-tions to four instances while the average deviation of all best solutions found from the collective best results reported in the literature is about 0.22%.We are also able to associate the ben
eficial u of special neighborhoods with some test instance characteristics and uncover some sources of the collective power of multi-neighborhood cooperation.
Ó2012Elvier B.V.All rights rerved.
1.Introduction
The vehicle routing problem (VRP )describes the allocation of transportation tasks to a fleet of vehicles,and the simultaneous routing of each vehicle.The VRP was first described by Dantzig and Ramr (1959),and has been proved NP-hard by Lenstra and Kan (1981).Due to its high industrial applicability and complexity,the VRP has been the object of numerous studies and a great num-ber of papers have propod solution methods.The methods compri both exact and heuristic algorithms.Since the VRP is NP-hard,it is not always possible to solve instances to optimality within limited computing time.Exact algorithms have been ud to solve the VRP instances with up to about 100customers (La-porte,2007).For larger problems,heuristics and metaheuristics are more appropriate,especially tabu arch (TS )(Glover and Lagu-na,1997),which has often been ud successfully.For more infor-mation on the VRP,its solution methods and the recent work,we refer to the books of Toth and Vigo (2002),Golden et al.(2008)and the survey paper of Laporte (2007).
Among the solution methods for solving the VRP,one trend is to adopt parallel algorithms.For instance,parallel algorithms are increasingly applied in real time vehicle routing contexts,where solutions have to be timely generated (Ghiani et al.,2003).Unlike quential algorithms which run on a single processor and are exe-cuted quentially,parallel algorithms run multiple process simultaneously on available processors with the common goal of solving a given problem instance.Crainic (2008)describes the main strategies ud on this group of algorithms and also provides an up-to-date survey of contributions to this rapidly evolving field.The author also points out that parallel algorithms can both speed up the arch and improve the robustness and the quality of the solutions attained.Thus it would be advantageous to make u of parallelism.
Another feature of the latest metaheuristics for the VRP is to u multiple neighborhoods (e.g.,Li et al.,2005;Kytöjoki et al.,2007;Mester and Bräysy,2007;Groër et al.,2011).From the outcome of the algorithms,one may perceive that it is beneficial to em-ploy multiple neighborhoods.Indeed,each neighborhood can be ud to improve or modify a solution in its particular way such as reinrting a node,swapping two nodes and so forth.For a par-ticular instance,at a certain stage,a specific neighborhood may be more effective than the others by leading the arch through its own distinct arch trajectory and producing better solutions.We term such a capability of a neighborhood as its
effectiveness.Moreover,it is also noticeable that in the methods multiple neighborhoods are ud in rial manner,in that each neighbor-hood is ud one after another following a fixed or randomized -quence.One may wonder whether it can be more effective to u multiple neighborhoods in a parallel way instead.The objective of this paper is to explore the strategy of utilizing multiple neigh-borhoods in a parallel tting and analyze their effectiveness for solving the capacitated vehicle routing problem (CVRP ).
热水洗脸
The CVRP,as the classical version of the VRP,is defined on a graph G ¼ðN ;A Þ,where N ¼f 0;...;n g is a vertex t and A ¼fði ;j Þ:i ;j 2N g is an arc t.Vertex 0is the depot,where the
0377-2217/$-e front matter Ó2012Elvier B.V.All rights rerved.dx.doi/10.1016/j.ejor.2012.05.025
本科没有学位证Corresponding author.Tel.:+15143437143;fax:+15143437121.
E-mail ainic@cirrelt.ca (T.G.Crainic).
vehicles depart from and return to.The other vertices are the cus-tomers which have a certain demand d to be delivered(or picked up).The travel cost between customer i and j is defined by c ij>0.
The vehicles are identical.Each vehicle has a capacity of Q.The objective is to design a least cost t of routes,all starting and ending at the depot.Each customer is visited exactly once. The total demand of all customers on a route must be within the vehicle capacity Q.Some CVRP instances may have an additional route duration limit constraint,restricting the duration(or length) of any route not to exceed a pret bound D.The method prented in this paper is able to solve problems both without and with route duration limit constraint.
The main contribution of this paper is the development of an effective parallel multi-neighborhood tabu arch(PMNTS)meth-od which contains veral cooperative TS threads,each using a sin-gle neighborhood or a neighborhood combination.The experiments on32large scale CVRP benchmarks demonstrate that the propod algorithm is effective and competitive.Itfinds new best solutions for four instances while the rest of the results are highly comparable to the best solutions reported in the literature. In addition,we are also able to associate the beneficial u of spe-cial neighborhoods with some test instance characteristics and un-cover some origins of the collective power of multi-neighborhood cooperation.
The remainder of this paper is organized as follows.In the next ction our problem solving methodology is introduced.After that, Section3describes veral variants developed for analyzing the
performance of the propod method.Then Section4prents the algorithm configurations and the computational results.Final-ly,conclusions are prented in Section5.
2.Description of the parallel algorithm
In this ction,the propod parallel multi-neighborhood coop-erative tabu arch metaheuristic is introduced.We start with a general description of the algorithm,and then the description of the main arch pha is provided in Section2.1.After that,Section 2.2introduces the cooperating TS threads.Then the initial solution pha is described in Section2.3.
The general scheme of the propod algorithm is displayed in Algorithm1.The method consists of two phas.The goal of the first pha is to create a feasible starting solution(Line1of Algo-rithm1).In the cond pha(Line2–8of Algorithm1),the starting solution is gradually improved by the joint effort of four different TS threads working in parallel(Line4).Each TS thread utilizes a distinct neighborhood or neighborhood combination for inter-route moves and thus follows a different arch strategy.The threads exchange the best solutions found periodically through a solution pool(Line5–6).This pha is the core component and 2.1.The main arch pha
In the main arch pha,the four TS threads cooperate through a solution pool,focusing on improvi
ng the starting solution.
For a multi-thread metaheuristic,generally there are three types of parallelization strategy.Thefirst type is independent mul-ti-arch in which multiple threads run simultaneously without any information exchange.The cond type is allowing arch threads to exchange information directly between each other. The third strategy is to exchange information between threads through a solution pool.The reason we lect the last strategy is twofold.First,it has been stated that the third strategy is more effective and parsimonious than the other two(Crainic,2008).Sec-ond,some TS threads included in the propod algorithm are not designed for independent u.Their individual performances are quite poor.Information exchange ems to be a necessity for them to work well in this context.The collaboration between the TS threads and the solution pool is depicted in Fig.1.The arrows in thefigure reprent the solution exchange between the TS threads and the solution pool.
The solution pool,which can be called a solution warehou as well,keeps the best solutions nt by each arch thread and sorts the solutions according to their quality,eliminating duplicate solutions and providing new starting solutions for each arch thread.Each arch thread only communicates with the solution pool.
To create moments for communications with each arch thread,the cond pha is partitioned into a certain number of gments(or arch periods).During each gment the four arch threads operate a certain amount of time,then they stop to export their best solutions found to the solution pool and obtain a new solution from where to start the next gment.If there is a new best solution in the pool,this new best will be the starting solution for the next gment.Though a best solution may not al-ways lead to another best one,we prefer to explore itfirst rather than a solution randomly lected.When there are no new best solutions in the pool,the new starting solution is lected by con-sidering two criteria,namely the solution quality(the total travel distance)and the difference from the current best solution.The solution difference is measured by the number of different edges. Here,solutions with a certain amount(a parameter)of different edges are accepted so as to resume the arch from sufficiently dis-tinct solutions compared to the one reached when the arch stopped.The solutions in the pool are sorted from the best to the worst according to the total travel distance,and each solution also has aflag that indicates whether it has been previously improved upon.Thisflag is ud to avoid repeatedly lecting the same solu-tion to resume the arch.The solutions are checked from the best to the worst,and thefirst solution which has not been ud before
Fig.1.Collaboration diagram.
442J.Jin et al./European Journal of Operational Rearch222(2012)441–451
are kept in the same area of the arch space to intensively arch that area.Third,for a given starting solution,the neighborhood that is the most appropriate for generating improvement will have the opportunity to work on the solution.
In terms of the taxonomy introduced by Crainic and Nourredine (2005)for parallel metaheuristics,our algorithmfits into the pC/ KS/SPDS classification.Thefirst dimension pC indicates the global arch is controlled by multiple cooperative threads.The cond dimension KS stands for knowledge synchronization and refers to the fact that multiple threads share information synchronously. The last dimension SPDS indicates multiple arch threads make u of different arch strategies from the same initial solution during each period.
2.2.The tabu arch threads
In this sub-ction,the common features and the differences between the TS threads included in the propod algorithm are provided.
2.2.1.The common features of the tabu arch threads
The TS threads included in the propod method are developed on the basis of the granular tabu arch that wasfirst introduced by Toth and Vigo(2003).Granular TS is a mechanism which is able to reduce the computational effort,especially for large instances by not considering some of the unpromising solution components(in their ca,the long edges).In this paper,a similar,but somewhat different granular neighborhood is implemented.It is to lect a t of the nearest neighbors(plus the depot)for each customer, and then only moves involving one member of this nearest neigh-bors t will be considered.The size of the nearest neighbors t (denoted as SNNS)can be lected by considering the instance characteristics and the requirements of the solution quality(or the time available for computation)as suggested by Branchini et al.(2009).The other aspects of TS framework are described below.
2.2.2.Inter-route neighborhood structure
Three basic neighborhood structures for inter-route operations, which are commonly ud in the previously published metaheuris-tics for the VRP,are lected and implemented in the TS threads. The basic idea of each neighborhood structure is described as follows.
秋季旅游Reinrtion(Savelsbergh,1992)refers to relocating a customer node from one route to another route.
Exchange(Osman,1993)swaps two customer nodes from two routes.
2-opt⁄(Potvin and Rousau,1995)combines two routes so that the last customers of a given route are introduced after thefirst customers of another hanging the head or tail part of two routes.
Each TS thread included in the propod algorithm utilizes one or a distinct subt of the neighborhoods.Thus each thread fol-lows a different arch strategy.When a TS thread incorporates more than one neighborhoods for inter-route moves,one of the in-cluded neighborhoods is randomly lected according to a certain probability at each iteration.
2.2.
3.Neighborhood generation and evaluation
For each inter-route neighborhood structure,at each iteration, all customer nodes are ud to generate neighboring solutions. For each customer node u,assuming in route R1in the current solution s,find the nodes which are in its nearest neighbors t but not in route R1.The t of the nodes is denoted as X.For each node v in X in route R2,
Reinrtion:move u to route R2after node v.
Exchange:swap the positions of u and v.
2-opt⁄:denote the node after u in route R1as u0,denote the node before v in route R2as v0,replace edgeðu;u0Þandðv;v0Þwith edgeðu;vÞandðu0;v0Þ.
To explore the solution space more thoroughly,infeasible inter-mediate solutions are allowed.For this purpo,capacity and route length constraints are relaxed and their violations are penalized in the objective function.This augmented objective function is com-puted as FðsÞ¼CðsÞþa QðsÞþb DðsÞ,where CðsÞis the total travel distance,QðsÞand DðsÞdenote the total violations of capacity and route length constraints respectively,a and b are penalty multipli-ers.The values of the penalty multipliers are lf-adjusted during the cour of the arch as described by Toth and Vigo(2003). The neighboring solutions(either feasible or infeasible)generated by each neighborhood operator are evaluated in terms of the aug-mented objective function.
In addition,to speed up the arch,the neighborhood explora-tion and evaluation for inter-route moves are parallelized by decomposing the computational tasks to different threads.
2.2.4.Solution acceptance and tabu mechanism
Among the neighboring solutions,the best move in terms of the augmented objective function that is non-tabu or satisfies the aspi-ration criterion is accepted.The aspiration criterion overrides the tabu status of a move if this move leads to a new best solution.
The tabu list is neighborhood dependent.The tabu list tenure tt of each neighborhood is t to be proportional to the number of customer nodes in the instance.For reinrtion,if u is relocated, u is declared tabu for tt iterations and any moves relocating u can-not be performed unless it satisfies the aspiration criterion.For ex-change move swapping u and v,the two nodes are declared tabu and any moves swapping u and v cannot be performed unless it satisfies the aspiration criterion.For2-opt⁄moves adding edge ðu;vÞandðu0;v0Þ,node u,v and v0are declared tabu,any moves adding edgeðu;u0Þandðv;v0Þare forbidden unless it satisfies the aspiration criterion.
2.2.5.Route refinement
In the TS threads,at each iteration,after an inter-route move, the two modified routes are refined parately by an intra-route optimization procedure.The procedure consists of two simple heu-ristics developed by implementing2-opt(Flood,1956)and reinr-tion(Savelsbergh,1992)neighborhood structures in local arch tting.The two heuristics are applied to a route alternately.The heuristic us
ing2-opt repeatedly eliminates two edges and adds two new edges,improving moves are accepted until no improve-ment can be found.The heuristic using reinrtion eks improve-ment by relocating a node to another position,if a move reduces the route length,then it is accepted.The procedure terminates when no improvement can be found.
2.2.6.Solution exchange
父爱The TS threads pau and exchange solutions with the solution pool after running for a certain amount of time.Each TS thread ex-ports its best solution and receives a new solution to resume the arch from.
2.2.7.Search process
Each tabu arch thread starts off with the starting solution s i created in thefirst pha.At each iteration,a neighborhood is -lected to generate a t of neighbors and the least cost non-tabu
J.Jin et al./European Journal of Operational Rearch222(2012)441–451443
solution s is lected to replace the current solution s.Then the re-ver moves are declared tabu and the routes just modified are re-fined by the intra-route optimization procedure.In addition,if the c
urrent solution s is feasible and better than the best solution sÃ,re-place sÃwith s.Moreover,periodically each tabu arch thread stops to exchange solutions with the solution pool and us the re-ceived solution to replace its current solution and the best solution, the tabu lists are re-initialized.This process is summarized in Algo-rithm2.
Algorithm2.Tabu arch
1:Set süs i;s¼s i;CðsÃÞ¼Cðs iÞ
2:Initialize tabu lists and penalty multipliers
3:while termination conditions not met do
4:Select a neighborhood and SNNS for inter-route moves
5:Generate and evaluate neighboring solutions
6:Select a neighboring solution s that minimize Fð sÞand is non-tabu or satisfies the aspiration criterion,t s¼ s
7:Set the rever moves tabu for tt iterations
8:Refine the routes modified
9:If s is feasible and CðsÞ<CðsÃÞ,t süs;CðsÃÞ¼CðsÞ
10:Update penalty multipliers
11:If reaching the time limit,pau and exchange solutions with the solution pool,ret sÃ,s,CðsÃÞand tabu lists
12:end while
2.2.8.The differences between the tabu arch threads
As summarized in Table1,each TS thread utilizes a distinct neighborhood or neighborhood combination for inter-route moves and thus each thread plays a different role in the cooperative arch.
Thread1utilizes two neighborhoods(reinrtion and2-opt⁄) for inter-route moves in rial fashion.In each iteration a neigh-borhood is randomly lected according to a certain probability. The probability of using reinrtion neighborhood is much higher than using2-opt⁄.Preliminary computatio
nal experiments show that using such a combination is more effective than using only reinrtion neighborhood,especially for the instances with tight constraints.For the actual probability values ud,e Section 4.3.One advantage of such rial neighborhood cooperation can be that this mechanism allows different neighborhoods to work one after another on intermediate infeasible solutions which may lead to good feasible solutions.
Thread2and Thread3are similar.They utilize one single neigh-borhood for inter-route moves trying to improve the given solu-tion.The two neighborhoods can be quite effective for some instances at various arch stages.Thus,with the two threads, the propod method is able to identify good solutions for a broad variety of instances.
Thread4is different from the other three.Its main task is to diversify the arch process.This thread consists of an extra solu-tion perturbation procedure.Before the normal TS procedure starts,the starting solution is perturbedfirst.The perturbation pro-cedure consists of two steps.Firstly,a certain percentage of nodes of a solution are removed from the solution.The term perturbation strength is ud to refer to this percentage.Half of tho nodes are lected from the nodes which are connected to their distant neighbors while the other half are lected randomly.During the cond step,reinrt the nodes removed one by one to a different route,next to one of its nearest neighbors
so as to cau the least deterioration in terms of the augmented objective function value. The thread utilizes three neighborhoods(reinrtion,2-opt⁄and exchange)for inter-route moves in rial fashion.The neighbor-hood lection rule is similar as in Thread1.
2.3.The initial solution pha
As displayed in Algorithm1,the goal of thefirst pha is to cre-ate a feasible starting solution.There are three steps in the pha. Step one creates an initial solution in which each customer is rved individually by a parate ,the number of routes equals the number of customers.In step two,the routes are merged by a route reduction procedure so that the number of routes is reduced to a prelected level.In the route reduction pro-cedure,there are two sub-steps.Thefirst sub-step is to lect the route with the smallest load,denote the route as R1.The cond sub-step is to reinrt each customer node in R1to another route. To this end,for each customer node in R1,u reinrtion neigh-borhood operator to generate and evaluate possible moves as de-scribed in Section2.2.1,and then the best move in terms of the augmented objective function value is executed.Repeat the two sub-steps until the number of routes reaches the prelected level. The solutions generated in step two are often infeasible regarding either the capacity constraint or the route length constraint.Thus, in step three,an attempt is made to restore the feasibility by a re-pair procedure.The repair procedur
e is a variant of the tabu arch procedure described in Section2.2.1,in which three neighbor-hoods(reinrtion,exchange and2-opt⁄)are ud.To focus restor-ing the feasibility,a special move evaluation and acceptance criterion is ud for reinrtion and exchange neighborhoods.For the two neighborhoods,the neighbors are generated as described in Section2.2.1,but they are evaluated in terms of three parate ,the total travel distance,the capacity constraint viola-tions and the route length constraint violations.Among the avail-able moves,only moves which result in the positive decrea in the total travel distance will be considered.If such moves exist, then the repair procedure checks whether there exist route length constraint violations.If there are route length constraint violations, the move leading to the neighboring solution with the lowest route length constraint violations is executed,otherwi,the move lead-ing to the neighboring solution with the lowest capacity constraint violations is executed.The rationale behind this decision is that the capacity is relatively easier to restore.If such improving moves are not found,no moves will be executed.At each iteration,reinrtion neighborhood is appliedfirst to arch for improving moves.If no such moves can be found,then exchange neighborhood is applied. When neither reinrtion nor exchange neighborhood canfind improving moves,2-opt⁄neighborhood is applied.For this neigh-borhood operator,the moves are evaluated in terms of the aug-mented objective function value and the best non-tabu move will be accepted even though it may increa the total constraint viola-tions.Thefirst pha terminates when solution feasibility is attained.
In the propod algorithm,the number of routes in the solu-tions isfixed during the subquent arch cour after the route reduction procedure.The rationale behind this decision is twofold. First,the number of vehicles is often known beforehand in some VRP contexts.Second,tofix the number of tours facilitates the
家庭主要成员
Table1
The features of each TS thread.
TS thread Neighborhood ud for inter-route Role
Thread1Reinrtion,2-opt⁄Main improving thread Thread22-opt⁄Assistant improving thread Thread3Exchange Assistant improving thread
Thread4Solution perturbation+reinrtion,
2-opt⁄,exchange Diversifying the arch
444J.Jin et al./European Journal of Operational Rearch222(2012)441–451
method to focus on minimizing the total travel distance.For situa-tions,where the number of vehicles is unknown,the propod algorithm is also able tofind solutions with the minimum number of routes by enclosing it in a binary arch in the number of routes. For the CVRP benchmarks tested during computational experi-ments,the minimum route number of each problem reported in the literature is adopted for the sake of simplicity.
3.Several other variants
To evaluate the role of cooperation and to compare the effec-tiveness of using multiple neighborhoods in rial and parallel manner,we have also developed six other four quential variants(denoted as SV1,SV2,SV3and SV4),two paral-lel variants(denoted as PV1and PV2).
The four quential variants are developed by removing the solution pool and three threads from the cond pha of PMNTS. For instance,SV1is developed by removing the solution pool, Thread2,Thread3and Thread4,thus only keeping Thread1at the cond pha.SV2,SV3and SV4are developed analogously by only keeping Thread2,Thread3and Thread4at the cond pha respectively.Thus,in particular,SV4corresponds to a quential TS using all the neighborhoods ud
by the parallel ver-sion.The quential variants have only one thread,run on a sin-gle processor and correspond to each of the four TS threads included in PMNTS respectively.The objective of generating the variants is to evaluate the performance of each simple TS thread in-cluded in the propod algorithm.
Thefirst parallel variant PV1is developed by removing Thread4 and2-opt⁄neighborhood at Thread1from PMNTS.It consists of only three threads in the cond pha and each arch thread uti-lizes a single neighborhood(reinrtion,exchange or2-opt⁄)for in-ter-route moves respectively.The three TS threads cooperate through the solution pool.The solution pool functions exactly the same way as discusd above for PMNTS.The goal of generating this variant is to evaluate the effectiveness of using only one neigh-borhood for inter-route moves in each TS thread and explore the association between the beneficial u of special neighborhoods with test instance characteristics.
The cond parallel variant PV2is developed by replacing the original Thread2and Thread3at the cond pha of PMNTS with clones of Thread1.In the resulting parallel variant,three copies of Thread1cooperate with Thread4through the solution pool.The objective of developing this variant is to evaluate the performance of PMNTS without Thread2and Thread3in which single neighbor-hoods
are ud in a parallel manner.
The variants are tested with a subt of CVRP benchmark in-stances to compare their effectiveness.The results are discusd in Section4.
4.Computational results
In this ction we describe the experimental platform,the test data ts,the algorithm configurations,the experimental results and give some obrvations.
4.1.Experimental platform and implementation issues
The propod algorithm is implemented in C++and Intel Thread-ing Building Blocks(TBB)libraries are ud for parallelization.TBB is a C++template library developed by Intel Corporation for writing software programs that take advantage of multi-core processors. More information about TBB can be found at www.thread-ingbuildingblocks/.The computational experiments are carried out on a computer with2IntelÒXeonÒE54503.00GHZ CPUs(quad-core)and8GB of RAM.A master thread is ud to control the global arch process,launch the four arch threads in pha2and man-age the solution pool.Each arch thread is run on one core.The rest of the available cores are ud by the parallel neighborhood gener-ation and evaluation procedures.
4.2.The test data ts
The computational tests were carried out using the CVRP benchmarks of Golden et al.(1998)and Li et al.(2005).The20 benchmark instances of Golden et al.(1998)have200to483cus-tomers.Thefirst eight instances also have route length restrictions. Each instance is bad on a simple geometric structure:eight in-stances have customers located in concentric circles around the de-pot,four instances have customers located in concentric squares with the depot located in one corner,four instances have custom-ers located in concentric squares around the depot,and four in-stances have customers located in a six-pointed star around the depot.The benchmark instances of Li et al.(2005)have560–1200customers and route length restrictions,and their geometric structure is bad on concentric circles around the depot.For each instance,the algorithm was executed10times with different ran-dom eds and both the best and average results are reported.
4.3.The algorithm configurations
The configurations of PMNTS and the other variants are intro-duced below.
4.3.1.The configurations of PMNTS
The parameters of the propod parallel multi-neighborhood cooperative tabu arch algorithm are shown in Table2.
Here,N reprents the number of customer nodes in the in-stance.Tabu tenure is t to be proportional to N.For example, in Thread1,tabu tenure of reinrtion neighborhood is0.05N while2-opt⁄neighborhood us0.1N.In Thread1,the probability of lecting reinrtion neighborhood is6/7while the probability of lecting2-opt⁄neighborhood is1/7.The size of the nearest neighbors t is calculated as10plus a uniform random number from the interval[0,10]at each iteration in the cond pha.In Thread4,20%of nodes are relocated in the perturbation procedure. As for solution difference,the requirement is that a solution has at least10%percent different edges from the current best solution.In each gment,the running time is controlled by Thread1.After running250
ffiffiffiffi
N
p
iterations,the thread stops,and the other three threads are also terminated.The whole arch termina
tes after 60gments or when there is no improvement for15concutive gments.The values of the parameters are tuned through exten-sive testing on the Problems1,4,5,8,9,12,13,16,17and20of Golden et al.(1998)bad on preliminary computational experi-ments.The instances are lected since they differ in both in-stance size and customer location structure.As an example,Fig.2 shows the impact of the size of nearest neighbors t on the solu-tion quality and time.The solution quality is measured with the average deviation of all instances tested from the best known solu-tions while the time is the average running time of all instances tested in minutes.It is noticeable that larger values cau longer running times but not necessarily better solution quality.The re-sults also show that the solution quality is not so nsitive to the parameter.Among the values tested,10+random[0,10]is chon. The other parameters are calibrated in a similar way.
4.3.2.The configurations of the variants
For the four quential variants,the parameters of thefirst pha remain identical as in PMNTS.At the cond pha,the parameters are t to the same as for the corresponding TS thread,
J.Jin et al./European Journal of Operational Rearch222(2012)441–451445
