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.