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.
| Subject : | : | Abstracts |
| Topics | : | Pickup and Delivery |
| Topics | : | Routing and Packing |
| Topics | : | TSP Variants |
| PDF version | : |  PDF version |
