机动设施选址问题及其变形的近似算法研究

Facility location problems have received a great deal of attention in the operations research and computer science communities, and have a wide range of applications in combinatorial optimization, network optimization, supply chain management, logistics, and machine learning. In the mobile facility location problem, which is a variant of the classical facility location, each facility and client is assigned to a start location in a metric graph. The goal is to move each facility from its initial location to a destination and assign each client to the destination of some facility so as to minimize the sum of the movement-costs of the facilities and the client-assignment costs. On the one hand, based on a series of improved algorithms for facility location problem and k-median problem, we explore the approximation algorithm for mobile facility location problem from multiple perspectives, to obtain high quality solutions, by LP-rounding, primal-dual, dual fitting, greedy augmentation, and local search scheme etc. On the other hand, we consider a more general version in which there is a weight associated with each facility. Furthermore, we introduce the concepts of penalties, priority and game, to study three variants of the mobile facility location problem, which are both theoretically interesting and have applications in real world. The results of this research can not only enrich the theoretical methods of combinatorial optimization, but also have important application values.

设施选址问题是运筹学和计算机领域十分关注的问题，广泛应用于组合优化，网络优化，供应链管理，物流以及机器学习中。本项目研究的机动设施选址问题是经典设施选址问题的变形，给定一个可度量的图，每一个设施和顾客都被配置在一个初始点上。目标是将每一个设施从初始点移动到终点，并将每一个顾客连接到某设施的终点，使得设施的移动费用和顾客的连接费用之和最小。一方面，我们在设施选址问题及k-中位问题一系列改进的算法思想基础上，采用线性规划舍入、原始对偶、对偶拟合、贪婪增广、局部搜索等技巧，探索从多个角度设计机动设施选址问题的近似算法，得到高质量的解。另一方面，我们将研究机动设施选址问题更一般的形式，即每个设施都有一个权重。进一步，我们引入惩罚，优先和博弈的概念，研究了机动设施选址问题的三个变形，理论上很有趣，在实际中也有应用。本项目的研究结果不仅能够丰富组合最优化的理论方法，而且有着重要的应用价值。

在经典设施选址模型框架下，学者们针对一些实际应用背景中的选址问题，通过设置不同的条件进行了进一步扩展，从而发展了各种设施选址变形问题，这些问题一直是组合优化领域理论研究的热点问题。本项目研究了基于不同应用背景的机动设施选址及其相关问题，探索了采用不同的技巧设计近似算法求解问题，并对算法的复杂性、近似比进行理论分析证明。从问题模型、算法与分析三方面入手，以整数规划、近似算法等组合优化的理论/方法为基础，将机动设施选址问题相关算法思想及技巧在带惩罚的k层设施选址博弈问题，带起点和终点的设施选址问题，共享单车站点选址问题，基于动态规划的导航误差修正路径规划问题，带转弯半径约束条件下的可行路径计算问题，背包约束的单调非次模函数的最大化问题，流场景下带基数约束的正则次模最大化问题等方面进行了拓展并取得了预期研究结果，进一步丰富和完善了选址问题的应用场景和计算方法。项目共发表论文8篇，项目执行期间营造了良好的组合优化应用基础理论创新研究生态圈。