2005 | OriginalPaper | Chapter
A New Tabu Search Heuristic for the Site-Dependent Vehicle Routing Problem
Authors : I-Ming Chao, Tian-Shy Liou
Published in: The Next Wave in Computing, Optimization, and Decision Technologies
Publisher: Springer US
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The site-dependent vehicle routing problem takes into account some real-life applications of the basic vehicle routing problem when there are compatible dependencies between customers (sites) and vehicle types. Every customer is associated with a set of allowable vehicle types and has to select only one of them. A series of basic vehicle routing problems are solved over the customers that select the same vehicle type. The objective is to minimize the total distance traveled (or the total travel cost incurred) by the fleet and all constraints for the basic vehicle routing problem as well as the site-dependency constraints must be satisfied. In this paper, we present a new heuristic method based on tabu search combined with the deviation of the deterministic annealing method to carry out the intensification and diversification search by varying the values of the deviations within two different ranges respectively. We test the method on a set of 23 benchmark problems taken from literature, and the computational results show that the new method can solve the problem quite effectively.