OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Capacitated Vehicle Routing Problem under Deadlines

Dubois, Florent and Renaud-Goud, Paul and Stolf, Patricia Capacitated Vehicle Routing Problem under Deadlines. (2020) In: International Conference on Information and Communication Technologies for Disaster Management (ICT-DM 2019), 18 December 2019 - 20 December 2019 (Paris, France).

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: https://doi.org/10.1109/ICT-DM47966.2019.9033000


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.

Item Type:Conference or Workshop Item (Paper)
HAL Id:hal-02942308
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Laboratory name:
ANR : Agence Nationale de la Recherche (France)
Deposited On:04 Sep 2020 14:45

Repository Staff Only: item control page