New neighborhood search algorithms based on exponentially large neighborhoods

A practical approach for solving computationally intractable problems is to employ heuristic (approximation) algorithms that can find nearly optimal solutions within a reasonable amount of computational time. An improvement algorithm is an approximation algorithm which starts with a feasible solution and iteratively attempts to obtain a better solution. Neighborhood search algorithms (alternatively called local search algorithms) are a wide class of improvement algorithms where at each iteration an improving solution is found by searching the "neighborhood" of the current solution. This thesis concentrates on neighborhood search algorithms where the size of the neighborhood is "very large" with respect to the size of the input data. For large problem instances, it is impractical to search these neighborhoods explicitly, and one must either search a small portion of the neighborhood or else develop efficient algorithms for searching the neighborhood-implicitly. This thesis consists of four parts. Part 1 is a survey of very large scale neighborhood (VLSN) search techniques for combinatorial optimization problems. In Part 2, we concentrate on a VLSN search technique based on compounding independent simple moves such as 2-opts, swaps, and insertions. We show that the search for an improving neighbor can be done by finding a negative cost path on an auxiliary graph. We show how this neighborhood is applied to problems such as the TSP, VRP, and specific single and multiple machine scheduling problems.

Department dc:contributor.department

Massachusetts Institute of Technology. Operations Research Center

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2001

Author dc:creator

• Ergun, Özlem

Advisor dc:contributor.advisor

• James B. Orlin.

• Operations Research Center.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/17517

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/17517