An Algorithm For The Elementary Shortest Path Problem With Resource Constraints

The shortest path problem is a classic problem in graph theory.Its algorithm research has important theoretical value in optimization problem.With the rapid development of science and technology and the needs of daily life,the ordinary shortest path problem can not meet people's needs,which leads to the shortest path problem with various resource constraints.The problem model studied in this paper is among them.One is the basic shortest path problem with time window and capacity resource constraints(ESPPRC).In this paper,the exact algorithm of the basic shortest path problem with resource constraints is studied.It is found that the efficiency of the existing accurate algorithm can not meet the needs.Therefore,an improved algorithm is proposed to accelerate the rate of obtaining the exact solution.In this paper,through the research and analysis of three solving ideas of the basic shortest path problem with resource constraints,the advantages and problems of each algorithm are found,and the improved ideas and directions are proposed.Based on the original method,an improved algorithm for ESPPRC problem is proposed.The algorithm combines the idea of lower bound matrix in pulse algorithm and the idea of using label to store local path in label algorithm,and uses branch delimitation and pruning strategy.To narrow down the search space.The algorithm expands the storage content of the lower bound matrix from the local path cost to the complete path information,and uses this matrix to design the stitching path strategy to improve the algorithm's solution rate.Two sorting strategies are proposed to optimize the sparse graph and the dense graph respectively.The order in which the matrices are generated further improves the efficiency of problem solving.In this paper,the improved algorithm is validated by the example in Solomon dataset,and the performance of the algorithm is evaluated in detail.It is proved that the improved algorithm has better efficiency than the original algorithm.Finally,the application of ESPPRC problem in real life is briefly introduced,and the improved algorithm proposed in this paper is applied to more types of multi-constrained shortest path problems.