Routing Trains with Consideration of Congestion-Induced Link and Node Delay
Publication: Journal of Transportation Engineering
Volume 142, Issue 3
Abstract
North American heavy haul railroads are experiencing growth in traffic demand and increases in capacity constraints. An appropriate service-design process is thus crucial to allow for more effective network capacity planning and efficient rail operations. Existing approaches to freight train routing usually ignore the congestion-induced delay and fail to consider the dynamics in link and node delay in response to traffic volume. Furthermore, different train types can have substantially different operating characteristics, including maximum speed, power-to-ton ratio, and dispatching priority. This heterogeneity causes conflicts between trains that can increase delays and reduce capacity. Therefore, traffic volume and heterogeneity should both be incorporated into the decision process for service design. In this research, the authors proposed to add an additional traffic routing process in service design and developed a novel optimization framework to route trains by considering link and node delay, directional traffic, heterogeneity, and various delay costs according to train types. To improve the solution efficiency, a solution algorithm using Lagrangian relaxation (LR) techniques is also presented. Numerical results show that the optimal strategy has the potential to substantially reduce operational costs. Using this tool can help design better traffic routing, more efficient capacity utilization, and reliable services.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The authors thank the members of the National University Rail (NURail) Center for their collaborative technical insight.
References
AASHTO. (2007). “Transportation—Invest in our future: America’s freight challenge.” Washington, DC.
Abril, M., Barber, F., Ingolotti, L., Salido, M. A., Tormos, P., and Lova, A. (2008). “An assessment of railway capacity.” Transp. Res. Part E, 44(5), 774–806.
Ahuja, R. K., Cunha, C. B., and Sahin, G. (2005). “Network models in railroad planning and scheduling.” INFORMS Tutorials in operations research, 54–901.
Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. (1993). Network flows: Theory, algorithms, and applications, Prentice Hall, Englewood Cliffs, NJ.
Briggs, K., and Beck, C. (2007). “Modelling train delays with Q-exponential functions.” Phys. A, 378(2), 498–504.
Bronzini, M. S., and Clarke, D. B. (1985). “Estimating rail line capacity and delay by computer simulation.” Transp. Forum, 2(1), 5–11.
Carlyle, W. M., Royset, J. O., and Wood, R. K. (2008). “Lagrangian relaxation and enumeration for solving constrained shortest-path problems.” Networks, 52(4), 256–270.
Cordeau, J., Toth, P., and Vigo, D. (1998). “A survey of optimization models for train routing and scheduling.” Transp. Sci., 32(4), 380–404.
Crainic, T. G. (1984). “A comparison of two methods for tactical planning in rail freight transportation.” Proc., 10th Int. Conf. on Operation Research, Washington, DC.
Daskin, M. S. (1995). Network and discrete location: Models, algorithms and applications, Wiley, New York.
Day, J., Nemhauser, G. L., and Sokol, J. (2002). “Management of railroad impedances for shortest path-based routing.” Electr. Notes Theor. Comput. Sci., 66(6), 53–65.
Dingler, M. H., Lai, Y. C., and Barkan, C. P. L. (2009). “Impact of train type heterogeneity on single-track railway capacity.” Transp. Res. Rec., 2117, 41–49.
Dingler, M. H., Lai, Y. C., and Barkan, C. P. L. (2013). “ Mitigating train type heterogeneity on a single track line.” J. Rail Rapid Transit., 227(2), 140–147.
Dingler, M. H., Lai, Y. C., and Barkan, C. P. L. (2014). “Effect of train type heterogeneity on single-track heavy haul railway line capacity.” J. Rail Rapid Transit., 228(8), 845–856.
Fisher, M. L. (2004). “The Lagrangian relaxation method for solving integer programming problems.” Manage. Sci., 50(12), 1861–1871.
Freund, R. M. (2004). “Benders’ decomposition method for structured optimization, including stochastic optimization.” Massachusetts Institute of Technology, Cambridge, MA.
GAMS. (2009). A user’s guide, GAMS Development Corporation, Washington, DC.
Gorman, M. F. (2009). “Statistical estimation of railroad congestion delay.” Transp. Res. Part E, 45(3), 446–456.
Haghani, A. E. (1989). “Formulation and solution of a combined train routing and makeup, and empty car distribution model.” Transp. Res. Part B, 23(6), 433–452.
Harrod, S. (2009). “Capacity factors of a mixed speed railway network.” Transp. Res. Part E, 45(5), 830–841.
Huisman, T., and Boucherie, R. J. (2001). “Running times on railway sections with heterogeneous train traffic.” Transp. Res. Part B., 35(3), 271–292.
Imai, A., Nishimura, E., and Current, J. (2007). “A Lagrangian relaxation-based heuristic for the vehicle routing with full container load.” Eur. J. Oper. Res., 176(1), 87–105.
Jin, J. G., Zhao, J., and Lee, D. H. (2013). “A column generation based approach for the train network design optimization problem.” Transp. Res. Part E, 50, 1–17.
Keaton, M. H. (1989). “Designing optimal railroad operating plans: Lagrangian relaxation and heuristic approaches.” Transp. Res. Part B, 23(6), 415–431.
Keaton, M. H. (1992). “Designing railroad operating plans: A dual adjustment method for implementing Lagrangian relaxation.” Transp. Sci., 26(4), 263–279.
Kraft, E. R. (1983). “Analytical models for rail line capacity analysis.” J. Transp. Res.Forum, 24, 153–162.
Krueger, H. (1999). “Parametric modeling in rail capacity planning.” Proc., 31st Conf. on Winter simulation: Simulation—A Bridge to the Future, Vol. 2, ACM, New York, 1194–1200.
Kwon, O. K, Martland, C. D., and Sussman, J. M. (1998). “Routing and scheduling temporal and heterogeneous freight car traffic on rail networks.” Transp. Res. Part E, 34(2), 101–115.
Lai, Y. C., and Barkan, C. P. L. (2009). “Enhanced parametric railway capacity evaluation tool.” Transp. Res. Rec., 2117, 33–40.
Lai, Y. C., and Barkan, C. P. L. (2011). “Comprehensive decision support framework for strategic railway capacity planning.” J. Transp. Eng., 738–749.
Lai, Y. C., Dingler, M. H., Hsu, C. E., and Chiang, P. C. (2010). “Optimizing train network routing with heterogeneous traffic.” Transp. Res. Rec., 2159, 69–76.
Lai, Y. C., Huang, Y. A., and Chu, H. Y. (2014a). “Estimation of rail capacity using regression and neural network.” Neural Comput. Appl., 25(7), 2067–2077.
Lai, Y. C., Lin, Y. J., and Cheng, Y. F. (2014b). “Assessment of capacity charges for shared-use rail lines.” Transp. Res. Rec., 2448, 62–70.
Lai, Y. C., Liu, Y. H., and Lin, Y. J. (2015). “Standardization of capacity unit for headway-based rail capacity analysis.” Transp. Res. Part C, 57, 68–84.
Lai, Y. C., and Shih, M. C. (2013). “A stochastic multi-period investment selection model to optimize strategic railway capacity planning.” J. Adv. Transp., 47(3), 281–296.
Lai, Y. C., and Wang, S. H. (2012). “Development of analytical capacity models for conventional railways with advanced signaling systems.” J. Transp. Eng., 961–974.
Linder, T. (2011). “Applicability of the analytical UIC code 406 compression method for evaluating line and station capacity.” J. Rail Transp. Plann. Manage., 1(1), 49–57.
Magnanti, T. L., and Wong, R. T. (1984). “Network design and transportation planning: Models and algorithms.” Transp. Sci., 18(1), 1–55.
Minoux, M. (1989). “Network synthesis and optimum network design problems: Models, solution methods, and applications.” Networks, 19(3), 313–360.
Moniz, M., Silva, D., and Telhada, J. (2014). “Metaheuristic for the integrated approach to the freight train routing and block-to-train assignment.” Int. J. Transp., 2(1), 53–76.
Ouyang, Y., Li, X., Barkan, C. P. L., Kawprasert, A., and Lai, Y. C. (2009). “Optimal locations of railroad wayside defect detection installations.” Comput. Aided Civ. Infrastruct. Eng., 24(5), 309–319.
Sogin, S., Barken, C. P. L., and Saat, M. R. (2011). “Simulating the effects of higher speed passenger trains in single track freight networks.” Proc., 2011 Winter Simulation Conf., IEEE, New York, 3684–3692.
Warg, J. (2012). “Effects of increased traffic volume and speed heterogeneity on the capacity of a railway with dense mixed traffic.” WIT Trans. Built Environ., 127, 485–497.
Yaghini, M., and Akhavan, R. (2012). “Multicommodity network design problem in rail freight transportation planning.” Proc. Social Behav. Sci., 43, 728–739.
Yuan, J., and Hansen, I. A. (2007). “Optimizing capacity utilization of stations by estimating knock-on train delays.” Transp. Res. Part B, 41(2), 202–217.
Information & Authors
Information
Published In
Journal of Transportation Engineering
Volume 142 • Issue 3 • March 2016
Copyright
© 2015 American Society of Civil Engineers.
History
Received: Jun 10, 2014
Accepted: Oct 7, 2015
Published online: Dec 22, 2015
Published in print: Mar 1, 2016
Discussion open until: May 22, 2016
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.