arXiv:1009.5029v1  [cs.CC]  25 Sep 2010
ON THE COMPLEXITY OF THE MULTIPLE
STACK TSP, kSTSP
Sophie Toulouse and Roberto Wolfler Calvo
LIPN (UMR CNRS 7030) - Institut Galil´ee, Universit´e Paris 13
99 av. Jean-Baptiste Cl´ement, 93430 Villetaneuse, France.
sophie.toulouse@lipn.univ-paris13.fr, wolfler@lipn.univ-paris13.fr
Abstract. Given a universal constant k, the multiple Stack Travelling
Salesman Problem (kSTSP in short) consists in finding a pickup tour T 1
and a delivery tour T 2 of n items on two distinct graphs. The pickup
tour successively stores the items at the top of k containers, whereas
the delivery tour successively picks the items at the current top of the
containers: thus, the couple of tours are subject to LIFO (“Last In First
Out”) constraints. This paper aims at finely characterizing the complex-
ity of kSTSP in regards to the complexity of TSP. First, we exhibit
tractable sub-problems: on the one hand, given two tours T 1 and T 2, de-
ciding whether T 1 and T 2 are compatible can be done within polynomial
time; on the other hand, given an ordering of the n items into the k con-
tainers, the optimal tours can also be computed within polynomial time.
Note that, to the best of our knowledge, the only family of combinatorial
precedence constraints for which constrained TSP has been proven to be
in P is the one of PQ-trees, [2]. Finally, in a more prospective way and
having in mind the design of approximation algorithms, we study the
relationship between optimal value of different TSP problems and the
optimal value of kSTSP.
1
Introduction
1.1
The problem specification
Assume that a postal operator has to pick up n items in some city 1, and then
to deliver the same items in some city 2. Such a situation can be modelized by
means of two TSP instances I1 = (G1, d1) and I2 = (G2, d2), where the two
graphs G1 = (V 1, E1) and G2 = (V 2, E2) have the same order n + 1 (vertex
0 represents the depot, whereas vertices [n] represent the location where the
items have to be picked up or delivered), and the distance functions d1 : E1 →
N, d2 : E2 →N associate integer values to the edges of G1, G2. The two TSP
instances I1, I2 thus represent the search of an optimal pickup tour in city 1,
and the search of an optimal delivery tour in city 2, respectively. If no constraint
occurs between the two tours, then the problem is equivalent to the resolution
of two independent TSP. In kSTSP, one assumes that the tours are subject to
LIFO contraints, namely: the pickup tour stacks the items into k containers,
so that the delivery tour must deliver at first the items that have been stored
at last by the pickup tour. Hence, a solution of kSTSP consists of a couple
of tours (T 1, T 2), together with a stacking order P on the k containers that is
compatible with both the pickup and the delivery tours. Here, a stacking order is
defined as a set {P 1, . . . , P k} of k qℓ-uples P ℓ= (vℓ
1, . . . , vℓ
qℓ) that partitions [n],
where vertices vℓ
1 and vℓ
qℓrespectively represent the bottom and the top of the
ℓth stack. A feasible solution (T 1, T 2, P) is optimal if it is of optimal distance,
where the distance is given by the sum d1(T 1) + d2(T 2) of the distances of the
two tours. For sake of simplicity, we will always consider that G1 and G1 are
the complete directed graph Kn+1 on V = {0} ∪[n]. In the case of symetric
distance functions, one just has to consider dα(u, v) = dα(v, u) for u, v ∈V
and α ∈{1, 2}; moreover, one could recognize unexisting arcs by associating
to each couple of vertices u, v ∈V such that (u, v) /∈Eα, e.g., the distance
dα(u, v) = dα
max + 1, where dα
max = max{dα(e) | e ∈Eα}.
1.2
Related work & outline
By contrast to other TSP problems, only a few literature exists on this problem
(see, for example, [3,8] for some heuristic approaches), and none (to the best of
our knowledge) about its complexity. Anyway, the problem we address naturally
is NP −hard, from TSP.
Nevertheless, one could wonder about what combinatorial structure of kSTSP
impacts more on its complexity: the stacks (and the LIFO constraints they in-
duce on the tours), or the permutations themselves? The answer is not clear and
this paper shows why. First of all we prove that, given two tours T 1 and T 2,
deciding whether T 1 and T 2 are compatible or not is tractable, since the decision
reduces to k-coloring in comparability graphs. Moreover, given an ordering of
the n items into the k stacks, the optimal tours can also be computed within
polynomial time, by means of dynamic programming. Another interesting ques-
tion concerns the relative complexity of kSTSP in regards to TSP: how much its
trickier combinatorial structure makes kSTSP harder to solve (exactly as well
as approximatively) than TSP? Although we do not provide formal answers to
this latter question, we give some intuition that kSTSP is globally harder than
general TSP to optimize: it is obvious that efficient algorithms for kSTSP can
be derived in order to solve TSP; by contrast, we establish that tours of good
quality for TSP may lead to arbitrary low quality solutions for STSP.
The paper is organized as follows: we first expose in section 2 some notations
and properties that will be useful for the next sections; section 3 exhibits two
tractable sub-problems (one of decision when the tours are given, 3.2, one of
optimization when the stacks are given, 3.3); section 4 compares the behaviour
of solution values in STSP instances and some related TSP instances, bringing
to the fore that good resolution of TSP may not lead to good resolution of STSP;
finally, section 5 concludes with some perspectives.
2
Preliminaries
Three strict orders <1, <2, <3 on [n] are associated, respectively, to the pickup
tour T 1 = (0, u1
1, . . . u1
n, 0), to the delivery tour T 2 = (0, u2
1, . . . u2
n, 0) and to a
stacking order P = {P 1, . . . , P k}. The two orders <1, <2 are complete whereas
<3 is partial. It means that ∀a ̸= b ∈[n] we can write:
<1:
a <1 b
⇔T 1 picks up a before b
<2:
a <2 b
⇔T 2 delivers b before a
<3:
a <3 b
⇔∃ℓ∈[1, k] / a, b ∈P ℓ, a is stacked before b in P ℓ
¬(a <3 b) ∧¬(a <3 b) ⇔a, b are stacked into two distinct stacks
Lemma 1. A solution (T 1, T 2, P) is feasible iffthe three orders <1, <2, <3 it
induces on [n] satisfy the following conditions:
∀a ̸= b ∈[n], a <1 b ⇒¬(a >3 b)
(1)
∀a ̸= b ∈[n], a <2 b ⇒¬(a >3 b)
(2)
Proof. The necessary condition is obvious. For the sufficient condition, let con-
sider a pickup tour T 1 and a stacking order P (the argument is rather similar
for the delivery tour). For any i ∈[n], T 1 has to pick up the item u1
i , that is
of index j in some stack P ℓ; this is possible iffthe previous item that T 1 has
picked up in P ℓis the item uℓ
j−1, or there is no such index and j = 1, what is
always true if T 1 and P verify condition (1).
⊓⊔
3
Complexity classes and properties
3.1
Global complexity
The problem obviously is NP −hard, for arbitrary instances (G1, d1; G2, d2) of
kSTSP (where by “arbitrary”, we mean that we do not make any asumption,
neither on the graph completeness, nor on the symetry of the distance functions).
When the distance functions d1 and d2 are the same, up to the arc direction (that
is, d1(a, b) = d2(b, a) for all a, b ∈{0} ∪[n]), it is equivalent to the regular TSP
(consider on the one hand that T 1 = (0, u1, . . . , un, 0) is an optimal pickup tour
iffT 2 = (0, un, . . . , u1, 0) is an optimal delivery tour, on the other hand that
every stacking order that is feasible for T 1 also is feasible for T 2). Second, for
a given triple (T 1, T 2, P) where T 1, T 2 are two tours on {0} ∪[n] and P is a
stacking order of [n] using k stacks, checking whether (T 1, T 2, P) is feasible or
not can be done within linear time (quite immediate from Lemma 1).
3.2
Deciding feasibility for a couple of tours
Let us denote by G̸= = (V ̸=, E̸=) the graph induced by the set of pairs {a, b}
such that the two orders <1 and <2 are discordant:
E̸= = { {a, b} | a ̸= b ∈[n], a <1 b ∧a >2 b }, V ̸= =
[
{a,b}∈E̸=
{a, b}
Lemma 2. Given two tours T 1, T 2, a compatible stacking order P exists iff
χ(G̸=) ≤k, where χ(G̸=) denotes the chromatic number on G̸=.
Proof. For the necessary condition, consider a feasible solution (T 1, T 2, P) and
two items a ̸= b such that {a, b} ∈E̸=, iffa <1 ∧a >2 b, or a >1 b ∧a <2 b. In
both cases, we know from Lemma 1 that ¬(a >3 b)∧¬(a >3 b); thus, the k stacks
in P correspond to k independent sets in G̸=. For the sufficient condition, we
build from a k-coloring on V ̸= a stacking order P that fulfills, together with T 1
and T 2, conditions (1) and (2) of Lemma 1. We first fill each stack P ℓwith the
items of the ℓth color set {vℓ
1, . . . , vℓ
qℓ}, by considering on P ℓthe order induced
by the relation <1,2 defined as: <1,2=<1 ∧<2 (the two orders do coincide
on each color ℓ). It remains to insert into the stacks the items from [n]\V ̸=.
The orders <1 and <2 also coincide on ([n]\V ̸=) × [n]; we can therefore write
[n]\V ̸= = (v1, . . . , vr) with v1 <1,2 . . . <1,2 vr. For index i from 1 to r, we insert
vi in position j(vi) + 1 in P 1 iffj(vi) is the current maximum index j such that
v1
j <1,2 vi, if such an index exists; otherwise, j(vi) = 0 (in any case, indices in
P 1 are updated after each insertion). We finally obtain a partition of [n] within
a set of k stacks such that in every stack, the elements are ordered with respect
to <1,2, what fulfills conditions (1) and (2).
⊓⊔
Graph coloring problems (in general, but also k-coloring for a universal con-
stant k ≥3) are known to be NP −c (see, e.g., [4]); nevertheless, it turns out
that G̸= belongs to the class of perfect graphs, for which determining χ(G) is in
P, [6]. Hence, the considered decision problem is tractable, for any k (and this
even if k is not any longer considered as a universal constant, but as being part
of the input).
Theorem 1. The STSP sub-problem that consists, given a couple (T 1, T 2), in
deciding whether there exists or not a compatible stacking order, is in P.
Proof. E̸= represents the pairs {a, b} of [n] such that (a <1 b ∧a >2 b) or (a >1
b ∧a <2 b), where we recall that <1 and <2 both totally order [n]. Therefore,
G̸= is a comparability graph. Indeed, consider the set of arcs F ̸= = {(a, b) ∈
[n] × [n] | a <1 b ∧a >2 b}: (i) for all a ̸= b ∈V ̸=, (a, b) ∈F ̸= ∨(b, a) ∈F ̸=
iff{a, b} ∈E̸=; (ii) for all a ̸= b ∈V ̸=, (a, b) ∈F ̸= ⇒(b, a) /∈F ̸=; (iii) for all
distinct a, b, c ∈V ̸=, (a, b) ∈F ̸= and (b, c) ∈F ̸= iffa <1 b <1 c ∧a >2 b >2 c
and thus, (a, c) ∈F ̸=. Then, F ̸= defines a transitive orientation of the edge set
E̸=, and G̸= is a comparability graph. By the way, note that a comparability
graph G = (V, E) may represent the conflict graph of some couple or orders
(<1, <2) iffits complementary graph G = (V, E) also is a comparability graph
(representing <1 ∧<2). Algorithm 1 is a polynomial time procedure that, given
a couple of tours (T 1, T 2), responses NO if this couple is unfeasible, returns a
compatible stacking order P otherwise.
⊓⊔
3.3
Optimizing the tours when the stacks are given
In this section, we prove that it is a tractable problem to compute the optimal
tours, when the stacks are fixed.
Algorithm 1: STACKING FROM T 1 AND T 2
Input: T 1 a pickup tour, T 2 a delevery tour, k the number of stacks.
Output: A compatible stacking order P iff(T 1, T 2) is feasible.
for ℓ= 1 to k do P ℓ←−∅;
build G̸= = (V ̸=, E̸=) from T 1, T 2;
// Coloring stage
for each v ∈[n]\V ̸= do C(v) ←−1;
compute a minimum coloring
C : V ̸= →[χ(G̸=)], v 7→C(v)


on G̸=;
if χ(G̸=) > k then return NO;
// Stacking stage (done according to <1)
for i = 1 to n do { ℓ←−C(u1
i ); stack u1
i into P ℓ};
return P = {P 1, . . . , P k};
Theorem 2. For a given stacking order P, one can find an optimal pickup tour
and an optimal delivery tour within polynomial time (but exponential in k).
Proof. We only present the argument for the pickup tour (the proof being rather
similar for the delivery tour). Let P = P 1, . . . , P k where P ℓ= (vℓ
1, . . . , vℓ
qℓ) for
any ℓbe a stacking order. A pickup tour that is compatible with P starts by
picking up the items which must be placed at the bottom of each stack, until
all the stacks have been completely read. Hence, we will consider the space of
states S = ×k
ℓ=1[0, qℓ], where a state e = (e1, . . . , ek) ∈S represents the set of
items on each stack that have already been picked up. Therefore, eℓ= h means
that items vℓ
1, . . . , vℓ
h have been collected, and that the current bottom (that
is, its (h + 1)th element vℓ
h+1) is the next item in P ℓthat has to be picked
up. Let denote with W(e) = ∪k
ℓ=1{vℓ
1, . . . , vℓ
eℓ} the set of collected items once
the state e has been reached. Althought there are (in general) an exponential
number of paths to reach a given state e, there are only (at most) k possible
preceding states, depending on which stack has been considered at last. Hence,
we associate to each state e its list of possible predecessors p(e, 1), . . . , p(e, k),
where p(e, ℓ) = (e1, . . . , eℓ−1, eℓ−1, eℓ+1, . . . , ek), for e and ℓsuch that eℓ≥1.
In order to build an optimal tour, we associate to each state e a collection
of k labels that correspond to its cost. For any e ̸= (0, . . . , 0) ∈S, and for any
ℓ∈[k], the label E(e, ℓ) gives the minimum cost for picking up all the items of
W(e) starting from 0, compatible with P, and that end with P ℓ. According to
this definition, E(e, ℓ) may only depend on E(p(e, ℓ), ℓ′), for ℓ′ ∈[k]: the current
sub-tour T 1 may reach e after having picked up vℓ
eℓiffvℓ
eℓhas not been picked up
yet. Then, for any e ̸= (0, . . . , 0), (q1, . . . , qk) ∈×k
ℓ=1[0, qℓ] and for any ℓ∈[k],
we have the following reccurrence relation:
E(e, ℓ) =
(
+∞
if eℓ= 0
mink
ℓ′=1{E(p(e, ℓ), ℓ′) + d1(vℓ′
p(e,ℓ)ℓ′ , vℓ
eℓ) | p(e, ℓ)ℓ′ ≥1} if eℓ≥1
Note that item vℓ′
p(e,ℓ)ℓ′ differs from vℓ′
eℓ′ (that is, p(e, ℓ)ℓ′ differs from eℓ′) iff
ℓ′ = ℓ. The initial conditions are given by the k states f(ℓ) = (0, . . . , 0, 1, 0, . . ., 0)
that correspond to the ℓth canonical vectors:
E(f(ℓ), ℓ′) =

+∞if ℓ′ ̸= ℓ, d1(0, vℓ
1) if ℓ′ = ℓ
	
Finally, the expression of the labels on the final state F = (q1, . . . , qk) is the
following (for ℓsuch that F ℓ≥1):
E(F, ℓ) =
k
min
ℓ′=1{E(p(F, ℓ), ℓ′) + d1(vℓ′
p(F,ℓ)ℓ′ , vℓ
qℓ) + d1(vℓ
qℓ, 0) | p(F, ℓ)ℓ′ ≥1}
Algorithm 2: optimal PICKUP TOUR(P)
Input: I = (d1, d2) an instance of kSTSP, P a stacking order on I.
Output: An optimal pickup tour T 1 that is compatible with P.
// Initialization stage
for e ∈S, ℓ∈[k] s.t. eℓ= 0 do E(e, ℓ) ←−+∞;
for ℓ∈[k] do E(f(ℓ), ℓ) ←−d1(0, vℓ
1);
// Dynamic procedure
for p = 2 to n −1 do
for e ∈S s.t. |e| = p do
for ℓ= 1 to k s.t. eℓ≥1 do
E(e, ℓ) ←−mink
ℓ′=1{ E(p(e, ℓ), ℓ′) + d1(vℓ′
p(e,ℓ)ℓ′ , vℓ
eℓ) | p(e, ℓ)ℓ′ ≥1 };
// Termination
for ℓ= 1 to k s.t. F ℓ≥1 do
E(F, ℓ) ←−
k
min
ℓ′=1{ E(p(F,ℓ), ℓ′)+d1(vℓ′
p(F,ℓ)ℓ′, vℓ
F ℓ)+d1(vℓ
F ℓ, 0) | p(F, ℓ)ℓ′ ≥1 };
return T 1 the tour associated with the label arg min{E(F, qℓ) | ℓ= 1, . . . , k};
The optimal value is the minimal cost among E(F, 1), . . . , E(F, k), since any
feasible pickup tour must end with the top of some stack. Furthermore, the
recurrence relation indicates that the labels of a state e (including F) such that
|e| = p (where | · | denotes the Hamming norm) only depend on a subset of
the states e′ such that |e|′ = p −1. Based on these observations, Algorithm 2
computes an optimal pickup tour within polynomial time. The number of states
to consider is upper bounded by (n+1)k−1 (the worst configuration occurs when
the items are fairly distributed in the k stacks). The computation of the k labels
of a given state requires at worst k2 comparisons and the global complexity is
O((n + 1)k). Note that the computation of an optimal delivery tour is perfectly
symetric, considering the reverse order on each stack.
⊓⊔
4
Evaluating optimal kSTSP vs. optimal TSP
In this section, we discuss relationships between solution values of the two TSP
tours and the optimal value of the kSTSP. For a given instance I = (d1, d2) of the
kSTSP, we define the two instances I1 = (Kn+1, d1) and I2 = (Kn+1, d2) of the
TSP. The optimal values (resp., the worst solution values) on I1, I2 (for the TSP)
and I (for the kSTSP) are respectively denoted by optT SP (I1), optT SP (I2) and
optkST SP (I) (resp., by worT SP (I1), worT SP (I2) and workST SP (I)). For any I,
these extremal values obviously verify relations (3) and (4). Any feasible couple
(T 1, T 2) for the kSTSP is feasible for the couple of TSP instances (I1, I2). For
any tour T 1 on I1 (resp., T 2 on I2), there exists a compatible tour T 2 (resp.,
T 1). Note that for this latter fact (and thus, for relation 5), we must assume
that the underlying graphs are complete.
optT SP (I1) + optT SP (I2) ≤optkST SP (I)
(3)
workST SP (I) ≤worT SP (I1) + worT SP (I2)
(4)
optkST SP (I) ≤
optT SP (I1) + worT SP (I2)
worT SP (I1) + optT SP (I2)

≤workT SP (I)
(5)
In particular we discuss the results obtained by two simple heuristics denoted
here after TWS and TWD and based on the idea of solving to optimality a single
TSP. TWS builds a solution of the kSTSP, by solving to optimality the delivery
tour, while the pickup tour is fixed (or the reverse). TWD determines a solution
for the kSTSP, by solving to optimality a single stack TSP on a graph whose
distance function is obtained by summing up the original distance functions.
We prove that both TWS and TWD give an unbouded error, when particular
instances families are considered. Let’s introduce some more notations. Given the
TSP solutions T ′1, T ′2 for I1, I2, we denote by opt2ST SP |T ′1 (resp. opt2ST SP |T ′2)
the best solution value for the kSTSP on I, among the solutions (T 1, T 2, P)
where T 1 = T ′1 (resp., T 2 = T ′2). The optimal TSP tours on I1, I2 are denoted
by T 1,∗, T 2,∗, respectively. Moreover, for a given α ∈]0, 1[, we denote by Iα the
TSP instance on Kn+1 with distance function dα = 2
αd1 + (1 −α)(d2)−1

,
where (d2)−1 is defined as (d2)−1(a, b) = d2(a, b) for any couple (a, b) of items.
The optimal tour on Iα will be denoted by T ∗
α.
Lemma 3. We consider arbitrary distance functions d1, d2 (symetric or not).
1. For a ∈{1, 2}, the optimal value opt2ST SP |T ∗,a(I) verifies:
infI∈I2ST SP opt2ST SP |T a,∗(I)/opt2ST SP (I) = +∞
2. For α = 1/2, the quantities d1(T ∗
α) + d2(T ∗
α) and opt2ST SP (I) verify:
inf
I∈I2ST SP
d1(T ∗
α) + d2(T ∗
α)


/opt2ST SP (I) = +∞
Proof. 3-1, the asymetric case. Consider the instance family (In)n≥3, In =
(d1
n, d2
n), defined as (indexes are taken modulo n + 1):
d1
n(u, v) =

1
if v = u + 1
1 + ε
otherwise d2
n(u, v) =

1 if v = u + 1
n otherwise
The optimal values for TSP on I1
n and I2
n both are n + 1, reached by the
tours T 1,∗
n
= T 2,∗
n
= (0, 1, 2, . . ., n, 0). If we fix T ′1
n = T 1,∗
n , then any stacking
order Pn = {P 1
n, P 2
n} that is compatible with T ′1
n will order the items in such a
way that contradicts the order induced by the optimal delivery tour. In order to
evaluate the best possible compatible T 2
n, we consider three cases:
– Case (0, 1) ∈T 2
n: 1 >2 u ∀u ̸= 1 ∈[n], 1 <1 u ∀u ̸= 1 and thus, item 1 is non
comparable to any other item under <3; hence, P a
n = (1), P 3−a
n
= (2, . . . , n)
(for a ∈{1, 2}), T 2
n = (0, 1, n, n −1, . . . , 3, 2, 0) and d2
n(T 2
n) = 1 + n2.
– Case (n, 0) ∈T 2
n: by means of a similar argument, we obtain P a
n = (n), P 3−a
n
=
(1, . . . , n −1), T 2
n = (0, n −1, n −2, . . . , 2, 1, n, 0) and d2
n(T 2
n) = 1 + n2.
– Case (0, 1), (n, 0) /∈T 2
n: consider any item u ∈[n]\{1, n}, and assume (u −
1, u), (u, u + 1) ∈T 2
n; we then deduce from u −1 >2 u >2 u + 1 and u −1 <1
u <1 u + 1 that items u −1, u and u + 1 are pairwise non comparable under
<3, what is not possible for k = 2. Hence, T 2
n uses at least one arc (resp.,
exactly 2 arcs) of distance n per item v ∈[n] (resp., for the depot 0) and
thus, d2
n(T 2
n) ≥1/2(n(n + 1) + 2n) = n(n + 3)/2.
Moreover, the following solution is optimal for In, of value 2(n + 1) + (⌊(n +
1)/2⌋+ 1)ε; it consists in stacking items of odd and even values by decreasing
order into separated containers, which enables to use the delivery tour T 2
n = T 2,∗
n ,
while putting into T 1
n a maximum number of arcs of kind (u, u + 1) (figure 1
illustrates instance In for even value of n):
P 1
n = (n, n −2, . . . , n −2i, . . . , n −2⌊(n −1)/2⌋)
P 2
n = (n −1, n −3, . . . , n −(2i + 1), . . . , n −(2⌊(n −2)/2⌋+ 1))
Tn = {(0, n −1)} ∪{(n −(2i + 1), n −2i, n −(2i + 3)) | i = 0, . . . , ⌊(n −4)/2⌋}
T 1
n = T ∪{(2, 0)} if n even, T ∪{(3, 1), (1, 0)} if n odd
T 2
n = (0, 1, . . . , n, 0)
We thus get the expected result (note by the way that, since optT SP (I1
n) +
worT SP (I2
n) = (n + 1)2, the ratio opt2ST SP |T ′1
n (In)/(optT SP (I1
n) + worT SP (I2
n))
is asymptotically 1/2):
opt2ST SP |T ′1
n (In) ≥(n + 1) + n(n + 3)/2
opt2ST SP (In)
≤(n + 1)(2 + ε)

⇒
opt2ST SP |T ′1
n (In)
opt2ST SP (In)
−→
n→+∞+∞
3-1, the symetric case. Consider (Jn)n≥6, Jn = (d1
n, d2
n), defined as (see fig-
ure 2 for an illustration):
d1
n(u, v) =
1
if v = u ± 1
1 + ε
otherwise d2
n(u, v) =
1 if v + u ∈{n, n + 1}
n otherwise
The tours T 1,∗
n
= (0, 1, 2, . . ., n, 0) and T 2,∗
n
= (0, n, 1, n−1, 2, n−2, 3 . . ., ⌈n/2⌉, 0)
are optimal on J1
n, J2
n, of value n + 1 and 2n, respectively. Similary to the asy-
metric case, we show that, for items u = 2, . . . , n−1 such that 2u /∈{n−1, n, n+
1, n + 2}, any tour T 2
n thas is compatible with T ′1
n = T 1,∗
n
cannot use the whole
(undirected) sequence1:
{u + 1, n −u, u, n + 1 −u, u −1}
Hence, opt2ST SP |T ′1
n (Jn) ≥(n+1)+((n−4)(3+n)+5∗4)/4 ≥n2/4, whereas
the following solution is of value 3n + 2ε −1 (case n even):
P 1
n = (1, 2, 3, . . ., n/2),
P 2
n = (n, n −1, n −2, . . . , n/2 + 1)
T 1
n = (0, 1, 2, . . ., n/2; n, n −1, . . . , n/2 + 2, n/2 + 1; 0)
T 2
n = (0, n, 1, n −1, 2, . . . , n/2 −1, n/2 + 1, n/2; 0)
3-2. Consider the following symetric instance family (Hn)n≥3:
condition
d1
n(u, v) d2
n(u, v) d1
n(u, v) + d2
n(u, v)
if
v = u ± 1
1
n
n + 1
else if
v = u ± 2
1
n + 1
n + 2
else if
u + v ∈{n + 1, n + 3} n + 1
1
n + 2
else
n + 1
n + 1
2n + 2
The tour T ∗
n,1/2 = (0, 1, 2, . . . , n, 0) that is optimal for the aggregate distance
function is of value (n + 1)2, whereas there exists a couple (T 1,∗
n , T 2,∗
n ) of com-
patible optimal tours with d1
n(T 1,∗
n ) = n + 1 and d2
n(T 2,∗
n ) = (n −3) + 5(n + 1)
(for n even) or d2
n(T 2,∗
n ) = (n −4) + 6(n + 1) (for n odd); hence, the following
solution of 2STSP is optimal, of value in {7n + 2, 8n + 2} (case n even):
P 1
n = (1, 3, 5, . . ., n −3, n −1),
P 2
n = (n, n −2, n −4, . . . , 4, 2)
T 1
n = (0; 1, 3, . . ., n −3, n −1; n, n −2, . . . , 4, 2, 0)
T 2
n = (0; 1, n, 3, n −2, 5, . . ., 6, n −3, 4, n −1, 2; 0)
Note that there exist simplier instance families verifying that dn,1/2(T ∗
n,1/2)
is arbitrarly large vs. opt2ST SP ; however, for more relevancy, we built (Hn)(n)
in such a way that T ∗
n,1/2 and the couple (T 1,∗
n , T 2,∗
n ) are not compatible.
⊓⊔
5
Conclusion
This paper address the time complexity of kSTSP, whose highly combinatorial
structure suggests the search of approximation algorithms (may be the most
likely for the differential ratio, [7]). The good complexity of its sub-problems
makes relevant the design of exact methods based on constraints decomposition
1 due to lack of space, the proof is not provided here; please contact the authors for
further information
0
1
2
n/2
n
n −1
n/2 + 1
d1
n, d2
n: arcs of distance 1
P 1
n:
n −1
n −3
3
1
P 2
n:
n
n −2
4
2
0
0
0
0
The optimal tours:
T 1
n in plain lines, T 2
n in dashed lines
Fig. 1. Instance In for n even.
0
1
2
n/2
n
n −1
n/2 + 1
d1
n (plain lines), d2
n (dashed lines):
edges of distance 1
P 1:
1
2
n/2 −1
n/2
P 2:
n
n −1
n/2 + 2
n/2 + 1
0
0
0
0
The optimal tours:
T 1
n in plain lines, T 2
n in dashed lines
Fig. 2. Instance Jn for n even.
of kSTSP. Finally, it would be interesting to better characterize the shape of
precedence constraints for which TSP/sequencing under precedence contraints
are tractable. Indeed, we deduce from Theorem 2 that TSP under “stack prece-
dence constraints” is in P. Equivalently, the single machine scheduling with
sequence-dependent time or cost setup under the same shape of constraints, that
we denote by (1/k-stack,p,STsd/Cmax) ≡(1/k-stack,p,STsd/TST) and (1/k-
stack,p,SCsd/T SC), are tactable (for the notations used in order to represent
the α/β/γ-classification, [5] of scheduling problems, we refer to [1]). Here, by
“stack precedence constraints”, we mean that the constraints define a partial
order on [n] within at most k ordered subsets, where k is a universal constant.
References
1. Allahverdi A., Gupta J.N.D., Aldowaisan T.: A review of scheduling research in-
volving setup considerations. Omega 27(2):219-239 (1999).
2. Burkard R.E., Deineko V.G., Woeginger G.J.: The Travelling Salesman and the
PQ-Tree. In Proc. 5th Internat. IPCO Conference, LNCS 1084:490-504 (1996).
3. Felipe A., Ortu˜no M., Tirado G.: Neighborhood structures to solve the double TSP
with multiple stacks using local search. in Proc. of FLINS 2008 (2008).
4. Garey M.R., Johnson D.S.: Computers and intractability: a guide to the theory of
NP-completeness. CA, Freeman (1979).
5. Graham R.L., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G.: Optimization and
approximation in deterministic sequencing and scheduling: a survey. Ann. of Discrete
Math. 5:287-326 (1979).
6. Gr¨otschel M., Lov´asz L., Schrijver A.: The ellipsoid method and its consequences
in combinatorial optimization. Combinatorica 1(2):169-197 (1981).
7. Monnot J.: Differential approximation results for the Traveling Salesman and related
problems. Information Processing Letters 82(5):229-235 (2002).
8. Petersen H.L., Madsen O.B.G.: The double travelling salesman problem with multi-
ple stacks - Formulation and heuristic solution approaches. EJOR (2008, in press).