A Two-Phase Optimization Method for Solving the Multi-Type Maximal Covering Location Problem in Emergency Service Networks

Authors

  • Zorica Stanimirović Faculty of Mathematics, University of Belgrade
  • Stefan Mišković Faculty of Mathematics, University of Belgrade
  • Darko Trifunović Faculty of Security Studies, University of Belgrade
  • Veselin Veljović Faculty of Security Studies, University of Belgrade

DOI:

https://doi.org/10.5755/j01.itc.46.1.13853

Keywords:

variable neighborhood search, linear programming, emergency service network, maximal covering location problem

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.

DOI: http://dx.doi.org/10.5755/j01.itc.46.1.13853

Author Biographies

Zorica Stanimirović, Faculty of Mathematics, University of Belgrade

Associate Professor

Department of Numerical Mathematics and Optimization

Coordinator for International Cooperation

Faculty of Mathematics, University of Belgrade

 

 

Stefan Mišković, Faculty of Mathematics, University of Belgrade

PhD student

Department of Computer Science and Informatics

Faculty of Mathematics, University of Belgrade

Darko Trifunović, Faculty of Security Studies, University of Belgrade

Research Assistant Professor

Security Studies Institute

Faculty of Security Studies, University of Belgrade

Veselin Veljović, Faculty of Security Studies, University of Belgrade

PhD student

Faculty of Security Studies, University of Belgrade

Downloads

Published

2017-03-13

Issue

Vol. 46 No. 1 (2017)

Section

Articles

License

Copyright terms are indicated in the Republic of Lithuania Law on Copyright and Related Rights, Articles 4-37.