We introduce a novel incremental network design problem motivated by the expansion of hub capacities in package express service networks: the \textit{incremental network design problem with multi-commodity flows}. We are given an initial and a target service network design, defined by a set of nodes, arcs, and origin-destination demands (commodities), and we seek to find a transition from the initial service network to the target service network. In the target service network design, the capacity of a subset of arcs has been increased (hub capacities can be modeled as arcs in the network). In each period, the capacity of a single arc can be increased and the cost in a period is given by the solution to an unsplittable multi-commodity flow problem. Our objective is to find a sequence of arc capacity expansions such that the total cost during the transition is minimized. We model the problem as an integer program, propose and analyze greedy heuristics and develop an exact solution approach. We provide worst-case analyses for the greedy heuristics and compare the efficacy of the algorithms to solving the integer programming formulation of the problem using a commercial solver.
Citation
Georgia Institute of Technology H. Milton Stewart School of Industrial and Systems Engineering 755 Ferst Drive, NW, Atlanta, GA 30332, U.S., 11/2021