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

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

项目编号： No.71501157

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

立项/批准年度： 2016

项目学科： 管理科学

项目作者： 王阳

作者单位： 西北工业大学

项目金额： 18.5万元

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

中文关键词： 启发式算法；禁忌算法；路径重链接算法；混合算法；公平疏散问题

英文摘要： 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.

英文关键词： Heuristics;Tabu Search;Path Relinking;Hybrid Metaheuristics;Equity Dispersion Problems