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.