A Voronoi tabu search algorithm for the capacitated vehicle routing problem

A Voronoi tabu search algorithm for the capacitated vehicle routing problem

0.00 Avg rating0 Votes
Article ID: iaor20084447
Country: South Korea
Volume: 33
Issue: 4
Start Page Number: 469
End Page Number: 479
Publication Date: Dec 2007
Journal: Journal of the Korean Institute of Industrial Engineers
Authors: , , ,
Keywords: heuristics: tabu search
Abstract:

This paper focuses on the capacitated vehicle routing problem that determines the routes of vehicles in such a way that each customer must be visited exactly once by one vehicle starting and terminating at the depot while the vehicle capacity and the travel time constraints must be satisfied. The objective is to minimize the total traveling cost. Due to the complexity of the problem, we suggest a tabu search algorithm that combines the features of the existing search heuristics. In particular, our algorithm incorporates the neighborhood reduction method using the proximity information of the Voronoi diagram corresponding to each problem instance. To show the performance of the Voronoi tabu search algorithm suggested in this paper, computational experiments are done on the benchmark problems and the test results are reported.

Reviews

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