查看文章

Natural disasters cause significant disruption in road networks, rendering many crucial links unusable. We investigate how to identify a sequence for repairing these links that minimizes total travel time over the repair horizon, given that at each repair stage road traffic distributes according to the principle of user equilibrium. We derive an analogue of Bellman’s optimality principle, allowing us to solve the problem using methods of dynamic programming. We specifically develop a bidirectional search heuristic with customized pruning and branching strategies that exploit specific properties of traffic assignment. Our experiments show that our method is scalable and performs well even on networks involving thousands of links.