A new model and strengthening inequalities for the double TSP with multiple stacks
Michele Barbato  1, *@  , Luís Gouveia  1, *@  , Mathieu Lacroix  2, *@  
1 : DEIO, Faculdade de Ciências, Universidade de Lisboa, CMAFCIO
Campo Grande, Cidade Universitária Bloco C6 - Piso 4, 1749-016, Lisbon -  Portugal
2 : Laboratoire d'Informatique de Paris-Nord  (LIPN)  -  Website
Institut Galilée, Université Sorbonne Paris Cité (USPC), université Paris 13, CNRS : UMR7030
Institut Galilée, Université Paris 13, 99 avenue Jean-Baptiste Clément, F-93430, Villetaneuse. -  France
* : Corresponding author

In the double TSP with multiple stacks, a vehicle with several stacks performs a Hamiltonian circuit to pick up some items and stores them in its stacks. It then delivers each item to a corresponding customer by performing a second Hamiltonian circuit. The stacks are subject to a LIFO policy: only the items currently on the top of their stack can be delivered.
Petersen and Madsen (2009) model this problem as an ILP formulation involving arc and precedence variables as well as on binary variables z(r,i) indicating whether item i is in stack r.
This model easily lets one deal with instances in which the stacks have a finite capacity, and it has been used in a branch-and-cut framework by Petersen et al. (2010).
In order to reduce symmetry we also consider a new model obtained by replacing the variables z(r,i) by binary variables s(i,j) which are equal to one when items i and j are in the same stack.
In order to strengthen both formulations we introduce new exponential-size families of inequalities. We discuss the complexity of the associated separation problems and provide several efficient separation algorithms.
Both formulations are embedded in a branch-and-cut framework and compared from an experimental point of view.

Online user: 1 RSS Feed