(2006) Lamb, John Douglas; University of Aberdeen, Business School, Management Studies
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.
