Solving Real-Life Railroad Blocking Problems

Ravindra K. Ahuja (), Krishna C. Jha () and Jian Liu ()
Additional contact information
Ravindra K. Ahuja: Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611
Krishna C. Jha: Innovative Scheduling, Inc., GTEC, Gainesville, Florida 32641
Jian Liu: Norfolk Southern Corporation, Atlanta, Georgia 30309

Interfaces, 2007, vol. 37, issue 5, 404-419

Abstract: 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.

Keywords: networks; network design; multicommodity flows; flow algorithms; heuristics; transportation; freight; railroad; blocking; integer programming; neighborhood search (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (34)

Downloads: (external link)
http://dx.doi.org/10.1287/inte.1070.0295 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orinte:v:37:y:2007:i:5:p:404-419

Access Statistics for this article

More articles in Interfaces from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().