Using a Simulated Annealing Algorithm to Solve the Transit Route Network Design Problem
Publication: Journal of Transportation Engineering
Volume 132, Issue 2
Abstract
This paper uses a simulated annealing algorithm to solve the optimal bus transit route network design problem (BTRNDP) at the distribution node level. 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 that generates all feasible routes incorporating practical bus transit industry guidelines; and a network analysis procedure that assigns transit trips, determines service frequencies, and computes performance measures; and a simulated annealing procedure that combines these two parts, guides the candidate solution generation process and selects an optimal set of routes from the huge solution space. Three experimental networks are successfully tested as a pilot study. A genetic algorithm is also used as a benchmark to measure the quality of the simulated annealing algorithm. The presented numerical results clearly indicate that the simulated annealing outperforms the genetic algorithm in most cases using the example networks. Sensitivity analyses are performed and related characteristics and tradeoffs underlying the BTRNDP are also discussed.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The writers appreciate the U.S. Department of Transportation, University Transportation Center through SWUTC to the Center for Transportation Research, The University of Texas at Austin for sponsoring this research through Project Nos. 167525 and 167824. They also want to thank two anonymous reviewers for their incisive and seasoned suggestions.
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.
Ceder, A., and Israeli, Y. (1998). “User and operator perspective in transit network design.” Paper No. 980267, Proc., 77th Annual Meeting of TRB, Transportation Research Board, Washington, D.C.
Ceder, A., and Wilson, N. H. M. (1986). “Bus network design.” Transp. Res., Part B: Methodol., 20(4), 331–344.
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.
Eglese, R. W. (1990). “Simulated annealing: A tool for operational research.” Eur. J. Oper. Res., 46, 271–281.
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., CSCE 2004, 5th Transportation Specialty Conf. Canadian Society for Civil Engineering, Saskatoon, Sask., Canada.
Han, A. F., and Wilson N. (1982). “The allocation of buses in heavily utilized networks with overlapping routes.” Transp. Res., Part B: Methodol., 16, 221–232.
Hasselstrom, D. (1981). “Public transportation planning—A mathematical programming approach.” PhD thesis, Dept. of Business Administration, Univ. of Gothenburg, Gothenburg, Sweden.
Koulamas, C., Antony, S. R., and Jaen, R. (1994). “A survey of simulated annealing applications to operations research problems.” Omega, 22(1), 41–56.
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.
National Cooperative Highway Research Program (NCHRP). (1980). “Bus route and schedule planning guidelines.” 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 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.” Rep. PB204881, Univ. of Washington, Seattle, Wash.
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 TRB, 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.
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 2 • February 2006
Pages: 122 - 132
Copyright
© 2006 ASCE.
History
Received: Feb 8, 2005
Accepted: Jul 5, 2005
Published online: Feb 1, 2006
Published in print: Feb 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.