A spatial-knowledge-enhanced heuristic for solving the p-median problem

Wangshu Mu, Daoqin Tong

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


The p-median problem (PMP) is one of the most applied location problems in urban and regional planning. As an NP-hard problem, the PMP remains challenging to solve optimally, especially for large-sized problems. A number of heuristics have been developed to obtain PMP solutions in a fast manner. Among the heuristics, the Teitz and Bart (TB) algorithm has been found effective for finding high-quality solutions. In this article, we present a spatial-knowledge-enhanced Teitz and Bart (STB) heuristic method for solving PMPs. The STB heuristic prioritizes candidate facility sites to be examined in the solution set based on the spatial distribution of demand and service provision. Tests based on a range of PMPs demonstrate the effectiveness of the STB heuristic. This new algorithm can be incorporated into current commercial GIS packages to solve a wide range of location-allocation problems.

Original languageEnglish (US)
Pages (from-to)477-493
Number of pages17
JournalTransactions in GIS
Issue number2
StatePublished - Apr 2018

ASJC Scopus subject areas

  • General Earth and Planetary Sciences


Dive into the research topics of 'A spatial-knowledge-enhanced heuristic for solving the p-median problem'. Together they form a unique fingerprint.

Cite this