Optimization Modelling And Decision Analysis

R E S E A R C H P A P E R

Models and algorithms for the Asymmetric Traveling Salesman Problem: an experimental comparison

Roberto Roberti • Paolo Toth

Received: 15 October 2011 / Accepted: 25 April 2012 / Published online: 15 May 2012 ! Springer-Verlag + EURO - The Association of European Operational Research Societies 2012

Abstract This paper surveys the most effective mathematical models and exact algorithms proposed for finding the optimal solution of the well-known Asymmetric Traveling Salesman Problem (ATSP). The fundamental Integer Linear Program- ming (ILP) model proposed by Dantzig, Fulkerson and Johnson is first presented, its classical (assignment, shortest spanning r-arborescence, linear programming) relaxations are derived, and the most effective branch-and-bound and branch-and- cut algorithms are described. The polynomial ILP formulations proposed for the ATSP are then presented and analyzed. The considered algorithms and formulations are finally experimentally compared on a set of benchmark instances.

Keywords Asymmetric Traveling Salesman Problem ! Integer Linear Programming models ! Branch-and-bound algorithms ! Branch-and-cut algorithms ! Experimental comparison

Introduction

Let G = (V, A) be a given complete digraph, where V ¼ f1; . . .; ng is the vertex set and A ¼ fði; jÞ : i; j 2 Vg the arc set, and let cij be the cost associated with arc ði; jÞ2 A (with cii ¼þ1; for i 2 V ). A Hamiltonian circuit (tour) of G is a circuit visiting each vertex of V exactly once. The Asymmetric Traveling Salesman Problem (ATSP) is to find a Hamiltonian circuit G& ¼ ðV; A&Þ of G whose costP ði;jÞ2A& cij is minimum. If the considered graph G is undirected, the corresponding

problem is denoted as Symmetric Traveling Salesman Problem (STSP).

R. Roberti ! P. Toth (&) DEIS, University of Bologna, Viale Risorgimento, 2, 40136 Bologna (BO), Italy e-mail: [email protected]

R. Roberti e-mail: [email protected]

123

EURO J Transp Logist (2012) 1:113–133 DOI 10.1007/s13676-012-0010-0

The ATSP is known to be NP-hard in the strong sense, and has been intensively studied in the last six decades. In this paper, we will consider and experimentally compare the most effective Integer Linear Programming (ILP) models and exact algorithms proposed for finding the optimal solution of the ATSP. Previous surveys on the subject have been presented by Balas and Toth (1985), Fischetti et al. (2002), Öncan et al. (2009), D’Ambrosio et al. (2010). Several books dealing with the traveling salesman problem and its variations have been published. Among them we mention those by Lawler et al. (1985), Reinelt (1994), Gutin and Punnen (2002), Applegate et al. (2007).

The paper is organized as follows. In ‘‘The Dantzig-Fulkerson-Johnson formulation and its relaxations’’, the well-known Dantzig, Fulkerson and Johnson formulation Dantzig et al. (1954) and its ‘‘classical’’ relaxations are described. Polynomial formulations, i.e., formulations requiring a number of constraints polynomial in the number of vertices n, are described in ‘‘Review of polynomial formulations’’. ‘‘Exact Algorithms’’ reviews the most effective branch-and-bound and branch-and-cut algorithms proposed for the ATSP. In ‘‘Transformation of ATSP instances into STSP instances’’, the transformation of an ATSP instance into an equivalent STSP instance, proposed by Jonker and Volgenant (1983), is presented. Computational experiments, comparing the considered formulations and exact algorithms on a set of benchmark instances, are described in ‘‘Computational results’’.

The Dantzig–Fulkerson–Johnson formulation and its relaxations

Dantzig et al. (1954) proposed the following ILP model (hereafter DFJ), utilizing n2

binary variables xij, for the ATSP:

ðDFJÞ min Xn

i¼1

Xn

j¼1 cijxij ð1Þ

s.t. Xn

i¼1 xij ¼ 1; j ¼ 1; . . .; n; ð2Þ

Xn

j¼1 xij ¼ 1; i ¼ 1; . . .; n; ð3Þ

X

i2S

X

j2S xij ' jSj( 1; S) V : S 6¼ £; ð4Þ

xij 2f0; 1g; i; j ¼ 1; . . .; n; ð5Þ

where xij is equal to 1 if and only if arc (i, j) (i ¼ 1; . . .; n; j ¼ 1; . . .; n) is in the optimal tour. Constraints (2) and (3) impose that the in-degree and out-degree of each vertex, respectively, is equal to one, while constraints (4) are Subtour Elimi- nation Constraints (SECs) and impose that no partial circuit exists.

114 R. Roberti, P. Toth

123

Moreover, it is well known that one can halve the number of SECs (4) by replacing them with

X

i2S

X

j2S xij ' jSj( 1; S) Vnfrg : S 6¼ £;

where r is any vertex of vertex set V. Because of constraints (2) and (3), constraints (4) can be equivalently rewritten as

Connectivity constraints: X

i2S

X

j2VnS xij *1; S) V : S 6¼ £: ð6Þ

Also in this case, one can halve the number of connectivity constraints (6) by replacing them with

X

i2S

X

j2VnS xij *1; S) V : r 2 S ð7Þ

or with X

i2S

X

j2VnS xij *1; S) V : S 6¼ £; r 62 S ð8Þ

where r is any fixed vertex. A valid lower bound on the optimal solution value of the ATSP can be obtained

by optimally solving the Linear Programming (LP) relaxation of the previous models (1)–(5) or (1)–(3), (5) and (7), obtained by replacing constraints (5) with constraints

xij *0; i; j ¼ 1; . . .; n: ð9Þ

Although the considered ILP models require an exponential number of Subtour Elimination or Connectivity constraints, their LP relaxations can be efficiently solved in polynomial time using the effective polynomial separation procedure proposed by Padberg and Rinaldi (1990a) for the STSP.

Additional lower bounds can be obtained by considering the different substruc- tures of the ATSP, each associated with a subset of constraints defining a well- structured relaxation.

Constraints (2), (3) and (9), with objective function (1), define the well-known min-sum Assignment Problem (AP). Such a problem always has an integer optimal solution and requires the finding of a minimum-cost collection of vertex-disjoint subtours visiting all the vertices of G. Relaxation AP can be solved in O(n3) time (see, e.g., Lawler 1976; Carpaneto and Toth 1987 for an efficient implementation).

Constraints (2), (7) and (9), with objective function (1), define the well known shortest Spanning r-Arborescence Problem (r-SAP). Such a problem always has an integer optimal solution, and corresponds to find a minimum-cost spanning

subdigraph !G ¼ðV; !AÞ of G such that (1) the in-degree of each vertex is exactly one, and (2) each vertex can be reached from the root vertex r. Relaxation r-SAP can be solved in O(n2) time by finding the shortest spanning arborescence rooted at

Models and Algorithms for the ATSP 115

123

vertex r (see, e.g., Edmonds 1967; Tarjan 1977; Fischetti and Toth 1993 for an efficient implementation) and adding the minimum-cost arc entering vertex r.

A third substructure, corresponding to constraints (3), (8) and (9), with objective function (1), defines the shortest Spanning r-Antiarborescence Problem (r-SAAP). Such a problem can easily be transformed into r-SAP by simply transposing the input cost matrix, hence it can be solved in O(n2) time. Different choices of the root vertex r generally produce different values of the lower bounds corresponding to relaxations r-SAP and r-SAAP. In addition, these relaxations can be strengthened by considering the associated Lagrangian relaxations, obtained by embedding, in a Lagrangian fashion, the relaxed constraints (3) for r-SAP, and (2) for r-SAAP, into the objective function (1). Near optimal Lagrangian multipliers, leading to good lower bounds, can be obtained by applying the well-known subgradient optimiza- tion procedure proposed by Held and Karp (1970) and (1971) for the STSP.

The lower bounds corresponding to relaxations AP, r-SAP and r-SAAP can be also improved, as proposed by Fischetti and Toth (1992), by combining the associated substructures according to the so-called additive approachintroduced by Fischetti and Toth (1989).

Review of polynomial formulations

In this section, we consider the papers presenting polynomial formulations for the ATSP. For each paper, we focus on the formulation producing the tightest LP-relaxation lower bound. Unlike the exact algorithms described in ‘‘Exact algorithms’’ the polynomial formulations can be directly solved by a general- purpose ILP solver. Classifications and comparisons of the polynomial formulations for the ATSP have been recently presented in Öncan et al. (2009) and Godinho et al. (2011b).

The earliest polynomial formulation of the ATSP is owed to Miller et al. (1960) (hereafter MTZ) and is given by (1)–(3), (5) and

ui ( uj þðn ( 1Þxij 'n ( 2; i; j ¼ 2; . . .; n; ð10Þ

where ui; i ¼ 2; . . .; n; is an arbitrary real number representing the order of vertex i in the optimal tour, and constraints (10) break subtours. Miller et al. (1960) origi- nally proposed MTZ without any bound on variables ui. Later on, simple bounds (e.g., 1'ui 'n ( 1; i ¼ 2; . . .; n) were introduced to restrict the range of variables ui. This does not affect the LP bound of MTZ and, in our computational experi- ments, has shown to increase the computing time, so we leave variables ui unrestricted.

Gavish and Graves (1978) proposed another formulation (hereafter GG) having LP relaxation stronger than that of MTZ (see Wong 1980; Padberg and Sung 1991) but weaker than that of DFJ (see Gouveia 1995). GG is a single-commodity flow formulation, where subtours are broken by introducing n(n - 1) nonnegative variables gij (i ¼ 2; . . .; n; j ¼ 1; . . .; n). GG consists of constraints (1)–(3), (5) and the following constraints:

116 R. Roberti, P. Toth

123