The complete vertex p-center problem

The vertex p-center problem consists of locating p facilities among a set of\nM potential sites such that the maximum distance from any demand to its closest\nlocated facility is minimized. The complete vertex p-center problem solves the\np-center problem for all p from 1 to the total number of sites, resulting in a\nmulti-objective trade-off curve between the number of facilities and the\nservice distance required to achieve full coverage. This trade-off provides a\nreference to planners and decision-makers, enabling them to easily visualize\nthe consequences of choosing different coverage design criteria for the given\nspatial configuration of the problem. We present two fast algorithms for\nsolving the complete p-center problem, one using the classical formulation but\ntrimming variables while still maintaining optimality, the other converting the\nproblem to a location set covering problem and solving for all distances in the\ndistance matrix. We also discuss scenarios where it makes sense to solve the\nproblem via brute-force enumeration. All methods result in significant\nspeed-ups, with the set covering method reducing computation times by many\norders of magnitude.\n