New neighborhood search algorithms based on exponentially large neighborhoods
Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2001.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/17517 |
| _version_ | 1826198943235571712 |
|---|---|
| author | Ergun, Özlem |
| author2 | James B. Orlin. |
| author_facet | James B. Orlin. Ergun, Özlem |
| author_sort | Ergun, Özlem |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2001. |
| first_indexed | 2024-09-23T11:12:18Z |
| format | Thesis |
| id | mit-1721.1/17517 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T11:12:18Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/175172023-03-01T02:07:30Z New neighborhood search algorithms based on exponentially large neighborhoods New local search heuristics based on exponentially large neighborhoods Ergun, Özlem James B. Orlin. Massachusetts Institute of Technology. Operations Research Center. Massachusetts Institute of Technology. Operations Research Center Sloan School of Management Operations Research Center. Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2001. Includes bibliographical references (p. 155-166). 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. (cont.) In Part 3, we discuss dynamic programming approximations for the TSP and a generic set partitioning problem that are based on restricting the state space of the original dynamic programs. Furthermore, we show the equivalence of these restricted DPs to particular neighborhoods that we had considered earlier. Finally, in Part 4, we present the results of a computational study for the compounded independent moves algorithm on the vehicle routing problem with capacity and distance restrictions. These results indicate that our algorithm is competitive with respect to the current heuristics and branch and cut algorithms. by Özlem Ergun. Ph.D. 2005-06-02T15:33:18Z 2005-06-02T15:33:18Z 2001 2001 Thesis http://hdl.handle.net/1721.1/17517 49631933 eng 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. http://dspace.mit.edu/handle/1721.1/7582 166 p. 6515280 bytes 6515087 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Operations Research Center. Ergun, Özlem New neighborhood search algorithms based on exponentially large neighborhoods |
| title | New neighborhood search algorithms based on exponentially large neighborhoods |
| title_full | New neighborhood search algorithms based on exponentially large neighborhoods |
| title_fullStr | New neighborhood search algorithms based on exponentially large neighborhoods |
| title_full_unstemmed | New neighborhood search algorithms based on exponentially large neighborhoods |
| title_short | New neighborhood search algorithms based on exponentially large neighborhoods |
| title_sort | new neighborhood search algorithms based on exponentially large neighborhoods |
| topic | Operations Research Center. |
| url | http://hdl.handle.net/1721.1/17517 |
| work_keys_str_mv | AT ergunozlem newneighborhoodsearchalgorithmsbasedonexponentiallylargeneighborhoods AT ergunozlem newlocalsearchheuristicsbasedonexponentiallylargeneighborhoods |