A Rolling Horizon Heuristic for the Multiperiod Network Design and Routing Problem

The capacitated fixed‐charge network design (FCND) problem considers the simultaneous optimization of capacity installation and routing of traffic where a fixed cost is paid for opening a link and a linear routing cost is paid for sending traffic flow(s) on that link. The routing decisions must be performed such that the traffic flows remain bounded by the installed link capacities. The FCND problem appears as a particular case of the combined multiperiod network design and traffic flow routing problem with time‐dependent demands formulated in this article as a mixed integer linear program (MILP). A compact formulation based on the aggregation of traffic flows per destination and an extended formulation, where flows are decomposed by origin‐destination pairs while keeping the requirement of destination‐based routing, have been proposed in D. Papadimitriou and B. Fortz, IEEE International Conference on Communications (2014), pp.1124–1130 and IEEE Global Communications Conference (2014), pp.1303–1309, respectively. In this article, we propose to resolve this computationally challenging problem by means of the rolling horizon heuristic with the objective to decrease the computational time while degrading as less as possible the quality of the solution. The resulting improvements enable to progressively overcome the computational limits encountered when solving such problem, in particular, when the network size and number of periods increase. The improvements provided by the rolling horizon heuristic can be further exploited by extending the proposed model to account for different patterns of failures that may affect installed arcs over time. For this purpose, our generalized MILP formulation comprises a time‐variable link maintenance cost function. We further analyze the quality of the results for the proposed formulation with different link maintenance cost functions with the objective to derive the best arc replacement strategy.