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

循环交换邻域搜索和其他超大规模邻域搜索技术

• 批准号: 9820998
• 负责人: James Orlin
• 金额: --
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-07-01 至 2003-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9820998&HistoricalAwards=false
• 关键词: Cyclic; Exchange; Neighborhood; Search; Other

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.

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