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.
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].
Additive Bounds for the Double Traveling Salesman Problem with Multiple Stacks
L. DiedoloPrimo
;G. RighiniUltimo
2021
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.File | Dimensione | Formato | |
---|---|---|---|
DiedoloRighini final version.pdf
accesso riservato
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
101.97 kB
Formato
Adobe PDF
|
101.97 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Diedolo-Righini2021_Chapter_AdditiveBoundsForTheDoubleTrav.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
233.53 kB
Formato
Adobe PDF
|
233.53 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.