Local search in constraint programming: Application to the vehicle routing problem
Abstract
onstraint programming is an appealing technology to use for vehicle routing problems. Traditional linear programming models do not have the exibility or generality required by businesses wishing to model complex side constraints. This paper describes how a constraint programming framework for vehicle routing problems was implemented using ILOG Solver. A method for incorporating local search into a monotonic constraint programming toolkit is then described. Techniques for accelerating the method via filtering processes are also presented.
Computational tests using the constraint programming framework and a greedy search method were performed. Results indicate that moderately sized VRP (100-200 nodes) can be solved to within 10% of the best known solutions in seconds.
Computational tests using the constraint programming framework and a greedy search method were performed. Results indicate that moderately sized VRP (100-200 nodes) can be solved to within 10% of the best known solutions in seconds.
