Solving vehicle routing problems using constraint programming and metaheuristics

Solving vehicle routing problems using constraint programming and metaheuristics

0.00 Avg rating0 Votes
Article ID: iaor20023246
Country: Netherlands
Volume: 6
Issue: 4
Start Page Number: 501
End Page Number: 523
Publication Date: Sep 2000
Journal: Journal of Heuristics
Authors: , , , ,
Keywords: tabu search, constraint programming
Abstract:

Constraint Programming typically uses the technique of depth-first branch and bound as the method of solving optimization problems. Although this method can give the optimal solution, for large problems, the time needed to find the optimal can be prohibitive. This paper introduces a method for using local search techniques within a Constraint Programming framework, and applies this technique to vehicle routing problems. We introduce a Constraint Programming model for vehicle routing, and a system for integrating Constraint Programming and local search techniques. We then describe how the method can be accelerated by handling core constraints using fast local checks, while other more complex constraints are left to the constraint propagation system. We have coupled our local search method with a meta-heuristic to avoid the search being trapped in local minima. Several meta-heuristics are investigated ranging from a simple Tabu Search method to Guided Local Search. An empirical study over benchmark problems shows the relative merits of these techniques. Investigations indicate that the specific long-term memory technique used by Guided Local Search can be used as a diversification method for Tabu Search, resulting in significant benefit. Several new best solutions on the Solomon problems are found in relatively few iterations of our algorithm.

Reviews

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