A tabu search algorithm for the single vehicle routing allocation problem

A tabu search algorithm for the single vehicle routing allocation problem

0.00 Avg rating0 Votes
Article ID: iaor20081289
Country: United Kingdom
Volume: 58
Issue: 4
Start Page Number: 467
End Page Number: 480
Publication Date: Apr 2007
Journal: Journal of the Operational Research Society
Authors: , ,
Keywords: heuristics: tabu search
Abstract:

In the single vehicle routing allocation problem (SVRAP) 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 by the vehicle can either be allocated to a customer on the vehicle route, or they can be isolated. The objective is to minimize a weighted sum of routing, allocation and isolation costs. One special case of the general SVRAP 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 SVRAP. 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.

Reviews

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