A metaheuristic for the min–max windy rural postman problem with K vehicles

A metaheuristic for the min–max windy rural postman problem with K vehicles

0.00 Avg rating0 Votes
Article ID: iaor20104660
Volume: 7
Issue: 3
Start Page Number: 269
End Page Number: 287
Publication Date: Jul 2010
Journal: Computational Management Science
Authors: , ,
Keywords: vehicle routing & scheduling
Abstract:

In this paper we deal with the min–max version of the windy rural postman problem with K vehicles. For this problem, in which the objective is to minimize the length of the longest tour in order to find a set of balanced tours for the vehicles, we present here a metaheuristic that produces very good feasible solutions in reasonable computing times. It is based on the combination of a multi-start procedure with an Iterated Local Search. Extensive computational results on a large set of instances with up to 50 vertices, 184 edges and 5 vehicles are presented. The results are very good, the average gaps with respect to a known lower bound are less than 0.40% for instances with 2 or 3 vehicles and up to 1.60% when 4 or 5 vehicles are considered.

Reviews

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