-
题名鲁棒动态设施选址问题的近似算法
被引量:2
- 1
-
-
作者
吴晨晨
王丽
徐春明
徐大川
-
机构
南开大学商学院
天津理工大学理学院
北京工业大学数学学院
-
出处
《运筹与管理》
CSSCI
CSCD
北大核心
2020年第5期61-66,共6页
-
基金
国家自然科学基金资助项目(11971349,11871081)
教育部人文社会科学研究基金(19YJC630188)。
-
文摘
设施选址问题是组合优化中重要问题之一。动态设施选址问题是传统设施选址问题的推广,其中度量空间中设施的开设费用和顾客的需求均随着时间的变化而变化。更多地,经典设施选址问题假设所有的顾客都需要被服务。在这个模型假设下,所有的顾客都需要服务。但事实上,有时为服务距离较远的顾客,需要单独开设设施,导致了资源的浪费。因此,在模型设置中,可以允许一些固定数目的顾客不被服务(带异常点的设施选址问题),此外也可以通过支付一些顾客的惩罚费用以达到不服务的目的(带惩罚的设施选址问题)。本文将综合以上两种鲁棒设置考虑同时带有异常点和惩罚的动态设施选址问题,通过原始-对偶框架得到近似比为3的近似算法。
-
关键词
动态设施选址问题
近似算法
原始对偶算法
-
Keywords
dynamic facility location problem
approximation algorithm
primal-dual algorithm
-
分类号
O221.7
[理学—运筹学与控制论]
-
-
题名带惩罚的动态设施选址问题的近似算法
被引量:4
- 2
-
-
作者
姜春艳
徐大川
-
机构
武警学院基础部
北京工业大学应用数理学院
-
出处
《应用数学学报》
CSCD
北大核心
2009年第6期988-996,共9页
-
基金
国家自然科学基金(60773185)资助项目
-
文摘
本文研究带惩罚的动态设施选址问题,在该问题中假设不同时段内设施的开放费用、用户的需求及连接费用可以不相同,而且允许用户的需求不被满足,但是要有惩罚.对此问题我们给出了第一个近似比为1.8526的原始对偶(组合)算法.
-
关键词
动态设施选址问题
线性规划
近似算法
-
Keywords
dynamic facility location problem
linear programming
approximation algorithm
-
分类号
O221.7
[理学—运筹学与控制论]
-
-
题名软容量约束的动态设施选址问题的近似算法
- 3
-
-
作者
姜春艳
李改弟
-
机构
武警学院基础部
北京工业大学应用数理学院
-
出处
《系统科学与数学》
CSCD
北大核心
2012年第4期476-484,共9页
-
基金
国家自然科学基金(11071268)
北京市教育委员会科技计划面上项目(KM201210005033)资助课题
-
文摘
考虑软容量约束的动态设施选址问题.假设设施的开放费用及连接费用都与时间有关,而且每一个设施均有容量约束.对此问题给出了第一个近似比为6的原始对偶(组合)算法.运行贪婪增加程序后,近似比进一步改进到3.7052.
-
关键词
软容量约束动态设施选址问题
对偶
近似算法
-
Keywords
Soft-capacitated dynamic facility location problem, dual, approximation algorithm.
-
分类号
O224
[理学—运筹学与控制论]
-