Modeling formulation and a new heuristic for the railroad blocking problem. (English) Zbl 1480.90050
Summary: The railroad blocking problem is an important issue at the tactical level of railroad freight transportation. This problem consists of determining paths between the origins and destinations of each shipment to minimize the operating and user costs while satisfying the railroad supply and demand restrictions. A mixed-integer program (MIP) is developed to find the optimal paths, and a new heuristic is developed to solve the proposed model. This heuristic decomposes the model into two sub-problems of manageable size and then provides feasible solutions. We discuss the performance of the proposed heuristic for a set of instances with up to 90 stations. A comparison with the CPLEX MIP solver shows that the heuristic gives the exact solution for 10 out of 15 instances. For the remaining instances, the heuristic obtained solutions within a tolerance of 0.03–0.84%. Furthermore, compared with the CPLEX MIP solver, the heuristic reduced the run time by an average of 85% for all 15 instances. Finally, we present the computational results of the heuristic applied to Iranian railroads.
MSC:
| 90B06 | Transportation, logistics and supply chain management |
| 90C11 | Mixed integer programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Software:
CPLEXReferences:
| [1] | Jin, H., Designing Robust Railraod Blocking Plans (1998), Massachusetts Institute of Technology |
| [2] | Assad, A. A., Modelling of rail networks: toward a routing/makeup model, Transp. Res. B - Methodol., 14, 101-114 (1980) |
| [3] | Bodin, L. D.; Golden, B. L.; Schuster, A. D.; Romig, W., A model for the blocking of trains, Transp. Res. Part B: Methodol., 14, 115-120 (1980) |
| [4] | Keaton, M. H., Designing optimal railroad operating plans: Lagrangian relaxation and heuristic approaches, Transp. Res.: Part B, 23, 415-431 (1989) |
| [5] | Marin, A.; Salmerón, J., Tactical design of rail freight networks. Part I: exact and heuristic methods, Eur. J. Oper. Res., 90, 26-44 (1996) · Zbl 0916.90096 |
| [6] | Ahuja, R. K.; Cunha, C. B.; Sahin, G., Network models in railroad planning and scheduling, Tutor. Oper. Res., 1, 54-101 (2005) |
| [7] | Fügenschuh, A.; Homfeld, H.; Schülldorf, H., Single-car routing in rail freight transport, Transp. Sci., 49, 130-148 (2015) |
| [8] | Newton, H. N.; Barnhart, C.; Vance, P. H., Constructing railroad blocking plans to minimize handling costs, Transp. Sci., 32, 330-345 (1998) · Zbl 0987.90510 |
| [9] | Yaghini, M.; Momeni, M.; Sarmadi, M.; Seyedabadi, M.; Khoshraftar, M. M., A fuzzy railroad blocking model with genetic algorithm solution approach for Iranian railways, Appl. Math. Model., 39 (2015) · Zbl 1443.90080 |
| [10] | Martinelli, D. R.; Teng, H., Optimization of railway operations using neural networks, Transp. Res C - Emerg. Technol., 4, 33-49 (1996) |
| [11] | Lin, B.-L.; Wang, Z.-M.; Ji, L.-J.; Tian, Y.-M.; Zhou, G.-Q., Optimizing the freight train connection service network of a large-scale rail system, Transp. Res. Part B: Methodol., 46, 649-667 (2012) |
| [12] | Yaghini, M.; Foroughi, A.; Nadjari, B., Solving railroad blocking problem using ant colony optimization algorithm, Appl. Math. Model., 35, 5579-5591 (2011) · Zbl 1228.90014 |
| [13] | Yue, Y.; Zhou, L.; Yue, Q.; Fan, Z., Multi-route railroad blocking problem by improved model and ant colony algorithm in real world, Comput. Ind. Eng., 60, 34-42 (2011) |
| [14] | Voll, R.; Clausen, U., Branch-and-price for a European variant of the railroad blocking problem, Electron. Notes Discret. Math., 41, 45-52 (2013) |
| [15] | Barnhart, C.; Jin, H.; Vance, P. H., RailRoad blocking: a network design application, Oper. Res., 48, 603-614 (2000) |
| [16] | Manheim, M. L., Fundamentals of Transportation Systems Analysis (1978), The MIT Press |
| [17] | Wolsey, L. A., Integer Programming (1998), Wiley · Zbl 0930.90072 |
| [18] | Chiou, S.-W., A subgradient optimization model for continuous road network design problem, Appl. Math. Model., 33, 1386-1396 (2009) · Zbl 1168.90357 |
| [19] | Held, M.; Wolfe, P.; Crowder, H. P., Validation of subgradient optimization, Math. Prog., 6, 62-88 (1974) · Zbl 0284.90057 |
| [20] | Kelley, J.; James, E., The cutting-plane method for solving convex programs, J. Soc. Ind. Appl. Math., 8, 703-712 (1960) · Zbl 0098.12104 |
| [21] | ILOG. 1987-2009. ILOG CPLEX. Accessed May 2009, http://www.ilog.com/products/cplex/; ILOG. 1987-2009. ILOG CPLEX. Accessed May 2009, http://www.ilog.com/products/cplex/ |
| [22] | Moeinadini, A., Simulation of freight grouping and moving in railroad networks for evaluating freight transportation strategies, Civil Engineering (2013), Sharif University of Technology |
| [23] | Kang, L.; Zhu, X., Strategic timetable scheduling for last trains in urban railway transit networks, Appl. Math. Model., 45, 209-225 (2017) · Zbl 1446.90018 |
| [24] | Kang, L.; Zhu, X., A simulated annealing algorithm for first train transfer problem in urban railway networks, Appl. Math. Model., 40, 419-435 (2016) · Zbl 1443.90038 |
| [25] | Sayarshad, H. R.; Tavakkoli-Moghaddam, R., Solving a multi periodic stochastic model of the rail-car fleet sizing by two-stage optimization formulation, Appl. Math. Model., 34, 1164-1174 (2010) · Zbl 1186.90018 |
| [26] | Gao, Y.; Yang, L.; Li, S., Uncertain models on railway transportation planning problem, Appl. Math. Model., 40, 4921-4934 (2016) · Zbl 1459.90021 |
| [27] | Ahuja, R. K.; Jha, K. C.; Liu, J., Solving real-life railroad blocking problems, Interfaces, 37, 404-419 (2007) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
