arXiv:1009.5030v1  [cs.CC]  25 Sep 2010
Approximability of the Multiple Stack TSP
Sophie Toulouse 1
LIPN (UMR CNRS 7030) - Institut Galil´ee - Universit´e Paris 13,
99 av. Jean-Baptiste Cl´ement, 93430 Villetaneuse, France
Abstract
STSP seeks a pair of pickup and delivery tours in two distinct networks, where the
two tours are related by LIFO contraints. We address here the problem approxima-
bility. We notably establish that asymmetric MaxSTSP and MinSTSP12 are APX,
and propose a heuristic that yields to a 1/2, 3/4 and 3/2 standard approximation
for respectively Max2STSP, Max2STSP12 and Min2STSP12.
Keywords: Approximation algorithms, multiple stack TSP, TSP, LIFO constraints
1
Introduction
The multiple Stack Traveling Salesman Probem, STSP, has been recently in-
troduced in [1] and is very well motivated by the initial request of a trans-
portation company. Consider a company that owns a vehicle fleet and a depot
in m distinct cities C1, . . . , Cm. For any pair (Cj, Cj′) of cities, the company
handles orders from Cj suppliers to Cj′ customers, proceeding as follows: in
Cj, a single vehicle picks up all the orders that involve a Cj′ customer; during
this tour, the commodities are packed within a single container that consists
of a given number k of rows; the container is then sent to Cj′, where a local
vehicle delivers the commodities. The operator thus is faced with two levels of
1 Email: sophie.toulouse@lipn.univ-paris13.fr
transportation: the local one inside the cities, the long-haul one between the
cities. STSP models the local level problem; namely, in the context we have
just described, every pair of cities defines an instance of STSP. The problem
specificity relies on the way the containers are managed: their rows behave
like stacks, and no repacking is allowed. The rows of the containers thus are
subject to LIFO “Last In First Out” constraints. Therefore, the delivery tour
in Cj′ must handle at first orders that have been handled at last in Cj.
Formally, an instance I of STSP considers a number k of stacks (the
container rows), together with two distinct networks IA = (GA, dA), IB =
(GB, dB), where V (Gα) ≡[n + 1] and dα : E(Gα) →N, α ∈{A, B}. In both
networks, vertex 0 represents the depot, whereas vertex i ∈[n] represents
the ith order (the ith supplier in IA, the ith customer in IB). A solution
consists of a pickup tour ⃗T A on IA, a delivery tour ⃗T B on IB, and a packing
P = {P 1, . . . , P k} of the commodities into the stacks, where a stack P β is
described as a sequence (i1, . . . , ipβ) of commodities (index 1 refers to the bot-
tom of P β). We denote by <α, α ∈{A, B} the complete order that ⃗T α induces
on [n]: i <α i′ iff⃗T α handles order i earlier than it handles i′. Similary, we
denote by <P the partial order that P induces on [n]: i <P i′ iffP stacks i
at a lower position than i′ in a same stack P β. The LIFO constraints may
thus be expressed in terms of the three orders <A, <B, <P. Namely, a triple
(P, ⃗T A, ⃗T B) is consistent iffit satisfies:
∀i ̸= i′ ∈[n], i <P i′ ⇒(i <A i′) ∧(i >B i′)
(1)
The value of a solution (P, ⃗T A, ⃗T B) is given by the sum dA(⃗T A) + dB(⃗T B)
of the distance of its two tours. The ultimate goal naturally consists in finding
the feasible triple (P, ⃗T A, ⃗T B) of optimum value.
In what follows, the stacks are assumed to have unlimited capacities. The
most often, input graphs are complete.
For TSP (the Traveling Salesman
Problem), as well as for STSP, A(S)TSP, ∆(S)TSP and (S)TSPab respec-
tively refer the asymmetric, the metric and the bivaluated cases.
Finally,
kSTSP considers that k is a universal constant. Since one manipulates both
maximization and minimization goals, we use notations ⪰, ≻, opt, opt in-
stead of ≥, >, max, min (resp., ≤, <, min, max) if the goal is to maximize
(resp., to minimize). Finally, because one jointly considers pickup and delivery
tours, we respectively denote by E−1 = {(i′, i) | (i, i′) ∈E}, G−1 = (V, E−1),
d−1 : E−1 →N : d−1(i, i′) = d(i′, i) and I−1 = (G−1, d−1) the reverse of an
edge set E, a graph G = (V, E), a distance d : E →N, a network I = (G, d).
Hence, ⃗T is a tour of value d(⃗T) on I iff⃗T −1 is a tour of value d(⃗T) on I−1.
2
Preliminaries
The problem trivially is NP −hard, from TSP. Indeed, for extremal val-
ues of the number of stacks, STSP strictly is equivalent to TSP: if STSP
assumes a single stack, then it reduces to TSP, considering the distance
d : (i, i′) 7→dA(i, i′) + dB(i′, i); if on the opposite STSP assumes n stacks,
then it reduces to two independent TSP (packings that store one commodity
per stack do not induce any LIFO constraint). The litterature on computa-
tional aspects of STSP is rather thin: see [1,2] for metaheuristic approachs,
[3] for an exact approach (that solves 2STSP via the computation of the k
best tours in IA, IB), [4] for an analysis of STSP complexity. We here make
use of natural connections to TSP and observations made in [4] in order to
locate STSP within the approximation hierarchy.
Besides its practical impacts, STSP presents a rather intricate combina-
torial structure. One the one hand, one could wonder on what part of the
problem does structure / impact the most the solution / its complexity. It
appeared in [4] that both the packing and the tour subproblems are tractable:
Theorem 2.1 ([4]) In arbitrary input graphs:
(i) Deciding, given a pair (⃗T A, ⃗T B), whether it admits or not a consistent
packing P (and to design this packing if the answer is YES) is in P.
(ii) When k is a universal constant: given a packing P, computing a pair
of tours that are optimal for P is in P.
On the other hand, STSP has strong connections to coloring and schedul-
ing. Indeed, subproblem (i) reduces to graph coloring in C(⃗T A, ⃗T B) = {i ̸=
i′ ∈[n] | i <A i′ ⇔i <B i′}, whereas subproblem (ii) reduces to scheduling
under <P (or >P) precedence constraints.
3
A first classification of STSP
Property 1
(i) There exists a standard approximation preserving reduction
from ASTSP to ATSP that maps a ρ-approximate solution of ATSP to
a ρ/2, ρ/2 + (a/2b), ρ/2 + (b/2a)-approximate solution of ASTSP for
Max(S)TSP, Max(S)TSPab and Min(S)TSPab, respectively.
(ii) Case of arbitrary graphs. Any approximate factor ρ for any restriction
of STSP also holds for the same restricton of TSP.
Proof. i. Associate with the instance I = (IA, IB) of ASTSP the pair (IA, IB)
(i)
i1
j
?
i1
j′
i1
j
?
i1
j′
i2
h
i2
h′
(ii)
i1
j
i1
j′
i2
h
i2
h′
?
(iii)
i1
j
i1
j+1
i2
h+1
i2
h
?
i1
j
i1
j+1
i2
h+1
i2
h
?
Fig. 1. The three configurations that contradict consistency.
of instances of ATSP. Compute ⃗T α, α ∈{A, B} an approximate tour on Iα.
Pick the tour ⃗T A or ⃗T B that performs the best among dA(⃗T A) + (dB)−1(⃗T A),
(dA)−1(⃗T B) + dA(⃗T B). ii. Associate with the instance I = (G, d) of TSP the
instance I′ = (I, I−1) of STSP.
✷
Proposition 3.1 (Immediate from Property 1)
(i) Max(A)STSP, Max∆(A)STSP, Max(A)STSP01,
Min(A)STSP12 are standard-approximable within the following factor:
MaxSTSP
MaxASTSP
Max∆STSP
Max∆ASTSP
61/162 −o(1), [8]
1/3, [9]
7/16 −o(1), [7]
31/80, [10]
MaxSTSP01
MaxASTSP01
MinSTSP12
MinASTSP12
3/7, [12]
3/8, [11]
11/7, [12]
13/8, [11]
(ii) Max∆STSP∈MaxSNP-hard, [5]; MaxSTSP12∈APX-hard, [6]; Min-
STSP is not 2p(n+1) standard-approximable for any polynomial p, or P = NP
4
A matching based heuristic for the symmetric 2STSP
In what follows, we say that an edge set N is consistent with a packing P iff
there exists a completion N′ of N into a tour T s.t. T is feasible with respect
to P. We first provide a characterization of consistency for 2STSP.
Proposition 4.1 (Due to lack of space, the proof is omitted.) Given a
packing P, Jβ = {0, . . . , pβ +1} denotes the index set on P β, β ∈{1, 2}. Arti-
ficial indexes 0, pβ+1 are introduced in order to represent the depot vertex, i.e.,
iβ
0 = iβ
pβ+1 = 0. Let N be a collection of pairwise disjoint elementary chains on
[n + 1], then N is consistent with P iffit satifies the three following properties
(configurations that contradict consistency are illustrated in Figure 1):
(i) No jump: ∀β ∈{1, 2}, ∀j < j′ ∈Jβ,

{iβ
j , iβ
j′} ∈N

∨

∃h ≤h′ ∈J3−β, {iβ
j , i3−β
h
, . . . , i3−β
h′ , iβ
j′} ⊆N

⇒j′ = j + 1
(ii) No crossing edges: ∀j ̸= j′ ∈J1, ∀h ̸= h′ ∈J2, {{i1
j, i2
h}, {i1
j′, i2
h′}} ⊆N
⇒(j < j′ ⇔h < h′)
(iii) No way back: ∀j ∈J1, ∀h ∈J2, {{i1
j, i1
j+1}, {i2
h, i2
h+1}} ⊆N
⇒
{i1
j, i2
h}


/∈N ∧
{i1
j+1, i2
h+1}


/∈N
P 1 :
P 2 :
c1
1 = 0
c1
2
c1
3
c2
1
c2
2
c2
3
c2
4
c3
1
c3
2
c4
1
c4
2
c4
3
c4
4
c4
5
c4
6
MA
T A, T B\Mα
MB
e∗
B
A
A
B
0
Fig. 2. Possible completions of the approximate packing P: case n even.
j, j′ ̸= 1, j ≡j′ + 1[2]
0
c1
2
c1
3
c1
4
c1
5
c1
6
c1
7
c1
8
c1
9
e∗
j, j′ ̸= 1, j ≡j′[2]
0
c1
2
c1
3
c1
4
c1
5
c1
6
c1
9
c1
8
c1
7
0
e∗
j′ = 1
0
c1
2
c1
3
c1
4
c1
5
c1
6
c1
7
c1
8
c1
9
0
e∗
MA
MB
Fig. 3. The approximate packing when n is even and p = 1.
The algorithm relies on a pair (MA, MB) of optimum weight matchings
on IA, IB. Given such a pair, together with some additional edge e∗, it aims
at computing a packing P s.t. Nα, α ∈{A, B}, is consistent with P, where
Nα coincides with Mα (resp., Mα ∪{e∗}) when n is odd (resp., even). Let H
denote the multigraph ([n+1], MA∪MB), and C1, . . . , Cp denote its connected
components. We assume w.l.o.g., that the depot vertex (i.e., node 0) coincides
with vertex c1
1 in C1. If n is odd (iffn+1 is even), then every component Ch is
an elementary cycle {ch
1, . . . , ch
qh, ch
1} of even length qh ≥2. Otherwise, Ch =
{ch
1, . . . , ch
qh, ch
1}\{{ch
ℓ, ch
ℓ+1}} is an elementary chain of even length qh −1 ≥0
for a lonely index h ∈[p]. We define the additional edge e∗as follows:
∀p,
e∗
= arg opt{ opt
α=A,B
{dα(f)} | f ∈F(p)}, where:
(2)
F(1) =
{0} ∪{c1
3, . . . , c1
ℓ}


×
{0} ∪{c1
ℓ+1, . . . , c1
n}

	
\{{0, 0}}
(3)
F(p) = ∪p
(h<h′)=1V (Ch) × V (Ch′)
(4)
The heuristic is described in Algorithm 1: it first computes Mα, α ∈{A, B}
(Step (i)) and e∗(case n even, Step (ii)); it then builds the approximate
packing P by considering the components the one after each other, starting
with C1 (Step (iv)); it finally computes the best tours T α(P), α ∈{A, B},
with respect to the P (Step (v)). Note that before it operates the packing,
the algorithm may have in Step (iii) to perform some reindexation of the Ch,
depending on e∗(notably, if p ≥2, then the two connected components that
are incident to e∗must be stacked consecutively). The even case is illustrated
in Figures 2 (p ≥2) and 3 (p = 1).
Claim 4.2
(i) Algorithm 1 has polynomial-time complexity.
(ii) Nα, α ∈{A, B}, is consistent with the approximate packing P.
(iii) The solutions returned by the algorithm are 3/2, 3/4 and 1/2 standard ap-
proximate for Min2STSP12, Max2STSP12 and Max2STSP, respectively;
these ratios are (asymptotically) tight.
Algorithm 1. An appproximate algorithm for 2STSP.
(i) Compute Mα an optimum weight matching on Iα, α ∈{A, B}
(ii) Determine the connected components of H in such a way that c1
1 = 0
If n is even Then compute e∗= arg opt{optα=A,B{dα(f)} | f ∈F(p)}
(iii) If n is even and p ≥2 Then consider the components in such a way that:
(a) If V (e∗) ∩V (C1) ∈{∅, {0}} Then ∃h ∈[p]\{1} s.t. e∗= {ch
⌈qh/2⌉, ch+1
1
}
Else e∗= {c1
j, c2
1} // h is taken modulo [p], j ∈{2, . . . , q1} depends on c1
1
(b) If q2 ̸= 2 ∧e∗= {c1
j, c2
1} ∧∃α, {{0, c1
2}, {c2
1, c2
q2}} ⊆Mα Then reverse C2
(iv) If n is odd or p ≥2:
j1 ←(If n ≡0[2] ∧e∗= {c1
j, c2
1} Then j: ⌈(q1 −1)/2⌉+ 1 otherwise)
j2 ←(If n ≡0[2] ∧e∗= {c1
2, c2
1} ∧q2 = 2 Then q2: ⌈q2/2⌉otherwise)
P 1 ←(c1
2, . . . , c1
j1,
c2
1, . . . , c2
j2,
c3
1, . . . , c3
⌈q3/2⌉
, . . . , cp
1, . . . , cp
⌈qp/2⌉)
P 2 ←(c1
q1, . . . , c1
j1+1, c2
q2, . . . , c2
j2+1, c3
q3, . . . , c3
⌈q3/2⌉+1 , . . . , cp
qp, . . . , cp
⌈qp/2⌉+1)
Else (thus p = 1, e∗= {c1
j, c1
j′}, j ∈{1}∪{3, . . . , ℓ}, j′ ∈{1}∪{ℓ+1, . . . , n+1}):
If j, j′ ̸= 1 and j ≡j′ + 1[2] Then P 1 ←(c1
2, . . . , c1
ℓ), P 2 ←(c1
n+1, . . . , c1
ℓ+1)
Else If j, j′ ̸= 1 and j ≡j′[2] Then P 1 ←(c1
2, . . . , c1
ℓ), P 2 ←(c1
ℓ+1, . . . , c1
n+1)
Else If j′ = 1 Then P 1 ←(c1
2, . . . , c1
j), P 2 ←(c1
n+1, . . . , c1
j+1)
Else If j = 1 Then P 1 ←(c1
2, . . . , c1
j′−1), P 2 ←(c1
n+1, . . . , c1
j′)
(v) Compute T α(P), α ∈{A, B}, the best feasible tour for P = (P 1, P 2) on Iα
Ch
⌈qh/2⌉−1
⌈qh/2⌉
⌈qh/2⌉+ 1
e∗
Ch+1
1
2
qh+1
Ch
⌈qh/2⌉−1
⌈qh/2⌉
⌈qh/2⌉+ 1
e∗
Ch+1
1
2
qh+1
C1
0
2
q1
e∗
C2
1
2
q2
MA
MB
Fig. 4. Case n even and p ≥2: edge e∗induces “no jump” in Mα.
Proof. Claim (i). Step (v) only requires a O((n+1)2)-time, [4]; for the other
steps, the fact is either famous, or trivial. Claim (ii). Nα, α ∈{A, B} triv-
ially satisfies Properties (ii) and (iii) (resp., (i)) of Propositon 4.1, in any case
(resp., when n is odd or p = 1). Thus assume n ≡0[2] and p ≥2. Steps (iii-a)
and (iv) of the algorithm indicate: ∃h ∈[p], ∃j ∈[qh] s.t. e∗= {ch
j , ch+1
1
} and
e∗∈P 1 × (P 1 ∪{0}). Mα possibly links ch
j (resp., ch+1
1
) to vertices (when
they exist) ch
j−1, ch
j+1 (resp., ch+1
1
, ch+1
qh+1), with ch
j−1 ∈P 1 (unless e = {c1
2, c2
1}),
ch
j+1 ∈P 2, ch+1
2
∈P 1 and ch+1
qh+1 ∈P 2 (unless e∗= {c1
2, c2
1} and q2 = 2). More-
over, Steps (iii-b) and (iv) ensure that P satisfies: ¬({0, c1
2} ∈Mα∧{c2
1, c2
q2} ∈
Mα) ∧(c2
1, c2
q2) ∈P 1 × P 2).
Hence, the chain {ch
j−1, ch
j , ch+1
1
, ch+1
qh+1} (resp.,
{ch
j+1, ch
j , ch+1
1
, ch+1
2
}) may never jump ch
j+1 (resp., ch+1
qh+1) in P 2 (see Figure 4
for some illustration). Claim (iii). Let (P∗, T A,∗, T B,∗) (resp., (P, T A, T B))
denote an optimum (resp., the approximate) solution, we denote by OPT
resp., APX) its value; we observe:
(i) ∀α in {A, B}, ∃N′α s.t. T ′α = Nα ∪N′α is a tour, and T ′α is consistent
with P. By optimality of T α with respect to P, we thus have:
dα(T α) ⪰dα(Mα) + dα(N′α) + 1n≡0[2]dα(e∗), α ∈{A, B}.
(ii) If n is odd, then any tour on [n+1] is the union of two perfect matchings
on [n + 1]. By optimality of Mα, we thus have: 2dα(Mα) ⪰dα(T α,∗).
(iii) If n is even, then ∀T tour on [n + 1], ∀e ∈T, T\{e} is the union of two
almost perfect perfect matchings on [n+ 1]. Furthemore, by connectivity
of T α,∗, ∃eα ∈T α,∗∩F(p), α ∈{A, B}. By optimality of Mα, we thus
have: 2dα(Mα) ⪰dα(T α,∗) −dα(eα).
From (i), (ii), (iii), we deduce:
2APX ⪰OPT + 2
X
α
dα(N′α) + 1n≡0[2](2
X
α
dα(e∗) −
X
α
dα(eα))
(5)
What enables to conclude for Max2STSP, when n is odd. When n is even,
just observe that e∗is optimal on F(p), whereas eα ∈F(p), α ∈{A, B}:
X
α
dα(e∗) ⪰opt
α {dα(e∗)} ⪰opt
α {dα(eα)} ⪰1/2
X
α
dα(eα)
(6)
For the bivalued case, any edge set S satisfies |S| ≤dα(S) ≤2|S|, α ∈
{A, B}. When n is odd, thus consider |T α,∗| = n + 1 = |N′α| and conclude:
1/2OPT ≤2(n + 1) ≤2
X
α
dα(N′α) ≤4(n + 1) ≤2OPT
(7)
When n is even, |N′α| = n. Let Q denote the quantity 2(dA(e∗)+dB(e∗))−
(dA(eA) + dB(eB)): if the goal is to maximize, assume that Q < 2; then
dA(e∗) + dB(e∗) = 2 and dA(eA) + dB(eB) ≥3, what contradicts the fact that
e∗is optimal. Similary, Q may not reach values 5, 6 when minimizing.
Tight instances In,a,b are defined on Kn+1, n ≥1, as: dα(u, v) = a if (v =
u+2∧u ≡1[4]) or (v = u+2∧u ≡0[4]∧α = A) or (v = u+2∧u ≡2[4]∧α = B)
or (v = u+1∧u ≡1[2]∧α = A) or (v = u+1∧u ≡0[2]∧α = B), dα(u, v) = b
otherwise. We consider subfamilies In,a,b s.t. (a, b) = (1, 0) (resp., (2, 1), (1, 2))
for Max2STSP (resp., Max2STSP12, Min2STSP12) and n = 8q−1 (resp., 8q)
for the odd (resp., even) case.
✷
Theorem 4.3 (Immediate form Claim 4.2) Min2STSP12, Max2STSP12
and Max2STSP respectively are 3/2, 3/4 and 1/2 standard approximable.
5
Conclusion
Two main questions arise from the proposed analysis: Min∆STP approxima-
bility, STSP differential approximability.
References
[1] Petersen H.L., Madsen O.B.G.: The double travelling salesman problem with
multiple stacks - Formulation and heuristic solution approaches. EJOR 198(1):
139-147 (2009)
[2] Felipe A., Ortu˜no M., Tirado G.: New neighborhood structures for the Double
Traveling Salesman Problem with Multiple Stacks. TOP 17(1):190-213 (2009).
[3] R. Lusbyz, J. Larsenz, M. Ehrgott, D. Ryan: An Exact Method for the Double
TSP with Multiple Stacks. Report 2.2009 DTU Management Engineering (2009).
[4] S. Toulouse, R. Wolfler Calvo: On the complexity of the multiple stack TSP,
kSTSP. TAMC 2009, LNCS 5532:360-369 (2009).
[5] A. Barvinok, D. S. Johnson, G. J. Woeginger, R. Woodroofe: The Maximum
Traveling Salesman Problem Under Polyhedral Norms. IPCO VI, LNCS
1412:195-201 (1998).
[6] C.H. Papadimitriou, M. Yannakakis: The traveling salesman problem with
distances one and two. Mathematics of Operations Research 18:1-11 (1993).
[7] Z.-Z. Chen, T. Nagoya: Improved approximation algorithms for metric MaxTSP.
J. of Combinatorial Optimization 13(4):321-336 (2007).
[8] Z.-Z. Chen, Y. Okamoto, L. Wang: Improved deterministic approximation
algorithms for Max TSP. Inform. Proc. Letters 95(2):333-342 (2005).
[9] H. Kaplan, N. Shafrir, M. Lewenstein, M. Sviridenko: Approximation Algorithms
for Asymmetric TSP by Decomposing Directed Regular Multigraphs. J. of the
ACM 52(4):602-626 (2005).
[10] M. Bl¨aser, L. Shankar Ram, M. Sviridenko: Improved approximation algorithms
for metric maximum ATSP and maximum 3-cycle cover problems. Operations
Research Letters 37(3):176-180 (2009).
[11] M. Bl¨aser: A 3/4-Approximation Algorithm for Maximum ATSP with Weights
Zero and One. APPROX-RANDOM 2004 LNCS 3122:61-71 (2004).
[12] P. Berman; M. Karpinski: 8/7-approximation algorithm for (1,2)-tsp. SODA
2006, ACM 641-648 (2006).