论文摘要
由于设施选址问题是经典的NP-难问题之一,主要从近似算法的角度对带惩罚的优先设施选址问题进行了研究,该问题是设施选址问题的变形问题之一.介绍了两类变形问题.在带惩罚的设施选址问题中,允许某些顾客的需求不被满足,对需求没有被满足的顾客,将会造成一定的损失,即惩罚费用.在优先设施选址问题中,每个顾客都有一定的服务水平要求,并且每个设施的开设费用是关于服务水平的递增函数,与顾客相连接的设施必须是开设的且能够满足顾客的服务水平要求.结合上述两类设施选址问题,研究了带惩罚的优先设施选址问题,该问题中,既有惩罚费用,又有服务水平要求.问题的的目标是寻找一个方案：选择开设某些设施,且选择被惩罚的顾客,将未被惩罚的顾客连接到一个能够满足其服务水平要求的开设设施上,使得设施开设费用,顾客与设施之间的连接费用以及顾客的惩罚费用之和最小.针对该问题的特殊结构,对设施进行适当排序,设计了基于原始对偶技巧的近似算法,分析得到了近似比3；应用贪婪增广技巧,将设施开设费用按比例扩大,并对每个顾客添加了一个开设费用0的设施,将惩罚费用转化为连接费用,设计了改进的算法,将近似比3改进到了1.8526.
论文目录
相关论文文献
- [1].考虑不可行区域的重心法选址问题研究[J]. 河南科技 2020(05)
- [2].鲁棒动态设施选址问题的近似算法[J]. 运筹与管理 2020(05)
- [3].中山陵选址问题释疑[J]. 江淮文史 2016(05)
- [4].基于遗传算法解决配送企业的选址问题的探索[J]. 福建质量管理 2015(12)
- [5].考虑失灵风险的可靠性设施选址问题综述[J]. 重庆工商大学学报(自然科学版) 2016(02)
- [6].供应链系统节点设施选址问题研究[J]. 内蒙古科技与经济 2016(15)
- [7].考虑道路中断的医疗设施选址问题研究[J]. 商 2016(31)
- [8].需求导向的容量设施竞争选址问题研究[J]. 运筹与管理 2019(10)
- [9].带补偿机制的垃圾焚烧厂选址问题研究[J]. 数学的实践与认识 2015(06)
- [10].搬家公司的选址问题[J]. 数学学习与研究 2011(09)
- [11].欧氏平面上的占线中位选址问题分析[J]. 管理科学学报 2014(09)
- [12].竞争环境下的截流选址问题[J]. 商 2012(05)
- [13].设施选址问题中的基础模型与求解方法比较[J]. 北京联合大学学报(自然科学版) 2012(03)
- [14].带惩罚的动态设施选址问题的近似算法[J]. 应用数学学报 2009(06)
- [15].数学建模实例——河西学院校内充电站最佳选址问题[J]. 智库时代 2020(03)
- [16].应急物流多目标选址问题研究[J]. 时代金融 2017(26)
- [17].覆盖类选址问题分类及研究综述[J]. 物流科技 2015(03)
- [18].设施选址问题的近似算法综述[J]. 数学进展 2014(06)
- [19].零售商竞争选址问题探讨[J]. 商业时代 2012(08)
- [20].垃圾站选址问题的数学模型及应用[J]. 物流技术 2011(23)
- [21].基于最速下降法的平面选址问题应用研究[J]. 科技资讯 2011(36)
- [22].基于遗传算法的单点物流选址问题探析[J]. 物流工程与管理 2010(07)
- [23].竞争与合作设施并存的最大覆盖选址问题[J]. 武汉理工大学学报(信息与管理工程版) 2010(04)
- [24].时变环境下选址问题的一个启发式算法[J]. 物流工程与管理 2008(11)
- [25].最大覆盖选址问题的一种降阶回溯算法[J]. 系统管理学报 2020(01)
- [26].限制设施选址问题的近似算法[J]. 计算机工程与科学 2013(04)
- [27].灾后重建地区新增血站的选址问题研究[J]. 运筹与管理 2012(01)
- [28].一种采购中心选址问题的研究[J]. 沈阳师范大学学报(自然科学版) 2011(01)
- [29].关于工厂选址问题模型的讨论[J]. 科技信息 2011(28)
- [30].税务缴费多点选址问题研究[J]. 常州信息职业技术学院学报 2011(06)