Constructing Railroad Blocking Plans to Minimize Handling Costs

Harry N. Newton, Cynthia Barnhart and Pamela H. Vance
Additional contact information
Harry N. Newton: Department of Mathematical Sciences, United States Air Force Academy, USAF Academy, Colorado 80840
Cynthia Barnhart: Department of Civil and Environmental Engineering, M.I.T., Cambridge, Massachusetts 02139
Pamela H. Vance: Goizueta Business School, Emory University, Atlanta, Georgia 30322

Transportation Science, 1998, vol. 32, issue 4, 330-345

Abstract: On major domestic railroads, a typical general merchandise shipment may pass through many classification yards on its route from origin to destination. At these yards, the incoming traffic, which may consist of a number of individual shipments, is reclassified (sorted and grouped together) to be placed on outgoing trains. Each reclassification incurs costs due to handling and delay. To prevent shipments from being reclassified at every yard they pass through, several shipments may be grouped together to form a block. A block has associated with an origin–destination pair that may or may not be the origin or destination of any of the individual cars contained in the block. The objective of the railroad blocking problem is to choose which blocks to build at each yard and to assign sequences of blocks to deliver each shipment to minimize total mileage, handling, and delay costs. We model the railroad blocking problem as a network design problem in which yards are represented by nodes and blocks by arcs. Our model is intended as a strategic decision-making tool. We develop a column generation, branch-and-bound algorithm in which attractive paths for each shipment are generated by solving a shortest path problem. Our solution approach is unique in constraining the classification resources of each yard and simultaneously solving for different priority classes of shipments. We implement our algorithm and find near-optimal solutions in about one hour for the blocking problem of a large domestic railroad, in which the paths that shipments may take in the physical network are restricted. The resulting network design problem has 150 nodes, 1300 commodities, and 6800 possible arcs (blocks). We test the robustness of our solution on 19 test instances that are variations of the data for the real-world problems. If shipments are restricted to following one of a limited number of paths in the rail network, then, in four hours or less, our algorithm finds solutions within 0.4% of optimal for all test cases. Furthermore, the solutions obtained are no more than 3.9% from optimal even if all possible paths are allowed.

Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (28)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.32.4.330 (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:ortrsc:v:32:y:1998:i:4:p:330-345

Access Statistics for this article

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