Capacitated Vehicle Routing Problem under Deadlines

Florent Dubois (1) , Paul Renaud-Goud (1) , Patricia Stolf (1)

1 IRIT-SEPIA - Système d’exploitation, systèmes répartis, de l’intergiciel à l’architecture

Fast floods are usually not predictable and lead to lot of damages. In the context of a fast flood, the rescue teams need to elaborate the most efficient plan to save people in the impacted area, “as fast as possible”. Based on discussions with firefighters, the problem is formalized as a Capacitated Vehicle Routing Problem under Deadlines. We introduce tour planning which allows to plan vehicle trajectory for several travels through the rescue center to put casualties into safety. We model the “as fast as possible” requirement through two elements: (i) a deadline, i.e. the time before which someone has to get rescued, is associated with every demand, (ii) the objective function to minimize is the Flow-time, i.e. the sum over each victim of the period during which it was not into safety. We created a set of various graphs in order to evaluate our results varying size of the problem, temporal constraint parameter and capacity constraint parameter in order to observe the evolution of the model towards different kinds of problems. We express the problem as a MILP, which provides the optimal solution on reasonable instance size problems thanks to MILP solvers. Since finding the optimal solution in real-time will not be possible with MILP solver, we also propose and compare different heuristics algorithms. The results show that the heuristics results are close to the optimal solution given by the resolution using Linear programming formulation on small instances. The Best Flow-time Insertion algorithm shows better results than the other heuristics developed in this article for every problem size and it is the closest from optimal results for small size problems.

Mots clés: Routing; Flooding; Capacitated; Deadlines

Domaines: Réseaux et télécommunications [cs.NI]; Système d'exploitation [cs.OS]; Architectures Matérielles [cs.AR]; Systèmes embarqués

Florent Dubois, Paul Renaud-Goud, Patricia Stolf. Capacitated Vehicle Routing Problem under Deadlines. International Conference on Information and Communication Technologies for Disaster Management (ICT-DM 2019), Dec 2019, Paris, France. pp.1-8, ⟨10.1109/ICT-DM47966.2019.9033000⟩. ⟨hal-02942308⟩