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

点击翻译按钮获取中文摘要

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.