Insertion Heuristics for Central Cycle Problems

Abstract

A central cycle problem requires a cycle that is reasonably short and keeps a the maximum distance from any node not on the cycle to its nearest node on the cycle reasonably low. The objective may be to minimise maximumdistance or cycle length and the solution may have further constraints. Most classes of central cycle problems are NP-hard. This paper investigates insertion heuristics for central cycle problems, drawing on insertion heuristics for p-centres [7] and travelling salesman tours [21]. It shows that a modified farthest insertion heuristic has reasonable worstcase bounds for a particular class of problem. It then compares the performance of two farthest insertion heuristics against each other and against bounds (where available) obtained by integer programming on a range of problems from TSPLIB [20]. It shows that a simple farthest insertion heuristic is fast, performs well in practice and so is likely to be useful for a general problems or as the basis for more complex heuristics for specific problems.