Constructing railroad blocking plans to minimize handling costs

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 the 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 is 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.