arXiv:1009.5029v1 [cs.CC] 25 Sep 2010  ON THE COMPLEXITY OF THE MULTIPLE STACK TSP,   k STSP  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 ( k STSP 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   k STSP 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   k STSP.  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   I 1   = ( G 1 , d 1 ) and   I 2   = ( G 2 , d 2 ), where the two graphs   G 1   = ( V   1 , E 1 ) and   G 2   = ( V   2 , E 2 ) 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   d 1   :   E 1   →  N , d 2   :   E 2   →   N   associate integer values to the edges of   G 1 , G 2 . The two TSP instances   I 1 , I 2   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   k STSP, 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   k STSP 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   d 1 ( T   1 ) +   d 2 ( T   2 ) of the distances of the two tours. For sake of simplicity, we will always consider that   G 1   and   G 1   are the complete directed graph   K n +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   k STSP 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   k STSP in regards to TSP: how much its trickier combinatorial structure makes   k STSP 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   k STSP is globally harder than general TSP to optimize: it is obvious that efficient algorithms for   k STSP 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 , u 1 1 , . . . u 1  n ,   0), to the delivery tour   T   2   = (0 , u 2 1 , . . . u 2  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   6   =   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 iff the three orders   < 1 ,   < 2 ,   < 3   it induces on   [ n ]   satisfy the following conditions:  ∀ a   6   =   b   ∈   [ n ] , a < 1   b   ⇒ ¬ ( a > 3   b )   (1)  ∀ a   6   =   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   u 1  i   , that is of index   j   in some stack   P   ℓ ; this is possible iff the 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 ( G 1 , d 1 ;   G 2 , d 2 ) of  k STSP (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   d 1   and   d 2   are the same, up to the arc direction (that is,   d 1 ( a, b ) =   d 2 ( b, a ) for all   a, b   ∈ { 0 } ∪   [ n ]), it is equivalent to the regular TSP (consider on the one hand that   T   1   = (0 , u 1 , . . . , u n ,   0) is an optimal pickup tour iff   T   2   = (0 , u n , . . . , u 1 ,   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 6  =   = ( V   6   = , E 6   = ) the graph induced by the set of pairs   { a, b }  such that the two orders   < 1   and   < 2   are discordant:  E 6   =   =   { { a, b } |   a   6   =   b   ∈   [ n ] , a < 1   b   ∧   a > 2   b   } , V   6   =   =   ⋃  { a,b }∈ E 6   =  { a, b }
Lemma 2.   Given two tours   T   1 ,   T   2 , a compatible stacking order   P   exists iff  χ ( G 6  = )   ≤   k , where   χ ( G 6  = )   denotes the chromatic number on   G 6  = . Proof.   For the necessary condition, consider a feasible solution ( T   1 , T   2 ,   P ) and two items   a   6   =   b   such that   { a, b } ∈   E 6   = , iff   a < 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 6  = . For the sufficient condition, we build from a   k -coloring on   V   6   =   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   6   = . The orders   < 1   and   < 2   also coincide on ([ n ] \ V   6   = )   ×   [ n ]; we can therefore write [ n ] \ V   6   =   = ( v 1 , . . . , v r ) with   v 1   < 1 , 2   . . . < 1 , 2   v r   . For index   i   from 1 to   r , we insert  v i   in position   j ( v i ) + 1 in   P   1   iff   j ( v i ) is the current maximum index   j   such that  v 1  j   < 1 , 2   v i , if such an index exists; otherwise,   j ( v i ) = 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 6  =   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 6   =   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 6  =   is a comparability graph. Indeed, consider the set of arcs   F   6   =   =   { ( a, b )   ∈  [ n ]   ×   [ n ]   |   a < 1   b   ∧   a > 2   b } : ( i ) for all   a   6   =   b   ∈   V   6   = , ( a, b )   ∈   F   6   =   ∨   ( b, a )   ∈   F   6   =  iff   { a, b } ∈   E 6   = ; ( ii ) for all   a   6   =   b   ∈   V   6   = , ( a, b )   ∈   F   6   =   ⇒   ( b, a )   / ∈   F   6   = ; ( iii ) for all distinct   a, b, c   ∈   V   6   = , ( a, b )   ∈   F   6   =   and ( b, c )   ∈   F   6   =   iff   a < 1   b < 1   c   ∧   a > 2   b > 2   c  and thus, ( a, c )   ∈   F   6   = . Then,   F   6   =   defines a transitive orientation of the edge set  E 6   = , and   G 6  =   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 ) iff its 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 6  =   = ( V   6   = , E 6   = ) from   T   1 ,   T   2 ;  // Coloring stage  for each   v   ∈   [ n ] \ V   6   =   do   C ( v )   ←−   1; compute a minimum coloring   ( C   :   V   6   =   →   [ χ ( G 6  = )] , v   7   →   C ( v ) )   on   G 6  = ;  if   χ ( G 6  = )   > k   then return   NO;  // Stacking stage (done according to   < 1 )  for   i   = 1   to   n   do   {   ℓ   ←−   C ( u 1  i   ); stack   u 1  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   = ( e 1 , . . . , e k )   ∈ 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, ℓ ) = ( e 1 , . . . , e ℓ − 1 , e ℓ   −   1 , e ℓ +1 , . . . , e k ), 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   6   = (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 ℓ   iff   v ℓ e ℓ   has not been picked up yet. Then, for any   e   6   = (0 , . . . ,   0) ,   ( q 1 , . . . , q k )   ∈ × k ℓ =1 [0 , q ℓ ] and for any   ℓ   ∈   [ k ], we have the following reccurrence relation:  E ( e, ℓ ) =  {   + ∞   if   e ℓ   = 0 min k ℓ ′   =1 {E ( p ( e, ℓ ) , ℓ ′ ) +   d 1 ( 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   ℓ ′   6   =   ℓ, d 1 (0 , v ℓ  1 ) if   ℓ ′   =   ℓ   }  Finally, the expression of the labels on the final state   F   = ( q 1 , . . . , q k ) is the following (for   ℓ   such that   F   ℓ   ≥   1):  E ( F, ℓ ) =   k  min  ℓ ′ =1 {E ( p ( F, ℓ ) , ℓ ′ ) +   d 1 ( v ℓ ′  p ( F,ℓ ) ℓ ′   , v ℓ q ℓ   ) +   d 1 ( v ℓ q ℓ   ,   0)   |   p ( F, ℓ ) ℓ ′  ≥   1 }  Algorithm 2:   optimal PICKUP TOUR( P )  Input :   I   = ( d 1 , d 2 ) an instance of   k STSP,   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   ( ℓ ) , ℓ )   ←−   d 1 (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, ℓ )   ←−   min k ℓ ′ =1 { E   ( p ( e, ℓ ) , ℓ ′ ) +   d 1 ( 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, ℓ ) , ℓ ′ ) +   d 1 ( v ℓ ′  p ( F,ℓ ) ℓ ′   , v ℓ F   ℓ   ) +   d 1 ( 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   k 2   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   k STSP   vs.   optimal TSP  In this section, we discuss relationships between solution values of the two TSP tours and the optimal value of the   k STSP. For a given instance   I   = ( d 1 , d 2 ) of the  k STSP, we define the two instances   I 1   = ( K n +1 , d 1 ) and   I 2   = ( K n +1 , d 2 ) of the TSP. The optimal values ( resp. , the worst solution values) on   I 1 ,   I 2   (for the TSP) and   I   (for the   k STSP) are respectively denoted by opt T SP   ( I 1 ), opt T SP   ( I 2 ) and opt kST SP   ( I ) ( resp. , by wor T SP   ( I 1 ), wor T SP   ( I 2 ) and wor kST SP   ( I )). For any   I , these extremal values obviously verify relations (3) and (4). Any feasible couple ( T   1 , T   2 ) for the   k STSP is feasible for the couple of TSP instances ( I 1 , I 2 ). For any tour   T   1   on   I 1   ( resp. ,   T   2   on   I 2 ), 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. opt T SP   ( I 1 ) + opt T SP   ( I 2 )   ≤   opt kST SP   ( I )   (3) wor kST SP   ( I )   ≤   wor T SP   ( I 1 ) + wor T SP   ( I 2 )   (4) opt kST SP   ( I )   ≤  {   opt T SP   ( I 1 ) + wor T SP   ( I 2 ) wor T SP   ( I 1 ) + opt T SP   ( I 2 )  }  ≤   wor kT 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   I 1 , I 2 , we denote by opt 2 ST SP   | T   ′ 1   ( resp.   opt 2 ST SP   | T   ′ 2   ) the best solution value for the   k STSP 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   I 1 , I 2   are denoted by   T   1 , ∗ , T   2 , ∗ , respectively. Moreover, for a given   α   ∈ ]0 ,   1[, we denote by   I α   the TSP instance on   K n +1   with distance function   d α   = 2   ( αd 1   + (1   −   α )( d 2 ) − 1 ) , where ( d 2 ) − 1   is defined as ( d 2 ) − 1 ( a, b ) =   d 2 ( 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   d 1 , d 2   (symetric or not). 1. For   a   ∈ { 1 ,   2 } , the optimal value   opt 2 ST SP   | T   ∗ ,a   ( I )   verifies:  inf I ∈ I 2 ST SP   opt 2 ST SP   | T   a, ∗   ( I ) / opt 2 ST SP   ( I ) = + ∞  2. For   α   = 1 / 2 , the quantities   d 1 ( T   ∗  α   ) +   d 2 ( T   ∗  α   )   and   opt 2 ST SP   ( I )   verify:  inf  I ∈ I 2 ST SP  ( d 1 ( T   ∗  α   ) +   d 2 ( T   ∗  α   ) )   / opt 2 ST SP   ( I )   =   + ∞
Proof.   3-1, the asymetric case. Consider the instance family ( I n ) n ≥ 3 ,   I n   = ( d 1  n , d 2  n ), defined as (indexes are taken modulo   n   + 1):  d 1  n ( u, v ) =  {   1   if   v   =   u   + 1 1 +   ε   otherwise   d 2  n ( u, v ) =  {   1 if   v   =   u   + 1  n   otherwise The optimal values for TSP on   I 1  n   and   I 2  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   P n   =   { 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   6   = 1   ∈   [ n ], 1   < 1   u   ∀ u   6   = 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   d 2  n ( T   2  n   ) = 1 +   n 2 .  –   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   d 2  n ( T   2  n   ) = 1 +   n 2 .  –   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,   d 2  n ( T   2  n   )   ≥   1 / 2( n ( n   + 1) + 2 n ) =   n ( n   + 3) / 2. Moreover, the following solution is optimal for   I n , 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   I n   for even value of   n ):  P   1  n   = ( n, n   −   2 , . . . , n   −   2 i, . . . , n   −   2 ⌊ ( n   −   1) / 2 ⌋ )  P   2  n   = ( n   −   1 , n   −   3 , . . . , n   −   (2 i   + 1) , . . . , n   −   (2 ⌊ ( n   −   2) / 2 ⌋   + 1))  T n   =   { (0 , n   −   1) } ∪ { ( n   −   (2 i   + 1) , n   −   2 i, n   −   (2 i   + 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 opt T SP   ( I 1  n ) + wor T SP   ( I 2  n ) = ( n   + 1) 2 , the ratio opt 2 ST SP   | T   ′ 1  n   ( I n ) / (opt T SP   ( I 1  n ) + wor T SP   ( I 2  n )) is asymptotically 1 / 2): opt 2 ST SP   | T   ′ 1  n   ( I n )   ≥   ( n   + 1) +   n ( n   + 3) / 2 opt 2 ST SP   ( I n )   ≤   ( n   + 1)(2 +   ε )  }  ⇒   opt 2 ST SP   | T   ′ 1  n   ( I n )  opt 2 ST SP   ( I n )   −→  n → + ∞   + ∞  3-1, the symetric case. Consider ( J n ) n ≥ 6 ,   J n   = ( d 1  n , d 2  n ), defined as (see fig- ure 2 for an illustration):  d 1  n ( u, v ) =  {   1   if   v   =   u   ±   1 1 +   ε   otherwise   d 2  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   J 1  n , J 2  n , of value   n   + 1 and 2 n , respectively. Similary to the asy- metric case, we show that, for items   u   = 2 , . . . , n −   1 such that 2 u / ∈ { 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) sequence 1 :  { u   + 1 , n   −   u, u, n   + 1   −   u, u   −   1 }  Hence, opt 2 ST SP   | T   ′ 1  n   ( J n )   ≥   ( n +1)+(( n − 4)(3+ n )+5 ∗ 4) / 4   ≥   n 2 / 4, whereas the following solution is of value 3 n   + 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 ( H n ) n ≥ 3 :  condition   d 1  n ( u, v )   d 2  n ( u, v )   d 1  n ( u, v ) +   d 2  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   2 n   + 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   d 1  n ( T   1 , ∗  n   ) =   n   + 1 and   d 2  n ( T   2 , ∗  n   ) = ( n   −   3) + 5( n   + 1) (for   n   even) or   d 2  n ( T   2 , ∗  n   ) = ( n   −   4) + 6( n   + 1) (for   n   odd); hence, the following solution of 2STSP is optimal, of value in   { 7 n   + 2 ,   8 n   + 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   d n, 1 / 2 ( T   ∗  n, 1 / 2 ) is arbitrarly large   vs.   opt 2 ST SP   ; however, for more relevancy, we built ( H n ) ( 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   k STSP, 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  d 1  n ,   d 2  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   I n   for   n   even.  0  1   2   n/ 2  n   n   −   1   n/ 2 + 1  d 1  n   (plain lines),   d 2  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   J n   for   n   even.  of   k STSP. 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 , ST sd / C max )   ≡   (1/ k -stack, p , ST sd /TST) and (1/ k - stack, p , SC sd / 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).