κ-层有容量约束设施选址问题的近似算法

摘要

本论文考虑k-层有容量约束设施选址问题，此问题为NP-难问题.k-层有容量设施选址问题具有一般性，经典的无容量约束设施选址问题、1-层有容量约束设施选址问题和k-层无容量约束设施选址问题都是该问题的特殊情况.在论文中，关于1-层有容量约束设施选址问题介绍了多交换局部搜索算法和线性规划舍入算法(针对所有设施的开设费用都相等的特例)；关于k-层无容量约束设施选址问题介绍了参数路径贪婪退化算法、分裂递归路径算法和随机舍入算法. 在论文中，给出了k-层有容量约束设施选址问题的第一个(组合的)近似算法.在算法设计过程中，首先，根据给定的k-层有容量约束设施选址问题构造一个特殊的1-层有容量约束设施选址问题和一个特殊的(k-1)-层有容量约束设施选址问题；其次，通过调用多交换局部搜索算法给出1-层有容量约束设施选址问题的一个可行解，递归地解得(k-1)-层有容量约束设施选址问题的一个可行解；然后，通过解运输问题求得需求从第一层设施集合到路径集合的指派；最后，构造出原问题的一个可行解.在算法分析中，通过递归法给出近似比k+2+√k2+2k+5+5+ε(ε>0）

目录

文摘

英文文摘

声明

第1章 绪论

1.1基本概念

1.2k-层有容量约束设施选址问题

1.3国内外研究现状

1.4论文结构

第2章 两类设施选址问题的算法介绍

2.1 1-层有容量约束设施选址问题

2.1.1多交换局部搜索算法

2.1.2线性规划舍入算法

2.2k-层无容量约束设施选址问题

2.2.1参数路径贪婪退化算法

2.2.2分裂递归路径算法

2.2.3随机舍入算法

2.3本章小结

第3章 k-层有容量约束设施选址问题

3.1算法

3.2算法分析

3.3本章小结

结论

参考文献

攻读硕士学位期间所发表的论文

致谢