Cyclic Exchange Neighborhood Search and the Other Very Large Scale Neighborhood Search Techniques

该项目主要关注开发一类新的邻域搜索算法来解决分区问题，分区问题是组合优化问题的一个大子类，在物流，制造，电信和调度中有重要应用。众所周知，这些问题在实践中很难解决，邻域搜索算法通常是解决这些问题最有效的方法。研究人员计划使用循环交换邻域搜索，这是一种通用的非常大规模邻域搜索算法，来解决分区问题。作为概念验证，将该方法应用于电信网络设计中的一个基本划分问题——有能力最小生成树问题，并获得了令人印象深刻的结果。研究人员打算将这种方法应用于车辆路线、并行机器调度、位置理论、聚类和图划分中遇到的其他几个划分问题。该项目为理论、算法和实证研究提供了范围。我们还将研究这种方法的扩展，以解决几个非分区问题。该研究还包括开发非常大规模的社区搜索算法，以解决航空业和供应链管理中的物流问题。该方法为解决各种划分问题提供了统一的方法。除了统一的方法之外，它还有以下潜在的优势：(1)所开发的算法可以非常有效地解决广泛的分区问题，可能将可以解决的问题实例的大小扩展到接近最优。(2)算法可以非常健壮和灵活，并且应该很容易修改算法以根据需要纳入新的约束或目标。(3)开发的大部分软件将是可重用的，它们可能被重用以帮助解决不同的分区问题。(4)该方法通过系统地引导用户在给定的调度中进行改进，可以增强交互式（人-机）调度中的决策支持系统。

This project is mainly concerned with developing a new class of neighborhood search algorithms for solving partitioning problems, a large subclass of combinatorial optimization problems that find significant applications in logistics, manufacturing, telecommunications and scheduling. These problems are notoriously difficult to solve in practice and neighborhood search algorithms are often the most effective approaches available for solving them. The investigators plan to use the cyclic exchange neighborhood search, which is a general-purpose very large-scale neighborhood search algorithm, to solve partitioning problems. As a proof of concept, this methodology was applied to the capacitated minimum spanning tree problem, a fundamental partitioning problem arising in telecommunications network design, and obtained highly impressive results. The investigators intend to apply this methodology to several other partitioning problems encountered in vehicle routing, parallel machine scheduling, location theory, clustering, and graph partitioning. The project offers scope for theoretical, algorithmic, and empirical research. Extensions of this approach to solve several non-partitioning problems will also be investigated. The research also encompasses developing very large-scale neighborhood search algorithms to solve logistics problems in the airline industry and supply-chain management.The methodology provides a unified approach for solving a variety of partitioning problems. In addition to the unified approach, it has the following potential advantages: (1) The algorithms developed can be very effective in solving a wide range of partitioning problems, possibly expanding the size of problem instances that can be solved to near-optimality. (2) The algorithms can be quite robust and flexible and it should be easy to modify the algorithms to incorporate new constraints or objectives as needed. (3) Much of the software developed will be reusable and they may be reused to help solve different partitioning problems. (4) The approach can enhance decision support systems in interactive (person-machine) scheduling by systematically guiding users to improvements in a given schedule.