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

Cordeau, J. F.; Dell'Amico, Mauro; Iori, Manuel

doi:10.1016/j.cor.2009.08.003

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(2010), pp. 970-980.

Data di pubblicazione:	2010
Titolo:	Branch-and-Cut for the Pickup and Delivery Traveling Salesman Problem with FIFO Loading
Autore/i:	J. F., Cordeau; Dell'Amico, Mauro; Iori, Manuel
Autore/i UNIMORE:	J. F. Cordeau DELL'AMICO, Mauro IORI, MANUEL mostra contributor esterni nascondi contributor esterni
Digital Object Identifier (DOI):	http://dx.doi.org/10.1016/j.cor.2009.08.003
Rivista:	COMPUTERS & OPERATIONS RESEARCH
Volume:	37
Pagina iniziale:	970
Pagina finale:	980
Codice identificativo ISI:	WOS:000272652900017
Codice identificativo Scopus:	2-s2.0-70449108144
Citazione:	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(2010), pp. 970-980.
Tipologia	Articolo su rivista

File in questo prodotto:

File	Descrizione	Tipologia
CDI-BCut-FIFO.pdf	Articolo principale	Versione dell'editore (versione pubblicata)	Administrator Richiedi una copia
TSPPDF-BC.pdf	Versione post-print	Post-print dell'autore (bozza post referaggio)	Administrator Richiedi una copia

Utilizza questo identificativo per citare o creare un link a questo documento:
http://hdl.handle.net/11380/618394

Citazioni

I documenti presenti in Iris Unimore sono rilasciati con licenza Creative Commons Attribuzione - Non commerciale - Non opere derivate 3.0 Italia, salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris