Network design under budget constraints with application to the railroad blocking problem

We develop a column generation-based, branch-and-bound algorithm for the directed network budget design problem (BDP), also known as the optimal network design problem, when additional budget constraints are placed on some nodes. Our pricing sub-problems identify new paths for the commodities using a shortest path algorithm. We model the Railroad Blocking Problem (RBP) as a BDP with constraints on the capacities at the nodes and restrictions on the legal paths for each commodity. In RBP, the physical rail network (the railroad terminals and tracks) is already defined. The "blocking network" to be constructed is a virtual network that is overlayed on the physical network. The blocks are virtual "express" arcs which a commodity may take to have uninterrupted service between two terminals that are not necessarily connected by a physical link. Solving RBP requires specifying the blocking network and assigning paths through the blocking network for each commodity. Our solution technique to RBP is unique in constraining the use of resources at the nodes and allowing multiple priority classes for the commodities. Computational results for our algorithm show solutions within 2.3% of a known lower bound for a real-world RBP instance (with 150 nodes, 1300 commodities, and up to 6,800 candidate arcs after preprocessing) for a large domestic railroad and within 5.5% for randomly-generated instances of the same size.