A two-phase optimization method for solving the multi-type maximal covering location problem in emergency service networks

Abstract

This study introduces the Multi-Type Maximal Covering Location Problem (MTMCLP) that arises from the design of emergency service networks, and represents a generalization of the well-known Maximal Covering Location Problem (MCLP). Differently from the basic MCLP, several types of incidents and emergency units are considered and hierarchy of emergency units of different types is assumed in the MTMCLP. The numbers of available emergency units of each type are limited to some constants. The objective of the MTMCLP is to choose locations for establishing emergency units of each type, such that the total number of covered incidents is maximized. In order to provide a decision maker with optimal solutions in an efficient manner, a two-phase optimization approach to the MTMCLP is designed. In the first phase, a variant of Reduced Variable Neighborhood Search (RVNS) is applied to quickly find a high-quality solution. The obtained RVNS solution is used as a good starting point for the Linear Programming method in the second phase, which returns the optimal solution to the MTMCLP. All constructive elements of the proposed two-phase method, denoted as RVNS-LP, are adapted to the characteristics of the considered problem. The RVNS-LP approach is evaluated on real-life instances obtained from two networks of police units in Montenegro and Serbia, and randomly generated test instances of larger dimensions. Experimental evaluation shows that the proposed RVNS-LP reached all optimal solutions on all real-life test instances in very short CPU time. On generated test instances, the RVNS-LP also returned optimal solutions in all cases, within short running times and significant time savings compared to CPLEX solver. The mathematical model and the proposed two-phase optimization method may be applicable in the design and management of various emergency-service networks.