Research on an Algorithm of the Acceptable Shortest Path

Abstract

In transportation network, the path interruption occurs frequently, and how to choose a reasonable path before departure is the key to ensure the timely delivery of materials. In this paper, on the basis of defining the alternative acceptable coefficient of the edge, the alternative acceptable coefficient of the path and the acceptable shortest path (ASP), the algorithm of the ASP is proposed, which can guarantee the transportation time is still acceptable after path interruption, and its complexity is also analyzed. Finally, a numerical example is performed to validate the efficiency and rationality of the proposed algorithm, and the results indicate that the proposed algorithm provides a good way to solve such kinds of problems in the fields of traffic, communication and so on.