| 带有异常点的平方度量设施选址问题 |
| |
| 引用本文： | 任建峰,田晓云.带有异常点的平方度量设施选址问题[J].运筹学学报,2021,25(1):114-122. |
| |
| 作者姓名： | 任建峰 田晓云 |
| |
| 作者单位： | 1. 曲阜师范大学管理学院、运筹学研究院, 山东日照 276826 |
| |
| 基金项目： | 山东省自然科学基金(Nos.ZR2014AM012,ZR2017MA031,ZR2019MA061);山东省高等学校科技计划(No.XKJ201315);国家自然科学基金(No.11771251)。 |
| |
| 摘 要： | 传统的设施选址问题一般假设所有顾客都被服务，考虑到异常点的存在不仅会增加总费用（设施的开设费用与连接费用之和），也会影响到对其他顾客的服务质量。研究异常点在最终方案中允许不被服务的情况，称之为带有异常点的平方度量设施选址问题。该问题是无容量设施选址问题的推广。问题可描述如下：给定设施集合、顾客集，以及设施开设费用和顾客连接费用，目标是选择设施的子集开设以满足顾客的需求，使得设施开设费用与连接费用之和最小。利用原始对偶技巧设计了近似算法，证明了该算法的近似比是9。
|
| 关 键 词： | 异常点 设施选址 近似算法 原始对偶算法 NP-难 |
| 收稿时间： | 2018-11-19 |
Squared metric facility location problem with outliers |
| |
| REN Jianfeng,TIAN Xiaoyun.Squared metric facility location problem with outliers[J].OR Transactions,2021,25(1):114-122. |
| |
| Authors: | REN Jianfeng TIAN Xiaoyun |
| |
| Institution: | 1. Institute of Operations Research, School of Management, Qufu Normal University, Rizhao 276826, Shandong, China |
| |
| Abstract: | |
| |
| Keywords: | outliers facility location approximation algorithm primal-dual scheme NP-Hard |
| 本文献已被 CNKI 维普 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
