Solving Multi-Criteria Shortest Path by Optimization with Morphological Filters
Received: 1 November 2024 | Revised: 5 December 2024 | Accepted: 9 December 2024 | Online: 2 February 2025
Corresponding author: Amar Kateb Hachemi Amar
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 modelingDownloads
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
License
Copyright (c) 2024 Amar Kateb Hachemi, Mohammed Amin Tahraoui, Abderrahim Belmadani
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain the copyright and grant the journal the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) after its publication in ETASR with an acknowledgement of its initial publication in this journal.
