The Vehicle Routing Problem with Conflicts

Khaoula Hamdi-Dhaoui (1) , Nacima Labadie (1) , Alice Yalaoui (1)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels

The Vehicle Routing Problem (VRP) is a classical problem for which several exact and approximation methods were proposed. In real life applications, such as in Hazardous Material transportation, transported items may be incompatible. This paper summarizes the first methods developed for this extension called the Vehicle Routing Problem with Conflicts (VRPC). This study presents a mathematical model, heuristics, metaheuristics (an Iterated Local Search (ILS) and a Greedy Randomized Adaptive Search Procedure – Evolutionary Local Search (GRASP-ELS)). A lower bound is also introduced in this article.

Mots clés: Vehicle Routing; conflicts; heuristics; ILS; GRASP-ELS; branch and cut

Domaines: Recherche opérationnelle [math.OC]

Khaoula Hamdi-Dhaoui, Nacima Labadie, Alice Yalaoui. The Vehicle Routing Problem with Conflicts. IFAC Proceedings Volumes, 2011, 44 (1), pp.9799-9804. ⟨10.3182/20110828-6-IT-1002.01565⟩. ⟨hal-02521862⟩