An improved petal heuristic for the vehicle routeing problem

An improved petal heuristic for the vehicle routeing problem

0.00 Avg rating0 Votes
Article ID: iaor1997125
Country: United Kingdom
Volume: 47
Issue: 2
Start Page Number: 329
End Page Number: 336
Publication Date: Feb 1996
Journal: Journal of the Operational Research Society
Authors: , ,
Keywords: heuristics
Abstract:

Solutions produced by the first generation of heuristics for the vehicle routeing problem are often far from optimal. Recent adaptations of local search improvement heuristics, like tabu search, produce much better solutions but require increased computing time. However, there are situations where good solutions must be obtained quickly. The algorithm proposed in this paper yields solutions almost as good as those produced by tabu search adaptations, but at only a small fraction of their computing time. This heuristic can be seen as an improved version of the original petal heuristic. On 14 benchmark test problems, the proposed heuristic yields solutions whose values lie on average within 2.38% of that of the best known solutions.

Reviews

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