Geoscience Reference
In-Depth Information
Chapter 4
p
-Center Problems
Hatice Calik, Martine Labbé, and Hande Yaman
Abstract
A p-center is a minimax solution that consists in a set of p points that
minimizes the maximum distance between a demand point and a closest point
belonging to that set. We present different variants of that problem. We review
special polynomial cases, determine the complexity of the problems and present
mixed integer linear programming formulations, exact algorithms and heuristics.
Several extensions are also reviewed.
Keywords
p-Center Location in public sector Minimax facility location
4.1
Introduction
Minimizing the total or average distance that potential users have to travel to reach a
facility may not be the right decision criterion for placing a public facility. Total- or
average distance minimization tends to favor clients who are clustered in population
centers to the detriment of clients who are spatially dispersed. Discrimination of this
kind with regard to accessibility may have a negative impact on remote clients in the
case of an emergency service (ambulances, fire brigades, police stations, etc.). As a
result, decision makers may want to consider a criterion focusing on clients who are
the poorest served.
