Real Time Critical Edge of the Shortest Path in Transportation Networks

In transportation networks, a vehicle always travels longer than the shortest path due to sudden edge failure caused by unexpected events such as accident. In this situation, which edge failure results in the maximum of the travel distance between the source node and the destination node? If we know the edge, we can reduce the transportation cost and improve the networks structure. Regarding this problem, the most vital edge (MVE) problem considers in a global view and from the perspective of static decision-making based on complete information, while the longest detour (LD) problem solves in a local view and in terms of real time. This paper reconsiders this problem in a global view and in terms of real time. We propose the real time critical edge (RTCE) problem of the shortest path, and present an

O

(

n

2

) time algorithm by constructing the shortest path tree. Then, by giving a numerical example of urban transportation networks, we compare the results of MVE, LD and RTCE, and conclude that the RTCE problem has more practical significance.