The complete vertex p -center problem
- PDF / 888,125 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 15 Downloads / 187 Views
The complete vertex p‑center problem F. Antonio Medrano1 Received: 1 October 2019 / Accepted: 10 July 2020 © The Association of European Operational Research Societiesand Springer-Verlag GmbH Berlin Heidelberg 2020
Abstract The vertex p-center problem consists of locating p facilities among a set of M potential sites such that the maximum distance from any demand to its closest located facility is minimized. The complete vertex p-center problem solves the p-center problem for all p from 1 to the total number of sites, resulting in a multi-objective trade-off curve between the number of facilities and the service distance required to achieve full coverage. This trade-off provides a reference to planners and decision makers, enabling them to easily visualize the consequences of choosing different coverage design criteria for the given spatial configuration of the problem. We present two fast algorithms for solving the complete p-center problem: one using the classical formulation but trimming variables while still maintaining optimality and the other converting the problem to a location set covering problem and solving for all distances in the distance matrix. We also discuss scenarios where it makes sense to solve the problem via brute-force enumeration. All methods result in significant speedups, with the set covering method reducing computation times by many orders of magnitude. Keywords p-Center · Facility location · Location set covering · Spatial optimization · Location-allocation · Mathematical programming Mathematics Subject Classification 90C10 · 90C11 · 90C27 · 90C90
1 Introduction Let N be the set of discrete demands to be served, represented by the index i = 1, 2, …, n. Let M be the set of discrete potential facility sites that may serve those demands, represented by the index j = 1, 2, …, m. Let dij be the distance from * F. Antonio Medrano [email protected] 1
Conrad Blucher Institute for Surveying and Science, Department of Computing Sciences, Texas A&M University–Corpus Christi, 6300 Ocean Drive, Unit 5799, Corpus Christi, TX, USA
13
Vol.:(0123456789)
F. A. Medrano
demand i to site j. The vertex p-center problem consists of locating p facilities among a set of m potential sites such that the maximum distance from any demand to its closest located facility is minimized. This article considers the problem in the Euclidean space, where the “service distance” is a real number radius of coverage around the located facilities. The p-center (PC) problem was originally formulated by Hakimi (1964), and it is often used for equitable location of public services such as fire stations, police stations, ambulance depots (Daskin 2013; Marianov and ReVelle 1995; Shier 1977) since it minimizes the furthest distance of the service to any constituent. Variations include locating facilities anywhere in the Euclidean space (Drezner 1984), also known as the continuous or non-vertex problem; locating facilities on a network (Kariv and Hakimi 1979); covering continuous area demands rather than point de
Data Loading...
