Application of a Hill-Climbing Algorithm to Public Transportation Routes Design in Grid Networks

Document Type : Research Paper

Authors

1 Assistant Professor of Transportation Planning at University of Mazandaran

2 University of mazandaran

Abstract

Transit Routes Design (TRD) problem deals with optimizing the configuration of transit routes to satisfy a given objective, such as maximizing network coverage, while holding the budget constraint. In its discrete form, TRD is recognized as a computationally interactive problem. A review of the literature reveals that, despite extensive research on this problem, the number of studies on specific urban network configurations has remained limited. Among these studies, many have applied simplifying assumptions such as continuous design variables which may not be applicable to real-world settings. The present study focuses on a discrete version of the TRD problem for an urban “grid” network and aims to maximize the service coverage through the network. To this end, a local search Hill-Climbing (HC) heuristic algorithm is proposed and evaluated. The proposed HC algorithm performs several replications in which it starts with a combination of randomly selected routes and iteratively improves them by moving to the “best neighbour” until it reaches a local optimum solution. Our results for a 6×10 grid network for three budget levels (i.e. low, medium, and high budget levels) indicate that, in much shorter run-times than the exact algorithm, the proposed HC algorithm can produce high-quality solutions with 0.12%, 4.16%, and 2.22% difference from global optimums.

Keywords

References

- Baaj, M. H. and Mahmassani, H. S. (1991) “An AI-based approach for transit route system planning and design”, Journal of Advanced Transportation: Vol. 25, No. 2, pp. 187–210.
 
- Badia, H., Estrada, M. and Robusté, F. (2014). “Competitive transit network design in cities with radial street patterns”, Transportation Research Part B: Methodological, Vol. 59, pp. 161-181.
- Ceder, A. (2016) “Public transit planning and operation: Modeling, practice and behavior”, CRC press.
 
- Daganzo, C.F. (2010). “Structure of competitive transit networks”, Transportation Research Part B: Methodological, Vol. 44, No. 4, pp. 434-46.
 
- Dokeroglu, T., Sevinc, E., Kucukyilmaz, T. and Cosar, A. (2019). “A survey on new generation metaheuristic algorithms”, Computers & Industrial Engineering, Vol. 137, pp. 106040.
 
- Estrada, M., Roca-Riu, M., Badia, H., Robusté, F. and Daganzo, C.F. (2011). “Design and implementation of efficient transit networks: procedure, case study and validity test”, Procedia-Social and Behavioral Sciences, Vol. 17, pp. 113-35.
 
- Guihaire, V. and Hao, J. K. (2008) “Transit network design and scheduling: A global review”, Transportation Research Part A, Vol. 42, pp. 1251-73.
 
- Fan, W., Mei, Y. and Gu, W. (2018). “Optimal design of intersecting bimodal transit networks in a grid city”, Transportation Research Part B: Methodological, Vol. 111, pp. 203-26.
 
- Ibarra-Rojas, O. J., Felipe Delgado, R. G. and Juan C. M. (2015) "Planning, operation, and control of bus transport systems: A literature review", Transportation Research Part B: Methodological, Vol. 77, pp. 38-75.
 
- Iliopoulou, C., Kepaptsoglou, K. and Vlahogianni, E. (2019). “Metaheuristics for the transit route network design problem: a review and comparative analysis”, Public Transport, Vol. 11, No. 3, pp. 487-521.
 
- Kepaptsoglou, K., and Karlaftis, M. (2009) “Transit route network design problem”, Journal of transportation engineering, Vol. 135, No. 8, pp. 491-505.
- Khanzad, I. K., Zarrinmehr, A. Z., Seyedabrishami, S. S. and Saffarzadeh, M. S. (2017) “Application of A Route Expansion Algorithm for Transit Routes Design in Grid Networks”, International Journal of Transportation Engineering, Vol. 4, No. 3, pp. 179-96.
 
- Laporte, G., Ortega, F. A., Pozo, M. A. and Puerto, J. (2017) “Multi-objective integration of timetables, vehicle schedules and user routings in a transit network”, Transportation Research Part B: Methodological, Vol. 98, pp. 94-112.
 
- Li, W., Ding, Y., Yang, Y., Sherratt, R.S., Park, J.H. and Wang, J. (2020). “Parameterized algorithms of fundamental NP-hard problems: a survey”, Human-Centric Computing and Information Sciences, Vol. 10, No. 1, pp. 1-24.
 
 
- Mauttone, A., Cancela, H. and Urquhart, M.E. (2021). “Public Transportation”, In Network Design with Applications to Transportation and Logistics, Springer, Cham.
 
- Merlin, L.A., Singer, M. and Levine, J. (2021). “Influences on transit ridership and transit accessibility in US urban areas”, Transportation Research Part A: Policy and Practice, Vol. 150, pp. 63-73.
 
- Miyagawa, M. (2018). “Spacing of intersections in hierarchical road networks”, Journal of the Operations Research Society of Japan, Vol. 61, No. 4, pp. 272-280.
 
- Nourbakhsh, S.M. and Ouyang, Y. (2012). “A structured flexible transit system for low demand areas”, Transportation Research Part B: Methodological, Vol. 46, No. 1, pp. 204-16.
 
- Ranjbari, A., Hickman, M. and Chiu, Y.C. (2020). “Network Design with Elastic Demand and Dynamic Passenger Assignment to Assess the Performance of Transit Services”, Journal of Transportation Engineering, Part A: Systems, Vol. 146, No. 5, pp. 04020030 1-11.
 
- Rao, K.R., Mitra, S. and Szmerekovsky, J. (2021). “Bus Transit Network Structure Selection with Multiple Objectives”, International Journal of Operations Research and Information Systems (IJORIS), Vol. 12, No. 4, pp. 1-13.
 
- Saif, M.A., Zefreh, M.M. and Torok, A. (2019). “Public transport accessibility: a literature review”, Periodica Polytechnica Transportation Engineering, Vol. 47, No. 1, pp. 36-43.
 
- Stern, R. (1996) “Passenger transfer system review”, Synthesis of Transit Practice, Vol. 19, Transportation Research Board, National Academy Press, Washington D.C.
 
- Ukkusuri, V. and Patil, G. (2009) “Multi-period transportation network design under demand uncertainty”, Transportation Research Part B: Methodological, Vol. 43, No. 6, pp. 625–42.
 
- Ul Abedin, Z., Busch, F., Wang, D.Z., Rau, A. and Du, B. (2018). “Comparison of public transport network design methodologies using solution-quality evaluation”, Journal of Transportation Engineering, Part A: Systems, Vol. 144, No. 8, pp. 1-13.
 
- Walker, J. (2020) “Why do so many public transport networks use grid systems?”, https://www.citymetric.com/transport/why-do-so-many-public-transport-networks-use-grid-systems-955.
 
- Wu, Z. (2014). “Non-branching hybrid transit network design under heterogeneous demand”, Faculty of Civil and Environmental Engineering, University of Illinois at Urbana-Champaign.
 
- Zarrinmehr, A., Aashtiani, H.Z., Nie, Y. and Azizian, H. (2019). “Complementarity Formulation and Solution Algorithm for Auto-Transit Assignment Problem”, Transportation Research Record, Vol. 2673, No. 4, pp.384-97.
 
- Zarrinmehr, A., Saffarzadeh, M. and Seyedabrishami, S. (2018) “A local search algorithm for finding optimal transit routes configuration with elastic demand”, International Transactions in Operational Research, Vol. 25, No. 5, pp. 1491-514.
 
- Zarrinmehr, A., Saffarzadeh, M., Seyedabrishami, S. and Nie, Y.M. (2016) “A path-based greedy algorithm for multi-objective transit routes design with elastic demand”, Public Transport, Vol. 8, No. 2, pp. 261-93.
 
- Zarrinmehr, A. and Shafahi, Y. (2014) “Enumeration of Dominant Solutions: An Application in Transport Network Design”, International Journal of Transportation Engineering, Vol. 1, No. 4, pp. 335-48.
 
- Zarrinmehr, A. and Shafahi, Y. (2016) “Parallelization of the Branch-and-Bound Algorithm in Transportation Discrete Network Design”, Scientia Iranica, Vol. 23, No. 2, pp. 407-19.
International Journal of Transportation Engineering
Volume 9, Issue 2 - Serial Number 34
October 2021
Pages 597-612

Files

Share

How to cite

Statistics