Michele Barbato 
Université Paris 13

Abstract: In the double TSP with multiple stacks, one performs a Hamiltonian circuit to pick up n items, storing them in a vehicle with s stacks of finite capacity q satisfying last-in-first-out constraints, and then delivers every item to a corresponding customer by performing a Hamiltonian circuit.  For this problem we introduce an integer linear programming formulation with arc and precedence variables. We prove that a polytope arising from a relaxation of our formulation inherits all the facets of a polytope describing the Asymmetric TSP. We also explain how the underlying polytope of our formulation relates to a specific set covering polytope. These theoretical results let us obtain strengthening inequalities for our formulation.  Such inequalities are embedded into a branch-and-cut algorithm for the double TSP with two stacks, outperforming the existing exact methods to tackle this version of the problem and solving instances that were previously unsolved.

This is a joint work with Roland Grappe, Mathieu Lacroix et Roberto Wolfler Calvo.

This seminar is supported by National Funding from FCT - Fundação para a Ciência e a Tecnologia, under the project: UID/MAT/04561/2013.