In the Traveling Salesman Problem with Pickup and Delivery (TSPPD) a single vehiclemust serve a set of customer requests, each defined by an origin location where a load must be picked up, and a destination location where the load must be delivered. The problem consists of determining a shortest Hamiltonian cycle through all locations while ensuring that the pickup of each request is performed before the corresponding delivery. This article addresses a variant of the TSPPD in which pickups anddeliveries must be performed according to a Last-In First-Out (LIFO) policy. We propose three mathematical formulations for this problem and several families of valid inequalities which are used within a branch-and-cut algorithm. Computational results performed on test instances from the literature show that most instances with up to 17 requests can be solved in less than 10 min, whereas the largest instance solved contains 25 requests.

A Branch-and-Cut Algorithm for the Pickup and Delivery Traveling Salesman Problem with LIFO Loading / J. F., Cordeau; Iori, Manuel; G., Laporte; J. J., Salazar Gonzalez. - In: NETWORKS. - ISSN 0028-3045. - STAMPA. - 55:1(2010), pp. 46-59. [10.1002/net.20312]

A Branch-and-Cut Algorithm for the Pickup and Delivery Traveling Salesman Problem with LIFO Loading

IORI, MANUEL;
2010

Abstract

In the Traveling Salesman Problem with Pickup and Delivery (TSPPD) a single vehiclemust serve a set of customer requests, each defined by an origin location where a load must be picked up, and a destination location where the load must be delivered. The problem consists of determining a shortest Hamiltonian cycle through all locations while ensuring that the pickup of each request is performed before the corresponding delivery. This article addresses a variant of the TSPPD in which pickups anddeliveries must be performed according to a Last-In First-Out (LIFO) policy. We propose three mathematical formulations for this problem and several families of valid inequalities which are used within a branch-and-cut algorithm. Computational results performed on test instances from the literature show that most instances with up to 17 requests can be solved in less than 10 min, whereas the largest instance solved contains 25 requests.
2010
55
1
46
59
A Branch-and-Cut Algorithm for the Pickup and Delivery Traveling Salesman Problem with LIFO Loading / J. F., Cordeau; Iori, Manuel; G., Laporte; J. J., Salazar Gonzalez. - In: NETWORKS. - ISSN 0028-3045. - STAMPA. - 55:1(2010), pp. 46-59. [10.1002/net.20312]
J. F., Cordeau; Iori, Manuel; G., Laporte; J. J., Salazar Gonzalez
File in questo prodotto:
Non ci sono file associati a questo prodotto.
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/585507
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 75
  • ???jsp.display-item.citation.isi??? 66
social impact