We consider the Traveling Salesman Problem with Pickup and Delivery (TSPPD), an extension of the well-known Traveling Salesman Problem where each customer to be served is associated with two quantities of goods to be collected and delivered, respectively. A vehicle with given capacity starts at a depot and must visit each customer exactly once. The vehicle capacity must not be exceeded and the total length of the tour must be minimized. We describe new heuristics for TSPPD, the first based on the exact solution of a special case and the second based on tabu search, and we analyze their average performance through extensive computational experiments.

Gendreau M., Laporte G., Vigo D. (1999). Heuristics for the traveling salesman problem with pickup and delivery. COMPUTERS & OPERATIONS RESEARCH, 26(7), 699-714 [10.1016/S0305-0548(98)00085-9].

Heuristics for the traveling salesman problem with pickup and delivery

Vigo D.
Membro del Collaboration Group
1999

Abstract

We consider the Traveling Salesman Problem with Pickup and Delivery (TSPPD), an extension of the well-known Traveling Salesman Problem where each customer to be served is associated with two quantities of goods to be collected and delivered, respectively. A vehicle with given capacity starts at a depot and must visit each customer exactly once. The vehicle capacity must not be exceeded and the total length of the tour must be minimized. We describe new heuristics for TSPPD, the first based on the exact solution of a special case and the second based on tabu search, and we analyze their average performance through extensive computational experiments.
1999
Gendreau M., Laporte G., Vigo D. (1999). Heuristics for the traveling salesman problem with pickup and delivery. COMPUTERS & OPERATIONS RESEARCH, 26(7), 699-714 [10.1016/S0305-0548(98)00085-9].
Gendreau M.; Laporte G.; Vigo D.
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/954393
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 120
  • ???jsp.display-item.citation.isi??? ND
social impact