A hybridised taboo search heuristic to increase security in a utility network

In this paper we propose a decision model aimed at increasing security in a utility network (e.g., smart grid, water network). The network consists of edges that might be a viable target for terrorists depending on several factors such as geographical location, accessibility of the network, the political stability of a region. Based on this we assume that all edges (e.g., pipes, cables) have a certain, not necessary equal, probability of failure, which can be reduced by selecting appropriate edge-specific security strategies. The decision model proposed in this paper is based on a metaheuristic approach, that uses taboo search hybridised with iterated local search and a large scale neighbourhood decent heuristic. The main goal is to reduce the risk of service failure between a couple of network nodes by selecting the right combination of security measures for each network edge given a limited security budget. A generator for realistic instances is proposed and used to create a set of test instances. Experiments on these instances are conducted to tune the parameters and evaluate the proposed metaheuristic algorithm.