Solving Multi-Criteria Shortest Path by Optimization with Morphological Filters

Authors

  • Amar Kateb Hachemi Amar Department of Computer Science, Faculty of Mathematics and Computer Science, University of Science and Technology of Oran - Mohamed Boudiaf, Algeria
  • Mohammed Amin Tahraoui LIA Laboratory, Department of Informatics, Faculty of Exact Sciences and Informatics, University of Hassiba Benbouali of Chlef, Algeria
  • Abderrahim Belmadani Department of Computer Science, Faculty of Mathematics and Computer Science, University of Science and Technology of Oran - Mohamed Boudiaf, Algeria
Volume: 15 | Issue: 1 | Pages: 19856-19864 | February 2025 | https://doi.org/10.48084/etasr.9468

Abstract

The challenge of determining the shortest path within a multimodal transportation network involves identifying the most efficient travel route while considering various interconnected modes of transportation, such as roads, railways, and public transit. This problem becomes increasingly complex when numerous criteria and modes are involved, complicating the decision-making process. This study proposes a novel approach to computing the shortest path in multimodal networks, focusing on four modes of transportation: metro, trams, buses, and taxis. The optimization criteria include distance, travel time, and monetary cost. The proposed method utilizes a new metaheuristic called Optimization by Morphological Filters (OMF), inspired by image processing techniques. This approach was compared with the Genetic Algorithms (GA) and the Non-Dominated Sorting Genetic Algorithm II (NSGA-II). Experiments were carried out using graph models of multimodal transport networks that closely resemble real-world scenarios varying in size. Furthermore, the proposed method was evaluated using a real network from the city of Lyon, France. The results demonstrate that the OMF approach performs well in terms of convergence to optimal solutions and computation time.

Keywords:

multicriteria optimization, shortest path, multimodal transport networks, optimization by morphological filters, graph modeling

Downloads

Download data is not yet available.

References

L. Alessandretti, L. G. Natera Orozco, M. Saberi, M. Szell, and F. Battiston, "Multimodal urban mobility and multilayer transport networks," Environment and Planning B: Urban Analytics and City Science, vol. 50, no. 8, pp. 2038–2070, Oct. 2023.

Y. Zhou, C. Cao, and Z. Feng, "Optimization of Multimodal Discrete Network Design Problems Based on Super Networks," Applied Sciences, vol. 11, no. 21, Jan. 2021, Art. no. 10143.

P. Modesti and A. Sciomachen, "A utility measure for finding multiobjective shortest paths in urban multimodal transportation networks1," European Journal of Operational Research, vol. 111, no. 3, pp. 495–508, Dec. 1998.

T. Y. Ma, "An A* Label-setting Algorithm for Multimodal Resource Constrained Shortest Path Problem," Procedia - Social and Behavioral Sciences, vol. 111, pp. 330–339, Feb. 2014.

Y. Luo, Y. Zhang, J. Huang, and H. Yang, "Multi-route planning of multimodal transportation for oversize and heavyweight cargo based on reconstruction," Computers & Operations Research, vol. 128, Apr. 2021, Art. no. 105172.

M. Bielli, A. Boulmakoul, and H. Mouncif, "Object modeling and path computation for multimodal travel systems," European Journal of Operational Research, vol. 175, no. 3, pp. 1705–1730, Dec. 2006.

M. G. Battista, M. Lucertini, and B. Simeone, "Path Composition and Multiple Choice in a Bimodal Transportation Network. Volume 2: Modelling Transport Systems," presented at the World Transport Research. Proceedings of the 7th World Conference on Transport ResearchWorld Conference on Transport Research Society, 1996.

A. Idri, M. Oukarfi, A. Boulmakoul, K. Zeitouni, and A. Masri, "A new time-dependent shortest path algorithm for multimodal transportation network," Procedia Computer Science, vol. 109, pp. 692–697, Jan. 2017.

O. Dib, L. Moalic, M.-A. Manier, and A. Caminada, "An advanced GA–VNS combination for multicriteria route planning in public transit networks," Expert Systems with Applications, vol. 72, pp. 67–82, Apr. 2017.

O. Dib, M. Dib, and A. Caminada, "Computing Multicriteria Shortest Paths in Stochastic Multimodal Networks Using a Memetic Algorithm," International Journal on Artificial Intelligence Tools, vol. 27, no. 07, Nov. 2018, Art. no. 1860012.

H. Ayed, C. Galvez-Fernandez, Z. Habbas, and D. Khadraoui, "Solving time-dependent multimodal transport problems using a transfer graph model," Computers & Industrial Engineering, vol. 61, no. 2, pp. 391–401, Sep. 2011.

R. Wang, K. Yang, L. Yang, and Z. Gao, "Modeling and optimization of a road–rail intermodal transport system under uncertain information," Engineering Applications of Artificial Intelligence, vol. 72, pp. 423–436, Jun. 2018.

A. Abbassi, A. E. hilali Alaoui, and J. Boukachour, "Robust optimisation of the intermodal freight transport problem: Modeling and solving with an efficient hybrid approach," Journal of Computational Science, vol. 30, pp. 127–142, Jan. 2019.

H. C. Yu and F. Lu, "A multi-modal route planning approach with an improved genetic algorithm," in Advances in Geo-Spatial Information Science, CRC Press, 2012.

H. Jafarzadeh, N. Moradinasab, and M. Elyasi, "An Enhanced Genetic Algorithm for the Generalized Traveling Salesman Problem," Engineering, Technology & Applied Science Research, vol. 7, no. 6, pp. 2260–2265, Dec. 2017.

H. Faroqi, "Multiobjective route finding in a multimode transportation network by NSGA-II," Journal of Engineering and Applied Science, vol. 71, no. 1, Mar. 2024, Art. no. 81.

C. N. E. H. Khelifa and A. Belmadani, "New Approach for Continuous and Discrete Optimization: Optimization by Morphological Filters," in Heuristics for Optimization and Learning, F. Yalaoui, L. Amodeo, and E. G. Talbi, Eds. Springer International Publishing, 2021, pp. 425–440.

S. Zaoui and A. Belmadani, "Solving Engineering Optimization Problems Without Penalty," International Journal of Computational Methods, vol. 18, no. 04, May 2021, Art. no. 2150007.

S. Zaoui and A. Belmadani, "Solution of combined economic and emission dispatch problems of power systems without penalty," Applied Artificial Intelligence, vol. 36, no. 1, Dec. 2022, Art. no. 1976092.

S. A. Arhin, A. Gatiba, M. Anderson, B. Manandhar, and M. Ribbisso, "Acceptable Wait Time Models at Transit Bus Stops," Engineering, Technology & Applied Science Research, vol. 9, no. 4, pp. 4574–4580, Aug. 2019.

"TCL - Transports en commun à Lyon : métro, tramway, funiculaire et bus." https://www.tcl.fr/.

"Plans du réseau | TCL." https://www.tcl.fr/plans-du-reseau.

Downloads

How to Cite

[1]
Kateb Hachemi Amar, A., Tahraoui, M.A. and Belmadani, A. 2025. Solving Multi-Criteria Shortest Path by Optimization with Morphological Filters. Engineering, Technology & Applied Science Research. 15, 1 (Feb. 2025), 19856–19864. DOI:https://doi.org/10.48084/etasr.9468.

Metrics

Abstract Views: 40
PDF Downloads: 32

Metrics Information

Most read articles by the same author(s)