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.
Heuristics for the traveling salesman problem with pickup and delivery / Gendreau M.; Laporte G.; Vigo D.. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - STAMPA. - 26:7(1999), pp. 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
