The capacitated multi-commodity network design problem (CMND) represents a generic network design model for applications used in designing construction and improvements to telecommunication, logistics, transportation, distribution, and production networks. This paper presents an approach combining capacity scaling and local branching for CMND. Capacity scaling is an approximate iterative solution approach for capacitated network problems based on the principle of changing arc capacities that depend on flow volumes on arcs. Local branching is a method of solving new restricted problems based on an exploration of solution neighborhoods defined as local branching constraints. Capacity scaling with a strong path flow based formulation including forcing constraints can produce high-quality solutions within a short period of time allotted for computation. By combined capacity scaling and local branching, the combined approach can offer one of the best current solutions compared to previous heuristics for CMND.

capacitated network design, capacity scaling, local branching.