Neighborhood search algorithms are often very effective heuristic approaches available for solving difficult combinatorial optimization problems. This continuing project concerns the development of neighborhood search algorithms where the size of the neighborhood is "very large. " We refer to such algorithms as Very Large-Scale Neighborhood (VLSN) Search Algorithms. The number of neighbors in VLSN search algorithms is too large to be enumerated explicitly, and efficient methods are needed to identify improving neighbors quickly without explicitly enumerating all neighbors. We have used a variety of approaches for searching neighborhoods for improved neighbors including: network optimization, integer programming, dynamic programming as well as heuristic search. This paper summarizes our contributions (much of which is joint with collaborators) in the past three years to the development of very large-scale neighborhood search algorithms for several combinatorial optimization problems. We summarize our contributions to (i) a telecommunications network design problem; (ii) solving combined through-fleet assignment problems in airline scheduling and its various extensions; (iii) locomotive assignment and blocking problem for rail management planning; (iv) a clustering problem arising in the printed circuit board manufacturing; (v) the quadratic assignment problem; (vi) the capacitated facility location problem; (vii) the weapon-target assignment problem; and (viii) the vehicle routing problem. We also investigate the concept of extended neighbourhoods and the role of dynamic programming in neighborhood search as well as the concept of "extended neighborhoods."
展开▼
