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 every item by performing another Hamiltonian circuit while satisfying the last-in-first-out policy of its stacks. The consistency requirement ensuring that the pickup and delivery circuits can be performed by the vehicle is the major difficulty of the problem. This requirement corresponds, from a polyhedral standpoint, to a set covering polytope. When the vehicle has two stacks this polytope is obtained from the description of a vertex cover polytope. We use these results to develop a branch-and-cut algorithm with inequalities derived from the inequalities of the vertex cover polytope.
A set covering approach for the double traveling salesman problem with multiple stacks / M. Barbato, R. Grappe, M. Lacroix, R.W. Calvo (LECTURE NOTES IN COMPUTER SCIENCE). - In: Combinatorial Optimization / [a cura di] R. Cerulli, S. Fujishige, A. Ridha Mahjoub. - [s.l] : Springer Verlag, 2016. - ISBN 9783319455860. - pp. 260-272 (( Intervento presentato al 4. convegno International Symposium on Combinatorial Optimization, ISCO tenutosi a Vietri sul Mare nel 2016.
|Titolo:||A set covering approach for the double traveling salesman problem with multiple stacks|
BARBATO, MICHELE (Corresponding)
|Parole Chiave:||Double traveling salesman problem with multiple stacks; Polytope; Set cover; Vertex cover; Odd hole|
|Settore Scientifico Disciplinare:||Settore MAT/09 - Ricerca Operativa|
|Data di pubblicazione:||2016|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1007/978-3-319-45587-7_23|
|Tipologia:||Book Part (author)|
|Appare nelle tipologie:||03 - Contributo in volume|