This paper introduces a branch-and-cut algorithm for a variant of the pickup and delivery traveling salesman problem in which pickups and deliveries must obey the first-in-first-out policy. We propose a new mathematical formulation of the problem and several families of valid inequalities which are used within the branch-and-cut algorithm. Computational experiments on instances from the literature show that this algorithm outperforms existing exact algorithms, and that some instances with up to 25 requests (50 nodes) can be solved in reasonable computing time.

Branch-and-Cut for the Pickup and Delivery Traveling Salesman Problem with FIFO Loading / J. F., Cordeau; Dell'Amico, Mauro; Iori, Manuel. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - STAMPA. - 37:5(2010), pp. 970-980. [10.1016/j.cor.2009.08.003]

Branch-and-Cut for the Pickup and Delivery Traveling Salesman Problem with FIFO Loading

DELL'AMICO, Mauro;IORI, MANUEL
2010

Abstract

This paper introduces a branch-and-cut algorithm for a variant of the pickup and delivery traveling salesman problem in which pickups and deliveries must obey the first-in-first-out policy. We propose a new mathematical formulation of the problem and several families of valid inequalities which are used within the branch-and-cut algorithm. Computational experiments on instances from the literature show that this algorithm outperforms existing exact algorithms, and that some instances with up to 25 requests (50 nodes) can be solved in reasonable computing time.
37
5
970
980
Branch-and-Cut for the Pickup and Delivery Traveling Salesman Problem with FIFO Loading / J. F., Cordeau; Dell'Amico, Mauro; Iori, Manuel. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - STAMPA. - 37:5(2010), pp. 970-980. [10.1016/j.cor.2009.08.003]
J. F., Cordeau; Dell'Amico, Mauro; Iori, Manuel
File in questo prodotto:
File Dimensione Formato  
CDI-BCut-FIFO.pdf

non disponibili

Descrizione: Articolo principale
Tipologia: Versione dell'editore (versione pubblicata)
Dimensione 427.14 kB
Formato Adobe PDF
427.14 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
TSPPDF-BC.pdf

non disponibili

Descrizione: Versione post-print
Tipologia: Post-print dell'autore (bozza post referaggio)
Dimensione 197.96 kB
Formato Adobe PDF
197.96 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: https://hdl.handle.net/11380/618394
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 22
  • ???jsp.display-item.citation.isi??? 25
social impact