The double traveling salesman problem with multiple stacks is a variant of the pickup and delivery traveling salesman problem in which all pickups must be completed before any delivery. In addition, items can be loaded on multiple stacks in the vehicle and each stack must obey the last-in-rst-out policy. The problem consists in nding the shortest Hamiltonian cycles covering all pickup and delivery locations while ensuring the feasibility of the loading plan. We formulate the problem as two traveling salesman problems linked by infeasible path constraints. We also introduce several strengthenings of these constraints which are used within a branch-and-cut algorithm. Computational results performed on instances from the literature show that the algorithm outperforms existing exact algorithms. Instances with up to 28 requests (58 nodes) have been solved to optimality.

A Branch-and-Cut Algorithm for the Double Traveling Salesman Problem with Multiple Stacks / M. A., Alba Martinez; J. F., Cordeau; Dell'Amico, Mauro; Iori, Manuel. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - STAMPA. - 25:1(2013), pp. 41-55. [10.1287/ijoc.1110.0489]

A Branch-and-Cut Algorithm for the Double Traveling Salesman Problem with Multiple Stacks

DELL'AMICO, Mauro;IORI, MANUEL
2013

Abstract

The double traveling salesman problem with multiple stacks is a variant of the pickup and delivery traveling salesman problem in which all pickups must be completed before any delivery. In addition, items can be loaded on multiple stacks in the vehicle and each stack must obey the last-in-rst-out policy. The problem consists in nding the shortest Hamiltonian cycles covering all pickup and delivery locations while ensuring the feasibility of the loading plan. We formulate the problem as two traveling salesman problems linked by infeasible path constraints. We also introduce several strengthenings of these constraints which are used within a branch-and-cut algorithm. Computational results performed on instances from the literature show that the algorithm outperforms existing exact algorithms. Instances with up to 28 requests (58 nodes) have been solved to optimality.
25
1
41
55
A Branch-and-Cut Algorithm for the Double Traveling Salesman Problem with Multiple Stacks / M. A., Alba Martinez; J. F., Cordeau; Dell'Amico, Mauro; Iori, Manuel. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - STAMPA. - 25:1(2013), pp. 41-55. [10.1287/ijoc.1110.0489]
M. A., Alba Martinez; J. F., Cordeau; Dell'Amico, Mauro; Iori, Manuel
File in questo prodotto:
File Dimensione Formato  
DTSPMS-InformsJOC-Appeared-2013.pdf

non disponibili

Tipologia: Versione dell'editore (versione pubblicata)
Dimensione 375.93 kB
Formato Adobe PDF
375.93 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11380/684360
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 34
  • ???jsp.display-item.citation.isi??? 27
social impact