Optimization by Morphological Filters Applied to Multi Criteria Shortest Path Problems

Abstract The Multi-Criteria Shortest Path (MCSP) problem gets more challenging to solve due to numerous contradictory criteria and multimodality in transport networks which complicates the problem inducing difficulties in decision making. Several studies in the literature show that metaheuristics are often used to solve this sort of problem. In this paper, we propose a new approach based on the Optimization by Morphological Filters (OMF) algorithm applied for the first time to solve the multi-criteria shortest path problem in a multimodal transport network. To ameliorate and adapt the algorithm to the MCSP problem, two neighborhood calculation systems are proposed: Neighborhood in depth and Neighborhood in width. To test the approach, we propose a model of the multimodal transport road network of a real geographical area, by using a multivalued graph with three means of transportation. The comparison demonstrates that our technique outperforms several other proposed techniques including Non-dominated Sorting Genetic Algorithm (NSGA-II), with a six-fold improvement in processor execution time.