Minimizing the maximum flow loss in the network maintenance scheduling problem with flexible arc outages

We investigate a network maintenance scheduling problem where maintenance tasks are carried out on the arcs of a network within flexible time windows. During maintenance, an arc is interrupted and no flow can pass through it. Such arc outages introduce flow loss and thus affect network capacity and service capability. For some public services operated on networks, possible blackouts and serious flow loss introducing extreme risks are generally unacceptable. The problem is to find a feasible schedule of maintenance tasks so that the maximum flow loss during the planning horizon is minimized. We introduce a mixed integer programming formulation and a Benders reformulation for the problem. A Benders decomposition algorithm based on a branch-and-cut framework is designed. Strengthened initial cuts and effective cuts are introduced to reduce feasible region so that the exact algorithm is accelerated. An efficient separation procedure is proposed to generate Benders optimality cuts. Computational experiments were conducted on a set of benchmark instances and a set of simulated instances based on telecommunication networks. Computational results show that our algorithm performs much better than applying a solver to the formulation and an existing Benders decomposition algorithm for a related problem. Optimal schedules can reduce extreme risks caused by large flow loss on the network. Since multiple optimal solutions may exist, hierarchical optimization is used to further select a desirable schedule, by either minimizing total flow loss or minimizing the duration of maximum flow loss. With adaptations, our algorithm also performs well for two extensions.