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

DOI码：10.1016/j.ejor.2025.07.056

发表刊物：European Journal of Operational Research

关键字：Scheduling, Network maintenance scheduling, Arc outage, Flow loss, Benders decomposition

摘要：本文研究网络维护调度问题，该问题需要在灵活时间窗口内对网络弧段执行维护任务。维护期间弧段将中断通行，无法传输流量。此类弧段中断会导致流量损失，进而影响网络容量和服务能力。对于某些依托网络运行的公共服务而言，可能出现的服务中断及严重流量损失会带来极端风险，这通常是不可接受的。本研究旨在寻找可行的维护任务调度方案，以最小化规划周期内的最大流量损失。我们针对该问题提出了混合整数规划模型和Benders重构模型，设计了基于分支切割框架的Benders分解算法。通过引入强化初始割和有效割来缩减可行域，从而加速精确算法的求解效率。此外，还提出了高效分离程序以生成Benders最优割。基于电信网络的基准实例和模拟实例进行了计算实验，结果表明：相比直接采用求解器处理原模型及现有针对相关问题的Benders分解算法，我们的算法性能显著提升。最优调度方案能够有效降低因网络大流量损失引发的极端风险。鉴于可能存在多个最优解，采用分层优化方法进一步筛选理想调度方案——或最小化总流量损失，或最小化最大流量损失的持续时间。经过适应性调整，我们的算法在两个扩展问题中也表现出良好性能。

论文类型：SCI

是否译文：否

发表时间：2025-09-01

收录刊物：SCI