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

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.

Share and Cite:

S. Basu, "Tabu Search Implementation on Traveling Salesman Problem and Its Variations: A Literature Survey," American Journal of Operations Research, Vol. 2 No. 2, 2012, pp. 163-173. doi: 10.4236/ajor.2012.22019.

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(nr) 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.

 +1 323-425-8868 customer@scirp.org +86 18163351462(WhatsApp) 1655362766 Paper Publishing WeChat