The complete vertex p-center problem

F. Antonio Medrano ()
Additional contact information
F. Antonio Medrano: Texas A&M University–Corpus Christi

EURO Journal on Computational Optimization, 2020, vol. 8, issue 3, No 7, 327-343

Abstract: 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; 90C10; 90C11; 90C27; 90C90 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s13675-020-00131-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:eurjco:v:8:y:2020:i:3:d:10.1007_s13675-020-00131-y

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/13675

DOI: 10.1007/s13675-020-00131-y

Access Statistics for this article

EURO Journal on Computational Optimization is currently edited by Martine C. Labbé

More articles in EURO Journal on Computational Optimization from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().