A Novel Solution Methodology for Transit Route Network Design Problem

Transit route Network Design Problem (TrNDP) is the most important component in Transit planning, in which the overall cost of the public transportation system highly depends on it. The main purpose of this study is to develop a novel solution methodology for the TrNDP, which goes beyond pervious traditional sophisticated approaches. The novelty of the solution methodology, adopted in this paper, stands on the deterministic operators which are tackled to construct bus routes. The deterministic manner of the TrNDP solution relies on using linear and integer mathematical formulations that can be solved exactly with their standard solvers. The solution methodology has been tested through Mandl’s benchmark network problem. The test results showed that the methodology developed in this research is able to improve the given network solution in terms of number of constructed routes, direct transit service coverage, transfer directness and solution reliability. Although the set of routes resulted from the methodology would stand alone as a final efficient solution for TrNDP, it could be used as an initial solution for meta-heuristic procedures to approach global optimal. Based on the presented methodology, a more robust network optimization tool would be produced for public transportation planning purposes.

• Ghada Moussa
• Mamoud Owais

• Integer programming
• Transit route design
• Transportation
• Urban planning.

[1] E. Cipriani, S. Gori, and M. Petrelli, "Transit Network Design: A Procedure and an Application to a Large Urban Area," Transport Res C-Emer, 20, pp. vol.3, no.14, 2012.
[2] A. Ibeas, L. dell’Olio, B. Alonso, and O. Sainz, "Optimizing Bus Stop Spacing in Urban Areas," Transport Res D-Tr E, 46, pp. 446-458, 2010.
[3] R. Z. Farahani,E. Miandoabchi, W. Szeto, and H. Rashidi, "A Review of Urban Transportation Network Design Problems," Eur J Oper Res, vol.229, no.2, pp. 281-302, 2013.
[4] P. Chakroborty, "Genetic Algorithms for Optimal Urban Transit Network Design," Comput Aided Civil & Infrastructure Eng. Blackwell Pub., MA 02148, USA, 18, pp.184–200, 2003.
[5] M.Baaj,The Transit Network Design Problem: An AI-Based Approach, Ph.D, 1990.
[6] A. Gan, and F. Zhao, Optimization of Transit Network to Minimize Transfers. Final Report, Research Office Florida Department of Transportation 605 Suwannee Street, MS 30 Tallahassee FL 32399-0450, 2003.
[7] M. R. Garey, & D. S. Johnson, Computers and Intractability: A Guide to the Theory of np-Completeness,. W.H. Freeman, 5-1045, 1979.
[8] W. Lampkin, & P. Saalmans, "The Design of Routes, Service Frequencies and Schedules for a Municipal Bus Undertaking: A Case Study," Oper Res, vol. 18, pp. 375-397, 1967.
[9] M. H. Baaj, and H. Mahmassani "An AI-Based Approach for Transit Route System Planning and Design,"J. Adv Transport, vol. 25, no.2, pp. 187-210, 1991.
[10] M. H. Baaj, and H. Mahmassani, "Hybrid Route Generation Heuristic Algorithm for the Design of Transit Networks," Transport Res C-Emer, vol. 3, no.1, pp.31-50, 1995.
[11] M. C. Shih, and H. Mahmassani, A Design Methodology for Bus Transit Networks with Coordinated Operation. (Ph.D), the University of Texas at Austin, Austin, Texas, 1994.
[12] A. Mauttonw, and M. Urquhart, "A Route Set Construction Algorithm for the Transit Network Design Problem," Comput and Oper Res, vol 36, no.8, pp.2440-2449, 2009.
[13] S.B. Pattnaik, S. Mohan, and V. M. Tom, "Urban Bus Transit Route Network Design Using Genetic Algorithm," J Trans Eng., vol.124, no.4, pp.368-375, 1998.
[14] F. Zhao, Large-Scale Transit Network Optimization by Minimizing Transfers and User Cost. J Public Trans, vol. 9, no.2, pp.107–129, 2006.
[15] Yu, Bin, Yang, & Zhongzhen, "An Ant Colony Optimization Model: ThePeriod Vehicle Routing Problem with time Windows," Transport Res E-Log, vol. 47, no. 2, pp.166–181, 2011.
[16] M. Nikolic, and D. Teodorovic, "Transit Network Design by Bee Colony Optimization," Expert Syst Appl, vol.40, pp.5945–5955, 2013.
[17] W. R. Hamilton, "MemorandumRespecting a New System of Roots of Unity," Philos Mag, vol.12, no.4, pp. 446, 1856.
[18] G. Desaulniers, and M. Hickman, Handbook in OR and MS. Elsevier, (Chapter 2), 2007.
[19] C. Chriqui, and P. Robillard, "Common Bus Lines. Hautes Eludes Commercials, Montréal, Québec, Canada, Transportation, vol. 9, no.2, pp.115–121, 1975.
[20] P. Marguier, and A. Ceder, A. (1984). Passenger Waiting Strategies for Overlapping Bus Routes. Massachusetts Institute of Technology, Cambridge, Massachusetts, Transportation Science, vol. 18, no.3, pp. 207-230, 1984.
[21] H. Spiess, On Optimal Route Choice Strategies in Transit Networks, Publication 285, Centre de Recherche sur les Transports, Université de Montréal,1983.
[22] Dijkstra , A Note on Two Problems in Connection with Graphs. Numer Math,1, pp. 269-271, 1959.
[23] J. Yen, Finding the K Shortest Loopless Paths in a Network. Manag Sci , vol.7, no.11, pp.712-716, 1971.
[24] B. Yu, Z. Yang, P. Jin, S. Wu, and B. Yao, "Transit Route Network Design-Maximizing Direct and Transfer Demand Density," Transport Res C-Emer, vol.22, pp.58-75, 2012.
[25] N. E. Lownes, & R. B. Machemehl, "Exact and Heuristic Methods for Public Transit Circulator Design," Transport Res B-Meth, vol.44, no.2, pp.309–318, 2010.
[26] A. Ceder, and S Jerby, "Optimal Routing Design for Shuttle Bus Service. Transportation Research Record: Journal of the Transportation Research Board, pp.14-22, 2006.
[27] Mandl, C. E. (1980). Evaluation and Optimization of Urban Public Transportation Networks. European Journal of Operation Research, 5(6), 396-404.
[28] L. Fan, & C. Mumford, "A Metaheuristic Approach to the Urban Transit Routing Problem,"J Heuristics, vol. 16, pp.353-372, 2008.
[29] F. Zhao, and X. Zeng, "Optimization of Transit Route Network, Vehicle Headways and Timetables for Large-Scale Transit Networks," European Journal of Operational Research, 186, 841–855, 2008.
[30] Bagloee, S., & Ceder, A. (2011). Transit-Network Design Methodology for Actual-Size Road Networks. Transportation Research Part B: Methodological, 45(10), 1787-1804.