Robust model and solution algorithm for the railroad blocking problem under uncertainty

Document Type : Article

Authors

1 Department of Civil Engineering, Sharif University of Technology, Azadi Avenue, P.O. Box 11155 - 8639, Tehran, Iran

2 Department of Civil Engineering, Sharif University of Technology, Azadi Ave., P.O.Box: 11155-9313, Tehran, Iran

Abstract

The railroad blocking problem emerges as an important issue at the tactical level of planning in freight rail transportation. This problem consists of determining the optimal paths for freight cars in a rail network. Often, demand and supply resource indicators are assumed to be certain, so the solution obtained from a certain model might not be optimal or even feasible in practice because of the stochastic nature of these parameters. To address this issue, this paper develops a robust model for this problem with uncertain demand and uncertain travel time as supply resource indicators. Since the model combines integer variables and nonlinear functions, a branch-and-cut algorithm is used to solve the linearized version of the robust model. The performance of the proposed algorithm in several instances is discussed. A comparison with a well-known solver shows the high efficiency and effectiveness of the proposed algorithm. Finally, this algorithm is applied to a blocking problem of the railways of Iran. The results show that, by ignoring approximately 10% of the optimal value of the deterministic model, we have an optimal solution that remains unchanged with a probability of more than 0.98.

Keywords

Main Subjects

References

References

1. Crainic, T.G. and Laporte, G. Planning models for freight transportation", Eur. J. Oper. Res., 97, pp.
409-438 (1997).
2. Crainic, T.G. Service network design in freight transportation",
Eur. J. Oper. Res., 122, pp. 272-288
(2000).
3. Assad, A.A. Modelling of rail networks: Toward a
routing/makeup model", Transport Res. B-Meth, 14,
pp. 101-114 (1980).
4. Fugenschuh, A., Homfeld, H., and Schulldorf, H.
Single-car routing in rail freight transport", Transport
Sci., 49, pp. 130-148 (2013).
5. Barnhart, C., Jin, H., and Vance, P.H. RailRoad
blocking: A network design application", Oper. Res.,
48, pp. 603-614 (2000).
6. Bontekoning, Y. and Priemus, H. Breakthrough innovations
in intermodal freight transport", Transport
Plan Techn., 27, pp. 335-345 (2004).
7. Bodin, L.D., Golden, B.L., Schuster, A.D., and
William, R. A model for the blocking of trains",
Transport Res B-Meth, 14, pp. 115-150 (1980).
8. Marn, A. and Salmeron, J. Tactical design of rail
freight networks. Part I:Exact and heuristic methods",
Eur. J. Oper. Res., pp. 26-44 (1996).
9. Lin, B.-L., Wang, Z.-M., Ji, L.-J., Tian, Y.-M., and
Zhou, G.-Q. Optimizing the freight train connection
service network of a large-scale rail system", Transportation
Research Part B: Methodological, 46, pp.
649-667 (2012).
10. Newton, H.N., Barnhart, C., and Vance, P.H. Constructing
railroad blocking plans to minimize handling
costs", Transport Sci., 32, pp. 330-345 (1998).
11. Keaton, M.H. Designing optimal railroad operating
plans: Lagrangian relaxation and heuristic approaches",
Transportation Research: Part B, 23, pp.
415-431 (1989).
12. Hasany, R.M., Shafahi, Y., and Kazemi, S.F. A comprehensive
formulation for railroad blocking problem",
ECMS, pp. 758-763 (2013).
13. Ahuja, R.K., Jha, K.C., and Liu, J. Solving real-life
railroad blocking problems", Interfaces, 37, pp. 404-
419 (2007).
14. Martinelli, D.R. and Teng, H. Optimization of railway
operations using neural networks", Transport Res CEmer,
4, pp. 33-49 (1996).
15. Yaghini, M., Momeni, M., Sarmadi, M., Seyedabadi,
M., and Khoshraftar, M.M. A fuzzy railroad blocking
model with genetic algorithm solution approach for
Iranian railways", Appl. Math. Model, 20, pp. (2015).
16. Yue, Y., Zhou, L., Yue, Q., and Fan, Z. Multi-route
railroad blocking problem by improved model and ant
colony algorithm in real world", Comput. Ind. Eng.,
60, pp. 34-42 (2011).
1928 R. M. Hasany and Y. Shafahi/Scientia Iranica, Transactions A: Civil Engineering 25 (2018) 1916{1930
17. Yaghini, M., Ahadi, H.R., Barati, E., and Saghian,
Z. Tabu search algorithm for the railroad blocking
problem", J. Transp. Eng.-ASCE, 139, pp. 216-222
(2012).
18. Ahuja, R.K., Cunha, C.B., and Sahin, G. Network
models in railroad planning and scheduling", Tut.
Oper. Res., 1, pp. 54-101 (2005).
19. Voll, R. and Clausen, U. Branch-and-price for a
European variant of the railroad blocking problem",
Electronic Notes in Discrete Mathematics, 41, pp. 45-
52 (2013).
20. Yaghini, M., Rahbar, M., Karimi, M., and
Khoshkroudian, M. A branch-and-price algorithm for
solving the railroad blocking problem", International
Journal of Engineering Science (2008-4870), 25, pp.
99-108 (2014).
21. Yang, L., Gao, Z., and Li, K. Railway freight
transportation planning with mixed uncertainty of
randomness and fuzziness", Appl. Soft Comp., 11, pp.
778-792 (2011).
22. Gao, Y., Yang, L., and Li, S. Uncertain models
on railway transportation planning problem", Appl.
Math. Model, 40, pp. 4921-4934 (2016).
23. Meng, Q., Hei, X., Wang, S., and Mao, H. Carrying
capacity procurement of rail and shipping services for
automobile delivery with uncertain demand", Transport
Res. E-Log, 82, pp. 38-54 (2015).
24. Milenkovic, M.S., Bojovic, N.J., Svadlenka, L., and
Melichar, V. A stochastic model predictive control
to heterogeneous rail freight car
eet sizing problem",
Transport Res. E-Log, 82, pp. 162-198 (2015).
25. Jin, H., Designing Robust Railraod Blocking Plans,
Massachusetts Institute od Technology (1998).
26. Ben-Tal, A. and Nemirovski, A. Robust solutions
of Linear Programming problems contaminated with
uncertain data", Math. Prog., 88, pp. 411-424 (2000).
27. Prekopa, A., Stochastic Programming, Springer Science
& Business Media (2013).
28. Wong, W.G., Niu, H., and Ferreira, L. A fuzzy
method for predicting the demand for rail freight
transportation", J. Adv. Transport, 37, pp. 159-171
(2003).
29. Carvalho, G., Methodology for Railway Demand Forecasting
Using Data Mining, SAS Global Forum (2007).
30. Gorman, M.F. Statistical estimation of railroad congestion
delay", Transport Res. E-Log, 45, pp. 446-456
(2009).
31. Matas, A., Raymond, J.L., Gonzalez-Savignat, M.,
and Ruiz, A. Predicting the demand: Uncertainty
analysis and prediction models in Spain", Working
Paper in Economic Evaluation of Transportation
Projects, pp. 1-31 (2009).
32. Dong, Y. Modeling rail freight operations under
di erent operating strategies", PhD Thesis, MIT,
Cambridge, MA (1997).
33. Birge, J.R. and Louveaux, F., Introduction to Stochastic
Programming, Springer (2011).
34. Soyster, A.L. Convex programming with set-inclusive
constraints and applications to inexact linear programming",
Oper. Res., 21, pp. 1154-1157 (1973).
35. Ben-Tal, A. and Nemirovski, A. Robust convex optimization",
Mathematics of Operations Research, 23,
pp. 769-805 (1998).
36. Seref, O., Ahuja, R.K., and Orlin, J.B. Incremental
network optimization: Theory and algorithms", Oper.
Res., 57, pp. 586-594 (2009).
37. Han, J., Lee, C., and Park, S. A robust scenario approach
for the vehicle routing problem with uncertain
travel times", Transport Sci., 48, pp. 373-390 (2013).
38. Smith, J.C., Ahmed, S., Cochran, J.J., Cox, L.A., Keskinocak,
P., Kharoufeh, J.P., and Smith, J.C. Introduction
to robust optimization", Wiley Encyclopedia of
Operations Research and Management Science, John
Wiley & Sons, Inc. (2010).
39. Nemhauser, G.L. and Wolsey, L.A. Integer programming
and combinatorial optimization", W., Chichester,
G.L. Nemhauser, M.W.P. Savelsbergh, and G.S.
Sigismondi, Constraint Classi cation for Mixed Integer
Programming Formulations, COAL Bulletin, 20, pp.
8-12 (1988).
40. Lee, J. and Ley er, S., Mixed Integer Nonlinear Programming,
Springer Science & Business Media (2011).
41. ILOG, CPLEX OPTIMIZATION, INC. 2009. Using
the CPLEX Linear Optimizer.
42. Van Essen, H., Boon, B., den Boer, L., Faber, J.,
van den Bossche, M., Vervoort, K., and Rochez, C.,
Marginal Costs of Infrastructure Use - Towards a
Simpli ed Approach, Delft (2003).
43. Bertsimas, D. and Sim, M. Robust discrete optimization
and network
ows", Math. Prog., 98, pp. 49-71
(2003).
44. Ben-Tal, A., El Ghaoui, L., and Nemirovski, A., Robust
Optimization, Princeton University Press, New Jersey
(2009).

Scientia Iranica
Volume 25, Issue 4 - Serial Number 4
Transactions on Civil Engineering (A)
July and August 2018
Pages 1916-1930

Files

Share

How to cite

Statistics