On the Complexity of the Multiple Stack TSP, kSTSP

DOI10.1007/978-3-642-02017-9_38MaRDI QIDQ3630221zbMATH OpenOpenAlexFDO

Authors Sophie Toulouse, Roberto Wolfler Calvo

Publication date 3 June 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1009.5029

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Abstract: The multiple Stack Travelling Salesman Problem, STSP, deals with the collect and the deliverance of n commodities in two distinct cities. The two cities are represented by means of two edge-valued graphs (G1,d2) and (G2,d2). During the pick-up tour, the commodities are stored into a container whose rows are subject to LIFO constraints. As a generalisation of standard TSP, the problem obviously is NP-hard; nevertheless, one could wonder about what combinatorial structure of STSP does the most impact its complexity: the arrangement of the commodities into the container, or the tours themselves? The answer is not clear. First, given a pair (T1,T2) of pick-up and delivery tours, it is polynomial to decide whether these tours are or not compatible. Second, for a given arrangement of the commodities into the k rows of the container, the optimum pick-up and delivery tours w.r.t. this arrangement can be computed within a time that is polynomial in n, but exponential in k. Finally, we provide instances on which a tour that is optimum for one of three distances d1, d2 or d1+d2 lead to solutions of STSP that are arbitrarily far to the optimum STSP.

Recommendations

• Approximability of the multiple stack TSP
• Differential approximation of the multiple stacks TSP
• Approximation of the double traveling salesman problem with multiple stacks
• The double travelling salesman problem with multiple stacks - formulation and heuristic solution approaches
• An exact method for the double TSP with multiple stacks

Cited in

(12)

• Polyhedral results and a branch-and-cut algorithm for the double traveling salesman problem with multiple stacks
• Efficient algorithms for the double traveling salesman problem with multiple stacks
• Approximation of the double traveling salesman problem with multiple stacks
• Using intermediate infeasible solutions to approach vehicle routing problems with precedence and loading constraints
• A set covering approach for the double traveling salesman problem with multiple stacks
• Approximability of the multiple stack TSP
• Differential approximation of the multiple stacks TSP
• The traveling purchaser problem, with multiple stacks and deliveries: a branch-and-cut approach
• Exact algorithms for the double vehicle routing problem with multiple stacks
• A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks
• A branch-and-bound algorithm for the double travelling salesman problem with two stacks
• Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem

This page was built for publication: On the Complexity of the Multiple Stack TSP, kSTSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3630221)