Variable neighbourhood structures for cycle location problems

Variable neighbourhood search is a metaheuristic used mainly to tackle combinatorial optimization problems. Its performance depends on having a good variable neighbourhood structure: that is, a sequence of neighbourhoods that are ideally pairwise disjoint and contain feasible solutions further and further from a given feasible solution. This article defines a variable neighbourhood structure with these properties that is new for cycle location problems. It find bounds for the neighbourhood sizes and shows how to iterate over then when the cycle is a circuit. It tests the structure and iteration method using variable neighbourhood search on a range of median cycle problems and finds a neighbourhood size beyond which there is, on average, no benefit in applying local search. This neighbourhood size is found not to depend on problem size or bound on circuit length.

► The article gives a variable neighbourhood structure that is new for cycle location problems. ► It shows this structure has several desirable properties. ► It shows how to enumerate and iterate over neighbourhoods comprising circuits. ► It tests the structure on variable neighbourhood search for cycle centres. ► It finds a maximum useful search depth independent of problem size.