The p-Median Problem - Location Science - page 20

Chapter 2
The p -Median Problem

Mark S. Daskin and Kayse Lee Maass

Abstract The p -median problem is central to much of discrete location modeling
and theory. While the p -median problem is -hard on a general graph, it can

be solved in polynomial time on a tree. A linear time algorithm for the 1-median
problem on a tree is described. We also present a classical formulation of the
problem. Basic construction and improvement algorithms are outlined. Results
from the literature using various metaheuristics including tabu search, heuristic
concentration, genetic algorithms, and simulated annealing are summarized. A
Lagrangian relaxation approach is presented and used for computational results on
40 classical test instances as well as a 500-node instance derived from the most
populous counties in the contiguous United States. We conclude with a discussion
of multi-objective extensions of the p -median problem.

NP

Keywords Algorithm ￿ Center ￿ Covering ￿ Lagrangian relaxation ￿ Median ￿
Multi-objective

2.1 Introduction

The p -median problem is that of locating p facilities to minimize the demand
weighted average distance between demand nodes and the nearest of the selected
facilities. The problem dates back to the seminal work of Hakimi ( 1964 , 1965 ). The
p -median problem is one of several classical location problems which also include
the capacitated and uncapacitated facility location problems (Chap. 3 ) , the p -center
problem (Chap. 4 ) , covering problems (Chap. 5 ) and anti-covering problems (Chap.
6 ) . The p -median problem lies at the heart of many practical location problems, and,
as shown below (Sect. 2.7 ), some of the other classical location problems can readily
be formulated as p -median problems, leading to multicriteria location problems as
outlined in Chap. 9 .
Our objective is not to review every paper and every result related to this seminal
problem. Rather, we summarize key results, algorithms and important extensions.