A hybridised variable neighbourhood tabu search heuristic to increase security in a utility network

• A decision model aimed at increasing security in a utility network is proposed.
• The goal is to reduce the risk of service failure given a limited security budget.
• An exact approach and a variable neighbourhood tabu search heuristic are developed.
• A generator for realistic networks is built and used to test the solution methods.
• The hybridised heuristic reduces the total risk on average with 32%.

We propose a decision model aimed at increasing security in a utility network (e.g., electricity, gas, water or communication network). The network is modelled as a graph, the edges of which are unreliable. We assume that all edges (e.g., pipes, cables) have a certain, not necessarily equal, probability of failure, which can be reduced by selecting edge-specific security strategies. We develop a mathematical programming model and a metaheuristic approach that uses a greedy random adaptive search procedure to find an initial solution and uses tabu search hybridised with iterated local search and a variable neighbourhood descend heuristic to improve this solution. The main goal is to reduce the risk of service failure between an origin and a destination node by selecting the right combination of security measures for each network edge given a limited security budget.