Cyclic exchange and related neighborhood structures for combinatorial optimization problems

In this thesis, we concentrate on neighborhood search algorithms based on very large-scale neighborhood structures. The thesis consists of three parts. In the first part, we develop a cyclic exchange neighborhood search based approach for partitioning problems. A partitioning problem is to divide a set of n elements into K subsets S1,... ,SK so as to minimize f(S1)+...+f(SK) for some specified function f. A partition S'1,.. ,S'K is called a cyclic exchange neighbor of the partition S1,...,SK if [...]. The problem of searching the cyclic exchange neighborhood is NP-hard. We develop new exact and heuristic algorithms to search this neighborhood structure. We propose cyclic exchange based neighborhood search algorithms for specific partitioning problems. We provide computational results on these problems indicating that the cyclic exchange is very effective and can be implemented efficiently in practice. The second part deals with the Combined Through and Fleet Assignment Model (ctFAM). This model integrates two airline planning models: (i) Fleet Assignment Model and (ii) Through Assignment Model, which are currently solved in a sequential manner because the combined problem is too large. This leads to sub-optimal solutions for the combined problem we develop very large-scale neighborhood search algorithms for the ctFAM. We also extend our neighborhood search algorithms to solve the multi-criteria objective function version of the ctFAM. Our computational results using real-life data show that neighborhood search can be a useful supplement to the current integer-programming optimization methods in airline scheduling.

Department dc:contributor.department

Sloan School of Management.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2002

Author dc:creator

• Sharma, Dushyant, 1975-

Advisor dc:contributor.advisor

• James B. Orlin.

• Sloan School of Management.

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/8526

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/8526