不确定设施选址问题的理论与算法研究

设施选址问题是运筹学的核心问题之一，该问题是NP难解的，设计近似算法是处理该问题的有效途径之一。工厂，配送中心，及其他设施通常运行若干年或更长，在这期间运作环境可能会发生实质的变化。经典的设施选址模型里的费用，需求，运输时间，及其他参数都可能变得高度不确定。由此引起计算机科学、管理和运筹界的一些专家对不确定设施选址问题的研究兴趣。对于不确定设施选址问题已经有了相当多的处理技巧。我们主要关注随机和鲁棒设施选址模型的近似算法。确定型设施选址问题近似算法的研究技巧非常丰富，可以为不确定型问题提供研究工具。设施选址问题里的模型众多，如：经典的度量无容量约束的单层设施选址问题，多层设施选址问题，有容量约束的设施选址问题，有服务安装费用的设施选址问题，单层设施选址对策问题，多层设施选址对策问题，容错设施选址问题等。相应的不确定型问题都值得我们去研究。

设施选址问题是运筹学问题中的重要问题之一. 实际问题中, 不确定因素随处可见, 不确定性设施选址问题受到了大量专家学者的关注. 确定和不确定设施选址问题均为NP-困难问题. 近似算法是解决此类问题的重要手段之一. 本项目研究确定和不确定设施选址问题及其相关问题的近似算法. 在不确定设施选址问题中, 两阶段随机设施选址问题是常见的一类, 在这类问题中，顾客的分布是已知的，问题的随机性转化为场景及该场景出现的概率. .我们给出了带次模惩罚的设施选址问题的原始对偶3-近似算法，该算法提出了在对偶上升过程中处理次模结构的技巧，具有很强的移植性. 沿用该算法的思想, 我们分别给出了带次模惩罚的随机设施选址问题，仓库-零售商网络设计问题，以及随机运输-库存网络设计问题 的原始对偶3-近似算法. 利用对偶拟合技巧，我们给出了仓库-零售商网络设计问题的1.861-近似算法. 在仓库-零售商网络设计问题中限制开设仓库的个数不超过k, 则得到k-中心仓库-零售商网络设计问题, 我们利用仓库-零售商网络设计问题的原始对偶算法以及算法的拉格朗日乘子保持性质, 得到了k-中心仓库-零售商网络设计问题的6-近似算法. 我们提出了带次模惩罚的仓库零售商问题, 并给出原始对偶3-近似算法. 基于线性规划舍入的技巧, 我们对带线性惩罚的设施选址问题和次模惩罚的设施选址问题分别得到了1.5148和2-近似算法..在随机设施选址问题的基础上, 可以增加不同的约束得到新的变形. 如果顾客的需求是分等级的,这类问题称为随机优先设施选址问题，我们给出了原始对偶3-近似算法. 如果顾客需要连接到多个设施上, 这类问题称为随机容错设施选址问题, 我们得到了线性规划舍入5-近似算法. 对于随机设施选址问题，近似比估计的是算法在平均意义下所得解的质量，单场景界可以估计每个场景下解的质量，我们给出了带线性惩罚的随机设施选址问题的基于线性规划舍入的3.0294单场景界．