Multiconstrained Timetable Optimization and Performance Evaluation in the Presence of Travel Time Noise
Publication: Journal of Transportation Engineering, Part A: Systems
Volume 144, Issue 9
Abstract
This work addresses the problem of bus timetabling under multiple operational constraints with the objective of minimizing the waiting time variations of passengers at stops. It places specific emphasis on practical operational constraints such as the required meal and resting time breaks, the required headway ranges between successive bus trips, and many others that are largely ignored in the literature but impose significant problems on timetable planners. Given the computational intractability of the multiconstrained timetabling problem, the authors introduce an exterior point penalty scheme for approximating the constrained optimization problem by an unconstrained one. In this way, it becomes easier to explore the effect of multiple timetabling options with the use of evolutionary optimization. The proposed approach is tested at a major Asia Pacific (APAC) bus operator, demonstrating that a favorable trade-off between improving the service reliability and satisfying most of the operational constraints can be achieved. Finally, additional extensive simulation tests demonstrate that optimized timetables perform well for travel time noise levels of less than 30%.
Get full access to this article
View all available purchase options and get full access to this article.
References
Adamski, A., and A. Turnau. 1998. “Simulation support tool for real-time dispatching control in public transport.” Transp. Res. Part A: Policy Pract. 32 (2): 73–87. https://doi.org/10.1016/S0965-8564(97)00019-0.
Bartholdi, J. J., and D. D. Eisenstein. 2012. “A self-coördinating bus route to resist bus bunching.” Transp. Res. Part B: Methodol. 46 (4): 481–491. https://doi.org/10.1016/j.trb.2011.11.001.
Bazaraa, M. S., H. D. Sherali, and C. M. Shetty. 2013. Nonlinear programming: Theory and algorithms. Hoboken, NJ: Wiley.
Berrebi, S. J., K. E. Watkins, and J. A. Laval. 2015. “A real-time bus dispatching policy to minimize passenger wait on a high frequency route.” Transp. Res. Part B: Methodol. 81: 377–389. https://doi.org/10.1016/j.trb.2015.05.012.
Bertini, R. L., and A. M. El-Geneidy. 2004. “Modeling transit trip time using archived bus dispatch system data.” J. Transp. Eng. 130 (1): 56–67. https://doi.org/10.1061/(ASCE)0733-947X(2004)130:1(56).
Bertsekas, D. P. 1990. Nonlinear programming. 2nd ed. Belmont, MA: Athena Scientific.
Ceder, A. 2007. “Public transit planning and operation: Theory.” In Modeling and practice. Oxford, UK: Elsevier.
Ceder, A., B. Golany, and O. Tal. 2001. “Creating bus timetables with maximal synchronization.” Transp. Res. Part A: Policy Pract. 35 (10): 913–928. https://doi.org/10.1016/S0965-8564(00)00032-X.
Ceder, A. A., S. Hassold, and B. Dano. 2013. “Approaching even-load and even-headway transit timetables using different bus sizes.” Public Transp. 5 (3): 193–217. https://doi.org/10.1007/s12469-013-0062-z.
Daganzo, C. F. 2009. “A headway-based approach to eliminate bus bunching: Systematic analysis and comparisons.” Transp. Res. Part B: Methodol. 43 (10): 913–921. https://doi.org/10.1016/j.trb.2009.04.002.
Delgado, F., J. C. Muñoz, R. Giesen, and A. Cipriano. 2009. “Real-time control of buses in a transit corridor based on vehicle olding and boarding limits.” Transp. Res. Rec. 2090: 59–67. https://doi.org/10.3141/2090-07.
Dessouky, M., R. Hall, L. Zhang, and A. Singh. 2003. “Real-time control of buses for schedule coordination at a terminal.” Transp. Res. Part A: Policy Pract. 37 (2): 145–164. https://doi.org/10.1016/S0965-8564(02)00010-1.
Eberlein, X. J., N. H. Wilson, and D. Bernstein. 2001. “The holding problem with real-time information available.” Transp. Sci. 35 (1): 1–18. https://doi.org/10.1287/trsc.35.1.1.10143.
Farahani, R. Z., E. Miandoabchi, W. Y. Szeto, and H. Rashidi. 2013. “A review of urban transportation network design problems.” Eur. J. Oper. Res. 229 (2): 281–302. https://doi.org/10.1016/j.ejor.2013.01.001.
Fiacco, A. V., and G. P. McCormick. 1968. Nonlinear programming: Sequential unconstrained minimization techniques. New York: Wiley.
Fu, L., and X. Yang. 2002. “Design and implementation of bus-holding control strategies with real-time information.” Transp. Res. Rec. 1791: 6–12. https://doi.org/10.3141/1791-02.
Furth, P. G., and N. H. Wilson. 1981. “Setting frequencies on bus routes: Theory and practice.” Transp. Res. Rec. 818: 1–7.
Gallo, G., and F. D. Miele. 2001. “Dispatching buses in parking depots.” Transp. Sci. 35 (3): 322–330. https://doi.org/10.1287/trsc.35.3.322.10151.
Gkiotsalitis, K. 2018. “Rolling-horizon optimization of the bus holding problem with sequential hill climbing.” In Proc., Transportation Research Board 97th Annual Meeting. Washington, DC: Transportation Research Board.
Gkiotsalitis, K., and O. Cats. 2017. “Exact optimization of bus frequency settings considering demand and trip time variations.” In Proc., Transportation Research Board 96th Annual Meeting. Washington, DC: Transportation Research Board.
Gkiotsalitis, K., and O. Cats. 2018. “Reliable frequency determination: Incorporating information on service uncertainty when setting dispatching headways.” Transp. Res. Part C: Emerg. Technol. 88: 187–207. https://doi.org/10.1016/j.trc.2018.01.026.
Gkiotsalitis, K., and N. Maslekar. 2015. “Improving bus service reliability with stochastic optimization.” In Proc., 2015 IEEE 18th Int. Conf. on Intelligent Transportation Systems, 2794–2799. Las Palmas, Spain: IEEE.
Gkiotsalitis, K., and N. Maslekar. 2017. “Sequential evolutionary optimization for improving regularity-based bus services.” In Proc., 96th Annual Meeting of the Transportation Research Board. Washington, DC: Transportation Research Board.
Gkiotsalitis, K., and A. Stathopoulos. 2016. “Joint leisure travel optimization with user-generated data via perceived utility maximization.” Transp. Res. Part C: Emerg. Technol. 68: 532–548. https://doi.org/10.1016/j.trc.2016.05.009.
Hickman, M. D. 2001. “An analytic stochastic model for the transit vehicle holding problem.” Transp. Sci. 35 (3): 215–237. https://doi.org/10.1287/trsc.35.3.215.10150.
Ibarra-Rojas, O. J., and Y. A. Rios-Solis. 2012. “Synchronization of bus timetabling.” Transp. Res. Part B: Methodol. 46 (5): 599–614. https://doi.org/10.1016/j.trb.2012.01.006.
Karmarkar, N. 1984. “A new polynomial-time algorithm for linear programming.” In Proc., 16th Annual ACM Symp. on Theory of Computing, 302–311. New York: ACM.
Kepaptsoglou, K., and M. Karlaftis. 2009. “Transit route network design problem: Review.” J. Transp. Eng. 135 (8): 491–505. https://doi.org/10.1061/(ASCE)0733-947X(2009)135:8(491).
Kittelson & Associates, Parsons Brinckerhoff, KFH Group, Texas A&M Transportation Institute and Arup. 2013. Transit capacity and quality of service manual. Washington, DC: Transportation Research Board.
Knoppers, P., and T. Muller. 1995. “Optimized transfer opportunities in public transport.” Transp. Sci. 29 (1): 101–105. https://doi.org/10.1287/trsc.29.1.101.
Kraft, W. H., and T. F. Bergen. 1974. “Evaluation of passenger service times for street transit systems.” In Proc., 53rd Annual Meeting of the Highway Research Board. Washington, DC: Transportation Research Board.
Osuna, E., and G. Newell. 1972. “Control strategies for an idealized public transportation system.” Transp. Sci. 6 (1): 52–72. https://doi.org/10.1287/trsc.6.1.52.
Peeters, L., and L. Kroon. 2001. “A cycle based optimization model for the cyclic railway timetabling problem.” In Computer-aided scheduling of public transport, 275–296. Berlin: Springer.
Storn, R., and K. Price. 1997. “Differential evolution—A simple and efficient heuristic for global optimization over continuous spaces.” J. Global Optim. 11 (4): 341–359. https://doi.org/10.1023/A:1008202821328.
Strathman, J. G., T. J. Kimpel, K. J. Dueker, R. L. Gerhart, and S. Callas. 2002. “Evaluation of transit operations: Data applications of Tri-Met’s automated Bus Dispatching System.” Transportation 29 (3): 321–345. https://doi.org/10.1023/A:1015633408953.
Sun, A., and M. Hickman. 2005. “The real-time stop-skipping problem.” J. Intell. Transp. Syst. 9 (2): 91–109. https://doi.org/10.1080/15472450590934642.
Sun, D. J., Y. Xu, and Z.-R. Peng. 2015. “Timetable optimization for single bus line based on hybrid vehicle size model.” J. Traffic Transp. Eng. 2 (3): 179–186. https://doi.org/10.1016/j.jtte.2015.03.006.
Xuan, Y., J. Argote, and C. F. Daganzo. 2011. “Dynamic bus holding strategies for schedule reliability: Optimal linear control and performance analysis.” Transp. Res. Part B: Methodol. 45 (10): 1831–1845. https://doi.org/10.1016/j.trb.2011.07.009.
Zhao, J., S. Bukkapatnam, and M. M. Dessouky. 2003. “Distributed architecture for real-time coordination of bus holding in transit networks.” IEEE Trans. Intell. Transp. Syst. 4 (1): 43–51. https://doi.org/10.1109/TITS.2003.809769.
Zhao, J., M. Dessouky, and S. Bukkapatnam. 2006. “Optimal slack time for schedule-based transit operations.” Transp. Sci. 40 (4): 529–539. https://doi.org/10.1287/trsc.1060.0170.
Information & Authors
Information
Published In
Journal of Transportation Engineering, Part A: Systems
Volume 144 • Issue 9 • September 2018
Copyright
©2018 American Society of Civil Engineers.
History
Received: Oct 18, 2017
Accepted: Apr 20, 2018
Published online: Jul 13, 2018
Published in print: Sep 1, 2018
Discussion open until: Dec 13, 2018
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.