Efficient Constraint Programming Approaches for routing problem : a case study for the VRP
Bourreau Eric  1@  , Philippe Lacomme  2, 3@  , Gondran Matthieu  3@  
1 : Laboratoire dÍnformatique de Robotique et de Microélectronique de Montpellier  (LIRMM)  -  Website
Université de Montpellier : UMR5506, Centre National de la Recherche Scientifique : UMR5506
161 rue Ada - 34095 Montpellier -  France
2 : Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes  (LIMOS)  -  Website
Institut Français de Mécanique Avancée, Université Blaise Pascal - Clermont-Ferrand II, Université d'Auvergne - Clermont-Ferrand I, CNRS : UMR6158
Bât ISIMA Campus des Cézeaux BP 10025 63173 AUBIERE cedex -  France
3 : Laboratoire dÍnformatique, de Modélisation et dÓptimisation des Systèmes  (LIMOS)  -  Website
SIGMA Clermont, Université Clermont Auvergne : UMR6158, Centre National de la Recherche Scientifique : UMR6158
Bât ISIMA / Campus des Cézeaux BP 10025 / 63173 Aubière Cedex -  France

Numerous routing or scheduling problems encompass a lot of constraints including due date, time windows, precedence constraints or disjunctive constraints. Exact resolution based on linear formulation or heuristic based approaches should expect difficulties in finding a simple feasible solution. Strongly constraints optimization problems

 

To face this challenge, some approaches based on constraint programming are of great interest taking advantages of the great number of constraints to satisfy and providing one solution in short computation first and capable of investagating new best solution in the neighborhood of one initial solution. In numerous problems conversions of well-know mixed integer programming (MILP) formulation to CP, lead to poor CP performances. Well-known custom-made CP formulation are required to obtain CP formulation of interest. The generality of the CP approach and its efficiency is demonstrated to a VRP where the MILP formulation conversion lead to a 150s resolution time and the well-known custom-made CP formulation provide a resolution in 0.8s. The generic appaoch for solving combinatorial otpimization problem with a CP paradigm is based on global constraints, enumeration technics, propagating technics ... to facilitate strong reduction of domain and a proper exploration of the search tree. 



  • Poster
Online user: 2 RSS Feed