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: | |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/j.cor.2009.08.003 |
Rivista: | |
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 |

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