This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Ahuja, R. K. Articles by Liu, J. Search for Related Content

Solving Real-Life Railroad Blocking Problems

Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611
Innovative Scheduling, Inc., GTEC, Gainesville, Florida 32641
Norfolk Southern Corporation, Atlanta, Georgia 30309
ahuja{at}ufl.edu
krishna{at}innovativescheduling.com
liujian{at}cox.net

Each major US railroad ships millions of cars over its network annually. To reduce the intermediate handlings of shipments as they travel over the railroad network, a set of shipments is classified (or grouped together) at a railroad yard to create a block. The railroad blocking problem is to identify this classification plan for all shipments at all yards in the network to minimize the total shipment cost, i.e., to create a blocking plan. The railroad blocking problem is a very large-scale, multicommodity, flow-network-design and routing problem with billions of decision variables. Its size and mathematical difficulty preclude solving it using any commercial software package. We developed an algorithm using an emerging technique known as very large-scale neighborhood (VLSN) search that is able to solve the problem to near optimality using one to two hours of computer time on a standard workstation computer. This algorithm can also handle a variety of practical and business constraints that are necessary for implementing a solution. When we applied this algorithm to the data that several railroads provided us, the computational results were excellent. Three Class I railroad companies (a Class I railroad, as defined by the Association of American Railroads, has an operating revenue exceeding $319.3 million) in the United States—CSX Transportation, Norfolk Southern Corporation, and Burlington Northern and Santa Fe Railway—used it in developing their operating plans. Two US Class I railroads have also licensed it for regular use in developing their operating plans, and other railroads are showing considerable interest. We expect this algorithm to become an industry standard for freight railroads worldwide. In this paper, we outline our algorithm, show the computational results we received using real data, and describe areas for future research.

Key Words: networks; network design; multicommodity flows; flow algorithms; heuristics; transportation; freight; railroad; blocking; integer programming; neighborhood search

This article has been cited by other articles:

				O. Seref, R. K. Ahuja, and J. B. Orlin Incremental Network Optimization: Theory and Algorithms Operations Research, May 1, 2009; 57(3): 586 - 594. [Abstract] [PDF]

				A. Fugenschuh, H. Homfeld, A. Huck, A. Martin, and Z. Yuan Scheduling Locomotives and Car Transfers in Freight Transport Transportation Science, November 1, 2008; 42(4): 478 - 491. [Abstract] [PDF]