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

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.

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

随着经济的高速发展，流水线工作显得尤为重要，尤其在选址过程中体现得也尤为明显。本项目对当今科技水平下的诸多现实问题进行抽象，得到了更为贴切的推广模型，在前人研究基础上加以创新和推广，提出了一些新型近似算法。本项目围绕多层设施选址问题中具有深刻现实意义的NP-难问题，从近似算法角度进行研究。研究的问题主要包括设施选址问题，图划分问题和DC-规划问等，取得了很好的研究成果。在研究上述问题过程中将不同问题的算法设计技巧相融合，对后续研究提供了更多的思路和启发。在本项目支持下共发表期刊论文15篇(其中SCI检索论文14篇)，会议论文2篇。.在设施选址问题方面，我们考了2-层设施选址问题的变形--带软容量的设施选址问题和鲁棒设施选址问题，得到原始对偶的(4+1/(e-1)+\epi)和(3+\epi)-近似算法。我们考虑软容量多层设施选址问题，利用线性规划舍入得到5.5053-近似算法。我们提出和研究了带惩罚的一般设施选址问题并设计了其7.88-近似算法, 随后此结果被我们改进到了5.83。 通过违背开设设施个数限制的要求，我们设计得到带惩罚的k-中位问题的(1+\sqrt_3+\epi)-近似算法。此外, 我们研究了多阶段设施选址问题，随机设施选址问题，容错设施选址问题，平方度量设施选址问题和k-设施选址问题等。.图划分问题方面，我们主要研究了极大k-非割问题的复杂性和近似算法以及利用谱分析方法讨论极大有向割问题的近似算法。 .在算法设计的技巧研究方面，我们讨论了非凸问题的DC-规划，将极大和极小的容错的度数集中生成子图问题分别利用DC-算法进行求解。.作为技巧的延伸，我们还研究了斯坦纳树和无关机排序的部分变形问题。