An Improved Particle Swarm Optimization Algorithm for the Urban Transit Routing Problem
The Urban Transit Routing Problem (UTRP) is a challenging discrete problem that revolves around designing efficient routes for public transport systems. It falls under the category of NP-hard problems, characterized by its complexity and numerous constraints. Evaluating potential route sets for feas...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-08-01
|
| Series: | Electronics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2079-9292/12/15/3358 |
| _version_ | 1797586869644427264 |
|---|---|
| author | Vasileios Kourepinis Christina Iliopoulou Ioannis X. Tassopoulos Chrysanthi Aroniadi Grigorios N. Beligiannis |
| author_facet | Vasileios Kourepinis Christina Iliopoulou Ioannis X. Tassopoulos Chrysanthi Aroniadi Grigorios N. Beligiannis |
| author_sort | Vasileios Kourepinis |
| collection | DOAJ |
| description | The Urban Transit Routing Problem (UTRP) is a challenging discrete problem that revolves around designing efficient routes for public transport systems. It falls under the category of NP-hard problems, characterized by its complexity and numerous constraints. Evaluating potential route sets for feasibility is a demanding and time-consuming task, often resulting in the rejection of many solutions. Given its difficulty, metaheuristic methods, such as swarm intelligence algorithms, are considered highly suitable for addressing the UTRP. However, the effectiveness of these methods depends heavily on appropriately adapting them to discrete problems, as well as employing suitable initialization procedures and solution-evaluation methods. In this study, a new variant of the particle swarm optimization algorithm is proposed as an efficient solution approach for the UTRP. We present an improved initialization function and improved modification operators, along with a post-optimization routine to further improve solutions. The algorithm’s performance is then compared to the state of the art using Mandl’s widely recognized benchmark, a standard for evaluating UTRP solutions. By comparing the generated solutions to published results from 10 studies on Mandl’s benchmark network, we demonstrate that the developed algorithm outperforms existing techniques, providing superior outcomes. |
| first_indexed | 2024-03-11T00:28:16Z |
| format | Article |
| id | doaj.art-4712aa95f4d448ad96b2e6d889ec6e6a |
| institution | Directory Open Access Journal |
| issn | 2079-9292 |
| language | English |
| last_indexed | 2024-03-11T00:28:16Z |
| publishDate | 2023-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Electronics |
| spelling | doaj.art-4712aa95f4d448ad96b2e6d889ec6e6a2023-11-18T22:49:54ZengMDPI AGElectronics2079-92922023-08-011215335810.3390/electronics12153358An Improved Particle Swarm Optimization Algorithm for the Urban Transit Routing ProblemVasileios Kourepinis0Christina Iliopoulou1Ioannis X. Tassopoulos2Chrysanthi Aroniadi3Grigorios N. Beligiannis4School of Science and Technology, Hellenic Open University, 18 Aristotelous St., 26335 Patras, GreeceSchool of Rural, Surveying and Geoinformatics Engineering, National Technical University of Athens, Zografou, 15780 Athens, GreeceDepartment of Food Science & Technology, Agrinio Campus, University of Patras, G. Seferi 2, 30100 Agrinio, GreeceDepartment of Food Science & Technology, Agrinio Campus, University of Patras, G. Seferi 2, 30100 Agrinio, GreeceDepartment of Food Science & Technology, Agrinio Campus, University of Patras, G. Seferi 2, 30100 Agrinio, GreeceThe Urban Transit Routing Problem (UTRP) is a challenging discrete problem that revolves around designing efficient routes for public transport systems. It falls under the category of NP-hard problems, characterized by its complexity and numerous constraints. Evaluating potential route sets for feasibility is a demanding and time-consuming task, often resulting in the rejection of many solutions. Given its difficulty, metaheuristic methods, such as swarm intelligence algorithms, are considered highly suitable for addressing the UTRP. However, the effectiveness of these methods depends heavily on appropriately adapting them to discrete problems, as well as employing suitable initialization procedures and solution-evaluation methods. In this study, a new variant of the particle swarm optimization algorithm is proposed as an efficient solution approach for the UTRP. We present an improved initialization function and improved modification operators, along with a post-optimization routine to further improve solutions. The algorithm’s performance is then compared to the state of the art using Mandl’s widely recognized benchmark, a standard for evaluating UTRP solutions. By comparing the generated solutions to published results from 10 studies on Mandl’s benchmark network, we demonstrate that the developed algorithm outperforms existing techniques, providing superior outcomes.https://www.mdpi.com/2079-9292/12/15/3358swarm intelligencepopulation-based optimizationtransit network designparticle swarm optimizationUTRP |
| spellingShingle | Vasileios Kourepinis Christina Iliopoulou Ioannis X. Tassopoulos Chrysanthi Aroniadi Grigorios N. Beligiannis An Improved Particle Swarm Optimization Algorithm for the Urban Transit Routing Problem Electronics swarm intelligence population-based optimization transit network design particle swarm optimization UTRP |
| title | An Improved Particle Swarm Optimization Algorithm for the Urban Transit Routing Problem |
| title_full | An Improved Particle Swarm Optimization Algorithm for the Urban Transit Routing Problem |
| title_fullStr | An Improved Particle Swarm Optimization Algorithm for the Urban Transit Routing Problem |
| title_full_unstemmed | An Improved Particle Swarm Optimization Algorithm for the Urban Transit Routing Problem |
| title_short | An Improved Particle Swarm Optimization Algorithm for the Urban Transit Routing Problem |
| title_sort | improved particle swarm optimization algorithm for the urban transit routing problem |
| topic | swarm intelligence population-based optimization transit network design particle swarm optimization UTRP |
| url | https://www.mdpi.com/2079-9292/12/15/3358 |
| work_keys_str_mv | AT vasileioskourepinis animprovedparticleswarmoptimizationalgorithmfortheurbantransitroutingproblem AT christinailiopoulou animprovedparticleswarmoptimizationalgorithmfortheurbantransitroutingproblem AT ioannisxtassopoulos animprovedparticleswarmoptimizationalgorithmfortheurbantransitroutingproblem AT chrysanthiaroniadi animprovedparticleswarmoptimizationalgorithmfortheurbantransitroutingproblem AT grigoriosnbeligiannis animprovedparticleswarmoptimizationalgorithmfortheurbantransitroutingproblem AT vasileioskourepinis improvedparticleswarmoptimizationalgorithmfortheurbantransitroutingproblem AT christinailiopoulou improvedparticleswarmoptimizationalgorithmfortheurbantransitroutingproblem AT ioannisxtassopoulos improvedparticleswarmoptimizationalgorithmfortheurbantransitroutingproblem AT chrysanthiaroniadi improvedparticleswarmoptimizationalgorithmfortheurbantransitroutingproblem AT grigoriosnbeligiannis improvedparticleswarmoptimizationalgorithmfortheurbantransitroutingproblem |