An optimization model for scheduling freight trains on a single-rail track

Document Type : Article


1 University of Central Florida, Orlando, Florida, USA

2 Institute of Management and Planning Studies, Tehran, Iran


In many countries, a rail network consists of a series of single lines with sidings where inter-train interactions (meeting, passing) occur. An effort has been made in this paper to study two of these
network-related issues: 1) scheduling freight trains in a single-line corridor while ensuring the interactions to happen safely and 2) allocating freight to the scheduled trains considering the freight due/release date and train’s weight/capacity. To better illustrate the real-world freight
trains’ scheduling problems, both the scheduling and allocation problems have been addressed. Minimizing the trains’ traveling time, allocating maximum freight to the scheduled ones, and minimizing the total freight tardiness at the related destination are the objective functions of
this study. Both problems and their solutions have been addressed separately using integer linear programming models, but an integrated novel heuristic algorithm has been proposed to solve them. The computational results demonstrated through a generated data set show both the model
validation and the efficiency of the heuristic algorithm. This heuristic algorithm has been so designed to incorporate the practical operational railway rules with modest modification and although its outputs slightly differ from the exact solutions, it can solve both models simultaneously
in large scale problems.



[1] Blazewicz, J., Ecker, K.H., Pesch, E., Schmidt, G., Sterna, M. and Weglarz, J. nScheduling in logistics”, InHandbook on Scheduling, pages 761–811. Springer, (2019).
[2] Assad, A.A. nModels for rail transportation”, Transportation Research Part A: General,14(3), pp. 205–220, (1980).
[3] Haghani, A.E. nRail freight transportation: a review of recent optimization models for train routing and empty car distribution”, Journal of Advanced Transportation, 21(2), pp. 147–172, (1987).
[4] Cordeau, J.F., Toth, P. and Vigo, D. nA survey of optimization models for train routing and scheduling”, Transportation science, 32(4), pp. 380–404, (1998).
[5] Lusby, R.M., Larsen, J., Ehrgott, M. and Ryan, D. nRailway track allocation: models and methods.OR spectrum, 33(4), pp. 843–883, (2011).
[6] Harrod, S. and Gorman, M.F. nOperations research for freight train routing and scheduling”, Wiley Encyclopedia of Operations Research and Management Science, (2010).
[7] Meisel, F. and Fagerholt, K. nScheduling two-way ship traffic for the Kiel canal: Model, extensions and a matheuristic”, Computers & Operations Research, 106, pp. 119–132, (2019).
[8] Pellegrini, P., Tollo, G.D. and Pesenti, R. nScheduling ships movements within a canal harbor”, Soft Computing, 23(9), pp. 2923–2936, (2019).
[9] Szpigel, B. nOptimal train scheduling on a single line railway, (1973).
[10] Higgins, A., Kozan, E. and Ferreira, L. nOptimal scheduling of trains on a single line track”, Transportation research part B: Methodological, 30(2), pp. 147–161, (1996).
[11] Talebian, A., Zou, B. and Peivandi, A. nCapacity allocation in vertically integrated rail systems: A bargaining approach”, Transportation Research Part B: Methodological, 107, pp. 167–191, (2018).
[12] Godwin, T., Gopalan, R. and Narendran, T. nFreight train routing and scheduling in a passenger rail network, pp. computational complexity and the stepwise dispatching heuristic”, Asia-Pacific Journal of Operational Research, 24(04), pp. 499–533, (2007).
[13] Xu, X., Li, K. and Yang, L. nScheduling heterogeneous train traffic on doubletracks with efficient dispatching rules”, Transportation Research Part B: Methodological,78, pp. 364–384, (2015).
[14] Mu, S. and Dessouky, M. nEfficient dispatching rules on double tracks with heterogeneous train traffic”, Transportation Research Part B: Methodological, 51, pp. 45–64, (2013).
[15] Fu, L. and Dessouky, M. nModels and algorithms for dynamic headway control”, Computers & Industrial Engineering, 103, pp. 271–281, (2017).
[16] Cacchiani, V., Caprara, A., and Toth, P. nScheduling extra freight trains on railway networks”, Transportation Research Part B: Methodological, 44(2), pp. 215–231, (2010).
[17] Zyngier, D., Lategan, J. and Furstenberg, L. nA process systems approach for detailed rail planning and scheduling applications”, Computers & Chemical Engineering,114, pp. 273–280, (2018).
[18] Murali, P., Ordonez, F. and Dessouky, M.M. nModeling strategies for effectively routing freight trains through complex networks”, Transportation Research Part C: Emerging Technologies, 70, pp. 197–213, (2016).
[19] Rahimi Mazrae Shahi, M., Fallah Mehdipour, E., and Amiri, M. nOptimization using simulation and response surface methodology with an application on subway train scheduling”, International Transactions in Operational Research, 23(4), pp. 797–811, (2016).
[20] Behiri, W., Belmokhtar-Berraf, S. and Chu, C. nUrban freight transport using passenger rail network: Scientific issues and quantitative analysis”, Transportation Research Part E: Logistics and Transportation Review, 115, pp. 227–245, (2018).
[21] Jaumard, B., Le, T.H., Tian, H., Akgunduz, A. and Finnie, P. nA dynamic row/column management algorithm for freight train scheduling”, In12th Work shop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Schloss Dagstuhl- Leibniz-Zentrum fuer Informatik, (2012).
[22] Rahman A. and Froyland, G. nFreight train scheduling on a single line corridor”, In AIP Conference Proceedings, volume 1613, pp. 159–168. AIP, (2014).
[23] Ke, B.R., Lin, C.L., Chien, H.H., Chiu, H.W. and Chen, N. nA new approach for improving the performance of freight train timetabling of a single-track railway system”, Transportation Planning and Technology, 38(2), pp. 238–264, (2015).
[24] Kuo, A., Miller-Hooks, E. and Mahmassani, H.S. nFreight train scheduling with elastic demand”, Transportation Research Part E: Logistics and Transportation Review,46(6), pp. 1057–1070, (2010).
[25] Sinha, S.K., Salsingikar, S. and SenGupta, S. nAn iterative bi-level hierarchical approach for train scheduling”, Journal of Rail Transport Planning & Management, 6(3), pp. 183–199, (2016).
[26] Xu, X., Li, K., Yang, L., and Gao, Z. nAn efficient train scheduling algorithm on a single-track railway system”, Journal of Scheduling, 22(1), pp. 85–105, (2019).
[27] Cai, X., Goh, C. and Mees, A. nGreedy heuristics for rapid scheduling of trains on a single track”, IIE transactions, 30(5), pp. 481–493, (1998).