Local Search in Constraint Programming: Experiments with Tabu Search on the Vehicle Routing Problem

Constraint Programming has proved to be useful for solving many combinatorial problems. In particular, it provides a language allowing to easily model complex problems, and to describe a way to solve them. However, it has seldom been used to solve Vehicle Routing Problems (VRP). Indeed, traditional Constraint Programming systems explore the search space in a depth-first fashion. On the other hand, local search methods have proved to be efficient for solving VRP. In this article, a constraint programming model for the VRP is described, along with a method allowing to perform local non-monotonic search within a Constraint Programming framework. This framework has been used to implement Tabu Search meta-heuristics. The implementation choices are described, as well as the results of experiments performed on problems from the literature.