A New Tabu Search Heuristic for the Site-Dependent Vehicle Routing Problem

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.