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

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

Full description

Saved in:
Bibliographic Details
Published in:Transactions in GIS 2018-04, Vol.22 (2), p.477-493
Main Authors: Mu, Wangshu, Tong, Daoqin
Format: Article
Language:English
Subjects:
Geographical distribution
Geographical information systems
Heuristic
Heuristic methods
Mathematical models
Problem solving
Problems
Regional planning
Solutions
Spatial distribution
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1361-1682
1467-9671
DOI:10.1111/tgis.12322