设施选址问题基于线性规划的近似算法研究

项目名称： 设施选址问题基于线性规划的近似算法研究

项目编号： No.11201013

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 李改弟

作者单位： 北京工业大学

项目金额： 22万元

中文摘要： 设施选址问题是组合优化领域一个重要的模型，在运筹学、计算机科学、库存管理等方面都有广泛的应用。本项目主要采用线性规划舍入、原始对偶和dual-fitting算法研究设施选址问题的三个变形。拟研究的主要内容有：1.拟采用线性规划舍入方法，设计出新的选择cluster中心的算法，降低非cluster中心顾客的连接费用，改进k-层无容量设施选址问题的近似比3;基于Gabor & van Ommeren对k-层无容量设施选址问题提出的新模型，采用dual-fitting和原始对偶技巧，改进组合算法最好的近似比3.27；采用原始对偶算法，改进k-层集中器选址问题的近似比。2.容错设施选址问题常数近似比的组合算法的设计；相同需求容错设施选址问题的近似比的改进。3.研究凹设施选址问题的线性规划舍入算法；仓库零售商网络设计博弈和随机运输库存网络设计博弈的单调费用分摊算法。

中文关键词： 仓库零售网络；次模惩罚；设施选址；近似算法；费用分摊

英文摘要： Facility locaiton, a central problem in combinatorial optimization, has wide applications in the operations research,computer science and inventory management. This project proposes investiagting three variants of the classical facility location problem by LP-rounding, primal-dual and dual-fitting techniques. These variants inlcude: (1)k-level facility location problem. Firstly, the project proposes using an new LP-rounding method to select cluster center to reduce the connection cost of non-cluster center, with the aim to improve the previously best approximation ratio of 3. Moreover, we also investigate an new k-level facility location model introduced by Gabor & van Ommeren. We propose adopting the dual-fitting or the primal-dual method to improve the previous best combinatorial approximation ratio of 3.27. Finally, the project will also investigate whether it is possible to apply the primal-dual method to the k-level concentrator location problem. (2)Fault-tolerant facility location problem. The project proposes designing an constant-factor combinatorial approximation algorithm for this problem. In adddition, the project also proposes improving the approximation factor for the fault-tolerant facility location problem with uniform requirements.(3) Concave facility location problem and its application. The p

英文关键词： Warehouse- retailer network；Submodular penalties；facility location；approximation algorithm；cost-sharing