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!
cited_by cdi_FETCH-LOGICAL-c3372-161034e35dd020e93013eda83ede2e919478ef4dbf36d038b8402c0c1ce1b74a3
cites cdi_FETCH-LOGICAL-c3372-161034e35dd020e93013eda83ede2e919478ef4dbf36d038b8402c0c1ce1b74a3
container_end_page 493
container_issue 2
container_start_page 477
container_title Transactions in GIS
container_volume 22
creator Mu, Wangshu
Tong, Daoqin
description 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.
doi_str_mv 10.1111/tgis.12322
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2027122252</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2027122252</sourcerecordid><originalsourceid>FETCH-LOGICAL-c3372-161034e35dd020e93013eda83ede2e919478ef4dbf36d038b8402c0c1ce1b74a3</originalsourceid><addsrcrecordid>eNp9kLFOwzAQhi0EEqWw8ASR2JBSfLYbJ2NVQalUxECZLSe-tC5pEuyUqhuPwDPyJLiEmRvu_uG7-08_IddARxDqrltZPwLGGTshAxCJjLNEwmnQPIEYkpSdkwvvN5RSITI5IE-TyLe6s7r6_vx6q5t9hWaFQWO91nWBJlrjzlnf2SIqGxf5pvqw9Srq1hi1AduisbqOWtfkFW4vyVmpK49Xf3NIXh_ul9PHePE8m08ni7jgXLLwB1AukI-NoYxixilwNDoNDRlmkAmZYilMXvLEUJ7mqaCsoAUUCLkUmg_JTX83-L7v0Hdq0-xcHSwVo0wCY2zMAnXbU4VrvHdYqtbZrXYHBVQd41LHuNRvXAGGHt7bCg__kGo5m7_0Oz8X8m_V</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2027122252</pqid></control><display><type>article</type><title>A spatial‐knowledge‐enhanced heuristic for solving the p‐median problem</title><source>EBSCOhost Business Source Ultimate</source><source>Wiley</source><creator>Mu, Wangshu ; Tong, Daoqin</creator><creatorcontrib>Mu, Wangshu ; Tong, Daoqin</creatorcontrib><description>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.</description><identifier>ISSN: 1361-1682</identifier><identifier>EISSN: 1467-9671</identifier><identifier>DOI: 10.1111/tgis.12322</identifier><language>eng</language><publisher>Oxford: Blackwell Publishing Ltd</publisher><subject>Geographical distribution ; Geographical information systems ; Heuristic ; Heuristic methods ; Mathematical models ; Problem solving ; Problems ; Regional planning ; Solutions ; Spatial distribution</subject><ispartof>Transactions in GIS, 2018-04, Vol.22 (2), p.477-493</ispartof><rights>2018 John Wiley &amp; Sons Ltd</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c3372-161034e35dd020e93013eda83ede2e919478ef4dbf36d038b8402c0c1ce1b74a3</citedby><cites>FETCH-LOGICAL-c3372-161034e35dd020e93013eda83ede2e919478ef4dbf36d038b8402c0c1ce1b74a3</cites><orcidid>0000-0001-7005-5128</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27922,27923</link.rule.ids></links><search><creatorcontrib>Mu, Wangshu</creatorcontrib><creatorcontrib>Tong, Daoqin</creatorcontrib><title>A spatial‐knowledge‐enhanced heuristic for solving the p‐median problem</title><title>Transactions in GIS</title><description>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.</description><subject>Geographical distribution</subject><subject>Geographical information systems</subject><subject>Heuristic</subject><subject>Heuristic methods</subject><subject>Mathematical models</subject><subject>Problem solving</subject><subject>Problems</subject><subject>Regional planning</subject><subject>Solutions</subject><subject>Spatial distribution</subject><issn>1361-1682</issn><issn>1467-9671</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2018</creationdate><recordtype>article</recordtype><recordid>eNp9kLFOwzAQhi0EEqWw8ASR2JBSfLYbJ2NVQalUxECZLSe-tC5pEuyUqhuPwDPyJLiEmRvu_uG7-08_IddARxDqrltZPwLGGTshAxCJjLNEwmnQPIEYkpSdkwvvN5RSITI5IE-TyLe6s7r6_vx6q5t9hWaFQWO91nWBJlrjzlnf2SIqGxf5pvqw9Srq1hi1AduisbqOWtfkFW4vyVmpK49Xf3NIXh_ul9PHePE8m08ni7jgXLLwB1AukI-NoYxixilwNDoNDRlmkAmZYilMXvLEUJ7mqaCsoAUUCLkUmg_JTX83-L7v0Hdq0-xcHSwVo0wCY2zMAnXbU4VrvHdYqtbZrXYHBVQd41LHuNRvXAGGHt7bCg__kGo5m7_0Oz8X8m_V</recordid><startdate>201804</startdate><enddate>201804</enddate><creator>Mu, Wangshu</creator><creator>Tong, Daoqin</creator><general>Blackwell Publishing Ltd</general><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>F1W</scope><scope>FR3</scope><scope>H96</scope><scope>JQ2</scope><scope>KR7</scope><scope>L.G</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><orcidid>https://orcid.org/0000-0001-7005-5128</orcidid></search><sort><creationdate>201804</creationdate><title>A spatial‐knowledge‐enhanced heuristic for solving the p‐median problem</title><author>Mu, Wangshu ; Tong, Daoqin</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c3372-161034e35dd020e93013eda83ede2e919478ef4dbf36d038b8402c0c1ce1b74a3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2018</creationdate><topic>Geographical distribution</topic><topic>Geographical information systems</topic><topic>Heuristic</topic><topic>Heuristic methods</topic><topic>Mathematical models</topic><topic>Problem solving</topic><topic>Problems</topic><topic>Regional planning</topic><topic>Solutions</topic><topic>Spatial distribution</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Mu, Wangshu</creatorcontrib><creatorcontrib>Tong, Daoqin</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ASFA: Aquatic Sciences and Fisheries Abstracts</collection><collection>Engineering Research Database</collection><collection>Aquatic Science &amp; Fisheries Abstracts (ASFA) 2: Ocean Technology, Policy &amp; Non-Living Resources</collection><collection>ProQuest Computer Science Collection</collection><collection>Civil Engineering Abstracts</collection><collection>Aquatic Science &amp; Fisheries Abstracts (ASFA) Professional</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Transactions in GIS</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Mu, Wangshu</au><au>Tong, Daoqin</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A spatial‐knowledge‐enhanced heuristic for solving the p‐median problem</atitle><jtitle>Transactions in GIS</jtitle><date>2018-04</date><risdate>2018</risdate><volume>22</volume><issue>2</issue><spage>477</spage><epage>493</epage><pages>477-493</pages><issn>1361-1682</issn><eissn>1467-9671</eissn><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.</abstract><cop>Oxford</cop><pub>Blackwell Publishing Ltd</pub><doi>10.1111/tgis.12322</doi><tpages>17</tpages><orcidid>https://orcid.org/0000-0001-7005-5128</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1361-1682
ispartof Transactions in GIS, 2018-04, Vol.22 (2), p.477-493
issn 1361-1682
1467-9671
language eng
recordid cdi_proquest_journals_2027122252
source EBSCOhost Business Source Ultimate; Wiley
subjects Geographical distribution
Geographical information systems
Heuristic
Heuristic methods
Mathematical models
Problem solving
Problems
Regional planning
Solutions
Spatial distribution
title A spatial‐knowledge‐enhanced heuristic for solving the p‐median problem
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-14T10%3A06%3A55IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20spatial%E2%80%90knowledge%E2%80%90enhanced%20heuristic%20for%20solving%20the%20p%E2%80%90median%20problem&rft.jtitle=Transactions%20in%20GIS&rft.au=Mu,%20Wangshu&rft.date=2018-04&rft.volume=22&rft.issue=2&rft.spage=477&rft.epage=493&rft.pages=477-493&rft.issn=1361-1682&rft.eissn=1467-9671&rft_id=info:doi/10.1111/tgis.12322&rft_dat=%3Cproquest_cross%3E2027122252%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c3372-161034e35dd020e93013eda83ede2e919478ef4dbf36d038b8402c0c1ce1b74a3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2027122252&rft_id=info:pmid/&rfr_iscdi=true