The p-Median Problem

Mark S. Daskin () and Kayse Lee Maass ()
Additional contact information
Mark S. Daskin: University of Michigan
Kayse Lee Maass: University of Michigan

Chapter Chapter 2 in Location Science, 2015, pp 21-45 from Springer

Abstract: Abstract The p-median problem is central to much of discrete location modeling and theory. While the p-median problem is $$ \mathcal{N}\mathcal{P} $$ -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.

Keywords: Algorithm; Center; Covering; Lagrangian relaxation; Median; Multi-objective (search for similar items in EconPapers)
Date: 2015
References: Add references at CitEc
Citations: View citations in EconPapers (19)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:sprchp:978-3-319-13111-5_2

Ordering information: This item can be ordered from
http://www.springer.com/9783319131115

DOI: 10.1007/978-3-319-13111-5_2

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().