Tabu Search Algorithm for the Railroad Blocking Problem
Publication: Journal of Transportation Engineering
Volume 139, Issue 2
Abstract
The railroad blocking problem (RBP) is an important decision for freight railroad companies. The objective of this problem is to minimize the costs of delivering all commodities by deciding which interyard blocks to build and specifying the assignment of commodities to these blocks. In this paper, a mathematical model is presented for the RBP on Iran Railways. Its decision variables identify blocking scheme and demand assignment to these blocks. The RBP in medium and large sizes is not solvable with any commercial software available in the market. Therefore, a solution method based on tabu search algorithm is proposed for the suggested model. For evaluating the proposed algorithm, several simulated test problems are randomly generated and solved. The obtained results on the test problems are compared with those of solutions generated by CPLEX software. The comparison shows high efficiency and effectiveness of the proposed algorithm. The proposed model and solution method are applied to build a blocking plan for the Iranian railway.
Get full access to this article
View all available purchase options and get full access to this article.
References
Ahuja, R. K., Cunha, C. B., and Sahin, G. (2005). “Network models in railroad planning and scheduling.” Tutorials operations research, 54–101.
Ahuja, R. K., Jha, K. C., and Liu, J. (2007). “Solving real-life railroad blocking problems.” Interfaces, 37(5), 404–419.
Assad, A. A. (1983). “Analysis of rail classification policies.” INFORMS, 21(4), 293–314.
Balakrishnan, A., Magnanti, T. L., and Mirchandani, P. (1997). “Network design.” Annotated bibliographies in combinatorial optimization, M. Dell'Amico, F. Maoli and S. Martello, eds., Wiley, New York.
Barnhart, C., Jin, H., and Vance, P. H. (2000). “Railroad blocking: A network design application.” Oper. Res., 48(4), 603–614.
Bodin, L. D., Golden, B. L., Schuster, A. D., and Romig, W. (1980). “A model for the blocking of trains.” Transp. Res., 14(1–2), 115–120.
Chapman, S. J. (2003). Java for engineers and scientists, 2nd Ed., Prentice Hall, New York.
Cordeau, J. F., 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. (2000). “Service network design in freight transportation.” Eur. J. Oper. Res., 122(2), 232–288.
Crainic, T. G. (2002). “A survey of optimization models for long-haul freight transportation.” Handbook of transportation science, 2nd Ed., R. W. Hall, ed., Kluwer, Dordrecht, Netherlands.
Crainic, T. G. (2006). “Long-haul freight transportation.” Handbook of transportation science, International Series in Operations Research & Management Science, New York.
Crainic, T. G. (2009). “Service design models for rail intermodel transportation.” Innovations in distribution logistics, Lecture Notes in Economics and Mathematical Systems, Berlin, Germany, Vol. 619, 53–67.
Glover, F., and Laguna, M. (1997). Tabu search, Kluwer Academic, London.
Gorman, M. F. (1998). “An application of genetic and tabu searches to the freight railroad operating plan problem.” Ann. Oper. Res., 78(0), 51–69.
Huntley, C. L., Brown, D. E., Sappington, D. E., and Markowics, B. P. (1995). “Freight routing and scheduling at CSX Transportation.” Interfaces, 25(3), 58–71.
IBM ILOG. (2008). ILOG CPLEX version 11.0 user’s guide, ILOG CPLEX Division, IBM ILOG.
Jha, K. C., Ahuja, R. K., and Şahin, G. (2008). “New approaches for solving the block-to-train assignment problem.” Networks, 51(1), 48–62.
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.
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.” Networks, 19(3), 313–360.
Newton, H. N. (1996). “Network design under budget constraints with application to the railroad blocking problem.” Ph.D. thesis, Auburn Univ, Auburn, Alabama.
Newton, H. N., Barnhart, C., and Vance, P. H. (1998). “Constructing railroad blocking plans to minimize handling costs.” Transp. Sci., 32(4), 330–345.
Ridge, E. (2007). “Design of experiments for the tuning of optimization algorithms.” Ph.D. thesis, Dept. of Computer Science, Univ. of York, York, UK.
Talbi, E.-G. (2009). Metaheuristics: From design to implementation, Wiley, Hoboken, NJ.
Van Dyke, C. D. (1986). “The automated blocking model: A practical approach to freight railroad blocking plan development.” Transp. Res. Forum, 27(0), 116–121.
Van Dyke, C. D. (1988). “Dynamic management of railroad blocking plans.” Transp. Res. Forum, 29(1), 149–152.
Vaughn, N., Polnaszek, C., Smith, B., and Helseth, T. (2000). Design-Expert 6 user’s guide, Stat-Ease, Inc, Minneapolis.
Yaghini, M., Foroughi, A., and Nadjari, B. (2011a). “Solving railroad blocking problem using ant colony optimization algorithm.” Appl. Math. Modell., 35(12), 5579–5591.
Yaghini, M., Seyedabadi, S. M., and Khoshraftar, M. M. (2011b). “A population-based algorithm for the railroad blocking problem.” J. Ind. Eng. Int., 8(1), 8.
Yang, L., Gao, Z., and Li, K. (2011). “Railway freight transportation planning with mixed uncertainty of randomness and fuzziness.” Appl. Soft Comput., 11(1), 778–792.
Information & Authors
Information
Published In
Journal of Transportation Engineering
Volume 139 • Issue 2 • February 2013
Pages: 216 - 222
Copyright
© 2013 American Society of Civil Engineers.
History
Received: Mar 7, 2012
Accepted: Jul 23, 2012
Published online: Aug 22, 2012
Published in print: Feb 1, 2013
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.