多层设施选址问题的理论与算法研究

项目名称： 多层设施选址问题的理论与算法研究

项目编号： No.11501412

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

立项/批准年度： 2016

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

项目作者： 吴晨晨

作者单位： 天津理工大学

项目金额： 18万元

中文摘要： 设施选址问题是组合优化中最经典的问题之一，受到了专家学者的广泛关注。在设施选址问题中，顾客由一个开设的设施提供服务。在很多情况下，满足顾客的需求也许需要一系列的设施。这样就衍生出设施选址问题的一个重要变形——多层设施选址问题。这类问题在物流管理，应急管理，卫生保健等方面有着重要的应用。除了增加多层约束的变形外，设施选址问题还有其他的重要变形，例如带容量限制的设施选址问题，带惩罚的设施选址问题，k-设施选址问题等等。这些变形都可以看做在设施选址问题的基础上对设施或顾客增加了某一类约束。而随着经济和社会的高速发展，实际生产中出现了更多具有复杂结构的问题。本项目考虑经典的多层设施选址问题及具有不同网络结构的变形问题。本项目研究上述NP-困难问题快速有效的近似算法。在这类算法中不要求找到问题的最优解而是可行解并分析二者之间的比值。

中文关键词： 近似算法；设施选址问题；原始对偶；线性规划舍入；局部搜索

英文摘要： Facility location problem (FLP) is one of the most classical problems in combinatorial optimization which has been investigated extensively by many experts. In the FLP, the demand of each client is satisfied by an opened facility. However, the demand of the client maybe satisfied by a series of facilities in some practical situations. This incurs an important variant of the FLP, namely the multi-level FLP, in which the facilities form a hierarchy of multi levels, and a facility path consists of exactly one facility from each level in the hierarchical order from the lowest to the highest level. The objective is to open a subset of facilities in each level and connect every client to an open path (a facility path consisting of only open facilities) such that the total cost of opening facilities and connecting clients is minimized. The multi-level FLP has lots of applications in several fields including logistics management, emergency management, health care etc. Besides the multi-level facility location, facility location problem also has other variants such as capacitated facility location problem, facility location problem with penalties, k-facility location problem. Each of these variants can be viewed as the FLP equipped with one extra constraint on facilities or clients. The rapid economic and social development involves many FLPs with complicated structure. We focus the research on the classical multi-level facility location problem and the corresponding various variants which capture different network construction. Since the facility location problem is NP-hard, the problems we considered are also NP-hard generally. We will design rapid efficient approximation algorithms to handle these problems. For each problem, the approximation algorithm outputs a feasible solution instead of the optimal solution, and the ratio between the values of them can be quantified using several techniques.

英文关键词： approximation algorithm;facility location problem;primal-dual;linear programming rounding;local search