Cutting-Plane Matheuristic for Service Network Design with Design-Balanced Requirements

The paper introduces a cutting-plane matheuristic for the design-balanced capacitated multicommodity network design problem, one of the premier formulations for the service network design problem with asset management concerns increasingly faced by carriers within their tactical planning processes. The matheuristic combines a cutting-plane procedure efficiently computing tight lower bounds and a variable-fixing procedure feeding a MIP solver. Learning mechanisms embedded into the cutting-plane procedure provide the means to identify promising variables and thus both reduce the dimension of the problem instance, making it addressable by a MIP solver, and guide the latter toward promising solution spaces. Extensive computational experiments show the efficiency of the proposed procedures in obtaining high-quality solutions, outperforming the current best methods from the literature.