Railroad blocking: A network design application

In this study, we formulate the railroad blocking problems as a network des ign problem with maximum degree and flow constraints on the nodes and propo se a heuristic Lagrangian relaxation approach to solve the problem. The new approach decomposes the complicated mixed integer programming problem into two simple subproblems so that the storage requirement and computational e ffort are greatly reduced. A set of inequalities are added to one subproble m to tighten the lower bounds and facilitate generating feasible solutions. Subgradient optimization is used to solve the Lagrangian dual. An advanced dual feasible solution is generated to speed up the convergence of the sub gradient method. The model is tested on blocking problems from a major rail road, and the results show that the blocking plans generated have the poten tial to reduce the railroad's operating costs by millions of dollars annual ly.