Study on Vital Edges of Delivery Path under Terminal Uncertainty

In delivery, a vehicle usually takes goods to a terminal through the shortest path. But usually, the terminal is dubious, and the vehicle needs to be apprised that the destination has been changed before it arrives there. So the path has to be changed. Then, since a segment of the journey has been passed, the original path maybe not be the optimum one, and the vehicle shouldn't have arrived at the terminal on time. In this paper, the problem of delivery path when terminal is uncertain is studied. First, me concept of the vital edge in delivery under terminal uncertainty has been brought forward. Then an algorithm of computing the vital edge has been presented, and its time complexity has been analyzed. Finally, this paper point out that through a such way, a scientific schedule should be constituted, by which the vehicles can arrive the terminal on time.