Submitted Successfully!
To reward your contribution, here is a gift for you: A free trial for our video production service.
Thank you for your contribution! You can also upload a video entry or images related to this topic.
Version Summary Created by Modification Content Size Created at Operation
1
Grigorios N Beligiannis
 -- 993 2023-08-19 18:32:40 |
2 only format change
Alfred Zheng
 Meta information modification 993 2023-08-21 02:55:45 |

Video Upload Options

Do you have a full video?
Send video materials Upload full video

Confirm

Are you sure to Delete?
Yes No
Cite
If you have any further questions, please contact Encyclopedia Editorial Office.
Kourepinis, V.; Iliopoulou, C.; Tassopoulos, I.X.; Aroniadi, C.; Beligiannis, G.N. The Urban Transit Routing Problem. Encyclopedia. Available online: https://encyclopedia.pub/entry/48243 (accessed on 02 May 2024).
Kourepinis V, Iliopoulou C, Tassopoulos IX, Aroniadi C, Beligiannis GN. The Urban Transit Routing Problem. Encyclopedia. Available at: https://encyclopedia.pub/entry/48243. Accessed May 02, 2024.
Kourepinis, Vasileios, Christina Iliopoulou, Ioannis X. Tassopoulos, Chrysanthi Aroniadi, Grigorios N. Beligiannis. "The Urban Transit Routing Problem" Encyclopedia, https://encyclopedia.pub/entry/48243 (accessed May 02, 2024).
Kourepinis, V., Iliopoulou, C., Tassopoulos, I.X., Aroniadi, C., & Beligiannis, G.N. (2023, August 19). The Urban Transit Routing Problem. In Encyclopedia. https://encyclopedia.pub/entry/48243
Kourepinis, Vasileios, et al. "The Urban Transit Routing Problem." Encyclopedia. Web. 19 August, 2023.
The Urban Transit Routing Problem
Edit
This entry is adapted from the peer-reviewed paper 10.3390/electronics12153358

The Urban Transit Routing Problem (UTRP) is a challenging problem in transportation planning that involves designing and optimizing transit route networks for urban areas. The objective is to find the most efficient routes for public transportation vehicles, considering factors such as travel time, passenger demand, transfer connections, vehicle capacities, operating costs, and environmental impacts. 

UTRP metaheuristics Particle Swarm Optimization

1. Introduction

The field of transportation has grown rapidly in recent times, presenting significant challenges for engineers and planners alike. The escalating transportation needs of individuals, both domestically and internationally, have made transportation a critical concern in our era. Amidst high pollution levels in urban areas, environmental considerations have become paramount, putting sustainability at the forefront. As a result, researchers are increasingly emphasizing the integration of environmentally friendly measures into transportation models. Such strategies include the adoption of emission-free buses, public bike stations, and vehicle-sharing programs [1]. Transit networks play a crucial role in sustainable transportation systems, garnering considerable attention from the academic community in terms of both planning and operational aspects.
The Urban Transit Routing Problem (UTRP) is a challenging problem in transportation planning that involves designing and optimizing transit route networks for urban areas [2]. The objective is to find the most efficient routes for public transportation vehicles, considering factors such as travel time, passenger demand, transfer connections, vehicle capacities, operating costs, and environmental impacts. The problem is usually formulated as an optimization problem that seeks to minimize some form of total system costs while satisfying specific service levels and performance criteria. The UTRP is a complex problem due to the large number of potential routes and the various constraints that must be considered. Finding an optimal solution to the UTRP is known to be computationally difficult, with many heuristic and metaheuristic algorithms developed to address the problem [3]. These include techniques such as genetic algorithms (GAs), simulated annealing, and swarm intelligence methods [4]. Efficient and effective public transportation systems are critical for the mobility and sustainability of urban areas, making the UTRP an important area of research in transportation engineering.

2. The Urban Transit Routing Problem

In the field of transportation, addressing the UTRP has been an ongoing challenge for researchers. Early attempts to tackle the problem relied on heuristic approaches, which proved to be limited in handling large networks and delivering accurate solutions [5]. However, they did lay the groundwork for the development of future methodologies. Analytical methods were then employed, aiming to estimate network structure based on the physical characteristics of transit networks. Yet, as noted by Chakroborty and Wivedi [6], these methods optimized only parameters such as route spacing and length, rather than determining the actual routes themselves. Mathematical programming formulations were also investigated [7][8] but proved inadequate for realistically representing transit routes. Such formulations constructed routes to achieve desirable features, which were reflected by the objective function and constraints rather than determining them directly through the mathematical program.
Early work on metaheuristics included single-solution approaches and Gas. Various single-solution metaheuristics have been proposed, often in combination with other metaheuristics. Simulated annealing frameworks were presented by Zhao and Zeng [9], Fan and Machemehl [10], and Fan and Mumford [3]. Other approaches using Tabu Search were developed by Fan and Machemehl [11], Pacheco et al. [12], and Roca-Riu et al. [13]. Most relevant studies, however, proposed different evolutionary optimization approaches, including GAs, multi-objective evolutionary algorithms, and memetic algorithms for solving the UTRP. Among the early such studies, Chakroborty and Wiwedi [6] presented a novel stochastic initialization procedure and a multi-criteria evaluation method using a GA, while Chew and Lee [14] developed an efficient GA solution scheme. Nayeem et al. [15] used a GA featuring the concept of elitism and an increasing population approach. More recently, Jha et al. [16] used a GA for determining routes combined with a multi-objective PSO framework for generating corresponding frequencies. Additionally, differential evolution strategies and memetic evolutionary algorithms have also been proposed by Buba and Lee [17][18], Zhao et al. [19], and Duran-Micco et al. [20].
In a departure from earlier GAs and single-solution metaheuristics, swarm intelligence methods, such as Bee Colony Optimization (BCO), PSO, and Ant Colony Algorithms (ACOs), have been receiving growing attention for solving the UTRP, showcasing their potential in addressing the problem. Early efforts using swarm intelligence for transit network optimization were based on ACO. Hu et al. [21] proposed two methods to maximize passenger flow and optimize headways, while Yu and Yang [22] presented an iterative approach to obtain a Pareto-optimal solution for bus network design and transit assignment. Yang et al. [23] proposed a coarse-grain parallel ant colony algorithm to optimize a bus network, while Blum and Mathew [24] presented an intelligent agent system based on ant colonies to determine routes and frequencies for a given transit network. Yu et al. [25] extended the direct traveler density model to maximize transit trip density with respect to total demand and route length using ACO. A subsequent stream of studies investigated the potential of bee colonies for the UTRP. In this line of work, Szeto and Jiang [26] and Jiang et al. [27] used a hybrid enhanced artificial bee colony algorithm to determine the route structure for a bus network. Nikolić and Teodorović [28] proposed a BCO model for the UTRP, which outperformed other metaheuristics on Mandl’s network. They later extended their work [29] to simultaneously determine both routes and frequencies.
In terms of PSO, the standard version of the algorithm is well-suited for continuous optimization problems since it employs equations to calculate the velocity and position of any individual. However, for discrete decision variables such as those in the UTRP, appropriate modifications must be made to represent the search process. In this respect, Kechagiopoulos and Beligiannis [30] developed a discrete version of the PSO algorithm, demonstrating competitive performance compared to other metaheuristics. In a later effort, Gunby and Gustavsen [31] proposed a hybrid swarm intelligence method that combines ACO with additional attributes inspired by BCO and PSO, resulting in better performance than the basic ACO implementation. Recently, Katsaragakis et al. [32] introduced a modified version of the Cat Swarm Optimization (CSO) algorithm for the UTRP that achieved better results than previous implementations.

References

  1. Iliopoulou, C.; Tassopoulos, I.; Kepaptsoglou, K.; Beligiannis, G. Electric Transit Route Network Design Problem: Model and Application. Transp. Res. Rec. 2019, 2673, 264–274.
  2. Fan, L.; Mumford, C.L.; Evans, D. A Simple Multi-Objective Optimization Algorithm for the Urban Transit Routing Problem. In Proceedings of the 2009 IEEE Congress on Evolutionary Computation, Trondheim, Norway, 18–21 May 2009; pp. 1–7.
  3. Fan, L.; Mumford, C. A Metaheuristic Approach to the Urban Transit Routing Problem. J. Heuristics 2010, 16, 353–372.
  4. Durán-Micco, J.; Vansteenwegen, P. A Survey on the Transit Network Design and Frequency Setting Problem. Public Transp. 2022, 14, 155–190.
  5. Iliopoulou, C.; Kepaptsoglou, K.; Vlahogianni, E. Metaheuristics for the Transit Route Network Design Problem: A Review and Comparative Analysis. Public Transp. 2019, 11, 487–521.
  6. Chakroborty, P.; Wivedi, T. Optimal Route Network Design for Transit Systems Using Genetic Algorithms. Eng. Optim. 2002, 34, 83–100.
  7. Baaj, M.; Mahmassani, H.S. An AI-Based Approach for TRansit Route System Planning and Design. J. Adv. Transp. 1991, 25, 187–210.
  8. Ceder, A.; Israeli, Y. User and Operator Perspectives in Transit Network Design. Transp. Res. Rec. 1998, 1623, 3–7.
  9. Zhao, F.; Zeng, X. Optimization of Transit Route Network, Vehicle Headways and Timetables for Large-Scale Transit Networks. Eur. J. Oper. Res. 2008, 186, 841–855.
  10. Fan, W.; Machemehl, R.B. Using a Simulated Annealing Algorithm to Solve the Transit Route Network Design Problem. J. Transp. Eng. 2006, 132, 122–132.
  11. Fan, W.; Machemehl, R.B. Tabu Search Strategies for the Public Transportation Network Optimizations with Variable Transit Demand; Wiley: Hoboken, NJ, USA, 2008; Volume 23.
  12. Pacheco, J.; Alvarez, A.; Casado, S.; González-Velarde, J.L. A Tabu Search Approach to an Urban Transport Problem in Northern Spain. Comput. Oper. Res. 2009, 36, 967–979.
  13. Roca-Riu, M.; Estrada, M.; Trapote, C. The Design of Interurban Bus Networks in City Centers. Transp. Res. Policy Pract. 2012, 46, 1153–1165.
  14. Chew, J.S.C.; Lee, L.S. A Genetic Algorithm for Urban Transit Routing Problem. Int. J. Mod. Phys. Conf. Ser. 2012, 9, 411–421.
  15. Nayeem, M.A.; Rahman, M.K.; Rahman, M.S. Transit Network Design by Genetic Algorithm with Elitism. Transp. Res. Emerg. Technol. 2014, 46, 30–45.
  16. Jha, S.B.; Jha, J.K.; Tiwari, M.K. A Multi-Objective Meta-Heuristic Approach for Transit Network Design and Frequency Setting Problem in a Bus Transit System. Comput. Ind. Eng. 2019, 130, 166–186.
  17. Buba, A.T.; Lee, L.S. A Differential Evolution for Simultaneous Transit Network Design and Frequency Setting Problem. Expert. Syst. Appl. 2018, 106, 277–289.
  18. Buba, A.T.; Lee, L.S. Differential Evolution for Urban Transit Routing Problem. J. Comput. Commun. 2016, 4, 11–25.
  19. Zhao, H.; Xu, W.; Jiang, R. The Memetic Algorithm for the Optimization of Urban Transit Network. Expert. Syst. Appl. 2015, 42, 3760–3773.
  20. Duran-Micco, J.; Vermeir, E.; Vansteenwegen, P. Considering Emissions in the Transit Network Design and Frequency Setting Problem with a Heterogeneous Fleet. Eur. J. Oper. Res. 2020, 282, 580–592.
  21. Hu, J.; Shi, X.; Song, J.; Xu, Y. LNCS 3611—Optimal Design for Urban Mass Transit Network Based on Evolutionary Algorithms; Springer: Berlin, Germany, 2005; Volume 3611.
  22. Yu, B.; Yang, Z.; Cheng, C.; Liu, C. Optimizing bus transit network with parallel ant colony algorithm. In Proceedings of the Eastern Asia Society for Transportation Studies; Semantic Scholar: Seattle, WA, USA, 2005.
  23. Yang, Z.; Yu, B.; Cheng, C. A Parallel Ant Colony Algorithm for Bus Network Optimization. Comput. Aided Civ. Infrastruct. Eng. 2007, 22, 44–55.
  24. Blum, J.J.; Mathew, T.V. Intelligent Agent Optimization of Urban Bus Transit System Design. J. Comput. Civ. Eng. 2011, 25, 357–369.
  25. Yu, B.; Yang, Z.Z.; Jin, P.H.; Wu, S.H.; Yao, B.Z. Transit Route Network Design-Maximizing Direct and Transfer Demand Density. Transp. Res. Emerg. Technol. 2012, 22, 58–75.
  26. Szeto, W.; Jiang, Y. Hybrid Artificial Bee Colony Algorithm for Transit Network Design. Transp. Res. Rec. 2012, 2284, 47–56.
  27. Jiang, Y.; Szeto, W.; Ng, T. Transit Network Design: A Hybrid Enhanced Artificial Bee Colony Approach and a Case Study. Int. J. Transp. Sci. Technol. 2013, 2, 243–260.
  28. Nikolić, M.; Teodorović, D. Transit Network Design by Bee Colony Optimization. Expert. Syst. Appl. 2013, 40, 5945–5955.
  29. Nikolić, M.; Teodorović, D. A Simultaneous Transit Network Design and Frequency Setting: Computing with Bees. Expert. Syst. Appl. 2014, 41, 7200–7209.
  30. Kechagiopoulos, P.N.; Beligiannis, G.N. Solving the Urban Transit Routing Problem Using a Particle Swarm Optimization Based Algorithm. Appl. Soft Comput. J. 2014, 21, 654–676.
  31. Gunby, H.; Gustavsen, S. A Combined Swarm System for the Urban Transit Routing Problem; NTNU: Trondheim, Norway, 2015.
  32. Katsaragakis, I.V.; Tassopoulos, I.X.; Beligiannis, G.N. Solving the Urban Transit Routing Problem Using a Cat Swarm Optimization-Based Algorithm. Algorithms 2020, 13, 223.
More
© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.
Upload a video for this entry
Information
Subjects: Computer Science, Artificial Intelligence; Transportation; Transportation Science & Technology
Contributors MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register :
Vasileios Kourepinis
,
Christina Iliopoulou
,
Ioannis X. Tassopoulos
,
Chrysanthi Aroniadi
,
Grigorios N. Beligiannis
View Times: 270
Revisions: 2 times (View History)
Update Date: 21 Aug 2023
Table of Contents
    1000/1000
    Hot Most Recent
    Feedback