Solving the Multi-Objective Shortest Path Problem

International audienceMulti-objective Shortest Path problem consists in finding Pareto-optimal paths between two given nodes in a graph where each edge has several associated costs, while minimizing several objectives. To solve this multi-objective problem, we develop a new exact method called Label Setting algorithm with Dynamic update of Pareto Front (LSDPF), which aims to find all non-dominated solutions of the problem. Different exploration strategies and improvements techniques have been proposed and tested. Numerical experiments on real data sets and on instances of the literature were conducted. Comparison with recent benchmarks algorithms solving Bi-Objective Shortest Path Problem - the bounded Label Setting algorithm by (Raith, 2010) and the pulse algorithm by (Duque et al., 2015) - shows that our method outperforms these benchmarks algorithms. This work is in collaboration with an enterprise who provide a web platform called Géovélo that aims to propose routes for cycling by solving a Bi-Objective Shortest Path Problem that takes into account both distance and insecurity criteria