动态、鲁棒和容量约束设施选址的近似算法

发布时间：2022-08-13 09:56

　　设施选址问题在市政工程、电信领域、信息检索、供应链设计等方面有广泛的应用,从上个世纪六十年代以来一直是组合优化领域中的热点问题.最经典的是无容量设施选址问题,具体地,给出位置确定的设施集合和位置确定的顾客集合,每个设施有相应的开设费用,顾客和设施之间有连接费用,目标是确定一些设施开设,将顾客连接到开设的设施上,使得开设设施的费用与连接费用之和最小.由于设施选址问题是NP-难的,设计精确算法计算时间无法保证.启发式算法虽然能在较短的时间内得到可行解,但问题解决过程中容易陷入局部最优,不能通过理论分析得到近似比,一般情况下也很难得到最优解.因此,大部分研究采用设计近似算法解决问题.设施选址问题应用广泛,各种变形问题发展势头强劲,例如k-中位问题,带有容量的设施选址问题,鲁棒设施选址问题,随机设施选址问题,k-层设施选址问题等.本论文研究了几类设施选址问题,介绍数学模型,设计近似算法并给出算法的理论分析.设施选址问题中,当容量约束和开设设施基数约束同时出现时,问题变得复杂,目前没有常数近似算法.论文首先对非一致软容量k-设施选址问题进行研究,利用拉格朗日松弛技巧和随机算法得到该问题容量违反的... 

【文章页数】：87 页

【学位级别】：博士

【文章目录】：
摘要
Abstract
第1章 绪论
    1.1 研究背景
    1.2 国内外研究历史和现状
    1.3 基本知识
    1.4 主要结果
    1.5 论文结构
第2章 软容量k-设施选址问题
    2.1 数学模型
    2.2 预备知识
    2.3 算法与分析
    2.4 本章小结
第3章 平方度量动态设施选址问题
    3.1 数学模型
    3.2 算法及分析
    3.3 提高的算法与分析
    3.4 本章小结
第4章 鲁棒动态设施选址问题
    4.1 数学模型
    4.2 算法与分析
    4.3 提高的算法与分析
    4.4 本章小结
第5章 平方度量带下界的半径和问题
    5.1 数学模型
    5.2 松弛问题算法与分析
    5.3 原问题的算法与分析
    5.4 本章小结
结论
参考文献
攻读博士学位期间发表的学术论文
致谢


【参考文献】：
期刊论文
[1]设施选址问题的近似算法综述[J]. 徐大川,杜东雷,吴晨晨.  数学进展. 2014(06)



本文编号：3676813