Metaheuristics for protecting critical components in a service system: A computational study

• The application of the basic interdiction model is examined as a basis for computational experiments.
• A hybrid approach combining meta-heuristics and optimization methods are proposed for solving the basic interdiction model. They significantly cut down the computational requirement for getting good solutions.
• Extensive computational experiments have been carried to demonstrate the effectiveness and efficiency of our hybrid approach.

Deliberate sabotages and terrorist attacks are major threats to the safety of modern societies. These attacks often target at important infrastructures such as energy production and transmission systems, food and water supply networks, telecommunications networks, transportation networks, etc. In such systems, some components are critical as their malfunction may adversely affect the operations of the whole systems. This research examines several models based on the median problem for identifying these components in a service system. In addition to the existing exact solution methods, we propose meta-heuristics to tackle this computationally hard problem. Our hybrid approach combines the strengths of both meta-heuristics and exact solution methods. The experiment shows that the combination of solution methods significantly cut down the computational requirement for finding the critical components in a service network for protection.