Tabu Search Implementation on Traveling Salesman Problem and Its Variations: A Literature Survey

Sumanta Basu

Indian Institute of Management Calcutta, Kolkata, India.

DOI: 10.4236/ajor.2012.22019                

Abstract

The Traveling Salesman Problem (TSP) and its allied problems like Vehicle Routing Problem (VRP) are one of the most widely studied problems in combinatorial optimization. It has long been known to be NP-hard and hence research on developing algorithms for the TSP has focused on approximate methods in addition to exact methods. Tabu search is one of the most widely applied metaheuristic for solving the TSP. In this paper, we review the tabu search literature on the TSP and its variations, point out trends in it, and bring out some interesting research gaps in this literature.

Keywords

Tabu Search; Traveling Salesman Problem; Vehicle Routing Problem

1. Introduction

Many managerial problems, like vehicle routing problems, facility location problems, scheduling problems, network design problems, can either be modeled as combinatorial optimization problems, or solve combinatorial optimization problems as sub-problems. A very commonly researched combinatorial optimization problem in this and other contexts is the Traveling Salesman Problem (TSP). In a TSP (see e.g. [1]), we are given a weighted graph with a nodeset V and an arcset A. Cardinality of the nodeset V defines the problem size, i.e. |V| = n, and number of arcs is denoted by |A|. Cost of each arc connecting node i and node j is represented by . Given these input parameters, it is required to find a tour in the graph visiting each node exactly once such that the sum of the costs of the edges or arcs in the tour is the minimum possible. TSPs serve as a representation of many managerial problems, especially in logistics and distribution. Many more problems, though not obviously related to the TSP can be modeled as TSPs. A large number of other problems are not equivalent to solving TSPs, but solve TSPs as subproblems.

Apart from being a recurrent problem in managerial situations, the TSP is among the most widely studied problems in combinatorial optimization. It was one of the first problems whose decision version was shown to be NP-complete (see [2]), and has been a testbed for theoretical and computational studies ever since. Rich classes of benchmark problems exist for the TSP (see e.g., [3,4]), as do efficient implementations for solving reasonably large problems to optimality (see for example, NEOS: http://neos.mcs.anl.gov/neos/solvers/co:concorde/TSP.html).

The TSP is known to be NP-hard. This means that no known algorithm is guaranteed to solve all TSP instances to optimality within reasonable execution time. So in addition to exact solution approaches, a number of heuristics and metaheuristics have been developed to solve problems approximately. Heuristics and metaheuristics trade optimality of the solutions that they output with execution times. They are used to find “good” quality solutions within reasonable execution times. Metaheuristics are normally improvement algorithms, i.e., they start with one or more feasible solutions to the problem at hand and suggest methods for improving such solutions. Typical examples of metaheuristics include local search, tabu search, simulated annealing, and genetic algorithms. The literature shows that tabu search is one of the most widely used metaheuristic procedures to solve combinatorial optimization problems. It is an improvement heuristic based on local search. It starts with an initial solution to the problem, (a tour in case of the TSP), calls it a current solution, and searches for the best solution in a suitably defined neighborhood (a collection of tours that can be “easily” reached from the current solution) of the solution. It then designates the best solution in the neighborhood as the current solution and starts the search process again. Tabu search terminates when certain terminating conditions, either involving execution time or maximum iteration count conditions, or solution quality objectives, or both, have been met. In order to prevent tabu search from considering solutions that it has visited in recent iterations, tabu search maintains a list of neighbor generation moves that it considers forbidden, or tabu (hence the name, tabu search) and ignores solutions that can be reached using those tabu moves while searching the neighborhood of a solution. Once a move enters the list of tabu moves, it stays there for a pre-specified number of tabu search iterations (called the tabu tenure of the move). The list of tabu moves therefore changes continuously during the execution of the search, making tabu search an adaptive memory search algorithm. Several researchers have added features that enrich the basic tabu search algorithm described here, such as intermediate term memory structures, long term memory structures, and aspiration criteria, which have been widely applied to tabu search implementations for most problems in TSP or in VRP. Other features that have been proposed, but not commonly implemented for tabu search on TSPs are strategic oscillation, path relinking, candidate list strategies etc.

In this paper, we review the literature on application of tabu search to TSPs and problems very closely related to it, like vehicle routing problem and its variations. We reviewed 76 papers on the application of tabu search to these problems. The papers that we reviewed mostly appeared in print in the last twenty years. We classify the literature based on problem size (Section 2), generation of initial solutions (Section 3), selection of moves (Section 4), the choice of short, medium, and long term memory structures (Section 5 through Section 7), and aspiration criteria (Section 8). We summarize our findings in Section 9.

2. Problem Size

60 papers describe the problem context on TSPs and on VRPs where tabu search was implemented. Table 1 provides a summary of the problem sizes considered by different authors in the literature. For TSP, problem size is defined as number of nodes to be visited and for VRP, problem size is considered as number of customers (or demand nodes) to be covered. It is interesting to note that even though metaheuristics are meant to handle large problems, nearly half of the papers deal only with problem sizes up to 100 nodes. There are only 11 papers which address problem sizes of more than 400 nodes. Only three papers (e.g. [5-7]) address problem sizes between 500 and 1035 nodes. With the advent of more powerful computers one would expect recent papers to deal with larger problems. However, as is evident from Table 1, this trend is not observed in published literature. For example, in the last three years, we have not encountered a single paper that implements tabu search on TSPs with more than 400 nodes.

3. Initial Solution Generation

Initial solution plays a vital role in finding out a good solution using local search based metaheuristic like tabu search. We have identified various methodologies used to generate initial solutions and have categorized papers in published literature using those methodologies in Table 2. To keep number of categories manageable, we have ignored minor customizations used to generate initial solutions in some papers while putting it into a category.

General Randomized Adaptive Search Process (GRASP) is a modification of a greedy tour construction heuristic. In a greedy heuristic, a tour is constructed by growing a path in the graph and joining the end points once the path includes all the nodes in the graph. The first point is randomly chosen, and the node closest to the endpoints of the path being formed is the next point to be added to the path. In a GRASP heuristic, the point that is added to the path being grown is not necessarily the closest one to the endpoints, but a random one chosen from a set of points that are close enough to the endpoints of the existing path.

Route First Cluster Second (RFCS) algorithm is used specifically in the context of VRP. Initially a giant tour is constructed by relaxing the vehicle capacity constraint as done in TSP. Then clusters are formed by breaking the giant tour into smaller tours which satisfy constraints specific to VRP, e.g. time window, capacity

Table 1. Problem sizes considered in published literature.

Table 2. Methods to generate initial solutions.

constraints etc.

Cluster First Route Second (CFRS) Algorithm is used in the context of VRP for initial allocation of customers to vehicles. In this algorithm, a set of nodes are identified to form a cluster by meeting VRP constraints. Then a feasible tour is constructed by visiting each of those nodes in a single cluster.

Randomized Insertion (RandIns) starts with a partial tour and inserts nodes randomly into tour without forming sub-tours in between. It stops when all nodes in the graph have been included in the tour.

Nearest Neighbor (NN) also starts with a partial tour. It then searches for a node not included in the partial tour and has the minimum distance from the last added node in the partial tour. It adds this node to the partial tour. If the graph describing the TSP is not complete, there is a possibility that after the completion of this procedure, some of the nodes remain unconnected to the tour. These nodes are then added to the tour using the RandIns procedure (by not forming sub-tours in between). In some papers, e.g. [6], authors implement minor variations of this method like double ended nearest neighbor etc.

Sweep heuristic is suited for TSPs defined on a plane. A reference point is chosen and an arbitrary axis is drawn through the reference point. Next the vertices are arranged in increasing order of angle between the line linking the vertex to the reference point and the axis defined. Ties are generally broken by choosing the vertex having the smallest distance to the reference point. Multiple reference points are used for multiple depots in the context of VRP.

Clarke and Wright (C & W) heuristic is widely used in the context of VRP (see [63]). It is based on the notion of savings. Initially routes are created to connect depot and customers. Those routes are then merged based on maximum savings possible in the parallel version of the algorithm. In the sequential version of the algorithm, the same route keeps expanding until no feasible route is possible.

We summarize our findings in usage of methods to generate initial solutions in Table 2. We can see that the two most popular methods are Randomized Insertion (RandsIn) and Nearest Neighbor (NN). Ease in implementation is a reason behind wide selection of those moves in published literature. Sweep and C & W heuristics are also used specifically in the context of VRP.

4. Moves

Tabu search being an improvement heuristic moves from one solution to the next in search of an optimal solution. The method of moving from one solution to another is described by a set of rules and is called a move. The set of all solutions that can be reached from a given solution using a pre-specified move is called the neighborhood of the solution. Out of the papers we reviewed, we found 98 instances of move description with multiple moves being discussed in some papers. One paper that emphasizes the influence of the choice of moves on the solution generated is by Osman ([37]), although it deals only with VRPs. The following types of moves have been used in the literature in the context of TSP and related problems. Again while putting the instances under a move category, we ignored the minor deviations from standard moves in some papers for problem specific implementation. The detailed paperwise summary is given in Table 3.

2-opt move involves removal of two non-adjacent edges from an existing tour and two new edges are inserted by connecting the head and tail nodes of the deleted edges to create a new tour without creating subtours. While performing this move in an asymmetric graph, an additional operation is required to reverse the intermediate arc chain and it increases the computational complexity. A minor variation of this move is used in the context of VRP which is denoted by 2-opt* move in Table 3.

r-opt move is a generalization of the 2-opt move where r > 2 edges are involved in deletion/addition operation. Computational complexity of an r-opt move is O(n^r) in a symmetric graph where n is the problem size.

Table 3. Types of moves used in tabu search.

Hence mostly 3-opt or 4-opt moves are used in local search. It is practically infeasible to generate a neighborhood with r > 4 because it needs large computational time.

Or-opt move is a modification of the r-opt move. It was proposed by Or in 1976 (see [1] for details). It considers a small fraction of exchanges that would be considered by a regular r-opt move. In this move, due to computational convenience, only those exchanges are considered that would result in a string of up to three currently adjacent cities being inserted between two other cities.

Cross Exchange (CrossEx) is an advancement of 2-opt* move specifically used in VRP. Two edges are deleted from two different tours and the open nodes from each tour are connected to each other.

Vertex Insertion (VertexIns) consists of a move where a random vertex is chosen to remove from an existing tour and it is inserted between two other vertices to create a new neighboring tour.

Vertex Exchange (VertexEx) is a move where the positions of two vertices are interchanged to create a new tour from the existing one. In case of TSP, the vertices are exchanged in the same tour. In the context of VRP, vertices chosen can be from different tours as well.

Generalized Insertion (GENI) is a move introduced by Gendreau et al. ([66]). This move performs insertions of unrouted customers or removals of customers from their current routes and their reinsertions into different routes. In this move, one unrouted vertex is chosen, and is joined to two p-closest vertices (and not necessarily adjacent also) with p defined by a threshold distance. The nodes displaced from the route due to this operation are introduced at appropriate positions to complete the route.

λ-Interchange (λ-InterCh) is a move suggested by Osman ([37]), it works in the same principle as vertex exchange in a reduced neighborhood; only λ of the nearest nodes from a given node are considered for interchange.

Table 3 summarizes the choice of moves in published literature over time. It can easily be seen that the three frequently used moves are 2-opt, vertex insertion and vertex exchange. These moves are the easiest to implement among all the moves considered. They result in neighborhoods whose sizes are quadratic in the number of nodes in the TSP. Moves that result in larger neighborhoods often provide more improvement in each tabu search iteration, but searching them takes longer. For example, r-opt or GENI tends to produce a better solution in each iteration but in expense of higher computational time.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	E. Lawler, J. lenstra, K. Rinnooy and D. Shmoys, “The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization,” Wiley-Interscience Publication, 1985.
[2]	R. Karp, “Reducibility among Combinatorial Problems,” Plenum Press, New York, 1972, pp. 85-103.
[3]	D. Johnson, G. Gutin, L. McGeoch, A. Yeo, W. Zhang and A. Zverovich, “The Traveling Salesman Problem and Its Variations,” Kluwer Academic Publishers, Boston, 2002.
[4]	G. Reinelt, “TSPLIB—A Traveling Salesman Problem Library,” INFORMS Journal of Computing, Vol. 3, 1991, pp. 376-384. doi:10.1287/ijoc.3.4.376
[5]	J. Cordeau, G. Laporte and A. Mercier, “A Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows,” The Journal of the Operational Research Society, Vol. 52, No. 8, 2001, pp. 928-936. doi:10.1057/palgrave.jors.2601163
[6]	A. Bouthillier and T. Crainic, “A Cooperative Parallel Meta-Heuristic for the Vehicle Routing Problem with Time Windows,” Computers & Operations Research, Vol. 32, No. 7, 2005, pp. 1685-1708. doi:10.1016/j.cor.2003.11.023
[7]	J. Homberger and H. Gehring, “A Two-Phase Hybrid Metaheuristic for the Vehicle Routing Problem with Time Windows,” European Journal of Operational Research, Vol. 162, No. 1, 2005, pp. 220-238. doi:10.1016/j.ejor.2004.01.027
[8]	M. Malek, M. Guruswamy, M. Pandya and H. Owens, “Serial and Parallel Simulated Annealing and Tabu Search Algorithms for the Traveling Salesman Problem,” Annals of Operations Research, Vol. 21, No. 1, 1989, pp. 59-84. doi:10.1007/BF02022093
[9]	F. Semet and E. Taillard, “Solving Real-Life Vehicle Routing Problems Efficiently Using Taboo Search,” Annals of Operations Research, Vol. 41, 1993, pp. 469-488. doi:10.1007/BF02023006
[10]	B. Garcia, J. Potvin and J. Rousseau, “A Parallel Implementation of the Tabu Search Heuristic for Vehicle Routing Problems with Time Window Constraints,” Computers & Operations Research, Vol. 21, No. 9, 1994, pp. 1025-1033. doi:10.1016/0305-0548(94)90073-6
[11]	M. Gendreau, G. Laporte and R. Séguin, “A Tabu Search Heuristic for the Vehicle Routing Problem with Stochastic Demands and Customers,” Operations Research, Vol. 44, No. 3, 1996, pp. 469-477. doi:10.1287/opre.44.3.469
[12]	P. Badeau, M. Gendreau, F. Guertin, J.-Y. Potvin and E. Taillard, “A Parallel Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows,” Transportation Research, Vol. 5, 1997, pp. 109-122. doi:10.1016/S0968-090X(97)00005-3
[13]	J. Brand?o and A. Mercer, “A Tabu Search Algorithm for the Multi-Trip Vehicle Routing and Scheduling Problem,” European Journal of Operational Research, Vol. 100, No. 1, 1997, pp. 180-191. doi:10.1016/S0377-2217(97)00010-6
[14]	O. Br?ysy and M. Gendreau, “Tabu Search Heuristics for the Vehicle Routing Problem with Time Windows,” Technical Report, SINTEF Applied Mathematics, Department of Optimisation, Oslo, 2001.
[15]	P. Caricato, G. Ghiani, A. Grieco and E. Guerriero, “Parallel Tabu Search for a Pickup and Delivery Problem Under Track Contention,” Parallel Computing, Vol. 29, No. 5, 2003, pp. 631-639. doi:10.1016/S0167-8191(03)00046-2
[16]	H. Lau, M. Sim and K. Teo, “Vehicle Routing Problem with Time Windows and a Limited Number of Vehicles,” European Journal of Operational Research, Vol. 148, No. 3, 2003, pp. 559-569. doi:10.1016/S0377-2217(02)00363-6
[17]	C. Lin and R. Kwok, “Multi-Objective Metaheuristics for a Location-Routing Problem with Multiple Use of Vehicles on Real Data and Simulated Data,” European Journal of Operational Research, Vol. 175, No. 3, 2006, pp. 1833-1849.
[18]	N. Bianchessi and G. Righini, “Heuristic Algorithms for the Vehicle Routing Problem With Simultaneous Pick-Up and Delivery,” Computers & Operations Research, Vol. 34, No. 2, 2007, pp. 578-594. doi:10.1016/j.cor.2005.03.014
[19]	J. Brand?o, “A Deterministic Tabu Search Algorithm For the Fleet Size and Mix Vehicle Routing Problem” European Journal of Operational Research, Vol. 195, 2009, pp. 716-728. doi:10.1016/j.ejor.2007.05.059
[20]	J. Potvin, T. Kervahut, B. Garcia and J. Rousseau, “The Vehicle Routing Problem with Time Windows—Part I: Tabu Search,” INFORMS Journal of Computing, Vol. 8, 1996, pp. 158-164. doi:10.1287/ijoc.8.2.158
[21]	Y. Sharaiha, M. Gendreau, G. Laporte and I. Osman, “A Tabu Search Algorithm for the Capacitated Shortest Spanning Tree Problem,” Networks, Vol. 29, 1997, pp. 209- 223. doi:10.1002/(SICI)1097-0037(199705)29:3<161::AID-NET4>3.0.CO;2-F
[22]	W. Chiang and R. Russell, “A Reactive Tabu Search Metaheuristic for the Vehicle Routing Problem with Time Windows,” INFORMS Journal of Computing, Vol. 9, 1997, pp. 417-430. doi:10.1287/ijoc.9.4.417
[23]	S. Ho and D. Haugland, “A Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows and Split Deliveries,” Computers & Operations Research, Vol. 31, No. 12, 2004, pp. 1947-1964. doi:10.1016/S0305-0548(03)00155-2
[24]	H. Tang and E. Hooks, “A TABU Search Heuristic for the Team Orienteering Problem,” Computers & Operations Research, Vol. 32, No. 6, 2005, pp. 1379-1407. doi:10.1016/j.cor.2003.11.008
[25]	M. Bolduc, G. Laporte, J. Renaud and F. Boctor, “A Tabu Search Heuristic for the Split Delivery Vehicle Routing Problem with Production and Demand Calendars,” European Journal of Operational Research, Vol. 202, 2010, pp. 122-130. doi:10.1016/j.ejor.2009.05.008
[26]	A. Amberg, W. Domschke and S. Vob, “Multiple Center Capacitated Arc Routing Problems: A Tabu Search Algorithm Using Capacitated Trees,” European Journal of Operational Research, Vol. 124, No. 2, 2000, pp. 360- 376.
[27]	A. Hertz, G. Laporte and M. Mittaz, “A Tabu Search Heuristic for the Capacitated Arc Routing Problem,” Operations Research, Vol. 48, No. 1, 2000, pp. 129-135. doi:10.1287/opre.48.1.129.12455
[28]	W. Nanry and J. Barnes, “Solving the Pickup and Delivery Problem with Time Windows Using Reactive Tabu Search,” Transportation Research Part B: Methodological, Vol. 34, No. 2, 2000, pp. 107-121. doi:10.1016/S0191-2615(99)00016-8
[29]	S. Tsubakitani and J. Evans, “Optimizing Tabu List Size for the Traveling Salesman Problem,” Computers & Operations Research, Vol. 25, No. 2, 1998, pp. 91-97. doi:10.1016/S0305-0548(97)00030-0
[30]	R. Daniels, J. Rummel and R. Schantz, “A Model for Warehouse Order Picking,” European Journal of Operational Research, Vol. 105, No. 1, 1998, pp. 1-17. doi:10.1016/S0377-2217(97)00043-X
[31]	P. Franca, N. Sosa and V. Pureza, “An Adaptive Tabu Search Algorithm for the Capacitated Clustering Problem,” International Transactions in Operations Research, Vol. 6, 1999, pp. 665-678.
[32]	P. Augerat, J. M. Belenguer, E. Benavent, A. Corberán and D. Naddef, “Separating Capacity Constraints in the CVRP Using Tabu Search,” European Journal of Operational Research, Vol. 106, No. 2-3, 1998, pp. 546-557. doi:10.1016/S0377-2217(97)00290-7
[33]	I. Chao, “A Tabu Search Method for the Truck and Trailer Routing Problem,” Computers & Operations Research, Vol. 29, No. 1, 2002, pp. 33-51. doi:10.1016/S0305-0548(00)00056-3
[34]	J. Cordeau and G. Laporte, “A Tabu Search Heuristic for the Static Multi-Vehicle Dial-a-Ride Problem,” Transportation Research Part B: Methodological, Vol. 37, No. 6, 2003, pp. 579-594. doi:10.1016/S0191-2615(02)00045-0
[35]	S. Scheuerer, “A Tabu Search Heuristic for the Truck and Trailer Routing Problem,” Computers & Operations Research, Vol. 33, No. 4, 2006, pp. 894-909. doi:10.1016/j.cor.2004.08.002
[36]	M. Gendreau, A. Hertz and G. Laporte, “A Tabu Search Heuristic for the Vehicle Routing Problem,” Management Science, Vol. 40, No. 10, 1994, pp. 1276-1290. doi:10.1287/mnsc.40.10.1276
[37]	I. Osman, “Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem,” Annals of Operations Research, Vol. 41, 1993, pp. 421- 451. doi:10.1007/BF02023004
[38]	Y. Rochat and F. Semet, “A Tabu Search Approach for Delivering Pet Food and Flour in Switzerland,” The Journal of the Operational Research Society, Vol. 45, No. 11, 1994, pp. 1233-1246.
[39]	J. Brand?o and A. Mercer, “The Multi-Trip Vehicle Routing Problem,” The Journal of the Operational Research Society, Vol. 49, No. 8, 1998, pp. 799-805.
[40]	G. Barbarosoglu and D. Ozgur, “A Tabu Search Algorithm for the Vehicle Routing Problem,” Computers and Operations Research, Vol. 26, No. 3, 1999, pp. 255-270. doi:10.1016/S0305-0548(98)00047-1
[41]	D. Tuzun and L. Burke, “A Two-Phase Tabu Search Approach to the Location Routing Problem,” European Journal of Operational Research, Vol. 116, 1999, pp. 87- 99. doi:10.1016/S0377-2217(98)00107-6
[42]	D. Ahr and G. Reinelt, “A Tabu search Algorithm for the Min-Max k-Chinese Postman Problem,” Computers & Operations Research, Vol. 33, No. 12, 2006, pp. 3403- 3422. doi:10.1016/j.cor.2005.02.011
[43]	T. G. Crainic, M. Gendreau, P. Soriano and M. Toulouse, “A Tabu Search Procedure for Multicommodity Location/Allocation with Balancing Requirements,” Annals of Operations Research, Vol. 41, 1993, pp. 359-383. doi:10.1007/BF02023001
[44]	B. Crevier, J. Cordeau and G. Laporte, “The Multi-Depot Vehicle Routing Problem with Inter-Depot Routes,” European Journal of Operational Research, Vol. 176, No. 2, 2007, pp. 756-773. doi:10.1016/j.ejor.2005.08.015
[45]	E. Zachariadis, C. Tarantilis and C. Kiranoudis, “A Guided Tabu Search for the Vehicle Routing Problem with Two-Dimensional Loading Constraints,” European Journal of Operational Research, Vol. 195, 2009, pp. 729-743. doi:10.1016/j.ejor.2007.05.058
[46]	M. Gendreau, G. Laporte and F. Semet, “A Tabu Search Heuristic for the Undirected Selective Travelling Salesman Problem,” European Journal of Operational Research, Vol. 106, 1998, pp. 539-545. doi:10.1016/S0377-2217(97)00289-0
[47]	M. Gendreau, G. Laporte and D. Vigo, “Heuristics for the Traveling Salesman Problem with Pickup and Delivery,” Computers & Operations Research, Vol. 26, No. 7, 1999, pp. 699-714. doi:10.1016/S0305-0548(98)00085-9
[48]	M. Gendreau, M. Iori, G. Laporte and S. Martello, “A Tabu Search Heuristic for the Vehicle Routing Problem with Two-Dimensional Loading Constraints,” Networks, Vol. 51, No. 1, 2008, pp. 4-18. doi:10.1002/net.20192
[49]	N. A. Wassan, A. Wassan and G. Nagy, “A Reactive Tabu Search Algorithm for the Vehicle Routing Problem with Simultaneous Pickups and Deliveries,” Journal of Combinatorial Optimization, Vol. 15, 2008, pp. 368-386. doi:10.1007/s10878-007-9090-4
[50]	H. Tamashiro, M. Nakamura, T. Okazaki and D. Kang, “A Tabu Search Approach Combined with an Extended Saving Method for Multi-Depot Vehicle Routing Problems with Time Windows,” Biomedical Soft Computing and Human Sciences, Vol. 15, No. 1, 2010, pp. 31-39.
[51]	J. Cordeau and M. Maischberger, “A Parallel Iterated Tabu Search Heuristic for Vehicle Routing Problems,” Computers & Operations Research, Vol. 39, 2012, pp. 2033-2050. doi:10.1016/j.cor.2011.09.021
[52]	J. Renaud, G. Laporte and F. Boctor, “A Tabu Search Heuristic for the Multi-Depot Vehicle Routing Problem,” Computers & Operations Research, Vol. 23, 1996, pp. 229-235. doi:10.1016/0305-0548(95)O0026-P
[53]	F. Montane and R. Galvao, “A Tabu Search Algorithm for the Vehicle Routing Problem with Simultaneous Pick- Up and Delivery Service,” Computers & Operations Research, Vol. 33, No. 3, 2006, pp. 595-619. doi:10.1016/j.cor.2004.07.009
[54]	J. Brand?o, “A Tabu Search Algorithm for the Heterogeneous Fixed Fleet Vehicle Routing Problem,” Computers & Operations Research, Vol. 38, 2011, pp. 140-151. doi:10.1016/j.cor.2010.04.008
[55]	S. Thangiah, I. Osman and T. Sun, “Hybrid Genetic Algorithm, Simulated Annealing and Tabu Search Methods for Vehicle Routing Problem with Time Windows,” Technical Report, Computer Science Department, Slippery Rock University, 1994.
[56]	Y. Rochat and E. Taillard, “Probabilistic Diversification and Intensification in Local Search for Vehicle Routing,” Journal of Heuristics, Vol. 1, 1995, pp. 147-167. doi:10.1007/BF02430370
[57]	V. E. Taillard, P. Badeau, M. Gendreau, F. Guertin, and J.-Y. Potvin, “A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows,” Transportation Science, Vol. 31, No. 2, 1997, pp. 170-186. doi:10.1287/trsc.31.2.170
[58]	J. Cordeau, M. Gendreau and G. Laporte, “A Tabu Search Heuristic for Periodic and Multi-Depot Vehicle Routing Problems,” Networks, Vol. 30, No. 2, 1998, pp. 105-119. doi:10.1002/(SICI)1097-0037(199709)30:2<105::AID-NET5>3.0.CO;2-G
[59]	P. Toth and D. Vigo, “The Granular Tabu Search and Its Application to the VRP,” Technical Report, University of Bologna, 1998.
[60]	E. Zachariadis, C. Tarantilis and C. Kiranoudis, “A Guided Tabu Search for the Vehicle Routing Problem with Two-Dimensional Loading Constraints,” European Journal of Operational Research, Vol. 195, 2009, pp. 729-743. doi:10.1016/j.ejor.2007.05.058
[61]	J. C?té and J.-Y. Potvin, “A Tabu Search Heuristic for the Vehicle Routing Problem with Private Fleet and Common Carrier,” European Journal of Operational Research, Vol. 198, 2009, pp. 464-469. doi:10.1016/j.ejor.2008.09.009
[62]	C. Tarantilis, “Solving The Vehicle Routing Problem with Adaptive Memory Programming Methodology,” Computers & Operations Research, Vol. 32, No. 9, 2005, pp. 2309-2327. doi:10.1016/j.cor.2004.03.005
[63]	G. Clarke and J. Wright, “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Operations Research, Vol. 12, 1964, pp. 568-581. doi:10.1287/opre.12.4.568
[64]	J. Shen, F. Xu and P. Zheng, “A Tabu Search Algorithm for the Routing and Capacity Assignment Problem in Computer Networks,” Computers & Operations Research, Vol. 32, No. 11, 2005, pp. 2785-2800. doi:10.1016/j.cor.2004.04.004
[65]	A. Breedam, “Comparing Descent Heuristics and Metaheuristics for the Vehicle Routing Problem,” Computers & Operations Research, Vol. 24, No. 4, 2001, pp. 289- 315. doi:10.1016/S0305-0548(99)00101-X
[66]	M. Gendreau, A. Hertz and G. Laporte, “New Insertion and Post Optimization Procedures for the Traveling Salesman Problem,” Operations Research, Vol. 40, No. 6, 1992, pp. 1086-1094. doi:10.1287/opre.40.6.1086
[67]	X. Fan, N. Li, B. Zhang and Z. Liu, “Research on Vehicle Routing Problem with Soft Time Windows Based on Tabu Search Algorithm,” IEEE 18th International Conference, 3-5 September 2011.
[68]	D. Paraskevopoulos, P. Repoussis, C. Tarantilis, G. Ioannou and G. Prastacos, “A Reactive Variable Neighborhood Tabu Search for the Heterogeneous Fleet Vehicle Routing Problem with Time Windows,” Journal of Heuristics, Vol. 14, 2008, pp. 425-455. doi:10.1007/s10732-007-9045-z
[69]	L. Moccia, J. Cordeau and G. Laporte, “An Incremental Tabu Search Heuristic for the Generalized Vehicle Routing Problem with Time Windows,” Journal of the Operational Research Society, Vol. 63, 2012, pp. 232-244. doi:10.1057/jors.2011.25
[70]	T. Wu, C. Low and J. Bai, “Heuristic Solutions to Multi- Depot Location-Routing Problems,” Computers & Operations Research, Vol. 29, No. 10, 2002, pp. 1393-1415. doi:10.1016/S0305-0548(01)00038-7
[71]	C. Ting, S. Li and C. Lee, “On the Harmonious Mating Strategy through Tabu Search,” Information Sciences, Vol. 156, No. 3-4, 2003, pp. 189-214. doi:10.1016/S0020-0255(03)00176-2
[72]	P. Greistorfer, “A Tabu Scatter Search Metaheuristic for the Arc Routing Problem,” Computers and Industrial Engineering, Vol. 44, No. 2, 2003, pp. 249-266. doi:10.1016/S0360-8352(02)00178-X
[73]	R. Russell and W. Chiang, “Scatter Search for the Vehicle Routing Problem with Time Windows,” European Journal of Operational Research, Vol. 169, No. 2, 2006, pp. 606-622. doi:10.1016/j.ejor.2004.08.018
[74]	E. Taillard, “Robust Taboo Search for the Quadratic Assignment Problem,” Parallel Computing, Vol. 17, 1991, pp. 433-445. doi:10.1016/S0167-8191(05)80147-4
[75]	F. Glover, M. Laguna and C. Reeves, “Tabu Search,” In: C. Reeves, Ed., Modern Heuristic Techniques for Combinatorial Problems, Blackwell Scientific Publications, Oxford, 1993.
[76]	J. Crino, J. Moore, J. W. Barnes and W. Nanry, “Solving the Theater Distribution Vehicle Routing and Scheduling Problem Using Group Theoretic Tabu Search,” Mathematical and Computer Modelling, Vol. 139, No. 6-8, 2004, pp. 599-616. doi:10.1016/S0895-7177(04)90543-2