Benders Decomposition For Maximum Total Flow With Flexible Arc Outages Problem

Many problems in production and life present a very complicated network structure,such as the power transmission problem of the power network,the cargo distribution problem of the logistics network,and the information transmission problem of the communication network.In order to effectively solve these network optimization problems,a large number of related studies based on network flow problems have been widely used.However,as current management decisions pay more attention to network operation efficiency,reasonable scheduling of network resources corresponding to nodes and edges of the network has become an urgent problem to be solved.However,this scheduling will dynamically change the network over time.Although dynamic network flow problems overcomes the shortcomings of the static network flow problems without considering time factor,the network traffic,structure or parameters can change over time.But the change in the network structure or parameters is relatively simple without considering complex scheduling relationship between edges and edges,edges and nodes in the network.So it cannot be directly applied to the above problem.But combining dynamic network flow problems with scheduling problems,using dynamic network flow problems to evaluate and screen feasible scheduling schemes of network resources is an effective way to solve the above problem.The problem of Maximum Total Flow with Flexible Arc Outages(Max TFFAO)was raised by Boland et al.when studying the equipment maintenance scheduling problem of the Hunter Valley Coal Chain network.In practice,the Max TFFAO problem meets maintenance requirements by changing the network structure in different time slices,and finally achieves the optimization goal of maximizing network traffic.It is essentially a special dynamic network flow problem created by the combination of dynamic network flow and scheduling.However,because of its large scale and complex structure,it is also an NP-hard problem,so it is difficult to solve.Therefore,this dissertation deeply considers the special combined structure of dynamic network flow and scheduling of this problem,solves the problem with Benders decomposition,and makes further improvements on the solution.The main research contents and results of this dissertation are as follows:(1)In this dissertation,the research background of the Max TFFAO problem is reviewed and it is compared with the problem of dynamic facility location and Network outage recovery.We also expound related models and solving algorithms of linear programming,mixed integer linear programming and network maximum flow,and introduce the classic decomposition method and improvement schemes of Benders decomposition algorithm in detail.In addition,this dissertation also specifically describes the process of constructing the problem of Max TFFAO,and discusses the relationship between the structural characteristics of the model and its computational complexity.(2)The process of decomposing the model using Benders decomposition is introduced.A comparative experiment of two Benders decompositions algorithms,namely CBD based on repeated solving the master problem and B&BC based on a single solution to the master problem,is designed,and the solution efficiency of the two algorithms is compared.In general,experimental analysis shows that B&BC has better solution effect than CBD.Based on this,we also explore the impact of relatively slack primary subproblem cuts on the solution of the B&BC algorithm.Experimental results show that the positive effects of primary subproblem cuts on the solution of B&BC algorithm are generally limited.(3)Since the B&BC algorithm only needs to solve the master problem once,and the scale of the master problem to be solved in the Benders decomposition in this dissertation is relatively large,the B&BC algorithm shows a better solution effect in general.Based on the B&BC algorithm,this dissertation improves the solution from two aspects of the subproblem and the master problem respectively.At the same time,for the most difficult part of the calculation examples,a special time segmentation and its improved algorithm are designed according to the time structure.From the experimental results,the above improvements all accelerate the convergence of the algorithm to a certain extent in different solution times for different scale examples.