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

Wangshu Mu; Daoqin Tong

doi:10.1111/tgis.12322

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

Wangshu Mu, Daoqin Tong

Research output: Contribution to journal › Article › peer-review

12 Scopus citations

Abstract

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 language	English (US)
Pages (from-to)	477-493
Number of pages	17
Journal	Transactions in GIS
Volume	22
Issue number	2
DOIs	https://doi.org/10.1111/tgis.12322
State	Published - Apr 2018

ASJC Scopus subject areas

General Earth and Planetary Sciences

Access to Document

10.1111/tgis.12322

Cite this

@article{f91ffa6e18d9417eba22b94e7519b219,

title = "A spatial-knowledge-enhanced heuristic for solving the p-median problem",

abstract = "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.",

author = "Wangshu Mu and Daoqin Tong",

note = "Publisher Copyright: {\textcopyright} 2018 John Wiley & Sons Ltd",

year = "2018",

month = apr,

doi = "10.1111/tgis.12322",

language = "English (US)",

volume = "22",

pages = "477--493",

journal = "Transactions in GIS",

issn = "1361-1682",

publisher = "Wiley-Blackwell",

number = "2",

}

TY - JOUR

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

AU - Mu, Wangshu

AU - Tong, Daoqin

PY - 2018/4

Y1 - 2018/4

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85042542558&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85042542558&partnerID=8YFLogxK

U2 - 10.1111/tgis.12322

DO - 10.1111/tgis.12322

M3 - Article

AN - SCOPUS:85042542558

SN - 1361-1682

VL - 22

SP - 477

EP - 493

JO - Transactions in GIS

JF - Transactions in GIS

IS - 2

ER -

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

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this