A Variable Neighbourhood Search Combining Constraint Programming and Lagrangean Relaxation for Solving Routing Problems

Rosa Herrero, Daniel Guimarans, Juan José Ramos and Silvia Padrón

The 2010 Summer Computer Simulation Conference (SCSC 10)
Ottawa, Canada, July 11-14, 2010

---

Summary

This paper presents a methodology based on the Variable Neighbourhood Search metaheuristic, applied to the Capacitated Vehicle Routing Problem. The presented approach uses Constraint Programming and Lagrangean Relaxation methods in order to improve algorithm’s efficiency. The complete problem is decomposed into two separated submodels, to which the mentioned techniques are applied to obtain a complete solution. With this decomposition, the methodology provides a quick initial solution which is rapidly improved by means of metaheuristics’ iterative process. Constraint Programming and Lagrangean Relaxation are also embedded within this structure, in order to ensure constraints satisfaction and to reduce the calculation burden. Remarkable results have been obtained using this methodology, including a new best-known solution for a rarely solved 200-customers test instance and a better alternative solution for another benchmark problem.

---

START Conference Manager (V2.56.8 - Rev. 1182)