Robust Optimization Model of Bus Transit Network Design with Stochastic Travel Time
Publication: Journal of Transportation Engineering
Volume 139, Issue 6
Abstract
The design of urban bus transit systems aims to determine a network configuration with a set of bus lines and associated frequencies that achieve the targeted objective. This paper presents a methodology framework to formulate and solve the bus transit network design problem (TNDP). It first proposes a TNDP taking into account the travel time stochasticity. A robust optimization model is formulated for the proposed problem, which aims to minimize the sum of the expected value of the operator cost and its variability multiplied by a weighting value. A heuristic solution approach, based on -shortest path algorithm, simulated annealing algorithm, Monte Carlo simulation, and probit-type discrete choice model, is subsequently developed to solve the robust optimization model. Finally, the proposed methodology is applied to a numerical example.
Get full access to this article
View all available purchase options and get full access to this article.
References
Abdel-Aty, M. A., Kitamura, R., and Jovanis, P. P. (1997). “Using stated preference data for studying the effect of advanced traffic information on drivers’ route choice.” Transp. Res. Part C Emerg. Technol., 5(1), 39–50.
Agrawal, J., and Mathew, T. V. (2004). “Transit route design using parallel genetic algorithm.” J. Comput. Civ. Eng., 18(3), 248–256.
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.
Baaj, M. H., and Mahmassani, H. S. (1995). “A hybrid route generation heuristic algorithm for the design of transit networks.” Transp. Res. Part C Emerg. Technol., 3(1), 31–50.
Bagloee, S. A., and Ceder, A. (2011). “Transit-network design methodology for actual-size road networks.” Transp. Res. Part B Methodol., 45(10), 1787–1804.
Bielli, M., Caramia, M., and Carottenuto, P. (2002). “Genetic algorithms in bus network optimization.” Transp. Res. Part C Emerg. Technol., 10(1), 19–34.
Bovy, P. H. L., and Fiorenzo-Catalano, S. (2007). “Stochastic route choice set generation: Behavioral and probabilistic foundations.” Transportmetrica, 3(3), 173–189.
Bovy, P. H. L., and Stern, E. (1990). Route choice: Wayfinding in transport networks, Vol. 9 (Studies in operational regional science series), Kluwer Academic Publishers, Dordrecht, Netherlands.
Carrese, S., and Gori, S. (2002). “An urban bus network design procedure.” Transportation planning: State of the art, M. Patriksson and M. Labbé, eds., Kluwer Academic Publishers, Dordrecht, Netherlands, 177–196.
Ceder, A. (2007). Public transit planning and operation: Theory, modeling and practice, Butterworth-Heinemann, Oxford, UK.
Ceder, A., and Wilson, N. H. M. (1986). “Bus network design.” Transp. Res. Part B Methodol., 20(4), 331–344.
Chakroborty, P., and Dwivedi, T. (2002). “Optimal route network design for transit systems using genetic algorithms.” Eng. Optim., 34(1), 83–100.
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. Technol., 20(1), 3–14.
Desaulniers, G., and Hickman, M. (2007). “Public transit.” Handb. Oper. Res. Manage. Sci., 14, 69–127.
Fan, W., and Machemehl, R. (2006). “Using a simulated annealing algorithm to solve the transit route network design problem.” J. Transp. Eng., 132(2), 122–132.
Furth, P., and Rahbee, A. (2000). “Optimal bus stop spacing through dynamic programming and geographic modeling.” Transp. Res. Rec., 1731, 15–22.
Gallo, M., Montella, B., and D’Acierno, L. (2011). “The transit network design problem with elastic demand and internalization of external costs: An application to rail frequency optimization.” Transp. Res. Part C Emerg. Technol., 19(6), 1276–1305.
Guan, J. F., Yang, H., and Wirasinghe, S. C. (2003). “Simultaneous optimization of transit line configuration and passenger line assignment.” Transp. Res. Part B Methodol., 40(10), 885–902.
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.
Han, A. F., and Wilson, N. H. M. (1982). “The allocation of buses in heavily utilized networks with overlapping routes.” Transp. Res. Part B Methodol., 16(3), 221–232.
Hasselström, D. (1981). “Public transportation planning: A mathematical programming approach.” Ph.D. dissertation, Göteborg Univ., Göteborg, Sweden.
Jackson, W. B., and Jucker, J. V. (1982). “An empirical study of travel time variability and travel choice behavior.” Transp. Sci., 16(4), 460–475.
Kepaptsoglou, K., and Karlaftis, M. (2009). “Transit route network design problem: Review.” J. Transp. Eng., 135(8), 491–505.
Kidwai, F. A. (1998). “Optimal design of bus transit network: A genetic algorithm based approach.” Ph.D. dissertation, Indian Institute of Technology, Kanpur, India.
Lam, W. H. K., Gao, Z. Y., and Chan, K. S. (1999). “A stochastic user equilibrium assignment model for congested transit networks.” Transp. Res. Part B Methodol., 33(5), 351–368.
Liu, Z. Y., and Meng, Q. (2012). “Distributed computing approaches for large-scale probit-based stochastic user equilibrium problem.” J. Adv. Transp., in press.
Magnanti, T. L., and Wong, R. T. (1984). “Network design and transportation planning: Models and algorithms.” Transp. Sci., 18(1), 1–55.
Mandl, C. E. (1980). “Evaluation and optimization of urban public transportation networks.” Eur. J. Oper. Res., 5(6), 396–404.
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.
Meng, Q., and Liu, Z. Y. (2011). “Trial-and-error method for congestion pricing scheme under side-constrained probit-based stochastic user equilibrium conditions.” Transportation, 38(5), 819–843.
Meng, Q., and Liu, Z. (2012a). “Mathematical models and computational algorithms for probit-based asymmetric stochastic user equilibrium problem with elastic demand.” Transportmetrica, 8(4), 261–290.
Meng, Q., and Liu, Z. Y. (2012b). “Impact analysis of cordon-based congestion pricing on mode-split for a bimodal transportation network.” Transp. Res. Part C Emerg. Technol., 21(1), 134–147.
Meng, Q., Liu, Z. Y., and Wang, S. A. (2012). “Optimal distance tolls under congestion pricing and continuously distributed value of time.” Transp. Res. Part E Logist. Transp. Rev., 48(5), 937–957.
Murray, A. T. (2003). “A coverage model for improving public transit system accessibility and expanding access.” Ann. Operat. Res., 123(1), 143–156.
Newell, G. F. (1979). “Some issues relating to the optimal design of bus routes.” Transp. Sci., 13(1), 20–35.
Nielsen, O. A. (2000). “A stochastic transit assignment model considering differences in passengers utility functions.” Transp. Res. Part B Methodol., 34(5), 377–402.
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.
Rapp, M. H., and Gehner, C. D. (1976). “Transfer optimization in an interactive graphic system for transit planning.” Transp. Res. Rec., (619), 27–33.
Sheffi, Y. (1985). Urban transportation networks: Equilibrium analysis with mathematical programming methods, Prentice Hall, Upper Saddle River, NJ.
Szeto, W. Y., and Wu, Y. (2011). “A simultaneous bus route design and frequency setting problem for Tin Shui Wai, Hong Kong.” Eur. J. Oper. Res., 209(2), 141–155.
Tom, V. M., and Mohan, S. (2003). “Transit route network design using frequency coded genetic algorithm.” J. Transp. Eng., 129(2), 186–195.
van Nes, R., Hamerslag, R., and Immers, B. H. (1988). “Design of public transport networks.” Transp. Res. Rec., (1202), 74–83.
Vuchic, V. R. (2005). Transit systems: Operations, planning and economics, 1st Ed., John Wiley & Sons, New York.
Xu, W. T., He, S. W., Song, R., and Sohail, S. C. (2012). “Finding the K shortest paths in a schedule-based transit network.” Comput. Oper. Res., 39(8), 1812–1826.
Yan, Y. D., Meng, Q., Wang, S., and Guo, X. C. (2012). “Robust optimization model of schedule design for a fixed bus route.” Transp. Res. Part C Emerg. Technol., 25, 113–121.
Yan, S. Y., and Tang, C.-H. (2008). “An integrated framework for intercity bus scheduling under stochastic bus travel times.” Transp. Sci., 42(3), 318–335.
Yang, L., and Lam, W. H. K. (2006). “Probit-type reliability-based transit network assignment.” Transp. Res. Rec., 1977, 154–163.
Yen, J. F. (1971). “Finding the K shortest loopless paths in a network.” Manage. Sci. 17(11), 712–716.
Zhao, F. (2006). “Large-scale transit network optimization by minimizing user cost and transfer.” J. Public Transp., 9(2), 107–129.
Zhao, F., and Zeng, X. (2007). “Optimization of user and operator cost for large scale transit networks.” J. Transp. Eng., 133(4), 240–251.
Information & Authors
Information
Published In
Journal of Transportation Engineering
Volume 139 • Issue 6 • June 2013
Pages: 625 - 634
Copyright
© 2013 American Society of Civil Engineers.
History
Received: Aug 14, 2012
Accepted: Jan 3, 2013
Published online: Jan 5, 2013
Published in print: Jun 1, 2013
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.