European Journal of Operational Research 59 (1992) 231-247 231

North-Holland

Invited Review

The Traveling Salesman Problem:

An overview of exact
and approximate algorithms
Gilbert Laporte
Centre de recherche sur les transports, Universit~ de Montr&l, C.P. 6128, Station A, Montreal, Canada H3C
M7

Received May 1991; received July 1991

Abstract: In this paper, some of the main known algorithms for the traveling salesman problem are
surveyed. The p a p e r is organized as follows: 1) definition; 2) applications; 3) complexity analysis; 4) exact
algorithms; 5) heuristic algorithms; 6) conclusion.

Keywords: Traveling salesman problem; survey

Introduction C : (Cij) be a distance (or cost) matrix associated

with A. The TSP consists of determining a mini-
The Traveling Salesman Problem (TSP) is one m u m distance circuit passing through each vertex
of the most widely studied combinatorial opti- once and only once. Such a circuit is known as a
mization problems. Its statement is deceptively tour or Hamiltonian circuit (or cycle). In several
simple, and yet it remains one of the most chal- applications, C can also be interpreted as a cost
lenging problems in Operational Research. Hun- or travel time matrix. It will be useful to distin-
dreds of articles have been written on the TSP. guish between the cases where C (or the prob-
The book edited by Lawler et al. (1985) provides lem) is symmetrical, i.e. when c u = cyi for all
an insightful and comprehensive survey of all i,j ~ V, and the case where it is asymmetrical.
major research results until that date. The pur- Also, C is said to satisfy the triangle inequality if
pose of this survey p a p e r is less ambitious. Our and only if Cij q- Cjk ~ Cik for all i,j,k ~ V. This
main objective is to present an integrated overview occurs in Euclidean problems, i.e. when V is a set
of some of the best exact and approximate algo- of points in ~2 and c~ is the straight-line dis-
rithms so far developed for the TSP, at a level tance between i and j.
appropriate for a first graduate course in combi-
natorial optimization.
2. Applications

I. Definition The most common practical interpretation of

the TSP is that of a salesman seeking the shortest
Let G = (V, A) be a graph where V is a set of tour through n clients or cities. This basic prob-
n vertices. A is a set of arcs or edges, and let lem underlies several vehicle routing applications,

0377-2217/92/$05.00 © 1992 - Elsevier Science Publishers B.V. All rights reserved

232 G. Laporte / The travefing salesman problem: Overview of algorithms

but in this case a number of side constraints to 20. Players throw darts at target points on the
usually come into play (see Laporte, 1992). Sev- board. In the most common version of the game,
eral interesting permutation problems not di- the objective is to reduce an initial value of 301 to
rectly associated with routing can also be de- zero by substracting scores. The game rewards
scribed as TSPs. H e r e are some selected exam- accuracy in the throw and it is often more impor-
pies. tant to hit one's target that to merely register a
1. C o m p u t e r wiring (Lenstra and Rinnooy Kan, large score. A natural objective for designing a
1975). Some computer systems can be described dartboard is therefore to position the 20 numbers
as modules with pins attached to them. It is often around the board so as to maximize players' risk.
desired to link these pins by means of wires, so For fairly accurate players, it is reasonable to
that exactly two wires are attached to each pin assume that the sector that is hit is always the
and total wire length is minimized. targeted sector or its neighbour. Let ~ - =
2. Wallpaper cutting (Garfinkel, 1977). Here, n (rr(1) . . . . . ¢r(20)) be any permutation of the num-
sheets must be cut from a roll of wallpaper on bers 1. . . . . 20. In what follows, ~-(k) must be
which a pattern of length 1 is repeated. For sheet interpreted as ~-(k mod 20) whenever k < 1 or
i, denote by a i and b i the starting and ending k > 20. Consider a player aiming at ~-(k) and
points on the pattern, where 0 ~<a i ~< 1 and 0 ~< b i hitting 7r(k + 1) with probability p, and 7r(k)
1. Then cutting sheet j immediately after sheet with probability 1 - 2p. For this player, the ex-
i results in a waste of pected deviation from the aimed score is equal to
p [ ~ r ( k - 1) - 7r(k)] +p[Tr(k + 1) - or(k)]. A pos-
aj - b i if b i <~aj, sible objective is to maximize the expected sum of
cij = ~ 1 + a t - b i if b i > a j . (1) square deviations, i.e. Y'.2°a{p[~-(k - 1) - 7r(k)] 2
+ p [ T r ( k + 1)-Tr(k)]2}. Since p is a constant,
The objective is to order the n sheets so as to this is equivalent to solving a TSP with cii = (i -
minimize total waste. In order to define the prob- j)2.
lem as a TSP, consider a dummy sheet n + 1 with 6. C r y s t a l l o g r a p h y (Bland and Shallcross,
C i , n + 1 = 0 and cn+ 1,~'= 0 for all i , j = 1 . . . . . n. A l - 1989). In crystallography, some experiments con-
ternatively, define bn+ 1 as the end of the roll sist of taking a large number of X-ray intensity
position at the start of cutting and assume that measurements on crystals by means of a detector.
after the last sheet, a final cut must be made to Each m e a s u r e m e n t requires that a sample of the
restore the row to its original position. Then crystal be mounted on an apparatus and that the
an+ 1 = b , + l , and cij can be defined as in (1) for detector be positioned appropriately. The order
all i , j = 1 . . . . . n + 1. in which the various measurements on a given
3. Hole p u n c h i n g (Reinelt, 1989). In several crystal are made can be seen as the solution of a
manufacturing contexts, it is necessary to punch TSP. In practice, these problems are of large
holes on boards or metallic sheets. The problem scale and obtaining good TSP solutions can re-
consists of determining a minimum-time punch- duce considerably the time needed to carry out
ing sequence. Such a problem occurs frequently all measurements.
in metallic sheet manufacturing and in the con-
struction of circuit boards. These problems are
often of large scale and must be solved in real- 3. Complexity
time.
In order to study the complexity of the travel-
4. Job sequencing. Suppose n jobs must be
ing salesman problem first consider the following
performed sequentially on a single machine and
well-known decision problem:
that cij is the change-over time if job j is exe-
cuted immediately after job i. Then again, by H A M I L T O N I A N C I R C U I T (HC)
introducting a dummy job, this problem can be Instance: A graph G = (V, A).
formulated as a TSP. Question: Does G contain a Hamiltonian circuit?
5. D a r t b o a r d design (Eiselt and Laporte, 1991).
Dartboards are circular targets with concentric It is well known that H C is NP-complete (Garey
circles, and 20 sectors identified by the numbers 1 and Johnson, 1979, p. 47). We show that TSP is
 G. Laporte / The traveling salesman problem: Overview of algorithms 233

NP-hard by using the following transformation. (i, j), equal to 1 if and only if (i, j) is used in the
Given any instance of H C relative to a graph optimal solution, i =~j. The DFJ formulation is
G h = ( V h, A h) with vertex set V h = {1 . . . . . n} and (DFJ)
arc set A h = {(i, j)}, define a TSP instance having
V = V h, A = { ( i , j ) : i , j = l , . . . , n , i4=j} and cii Minimize ~ cijxij (2)
= 1 if (i, j) ~ A h and cir = m, otherwise. Then G i4=j
contains a Hamiltonian circuit if and only if the subject to ~_~ xij = 1, i = 1 . . . . , n, (3)
optimal value of the TSP instance is equal to n. j=l
n
A number of special cases of TSP are, how-
ever, solvable in polynomial time (see, for exam- ~ X i j = 1, j = 1 . . . . . n, (4)
ple, Gilmore, Lawler and Shmoys, 1985). Exam- i-1
ples of such problems include: £ Xij< I S I - 1 ,
1. TSPs where C = (cij) is an upper triangular i,j~s
matrix, i.e. cij = 0 for all i > j ; ScV, 2 ~ IS] ~ < n - 2 , (5)
2. The wallpaper cutting problem described in
Section 2;
xij ~ {0, 1},
3. A class of job sequencing problems defined i, j = 1 . . . . . n, i :~j. (6)
by Gilmore and G o m o r y (1964). In this problem,
In this formulation, the objective function
there are n - 1 jobs to be processed sequentially
clearly describes the cost of the optimal tour.
in a kiln. Job i requires a starting t e m p e r a t u r e of
Constraints (3) and (4) are degree constraints:
a i and must be finished at t e m p e r a t u r e b i. Fur-
they specify that every vertex is entered exactly
ther assume that the initial kiln t e m p e r a t u r e is a n
once (3) and left exactly once (4). Constraints (5)
and that the final t e m p e r a t u r e must be b n. Then
are subtour elimination constraints: they prohibit
the problem can be formulated as a TSP with
the formation of subtours, i.e. tours on subsets of
less than n vertices. If there was such a subtour
on a subset S of vertices, this subtour would
cij contain I S I arcs and as many vertices. Constraint
ifa <.bi (5) would then be violated for this subset since its
-¢1i left-hand side would be equal to I S[ and its
right-hand side equal to IS I - 1. Because of de-
where f and g are cost density functions and gree constraints, subtours over one vertex (and
f ( x ) + g ( x ) > 0 for all x since otherwise, it would hence, over n - 1 vertices) cannot occur. There-
be profitable to keep changing the kiln tempera- fore it is valid to define constraints (5) for 2 ~<
ture. I S I ~< n - 2 only. Finally, constraints (6) impose
binary conditions on the variables.
An alternative equivalent form of constraints
4. E x a c t a l g o r i t h m s (5) is

A large n u m b e r of exact algorithms have been £ £Xij>/1 ScV, 2 < ISl < n - 2 (5')
i~S j ~ 3
proposed for the TSP. These can be best under-
stood and explained in the context of integer where S = V \ S . Constraints (5') can be derived
linear programming (ILP). We examine in this from (5) by noting that every vertex i of S is the
section a number of ILP formulations and of origin of one arc to another vertex of S or to a
algorithms derived from these formulations. vertex of S. Since there are [SI vertices, I S[ =
~i,j~sXij at- ~i~S~j~_~Xij, and the equivalence of
4.1. Integer linear programming formulations (5) and (5') follows trivially. The geometric inter-
pretation of connectivity constraints (5') is that in
One of the earliest formulations is due to every TSP solution, there must be at least one arc
Dantzig, Fulkerson and Johnson (DFJ) (1954). It pointing from S to its complement, in other
associates one binary variable x/j to every arc words, S cannot be disconnected.
234 G. Laporte / The traveling salesman problem: Overview of algorithms

This formulation contains n ( n - 1) binary vari- - if xji = 0, then (10) is satisfied for any aji;
ables, 2n degree constraints and 2 n - 2n - 2 sub- - ifxji=l, thenxij=0(forn>2) anduj+l
tour elimination constraints. Even for moderate = u i, so that aji <~n - 3.
values of n, it is unrealistic to solve DFJ directly In spite of its relative compactness, the M T Z
by means of an ILP code. The model is usually formulation is weaker than the DFJ formula-
relaxed, and solved by means of specialized algo- tion in the following sense. D e n o t e by
rithms. z '(DFJ)[ z'(MTZ)] the optimal value of the linear
Miller, Tucker and Zemlin (MTZ) (1960) have relaxation of DFJ [MTZ], i.e. the relaxation ob-
proposed an alternative formulation that reduces tained by dropping integrality conditions. Then
the number of subtour elimination constraints at z ' ( M T Z ) ~<z ' ( D F J ) ( W o n g , 1980). This result has
the expense of extra variables u i (i = 2 . . . . . n). not been proved for the modified M T Z formula-
The M T Z subtour elimination constraints can be tion using constraints (9), but it is known that
expressed as there exist cases where it produces a weaker
linear relaxation than DFJ (Desrochers and La-
Ui -- Uj + ( n - 1 ) x i j <~n - 2
porte, 1991).
i, j = 2 . . . . , n , i 4:j, (7) Finally, a number of alternative formulations
l<~ui<~n-1 i = 2 . . . . . n. (8) have been proposed and compared, but none of
these seems to have a stronger linear relaxation
Constraints (7) ensure that the solution con- than DFJ (Langevin, Soumis and Desrosiers,
tains no subtour on a set of vertices S c_ V\{1} 1990).
and hence, no subtour involving less than n ver-
tices. Constraints (8) ensure that the u i variables 4.2. The assignment lower b o u n d and related
are uniquely defined for any feasible tour. In b r a n c h - a n d - b o u n d algorithms
order to see how constraints (7) operate, suppose
there was a subtour (il, i 2 . . . . . i k , il) with k < n. Branch-and-bound (BB) algorithms are com-
Writing constraints (7) for every arc of that sub- monly used for the solution of TSPs. In the
tour gives context of mathematical programming, they can
Uil--Ui2+ ( n - 1) ~<n - 2 , best be viewed as initially relaxing some of the
problem constraints, and then regaining feasibil-
l,li2--Ui3+ ( n -- 1) -<<n - 2, ity through an enumerative process. The quality
of a BB algorithm is directly related to the quality
of the bound provided by the relaxation.
u i k - ui, + ( n - 1) ~ n - 2. For the TSP, an initial lower bound can be
obtained from the DFJ formulation by relaxing
Summing up these constraints yields k ( n - 1) ~<
constraints (5). The resulting problem is an as-
k ( n - 2), a contradiction.
signment problem (AP) which can be solved in
It has been observed recently (Desrochers and
O ( n 3) time (see Carpaneto, Martello and Toth,
Laporte, 1991) that constraints (7) can be
1988). Thus, a valid lower bound on the value of
strengthened by introducing an extra term in
the optimal TSP solution is the AP bound de-
their left-hand side to yield
fined by (2)-(4) and the nonnegativity require-
U i -- Uj @ ( n - 1)Xij + ( n - 3)Xji <~n -- 2 ments on the variables.
i,j=Z,...,n, i~j. (9) Several authors have proposed BB algorithms
for the TSP, based on the AP relaxation. These
The validity of constraints (9) can be estab- include Eastman (1958), Little et al. (1963),
lished as follows. Rewrite constraints (7) as Shapiro (1966), Murty (1968), Bellmore and Mal-
u i - uj + ( n - 1)Xij + oljiXji ~ n - 2 (10) one (1971), Garfinkel (1973), Smith, Srinivasan
and Thompson (1977), Carpaneto and Toth
where currently o Q i = O. We seek the largest pos- (1980), Balas and Christofides (1981) and Miller
sible value of aji so that (10) remains a valid and Pekny (1991). We briefly describe the last
inequality. In the optimal solution, xji can take three algorithms which are probably the best
only two values: available.
 G. Laporte / The traveling salesman problem." Overview of algorithms 235

In the Carpaneto and Toth algorithm, the Execute Step 4-6 for r = 1,..., s.
problem solved at a generic node of the search Step 4. (Bounding.) Compute a lower bound
tree is a modified assignment problem (i.e. x , is Zhr on Zhr by row and column reduction of the
fixed at 0 for all i) in which s o m e x i j variables cost matrix. If Zhr < Z *, proceed to Step 5. Other-
are fixed at 0 or at 1. If the AP solution consists wise, consider the next r and repeat Step 4.
of a unique tour over all vertices, it is then Step 5. (Subproblem solution.) Solve the sub-
feasible for the TSP. Otherwise, it consists of a problem associated with node h r (a modified A P
number of subtours. One of these subtours is restricted by Ih, and Ehr). If Zh~>Z*, consider
selected and broken by creating subproblems in the next r and proceed to Step 4.
which all arcs of the subtour are in turn prohib- Step 6. (Feasibility check). Check whether the
ited. We will use the following notation: current solution contains subtours. If it does,
z*: the cost of the best TSP solution so far insert node h r in the queue. Otherwise, set z* :=
identified; Zhr and store the tour, if z* = z h, go to Step 2.
zh: the value of the objeiztive function of the
modified AP at node h of the search tree; Using their algorithm, Carpaneto and Toth
Zh: a lower bound on Zh; have consistently solved randomly generated
Ih: the set of included arcs (x~j variables fixed 240-vertex TSPs in less than one minute on a
at 1) at node h of the search tree; C D C 6600. The main limitation of this algorithm
Eh: the set of excluded arcs (xij variables fixed appears to be computed memory rather than
at O) at node h of the search tree. CPU time.
The Balas and Christofides algorithm uses a
s t r o n g e r relaxation than the AP relaxation. Its
Step 1. (Initialization.) Obtain a first value for
description and the computational effort required
z * by means of a suitdble heuristic. Create node
for the lower-bound computations are much more
1 of the search tree: set I 1 := E 1 := ~, and obtain
involved, but the resulting search trees are smaller
z~ by solving the associated modified AP. If z~ >/
and the procedure is overall more powerful. Due
z*, stop: the heuristic solution is optimal. If the
to its complexity, it will only be sketched here.
solution contains no illegal subtours, it consti-
Interested readers are referred to the Balas and
tutes the optimal tour: stop. Otherwise, insert
Christofides (1981) paper. In addition to con-
node 1 in a queue.
straints (3), (4) and (6), subtour elimination con-
Step 2. (Node selection.) If the queue is empty,
straints (5), connectivity constraints (5') and some
stop. Otherwise, select the next node (node h)
positive linear combinations of these are consid-
from the queue: here we use a breadth first rule,
ered, and introduced into the objective function
i.e. branching is always done on the pendant
in a Lagrangean fashion. Let T be the set of all
node having the lowest z h.
such constraints and t a given constraint. Their
Step 3. (Subproblem partitioning.) The solution
generic expression can be written as
obtained at node h is illegal and must be elimi-
nated by partitioning the current subproblem into y' ,
aijxij ~ ao, t ~ T.
descendant subproblems hr characterized by sets i,j~ V
Ihr and Eh; In order to create these subproblems,
The Lagrangean objective is then
consider a subtour having the least number s of
arcs not belonging to I h. Let these arcs be
(i 1, j~) . . . . . (i,, j~), in the order in which they L( A):min( E c i j x i j - E A,
x
a p p e a r in the subtours. Then create s subprob- i,j~V t~T
lems with

1k, r=l, ~ i,j~ V

I
Ih = l l h u { ( i , , , j ~ ) : u = l ..... r--i}, where A = (A 1. . . . . Ar ) is the vector of Lagrange
r=2,...,s, multipliers, and x is any modified AP solution.
The strongest relaxation is given by maxa~ 0
Eh = E h U { ( i r , j r ) } , r = l . . . . . s. {L(A)}. As the n u m b e r of components of A is
236 G. Laporte / The traveling salesman problem: Overview of algorithms

exponential, the required maximum is not deter- The authors prove the following proposition
mined by Lagrangean relaxation. Instead, a lower which they use as a basis for their algorithm: an
bound on its value is obtained by restricting A to optimal solution for TSP' is optimal for TSP if
lie in the set {A > 0: Zlu,v ~ ~n, such that u~ + v/
+ S , t ~ r A t a~j=cij if (i, j) belongs to the AP z*(TSP') -z*(AP) ~<A + 1 - u ; - V ' ~ x (16)
solution; u~ + v/+ E t ~ r A t a~j > c~j, otherwise}.
Balas and Christofides propose an approximation and
procedure for computing A. At a given node of
! r
the search tree, the procedure solves an AP with a + 1- u i - Uma x ~ 0 (17)
dual values given by u and v. It then computes A.
A lower bound on the value of the TSP tour for i = 1. . . . ,n, where u' and v' are optimal
associated to that node of the search tree is given solutions to DAP', and V'ax is the maximum
by element of v'. The quantity A + 1 - u~ - Vmax un-
derestimates the smallest reduced cost of any
Eui + E vj+ EAt a°. (12) discarded variable. The algorithm is then:
i~V j~V t~T Step 1 (Initialization). Choose A.
Step 2 (TSP' solution). Construct (ci~) and solve
The authors then show how (12) can be com- TSP'.
puted for three particular classes of constraints Step 3 (Termination check). If (16) and (17) hold,
(11). Using this procedure, Balas and Christofides then z * ( T S P ' ) = z * ( T S P ) : stop. Other-
report optimal solutions to randomly generated wise, double A and go to Step 2.
325-vertex problems in less than one minute on a
CDC 7600.
More recently, Miller and Pekny have pro- The authors report that if A is suitably chosen
posed a new powerful BB algorithm based on the in Step 1 (e.g., the largest arc cost in a heuristic
AP relaxation. Consider the dual AP: solution), there is rarely any need to perform a
(DAP) second iteration. To solve TSP', the authors have
developed a BB algorithm based on the AP relax-
n n
ation. They have applied this procedure to ran-
Maximize ~_, u s + ~., vj (13)
domly generated problems. Instances involving
i=1 j=l
up to 5000 vertices were solved within 40 seconds
subject to eij - u i - vj >~O on a Sun 4 / 3 3 0 computer. The largest problem
i,j=l,...,n, i~j. (14) reported solved by this approach contains 500000
vertices and required 12623 seconds of computing
Denote by z*(TSP) the optimal TSP solution time on a Cray 2 supercomputer.
value, by z * ( A P ) the optimal value of the AP Finally, it is worth mentioning that in a differ-
linear relaxation, and by z * ( D A P ) the optimal ent paper, Miller and Pekny (1989) describe a
value of the dual AP linear relaxation. Clearly parallel branch-and-bound algorithm based on
z * ( A P ) = z*(DAP). Moreover, note that z * ( A P ) the AP relaxation. These authors report that ran-
+ (c~j- u i - v j ) is a lower bound on the cost of domly generated asymmetrical TSPs involving up
an AP solution that includes arc (i, j). Miller and to 3000 vertices have been solved to optimality
Pekny make use of this in an algorithm that using this approach.
initially removes from consideration all x~j vari-
ables whose cost c~j exceeds a threshold value A.
Consider a modified problem TSP' with associ- 4.3. The shortest spanning arborescence bound and
ated linear assignment relaxation A P ' and its a related algorithm
dual DAP', obtained by redefining the costs ci~
as follows:
In a directed graph G = (F, A), an r-arbores-
cence is a partial graph in which the in-degree of
, [c~j ifc,y<A,
each vertex is exactly 1 and each vertex can be
Cij = (15)
otherwise. reached from the root vertex r. The shortest
 G. Laporte / The travelingsalesman problem. Overviewof algorithms 237

spanning r-arborescence problem (r-SAP) can be on the type of problem considered. For the easi-
formulated as est problem type, the authors report having solved
(r-SAP) 2000-vertex problems in an average time of 8329
seconds on an H P 9000/840 computer.
Minimize cijxij (18)
i~j 4.4. The shortest spanning tree bound and related
algorithms
subject to ~ xij = 1, j = 1 . . . . . n, (19)
i=1 The AP-based algorithms described in the pre-
i~j
vious section are valid whether C is asymmetrical
E ~-,xij>>-l, S c V ; r ~ S , (20) or symmetrical. However, in the latter case, the
i~S j ~ ,
AP solutions will in general contain several sub-
xij>~O,i,j=l ..... n,i-~j. (21) tours containing only two vertices, resulting in
The problem of determining a minimum-cost excessive computing times for their elimination.
r-arborescence on G can be decomposed into two Symmetrical problems are better handled by spe-
independent subproblems: determining a mini- cialized algorithms that exploit their structure.
mum-cost arborescence rooted at vertex r, and We now describe an ILP formulation for symmet-
finding the minimum-cost arc entering vertex r. rical TSPs.
The first problem is easily solved in O(n 2) time Consider a TSP defined on G = (V, E ) where
(Tarjan, 1977). This relaxation can be used in E is an edge set. Let xij be a binary variable
conjunction with Lagrangian relaxation. How- equal to 1 if and only if edge (i, j) is used in the
optimal Solution. These variables are only defined
ever, on asymmetric problems, the AP relaxation
for i < j. The formulation is then
would a p p e a r empirically superior to the r-
(SYM)
arborescence relaxation (Balas and Toth, 1977).
An early reference to this lower bound is made Minimize ~ CijXij
by Held and Karp (1970). More recently, Fis- i<j
chetti and Toth (1991) have used it within a subject to ~ xik + ~ xkj = 2, (24)
so-called 'additive bounding procedure' that com- i<k j>k
bines five different bounds: k = 1 . . . . . n, (25)
- the AP bound,
E Xij• ISI-1,
- the shortest spanning 1-arborescence bound, ijEs (26)
- t h e shortest spanning 1-antiarborescence
bound 1 - SAAP; (r-SAAP is defined in a man- ScV, 3~[SI ~<n-3,
ner similar to r-SAP but now it is required that xij ~ {0, 1}, (27)
vertex r should be reached from every remaining i,j=l . . . . . n, i < j .
vertex),
In this formulation, constraints (25) specify
- for r = 1 . . . . . n, a bound r-SADP obtained
from r-SAP by adding the constraint that every vertex has a degree of 2. Constraints
(26) are subtour elimination constraints. They
xrj = 1, (22) need not be defined for I SI = 2 and n - 2 since
j~r constraints (25) and (27) combined prevent the
- for r = 1 , . . . , n, a bound r - S A A D P obtained formation of subtours involving 2 (and thus n - 2)
from r-SAAP by adding the constraint vertices. Constraints (27) impose binary condi-
tions on the variables.
E Xir = 1. (23) As for (DFJ), connectivity constraints equiva-
i¢r
lent to (26) can be derived. These can be written
The lower-bounding procedure described by as
Fischetti and Toth was e m b e d d e d within the
Carpaneto and Toth (1980) branch-and-bound al- ~_~ xij>~2 , ScV, 3~< ISI ~ < n - 3 .
gorithm on a variety of randomly generated prob- i~S,j~S
or j~S,i~'S
lems and on some problems described in the
literature. The success of the algorithm depends (26')
238 G. Laporte / The traveling salesman problem: Overview of algorithms

In order to show the equivalence of (26) and redundant) to impose (27) for these values of
(26'), consider D(S) = )'~k~S(Ei<kXik + ~'j>k IsI.
Xk), the sum of degrees of vertices of S. Every Christofides (1970) and Held and Karp (1971)
edge (i, j) for which i,j ~ S makes a contribution were among the first to propose a TSP algorithm
of 2 to D(S), whereas edges (i, j) with i ~ S, based on this relaxation. Improvements and re-
j ~ S or j ~ S, i ~ S contribute by only one unit. finements were later suggested by Helbig Hansen
Hence, and Krarup (1974), Smith and Thompson (1977),
Volgenant and Jonker (1982), Gavish and
o ( s) = 2 E x,j + E x j, Srikanth (1986), and Carpaneto, Fischetti and
i,jeS iES,j~'S Toth (1989). In the original Held and Karp algo-
orjeS,i~S
rithm, the 1-SST bound is reinforced by introduc-
and the equivalence follows. ing constraints (25) in the objective function to
A useful relaxation can be extracted from SYM yield the Lagrangean
by exploiting the following consideration. In any
feasible solution, the degree of vertex 1 must be L(A) = min E CijXij
equal to 2, while the remaining vertices must all x i <j
be connected. A valid lower bound on the opti-
mal TSP solution value is therefore the length of
the shortest 1-spanning tree (1-SST), i.e. the k~V "i<k j>k
shortest tree having vertex set V\{1}, together
with two distinct edges at vertex 1. Formally, = m i n { Y'. E(cij--}-Ai+Aj)xij)
determining a least cost 1-SST is achieved by x i~Vj>i
solving -- 2 )-'~ Ai,
(1-SST) i~v

Minimize ~ cijxij (28) where x is a feasible 1-SST solution. By perform-

i<j ing dual ascents, Held and Karp obtain a lower
bound on the strongest Lagrangean relaxation
subject to ~ xiy = n, (29)
i<j max~{L(a)}. This bounding process is embedded
in a branch-and-bound scheme in the following
~ Xlj = 2, (30) manner. First define
j=2 z*: the cost of the best TSP solution so far
E Xij~ 1, identified;
i~S,j~S\{1} Zh: the best lower bound on max~{L(h)} de-
or j~S,i~S\{1} rived at node h of the search tree;
ScV\{1}, 1 < ISl < n - l , hh: the value of A yielding Zh;
Ih: the set of included edges at node h of the
(31) search tree;
Xij ~ {0, 1}. (32) Eh: the set of excluded edges at node h of the
search tree.

However, in practice the 1-SST problem is Step 1 (initialization). Obtain a first value for
better solved by means of a specialized algorithm z* by means of a suitable heuristic. Create node
(see Aho, Hopcroft and Ullman, 1974). This for- 1 of the search tree: set 11 := E 1 := ¢. Obtain z 1
mulation is clearly a relaxation of SYM. Indeed, and h 1 by performing Lagrangean ascents, start-
constraint (29) is obtained by taking half the sum ing with h =(0). If Zl>iZ*, stop: the heuristic
of constraints (25); constraint (30) is constraint solution is optimal. If the solution consists of a
(25) for k = 1, and constraints (31) are a weaker tour, it is feasible and optimal: stop. Otherwise,
form of (26'). The fact that these constraints are insert node 1 in a queue.
also imposed for t S[ = l , 2 , n - 2 a n d n - 1 is of Step 2 (Node selection). If the queue is empty,
no concern since it would have been valid (and stop. Otherwise, select the next node (node h)
 G, Laporte / The traveling salesman problem: Overview o f algorithms 239

from the queue on with to branch: select h with 4.5. The 2-matching lower bound and related algo-
the least lower bound z h. rithms
Step 3 (Subproblem partitioning). Rank the
edges e l , . . . , ep of E \ ( I h U E h) according to the The 2-matching relaxation of the TSP is ex-
amount by which z h would increase if the edge tracted from SYM by omitting constraints (26). It
was excluded. In other words, if h r w a s a node of provides a lower bound on the value of the opti-
the search tree with Ih, = I h and E h , = E h k.) {er} , mal TSP solution. This relaxation can then be
then z h >~z h >1 . . . >~z h . The sets of included
1 2 p • • •
embedded in an optimization algorithm by first
and excluded arcs in subproblems originating from solving the linear relaxation of the 2-matching
node h are problem, and by then gradually introducing vio-
lated subtour elimination constraints and inte-
grality constraints. The principles behind this
Ih~ = Ih, Eh~ = E h t_) {el} ,
method were first laid out in the seminal papers
Ih2 = I h U {el}, Eh2 = g h U {e2}, by Dantzig, Fulkerson and Johnson (1954, 1959).
Ih3=IhU{el, e2}, Eh3=EhU{e3}, This work was followed by that of Martin (1966)
and of Miliotis (1976, 1978). It was Miliotis who,
to our knowledge, developed the first completely
Ihs=Ih U { e l , . . . , e s _ l } , Ehs=Eh L)RiUR j
automatic procedure for solving symmetrical TSPs
using this relaxation. He proposed several algo-
rithms that differ in the order in which the vio-
where s ~<p is the smallest index for which there lated constraints are introduced and in the way
exists a vertex i such that Ih, does not contain integer solutions are reached. One of these is a
two edges incident to i, but Ih~+, does; there may pure cutting planes algorithm:
exist another vertex j possessing this property. R i
is the set of all edges incident to i and not in Ihs. Step 1 (First subproblem). Solve a first sub-
Execute Step 4 and 5 f o r r = 1. . . . . s. problem defined by (24), (25) and 0 ~<xii ~< 1 (i, j
Step 4 (Bounding). Compute Zh, starting with = 1 , . . . , n, i <j). If the solution is feasible, stop.
Ah. If zh < z * , proceed to Step 5. Otherwise, If the solution is infeasible but integer, go to Step
consider the next r and repeat Step 4. 3.
Step 5 (Feasibility check). If the solution ob- Step 2 (Reoptimization). Regain optimality by
tained at node h, is not a tour, insert node h r in introducing Gomory cutting planes (Gomory,
the queue. Othogwise, set z * := Zh, and store the 1963) and by reoptimizing. If the solution is feasi-
tour; if z* = z h, go to Step 2. ble, it is also optimal: stop.
Step 3 (Subtour elimination). Eliminate one or
several subtours by introducing the appropriate
Using this procedure, H e l d and Karp (1971) subtour elimination constraint(s). Reoptimize. If
have solved a number of classical TSPs with very the solution is not integer, go to Step 2. If the
limited branching. Helbig Hansen and Krarup solution is integer and contains subtours, repeat
(1974) have improved upon the original algorithm Step 3.
by a more judicious choice of parameters in the
ascent procedure. Volgenant and Jonker (1982) A variant of this problem consists of reaching
have experimented with a new ascent procedure, integrality by branch and bound. Subtour elimi-
upper-bound computations in the branch-and- nation constraints are then introduced in individ-
bound tree, and new branching schemes. Gavish ual subproblems through the branching process.
and Srikanth (1986) use fast sensitivity analysis These constraints remain, however, valid for the
techniques to increase the underlying graph spar- whole of the branch-and-bound tree.
sity and reduce the problem size. More recently, As indicated by Miliotis, the two steps that
Carpaneto, Fischetti and Toth (1989) have sug- consists of checking for integrality and then for
gested a number of further improvements to the violated subtour elimination constraints can be
Held and Karp lower bound by making use of an interverted, leading to a stronger algorithm. It
additive bounding procedure. must be observed that subtour elimination con-
240 G. Laporte / The travelingsalesmanproblem: Overviewof algorithms

straints can be applied to fractional components,

i.e. connected subgraphs having fractional xij T1
H
variables associated with some of their edges.
Efficient procedures for generating violated sub-
tour elimination constraints have been suggested
by Gomory and Hu (1961), Crowder and Padberg
(1980), and Padberg and Rinaldi (1990).
Miliotis' work was followed by that of Crowder J
..• Ts
and Padberg (1980), Padberg and Hong (1980),
Padberg and Rinaldi (1987, 1990) and Gr6tschel Figure 2. Comb inequalities
and Holland (1991), among others. The basic idea
behind this line of research consists of introduc-
ing several types of valid constraints before for all H, T1,..., Ts c V satisfying
branching on fractional variables (on this subject, (i) ITk A H I > / 1 ( k = 1 . . . . . s);
see Gr6tschel and Padberg, 1985, and Padberg (ii) [ T ~ \ H [ > t l ( k = l . . . . ,s);
and Gr6tschel, 1985). The effect of this is to (iii) T k A T t = ¢ ( l ~ k < l ~ < s ) ;
increase the value of the LP relaxation and thus, (iv) s >1 3 and odd.
to limit the growth of the search tree. These Again, H is called the handle and T t . . . . . Ts
constraints are particularly powerful since they are called the teeth of the comb (see Figure 2).
are facets of the polytope of integer solutions of (d) Clique tree inequalities,
SYM. Here are the most commonly used con-
straints (see Padberg and Rinaldi, 1990):
(a) Subtour elimination constraints, k=l i,j~H k t=l i,j~Tt k=l
J

x~j< ISI-1, S c V , 3~< ISI ~ < n - 3 , + ~ (IT, I - t t ) - (s + 1 ) / 2 , (35)

i,j~S l=1
(26)
for all H~ . . . . , H r c_ V, and all T 1. . . . . Ts _c V which
(b) 2-matching inequalities, are handles and teeth, respectively, of a clique
E Xij"b E Xij< [ H I + ½ ( I E ' [ - 1 ) , (33) tree. A clique tree is a connected subgraph of the
i,j~H (i,j)~E' graph K n derived from G by defined all Xn(n - 1)
potential edges. The cliques of a clique tree are
for all H c V and all E ' c E satisfying
partitioned into handles and teeth; they satisfy
(i) [{i, j} n H I = 1 for all (i, j) ~ E ' ;
the following properties:
(ii) [{i, j } n { k , I}[ = ¢ , (i, j)--/=(k, I ) ~ E ' ;
(i) no two teeth intersect;
(iii) ] E ' [ >t 3 and odd.
(ii) no two handles intersect;
The set H is called the handle and the edges of
(iii) each tooth contains at least 2 and at most
E ' are called teeth (see Figure 1).
n - 2 vertices, and at least one vertex not belong-
(c) Comb inequalities,
ing to any handle;
(iv) each handle intersects an odd number
E Xij"l- ~ E Xij< IHI
i,j~H k = l i,j~Tk (>/3) of teeth;
(v) if a tooth T and a handle H have a
+ ~ (ITkl--1)--½(s--1), (34) nonempty intersection, then H n T is an articula-
k=l tion set of the clique tree, i.e. a minimal set S of
vertices such that the subgraph of G = (V, E)
induced by V \ S has more connected compo-
H i~ =! • h nents than G.
Finally, in (35), t t is the number of handles
intersected by tooth Tt.
• j, Padberg and Rinaldi (1990) and Gr6tschel and
Holland (1991) suggest efficient procedures for
Figure. 1.2-Matching inequalities. E = {(il, Jl) . . . . . (is, Js)} identifying violated instances of these four types
 G. Laporte / The traveling salesman problem: Overview of algorithms 241

1 2 1 2
of constraints. By incorporating these procedures
within an ILP code, these authors have solved to
optimality TSPs containing between 17 and 2392
vertices. At time of writing, the 2392-vertex prob-
lem is believed to be the largest nonrandom sym- 4- 5 6 4 5 6
metrical TSP ever solved to optimality.
7~8 8
5. H e u r i s t i c a l g o r i t h m s Figure 3. Optimal traversal of a graph using a shortest span-
ning tree

Since the TSP is a NP-hard problem, it is

natural to tackle it by means of heuristic algo-
order to obtain a tour, the above procedure must
rithms. One stream of research has consisted of
be modified by using shortcuts. Follow the path
developing heuristics with a guaranteed worst-case
obtained, but skip any already visited vertex. In
performance. Most effort has, however, been de-
our example, one would follow the path
voted to the design of heuristics with good empir-
(1, 3, 2, 4, 5, 6, 8, 7, 1). Since the triangle in-
ical performance. In this section, we examine
equality is satisfied, this never increases the total
these two streams.
distance traveled and moreover, the resulting
closed path is a tour of length not exceeding
5.1. Heuristics with guaranteed worst-case perfor-
2/(T) ~< 2 z *
mance
Christofides (1976) has proposed an improve-
ment to the above procedure. It is based on the
Consider a symmetrical TSP defined on a graph
following observation. The shortest spanning tree
G and where C satisfies the triangle inequality.
is not in general Eulerian. However, an Eulerian
Let z * be the value of the optimal TSP solution.
graph can be derived from it by linking its odd-
A simple way to derive a lower bound on z * is to
degree vertices by means of a minimum-cost
first compute the length of a shortest spanning
matching algorithm. This can be done in O(n 3)
tree T on G. As shown by Aho, Hopcroft and
time (Papadimitriou and Steiglitz, 1982). New
Ullman (1974), this can be done in O(n 2) time.
edges corresponding to the optimal matching so-
Denote by l(T) the length of that tree. A possible
lution are then appended to the tree. Let l(M)
strategy for visiting all vertices is to traverse the
denote their total length. The resulting graph is
spanning tree along its edges in the following
Eulerian and its complete traversal requires a
fashion:
total distance of I ( T ) + l(M). Again, using short-
cuts, a tour of total length not exceeding l(T) +
Step 1 Consider any leaf i 0 (vertex of degree 1)
l(M) can be obtained. This is illustrated in Figure
of the spanning tree and set i := i 0.
4. Figures 4a and 3a are identical. Figure 4b is
Step 2
obtained by solving a minimum-cost matching
- If there is any untraversed edge (i, j ) inci-
problem; the added edges are shown by the
dent to vertex i, follow that edge to vertex j. Set
dashed lines. Traversing the resulting graph by
i := j and repeat Step 2.
- If all edges from vertex i have already been
traversed, go back to the vertex k from which i 1 2 1 2

was first reached. If k = i0, stop; otherwise set

k .'= i and repeat Step 2.

In order to illustrate this procedure, consider s 6 ""..s 6_

the spanning tree depicted in Figure 3. Starting
with i 0 = 1, one then proceeds to 3, 2, 3, 4, 5, 6, 5,
8, 5, 7, 5, 4, 3 and 1. It is easy to see that every 7~ 8 7~ " " 8
edge of the spanning tree is then covered exactly Figure 4. Optimal traversal of a graph using a shortest span-
twice. In general, this solution is not a tour. In ning tree and minimum matching
242 G. Laporte / The travelingsalesmanproblem: Overviewof algorithms

readings on this subject, see Rosenkrantz, Stearns

and Lewis (1977), Golden and Stewart (1985) and
Ong and Huang (1989).

5.2.1. Tour construction procedures

(a) The nearest-neighbour algorithm (Rosen-
krantz, Stearns and Lewis, 1977).
In this method, a feasible tour is constructed
by taking at each step the decision that is imme-
diately the most advantageous. The main-interest
of this 'myopic' algorithm lies in this simplicity.
Figure 5. Christofides'heuristic
Step 1. Consider an arbitrary vertex as a start-
ing point.
Step 2. Determine the closest vertex to the last
means of the above procedure can be done by vertex considered and include it in the tour. If
following the path (1, 2, 3, 4, 5, 6, 8, 5, 7, 5, 3, 1). any vertex has not yet been considered, repeat
Using shortcuts yields the tour (1, 2, 3, 4, 5, 6, 8, Step 2.
7, 1). Step 3. Link the last vertex of the tour to the
We now focus our attention on I(M). Consider first one.
the sequence of vertices on an optimal TSP tour
and link by shortcuts all vertex pairs correspond-
The complexity of this procedure is O(n2). A
ing to edges in the optimal matching solutions;
possible modification is to consider in turn all n
delete all in[ermediate vertices. The total length
vertices as a starting point. The overall algorithm
of these edges is I(M). Now close the tour by
complexity is then O(n3), but the resulting tour is
linking these edges in the same order as they
generally better.
appear on the tour (see Figure 5). The newly
(b) Insertion algorithms (Rosenkrantz, Stearns
introduced edges have a total length of I(M')<~
and Lewis, 1977; Stewart, 1977; Norback and
I(M) since the first matching is optimal. Since
Love, 1977, 1979; Or, 1976).
I(M) + I(M') <~z*, it follows that I(M) <~z * / 2
This category includes a number of similar
and therefore, the heuristic yields a tour of length
algorithms whose basic structure can be summa-
not exceeding I(T) + I(M) <~3z */2.
rized as follows:
Finally, it should be mentioned that no heuris-
tic with a guaranteed worst-case performance is
known for the asymmetrical TSP. Step 1. Construct a first tour consisting of two
vertices.
5.2. Heuristics with good empirical performance Step 2. Consider in turn all vertices not yet in
the tour. Insert in the tour a vertex chosen with
We now concentrate on a number of heuristics respect to a given criterion, for example:
known to yield good TSP solutions in an empiri- - the vertex yielding the least distance incre-
cal sense. Broadly speaking, TSP heuristics can ment;
be classical into tour construction procedures - the vertex closest to the current tour;
which involve gradually building a solution by - the vertex furthest away from the tour;
adding a new vertex at each step, and tour im- - the vertex forming the largest angle with two
provement procedures which improve upon a fea- consecutive vertices of the tour, etc.
sible solution by performing various exchanges.
The best methods are composite algorithms com- Depending on the criterion that is used, the
bining these two features. Most methods de- complexity of this type of procedure varies be-
scribed in this section work on symmetrical and tween O(n 2) and O(n log n).
asymmetrical problems. There are, however, some (c) The patching algorithm for asymmetrical TSPs
exceptions that will be indicated. For further (Karp, 1979).
 G. Laporte / The traeeling salesman problem: Overview of algorithms 243

Lin and Kerninghan (1973) have proposed an

improvement to this method. Here, the value of r
is modified dynamically throughout the algo-
rithm. This procedure is considerably more diffi-
cult to code than the original Lin r-opt method,
but it generally produces near-optimal solutions.
Recently Johnson (1990) has developed a "rando-
mized iterated L i n - K e r n i n g h a m m e t h o d " that
Figure 6. Merging two subtours in the patching algorithm produces near-optimal solutions. Or (1976) has
proposed a simplified exchange procedure requir-
ing only O(n 2) operations at each step, but pro-
The following procedure was devised by Karp ducing tours nearly as good on the average as
for asymmetrical TSPs. It exploits the fact that on those obtained with a 3-opt algorithm. Or's algo-
problems for which the cifs are uniformly dis- rithm can be described as follows:
tributed, the assignment relaxation of the TSP
Step 1. Consider an initial tour and set t := 1
provides a near-optimal solution (see Balas and
and s := 3.
Toth, 1985).
Step 2. Remove from the tour a chain of s
consecutive vertices, starting with the vertex in
Step 1. Solve the AP with cost matrix C.
position t, and tentatively insert it between all
Step 2. If the solution contains only one circuit,
remaining pairs of consecutive vertices on the
stop.
tour.
Step 3. Select the two circuits having the largest
- If the tentative insertion decreases the cost of
numbers of vertices. Select an arc (i, j ) on the
the tour, implement it immediately, thus defin-
first circuit and an arc (k, l) on the second circuit
ing a new tour; set t := 1 and repeat Step 2.
that minimize the cost Cil q- Ckj -- Cij -- Ckl o f
- If no tentative insertion decreases the cost of
merging the two circuits (see Figure 6). Go to
the tour, set t := t + 1. If t = n + 1, then pro-
Step 2.
ceed to Step 3, otherwise repeat Step 2.
Step 3. Set t : = l and s : = s - l . Ifs>0, goto
5.2.2. Tour improuement procedures
Step 2; otherwise stop.
These methods are used to improve a tour
obtained by any means. They will be classified Before closing this section, it is worth mention-
into three main categories. ing that Kanellakis and Papadimitriou (1980) have
(a) The r-opt algorithm (Lin, 1965). suggested an adaptation of the Lin and Kernighan
procedure to the asymmetrical case. According to
Step 1. Consider an initial tour. the analysis of Golden and Stewart (1985), fur-
Step 2. Remove r arcs from the tour and ther experiments are required to confirm that this
tentatively reconnect the r remaining chains in procedure is indeed competitive.
all possible ways. If any reconnection yields a (b) Simulated annealing (Kirkpatrick et al., 1983).
shorter tour, consider this tour as a new initial This successive improvements method is de-
solution and repeat Step 2. Stop when no im- rived from an analogy with a m~terial annealing
provement can be obtained. process used in mechanics (Metropolis et al.,
1953). In order to bring a material to a minimal-
This heuristic was originally devised for sym- energy solid state, it is necessary to heat it until
metrical TSPs. In this case, the n u m b e r of candi- its particles are randomly distributed in the liquid
date solutions at each step is of the order o f n r state; then, to avoid local minima, its t e m p e r a t u r e
since there are (~) ways to remove r arcs and r! is gradually reduced in steps, until the system
ways to reconnect the resulting undirected chains. reaches an equilibrium step for a given tempera-
Not all these reconnections are, however, feasi- ture level. At a high t e m p e r a t u r e T, all possible
ble. In general, r is taken as 2 or 3. One interest- states can be reached but as the system cools
ing exception is the Christofides and Eilon (1972) down, the n u m b e r of possibilities is reduced and
implementation of this method with r = 4 and 5. the process converges to a stable state.
244 G. Laporte / The traveling salesman problem: Overuiew of algorithms

In combinatorial optimization, the aim is to Step 2. Let N(x) be a neighbourhood of x. If

move from a given initial solution to a minimum- N ( x ) \ T = ¢, go to Step 3. Otherwise, identify a
cost solution, by performing gradual changes to least cost solution y in N ( x ) \ T and set x . ' = y .
the starting solution. Denote by T the state of Update T and the best known solution.
the process (T corresponds to a t e m p e r a t u r e level Step 3. If the maximum number of allowed
in a physical system). In the beginning, the value iteractions since the beginning of the process or
of T is high and the n u m b e r of allowed moves is since the last update has been reached, stop.
also high. This number decreases with T, until no Otherwise, go to Step 2.
change to the solution is possible. A local mini-
m u m has then been reached. The success of this method depends on the
For a given value of T, the algorithm is similar careful choice of a number of control parameters.
to the r-opt procedure: all solutions y in a neigh- For more details on this, see Soriano (1989).
bourhood of a solution x are examined. How- Several authors have applied tabu search to the
ever, substituting x by y is sometimes allowed TSP (see Knox, 1988, Malek, 1988, and Fiechter,
even if this results in a larger cost. This reduces 1990) with seemingly very positive results.
the probability of becoming trapped in a local
optimum. Simulated annealing can be applied to 5.2.3. Composite algorithms
a large spectrum of combinatorial optimization In recent years, two effective composite algo-
problems. Formally, it can be summarized as fol- rithms have been developed. The first is the
lows: Golden and Stewart (1985) C C A O heuristic. The
second, G E N I U S , is more recent. It was devised
Step 1. Consider an initial tour x of cost F(x). by Gendreau, Hertz and Laporte (1990).
Step 2. Consider a solution y of cost F(y) in (a) The CCAO algorithm (Golden and Stewart,
the neighbourhood of x. If F ( y ) < F(x), set x := y 1985).
and repeat Step 2. If F(y) >~F(x), define Pr exp This heuristic was designed for symmetrical
{[F(x) - F(y)]/T}, where T is a p a r a m e t e r tend- Euclidean TSPs. It exploits a well-known prop-
ing towards zero as the process evolves. Ran- erty of such problems, namely that in any optimal
domly select a number r in [0,1]. If r <~Pr, set solution, vertices located on the convex hull of all
x : = y and repeat Step 2. Otherwise, repeat Step 2 vertices are visited in the order in which they
with a new solution y in the neighbourhood of x, appear on the convex hull boundary (Flood, 1956).
or stop if this neighbourhood has been com- The method can be summarized as follows:
pletely examined.

Simulated annealing has been applied to the Step 1 (C: convex hull). Define an initial (par-
TSP by a number of authors including Bonomi tial) tour by forming the convex hull of vertices.
and Lutton (1984), Rossier, Troyon and Liebling Step 2 (C: cheapest insertion). For each vertex
(1986), Golden and Skiscim (1986) and Nahar, k not yet contained in the tour, identify the two
Sahni and Shragowitz (1989), with apparently a adjacent vertices i k and jk on the tour such that
mixed degree of success. Cik k "~ Ck Jk -- Cik Jk is minimized.
(c) Tabu search (Glover 1977, 1988, 1989, 1990; 'Step 3" (A: largest angle). Select the vertex k *
Glover and McMillan, 1986). that maximizes the angle between edges (ik, k)
As in the previous two methods, successive and (k, j~) on the tour, and insert it between ik.
neighbours of a solution x are examined and, as and Jk*-
for simulated annealing, the objective is allowed Step 4 R e p e a t Steps 2 and 3 until a Hamilto-
to deteriorate in order to avoid local minima. In nian tour of all vertices is obtained.
order to prevent - cycling, solutions that have al- Step 5 (O: Or-opt). Apply the Or-opt proce-
ready been examined are forbidden and inserted dure to the tour and stop.
in a constantly updated ' t a b u list'. The method
can be summarized in three steps: The rationale behind Steps 2 and 3 is that by
selecting k * so as to maximize the angle it makes
Step 1. Consider an initial solution x of cost with the tour, the solution remains as close as
F(x). Set the tabu list T := ~. possible to the initial convex hull.
 G. Laporte / The traveling salesman problem: Overview of algorithms 245

(b) The GENIUS algorithm (Gendreau, Hertz and search grant. An extended version of this paper
Laporte, 1992). will appear in Discrete Optimization Models, H.A.
One major drawback of the CCAO algorithm Eiselt and C.L. Sandblom (eds.), De Gruyter,
is that its insertion phase is myopic in the follow- Berlin, 1993. Permission to publish this paper in
ing sense: since insertions are executed sequen- E J O R is gratefully acknowledged. Finally, thanks
tially without much concern for global optimality, are due to Paolo Toth for his valuable comments
they may result in a succession of bad decisions on a preliminary version of this paper.
that the post-optimization phase will be unable to
undo. G E N I U S executes each insertion more
carefully, by performing a limited number of local
References
transformation of the tour, simultaneously with
the insertion itself. It consists of two parts: a
generalized insertion phase, followed by a post- Aho, A.V., Hopcroft, J.E., and Ullman, J.D. (1974), The
Design and Analysis of Computer Algorithms, Addison-
optimization phase that successively removes ver- Wesley, Reading, MA.
tices from the tour and reinserts them, using the Balas, E., Christofides, N. (1981), "A restricted lagrangean
generalized insertion rule. approach to the traveling salesman problem", Mathemati-
The algorithm has been extensively tested on cal Programming 21, 19-46.
randomly generated problems and on problems Balas, E., Toth, P. (1985), "Branch and bound methods", in:
E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B.
taken from the literature; all these problems were Shmoys (eds.), The Traveling Salesman Problem. A Guided
symmetrical and Euclidean. Tests revealed that Tour of Combinatorial Optimization, Wiley, Chichester,
G E N I U S produces in shorter computing times 361-401.
better solutions than CCAO, itself superior to all Bellmore, M., and Malone, J.C. (1971), "Pathology of travel-
ing-salesman subtour-elimination algorithms", Operations
tour construction heuristics developed in this sec-
Research 19, 278-307.
tion. This algorithm also appears to compare Bland, R.G., and Shallcross, D.F. (1989), "Large traveling
favourably to tabu search and simulated anneal- salesman problems arising experiments in X-ray crystallog-
ing, although the number of comparisons was raphy: A preliminary report on computation", Operations
more limited in the case of these two methods. Research Letters 8, 125-128.
Bonomi, E., and Lutton, J.-L. (1984), "The N-city travelling
salesman problem: Statistical mechanics an the Metropolis
algorithm", SIAM Review 26, 551-568.
6. Conclusion Carpaneto, G., Fischetti, M., and Toth, P. (1989), "'New lower
bounds for the symmetric travelling salesman problem",
The TSP occupies a central place in Opera- Mathematical Programming 45,233-254.
tional Research. It underlies several practical ap- Carpaneto, G., Martello, S., and Toth, P. (1988), "Algorithms
and codes for the assignment problem", in: B. Simeone, P.
plications and its study over the last 35 years or Toth, G. Gallo, F. Maffioli, and S. Pallottino (eds.), FOR-
so has led to important theoretical developments. TRAN Codes for Network Optimization, Annals of Opera-
Problems involving a few hundred vertices can tions Research 13, 193-223.
now be solved routinely to optimality. Instances Carpaneto, G., and Toth, P. (1980), "Some new branching
involving more than 2000 vertices have also been and bounding criteria for the asymmetric travelling sales-
man problem", Management Science 26, 736-743.
solved exactly by means of constraint relaxation Christofides, N. (1970), "The shortest Hamiltonian chain of a
algorithms. A number of powerful heuristics have graph", SIAM Journal on Applied Mathematics 19, 689-696.
also been proposed: tabu search methods and Christofides, N. (1976), "Worst-case analysis of a new heuris-
generalized insertion algorithms appear to hold tic for the travelling salesman problem", Report 388,
Graduate School of Industrial Administration, Carnegie-
much potential.
Mellon University, Pittsburgh, PA.
Christofides, N., and Eilon, S. (1972). Algorithms for large-
scale travelling salesman problems, Operational Research
Acknowledgements Quarterly 23, 511-518.
Crowder, H., and Padberg, M.W. (1980), "Solving large-scale
symmetric travelling salesman problems to optimality",
This research was in part supported by the
Management Science 26, 495-509.
Canadian Natural Sciences and Engineering Re- Dantzig, G.B., Fulkerson, D.R., and Johnson, S.M. (1954),
search Council (grant OGP0039682), and by a "Solution of a large-scale traveling-salesman problem",
Q u e b e c - N e w - Brunswick interprovincial re- Operations Research 2, 393-410.
246 G. Laporte / The traveling salesman problem: Overview of algorithms

Dantzig, G.B., Fulkerson, D.R., and Johnson, S.M. (1954), Glover, F., and McMillan, C. (1986), "The general employee
"Solution of a large-scale traveling-salesman problem", scheduling problem: An integration of MS and AI", Com-
Operations Research 2, 393-410. puters & Operations Research 13, 563-573.
Dantzig, G.B., Fulkerson, D.R., and Johnson, S.M. (1959), Golden, B.L., and Skiscim, C.C. (1986), "Using simulated
"On a linear-programming combinatorial approach to the annealing to solve routing and location problems", Naval
traveling-salesman problem", Operations Research 7, 58- Research Logistics Quarterly 33, 261-280.
66. Golden, B.L., and Stewart, Jr., W.R. (1985), "Empirical analy-
Desrochers, M., and Laporte, G. (1991), "Improvements and sis of heuristics", in: E.L. Lawler, J.K. Lenstra, A.H.G.
extensions to the Miller-Tucker-Zemlin subtour elimina- Rinnooy Kan, and D.B. Shmoys (eds.), The Traveling
tion constraints", Operations Research Letters 10, 27-36. Salesman Problem. A Guided Tour of Combinatorial Opti-
Eastman, W.L. (1958), "Linear programming with pattern mization, Wiley, Chichester, 207-249.
constraints", Ph.D. Thesis, Harvard University, Cam- Gomory, R.E. (1963), "An algorithm for integer solutions to
bridge, MA. linear program", in: R.L. Graves, and P. Wolfe (eds).
Eiselt, H.A., and Laporte, G. (1991), "A combinatorial opti- Recent Advances in Mathematical Programming, McGraw-
mization problem arising in dartboard design", Journal of Hill, New York, 269-302.
the Operational Research Society 42, 113-118. Gomory, R.E., and Hu, T.C. (1961), "Multi-terminal network
Fiechter, C.-N. (1990), "A parallel tabu search algorithm for flows", SlAM Journal on Applied Mathematics 9, 551-556.
large scale traveling salesman problems", Working Paper Gr6tschel, M., and Holland, O. (1991), "Solution of large-scale
90/1, D~partement de Math~matiques, lEcole Polytech- symmetric travelling salesman problems", Mathematical
nique F6d6rale de Lausanne. Programming 51, 141-202.
Fischetti, M., and Toth, P. (1991), "An additive bounding Gr6tschel, M., and Padberg, M.W. (1985), "Polyhedral
procedure for the asymmetric travelling salesman theory", in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy
problem", Mathematical Programming, forthcoming. Kan, and D.B. Shmoys (eds.), The Traveling Salesman
Flood, M.M. (1956), "The traveling-salesman problem", Oper- Problem. A Guided Tour of Combinatorial Optimization,
ations Research 4, 61-75. Wiley, Chichester, 251-305.
Garey, M.R., and Johnson, D.S. (1979), "Computers and Helbig Hansen, K., and Krarup, J. (1974), "Improvements of
intractability: A guide to the theory of NP-completeness", the Held-Karp algorithm for the symmetric traveling-sales-
Freeman, San Francisco. man problem", Mathematical Programming 7, 87-96.
Garfinkel, R.S. (1973), "On partitioning the feasible set in a Held, M., and Karp., R.M. (1970), "The traveling salesman
branch-and-bound algorithm for the asymmetric problem and minimum spanning trees", Operations Re-
traveling-salesman problem", Operations Research 21, search 18, 1138-1162.
340-343. Held, M., and Karp, R.M. (1971), "The traveling salesman
Garfinkel, R.S. (1977), "Minimizing wallpaper waste, Part I: problem and minimum spaning trees: Part II", Mathemati-
A class of traveling salesman problems", Operations Re- cal Programming 1, 6-25.
search 25, 741-751. Johnson, D.S. (1990), "Local optimization and the traveling
Gavish, B., and Srikanth, K.N. (1986), "An optimal solution salesman problem", in: M.S. Paterson (ed.), Proceedings of
method for large-scale multiple traveling salesman prob- the 17th International Colloquium on Automata, Languages
lems", Operations Research 34, 698-717. and Programming, Lecture Notes in Computer Science,
Gendreau, M. Hertz, A., and Laporte, G. (1992), "New inser- Springer-Verlag, Berlin, 446-461.
tion and post-optimization procedures for the traveling Kanellakis, P.-C., and Papadimitriou, C.H. (1980), "Local
salesman problem", Operations Research, forthcoming. search for the asymmetric traveling salesman problem",
Gilmore, P.C., and Gomory, R.E. (1964), "Sequencing a one Operations Research 28, 1086-1099.
state-variable machine: A solvable case of the traveling Karp, R.M. (1979), "A patching algorithm for the nonsymmet-
salesman problem", Operations Research 12, 655-679. ric traveling-salesman problem", SIAM Journal on Com-
Gilmore, P.C., Lawler, E.L., and Shmoys, D.B. (1985), "Well- puting 8, 561-573.
solved special cases", in: E.L. Lawler, J.K. Lenstra, A.H.G. Kirkpatrick, S., Gelatt, Jr., C.D., and Vecchi, M.P. (1983),
Rinnooy Kan, and D.B. Shmoys (eds.), The Traveling "Optimization by simulated annealing", Science 220, 671-
Salesman Problem. A Guided Tour of Combinatorial Opti- 680.
mization, Wiley, Chichester, 87-143. Knox, J. (1988), "An application of TABU search to the
Glover, F. (1977), "Heuristic for integer programming using symmetric traveling salesman problem", Ph.D. Thesis,
surrogate constraints",Decision Sciences 8, 156-166. Center for Applied Artificial Intelligence (CAAI), Gradu-
Glover, F. (1988), "Tabu search", Report 88-3, Center for ate School of Business, University of Colorado.
Applied Artificial Intelligence (CAAI), Graduate School Langevin, A., Soumis, F., and Desrosiers, J. (1990), "Classifi-
of Business, University of Colorado. cation of travelling salesman problem formulations", Oper-
Glover, F. (1989), "Tabu search, Part I", ORSA Journal on ations Research Letters 9, 127-132.
Computing 1, 190-209. Laporte, G. (1992), "The vehicle routing problem: An overview
Glover, F. (1990), "Tabu search", Part II, ORSA Journal on of exact and approximate algorithms", European Journal
Computing 2, 4-32. of Operational Research, 59, 345-358 (to appear).
 G. Laporte / The traveling salesman problem: Overview of algorithms 247

Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., and lems and their relation to the logistics of regional blood
Shmoys, D.B. (1985), The Traveling Salesman Problem. A banking", Ph.D. Dissertation, Northwestern University,
Guided Tour of Combinatorial Optimization, Wiley, Chich- Evanston, IL.
ester. Padberg, M.W., and Gr6tschel, M. (1985), "Polyhedral com-
Lenstra, J.K., Rinnooy Kan, A.H.G. (1975), "Some simple putations", in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy
applications of the travelling salesman problem", Opera- Kan, and D.B. Shmoys (eds.), The Traveling Salesman
tional Research Quarterly 26, 717-733. Problem. A Guided Tour of Combinatorial Optimization,
Lin, S. (1965), "Computer solutions of the traveling salesman Wiley, Chichester, 307-360.
problem", Bell System Computer Journal 44, 2245-2269. Padberg, M.W., and Hong, S. (1980), "On the symmetric
Lin, S., and Kernighan, B.W. (1973), "An effective heuristic traveling salesman problem: A computational study",
algorithm for the traveling-salesman problem", Operations Mathematical Programming Study 12, 78-107.
Research 21,498-516. Padberg, M.W., and Rinaldi, G. (1987), "Optimization of a
Little, J.D.C., Murty, K.G., Sweeney, D.W., and Karel, C. 532-city symmetric traveling salesman problem by branch
(1963), "An algorithm for the traveling salesman problem", and cut", Operations Research Letters 6, 1-7.
Operations Research 11, 972-989. Padberg, M.W., and Rinaldi, G. (1990), "Facet identification
Malek, M. (1988), "Search methods for traveling salesman for the symmetric traveling salesman problem", Mathemat-
problems", Working Paper, University of Texas, Austin, ical Programming 47, 219-257.
TX. Papadimitriou, C.H., and Steiglitz, K. (1982), Combinatorial
Martin, G.T. (1966), "Solving the traveling salesman problem Optimization: Algorithms and Complexity, Prentice-Hall,
by integer programming", Working Paper, CEIR, New Englewood Cliffs, NJ.
York. Reinelt, G. (1989), "Fast heuristics for large geometric travel-
Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, ing salesman problems", Report No. 185, Institut fiir
A.H., and Teller, E. (1953), "Equation of state calcula- Mathematik, Universit~it Augsburg.
tions by fast computing machines", Journal of Chemical Rosenkrantz, D.J., Stearns, R.E., and Lewis, II, P.M. (1977),
Physics 21, 1087-1091. "An analysis of several heuristics for the traveling sales-
Miliotis, P. (1976), "Integer programming approaches to the man problem", SIAM Journal on Computing 6, 563-581.
travelling salesman problem", Mathematical Programming Rossier, Y., Troyon, M., and Liebling, T.M. (1986), "Prob-
10, 367-378. abilistic exchange algorithms and the Euclidian traveling
Miliotis, P. (1978), "Using cutting planes to solve the symmet- salesman problem", Operations Research Spektrum 8, 151-
ric salesman problem", Mathematical Programming 15, 164.
177-188. Shapiro, D.M. (1966), "Algorithms for the solution of the
Miller, D.L., and Pekny, J.F. (1989), "Results from a parallel optimal cost and bottleneck traveling salesman problems",
branch and bound algorithm for solving large asymmetric Sc.D. Thesis, Washington University, St. Louis, MO.
traveling salesman problems", Operations Research Letters Smith, T.H.C., Srinivasan, V., and Thompson, G.L. (1977),
8, 129-135. "Computational performance of three subtour elimination
Miller, D.L., and Pekny, J.F. (1991), "Exact solution of large algorithms for solving asymmetric traveling salesman prob-
asymmetric traveling salesman problems", Science 251, lems", Annals of Discrete Mathematics 1,495-506.
754-761. Smith, T.H.C., and Thompson, G.L. (1977), "A LIFO implicit
Miller, C.E., Tucker, A.W., and Zemlin, R.A. (1960), "Integer enumeration search algorithm for the symmetric traveling
programming formulations and traveling salesman prob- salesman problem using Held and Karp's 1-tree
lems", Journal of the Association for Computing Machinery relaxation", Annals of Discrete Mathematics 1, 479-493.
7, 326-329. Soriano, P. (1989), "l~tude de nouvelles avenues de recherche
Murty, K.G. (1968), "An algorithm for ranking all the assign- propos~es en optimisation combinatoire", Publication
ments in order of increasing cost", Operations Research 16, CRT-619, Centre de recherche sur les transports,
682-687. Montr6al.
Nahar, S., Sahni, S., and Shragowitz, E. (1989), "Simulated Stewart, Jr., W.R. (1977), "A computationally efficient heuris-
annealing and combinatorial optimization", International tic for the traveling salesman problem", Proceedings of the
Journal of Computer Aided VLSI Design 1, 1-23. 13th Annual Meetings of S.E. Tims, 75-85.
Norback, J., and Love, R. (1977), "Geometric approaches to Tarjan, R.E. (1977), "Finding optimum branchings", Net-
solving the traveling salesman problem", Management Sci- works 7, 25-35.
ence 23, 1208-1223. Volgenant, T., and Jonker, R. (1982), "A branch and bound
Norback, J., and Love, R. (1979), "Heuristic for the Hamilto- algorithm for the symmetric traveling salesman problem
nian path problem in Euclidean two space", Journal of the based on the 1-tree relaxation", European Journal of Oper-
Operational Research Society 30, 363-368. ational Research 9, 83-89.
Ong, H.L., and Huang, H.C. (1989), "Asymptotic expected Wong, R.T. (1980), "Integer programming formulations of the
performance of some TSP heuristics", European Journal of travelling salesman problem", Proceedings of the IEEE
Operational Research 43, 231-238. International Conference on Circuits and Computers, 149-
Or, I. (1976), "Traveling salesman-type combinatorial prob- 152.