Transit Frequency Optimization in Bi-modal Networks Using Differential Evolution Algorithm

Abstract

This study proposes a bi-level optimization model for the transit frequency setting problem in bi-modal networks. The objective of the upper-level problem is to obtain a solution set of bus line frequencies that provide the minimum total travel cost of the car and bus users. Differential Evolution (DE) algorithm is employed in the upper-level model to determine the optimal headways for a given route structure. The lower-level model is a congested multi-modal user equilibrium assignment model, which considers the interactions of car and bus flows, for determining joint mode/route preferences of the network users, which considers the interactions of car and bus flows. The developed model is tested on Mandl's benchmark network to evaluate its performance and applicability. The comparative experiments demonstrate that the proposed model leads to reductions in transportation costs. Also, the results of numerous optimization runs show that DE performs well in finding similar frequency sets in independent optimizations.

Keywords

• Transit frequency setting problem
• bus frequency optimization
• multimodal assignment
• differential evolution algorithm
• bi-level optimization

References

1. Ceder. A., Public Transit Planning and Operation: Modeling, Practice and Behavior, CRC Press, Boca Raton, USA, 2015.
2. Magnanti, T. L., Wong, R. T., Network Design and Transportation Planning: Models and Algorithms. Transportation Science, 18(1), 1–55, 1984.
3. Guihaire, V., Hao, J.-K. K., Transit network design and scheduling: A global review. Transportation Research Part A: Policy and Practice, 42(10), 1251–1273, 2008.
4. Zhao, F., Large-Scale Transit Network Optimization by Minimizing User Cost and Transfers. Journal of Public Transportation, 9(2), 107–129, 2006.
5. Yang, H., Bell, M. G. H., Models and algorithms for road network design: a review and some new developments. Transport Reviews, 18(3), 257–278, 1998.
6. Farahani, R. Z., Miandoabchi, E., Szeto, W. Y., Rashidi, H., A review of urban transportation network design problems. European Journal of Operational Research, 229(2), 281–302, 2013.
7. Ibarra-Rojas, O. J., Delgado, F., Giesen, R., Munoz, J. C., Planning, operation, and control of bus transport systems: A literature review. Transportation Research Part B: Methodological, 77, 38–75, 2015.
8. Constantin, I., Florian, M., Optimizing Frequencies in a Transit Network: A Nonlinear Bi-level Programming Approach. International Transactions in Operational Research, 2(2), 149–164, 1995.

9. Gao, Z., Sun, H., Shan, L. L., A continuous equilibrium network design model and algorithm for transit systems. Transportation Research Part B: Methodological, 38(3), 235–250, 2004.
10. Yoo, G. S., Kim, D. K., Chon, K. S., Frequency design in urban transit networks with variable demand: Model and algorithm. KSCE Journal of Civil Engineering, 14(3), 403–411, 2010.
11. dell'Olio, L., Ibeas, A., Ruisánchez, F., Optimizing bus-size and headway in transit networks. Transportation, 39(2), 449–464, 2012.
12. Giesen, R., Martinez, H., Mauttone, A., Urquhart, M. E., A method for solving the multi-objective transit frequency optimization problem. Journal of Advanced Transportation, 50 (8), 2323-2337, 2016.
13. Gholami, A., Tian, Z., The comparison of optimum frequency and demand based frequency for designing transit networks. Case Studies on Transport Policy, 7(4), 698–707, 2019.
14. Mutlu, M. M., Aksoy, İ. C., Alver, Y., COVID-19 transmission risk minimization at public transportation stops using Differential Evolution algorithm. European Journal of Transport and Infrastructure Research, 21(1), 53-69, 2021.
15. Gallo, M., D'Acierno, L., Montella, B., A multimodal approach to bus frequency design. 17th International Conference on Urban Transport and the Environment, Pisa, Italy, 2011.
16. Uchida, K., Sumalee, A., Watling, D., Connors, R., Study on Optimal Frequency Design Problem for Multimodal Network Using Probit-Based User Equilibrium Assignment. Transportation Research Record: Journal of the Transportation Research Board, 1923(1), 236-345, 2005.
17. Nearchou, A. C., Meta-heuristics from nature for the loop layout design problem. International Journal of Production Economics, 101(2), 312-328, 2006.
18. Civicioglu, P., Besdok, E., A conceptual comparison of the Cuckoo-search, particle swarm optimization, differential evolution and artificial bee colony algorithms. Artificial Intelligence Review, 39, 315-346, 2013.
19. Hammouche, K., Diaf, M., Siarry, P., A comparative study of various metaheuristic techniques applied to the multilevel thresholding problem. Engineering Applications of Artificial Intelligence, 23(5), 676-688, 2010.
20. Miandoabchi, E., Daneshzand, F., Szeto, W. Y., Farahani, R. Z., Multi-objective discrete urban road network design. Computers & Operations Research. 40(10), 2429–2449, 2013.
21. Storn, R., Price, K.,. Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization, 11, 341–359, 1997.
22. De Cea, J., Fernández, E., Transit Assignment for Congested Public Transport Systems: An Equilibrium Model. Transportation Science, 27(2), 133–147, 1993.
23. Chriqui, C., Robillard, P., Common Bu Lines. Transportation Science, 6(2), 115-121, 1975.
24. Florian, M., Spiess, H., The convergence of diagonalization algorithms for asymmetric network equilibrium problems. Transportation Research Part B: Methodological, 16(6), 477–483, 1982.
25. Miandoabchi, E., Farahani, R. Z., Szeto, W. Y., Bi-objective bimodal urban road network design using hybrid metaheuristics. Central European Journal of Operations Research, 20(4), 583–621, 2012.
26. Sheffi. Y., Urban transportation networks, Prentice-Hall, NJ, USA, 1985.
27. Frank, M., Wolfe, P., An algorithm for quadratic programming. Naval Research Logistics, 3(1‐2), 95–110, 1956.
28. Mandl, C. E., Evaluation and optimization of urban public transportation networks. European Journal of Operational Research, 5(6), 396–404, 1980.
29. Arbex, R. O., da Cunha, C. B., Efficient transit network design and frequencies setting multi-objective optimization by alternating objective genetic algorithm. Transportation Research Part B: Methodological, 81(2), 355–376, 2015.
30. 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. Computers and Industrial Engineering, 130, 166–186, 2019.