求解一类公平疏散问题的高性能混合算法研究

Equity dispersion problems are among classical NP-hard combinatorial optimization problems, with applications in locating dangerous devices, distribution of commercial franchises, multi-objective decision, etc. Although equity dispersion problems have many variations, no research of solving all these variations within one algorithm has been found in the literature. Based on developing a unified problem model, this project focuses on designing general high-performance hybrid metaheuristics, which is a hot and cutting-edge research topic within the current operation research society. In order to utilize complementary features of different algorithmic strategies, this project mainly works on the following aspects: (1) the hybrid of multiple neighborhood moves operators and multiple perturbation moves operators to improve the intensification and diversification of iterated tabu search algorithms; (2) the hybrid of iterated tabu search and path relinking algorithms, in which both the solution quality and distances between solutions are taken into consideration when building path and selecting path solutions to achieve the balance between intensification and diversification; (3) the hybrid of iterated tabu search and exact algorithms, in which efficient variable fixing techniques are developed to reduce the search area where exact algorithms search for solution improvement. The goal of this project is not only to solve equity dispersion problems quite effectively, but also to propose general hybrid mechanisms for solving other combinatorial optimization problems as well.

公平疏散问题是一类经典的NP困难问题，在危险设备选址、连锁店的位置分布、多目标决策等诸多领域有广泛的应用。公平疏散问题具有多个问题变种，目前尚未有研究对这些不同的问题进行统一建模求解。本课题将以构建一个统一的问题模型为基础，设计一类通用高效的混合算法。混合算法是当前运筹学领域的热点与前沿课题，为有效结合不同算法策略之间的互补特性，本课题将研究以下方面：（1）通过混合多种邻域移动算符和多种扰动算符， 提高迭代禁忌算法的集中搜索能力和疏散能力；（2）混合迭代禁忌算法和当前热点路径重链接算法，通过在建立路径和选择解时综合考虑解的质量和解之间的距离以获得搜索在集中性和疏散性上的平衡；（3）混合迭代禁忌算法和精确算法，通过有效的变量固定技术缩减搜索空间并利用精确算法提高解质量。本课题的研究不仅力求实现对一类公平疏散问题的高效求解，而且通用的算法混合机制也将对求解其它的组合优化问题具有很好的借鉴意义。

疏散问题是一类经典的组合优化问题，是运筹学及人工智能领域的研究重点之一。对于某些疏散问题，当其距离函数的定义考虑了元素之间的公平性时，该类疏散问题就通常被称为公平疏散问题。近几年来，公平疏散问题在实践中展现了重要的应用价值，引起了学者们的广泛关注。本课题以构建统一的问题模型为基础，有效结合不同算法策略之间的互补特性，研究一类公平疏散问题的高性能混合求解算法。研究成果主要包括：1）研究了公平疏散问题中的最小差疏散和最大平均疏散问题，设计了多个新颖且高效的混合算法，包括最小差疏散问题的混合进化算法，最大平均疏散问题的多波算法和分布估计指导的禁忌搜索算法。在此基础上，研究了求解一类公平疏散问题的蒙特卡洛树搜索框架，通过集成有效的局部寻优组件类和全局搜索组件类，算法能够对任意公平疏散问题实例自动选取最有效的组件执行序列。通过与当前国际文献中最好的算法结果进行详细的对比和分析，表明了提出的算法在优度和效率上都具有优势。2）将项目拓展到其他0/1二次优化问题的混合算法研究，研究了带有变量划分约束的二分二次规划问题的多算符驱动自适应禁忌搜索算法、带有广义上界约束的0/1二次规划模型的混合算法、无约束二分二次规划问题的禁忌搜索和策略性扰动驱动的路径重连算法，以及无约束0/1二次优化问题的聚类驱动的路径重连算法等。这些研究不仅丰富了大规模0/1二次优化问题的求解算法，而且提出的混合策略具有通用性，能够用于其他组合优化问题的求解。本课题开发了一类公平疏散问题的通用求解器，研究成果可在危险设施选址、商业连锁店选址、公司团队管理、云计算资源分配等领域进行推广。