Research On Dynamic Network Flow And Dynamic Disjoint Backward Hyperpath Optimization Algorithm

Under the background of continuous time dynamic networks,we study the minimum cost maximum flow in dynamic continuous time networks and the restricted disjoint backwardhyperpath(B-path)in dynamic directed hypergraph respectively.The main difficulty is to solve the problem of time continuity in continuous time dynamic networks.Firstly,we give some definitions and theorems about continuous time dynamic networks.Secondly,we propose the concrete modeling process of two kinds of dynamic network problems,and give examples and algorithms.In the continuous time dynamic flow network,each arc e is associated with two timevary weight functions in the continuous time range:the cost function we(t)of the unit flow and the capacity function ce(t),where t is the start time of flow on e.The objective in this work is to find an optimal scheme to send the maximum flow from a source to a sink with the minimum cost in a dynamic network.Due to the complexity of the problem in the network with time-varying cost and capacity functions,many researches are about the computing of the approximate solutions through transforming the continuous-time dynamic network into classical static network by time discretization.Then the degree of approximation is closely related to the degree of time discretization.Considering that in the changeable actual environment,some important changes of weight functions may be ignored due to time discretization.However,by using dynamic weight functions in different time periods,we consider the continuity of the transmission time and propose an efficient algorithm to find the maximum flow of minimum total cost.After solving the continuous time dynamic minimum cost and maximum flow problem,we solve the disjoint path problem in dynamic SRLG network.Next,in order to further study the non-intersecting problem in dynamic networks and improve the network survival performance,we propose to solve the restricted non-intersecting B-path problem in dynamic directed hypergraphs.The occurrence of faults in large-scale networks is inevitable and extremely destructive.Therefore,it has important research value to improve the survival performance of networks and ensure the fault tolerance of networks.Designing disjoint hyperpath is the main solution to improve network fault tolerance.Because the B-path in hyperpath has good structural properties and wide application background,we consider the construction of disjoint B-paths satisfying time constraints in time-varying hypergraph networks in this section.The research content is to give an optimal solution algorithm for non-intersecting B-path problems under the condition that the delay function of each super-arc is continuous time dynamic function when the starting time is given,and to prove the correctness and operation complexity of the algorithm.Finally,we summarize the whole paper and give the summary and prospect of the research content of this paper.Through our research,the models and algorithms for solving two kinds of dynamic networks are proposed,which improves the fault-tolerant performance of networks and expands the research content and field of dynamic networks.