Data di Pubblicazione:
2021
Citazione:
Additive Bounds for the Double Traveling Salesman Problem with Multiple Stacks / L. Diedolo, G. Righini (AIRO SPRINGER SERIES). - In: Optimization and Decision Science / [a cura di] R. Cerulli, M. Dell'Amico, F. Guerriero, D. Pacciarelli, A. Sforza. - [s.l] : Springer Nature, 2021. - ISBN 978-3-030-86840-6. - pp. 203-212 (( convegno ODS tenutosi a Virtual nel 2020 [10.1007/978-3-030-86841-3_17].
Abstract:
The Double TSP with Multiple Stacks is a challenging combinatorial optimization problem, asking for two Hamiltonian cycles on two weighted graphs, a pick-up graph and a delivery graph; the two cycles originate from two given depots, one for each graph, and they visit the vertices in an order that allows a single vehicle to collect the pick-up items in a given number of stacks and to deliver them according to a Last-In-First-Out policy for each stack. We investigate the use of the additive bounding procedure, starting from the Held-Karp lower bound, within a branch-and-bound algorithm. Computational results show that this method often provides tighter bounds than the Double TSP relaxation.
Tipologia IRIS:
03 - Contributo in volume
Keywords:
Traveling Salesman Problem; Held-Karp lower bound; Additive bounding
Elenco autori:
L. Diedolo, G. Righini
Link alla scheda completa:
Titolo del libro:
Optimization and Decision Science