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 by performing a Hamiltonian circuit. We introduce an integer linear programming formulation with arc and precedence variables. We show that the underlying polytope shares some polyhedral properties with the ATSP polytope, which let us characterize large number of facets of our polytope. We convert these theoretical results into a branch-and-cut algorithm for the double TSP with two stacks. Our algorithm outperforms the existing exact methods and solves instances that were previously unsolved.
Polyhedral results and a branch-and-cut algorithm for the double traveling Salesman problem with multiple stacks / M. Barbato, R. Grappe, M. Lacroix, R. Wolfler Calvo. - In: DISCRETE OPTIMIZATION. - ISSN 1572-5286. - 21(2016), pp. 25-41. [10.1016/j.disopt.2016.04.005]
Polyhedral results and a branch-and-cut algorithm for the double traveling Salesman problem with multiple stacks
M. Barbato;
2016
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 by performing a Hamiltonian circuit. We introduce an integer linear programming formulation with arc and precedence variables. We show that the underlying polytope shares some polyhedral properties with the ATSP polytope, which let us characterize large number of facets of our polytope. We convert these theoretical results into a branch-and-cut algorithm for the double TSP with two stacks. Our algorithm outperforms the existing exact methods and solves instances that were previously unsolved.File | Dimensione | Formato | |
---|---|---|---|
dtsp.pdf
accesso aperto
Descrizione: Articolo principale. Accepted paper conforme a quello apparso sulla rivista (dopo proof reading).
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
331.98 kB
Formato
Adobe PDF
|
331.98 kB | Adobe PDF | Visualizza/Apri |
1-s2.0-S1572528616300214-main.pdf
accesso aperto
Tipologia:
Publisher's version/PDF
Dimensione
667.37 kB
Formato
Adobe PDF
|
667.37 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.