Hybrid metaheuristic method for solving a multi-period emergency service location problem

Abstract

This study deals with the problem of establishing the network of emergency service units. The goal of the basic problem proposed in the literature is to locate certain number of units at given discrete points of the region and to allocate cities to established units, in order to balance the load of established emergency units. Having in mind that emergency units work in shifts, we extend the basic model to a multi-period model and involve additional constraints on the number of units to be located. Since, in practice, the number of emergency incidents varies on daily or monthly basis, we consider the uncertainty of the number of incidents and propose a robust integer programming formulation of the multi-period model, which controls the deviation of objective value under uncertainty of input data. In order to solve both deterministic and robust variant of the problem, we design an efficient hybrid metaheuristic method based on combination of Particle Swarm Optimization method (PSO) and Reduced Variable Neighborhood Search (RVNS). Computational results show that the proposed hybrid PSO-RVNS method quickly reaches all known optimal solutions obtained by CPLEX solver, and provides solutions for instances that remained out of reach of CPLEX. In the single-period case, PSO-RVNS outperforms existing metaheuristic method from the literature in the sense of CPU time. Short running times of PSO-RVNS and high-quality solutions indicate the efficiency of the proposed hybrid metaheuristic approach when solving the considered problem. Results presented in this study may help security experts and emergency managers to design an efficient and sustainable emergency system.