The network design problem is used to model a wide variety of problems in the design of and improvements to logistics, transportation, distribution, production, and telecommunication networks. For logistics or telecommunication network problems, each commodity is transported via transshipment facilities, such as distribution centers or routers. Generally, the number of transshipment facilities on the path of each commodity is small or at least limited. Conditions that limit the number of arcs between transshipment facilities on a commodity path are called hop-constraints. In this paper, we consider the hop-constrained network design problem with multiple commodities and capacitated arcs. We present an approach that combines capacity scaling and a local branching matheuristic for the hop-constrained network design problem, and propose column-generation for the hop-constrained paths.

hop-constraint, network design, capacity scaling, local branching.