Identification of road links with the gravest network impacts when blocked concurrently

Abstract

The identification of a combination of links which can cause the gravest impact on network performance, when interrupted simultaneously, is of great practical importance. The links can be spatially dispersed due to an event such as an earthquake or due to a combination of accidents and disasters. This task is, thus, extremely computationally demanding when applied to real-world networks. We focused on approaches which are both capable of accomplishing this task and where the computational time is acceptable for application in practice. We tested three algorithms based on known heuristic methods: Simulated Annealing (SA), Guided Local Search (GLS) and Variable Neighborhood Search (VNS). The algorithms were modified in the sense of adjusting the searching neighborhood. All the algorithms were subsequently applied to four actual road networks in order to evaluate the impacts of complete simultaneous blockage of four and ten links. The results suggest that the modified SA algorithm identified scenarios with worse consequences than the algorithms based on GLS and VNS. The SA results, for the setting with four interrupted links, were even comparable with those obtained from a deterministic algorithm (which evaluates the entire state space). The algorithm based on SA was also performing best for situations with ten concurrently blocked links. The approach based on SA is thus suitable when modeling the potential impacts of events where a large number of concurrently blocked links is expected. Network managers will thus be able to monitor the immediate state of the network and potential risks related to network disintegration.