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.
2010
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

Accesso riservato

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

Open access

Descrizione: Versione post-print
Tipologia: Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione 197.96 kB
Formato Adobe PDF
197.96 kB Adobe PDF Visualizza/Apri
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 25
  • ???jsp.display-item.citation.isi??? 28
social impact