Optimal Modification of Urban Bus Network Routes Using a Genetic Algorithm
Publication: Journal of Transportation Engineering
Volume 141, Issue 3
Abstract
The bus network design problem refers to a determination of optimizing the network of bus routes, usually in urban areas. The optimal routes must comply with a given passenger demand matrix and attain a compromise best solution from the user, the operator, and the community. This paper proposes the use of a genetic algorithm as a tool to handle the complexity of the bus network design problem. The methodology developed considers a mechanism to maintain as many satisfactory routes of the existing network as possible and, at the same time, to incorporate experience-based suggestions, such as minimizing of the number of transfers required by a passenger, into the revised bus network. The solution method, using genetic algorithm, has four steps: (1) generating a set of potential routes, (2) designing the bus network, (3) checking the routes for implementation, and (4) examining the extension of routes for improvement. The proposed method is validated through a benchmark bus network and a case study. The result of the case study, with a bus network serving a city with a population of 3.2 million, shows an improvement of 26.36% in the objective function value over the existing bus network. This improvement was realized by modifying only 36% of the routes while the remaining 74% of the existing network remained intact.
Get full access to this article
View all available purchase options and get full access to this article.
References
Agrawal, J., and Mathew, T. (2004). “Transit route network design using a parallel genetic algorithm.” J. Comput. Civ. Eng., 248–256.
Amiripour, S. M. M., Ceder, A., and Shariat Mohaymany, A. (2012). “Bus-network design considering high seasonal demand variations.” Proc., 91st Transportation Research Board Annual Meeting (CD-Rom), Transportation Research Board, Washington, DC.
Amiripour, S. M. M., Ceder, A., and Shariat Mohaymany, A. (2014). “Hybrid method for bus network design with high seasonal demand variation.” J. Transp. Eng., 04014015.
Baaj, M. H., and Mahmassani, H. S. (1991). “AI-based approach for transit route system planning and design.” J. Adv. Transp., 25(2), 187–209.
Baaj, M. H., and Mahmassani, H. S. (1995). “Hybrid route generation heuristic algorithm for the design of transit networks.” Transp. Res. Part C Emerg., 3(1), 31–50.
Bagloee, A. S., and Ceder, A. (2011). “Transit-network design methodology for actual-size road networks.” Transp. Res. Part B Method., 45(10), 1787–1804.
Bielli, M., Caramia, M., and Carotenuto, P. (2002). “Genetic algorithms in bus network optimization.” Transp. Res. Part C Emerg., 10(1), 19–34.
Black, A. (1978). “Optimizing urban mass transit systems: A general model.”, Transportation Research Board, Washington, DC, 41–47.
Byrne, B. F. (1975). “Public transportation line positions and headways for minimum user and system cost in a radial case.” Transp. Res., 9(2–3), 97–102.
Byrne, B. F. (1976). “Cost minimizing positions, lengths and headways for parallel public transit lines having different speeds.” Transp. Res., 10(3), 209–214.
Byrne, B. F., and Vuchic, V. R. (1972). “Public transportation line positions and headways for minimum cost.” Traffic flow and transportation, F. G. Newell, ed., Elsevier, New York, 347–360.
Ceder, A. (2007). Public transit planning and operation: Theory, modeling and practice, Elsevier, Oxford, U.K.
Ceder, A., and Wilson, N. H. M. (1986). “Bus network design.” Transp. Res., Part B Method., 20(4), 331–344.
Chakroborty, P. (2003). “Genetic algorithms for optimal urban transit network design.” Comput. Aided Civ. Infrastruct. Eng., 18(3), 184–200.
Chakroborty, P., and Dwivedi, T. (2002). “Optimal route network design for transit systems using genetic algorithms.” Eng. Optim., 34(1), 83–100.
Chang, S. K., and Schonfeld, P. M. (1991). “Multiple period optimization of bus transit systems.” Transp. Res., Part B Method., 25(6), 453–478.
Chua, T. A. (1984). “The planning of urban bus routes and frequencies: A survey.” Transportation, 12(2), 147–172.
Cipriani, E., Gori, S., and Petrelli, M. (2012). “Transit network design: A procedure and an application to a large urban area.” Transp. Res., Part C Emerg., 20(1), 3–14.
Fan, W., and Machemehl, R. B. (2006a). “Optimal transit route network design problem with variable transit demand: Genetic algorithm approach.” J. Transp. Eng., 40–51.
Fan, W., and Machemehl, R. B. (2006b). “Using a simulated annealing algorithm to solve the transit route network design problem.” J. Transp. Eng., 122–132.
Guihaire, V., and Hao, J. K. (2008). “Transit network design and scheduling: A global review.” Transp. Res. Part A Policy Pract., 42(10), 1251–1273.
Holroyd, E. M. (1967). “The optimal bus service: A theoretical model for a large uniform urban area.” Vehicular traffic science, L. C. Edie, ed., Elsevier, New York, 308–328.
Hu, J., Shi, X., Song, J., and Xu, Y. (2005). “Optimal design for urban mass transit network based on evolutionary algorithms.” Lecture notes in computer science 3611, L. Wang, K. Chen, and Y. S. Ong, eds., Springer, Berlin.
Kepaptsoglou, K., and Karlaftis, M. (2009). “Transit route network design problem: Review.” J. Transp. Eng., 491–505.
Kocur, G., and Hendrickson, C. (1982). “Design of local bus service with demand equilibrium.” Transp. Sci. 16(2), 149–170.
Lee, Y. J., and Vuchic, V. R. (2005). “Transit network design with variable demand.” J. Transp. Eng., 1–10.
Mandl, C. E. (1979). Applied network optimization, Academic Press, London.
Mauttone, A., and Urquhart, M. E. (2009). “A route set construction algorithm for the transit network design problem.” Comput. Oper. Res., 36(8), 2440–2449.
Morlok, E. K., and Viton, P. A. (1984). “Feasibility of profitable transit service in radial urban corridors.”, Transportation Research Board, Washington, DC, 46–54.
Newell, G. F. (1979). “Some issues relating to the optimal design of bus routes.” Transp. Sci., 13(1), 20–35.
Pattnaik, S. B., Mohan, S., and Tom, V. M. (1998). “Urban bus transit route network design using genetic algorithm.” J. Transp. Eng., 368–375.
Patz, A. (1925). “The correct selection of traffic lines with large streetcar networks.” Verkehrstechnik 50/51 (in German).
Petrelli, M. (2004). “A transit network design model for urban areas.” Urban transport X, C. A. Brebbia and L. C. Wadhwa, eds., Wessex Institute of Technology (WIT), Southampton, U.K., 63–172.
Poorzahedy, H., and Safari, F. (2011). “An ant system application to the bus network design problem: An algorithm and a case study.” Publ. Transp., 3(2), 165–187.
Russo, F. (1998). “Transit frequencies design for enhancing the efficiency of public urban transportation systems: An optimization model and an algorithm.” Proc., 31st Int. Symp. on Automotive Technology and Automation, Dusseldorf, Germany.
Shih, M., and Mahmassani, H. S. (1994). “A design methodology for bus transit networks for coordinated operations.”, Center for Transportation, Bureau of Engineering Research, Univ. of Texas at Austin, Austin, TX.
Shimamoto, H., Schmöker, J. D., and Kurauchi, F. (2012). “Optimization of a bus network configuration considering the common lines problem.” Proc., 91st Transportation Research Board Annual Meeting (CD-Rom), Transportation Research Board, Washington, DC.
Spasovic, L., and Schonfeld, P. (1997). “Method for optimizing transit service coverage.”, Transportation Research Board, Washington, DC, 28–39.
Spasovic, L. N., Boile, M. P., and Bladikas, A. K. (1994). “Bus transit service coverage for maximum profit and social welfare.”, Transportation Research Board, Washington, DC, 12–22.
Tom, V., and Mohan, S. (2003). “Transit route network design using a frequency coded genetic algorithm.” J. Transp. Eng., 186–195.
Vaughan, R. (1986). “Optimum polar networks for an urban bus system with a many-to-many travel demand.” Transp. Res., Part B Methodol., 20(3), 215–224.
Vuchic, V. (2007). Urban transit systems and technology: Systems and technology, Wiley, Hoboken, NJ.
Yang, Z., Yu, B., and Cheng, C. (2007). “A parallel ant colony algorithm for bus network optimization.” Comput. Aided Civ. Infrastruct. Eng., 22(1), 44–55.
Zhao, F., and Gan, A. (2003). “Optimization of transit network to minimize transfers.” Final Rep., Lehman Center for Transportation Research, Florida International Univ., Miami, FL.
Zhao, F., and Zeng, X. (2006). “Simulated annealing-genetic algorithm for transit network optimization.” J. Comput. Civ. Eng., 57–68.
Information & Authors
Information
Published In
Journal of Transportation Engineering
Volume 141 • Issue 3 • March 2015
Copyright
© 2014 American Society of Civil Engineers.
History
Received: Apr 12, 2014
Accepted: Aug 27, 2014
Published online: Oct 6, 2014
Published in print: Mar 1, 2015
Discussion open until: Mar 6, 2015
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.