The hierarchical network design problem with transshipment facilities

The hierarchical network design problem with transshipment facilites was first formulated by Current, in 1988. The objective of the FC-HNDP is to identify a least cost, two-level network. The network must include a primary path from a prespecified origin node to a prespecified terminus node. All nodes not on the primary path must be connected to that path via secondary arcs. In addition, transshipment facilities are required at the intersections of the two network levels. In this paper the authors present two efficient heuristics for solving the FC-HNDP. These heuristics were based upon a Lagrangian relaxation of the problem. To facilitate this relaxation, the authors have reformulated the original problem. Results for 240 randomly generated problems are summarized. The heuristics yielded the optimal solution in 72% of these problems. The mean gap between the Lagrangian lower bound and the feasible solution value was 0.38% and the maximum gap was 4.33% of the lower bound.