Abstract
The multi-modal transportation problem is a type of shortest path problem (SPP). Its goal is to find the best path between two points in a network with more than one means of transportation. This network can be modeled using a weighted directed colored graph. Hence, an optimization method can be applied to find a better path between two nodes. There are some digital applications, like the well-known Google Maps, that present solution to this problem. Most of them choose the best path according to one objective function: the minimum travel time. However, this optimization process can consider multiple objective functions if different user’s interests are treated in the model such as the cheapest or the most comfortable path. In this work, we implemented and compared two different approaches of algorithms with multiple objectives. One of them is an exact method based on Dijkstra’s algorithm added by sum weight method, and the other one is a heuristic approach based on the non-dominated sorting genetic algorithm (NSGA-II). The computational results of the two methods were compared. The comparison shows that the heuristic method is promising due to the low execution time—around 20 s—and the quality of the results. This quality was measured by the closeness of the points found by the two methods in the objective domain. The runtime and the quality of the results can indicate that this modeling is suitable to a real-time problem, for instance, the multi-modal transportation problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Upper Saddle River (1993)
Ambrosino, D., Sciomachen, A.: A shortest path algorithm in multimodal networks: a case study with time varying costs. In: Proceedings of International Network Optimization Conference, Pisa (2009)
Belhaiza, S., M’Hallah, R., Ben Brahim, G.: A new hybrid genetic variable neighborhood search heuristic for the vehicle routing problem with multiple time windows. In: IEEE Congress on Evolutionary Computation (CEC) (2017)
Deb, K., Agrawal, S., Pratap, A., et al.: A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In: Schoenauer, M., et al. (eds.) Parallel Problem Solving from Nature PPSN VI. PPSN 2000. Lecture Notes in Computer Science. Springer, Berlin (2000)
Dib, O., Manier, M.A., Caminada, A.: Memetic algorithm for computing shortest paths in multimodal transportation networks. Transp. Res. Procedia 10, 745–755 (2015)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1, 269–271 (1959)
Dotoli, M., Epicoco, N., Falagario, M.: A technique for efficient multimodal transport planning with conflicting objectives under uncertainty. In: IEEE In Control Conference (ECC) (2016)
Kirchler, D.: Efficient routing on multi-modal transportation networks. Ecole Polytechnique X (2013)
Liu, L., Mu, H., Yang, J.: Toward algorithms for multi-modal shortest path problem and their extension in urban transit network. J. Intell. Manuf. 28(3), 767–781 (2017)
Mnif, M., Bouamama, S.: Firework algorithm for multi-objective optimization of a multimodal transportation network problem. Procedia Comput. Sci. 112, 1670–1682 (2017)
Ziliaskopoulos, A., Wardell, W.: An intermodal optimum path algorithm for multimodal networks with dynamic arc travel times and switching delays. Eur. J. Oper. Res. 125(3), 486–502 (2000)
Acknowledgements
The authors would like to thank CNPq (National Council for Scientific and Technological Development) for the financial support received.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Silva, J., Rampazzo, P.B., Yamakami, A. (2019). Urban Mobility in Multi-Modal Networks Using Multi-Objective Algorithms. In: Nazário Coelho, V., Machado Coelho, I., A.Oliveira, T., Ochi, L.S. (eds) Smart and Digital Cities. Urban Computing. Springer, Cham. https://doi.org/10.1007/978-3-030-12255-3_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-12255-3_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-12254-6
Online ISBN: 978-3-030-12255-3
eBook Packages: Computer ScienceComputer Science (R0)