The p-Median Problem - Location Science - page 43

2.8 Conclusions

The p -median problem is central to much of discrete location theory and modeling.
This chapter has outlined several important model properties and has reviewed a
classic formulation of the problem. While the problem is

-hardonageneral
graph, it can be solved in polynomial time on a tree. We summarized a linear-time
algorithm for the 1-median on a tree and cited results for the general p -median
problem on a tree. The chapter then presented classic construction and improvement
algorithms for the p -median problem and pointed the reader to literature on a
number of modern heuristic algorithms that have been employed in solving the
problem on general graphs. Computational results were presented for both the
classical Beasley datasets as well as a 500-node instance based on the most populous
counties in the contiguous United States. A well-constructed Lagrangian algorithm
embedded in a branch-and-bound algorithm can solve problem instances with up to
1,000 demand nodes and 1,000 candidate sites in reasonable time. (For p D 1
the myopic algorithm—which amounts to total enumeration in this case—will
find provably optimal solutions.) Larger problem instances may require the use of
heuristic algorithms such as tabu search or simulated annealing.
The chapter concluded with two multi-objective extensions of the p -median
problem. The first examines the tradeoff between the p -median objective and the
maximum covering objective, while the second explores the tradeoff between the p -
median objective and the p -center objective. For small instances it is often possible
to solve bi-objective problems using extensions of the Lagrangian algorithm
outlined above. For larger instances, using a genetic algorithm is often advisable
since the population of solutions in a genetic algorithm automatically gives an initial
approximation of the non-dominated set of solutions.

NP

References

Al-khedhairi A (2008) Simulated annealing metaheuristic for solving P-median problem. Int J
Contemporary Math Sci 3:1357-1365
Alp O, Erkut E, Drezner Z (2003) An efficient genetic algorithm for the p -median problem. Ann
Oper Res 122:21-42
Beasley JE (1990) OR-library: distributing test problems by electronic mail. J Oper Res Soc
41:1069-1072
Chiyoshi F, Galvão RD (2000) A statistical analysis of simulated annealing applied to the p -median
problem. Ann Oper Res 96:61-74
Church RL (2008) BEAMR: an exact and approximate model for the p -median problem. Comput
Oper Res 35:417-426
Church RL, ReVelle CS (1974) The maximal covering location problem. Pap Reg Sci Assoc
32:101-118
Cohon JL (1978) Multiobjective programming and planning. Academic, New York
Daskin MS (2013) Network and discrete location: models, algorithms and applications, 2nd edn.
Wiley, New York