P-中位問題

P-中位問題是研究如何選擇P個服務站使得需求點和服務站之間的距離與需求量的乘積之和最小。

基本介紹

• 中文名：P-中位問題
• 外文名：p-median problems
• 也叫：P-中值問題
• 研究：如何選擇P個服務站

起源

Hakimi提出該問題之後給出了 P-中位問題的 Hakimi 特性，他證明了 P-中位問題的服務站候選點限制在網路節點上時至少有一個最優解是與不對選址點限制時的最優解是一致的，所以將網路連續選址的 P-中位問題簡化到離散選址問題不會影響到目標函式的最優值。Goldman給出了在樹和只有一個環的網路上為單個服務站選址中位問題的簡單算法。Miehle 於 1958 年也研究過平面1-中位問題，也就是Weber 問題，是他發現了 Weiszfeld 的研究成果，被選址-分配問題的里程碑文章 Cooper譽為 Weiszfeld 研究的發現者。對於空間 P-中位問題，也就是更一般的Weber 問題，Rosing提出了最優解法。Garey 和 Johnson證明了 P-中位問題是 NP-困難問題。Francis、Francis 和 Cabot、Chen以及 Chen 和 Handler研究了基於歐氏距離的 P-中位問題。

研究現狀

近年來，P-中位問題仍然是研究的熱點，許多學者研究 P-中位問題的各種變形和擴展模型：Wesolowsky 和ruscott、Drezner研究了動態 P-中位問題。ReVelle將目標函式定義為新建的服務站所占據的市場份額的最大化，成功地將中位問題運用於競爭環境下的零售商店選址問題中。Lorena、Senne和 Luiz 等運用列生成方法解決帶容量限制的 P-中位問題。Berman 等研究服務的可靠度隨著服務設施與需求的距離變化的設施問題問題。Church 提出了通過減少分配的變數來減少約束的傳統 P-中位問題的新建模方法。Drezner、Chen、Handler在此基礎上研究條件中位問題，又稱 PQ-中位問題，即網路中已存在 Q 個服務站的條件下，如何為 P 個同類服務站選址的中位問題。