×

Solving vehicle routing problems using constraint programming and metaheuristics. (English) Zbl 0972.68631

Summary: 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 prograniming 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 signiticant benefit. Several new best solutions on the Solomon problems are found in relatively few iterations of our algorithm.

MSC:

68U99 Computing methodologies and applications
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90B20 Traffic problems in operations research
PDFBibTeX XMLCite
Full Text: DOI