关键词: 网络维护调度, 灵活弧中断, 混合整数规划, 变邻域搜索, 基于优化的启发式

Abstract:

Maintenance scheduling is to make a scheduling plan for a series of maintenance activities within a certain period before an accident occurs. Through preventive maintenance， the service life of equipment or facilities can be effectively improved to avoid losses caused by unexpected faults. In practice， there are many network-based services， such as communication networks， transportation networks， supply chain networks， etc. Different maintenance activities are distributed in different locations of the network， and maintenance downtime will cause flow losses in the network.A network maintenance scheduling problem where maintenance activities are carried out on the arcs of the network with flexible start time window constraints. An arc is closed if a maintenance activity is being carried out on it and thus no flow can pass through it. The problem is to arrange the start time of each maintenance activity in the maintenance period， to maximize the total flow of the network with flexible arc outages （MaxTFFAO）， that is minimizing the flow reduction caused by maintenance. The problem has been proposed initially from the actual demand of a coal supply chain and there exist some studies of greedy heuristics and Benders decomposition algorithm on it.Considering large-scale networks and different time limits in practical applications， it expects to further explore the characteristics of this problem and design more effective heuristic algorithms. Firstly， the problem is formulated as a mixed integer programming model， and some properties which are useful for algorithm design are analyzed. Secondly， effective neighborhood operators are designed and embedded into heuristic algorithms. A variable neighborhood search heuristic algorithm （VNS） and an optimization-based heuristic algorithm （OBH） are proposed for the problem. Specifically， VNS is enhanced with the above operators， fast solution evaluation， polynomial algorithms for network flow subproblems， hash tables， etc. OBH decomposes the problem by slicing the planning horizon and makes use of the advantage of a solver which can solve small subproblems optimally and efficiently. Next， computational experiments are carried out on a set of simulated test instances with various sizes of network and maintenance activities， and a set of real-world test instances from the literature. The comparison results show that both two proposed heuristic algorithms are effective in finding feasible solutions of high quality， and the results further verify the effectiveness of algorithm components. Finally， the algorithms introduced in this paper can be well applied to the related variants， so as to provide a good foundation for problem-solving.

Key words: network maintenance scheduling, flexible arc outages, mixed integer programming, variable neighborhood search, optimization-based heuristic