选址问题的算法设计与分析

选址问题是运筹学里的核心问题之一, 它来自于工厂，仓库，学校，医院等位置的确定问题，当今的应用包括网络上代理服务器，传感器的安置问题等。多层选址问题和多层选址对策在供应链管理中有非常重要的应用。选址问题是NP难解的，在组合优化学科中的绝大多数著名问题属于所谓的NP完备问题，除非P=NP,人们不可能对它们找到多项式时间的算法。我们采用近似算法来求解选址问题。选址问题的研究技巧非常丰富：包括局部搜索，贪婪算法，随机算法，过滤技巧，线性规划舍入，原始对偶程式，对偶装配, 线性规划揭示， 比例缩放等。选址问题模型众多：包括经典的度量无容量约束的单层选址问题，多层选址问题，有容量约束的选址问题，有服务安装费用的选址问题，单层选址对策问题，多层选址对策问题，Fault-Tolerant选址问题，在线选址问题，半在线选址问题，随机选址问题，极大形式的选址问题等。