Variable neighborhood search method for optimizing the emergency service network of police special forces units

Abstract In this study we consider mathematical models that arise from the problem of establishing and optimally utilizing the network of Police Special Forces Units (PSFUs) in the Republic of Serbia. The goal is to locate certain number of PSFUs in the given network in order to minimize the maximal load of established emergency units. We have designed an efficient metaheuristic method, based on the combination of the Reduced Variable Neighborhood Search (RVNS) and the basic Variable Neighborhood Search (VNS). The proposed approach, named RVNS-VNS, involves two efficient improvement procedures: Local Search Deletion and Steepest-descent Hill Climbing, which help the algorithm converge to high-quality solutions. Computational experiments show that the proposed RVNS-VNS method quickly reaches all known optimal solutions. Furthermore, it provides solutions for the instances that CPLEX solver was unable to obtain.