Methods for time-dependent combined network design and routing optimization

The combined network design and (distributed) traffic routing problem can be formulated as a large-scale multi-period mixed integer optimization problem. This problem combines network design decisions and routing decisions, with time-dependent demands. In cite{FP14}, we proposed a compact formulation based on the aggregation of flows by destination. We observed that its resolution on realistic instances becomes intractable and unscalable with state-of-the-art solvers due to the weak linear programming bound that this formulation provides. In this paper, we consider an extended formulation where flows are decomposed by origin-destination pairs, while keeping the requirement of destination-based routing. The quality of the extended formulation and the computational time needed to solve it are evaluated on a representative set of network topologies and traffic demands, and compared to results obtained with the base formulation of cite{FP14}. The extended formulation can then be considered for more efficient resolution methods involving decomposition and cutting planes approaches.