Article ID: | iaor20012927 |
Country: | United Kingdom |
Volume: | 7 |
Issue: | 4/5 |
Start Page Number: | 301 |
End Page Number: | 317 |
Publication Date: | Jul 2000 |
Journal: | International Transactions in Operational Research |
Authors: | Orlin James B., Ahuja Ravindra K., Sharma Dushyant |
Neighborhood search algorithms are often the most effective approaches available for solving partitioning problems, a difficult class of combinatorial optimization problems arising in many application domains including vehicle routing, telecommunications network design, parallel machine scheduling, location theory, and clustering. A critical issue in the design of a neighborhood search algorithm is the choice of the neighborhood structure, that is, the manner in which the neighborhood is defined. Currently, the two-exchange neighborhood is the most widely used neighborhood for solving partitioning problems. The paper describes the cyclic exchange neighborhood, which is a generalization of the two-exchange neighborhood in which a neighbor is obtained by performing a cyclic exchange. The cyclic exchange neighborhood has substantially more neighbors compared to the two-exchange neighborhood. This paper outlines a network optimization based methodology to search the neighborhood efficiently and presents a proof of concept by applying it to the capacitated minimum spanning tree problem, an important problem in telecommunications network design.