For the Traveling Salesman Problem
MULTILEVEL TABU SEARCH AND EMBEDDED SEARCH NEIGHBORHOODS
FOR THE TRAVELING SALESMAN PROBLEM
by
Fred Glover
U S West Chair in Systems Science
Graduate School of Business, Box 419
University of Colorado
Boulder, Colorado 80309—0419
June 1991
ABSTRACT
We present a tabu search procedure for traveling salesman problems that can be implemented at a variety of levels, exploiting tradeoffs between ease of implementation and sophistication of search. A principal contribution of the paper is a new embedded neighborhood structure based on the idea of ejection chains. These neighborhoods exhibit a special property called combinatorial leverage, where for small values of k, a level k neighborhood contains 0(nk+l) elements, but a best member can be determined with k examinations of 0(n2) “component” elements. In addition, accelerated constructions are given that yield a significant reduction in the number of elements examined and allow convenient exploration of higher levels, with heuristic advantages. Finally, we provide extensions to vehicle routing and quadratic assignment problems which show how these ideas can be applied in other settings.
1.Introduction
This paper gives a tabu search procedure for the symmetric and asymmetric traveling salesman problem (TSP) based on alternative types of search neighborhoods, ranging from simple to more advanced. Correspondingly, the method can be implemented at a variety of levels, to establish different tradeoffs between simplicity of programming and sophistication of search. At a basic level, the method draws on ideas that have proved useful in solving single machine scheduling problems (Glover and Laguna, 1990), including the integration of memory structures to respond adaptively to different states of search. In addition, the method includes several useful components: (1) coordinated move evaluation and selection, enabling moves of different types to be chosen more flexibly than in customary hierarchies; (2) preferred attribute candidate lists to establish improved trade—offs between the number and quality of moves examined at each iteration; (3) a displaced link definition of tabu status, with associated aspiration criteria.
A key contribution of this paper is the introduction of embedded neighborhood structures for defining moves, based on the notion of ejection chains. Such neighborhoods provide the foundation for more advanced levels of the method, and are designed to produce moves of greater power with an efficient investment of effort. We describe a move generation process that provides a combinatorial leverage effect, where the size of the neighborhood grows multiplicatively while the effort of finding a best move in the neighborhood grows only additively. We also provide accelerated methods for generating moves that characteristically produce moves of greater depth (i.e., that encompass a greater number of embedded levels)
Although oriented toward the traveling salesman problem, the ideas of this paper can also be adapted to a variety of other contexts. We sketch extensions to vehicle routing and quadratic assignment problems that demonstrate the basic considerations relevant to such adaptations.
2.Problem Definition and Notation
The directed (asymmetric) form of the TSP may be defined as that of finding a minimum length directed Hamiltonian tour on a graph G = (N,A), where N = {1,...,n) denotes the set of nodes, and where c(i,j) denotes the length (cost) of arc (i,j) in A. We define the forward star and reverse star of a node i respectively to be the set of arcs (i,j) out of node i and the set of arcs (j,i) into node i. (Sometimes we refer to the nodes j of these arcs as elements of the corresponding forward or reverse star.) The union of the forward and reverse stars is called the star of the node.
In the symmetric form of the problem c(i,j) = c(j,i), allowing the elements of A to be treated as undirected, where the pair (i,j) is the same as the pair (j,i). In this case the forward and reverse stars of a node are indistinguishable, both equal to the star.
For the following development we assume a starting tour is given, and is recorded by identifying the (immediate) predecessor and successor of each node i, which we denote respectively by i’ and i”. In the case of the undirected problem, an arbitrary orientation (clockwise or counterclockwise) is assigned to the tour. Subsequently we identify procedures for creating good initial tours based on the ejection chain approaches.
3.Simple Neighborhood Structures for Defining Moves
As a prelude to identifying more advanced neighborhood structures defined later, we consider the customary types of moves found useful in machine scheduling:
(1) insert moves: a selected node i is inserted between two nodes and p and q of an arc (p,q) of the tour. Thus, the predecessor i’ and successor i” of node i are re—linked so that H becomes the new predecessor of i”, while node i becomes identified as the new successor p” of p and the new predecessor q’ of q.
(2) exchange moves: two nodes i and j exchange positions. Thus, i’ and i” become the new predecessor and successor of node j, and similarly j’ and j” become the predecessor and successor of node i. An exception occurs if (i,j) is an arc of the tour, in which case the move is equivalent to inserting i after j (or inserting j before i), and the predecessor and successor updates are given accordingly.
In sparse graphs some insert and exchange moves may not exist for certain identities of nodes i,j and the tour arc (p,q) We allow an artificial arc (with a large cost) to be introduced where necessary so that prospective moves are well defined.
Restricted multi—node insert and exchange moves may be included as a first level extension of these simple neighborhood structures. We will restrict attention to inserts and exchanges that transfer blocks of at most two nodes at a time, relying on the special compounding effects of other elements of the method to create more complex alternatives.
To provide alternatives for implementation at several levels, we describe efficient procedures for executing update and evaluation operations in appendices at the end of the paper. In particular, methods to co—ordinate the process of selecting among one—node and two—node moves are provided in Appendix A.
4.Candidate Lists
Candidate lists occupy an important practical role in tabu search by balancing computational efficiency against the goal of obtaining a highest evaluation move, subject to satisfying associated tabu restrictions.
A complete evaluation of insert and exchange moves in dense traveling salesmen problems requires 0(n2) effort. This effort can be notably reduced by two standard types of candidate lists. The first limits candidate moves to the subset in which no node is moved more than k nodes away from its current position in the tour on any given iteration (e.g., for k = 10 to 20). The second more restrictively decomposes the tour into segments (whose boundaries periodically shift) and restricts attention to moves that occur only within given segments. Both approaches have merit (see, for example, Fiechter (1990) and Laguna et al (1989)). However, in this paper we will primarily focus on an alternative construction which we call a preferred attribute candidate list.
A number of studies have observed that optimal or near optimal solutions often can be constructed for traveling salesman problems by limiting consideration to a small number of shortest arcs out of each node (usually from 5 to 20, depending on the problem size) . At the same time, there are problems where the best solutions significantly violate this restriction, as exemplified by the situation where cities on a Euclidean plane occur in separated clusters. Consequently, more intelligent approaches, such as those used by Gendreau, Hertz and Laporte (1990) and by Johnson (1990), create moves by requiring some but not all arcs to belong to a “shortest arc” collection.
We conjecture that the success of these more refined approaches in solving hard problems (where nodes are not uniformly diffused but may clump and cluster) will depend in part on their amplification factor, which is the ratio of the total number of arcs added by a move to the number that belong to the “k shortest” category. The approaches cited allow only one arc to be excluded from this category. In the first of these approaches, the amplification factor ranges from 1.5 to 1.25, and in the second begins at 2 (for the simplest moves) and becomes progressively closer to 1 as the complexity of moves increases. (A factor of 1 indicates no amplification occurs.) By contrast we organize the use of shortest arcs to achieve amplification factors that always exceed 2, regardless of the move complexity. In the simplest cases the factors range from 3 to 4.
The generation of moves by reference to subsets of shortest arcs constitutes an application of what we call a preferred attribute candidate list (Glover, 1990) . In this instance, the k shortest arcs out of (and into) each node i identify the “preferred attributes” used to control the construction of moves. We first define the way we intend to use these attributes and then identify the rules and data structures for handling them efficiently.
The preferred attribute candidate lists we propose for simple insert and exchange moves compel only a single arc, from the set of arcs involved in a move, to belong to a preferred class. The logical conditions defining such a candidate list in the present context are easy to specify. For an insert move, where a selected node i is repositioned to lie between nodes p and q, we require one of the two added arcs (p,i) or (i,q) to be among the k shortest arcs into or (respectively) out of node i. Since three arcs are added by the move (including the arc joining i’ to i”), this single—arc requirement gives an amplification factor of 3. (More than one of the three added arcs may belong to the “k shortest” category, but only one is compelled to do so.) Given node i, the form of the insert move is completely determined once either the arc (p,i) or (i,q) is specified.
Similarly, for exchange moves, where nodes i and j interchange positions, we require only one of the four added arcs ((i’,j), (j’,i), (i, j”), (j,i”)) to belong to the “k shortest” group, yielding an amplification factor of 4. Here, a given added arc can be used to define two different moves.
The features attending these two cases are characteristic of those exhibited by a preferred attribute candidate lists more generally: (1) each attribute (or attribute set) on the list exhibits a property expected to be found in good solutions; (2) the set of current moves containing the attribute is relatively small and easily generated from knowledge of the attribute; (3) the full collection of solutions that can be generated by iteratively exploiting the condition (2) is “rich”, and contains attributes not restricted to the preferred category.
We might stipulate a further condition as a desirable addition to the preceding three, which is that a procedure can be devised to manage the candidate list efficiently. The next two subsections address this issue.
4.1Candidate List Structure and Organization.
The preferred attribute candidate lists for the present setting are constructed more precisely as follows. Select a small value of k (e.g., k = 4 to 15) and define the preferred forward (reverse) star of a given node i to consist of the k shortest arcs (i,j) out of node i (respectively, the k shortest arcs (j,i) into node i) . (For symmetric problems, the preferred forward and reverse stars are replaced by a single preferred star.) Define an arc to be a preferred arc if it lies in either a preferred forward or reverse star. Finally, expand the membership of the preferred forward and reverse stars so that the preferred forward (reverse) star for each node includes all preferred arcs out of (into) the node.
For directed problems, the set of preferred arcs is thus the same as the union either of all preferred forward stars or all preferred reverse stars, and each preferred arc lies in one preferred forward star and in one preferred reverse star. For undirected problems, the preferred stars may be subdivided into pseudo forward and reverse components to permit these same relationships to hold (as a convenience for certain updating operations, where it is desired to process the set of all preferred arcs (edges) without double counting). These constructions provide a foundation for identifying the moves derived from the preferred attribute candidate lists in a straightforward manner.
Consider first the case of insert moves. Each preferred arc (i,j) then generates two candidate moves, the first inserting i between j’ and j, and the second inserting j between i and i”, excluding the case where (i,j) is an arc of the tour. For the undirected problem, the undirected preferred edge (i,j) generates two insert moves in addition to those indicated, the first inserting i between j and j”, and the second inserting j between i’ and i.
Two—node insert moves are generated for the directed case by inserting the pair (i’,i) between j’ and j, and inserting the pair (j,j”) between i and i”, again excluding cases where node identities overlap. The undirected problem generates two additional insert moves, involving the pairs (i’,i) and (j,j”), and inverts the order of these pairs as a result of the insert operation.
The preferred attribute candidate list for exchange moves is similarly constructed. Each preferred arc (i,j) generates two candidate exchange moves, the first exchanging j with j” and the second exchanging i with i’. The undirected case generates the two additional candidates that result by treating a preferred edge in its two equivalent forms of (i,j) and (j,i) . (“Two—for— one” exchanges result by replacing node i or node j with the pair (i’) or (j,j”), and replacing previous references to i’ and j” by the predecessor and successor of those later nodes.)
We suggest that fuller advantage can be gained from the preferred attribute candidate list by replacing the costs c(i,j) with non—negative reduced costs derived by solving an assignment network relaxation of the traveling salesman problem. This will not change the move evaluations, but typically will change the identities of the “k shortest” arcs leaving and entering the nodes. (Ties can be broken be reference to original costs.) Additional shortest arcs may be included as determined by “modified” reduced costs, where subtour elimination constraints are incorporated in a Lagrangian function to amend the network assignment solution. Another option is to use the successive minimum spanning tree constructions of Stewart (1987). (In tabu search applications, preferred arcs can also be identified by reference to customary criteria used in intensification and diversification processes, such as historical information about their frequency of occurrence in solutions of a particular quality.)
4.2Effective Updates of Candidate List Evaluations
Candidate list information can be updated from iteration to iteration by a rule that permits only a small number of evaluations to be recalculated (in order to identify a “new best” move) . The forward and reverse stars of the preferred attribute candidate list again play a key role. More precisely, all updating operations can be effected by reference to a restricted subset of forward and reverse stars, with simplified calculations and substantial gains in efficiency. The way to do this is described in Appendix B. In addition, Appendix C identifies a way to support the preferred attribute candidate list with a second elite evaluation candidate list that provides further efficiencies.
5.Tabu Restrictions for One—Node and Two—Node Moves
To provide a background for the determination of tabu restrictions, we first discuss two types of tabu restrictions used effectively in related settings. Then we suggest a third type of tabu restriction, as an alternative for the present approach when simple one—node and two—node insert and exchange moves are used. Tabu restrictions for more advanced moves are described subsequently.
A relatively stringent restriction that has worked well in machine scheduling (Glover and Laguna, 1990) prevents a node from being inserted between two others, or from swapping with one other, if it has taken part in the same type of move on one of the t preceding iterations. The value t represents the size of a short term tabu list, and normally increases as a function of n. Experience indicates there are advantages to varying t over an interval (randomly or systematically), retaining each assigned value for about 2t iterations before assigning another value in the interval (see, e.g., Taillard, 1990) . However, for the indicated tabu restriction in machine scheduling, a special longer term diversification strategy was employed which caused the best value of t to be simply a constant value of 7.
The form of this diversification approach is as follows. The strategy is initiated when the rate of finding improved solutions diminishes, and is applied only on the iterations where the best non—tabu move does not improve the current solution. The evaluation of the moves then is penalized by subtracting the value w*count(i), where w represents a parameterized weight and count(i) identifies the number of times node i was inserted between other nodes over the history of the search. A corresponding count is maintained for exchange moves. In the machine scheduling context studied, a weight of w = 10 proved effective. (The best results in the absence of this frequency— based memory were obtained by varying t systematically over an interval several units above and below 1.5 ‘In.)
Another type of tabu restriction, found effective for quadratic assignment problems (Skorin—Kapov, 1990; Taillard, 1990), forbids a move that places each of two exchanged nodes i and j in positions they respectively occupied on one of the t preceding iterations. For the traveling salesman context, if fixed positions are replaced by relative positions, we may identify a tabu predecessor (and/or tabu successor) for each node i, defined to be the node that preceded (succeeded) i in the tour immediately before node i was last moved. The type of restriction used in QAP applications then can be adapted both to insert moves and exchange moves in the traveling salesman setting. This restriction is somewhat weaker than the one indicated for machine scheduling and requires larger values of t (again best managed by varying t over an interval). Improved performance may result by coupling the two restrictions, and by imposing the stronger one only for a much smaller value of t (e.g., 3 or 4).
We propose a somewhat different type of tabu restriction as an alternative to these earlier ideas. The restriction forbids an arc (or “link”) displaced by a move from being reestablished in the tour for a specified number of iterations. In the case of a move that inserts a node between adjacent nodes p and q, the restriction specifically prohibits all moves for t iterations that allow arc (p,q) to return to the tour. (Thus the node inserted cannot be moved immediately again, at least until node p or q is moved, or until another node is inserted after p or before q.)