Top

Published in:

2024 | OriginalPaper | Chapter

13. Comparing Meta-Heuristic Algorithms for Transit Network Design

Authors : Obiora A. Nnene, Mark H. P. Zuidgeest, Johan W. Joubert

Published in: Dynamics of Transportation Ecosystem, Modeling, and Control

Publisher: Springer Nature Singapore

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This work presents a comparative study of the performance of different meta-heuristic algorithms used within a simulation-based optimisation model that is used to design public transit networks. Simulation-based optimisation focuses on solving decision-based problems by integrating optimisation and simulation. The model combines multi-objective meta-heuristic optimisation algorithm with an activity-based travel simulation to design public transport networks. The simulation evaluates different network solutions, while the meta-heuristic framework identifies optimal ones. The model is robust, thus allowing for integrating different meta-heuristic algorithms, thereby making it feasible to compare the performance of multiple algorithms relative to the network design problem. Four different algorithms, the non-dominated sorting algorithm-II (NSGA-II), strength Pareto evolutionary algorithm (SPEA2), non-dominated sorting algorithm-III (NSGA-III) and the indicator-based evolutionary algorithm (IBEA), are then compared against each other within the simulation-based network design framework using four multi-objective quality indicators including hypervolume, generational distance and maximum Pareto front error. The obtained results show that NSGA-II yields better results than the other algorithms.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Revolutionizing Transportation: The Future Impact of Green Energy

next chapter Assessment and Mapping of Traffic Noise Levels in Coal Capital of India, Dhanbad: Implications for Noise Pollution Management

Abd G, M. A, M. ES. A (2014) Comparative study of meta-heuristic algorithms for solving quadratic assignment problem. Int J Adv Comput Sci Appl 5(1):1–6

Aktel A, Betul Y, Özcan T, Yenisey M, Engin S (2016) The comparison of the metaheuristic algorithms performances on The comparison of the metaheuristic algorithms performances on airport gate assignment problem airport gate assignment problem. Transp Res Procedia [Internet] 22(2016):469–78. Available from: https://doi.org/10.1016/j.trpro.2017.03.061

Amaran S, Sahinidis NV, Sharda B, Bury SJ (2016) Simulation optimization: a review of algorithms and applications. Ann Oper Res 240(1):351–380MathSciNetCrossRef

Arıcı F, Kaya E (2019) Comparison of meta-heuristic algorithms on benchmark functions. Acad Perspect Procedia. 2(3):508–517CrossRef

Arisha A, Abo-Hamad W (2010) Optimisation methods in supply chain applications: a review. Irish J Manag 95–124

Beltran B, Carrese S, Cipriani E, Petrelli M (2009) Transit network design with allocation of green vehicles: a genetic algorithm approach. Transp Res Part C Emerg Technol 17(5):475–483CrossRef

Biswas A, Pal T (2021) A comparison between metaheuristics for solving a capacitated fixed charge transportation problem with multiple objectives. Expert Syst Appl [Internet] 170(December 2020):114491. Available from: https://doi.org/10.1016/j.eswa.2020.114491

Bringmann K, Friedrich T (2013) Approximation quality of the hypervolume indicator. Artif Intell 195:265–290MathSciNetCrossRef

Buba AT, Lee LS (2018) A differential evolution for simultaneous transit network design and frequency setting problem. Expert Syst Appl 106:277–289CrossRef

Cipriani E, Gori S, Petrelli M. Transit network design: A procedure and an application to a large urban area. Transp Res Part C Emerg Technol [Internet]. 2012;20(1):3–14. Available from: https://doi.org/10.1016/j.trc.2010.09.003

Dandl F, Engelhardt R, Hyland M, Tilg G, Bogenberger K, Mahmassani HS (2021) Regulating mobility-on-demand services: Tri-level model and Bayesian optimization solution approach. Transp Res Part C Emerg Technol. 125(December 2020)

Das S, Pandit D (2013) Importance of user perception in evaluating level of service for bus transit for a developing country like India: a review. Transp Rev [Internet] 33(4):402–20. Available from: https://doi.org/10.1080/01441647.2013.789571

Deb K, Agrawal S, Pratap A, Meyarivan T (2000) A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In: Schoenauer M, Deb K, Rudolph G, Yao X, Lutton E, Julian J et al (eds) Parallel problem solving from nature PPSN VI PPSN 2000 lecture notes in computer science, vol 1917. Springer-Verlag, Berlin, pp 849–858

Deb K, Jain H. An Evolutionary many-objective optimization algorithm using reference-point based non-dominated sorting approach, Part I. IeeexploreIeeeOrg. 2013;18(c):1–1

Durán-Micco J, Vansteenwegen P (2022) A survey on the transit network design and frequency setting problem. Public Transp 14:155–190CrossRef

Ezugwu AE, Adeleke OJ, Akinyelu AA, Viriri S (2020) A conceptual comparison of several metaheuristic algorithms on continuous optimisation problems [Internet]. Vol. 32, pp 6207–6251.Neural Computing and Applications. Springer London. Available from: https://doi.org/10.1007/s00521-019-04132-w

Fan L, Mumford CL (2008) A metaheuristic approach to the urban transit routing problem. J Heuristics [Internet] 16(3):353–72. Available from: https://doi.org/10.1007/s10732-008-9089-8

Fonseca CM, Fleming PJ (1993) Genetic algorithms for multiobjective optimization: formulation discussion and generalization. In: Proceedings of the 5th International Conference on Genetic Algorithms [Internet], pp 416–23. San Francisco: Morgan Kaufmann Publishers. Available from: http://dl.acm.org/citation.cfm?id=657757

Gallo M, D’Acierno L, Montella B (2010) A meta-heuristic approach for solving the Urban Network Design Problem. Eur J Oper Res 201(1):144–157CrossRef

Gallo M, Montella B, D’Acierno L (2011) The transit network design problem with elastic demand and internalisation of external costs: an application to rail frequency optimisation. Transp Res Part C Emerg Technol. 19(6):1276–1305CrossRef

Gerami Matin A, Vatani Nezafat R, Golroo A (2017) A comparative study on using meta-heuristic algorithms for road maintenance planning: Insights from field study in a developing country. J Traffic Transp Eng (English Ed [Internet] 4(5):477–86. Available from: https://doi.org/10.1016/j.jtte.2017.06.004

Gosavi A (2015) Simulation-based optimization : parametric optimization techniques and reinforcement learning. Second, p 554. Springer, New York

Hachicha W, Ammeri A, Masmoudi F, Chachoub H (2010) A comprehensive literature classification of simulation optimisation methods. In: international conference on multiple objective programming and goal programming—MOPGP10, p 13

Hadka D (2017) Beginner’s Guide to the MOEA Framework. 2.12. Raleigh-Durham: CreateSpace Independent Publishing Platform (1833), p 214

Hadka D, Reed P (2013) Borg: an auto-adaptive many-objective evolutionary computing framework. Evol Comput 21(2):231–259CrossRef

Huang D, Liu Z, Fu X, Blythe PT (2018) Multimodal transit network design in a hub-and-spoke network framework. Transp A Transp Sci 14(8):706–735

Ibarra-Rojas OJ, Delgado F, Giesen R, Muñoz JC (2015) Planning, operation, and control of bus transport systems: a literature review. Transp Res Part B Methodol 77(3):38–75CrossRef

Jain H, Deb K (2014) An Evolutionary many-objective optimization algorithm using reference-point based nondominated sorting approach, Part II: handling constraints and extending to an adaptive approach. IEEE Trans Evol Comput 18(4):602–622CrossRef

Johar A, Jain SS, Garg PK (2016) Transit network design and scheduling using genetic algorithm—a review. An Int J Optim Control Theor Appl 6(1):9–22

Liu Y, Wei J, Li X, Li M (2019) Generational distance indicator-based evolutionary algorithm with an improved niching method for many-objective optimization problems. IEEE Access. 7:63881–63891CrossRef

Matnei Filho RA, Vergilio SR (2016) A multi-objective test data generation approach for mutation testing of feature models. J Softw Eng Res Dev [Internet] 4(1). Available from: https://doi.org/10.1186/s40411-016-0030-9

Newell GF (1979) Some issues related to the optimal design of bus routes. Transp Sci 13(1):20–35CrossRef

Nikolić M, Teodorović D (2014) A simultaneous transit network design and frequency setting: Computing with bees. Expert Syst Appl 41(16):7200–7209CrossRef

Nnene OA, Zuidgeest MHP, Beukes EA (2017) Application of metaheuristic algorithms to the improvement of the MyCiTi BRT network in Cape Town. J South African Inst Civ Eng. 59(4):56–63CrossRef

Nnene OA, Joubert JW, Zuidgeest MHP (2019) Transit network design with meta-heuristic algorithms and agent based simulation. IFAC-PapersOnLine 52(3):13–18MathSciNetCrossRef

Nnene OA, Joubert JW, Zuidgeest MHP (2019) An agent-based evaluation of transit network design. Proc Comput Sci 1(151):757–762CrossRef

Nnene OA (2020) Simulation-based optimisation of public transport networks [Internet]. Faculty Eng Built Environ 2020. Available from: https://open.uct.ac.za/handle/11427/32308

Nnene OA, Joubert JW, Zuidgeest MHP (2023) A simulation-based optimization approach for designing transit networks. Public Transp

Nnene OA, Zuidgeest MHP, Joubert JW (2023) Optimising transit networks using simulation-based techniques. In: Upadhyay RK, Sharma SK, Kumar V, Valera H, editors. Transportation Systems Technology and Integrated Management [Internet], pp 317–45. Singapore: Springer Nature Singapore. Available from: https://doi.org/10.1007/978-981-99-1517-0_15

Nnene OA, Zuidgeest MHP, Joubert JW (2023) BRT network design for transit cost reduction in Cape Town, South Africa. J Public Transp [Internet]. 25(March):100042. Available from: https://doi.org/10.1016/j.jpubtr.2023.100042

Phan DH, Suzuki J (2013) R2-IBEA: R2 indicator based evolutionary algorithm for multiobjective optimization. 2013 IEEE Congr Evol Comput CEC 2013 (June):1836–45

Rodrigue J, Comtois C, Slack B (2013) The geography of transport systems. Third, p 432. United Kindom: Routledge

Silberholz J, Golden B. Comparison of Metaheuristics. In: Gendreau M, Potvin JY, editors (2010) Handbook of metaheuristics [Internet], pp 625–40. Boston, MA: Springer US. Available from: https://doi.org/10.1007/978-1-4419-1665-5_21

Siriwardene NR, Perera BJC (2006) Selection of genetic algorithm operators for urban drainage model parameter optimisation. Math Comput Model 44(5–6):415–429CrossRef

Song M, Yin M, Chen X (Michael), Zhang L, Li M (2013) A simulation-based approach for sustainable transportation systems evaluation and optimization: theory, systematic framework and applications. Proc Soc Behav Sci 2013;96(Cictp):2274–86

Yen GG, He Z (2014) Performance metric ensemble for multiobjective evolutionary algorithms. IEEE Trans Evol Comput 18(1):131–144CrossRef

Zitzler E, Künzli S (2004) Indicator-Based Selection in Multiobjective Search. In: International conference on parallel problem solving from nature, pp 832–42. Berlin, Heidelberg: Springer

Zitzler E, Laumanns M, Thiele L (2002) SPEA2: improving the strength pareto evolutionary algorithm for multiobjective optimizationations (Single Publication). In: Evolutionary methods for design, optimization and control with applications to industrial problems proceedings of the EUROGEN’2001, 95–100. Athens: CIMNE, Barcelona, Spain

Title: Comparing Meta-Heuristic Algorithms for Transit Network Design
Authors: Obiora A. Nnene
Mark H. P. Zuidgeest
Johan W. Joubert
Publisher: Springer Nature Singapore
Book: Dynamics of Transportation Ecosystem, Modeling, and Control
Print ISBN: 978-981-9704-36-1

Electronic ISBN: 978-981-9704-37-8

Copyright Year: 2024
DOI: https://doi.org/10.1007/978-981-97-0437-8_13

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"