Very Large Scale Neighborhood Search
A Neighborhood Search Technique has 3 Parts
Very Large Scale Nbhd (VLSN) search
An example of VLSN: Independent 2-exchanges
Pairs that are not independent
Dynasearch/ Ejection Chains, and more
Some advantages for VLSN search
Cyclic Exchange for Partitioning Problems
Vehicle Routing Problems, Scheduling Problems, Clustering Problems, and more
Capacitated Minimum Spanning Tree Problem (CMST)
The Cyclic Exchange
Neighborhood
(Multi-Swap)
A Simplification for this talk
The Effect of a Cyclic Exchange, Multi-Swap
Airline Fleet Assignment Model
Computational Results:
Research with United Airlines
Ahuja,
Orlin, Sharma [2000]
Neighborhoods Based on Polynomial Time Algorithms for Special Cases