A tabu search heuristic for the single vehicle pickup and delivery problem with time windows

A tabu search heuristic for the single vehicle pickup and delivery problem with time windows

0.00 Avg rating0 Votes
Article ID: iaor20022825
Country: Netherlands
Volume: 12
Issue: 5/6
Start Page Number: 497
End Page Number: 508
Publication Date: Oct 2001
Journal: Journal of Intelligent Manufacturing
Authors: , ,
Keywords: tabu search
Abstract:

The single vehicle pickup and delivery problem with time windows is a generalization of the traveling salesman problem. In such a problem, a number of transportation requests have to be satisfied by one vehicle, each request having constraints to respect: a pickup at its origin and a delivery at its destination, and a time window at each location. The capacity of the vehicle has to be respected. The aim is to minimize the total distance traveled by the vehicle. A number of exact and approximate solution methods exists in the literature, but to the author's knowledge none of them make use of metaheuristics, still promising with other vehicle routing problems. In this paper we present tabu search and probabilistic tabu search. Results obtained on classical traveling salesman problems and a class of randomly generated instances indicate that our approach often produces optimal solutions in a relatively short execution time.

Reviews

Required fields are marked *. Your email address will not be published.