A Tabu Search Algorithm for the Single Vehicle Routing Allocation Problem (with L. Vogt and C.A. Poojari) Journal of the Operational Research Society, vol.58, 2007, pp467-480
In the single vehicle routing allocation problem we have a single vehicle, together with a set of customers, and the problem is one of deciding a route for the vehicle (starting and ending at given locations) such that it visits some of the customers. Customers not visited can either be allocated to a customer on the vehicle route, or can be isolated. The objective is to minimise a weighted sum of routing, allocation and isolation costs.
One special case of the general single vehicle routing allocation problem is the median cycle problem, also known as the ring star problem, where no isolated vertices are allowed. Other special cases include the covering tour problem, the covering salesman problem and the shortest covering path problem.
In this paper we present a tabu search algorithm for the single vehicle routing allocation problem. Our tabu search algorithm includes aspiration, path relinking and frequency based diversification. Computational results are presented for test problems used previously in the literature and our algorithm is compared with the results obtained by other researchers. We also report results for much larger problems than have been considered by others.
Keywords: tabu search; single vehicle routing allocation problem; median cycle problem; ring star problem; covering tour problem; covering salesman problem; shortest covering path problem