Very large-scale neighborhood search

Very large-scale neighborhood search

0.00 Avg rating0 Votes
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: , ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.