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.