**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**