On Shortest Walk Problem With Two Resource Constraints And Replenishment

Resource constrained shortest path problem(RCSPP) is an important generalization of shortest path problem,which is widely used in communication network construction,flight crew management and other scenarios.The resource constrained shortest path problem with replenishment is a generalization of RCSPP,but only one resource constrained with replenish-ment problem has been studied.The feasible solution or the optimal solution of the problem can be a walk(vertices and edges may repeat) rather than a path(vertices and edges do not repeat)because of the resource constraints and replenishment.This paper focuses on the shortest path problem with two resource constraints and replenishment and the main contents are summarized as follows:The first chapter introduces the background of the classical shortest path problem and the related research results and progress of the constrained shortest path problems.Also,a general model of the shortest path problem with multiple resource constraints and replenishment is proposed.The second chapter focuses on the shortest path problem with two resource constraints and replenishment on acyclic digraphs(in acyclic digraphs,the vertices and edges of any walk do not repeat and so it is a path).Firstly,it is proved that the problem is NP-Hard,and then two polynomial time algorithms are given to determine whether there is a solution and find the least step solution whose time complexities are O(m)and O(mn),where m represents the number of arcs and n represents the number of nodes.Then,an exact exponential time algorithm is given for solving shortest path in general cases,and it is pointed out that if there is no edge between two nodes which can replenish the same resource,it can be solved in time complexity of O(m?~-),where ?~- represents the maximum in-degree among all nodes.Finally,an algorithm with time complexity of O(mn log n)is designed when the distance function and two resource consumption functions are the same.The third chapter deals with the shortest walk problem with two resource constraints and replenishment on a general digraph.Firstly,we analyze the properties of the feasible solutions and propose an algorithm with time complexity of O(n~3m) to find the optimal resource walk from the starting point to any intermediate point.Then,an algorithm with time complexity of O(n~3m) for finding the shortest walk is designed for the case that the distance function is a constant function.Finally,an algorithm with complexity of O(nm log n) for finding the shortest walk is designed when the distance function and two resource consumption functions are the same.In the fourth chapter,We implement the above algorithms with MATLAB.The numerical computations are conducted on instances of the flight routing problem as well as on randomly generated instances.The computation results are compared with Gurobi optimization software.The fifth chapter makes a summary of this paper and prospects the future research.