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

Shuang Jin, Ying Liu, Jing Zhou and Qian Hu

European Journal of Operational Research, 2026, vol. 328, issue 2, 430-445

Abstract: 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.

Keywords: Scheduling; Network maintenance scheduling; Arc outage; Flow loss; Benders decomposition (search for similar items in EconPapers)
Date: 2026
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722172500582X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:328:y:2026:i:2:p:430-445

DOI: 10.1016/j.ejor.2025.07.056

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().