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.1 Candidate 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.2 Effective 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.)

A two—node insert move creates the same displaced link restriction (allowing one but not both of the inserted nodes to move immediately again) . For exchange moves, the restriction may be created by conceiving the move as a sequence of two insert moves. The first component move inserts node i either between j’ and j, or between j and j”, and the second move inserts j between i’ and i”. We identify node i in this operation to be the node that yields the largest length for the arc (i’,i”), a definition that assures this arc will be rendered tabu by the exchange. Then we stipulate that node i is inserted between the endpoints of the larger of the two arcs (j’,j) and (j,j”), also assuring this arc will be rendered tabu. In the special case where i and j are adjacent in the tour, thus causing the exchange move to be equivalent to an insert move, we identify node i as indicated, and make the single arc (i’,i”) tabu. (As an alternative, this single arc may be made tabu for exchange moves in general.)

The displaced link tabu restrictions can be implemented by maintaining an array tabu_time(i,j), initialized to 0, whose entry (i,j) is assigned the value of the current iteration when arc (i,j) becomes tabu. (That is, tabu_time(i,j) identifies the most recent iteration that arc (i,j) received a tabu status.) Then arc (i,j) remains tabu for as long as its tabu age, given by current_iteration — tabu_time(i,j), is no more than t (hence as long as tabu time(i,j) > current iteration — t)

When t is varied dynamically, which as noted is generally preferable, the updating can be modified by setting tabu_time(i,j) = current_iteration + t at the point where arc (i,j) becomes tabu. Then (i,j) remains tabu until tabu_time(i,j) < current_iteration. This type of update is also valid when t remains fixed. It has the advantage that a change in t will not cause the tabu tenure of arc (i,j) to shift after the arc becomes tabu. This approach also avoids the need to keep t smaller than the current iteration value during the first few iterations (to avoid falsely identifying arcs with tabu_time(i,j) = 0 as tabu during initial iterations) . This update has a disadvantage if the same array is used for long term as well as short term memory, since then the record of when an element in fact became tabu will be masked by the changes in t.

6. Embedded Neighborhood Structures and Ejection Chains

The use of embedded neighborhoods adds another level of sophistication to the procedure and the chance to generate moves of somewhat greater power. Embedded neighborhoods of various types have been used in other methods and may be conceived as the outcome of compressing a sequence of moves into a single compound move. However, the structure of the resulting neighborhood is not always explicitly recognized, nor is it usually exploited in a way designed to identify its superior members. From our perspective, embedded neighborhoods are derived in the following manner: (1) the neighborhood for a simple type of move (e.g., a one or two—node insert move) becomes embedded, level by level, in successively larger neighborhoods that represent more complex moves; (2) the moves at each level cannot be obtained by collections of independent (non—intersecting) moves of previous levels, and hence their evaluations cannot be known from the evaluations of lower level moves; (3) the component moves carried forward from one level to the next are incomplete or infeasible, by themselves, but yield legitimate higher level moves with appropriate trial completions.

In addition to these characteristics, the embedded neighborhoods we propose yield an important form of combinatorial leverage. Specifically, the number of moves represented by a level k neighborhood is multiplicatively greater than the number of moves in a level k—i neighborhood, but a best move from the neighborhoods at each successive level can be determined by repeating only the effort required to determine a best first level move. In our application, for example, the moves of the first, second and third levels are respectively 0(n2), 0(n3) and 0(n4) in number, but a best member of each can be found by repeating the 0(n2) effort required to determine a best move of the first level.

To understand the operation of these moves, consider starting with a simple one—node (or two—node) insert move. If the best of these moves is not improving, then any legitimate (non—overlapping) succession of these moves will still not yield an improvement. However, an opportunity for improvement may be afforded by a more complex linking where successive moves are modified to permit overlaps, as where a node i is first inserted between two others, and then one of the nodes now adjacent to i is then inserted between two additional nodes (implicitly modifying the original structure of the second insert) . We may conceive of this as a succession of two transition moves, the first an ejection move where node i is moved to occupy the position of a second node j (which thereby will be ejected from that position), and the second a reduced insert move where node j is then cut loose and inserted between two other adjacent nodes. (The second move is not a regular insert move because j’ and j” are not joined by the move.) The neighborhood for inserting a node i becomes modified by transforming the insertion into an ejection, and then embedded in a larger neighborhood, whose marginal component is again modified by transforming a second insertion into a reduced insertion.

Evidently the second level neighborhood contains 0(n3) moves (barring the use of candidate lists), since each of the n choices for i can eject 0(n) alternatives for node j, which in turn can be inserted between 0(n) adjacent pairs. However, we can identify a best move from a closely related 0(n3) neighborhood by two applications of 0(n2) effort. More precisely, the 0(n3) neighborhood we treat is less encompassing than the one indicated, as a result of interference among certain move components. In particular, it is necessary to avoid duplications among certain nodes as different levels are constructed, and this implicitly restricts the scope of a neighborhood over which a best move is identified. However, as long as the number of levels is small relative to n, the combinatorial leverage is not significantly affected by this restriction.

The constructions we propose incorporate sequences other than those ending in insert moves, and include additional accelerated move generation procedures that can quickly penetrate to more advanced levels. We also include procedures capable of constructing tours by successively augmenting the number of tour nodes, employing the same frameworks and hence offering the same opportunities for leverage.

6.1 The Ejection Chain and its Components.

The basic element of construction we propose for building embedded neighborhood structures is an ejection chain. An ejection chain may be viewed as a series of levels, each consisting of three nodes which appear consecutively in the tour, and which we designate as entry nodes, core nodes and exit nodes. (The entry node and the exit node are respectively the predecessor and successor of the core node. Hence all nodes of the chain can be identified by specifying the core nodes.)

For visualization purposes we may imagine the levels of an ejection chain as a vertical stack. The chain represents a partial transition from the current tour to a new tour, determined by a sequence of moves where each core node ejects the core node immediately below it, ending with the ejection of the bottom node. More precisely, the transition may be characterized as detaching each core node from its current predecessor and successor, and reattaching it to the predecessor and successor of the succeeding (lower) core node. The top core node therefore leaves an unoccupied position and the bottom core node becomes detached, free to be relocated.

A diagram of an ejection chain is given in Figure 1. The altered node connections created by the associated transition move occur by introducing the diagonal arcs of the diagram as new arcs of the tour, and by dropping the horizontal arcs (which are shown in the diagram as “hollow” arcs)

We define the collection of entry nodes, core nodes and exit nodes to be the spanning nodes of the ejection chain. For the ejection chain to have a legitimate structure, we require that each core node occurs only once in the chain; that is, it cannot reappear as any of the other spanning nodes. A given node may possibly appear both as an entry node and as an exit node without violating this restriction.

The preceding characterization of legitimacy implies that no arc will be added or dropped more than once by the transition move associated with the ejection chain, and the tour cost change created by the transition move equals the sum of the costs of the added arcs minus the sum of the costs of the dropped arcs. These outcomes are important to the goal of efficiently generating and evaluating chains of progressively greater complexity. (We will later show how it is possible to get around this definition of legitimacy, although at the expense of greater memory and computational effort.)

6.2 Trial Moves to Create New Tours.

Trial moves to complete the transition from the current tour to a new tour, with no unoccupied positions and no disconnected nodes, are of two types.

Type 1 Trial Move (Circularization Move) : Relocate the bottom core node b to occupy the vacant position left by the top core node t, circularizing the ejection sequence.

Type 2 Trial Move (Cap and Anchor Move) : Join the top entry and exit nodes by adding the arc (t’,t”) (capping the “hole” left by t), and insert b between two adjacent nodes p and q = p” (anchoring the chain)

The nodes p and q of a Type 2 trial move effectively become additional members of the set of spanning nodes. Thus, for a Type 2 trial move to be legitimate, p and q cannot correspond to any of the core nodes of the ejection chain. Illustrations of Type 1 and Type 2 trial moves are provided in Figures 2 and 3.

The effect of the two indicated trial moves on the tour cost can be readily identified. A Type 1 trial move modifies the ejection chain by adding arcs (t’,b) and (b,t”), while a Type 2 trial move modifies the chain by adding arcs (t’,t”), (p,b), (b,q), and dropping arc (p,q) . It is convenient to subdivide these changes into three component operations: relocating b to the position t, capping the position of t, and inserting b between p and q. The cost changes associated with these operations may be expressed as follows:

relocate(b,t) = c(t’,b) + c(b,t”)

cap(t) = c(t’,t”)

insert(b,p) = c(p,b) + c(b,q) — c(p,q) for q = p”. Denote the tour cost change of the transition move associated with the ejection chain by ejection_value, and denote the tour cost changes associated with Type 1 and Type 2 trial moves respectively by trial_value_1 and trial_value_2. Then, for an ejection chain satisfying the requirements of legitimacy (including p and q as spanning nodes for a Type 2 trial move), we have:

trial_value 1 = ejection_value + relocate(b,t)

trial_value 2 = e jection value + cap(t) + insert(b,p)

6.3 Growing the Chain

An ejection chain can be grown from either end, by a top extension move or a bottom extension move. A top extension move selects a node i to become the new top core node by disconnecting i from its current position and relocating it to occupy the position of node t. A bottom extension move selects a node j to become the new bottom core node by disconnecting j from its current position and relocating node b to occupy this position. The forms of these two extension moves are shown in Figure 4.

To maintain the legitimacy of the ejection chain produced by these extension operations, it suffices to stipulate that the newly added core node does not equal any of the previous spanning nodes, or equivalently, that the newly added spanning nodes (the new core node and its predecessor and successor) do not equal any of the previous core nodes.

To characterize the effect of the top and bottom extension moves, we identify the cost change associated with the component operation of disconnecting an arbitrary node i from its predecessor and successor, by defining:

disconnect(i) = —(c(i’,i) + c(i,i”))

Let add_top(i,t) denote the increment to ejection_value from adding a new node i to replace t as the top node, and let add_bottom(j,b) denote the increment to ejection_value from adding a new node j to replace b as the bottom node. Then by the preceding definitions:

add_top(i,t) = disconnect(i) + relocate(i,t) add_bottom(j,b) = disconnect(j) + relocate(b,j)

The tour cost change created by the new ejection chain (i.e., by the transition move associated with this chain) may therefore be expressed as

new_ejection_value = ejection value + add_top(i,t) for a top extension move, and

new ejection_value = ejection_value + add_bottom(j,b) for a bottom extension move. Because the quantities add_top(i,t) and add_bottom(j,b) are independent of the composition of the ejection chain (except for the identities of t and b), they may be precomputed to save work when these values are used multiple times.

6.4 One—Sided Ejection Chains

There are organizational advantages to growing an ejection chain in only a single direction (i.e., allowing only top extensions or bottom extensions) . When the direction of growth is thus restricted, methods based on Type 2 (cap and anchor) trial moves gain additional benefit by operating with a one—sided ejection chain that begins either capped or anchored, and remains that way through subsequent extensions. The basic starting structures for these two types of one—sided ejection chains are shown in Figure 5.

A capped ejection chain, as in the upper part of Figure 5, effectively has no top node t (since the top position is inaccessible), and an anchored ejection chain, as in the lower part of Figure 5, effectively has no bottom node b (since no node is free for relocation) . A more rudimentary form of capped ejection chain than shown in Figure 5 results by eliminating the lower level of nodes (and their incident arcs), leaving only the upper capped level. However, the anchored ejection chain of Figure 5 has no simpler form.

These two types of chains can be grown by the same extension moves described previously. That is, a new node j may be added to the bottom of a capped chain, with an incremental cost equal to add_bottom(j); or a new node i may be added to the top of an anchored chain, with an incremental cost equal to add_top(i) For node j to be legitimately added to a capped chain, nodes j, j’ and j” cannot equal any of the core nodes, while for a node i to be legitimately added to an anchored chain, nodes i, i’ and i” cannot equal any of the core nodes and nodes i and i’ cannot equal node p (or equivalently, i cannot equal either p or q =

The trial moves for these two types of one—sided ejection chains are given by the “missing half” of a normal Type 2 trial move (i.e., it is only necessary to anchor a capped chain and to cap an anchored chain) . Denote the tour cost change of the transition move associated with an ejection chain by ejection_value (as before), and let trial_value_2A and trial_value_2B respectively denote the tour cost change created by capping an anchored chain. Then and by anchoring a capped chain, we have:

trial_value 2A = ejection_value + cap(t)

trial value 2B = ejection value + insert (b,p)

The simplified trial moves that produce these two trial values will be called Type 2A trial moves and Type 2B trial moves. It is standardly more convenient to work with anchored chains and Type 2A trial moves, where the choice of p is made at the start and is not repeated.

We describe an additional role for one—sided and two—sided ejection chains, and then give the procedures for exploiting them.

6.5 Constructing Initial Tours

Procedures for solving ~traveling salesman problems are often concerned with the construction of initial tours. Such tours can be constructed using ejection chains by the simple device of replacing the capping operation of Type 2 and Type 2A trial moves with a filling operation. Instead of capping the vacant position left by the top node t, the trial move fills this position with a node not currently in the tour. Thus, starting with any partial tour consisting of three or more nodes, ejection chains can be used to add new nodes until a complete tour containing all nodes is created.

A tour construction method based on this process has an attractive property. A fill move that places a non—tour node h in the position vacated by a tour node t consists of adding the two arcs (t’,h) and (h,t”). The change in tour cost contributed by this move therefore equals relocate (h,t) . The choice of the non—tour node h does not have to be restricted to assure the

resulting ejection chain will be legitimate (since h cannot corr?spond to any of the spanning nodes of the ejection chain) Consequently, for any given node t of the tour, there is a best node h* to replace it, identified as a non—tour node that yields a minimum value of relocate(h,t) . This outcome holds regardless of the ejection chain to which t belongs.

Consequently, a best h* can be determined in advance for each tour node t, recording best(t) = h’, before initiating the creation of ejection chains. Then, we define fill(t) = relocate(h*,t), and when Type 2 and Type 2A trial moves are modified to replace the capping operation with the filling operation, the associated tour cost changes (trial_value 2 and trial_value_2A) simply replace the quantity cap(t) with the quantity fill (t) . Denoting these two tour cost changes by trial_value_2* and trial_value_2A*, we therefore have:

trial value 2* = ejection value + fill(t) + insert (b,p)

trial_value 2A* = ejection_value + fill (t)

Based on these observations, the ejection chain methods for creating improved tours from preexisting tours can be directly adapted to generate tours constructively. Such constructive approaches can include simple insert moves to round out the range of alternatives considered. We now describe the fundamental variants of ejection chain methods, beginning with the intensive computational method that yields an assured degree of combinatorial leverage.

6.6 An Anchored Chain Construction

Operating with an ejection chain that is always anchored, we give a procedure that finds best moves from neighborhoods that grow by increasing the power of n at each level, while adding only 0(n2) effort to the work expended. The chain is initiated by an insert move, and each augmentation of the chain is a top extension move.

The ejection chain is recorded by storing its core nodes and the additional node p of the adjacent node pair (p,q) that the bottom node is inserted between. We call p the anchor node of the chain. A collection of chains is created at each level, each associated with a different top core node t, as t ranges over the nodes of the tour. Thus for each t = 1, ... ,n, we retain a vector core(t), an element anchor(t), and a value ejection_value(t), where core(t) lists the core nodes of the anchored ejection chain for t, anchor(t) identifies the anchor node p, and ejection_value(t) identifies tour cost change for the transition move associated with the ejection chain.

By construction, each chain at a given level k will give a minimum value of ejection_value (t) . This minimum occurs over a restricted set of anchored ejection chains with top core node t and containing k core nodes. The set is restricted (i.e., does not include all possible “level k” ejection chains with top t) because of the requirements of legitimacy that influence the way a chain can be grown. The size of the restricted set nevertheless is on the same order as the size of the

corresponding unrestricted set if k is small. The neighborhood that results by allowing t to range over all tour nodes encompasses all level k ejection chains in the unrestricted case and “most” of these chains in the restricted case.

The method obtains a best move from the restricted neighborhood by the following mechanism. A trial move to create a complete new tour results by capping the ejection chain, adding the arc (t’,t”) . Since the cost of this operation depends only on t, a best anchored chain for t translates into a best new tour associated with t. Hence, since every anchored chain must have some node of the tour as its top node t, the choice of the best t must give the best transition move, from the class considered, at each level.

Employing this rationale, the form of the construction is as follows.

Anchored Chain Method.

Level 1. (Determine a best insert move to anchor each node i) . Examine each node i in turn. Consider each node p not equal i or i’, and identify a node p~ (given i) that yields the minimum value of insert(i,p).

(A) Record the values:

anchor(i) =

ejection_value(i) = insert(i,p*) + disconnect(i),

and create the vector core(i) to consist of the single element i.

(B) Define:

trial_value(i) = ejection_value(i) + cap(i) identifying the tour cost change for the best complete trial move (insert move) for node i. Record the minimum trial_value(i) as best trial value, and save the associated core(i) and anchor(i), to identify the current best candidate for the trial move to select when the method terminates.

Level k for k ( 2. (Determine a best level k chain that includes node i as its new top core node, for each node i.) Examine each node i, and consider each node t that may legitimately be matched with i (i.e., such that i, i’ and i” do not equal any node of core(t), and i and i’ do not equal p = anchor (t))

(A) Identify

value(t) = ejection_value(t) + add_top(i,t) (This gives the ejection_value for chains with different top nodes t, when node i is added as the new top core node.) Let t~ denote the t, given i, that yields the minimum value (t) . Record the associated level k anchored chain for node i by setting

new_ejection_value(i) = value (t

new_anchor(i) = anchor (t’)

and create the vector new_core(i) by adding node i as the new top node of the vector currently recorded as core (t*) . Identify the tour cost change for the associated best trial move for node i by

trial_value(i) = new_ejection_value(i) + cap(i).

(C) If trial_value(i) is smaller than best_trial value, record it as the new best trial_value, and save the associated new_core(i) and new_anchor(i) (identifying the new best move to select when the method ends) . When the current level k step has been executed for all nodes i, replace ejection_value(i), anchor(i) and core(i) by new ejection value(i), new start(i) and new_core (i) . Then repeat the level k step for the next value of k (until reaching a chosen cutoff)

The foregoing procedure can be used alternately to construct initial tours by replacing capt(t) with fill(t) in the definition of trial_value(i), following the approach previously indicated. The level to which the procedure is carried will depend in part on the effort of checking node i and its adjacent tour nodes against core(t) and anchor (t) . The effort is negligible for k = 2, when core(t) contains the single element t. However, as the size of the core vectors grows this effort becomes increasingly burdensome and the effect of combinatorial leverage is also eroded. Consequently, at some point further increases in k become unproductive. To compensate for this limitation we will later provide accelerated methods designed to generate chains of greater depths.

6.7 An Unanchored Chain Construction

A natural analog of the preceding anchored chain approach is an unanchored chain approach, using circularized instead of cap and anchor trial solutions. The interpretation of a “best move” at each level is less clear in this approach, because the best ejection chain to be matched with a node (to create an extension) is generally not the same chain that yields a best trial solution. (The choice rules may be modified to allow such a correspondence, although causing a “best chain” to be different than one that minimizes the associated tour cost change.) Nevertheless, it seems appropriate to generate unanchored chains by a growth pattern of the same form used in the anchored case. The different types of trial moves for unanchored chains, and the different neighborhoods implicitly explored, may offer the chance for superior outcomes.

The starting process for unanchored ejection chains creates a core vector of two elements (instead of a single element vector coupled with an anchor node) . The method may be organized to make either successive top extensions or successive bottom extensions, in contrast to the anchored chain approach where only top extensions were available. The initial ejection chains have the same topology for both the top extension and bottom extension procedures, which consist simply of a two level chain that is neither capped nor anchored, but the constructions for the two procedures are organized and evaluated differently. Specifically, in a top extension process, where an initial bottom b remains constant, the evaluation is made relative to the quantity

start_top(i,b) = add_top(i,b) + disconnect (b) where node i is a candidate for the first top node above b. (This may be viewed as starting with a “degenerate” unanchored chain whose only core node is b, and whose evaluation is given by disconnect (b) .) Similarly, in a bottom extension process, where an initial top t remains constant, the evaluation is made relative to the quantity

start_bottom(j,t) = add_bottom(j,t) + disconnect(t) where node j is a candidate for the first bottom node below t.

In the following, we give a process based only on top extension moves (from which the corresponding process using bottom extension moves can be readily inferred) . Beginning with a construction that yields two core nodes at Level 1, each successive level k produces a construction with k + 1 core nodes.

Unanchored Chain Method

Level 1. (Determine a best starting 2—node unanchored chain that includes node i as the top node, for each node i.) Examine each node i in turn. Consider each node b not equal or adjacent to 1.

(A) Select b* to minimize start_top(i,b), and set ejection_value(i) = start_top(i,b’)

Create the vector core(i) to contain i as its top node and b~ as its bottom node.

(B) Identify the node b that minimizes the quantity start_top(i,b) + relocate(b,i) and define:

trial_value(i) = start_top(i,b) + relocate(b,i)

(C) Save the minimum trial value(i) as best trial_value, and correspondingly save the core vector with top node i and

associated bottom node b, to identify the current best candidate for :he trial move to select when the method terminates. (Note, at Level 1 the best recorded move is an exchange move, and may be found with less effort using symmetry, noting that the exchange involving a given top and bottom node gives the same outcome as when the roles of these nodes are reversed.)

Level k for k ( 2. (Determine a best level k chain, containing k + 1 nodes, for each node i as the current top node.)

Examine each node i, and consider each node t such that i, H and i” do not equal any node of core(t)

(A) Identify

value(t) = ejection_value(t) + add_top(i,t)

Let t~ denote the t that minimizes value(t), given i, and record:

new_ejection_value(i) = value (t*)

Correspondingly, create new_core(i) by adding node i as the new top node of core (t’)

(B) Identify the node t that minimizes value(t) + relocate (b(t),i), where b(t) denotes the bottom node of core(t), and define:

trial_value(i) = value(t) + relocate(b(t),i)

(C) If trial value(i) is smaller than best_trial value, save it as the new best_trial_value, and save the corresponding vector core(t), augmented to include node i as its new top node, to identify the associated current best trial move. When the current level k step has been executed for all nodes i, replace ejection_value(i) and core(i) by new_ejection_value(i) and new_core(i) . Then repeat the step for tlre next level k (until reaching a selected cutoff)

The foregoing design clearly yields a different set of alternatives than the anchored chain construction, not only because the trial solutions are different, but because the underlying ejection chains on which they are based are different (generated by different criteria) . An unanchored chain method using bottom extensions may also yield different moves than those using top extensions.

6.8 Exploiting the Preferred Attribute candidate Lists

The 0(n2) effort at each level of both the anchored and unanchored chain methods can be significantly reduced by taking advantage of the preferred attribute candidate lists, with some possibility of reducing the quality of the best move found. This may be accomplished conveniently as follows.

In the case of a top extension move, in which a node i is added to an ejection chain to replace the current top t, we adopt a natural extension of our earlier ideas and require that at least one of the two added arcs, (t’,i) and (i,t”), is a preferred arc. To fulfill this requirement, we scan the preferred forward and reverse stars of each node i as it is examined in the normal course of the preceding methods. Node i is then matched with the ejection chain associated with top node t, where: (1) t = h’ as h ranges over endpoints of arcs (i,h) in the preferred forward star of node i; (2) t = h” as h ranges over endpoints of arcs (h,i) in the preferred reverse star of node i. (For the Level 1 stage of the anchored chain procedure, node p takes the role of t, and these two cases are amended by setting p

— j’ and p = j, respectively.)

To avoid examining the same t twice, employ a marker m(t) that is assigned the value m(t) = i when node t is matched with i. The condition m(t) = i then signals that the match should not be made again. (To avoid reintializing m(t) = 0 at each level, set m(t) equal to —i at alternate levels.)

In the case of bottom extension moves, where a node j is added to replace a bottom node b, we require that at least one of the arcs (j’,b) and (b,j”) is a preferred arc. Rather than scan the preferred forward and reverse stars of j, we examine the forward star of j’ and the reverse star of j” to identify the nodes that qualify for b. In this case, a marker m(b) = j can be used to avoid duplicate examinations.

7. Accelerated Ejection Chain Methods

The ejection chain methods described in the preceding sections may be viewed as outside—in, or element—to—configuration methods. Each stage is initiated by scanning the tour nodes (elements) and seeking a best ejection chain (configuration) to be joined with each node in order to yield a new ejection chain at a higher level. By contrast, the procedures we now propose are inside—out, or configuration—to—element methods. These operate by scanning a set of one or more ejection chains (configurations) at each stage, seeking a best node (element) to extend each chain to a new higher chain level. The inside—out procedures provide fuller control over the number of alternatives carried forward from level to level, thus offering the possibility of accelerating the generation of ejection chains. They also offer the chance to use memory structures that yield further efficiencies.

The inside—out procedures we propose carry forward “r best” ejection chains from each level to the next. By choosing r to be smaller than n, the approach can exploit trade offs between effort expended and quality of outcomes generated. We will focus on two main types of inside—out strategies, fanning methods and focused methods. These methods may be differentiated by the degree to which alternative extensions are restricted. The fanning methods scan the possible node extensions of each of r current best chains to isolate r “new best” chains for the following level. The focused methods start with r initial best chains, but extend each independently of the others. In tightly focused versions, consideration is limited to a single option at each step, and permissible extensions are “pre—programmed” to be executed with particular efficiency.

Both the fanning procedures and the focused procedures begin with the fundamental configuration used as the starting point for the unanchored chain procedure, i.e., a simple two level chain that is uncapped and unanchored. Thus the initial core nodes are represented either by the pair (i,b) or (t,j), corresponding to the two cases where node i initiates a top extension from a bottom node b and node j initiates a bottom extension from a top node t. The starting configurations in these two cases therefore receive evaluations start_top(i,b) and start_bottom(j,t), where

start_top(i,b) = add_top(i,b) + disconnect (b)

start_bottom(j,t) = add_bottom(j,t) + disconnect (t)

In contrast to previous approaches, the accelerated procedures. can grow an extension chain in either of two directions at each step (by choosing either of the two ends to extend) . For convenience, however, we describe how the procedures operate in a single direction, where all extensions are top extensions. The conversion to bottom extension or bidirectional processes is straightforward, as subsequently indicated.

7.1 Fanning Methods.

Fanning methods reverse the roles of nodes outside the ejection chain and nodes at the ends of the chain, as a basis for extending the chain at each step. Preferred attribute candidate lists are important to efficiency in these methods and their operation is explicitly identified in the description of these procedures. (Each reference to a preferred forward star or to a preferred reverse star becomes simply a reference to a preferred star in the symmetric case.) The general framework for a top extension fanning method may then be given as follows.

Top Extension Fanning Method (Unanchored)

Initialization. For each node b, consider each nonadjacent node i (i ( b) contained in the preferred forward star of b’ or in the preferred reverse star of b”. Over the resulting node pairs (i,b)

(A) Select r pairs that yield the smallest values of start_top(i,b), and index the corresponding ejection chains by e = 1, ..., r. Let core(e) denote the core vector for chain e, whose top and bottom nodes are given by nodes i and b, and record the tour cost change for its associated transition move by value(e) = add top(i,b)

(B) Evaluate the circularization trial moves for exchanging i and b, which give tour cost changes equal to

trial_value = add_top(i,b) + relocate (b,i)

Save the minimum trial value as best trial value, and record its associated initial core vector, consisting of i and b. (This pair (i,b) may not correspond to any of those saved as core (e) fore=1, ..., r.)

General Step. Examine each of the r current ejection chains, and denote the top and bottom nodes of its core vector by t = t(e) and b = b(e) . Consider each node i in the preferred forward star of t’ and in the preferred reverse star of t”, such that i can be legitimately matched with ejection chain e. Over the resulting pairs (i,e), define:

add_value(i,e) = value(e) + add_top(i,t). trial_value(i,e) = add_value(i,e) + relocate (b,i)

(A) Select r pairs (i,e) that yield smallest values of add value (i,e) . These give r new ejection chains, upon adding the associated node i as the top core node for the new chain.

(B) Update the record of the best circularization trial move by resetting best_trial_value equal to trial_value(i,e) whenever the latter value is smaller. Correspondingly, record the associated new core vector consisting of core(e) with node i added as the new top node. (This vector may not correspond to any of the new core vectors generated in (A) .)

(C) After completing the previous updates, again denote the core vectors for the r best new chains identified in (A) by core(e), for e = 1, ..., r, and record the associated evaluations by value(e) = add_value(i,e) (for add value(i,e) as determined in selecting these new chains) . Then repeat the General Step until a desired cut off is reached.

The foregoing procedure can be accelerated further by introducing a vector span(i) to facilitate the determination of whether a given node i in the General Step can be legitimately matched with an ejection chain e. For this, let k be an index (associated with the current level) that identifies the number of times the General Step is executed, and let C = (n+1)k. To begin, span(i) = 0 for all i. Then the spanning nodes of ejection chain e can be uniquely identified at each level k, without re—initializing span(i), by setting span(i) = C + e for each node i such that i = j, j’ or j”, as j ranges over the nodes in core (e) . (This operation is executed just before examining a given ejection chain e.) Then an arbitrary node i is legitimate to be matched with ejection chain e if span(i) ( C + e. This enables legitimacy to be determined by a single pass of core(e), rather than by a separate pass for every node i tested.

When scanning preferred forward and reverse stars (e.g., of t’ and t”, respectively) a marker m(i) can be used to avoid double examination of node i for the same ejection chain e, setting m(i) = e during a forward star scan and checking whether m(i) = e during a reverse star scan. (These scans both become complete preferred star scans in the symmetric case.) To avoid re—initializing m(i), set m(i) = —e on odd iterations of the general step. (On the initialization step, set m(i) = b for each node b matched with i.)

A useful degree of variation in the r current best ejection chains can be obtained by limiting the number of chains associated with any given node b in the initialization step (and by similarly limiting the number of chains associated with any given e in the general step) . If the method is carried to a level where fewer than r new ejection chains can be generated, then r is decreased.

Fanning methods also can be speeded up by decreasing the value of r as the number of levels increases. At an extreme, after a chosen point r can be reduced to 1 and a single chain can traced thereafter to a desired depth.

7.2 An Anchored Variant.

In addition to the alternative of operating in the reverse direction, replacing top extensions with bottom extensions, the method also can be initiated from an anchor move. In this case, each chain inherits the anchor of its predecessor, and trial moves become capping moves rather than circularization moves. In particular, for an anchored version of the fanning method, the initialization step is altered to examine each node p (instead of b), and to consider nodes i in the preferred forward star of p or the preferred reverse star of p”. The r best anchors (insert constructions) associated with pairs (i,p) are carried forward to the general step. To determine the legitimacy of matching node i and ejection chain e using the span(i) vector, set p = anchor(e) and set span(p) and span(p”) equal to C + e just before examining chain e. (Trial move evaluations correspondingly replace relocate(b,i) with cap(i) .)

An alternative initialization is possible, both for anchored and unanchored variants, which examines each node i, to identify the best nodes p such that p is in the preferred reverse star of i or such that q = p” is in the preferred forward star of node i. The structure recorded to initialize the ejection chain is not affected, hence the general steps are unaltered from those described. Anchored versions of the fanning method alternately may be organized to generate initial tours, replacing cap(i) by fill(i), as noted earlier.

7.3 Focused Methods

Though we have reserved their description to the last, focused methods provide one of the more appealing ways to exploit ejection chains. These methods perform extra work in the initialization step to substitute for effort that may otherwise be required later. One of the strategic components is to predetermine a best top (and/or bottom) extension move for each node of tlie tour, disregarding whether the move will be legitimate for a particular ejection chain. Consequently, in addition to the two initial configurations used in the fanning methods, whose evaluations are given by start_top(i,b) and start_bottom(j,t), a predetermined extension move configuration is established. Again we focus primarily on top extension methods.

The vector span(i) can be organized in the focused method to provide greater efficiencies than in the fanning method, and hence is directly incorporated into the description of the focused method. Specifically, in this approach span(i) can differentiate all nodes in the spanning set for an ejection chain e by the simplified assignment span(i) = e, and by the assignment span(i) = —e for core nodes.

A special Intermediate Step is included in the focused method that selects one of the previously unchosen ejection chains from the r best starting chains identified in the Initialization Step. The index e of the selected chain remains fixed through subsequent steps, and the elements of core(e) are identified by reference to the level k that determines their position in the chain, starting at level k = 0. More specifically, the elements of core(e) are denoted by core_level(k), for k ( 0, where core_level(0) is the (unchanging) bottom node b, core_level(1) is the initial top node, and core_level(k) for each subsequent level k identifies the node that next becomes the new top node.

Corresponding to core_level(k), we identify value_level(k), which is the evaluation (tour cost change) for the ejection chain at level k. Thus, value_level(0) = disconnect(b) (corresponding to a “degenerate” ejection chain containing only the core node b), and value_level(1) = start_top(i,b), where i = core level(l). In general, for all k ( 0, we have

value level(k+1) = value level(k) + add top(i,t) where i core_level(k+l) and t = core_level(k) (i.e., t is the top before adding i)

With these conventions, the focused method can be described as follows.

Top Extension Focused Method (Unanchored)

Initialization: For each node h, set span(h) = 0, and consider each nonadjacent node i (i ( h) contained in the preferred forward star of h’ or the preferred reverse star of h”. Over the resulting node pairs (i,h)

(A) Select r pairs that yield the smallest values of start_top(i,h), and index the corresponding ejection chains by e — 1,...,r. Let core(e) denote the core vector for chain e (with top node i and bottom node h), and record its evaluation by value(e) = add_top(i,h) . Simultaneously identify an initial best trial exchange move, as in step (B) of the fanning method initialization.

(B) For each h, identify a best i to become a new top node to extend a chain headed by h, setting:

extend_top(h) = f, where f minimizes add_top(i,h)

Intermediate Step. Select one of the previously unchosen ejection chains e. Set span(b) = span(h) = —e, for b = core_level(0) and h = core_level(1), and set span(i) = e for i = b” , h’ ,

Create a set Trial_Set to contain all nodes p such that span(p) ( —e and span(p”) ( —e; where either p is in the preferred reverse star of b or p” is in the preferred forward star of b. (Trial_Set contains those nodes p that define legitimate insert moves for node b.) As Trial_Set is determined, identify best_p as the element p that minimizes insert (b,p) . If Trial_Set is empty, set best_p = 0.

General Step. For k ( 1:

Set t = core_level(k) and b = core_level (0)

(A) (Check Trial Solutions)

(Al) (Circularization) . Define

trial value = value level(k) + relocate(b,t)

Set best_trial_value equal trial_value if the latter is smaller and zorrespondingly save the current core vector to identify a best (circularized) trial solution.

(A2) (Cap and Anchor) . Let p = best_p. If p = 0, or if span(p) = —e or span(p”) = —e, skip this step. Otherwise, let

trial_value = value_level(k) + cap(t) + insert (b,p) Set best_trial_value equal to trial_value if the latter is smaller, and correspondingly save the current core vector and anchor node p to identify a best cap and anchor trial solution.

(A3) (Optional Multilevel circularization) : If k ( 3 then for h = 1 to h = k — 2 set b* = core_level(h) and define

trial value = value_level(k) — value_level(h) +

disconnect(h) + relocate (b*,t)

Set best_trial_value equal to trial_value if the latter is smaller and correspondingly save the partial core vector, whose elements range from core_level(h) to core_level(k), to identify a best circularized trial solution.

(A4) (Optional Cap and Anchor) Perform this step only if step (A2) can’t be performed and bestp ( 0. Eliminate each node p from Trial_Set such that span(p) = —e or span(p”) = —e. Let best_p identify the remaining node p that minimizes insert(b,p), setting besty = 0 if Trial Set becomes empty. If bestp ( 0, return and apply (A2)

(B) (Extend the Ejection Chain) If the level k has reached a desired cut off value, terminate and return to the Intermediate Step. Otherwise, let i = extend_top(t)

(Bl) If span(i) ( let, let core_level(k+l) = i value_level(k+l) = value_level(k) + add_top(i,t) . Then increase k by 1 and return to the start of the General Step.

(B2) If span(i) = —e, and if multilevel trial moves are not checked in (A2), identify the level h such that core_level(h) = i. Then if 1 ( h ( k—2, check the trial solution for h as specified in (A3) (for this single h only)

(B3) If span(i) ( let (including case (B2)), terminate and return to the Intermediate Step.

(B4) (Option to (B3)) If span (i) ( tel, examine each node i in the preferred forward star of t’ and in the preferred reverse star of t” such that span(i) ( tel. If no such i exists, terminate and return to the Intermediate Step. Otherwise, choose an i that minimizes add_top(i,t) . Then return to perform (Bi).

A tightly focused version of the preceding method results by disregarding the optional steps, (A3), (A4) and (B4) . Additional speed may be gained this way, although reducing the number of alternatives considered. Such a tightly focused method will generate a natural “self circularized” succession of moves, identified by the conditions of (B2), for about one of three ejection chains examined (since the core nodes represent one— third of the spanning nodes) . These successions are appealing because each component is locally best in an unrestricted sense.

Initial tours can be constructed, as in other ejection chain procedures, by replacing cap(t) with fill(t) in the cap and anchor trial moves. In this case, a simplified anchored version of the method may be employed, where circularization moves are disregarded and Trial_Set is irrelevant (because a permanently identified anchor node is associated with each chain) . Trial Set also is irrelevant when the method is organized to make bottom extension moves.

Elaborations.

A more ambitious version of the method can consider additional trial solutions during the execution of step (B) Such a process scans each node i in the preferred forward star of U and in the preferred reverse star of t” such that span(i) (let, and chooses an i that minimizes the quantity

trial_value = core_level(k) + add_top(i,t) + relocate (b,i) This trial_value corresponds to a best circularization that can be obtained by adding a node i. If such an effort is performed, the effort and memory used to record extend_top(h) in the initialization step may be avoided. Then identification of i to extend the ejection chain can be performed as part of the indicated scan step, choosing i to minimize add_top(i,t) (Alternatively, this choice of node i can be the same as the one that yields the circularized trial solution.) To put this in perspective, the increased work of this added step is slightly less than the work required by the fanning method in the case where r = 1, due to organizational advantages of the focused method.

An augmentation of the added scan step makes it possible simultaneously to identify a locally best cap and anchor move, where the identity of the anchor p is held constant at the value best_p. For this, it is necessary additionally to exclude consideration of nodes i such that i = p or p” (as well as those for which span(i) = let) . From the nodes i remaining, choose i to minimize

trial_value = core_value(k) + add_top(i,t) + cap(i) + insert (b,p)

This step is the same step that would be executed in the anchored chain version, noting that the value of insert(b,p) in that case will be unchanging and can be absorbed into core value (k).

Finally, we observe that “two—node moves” can be incorporated into the process (just as such moves can be incorporated in the simpler neighborhoods without reference to ejection chains) . Specifically, in a top extension procedure, a “two—node bottom” can be maintained for an ejection chain, and this pair of nodes can replace the single node b in determining insert and circularization moves to create trial solutions. (This type of variation is easier to include in the focused methods than in the other ejection chain methods.)

Alternately, when considering a node i to incorporate as a new top node, it is possible simultaneously to consider trial solutions based on incorporating an adjacent pair (i,j) as the new top. For this, define

disconnect(i,j) = —(c(i’,i) + c(j,j”))

relocate((i,j),t) = c(t’,i) + c(j,t”)

relocate(b, (i,j)) = c(i’,b) + c(b,j”)

Then we have

add_top((i,j),t) = disconnect(i,j) + relocate((i,j),t), and the cost change associated with a circularization move is

add_top((i,j),t) + relocate(b,(i,j)).

Similarly, the cost change for a cap and anchor move is add_top((i,j),t) + cap(i,j) + insert(b,p),

where cap(i,j) = c(i’,j”). Legitimacy restrictions can be enforced by simple reference to the span vector, requiring span(i) and span(j) ( ±e. The strategy of introducing two—node moves only in the creation of trial solutions allows the procedure to function otherwise as previously specified. A potentially useful expansion of alternatives therefore results at a relatively modest increase in effort.

8. Tabu Restrictions for Ejection Chains

There are evidently a variety of ways to create tabu restrictions for moves derived from ejection chains. Among the simplest and easiest to implement are restrictions that prevent the bottom and/or top node of a chain from serving (in reverse) as a top or bottom node for a specified tabu tenure (number of iterations) . Frequency—based memory can be used to prevent a node from being a core node if it has taken this role in, for example, 3 of the last 10 iterations. An effort—saving strategy may require the initial bottom or top node to be a spanning node (or more restrictively, a non—core spanning node) from the previous iteration —— a requirement periodically relaxed. The determination of best tabu restrictions and associated choice strategies to be used with ejection chains will provide a worthwhile area for experimentation.

Strategic oscillation can be applied quite naturally within this framework. Just as ejection chains can be used to introduce non—tour nodes to expand a tour, they also can be used to remove tour nodes to shrink a tour. The chain is simply left unanchored, allowing the bottom node to become a member of the non—tour set. Thus a strategy of alternately removing nodes and then adding them back is easily executed. Tabu restrictions in this case can be based on the identity of nodes removed and on the predecessor—successor links of nodes replaced.

9. Ejection Chains in Other Problem Applications

To demonstrate the general applicability of ejection chains in other settings, we sketch how they may be incorporated into the solution of vehicle routing and quadratic assignment problems.

9.1 Vehicle Routing Problems

Vehicle routing problems, which require the creation of multiple TSP tours, can be treated using ejection chains by allowing a chain to cross from one tour to another. Chains that are circularized, or that are capped and anchored within the same tour, maintain a constant number of nodes in each tour. In remaining cases, a tour that contains an anchored chain segment gains a node, while a tour that contains a capped chain segment loses a node. A depot node which the tours share in common can be treated as a different node in each tour, and also can be treated as a “degenerate tour” by itself. Thus, a new tour can be created by an anchor move that inserts a node into the degenerate tour.

Capacity restrictions may serve to modify evaluations of component moves that grow an ejection chain. There are a variety of ways to do this. A simple alternative for top extension moves is to note how much slack is created when a node is transferred out of a given tour, and to require that the move that “crosses” out of this tour to another (bringing a new node into the present tour) maintains feasibility by reference to this slack. Bottom extensions analogously seek to restore feasibility lost by the step of crossing into a new tour. Circularization moves are selected to offset a possible infeasibility created in the first or last tour of such a sequence. In a strategic oscillation approach, feasibility of capacity constraints can be allowed to decay, and then gradually restored by imposing an “improvement requirement” on the move that crosses from a given tour to another (i.e., either adding more available capacity than previously lost or relinquishing less capacity than previously added).

9.2. The Quadratic Assignment Problem

The quadratic assignment problem (QAP) involves a more comprehensive adaptation of ejection chains, and therefore gives a model that provides a broader understanding of how these chains may be implemented in a range of additional settings. The QAP consists of assigning n elements to n locations, where a predetermined flow f(i,j) must be transmitted (or shipped) between each pair of elements i,j, and where a cost c(u,v) is attached to each unit of flow sent between a pair of locations u,v. Thus, if elements i and j are assigned to locations loc(i) and loc(j), the cost of the flow between them is f(i,j)*c(loc(i),loc(j)). The goal is to find a one — one assignment of elements to locations in order to

Minimize ((f(i,j)*c(loc(i),loc(j)) : all pairs (i,j)) The adaptation of ejection chains to the QAP setting requires additional memory and computational effort beyond that required in the TSP setting, but offers compensation by allowing limitations based on definitions of legitimacy to be dropped. In the traveling salesman problem these limitations are introduced to reduce memory and accelerate computation, but the memory and computational demands of a more complex problem structure eliminate their relevance. We describe how the process can be organized in the framework of a focused method, which offers the greatest opportunities for specialization to increase speed.

A QAP Ejection Chain Construction.

An analogy with the ejection chain constructions previously discussed can be established by thinking of the elements i as “nodes” which are to be assigned to locations. We let loc(i) represent the location of i in a current solution, and let loc~(i) represent the location of i in a solution corresponding to a trial ejection chain under consideration. In the QAP setting we are not concerned with spanning nodes of a chain (since previous notions of adjacency and legitimacy are no longer relevant), but only with the identity of “core elements” that are moved to occupy new locations, that is, the elements i such that loc’(i) ( loc(i)

In a focused method, we begin by identifying the best local move for each element i, which constitutes removing i from its current location and relocating it in the position occupied by an element h, which is thereby rejected. This move initiates a chain in which i is the first top element and h is the first bottom element. The r best such moves are thus selected in the initialization step. (The method may alternately start by looking at each h and finding the best i to replace it, or, may simply select initial chains based on the r best exchange moves.)

Initializing loc*(i) = loc(i) for all i, the cost changes induced by the component operations of disconnecting an element i can be expressed for any iteration as follows:

disconnect(i) = -( (f(i,j)c(loc*(i),loc*(j)) : all j ( i,b) The node b represents the bottom element, already disconnected. Initially if i is under consideration to become b, then the stipulation j ( i,b in the definition of disconnect(i) is treated as equivalent to j ( i.

The cost change of relocating an element i depends on the new location it is allowed to occupy. In bottom extensions this will be a location currently occupied by an element h (hence loc*(h)), while in top extensions it will be a location recently vacated by such an element (hence not loch (h)) . However, in each case the location can be specified, and we will simply call it newloc. Under the natural and convenient restriction that prevents an element from being moved twice in constructing an ejection chain, newloc = loc(h) for the selected element h, independent of employing a top extension or bottom extension.

Basics of a QAP Focused Method

We describe the focused method relative to top extensions, understanding that newloc represents the location vacated by an element h. The disconnected bottom element b remains constant. Then the cost change relocate(i,h) of relocating i in the position newloc (independent of disconnecting i), may be expressed as

relocate(i,h) = ((f(i,j)c(newloc,lOc’ (j): all j ( i,b). (For bottom extensions, element h must be interpreted as the one that was most recently placed in the location vacated by i, noting that j may take the value h in the summation, and newloc refers to the location currently occupied by b.)

The cost change contributed by adding element i as a new top element, replacing a current top t, is therefore add_top(i,t) = disconnect(i) + relocate(i,t).

This is the same formula used in the TSP setting. Thus, if current value represents the cost change induced by the current ejection change and new_value represents this change after adding element i as the new top, we have

new_value = current_value + add_top(i,t)

To identify the associated trial value for a circularization move that places element b in the location occupied by i, first set newloc* = bc’, then set bc * = newloc, and finally reset newboc = newloc’. This creates a properly amended definition of rebocate(b,i), where i tentatively has become the new top. (Note that the definition of rebocate(b,i) literally yields a summation over j ( b,b, hence simply over j ( b.) As a consequence, we obtain

trial value = new value + rebocate(b,i)

which again is the same formula that applies to traveling salesman problems.

By precomputing values of disconnect(i) and add_top(i,h) during initialization, their current values can be identified by examining the elements for which loc’(i) ( loc(i) and calculating adjustments over this reduced set, thus saving computation. In general, the initialization will identify top_extension(h) for each h to be the element i’ that minimizes add_top(i,h), where b — h and newloc = boc(h) in the definitions of disconnect(i) and relocate (i,h)

A tightly focused method generates top extensions solely by reference to these initial determinations. In this case it is automatically assured that no element can be moved twice, and the trial value at each step simplifies to

trial_value = current_value + relocate (b,t)

By contrast, a more broadly focused method scans the current top element t and selects an extension based on the minimum new value, while simultaneously generating associated trial values as previously identified. Elements potentially may be moved more than once in these procedures, although legitimacy restrictions reasonably may be based on aspiration criteria, as by allowing an element to be moved again only if the resulting move evaluation (or associated trial move value) passes a threshold of attractiveness.

Such options, coupled with the potential for creating streamlined updating operations, provide a significant range of alternatives for applying ejection chains to quadratic assignment problems. In addition, the accounting for positional dependencies indicated for the quadratic assignment problem can be adapted to handle other objective functions and permutation based structures, permitting ejection chain procedures to be established for a variety of scheduling problems beyond those susceptible to a QAP formulation.

10. Specialized Memory for TSP’s and General Implications.

The memory structures used for quadratic assignment problems allow more flexible definitions of legitimacy for traveling sale3man problems, which are special cases of QAP’s. However, this entails considerable expense, and it should be noted that the combinatorial leverage effect of the first methods described for TSP’s is probably not enhanced (and may be hindered) by alternate legitimacy definitions. In the case of the accelerated fanning methods and focused methods, the relative advantages and disadvantages of relaxed requirements for legitimacy are unclear.

Notably, flexibility in defining legitimacy for TSP’s can be obtained by a different memory than required for QAP’s, and with far less calculation. Specializing the observations underlying the QAP organization, it is only necessary to know the current predecessors and successors of spanning nodes in the TSP setting, and to define the tour cost changes underlying the determination of quantities such as disconnect(i) and relocate(i,h) relative to these records. Analogous specializations can be instituted in other problem contexts, according to the forms of connectivity inherent in evaluating cost and feasibility conditions. Appendix D suggests a network perspective for viewing such specializations, with an associated opportunity for creating moves by relaxation strategies.

Ejection chains permit a variety of alternative constructions, and their most effective exploitation is a matter to be determined by empirical investigation. The frameworks and associated data structures proposed here are intended to identify the primary alternatives, together with rules for implementing them efficiently.

This research was supported in part under the Air Force Office of Scientific Research and Office of Naval Research Contract F49620— 90—C—0033 at the University of Colorado.

REFERENCES

Fiechter, C.—N. 1990. A Parallel Tabu Search Algorithm for Large Scale Traveling Salesman Problems. Working Paper 90/1, D~partement de Mathématiques, École Polytechnique Fédérale de Lausanne, Switzerland.

Gendreau, M., Alain Hertz and Gilbert Laporte 1990. New

Insertion and Post—Optimization Procedures for the Traveling Salesman Problem. CRT—708, Centre de Recherche Sur Les Transports, Université de Montréal.

Glover, F. 1964. A Bound Escalation Method for the Solution of Integer Linear Programs. Cahiers du Centre D’Etudes de Recherche Operationale, 6, Brussels.

Clover, F. 1989. Tabu Search—Part I. ORSA Journal on Computing, 1, 190—206.

Glover, F. 1990. Candidate List Strategies for Tabu Search. School of Business, University of Colorado, Boulder.

Hertz, A. and D. de Werra 1990. The Tabu Search Metaheuristic:

How we use it. Annals of Mathematics and Artificial Intelligence, 1, 111—121.

Johnson, D. 1990. Local Optimization and the Traveling Salesman

Problem. Proceedings of the 17th Annual Colloguium on

Automata, Languages and Programming, Springer—Verlag, 446—

461.

Laguna, M. and F. Glover, 1991. Integrating Target Analysis and Tabu Search for Improved Scheduling Systems. School of Business, University of Colorado, Boulder.

Laguna, M., J. W. Barnes, and F. Glover. 1989. Scheduling Jobs with Linear Delay Penalties and Sequence Dependent Setup Costs and Times Using Tabu Search. Technical Report Series 0RP89—01, Graduate Program in Operations Research, The University of Texas at Austin.

Lin, S., and B.W. Kernighan. 1973. An Effective Heuristic Algorithm for the Traveling Salesman Problem. Operations Research. 21, 498—516.

Or, I. 1976. Traveling Salesman—Type Combinatorial Problems and their Relation to the Logistics of Regional Blood Banking. Doctoral Dissertation, Northwestern University, Evanston, Illinois.

Skorin—Kapov, J. 1991. Extensions of a Tabu Search Adaptation to the Quadratic Assignment Problem, Harriman School Working Paper 90—006, State University of New York at Stony Brook.

Stewart, W.R. Jr. 1987. Accelerated Branch Exchange Heuristics for Symmetric Traveling Salesman Problems. Networks. 17,

423—437.

Taillard, E. 1990. A Robust Tabu Search for the Quadratic Assignment Problem, Research Report ORWP 90/10, D6partement de Mathématiques, Ecole Polytechnique Fédérale de Lausanne.

APPENDIX A

Preliminary Coordination of One—Node and Two—Node Moves

Approaches that incorporate multi—node moves frequently apply them in isolated hierarchies. For example, the popular Or— opt procedure (Or, 1978) inserts a string of successive tour nodes between other adjacent tour nodes, starting first with three—node strings then with two—node strings, and finally with one—node strings. Each string size is treated in its own separate phase. By contrast, we suggest that the preliminary form of our procedure be organized to coordinate the choice among one—node and two—node moves.

Consider first the situation of inserting a given node i between different pairs of adjacent tour nodes p and q, and of inserting the two nodes i and j (of a tour arc (i,j)) between these same alternative pairs. The one—node insert moves relative to node i can be evaluated conveniently in two stages, first calculating d = c(i’,i”) — c(i’,i) — c(i,i”), and then for each arc (p,i) in the reverse star of i, calculating v = d + c(p,i) ±c(i,q) — c(p,q) . (The value v represents the cost difference between the objective functions before and after the insert move. In the undirected case, v is computed be allowing (p,i) to range over all edges in the undirected star of i.)

The same calculation evaluates the associated two—node insert move (based on inserting an arc (i,j) in place of node i), by replacing c(i’,i”) and c(i,i”) in calculating d by c(i’,j”) and c(j,j”), and replacing c(i,q) in calculating v by c(j,q) Thus, in the repetitive v calculation only one more addition is required for each v when both types of insert moves are considered together than when the one—node insert moves are considered by themselves. Calculating the d values for the two types of insert moves simultaneously requires two more additions than in the one—node insert case alone. If one—node exchange moves are evaluated at the same time, the marginal effort of evaluating the exchange moves can be similarly reduced.

Corresponding observations facilitate the evaluation of moves that exchange a pair of nodes with a singleton or another pair.

APPENDIX B

Updating Evaluations for Preferred Attribute Candidate Lists

The evaluations of one—node and two—node insert and exchange moves can be significantly accelerated by exploiting the preferred attribute candidate lists.

First consider insert move updates. For each preferred arc (i,j) maintain two evaluation arrays, evaluationl(i,j) and evaluation2(i,j), which respectively identify the change in the tour cost of inserting node i between j’ and j and of inserting node j between i and i”. (If (i,j) is an arc of the tour, these cost changes are 0, because the insert move is a “null” move.) Designate the nodes i’, i, i”, and p and q to be the spanning nodes of the move (corresponding to definitions introduced in the ejection chain context) . After the insert move is carried out, precisely the following two classes of evaluations need to be recomputed to insure that all entries of the arrays evaluationl() and evaluation2() are correct:

(1) recompute evaluationl(h,s) for each node s in the preferred forward star of h, where h where h ranges over the spanning nodes; (2) recompute evaluation2(r,h) for each node r in the preferred reverse star of h, where h ranges over the spanning nodes; (3) recompute evaluation(r,h) for each r in the preferred reverse star of h, where h ranges over the three nodes i, i” and q; (4) recompute evaluation2(h,s) for all each 5 in the preferred forward star of h, where h ranges over the three nodes i’, i and p.

The evaluations of the two classes of moves (1) and (2) can be recomputed rapidly. In particular, if h denotes any of the spanning nodes then there is an easily identified constant C(h) such that the new value of evaluationl(h,s) and of evaluation2(r,h) in (1) and (2) equals the old value plus C(h), excluding the special cases where s is one of the spanning nodes i, i” or q, or where r is one of the spanning nodes i’, i or p. These special cases are precisely those in which the updates of (1) and (2) may overlap with those of (3) and (4), if the preferred arcs exist that permit such overlaps. (Note that no complications are created by the fact that the same move may be represented by two different evaluations. For example, such a case arises in (1) and (2), for a given h, if r = s’. Then evaluationl(h,s) and evaluation2(r,h) refer to the same move, and both evaluations are appropriately updated by adding C(h) .)

To update the evaluations of insert moves after making an exchange move, the same classes of updates apply. In this case designate i’, i, i”, j’, j, j” to be the spanning nodes. Then the changed evaluations for insert moves (after the indicated exchange move) are given as before, where h ranges over the four nodes i, j, i” and j” in (3), and over the four nodes i, j, i’ and j’ in (4)

These rules also identify the evaluation updates for exchange moves after making either an insert or an exchange move. It is only necessary to change notation so that evaluationl(i,j) and evaluation2(i,j) represent the evaluations for exchanging i with j’, and for exchanging j with i”. However, accelerated updates by reference to a constant C(h) in (1) and (2) are not available. (The situation where adjacent nodes exchange positions, which is also a special instance of an insert move, gives a redundant assignment of identities to nodes by these rules.)

These same principles can be used to generate the “pre-programmed” evaluation for the tightly focused ejection chain procedures, by reference to the spanning nodes explicitly identified in that context.

APPENDIX C

A Supporting Candidate List for Greater Efficiency

In order to exploit the preferred attribute candidate list fully, it is appropriate to organize its elements by reference to another type of candidate list called an elite evaluation candidate list, which is often used on linear programming and network optimization. To adapt such a list to an application of tabu search (Glover, 1990), we note that the complete evaluation of a move has both a variable and a fixed component. The variable component depends on tabu status and other historical information that varies with time, while the fixed component depends on elements such as the objective function change induced by the move.

An elite evaluation (EV) candidate list in the present context may be constructed by recording moves with highest fixed component evaluations, e.g., either the r best or a set whose evaluations pass a specified threshold. Specifically, we create such a list to augment the preferred attribute candidate list by recording the preferred arcs that give best values of evaluationl(i,j) and evaluation2(i,j) as defined in Appendix B. This list may further be stratified to isolate ranges of evaluations whose components are to be treated as essentially identical.

We differentiate between “standard” evaluations and “complete” evaluations, i.e., which take tabu status into account. The purpose of the EV candidate list is to permit only a subset of preferred arcs to be scanned to determine one with a best complete evaluation. The management of the list is designed to minimize the chances that an element not on the list will have an appreciably better complete evaluation than the best on the list. This may be accomplished by the following strategy.

In the same way that we differentiate between evaluations and complete evaluations, we differentiate between best and true best moves (where the latter are based on complete evaluations)

EV Strategy

Step 1. (Build the list.) By reference to the currently updated values evaluationl(i,j) and evaluation2(i,j), etc., for the preferred arcs (i,j), record the b* true best moves (e.g., b~ = 20 to 100) . That is, for b = 1, ... ,b* store the values type(b), arc(b) and key(b), that respectively identify the type of move (one—node or two—node insert, one or two—for—one exchange, etc.), the preferred arc that (partially) defines the move (e.g., (an arc (i,j) such that i (or j) is to be inserted or exchanged to become the new predecessor of j (successor of i)), and the key (e.g.) a value 1 or 2) that tells whether the move is associated with evaluationl(i,j) or evaluation2(i,j) (hence whether i or j is the node to become the new predecessor or successor of the other)

Step 2. (Scan and select) . For i~ consecutive iterations after the EV list is constructed (e.g., for i’= 6 to 20), select the true best move from the list. On the iteration that the list is constructed, this move will be known. Afterward, each move on the list must be reevaluated accessing (or calculating) the current correct associated value of evaluationl(i,j) or evaluation2(i,j), and taking current tabu status into consideration.

Step 3. (List expansion) . During the i~ iterations that choices are made from the EV list, expand the list by reference to the restricted subset of moves whose evaluations change, as identified in the preceding section. As evaluationl() and evaluation2() values are updated, add the 3 to 5 true best of the associated moves to the EV list. (The same move may appear more than once on the list. To compensate for the expansion, a similar set of “worst” current moves can be dropped from the list as new moves are added.) Once i~ iterations have elapsed, the method returns to Step 1 to rebuild the list.

When building the list in Step 1, it is preferable that no single node contributes to more than a few of the moves on the list. One way to assure this is to build the list by screening the preferred node stars. As each preferred star is examined in succession, only the 3 to 5 true best moves associated with the node are considered for inclusion among the moves recorded on the EV list.

Uses of Nesting

Computational savings also may result by nesting the strategy used to create and process the list. For example, initially the 6 best of the b * moves may be isolated, and for the first 3 iterations only these moves are considered as candidates (except for allowing superior moves from Step 3 to replace them) Then the full EV list is scanned, again picking up the 6 best current moves and repeating.

For both the full procedures and the nested procedure, the number of iterations before rebuilding the current list of candidates can be controlled in an additional way. In particular, the list should be reconstructed whenever the best evaluation falls below a preferred threshold level, which itself can depend on the number of elapsed iterations. For example, the history of the search when using a small f value (and an “ample” candidate list) may suggest that non—tabu improving moves usually should be found after a string of (say) p = 3 to 6 nonimproving moves, and that the number of consecutive improving moves should fall in an associated range (e.g., as a function of p) . Then any significant departure from these conditions may be a signal that the list should be rebuilt. Alternative conditions can be identified relative to the magnitude of improvement or dis-improvement.

The potential value of such refinements may be indicated by comparing EV candidate list procedures using both small and “normal” i~ values, running each for the same number of iterations.

APPENDIX D

Network Relaxations for Election Chains

The procedures described for generating ejection chains may be interpreted as methods for seeking (approximate) shortest paths and cycles in a network אwhose arcs are implicitly defined by the various move types (top extensions, bottom extensions, anchors, caps, and their combinations) . In order for the paths and cycles in א to give rise to valid transformations creating new tours (or feasible solutions), they must satisfy the constraints embodied in the definitions of legitimacy. Alternately, they must entail a progressively amended specification of the identity (and hence cost) of an arc in אdepending on the arcs preceding the given arc in a path under construction, as in the QAP form of adaptation.

This observation suggests the possibility of a relaxation strategy to exploit the network א. Arcs of א are created in advance (as implicitly occurs in the focused methods), and standard network procedures are applied (with minimal modification) to identify shortest paths or cycles. In the TSP setting, shortest paths begin with an anchor and end with a cap, and can be represented by creating a source node in א to initiate all anchors and a sink node to terminate all caps.

Arcs of א associated with top extensions correspond to the operation of moving an element (or node in the TSP context) out of its current location and into the location most recently occupied by another element. The tail node of the arc identifies the previous top element and the head node identifies the new top element. Special arcs to initiate an ejection chain (other than by anchoring) and to complete a cycle in א (by circularization) can be avoided, if desired, by redefining a starting chain to be the same configuration as produced by a top extension move. This means the “bottom element” of an ejection chain remains in its original position until the cycle is complete (whereon it also becomes a top element).

Paths and cycles in א thus are readily mapped into corresponding ejection chains, which may be evaluated to determine their true cost. In the TSP context, if the chain satisfies the definition of legitimacy, this cost will be the same as the length of the associated path or cycle in א The merit of a network relaxation strategy depends on the degree of distortion when path distances serve as proxies for true costs.

Conceiving ejection chains as paths and cycles in a network א allows the possibility to incorporate the procedures of the paper in other embedded neighborhood contexts. The convenience of the ejection chain construction, and the natural manner in which it adapts to different settings suggests the relevance of hybrid neighborhoods that interweave these chains with moves based on alternative constructions.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download