Efficient heuristics for Median Cycle Problems

Abstract

This article proposes a number of efficient heuristics for two versions of the Median Cycle Problem. In both versions, the aim is to construct a simple cycle containing a subset of the vertices of a mixed graph. In the first version, the objective is to minimize the cost of the cycle and the cost of assigning vertices not on the cycle to the nearest vertex on the cycle. In the second version, the objective is to minimize the cost of the cycle subject to an upper bound on the total assignment cost. Two heuristics are developed. The first, called the multistart greedy add heuristic, is composed of two main phases. In the first phase, a cycle composed of a limited number of randomly chosen vertices is constructed and augmented by iteratively adding the vertex yielding the largest cost reduction until either no further reduction is possible (for the first version) or the assignment cost is below the upper bound (for the second version). The second phase applies a number of improvement routines. The second heuristic is a random keys evolutionary algorithm. Computational results on a number of benchmark test instances show that the proposed heuristics are highly efficient for both versions of the problem, and superior to the only other available heuristic for these two versions of the problem.

Keywords:

• Median Cycle Problem
• greedy add heuristic
• evolutionary algorithm

Acknowledgements

This work was partially supported by the Canadian Natural Sciences and Engineering Research Council (NSERC) under Grants OPG0039682, OPG0036509 and OPG0172633. This support is gratefully acknowledged. Thanks are also due to Keld Helsgaum who provided us with his Lin–Kernighan code and to Juan José Salazar González and Inmaculada Rodríguez Martín who provided their solutions of the TSPLIB instances. Finally, we thank two referees for their valuable comments.