CFP last date
20 June 2024
Reseach Article

Simple and Effective Solution Methodology for Transit Network Design Problem

by Mahmoud Owais, Ghada Moussa, Yousef Abbas, Mohamed El-shabrawy
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 89 - Number 14
Year of Publication: 2014
Authors: Mahmoud Owais, Ghada Moussa, Yousef Abbas, Mohamed El-shabrawy
10.5120/15702-4681

Mahmoud Owais, Ghada Moussa, Yousef Abbas, Mohamed El-shabrawy . Simple and Effective Solution Methodology for Transit Network Design Problem. International Journal of Computer Applications. 89, 14 ( March 2014), 32-40. DOI=10.5120/15702-4681

@article{ 10.5120/15702-4681,
author = { Mahmoud Owais, Ghada Moussa, Yousef Abbas, Mohamed El-shabrawy },
title = { Simple and Effective Solution Methodology for Transit Network Design Problem },
journal = { International Journal of Computer Applications },
issue_date = { March 2014 },
volume = { 89 },
number = { 14 },
month = { March },
year = { 2014 },
issn = { 0975-8887 },
pages = { 32-40 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume89/number14/15702-4681/ },
doi = { 10.5120/15702-4681 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:09:16.442881+05:30
%A Mahmoud Owais
%A Ghada Moussa
%A Yousef Abbas
%A Mohamed El-shabrawy
%T Simple and Effective Solution Methodology for Transit Network Design Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 89
%N 14
%P 32-40
%D 2014
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Transit Network Design Problem (TNDP) is the most important component in Transit planning and operation, in which the overall cost of the public transportation system highly depends on it. The main purpose of this study is to develop a simple and effective solution methodology for the TNDP, which goes beyond previous traditional sophisticated approaches. The solution methodology adopted in this research for the TNDP is based on partitioning the solution into two consecutive stages; Transit route Network Design Problem "TrNDP" stage and frequency setting stage. In the first stage; a deterministic solution for TrNDP is 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. In the second stage; bus frequencies are optimized among bus routes (obtained in stage 1) via Genetic Algorithm, for a total bus fleet size representing operator's main cost. The adopted solution methodology has been tested through Mandl's benchmark transit network problem. The test results showed that the methodology developed in this research is able to provide and effective solution in terms of the number of constructed routes, the direct demand coverage, and the total travel time.

References
  1. Cipriani, E. , S. Gori, and M. Petrelli, Transit network design: A procedure and an application to a large urban area. Transportation Research Part C, 2012. 20: p. 3-14.
  2. Ibeas, Á. , et al. , Optimizing bus stop spacing in urban areas. Transportation Research Part E, 2010. 46: p. 446-458.
  3. Farahani, R. Z. , et al. , A review of urban transportation network design problems. European Journal of Operational Research, 2013. 299(2): p. 281-302.
  4. Chakroborty, P. , Genetic Algorithms for Optimal Urban Transit Network Design. Computer – Aided Civil and Infrastructure Eng. Blackwell Publishing, Malden MA 02148, USA, 2003. 18: p. 184–200.
  5. Garey, M. R. and D. S. Johnson, Computers and intractability: A guide to the theory of np-completeness. W. H. Freeman, 1979: p. 5-1045.
  6. Baaj, M. H. , The Transit Network Design Problem: An AI-Based Approach, in Department of Civil Engineering, University of Texas, Austin, Texas. 1990.
  7. Gan, A. 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.
  8. Yu, B. , et al. , Transit route network design-maximizing direct and transfer demand density. Transportation Research Part C: Emerging Technologies, 2012. 22: p. 58-75.
  9. Gao, Z. , H. Sun, and L. Shan, A Continuous Equilibrium Network Design Model and Algorithm for Transit Systems. Transportation Research Part B: Methodological, 2004. 38(3): p. 235-250.
  10. Guan, J. F. , H. Yang, and S. C. Wirasinghe, Simultaneous optimization of transit line configuration and passenger line assignment. Transportation Research Part B, 2006. 40: p. 885–902.
  11. Pattnaik, S. B. , S. Mohan, and V. M. Tom, Urban Bus Transit Route Network Design Using Genetic Algorithm. Journal of Transportation Engineering, 1998. 124(4): p. 368-375.
  12. Szeto, W. Y. and Y. Wu, A simultaneous bus route design and frequency setting problem for Tin Shui Wai, Hong Kong. European Journal of Operational Research, 2011. 209(2): p. 141-155.
  13. Mandl, C. E. , Evaluation and optimization of urban public transportation networks. European Journal of Operation Research, 1980. 5(6): p. 396-404.
  14. Shih, M. -C. and H. Mahmassani, A design methodology for bus transit networks with coordinated operation, in SWUTC/94/60016-1, Center for Transportation, Bureau of Engineering Research. 1994, the University of Texas at Austin, Austin, Texas.
  15. Baaj, M. H. and H. Mahmassani, Hybrid Route Generation Heuristic Algorithm for the Design of Transit Networks. Transportation Research Part C: Emerging Technologies, 1995. 3(1): p. 31-50.
  16. Chakroborty, P. , K. Deb, and R. K. Sharma, Networkwide optimal scheduling of urban transit networks using genetic algorithms. Transportation Planning and Technology, 2001. 24(3): p. 209–26.
  17. Zhao, F. , Large-scale transit network optimization by minimizing transfers and user cost. Journal of Public Transportation, 2006. 9(2): p. 107–129.
  18. Fan, L. and C. Mumford, A Metaheuristic Approach to the Urban Transit Routing Problem. J Heuristics, 2008. 16: p. 353-372.
  19. Mauttonw, A. and M. Urquhart, A route set construction algorithm for the transit network design problem. Computers and Operations Research, 2009. 36(8): p. 2440-2449.
  20. Dijkstra, E. W. , A Note on Two Problems in Connection with Graphs. Numeriche Mathematik, 1959. 1: p. 269-271.
  21. Yen, J. Y. , Finding the K Shortest Loopless Paths in a Network. Management Science, 1971. 7(11): p. 712-716.
  22. Lownes, N. E. and R. B. Machemehl, Exact and heuristic methods for public transit circulator design. Transportation Research Part B, 2010. 44(2): p. 309–318.
  23. Ceder, A. and S. Jerby, Optimal Routing Design for Shuttle Bus Service. Transportation Research Record: Journal of the Transportation Research Board, 2006: p. 14-22.
  24. Bagloee, S. and A. Ceder, Transit-network design methodology for actual-size road networks. Transportation Research Part B: Methodological, 2011. 45(10): p. 1787-1804.
  25. Desaulniers, G. and M. Hickman, Handbook in OR & MS. Elsevier, (Chapter 2). 2007.
  26. Chriqui, C. and P. Robillard, Common Bus Lines. Hautes Eludes Commercials, Montréal, Québec, Canada, Transportation, 1975. 9(2): p. 115–121.
  27. Spiess, H. , On optimal route choice strategies in transit networks. Publication 285, Centre de Recherche sur les Transports, Université de Montréal, 1983.
  28. Marguier, P. and A. Ceder, Passenger Waiting Strategies for Overlapping Bus Routes. Massachusetts Institute of Technology, Cambridge, Massachusetts, Transportation Science, 1984. 18(3): p. 207-230.
  29. Cea, J. D. and E. Fernandez, Transit assignment for congested public transport system: An equilibrium model. Transportation Science, 1993. 27(133–147).
  30. Lampkin, W. and P. D. Saalmans, The Design of Routes, Service Frequencies and Schedules for a Municipal Bus Undertaking: A Case Study. Operation Research Ouarterly, 1967. 18: p. 375-397.
  31. Holland, J. H. , Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, MI, 1975.
  32. Goldberg, D. E. , Genetic Algorithm in Search, Optimization and Machine Learning. Addison Wesley, Reading, MA, 1989.
  33. Baaj, M. H. and H. Mahmassani, An AI-Based Approach for Transit Route System Planning and Design. Journal of Advance Transportation, 1991. 25(2): p. 187-210.
  34. Zhao, F. and X. Zeng, Optimization of transit route network, vehicle headways and timetables for large-scale transit networks. European Journal of Operational Research, 2008. 186: p. 841–855.
  35. Nikolic, M. and D. Teodorovic, Transit network design by Bee Colony Optimization. Expert Systems with Applications, 2013. 40: p. 5945–5955.
Index Terms

Computer Science
Information Sciences

Keywords

Transportation transportation network design problem transit route design frequency setting direct demand coverage integer programming genetic algorithm.