Very Large Scale Neighborhood Search

Neighborhood Search

Neighborhood Search

TSP and 2-exchanges

A Neighborhood Search Technique has 3 Parts

Slide 6

Very Large Scale Nbhd (VLSN) search

Slide 8

Two survey papers

Personal view of VLSN search

An example of VLSN:  Independent 2-exchanges

Slide 12

Pairs that are not independent

Dynasearch/ Ejection Chains, and more

The Improvement Graph

Slide 16

Insertion based neighborhoods

Some advantages for VLSN search

Cyclic Exchange for Partitioning Problems

Partitioning Problems

The Cost Structure

Vehicle Routing Problems, Scheduling Problems, Clustering Problems, and more

Capacitated Minimum Spanning Tree Problem (CMST)

Some references on CMST

The Cyclic Exchange Neighborhood
(Multi-Swap)

A Path Exchange

A Simplification for this talk

The Effect of a Cyclic Exchange, Multi-Swap

The improvement Graph G

About the improvement graph

The Improvement Graph

Slide 32

Airline Scheduling

Airline Fleet Assignment Model

On Neighborhood Search

Single A-B Swaps (before)

Single A-B Swaps (after)

Multi A-B Swaps

A-B Graph (Talluri [1996])

Computational Results:    
Research with United Airlines
Ahuja, Orlin, Sharma [2000]

Neighborhoods Based on Polynomial Time Algorithms for Special Cases

Pyramidal Tours and Neighbors

Halin Graphs

Halin Graphs

Halin Neighbors

A Generic Approach

A Generic Approach

More on the generic approach

Conclusions