Optimal Transit Route Network Design Problem with Variable Transit Demand: Genetic Algorithm Approach
Publication: Journal of Transportation Engineering
Volume 132, Issue 1
Abstract
This paper uses a genetic algorithm to systematically examine the underlying characteristics of the optimal bus transit route network design problem (BTRNDP) with variable transit demand. A multiobjective nonlinear mixed integer model is formulated for the BTRNDP. The proposed solution framework consists of three main components: an initial candidate route set generation procedure (ICRSGP) that generates all feasible routes incorporating practical bus transit industry guidelines; and a network analysis procedure (NAP) that decides transit demand matrix, assigns transit trips, determines service frequencies, and computes performance measures; and a genetic algorithm procedure (GAP) that combines these two parts, guides the candidate solution generation process, and selects an optimal set of routes from the huge solution space. A program code is developed to implement the proposed solution methodology for the BTRNDP with variable transit demand. An example network is successfully tested as a pilot study. Sensitivity analyses are performed. Comprehensive characteristics underlying the BTRNDP, including the effect of route set size, the effect of demand aggregation, and the redesign of the existing transit network issue, are also presented.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The writers want to express their deepest gratitude to two anonymous reviewers for their incisive and seasoned suggestions. The writers also appreciate the United States Department of Transportation, University Transportation Center through SWUTC to the Center for Transportation Research at The University of Texas at Austin for sponsoring this research by Project Nos. 167525 and 167824.
References
Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. (1993). Network flows: Theory, algorithms, and applications, Prentice-Hall, Englewood Cliffs, N.J.
Baaj, M. H., and Mahmassani, H. S. (1991). “An AI-based approach for transit route system planning and design.” J. Adv. Transp., 25(2), 187–210.
Bhat, C. (2003). “Discrete choice modeling.” Course notes, Univ. of Texas at Austin, Austin, Tex.
Bielli, M., Caramia, M., and Carotenuto, P. (2002). “Genetic algorithms in bus network optimization.” Transp. Res., Part C: Emerg. Technol., 10, 19–34.
Ceder, A., and Israeli, Y. (1998). “User and operator perspective in transit network design.” Proc., 77th Annual Transportation Research Board Meeting, Paper No. 980267, Transportation Research Board, Washington, D.C.
Ceder, A., and Wilson, N. H. M. (1986). “Bus network design.” Transp. Res., Part B: Methodol., 20B(4), 331–344.
Chakroborty, P. (2003). “Genetic algorithms for optimal urban transit network design.” Comput. Aided Civ. Infrastruct. Eng., 18, 184–200.
Chakroborty, P., and Dwivedi, T. (2002). “Optimal route network design for transit systems using genetic algorithms.” Eng. Optimiz., 34(1), 83–100.
Chang, S. K., and Schonfeld, P. (1991). “Multiple period optimization of bus transit systems.” Transp. Res., Part B: Methodol., 25B(6), 453–478.
Chang, S. K., and Schonfeld, P. (1993). “Welfare maximization with financial constraints for bus transit systems.” Transportation Research Record 1395, Transportation Research Board, Washington, D.C., 48–57.
Chien, S., and Schonfeld, P. (1997). “Optimization of grid transit system in heterogeneous urban environments.” J. Transp. Eng., 123(1), 28–35.
Chien, S., Yang, Z., and Hou, E. (2001). “A genetic algorithm approach for transit route planning and design.” J. Transp. Eng., 127(3), 200–207.
Dubois, D., Bell, G., and Llibre, M. (1979). “A set of methods in transportation network synthesis and analysis.” J. Oper. Res. Soc., 30, 797–808.
Fan, W. (2004). “Optimal transit route network design problem: Algorithms, implementations, and numerical results.” PhD dissertation, Univ. of Texas at Austin, Austin, Tex.
Fan, W., and Machemehl, R. B. (2004). “A genetic algorithm approach for the transit route network design problem.” Proc., 5th Transportation Specialty Conf., Canadian Society for Civil Engineers, Saskatoon, Sask., Canada.
Goldberg, D. E. (1989). Genetic algorithms in search, optimisation, and machine learning, Addison-Wesley, Reading, Mass.
Han, A. F., and Wilson, N. (1982). “The allocation of buses in heavily utilized networks with overlapping routes.” Transp. Res., Part B: Methodol., 16B, 221–232.
Holland, J. H. (1975). Adaptation in natural and artificial systems, University of Michigan Press, Ann Arbor, Mich.
Lampkin, W., and Saalmans, P. D. (1967). “The design of routes, service frequencies and schedules for a municipal bus undertaking: A case study.” Oper. Res. Q., 18, 375–397.
LeBlanc, L. J. (1988). “Transit system network design.” Transp. Res., Part B: Methodol., 22B(5), 383–390.
Lee, Y. J., and Vuchic, V. R. (2000). “Transit network design with variable demand,” Proc., 79th Annual Meeting of the Transportation Research Board, Transportation Research Board, Washington, D.C.
Michalewicz, Z. (1999). Genetic algorithms data structure=evolution programs, 3rd Ed., Springer, New York.
National Cooperative Highway Research Program (NCHRP). (1980). “Bus route and schedule planning guidelines.” National Cooperative Highway Research Program Synthesis of Highway Practice 69, Transportation Research Board, National Research Council, Washington, D.C.
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., 124(4), 368–375.
Rea, J. C. (1971). “Designing urban transit systems: An approach to the rout-technology selection problem.” PB 204881, Univ. of Washington, Seattle.
Shih, M., Mahmassani, H. S., and Baaj, M. (1998a). “Trip assignment model for timed-transfer transit systems.” Transportation Research Record 1571, Transportation Research Board, Washington, D.C., 24–30.
Shih, M. C., Mahmassani, H. S., and Baaj, M. H. (1998b). “A planning and design model for transit route networks with coordinated operations.” Proc., 77th Annual Meeting of the Transportation Research Board, Paper No. 980418, Transportation Research Board, Washington, D.C.
Silman, L. A., Barzily, Z., and Passy, U. (1974). “Planning the route system for urban buses.” Comput. Oper. Res., 1, 201–211.
Spasovic, L. N., Boilé, M. P., and Bladikas, A. K. (1994). “Bus transit service coverage for maximum profit and social welfare.” Transportation Research Record 1451, Transportation Research Board, Washington, D.C., 12–22.
Spasovic, L. N., and Schonfeld, P. (1993). “A method for optimizing transit service coverage.” Transportation Research Record 1402, Transportation Research Board, Washington, D.C., 28–39.
Van Nes, R., Hamerslag, R., and Immer, B. H. (1988). “The design of public transport networks.” Transportation Research Record 1202, Transportation Research Board, Washington, D.C., 74–83.
Yen, J. Y. (1971). “Finding the shortest loopless paths in a network.” Manage. Sci., 17(11), 712–716.
Information & Authors
Information
Published In
Journal of Transportation Engineering
Volume 132 • Issue 1 • January 2006
Pages: 40 - 51
Copyright
© 2006 ASCE.
History
Received: Mar 3, 2005
Accepted: May 18, 2005
Published online: Jan 1, 2006
Published in print: Jan 2006
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.