Two lower-bounding algorithms for the p-center problem in an area
Author:
Open Access
- 24 January 2022
- journal article
- research article
- Published by Springer Nature in Computational Urban Science
- Vol. 2 (1) , 1-19
Abstract
The p-center location problem in an area is an important yet very difficult problem in location science. The objective is to determine the location of p hubs within a service area so that the distance from any point in the area to its nearest hub is as small as possible. While effective heuristic methods exist for finding good feasible solutions, research work that probes the lower bound of the problem’s objective value is still limited. This paper presents an iterative solution framework along with two optimization-based heuristics for computing and improving the lower bound, which is at the core of the problem’s difficulty. One method obtains the lower bound via solving the discrete version of the Euclidean p-center problem, and the other via solving a relatively easier clustering problem. Both methods have been validated in various test cases, and their performances can serve as a benchmark for future methodological improvements.Keywords
Funding Information
- Division of Civil, Mechanical and Manufacturing Innovation (1944068)
This publication has 64 references indexed in Scilit:
- GloMIQO: Global mixed-integer quadratic optimizerJournal of Global Optimization, 2012
- Covering problems in facility location: A reviewComputers & Industrial Engineering, 2012
- Variable neighbourhood search: methods and applications4OR, 2008
- Minimum-Cost Load-Balancing PartitionsAlgorithmica, 2007
- A Continuous Location-Allocation Problem with Zone-Dependent Fixed CostAnnals of Operations Research, 2005
- Heuristic solution of the multisource Weber problem as a p-median problemOperations Research Letters, 1998
- Tabu search for large location–allocation problemsJournal of the Operational Research Society, 1997
- Approximation Algorithms for NP-Hard ProblemsACM SIGACT News, 1997
- Solving the Continuous p-Dispersion Problem Using Non-linear ProgrammingJournal of the Operational Research Society, 1995
- The Weber Problem: Solution and Interpretation*Geographical Analysis, 1972