A parallel time-dependent multimodal shortest path algorithm based on geographical partitioning

摘要

This paper deals with the multi-objective shortest path problem in the context of time-dependent transportation networks. We all know that there is rarely a unique global solution that is efficient when optimizing several objectives simultaneously. But rather, it exists a set of optimums of equivalent solutions known as pareto-optimal front. Thus, the goal of multi-objective strategies is to generate a set of non-dominated solutions as an approximation to this front. In this paper, we focus on the computation of pareto front. We discussed two approaches. The first one is exact Martins's algorithm while second algorithm is based on NSGA-II. In each case, we present various test instances to prove the performances and the limitations of our two approaches.