Abstract

Khaoula DHAOUI

Abstract : The Vehicle Routing Problem (VRP) is a classical problem for which several exact and approximation methods have been proposed. In real life applications, such as in Hazardous Material transportation, transported items may be incompatible. This complication has not yet been considered in the literature. This paper introduces this extension called the Vehicle Routing Problem with Conflicts (VRPC) which is NP-hard since it generalizes the VRP, already NP-hard. This study presents a mathematical model, heuristics and a metaheuristic for this new problem. Three among the developed heuristics are adaptations of existing methods for the VRP. The last one is especially designed for the VRPC. The metaheuristic is an Iterated Local Search (ILS) which uses as initial solution the one obtained by the best proposed heuristic.

Keywords : Routing; hazardous materials; conflicts; ILS

Year : 2011
Issue : 1
Volume : 4