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 com-bines network design decisions and routing decisions, with time-dependent demands. A compact formulation for this problem,based on the aggregation of flows by destination, was proposedin [1]. They observed that the resolution on realistic instancesbecomes intractable and unscalable with state-of-the-art solversdue to the weak linear programming bound provided by theformulation. In this paper, we consider an extended formulationwhere flows are decomposed by origin-destination pairs, whilekeeping the requirement of destination-based routing. The qualityof the extended formulation and the computational time neededto solve it are evaluated on a representative set of networktopologies and traffic demands, and compared to results obtainedwith the base formulation of [1]. The extended formulation canthen be considered for more efficient resolution methods involvingdecomposition and cutting planes approaches.
info:eu-repo/semantics/published