An Efficient Solution Approach for the p -Median Problems with Spatially Autocorrelated Weights

Datos Bibliográficos

ID8135877
AutoresHyun Kim (0000-0002-7637-678X, University of Tennessee at Knoxville, autor de correspondencia), Yongwan Chun (0000-0002-4957-1379, The University of Texas at Dallas), Daniel A Griffith (0000-0001-5125-6450, The University of Texas at Dallas)
Año2026
Páginas1-22
Fecha de publicación2026-03-16
Peer ReviewedSí
Open AccessNo
TipoARTICLE
RevistaAnnals of the American Association of Geographers (JOURNAL)
Identificadores de la revistaISSN: 2469-4452 • E-ISSN: 2469-4460
EditorialInforma UK Limited (PUBLISHER • GB)
DOI10.1080/24694452.2026.2636121
OpenAlexW7137239024
IdiomaEN
Referencias citadas44

The p-median problem (PMP) is a classical location-allocation problem that involves simultaneously determining the locations of facilities and allocating demand points (nonfacilities) in a discrete space. The PMP is known to be NP-hard. Given its wide applicability, obtaining optimal solutions for large instances, particularly when multiple optimal solutions exist, remains computationally challenging. Nevertheless, there is a continuing and considerable need for exact solution methods in empirical analyses involving the PMP, especially when the priority is to obtain exact solutions rather than compromising solution quality with heuristic approaches. This article proposes an efficient approach to solving the PMP by incorporating a prevailing spatial pattern of weights into the model formulation. This formulation, referred to as the spatial autocorrelation-informed p-median problem (PMP-SA), enables the use of spatial properties within the constraint sets to improve solution quality, especially for challenging instances. As an extension, adaptive PMP-SA methods are introduced for situations where obtaining reliable solution outcomes with incremental reductions in model complexity is critical, based on the behavior of the solution space as influenced by p. Compared with the standard PMP, both PMP-SA and adaptive PMP-SA demonstrate a superior capability to find optimal solutions and significantly reduce computational effort, highlighting this approach’s potential for more complex PMP applications.

Autocorrelation · Context (archaeology · Estimation · Field (mathematics · Process (computing · Advanced Optimization Algorithms Research · Facility Location and Emergency Management · Stochastic Gradient Optimization Techniques