Research On Multi-constraint Shortest Path Problem

With the rapid development of communication networks,users’demand for information transmission is increasing,and communication is moving towards low latency and high bandwidth.With the increase of the number of services and the frequency of information interaction,traditional technologies will encounter problems such as network link congestion and excessive transmission delay.Therefore,it is necessary to explore end-toend routing technology,adaptively and dynamically adjust the transmission path under the constraints of network resources and ultrashort delay requirements,achieve real-time information transmission,and improve the overall network carrying capacity.End-to-end transmission path planning can be reduced to the constrained shortest path problem in graph theory,which is a highly non-convex NP-hard problem.Common research methods include heuristic methods,approximation algorithms,Lagrangian dual-based algorithms,and exact algorithms.This thesis focuses on the research of single-constraint shortest path problem and multi-constraint shortest path problem,and proposes high-performance solving algorithms.For the single-constraint shortest path problem,this paper uses a solution algorithm designed based on Lagrangian duality theory to transform the original problem into a problem of maximizing a piecewise linear concave function.By solving the optimal solution of the dual problem,we provide a lower bound and an approximate optimal solution for the original problem.Our algorithm innovatively constructs a tighter upper bound for the initial feasible domain and constructs the gradient information of the dual problem objective function.We use the Newton iteration format to solve the dual problem,further improving the solution efficiency.Through the tightening technique of the bound and the application of the Newton method,this method has good performance in practice.For the multi-constraint shortest path problem,this paper focuses on the shortest path problem with two constraints.Due to the NP-hardness of the feasibility verification of this problem,we first design an exact algorithm to check the feasibility of the multi-constraint shortest path problem to determine the necessity of subsequent solutions.We transform the problem into a single-constraint shortest path problem and solve its Lagrangian dual problem in the first stage.The second stage is for exact solution.For the dual problem of the multi-constraint shortest path problem,we first convexly combine the two constraints and further optimize the parameters of the convex combination to obtain the optimal combination parameter,which can then be used to transform the multi-constraint shortest path problem into a single-constraint shortest path problem for solution.We provide an efficient solution.By analyzing the number of times the algorithm calls the Dijkstra algorithm,we demonstrate its practical value.