Premium
Insertion heuristics for central cycle problems
Author(s) -
Lamb John D.
Publication year - 2010
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20348
Subject(s) - heuristics , travelling salesman problem , node (physics) , heuristic , computer science , mathematical optimization , range (aeronautics) , algorithm , mathematics , engineering , structural engineering , aerospace engineering
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