Insertion heuristics for central cycle problems

✍ Scribed by John D. Lamb

• Publisher: John Wiley and Sons
• Year: 2009
• Tongue: English
• Weight: 250 KB
• Volume: 56
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.20348

✦ Synopsis

Abstract

A central cycle problem requires a cycle that is reasonably short and keeps the maximum distance from any node not on the cycle to its nearest node on the cycle reasonably low. The objective may be to minimize maximum distance or cycle length. Most classes of central cycle problems are NP‐hard. This article investigates insertion heuristics for central cycle problems, drawing on insertion heuristics for p centers and travelling salesman tours. It shows that a modified farthest insertion heuristic has reasonable worst‐case bounds. It then compares the performance of two farthest insertion heuristics on a range of problems from TSPLIB. It shows that a simple farthest insertion heuristic performs well in practice. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010