AURA Takes you to the home page
 

Aberdeen University Research Archive >
6 - All research >
All research >

Please use this identifier to cite or link to this item: http://hdl.handle.net/2164/96

This item has been viewed 37 times in the last year. View Statistics

Files in This Item:

File Description SizeFormat
ISSN 0143-06-07.pdf155.25 kBAdobe PDFView/Open
Title: Insertion Heuristics for Central Cycle Problems
Authors: Lamb, John Douglas
University of Aberdeen, Business School, Management Studies
Keywords: tour
cycle, centre, eccentricity, cyclelength
Issue Date: 2006
Series/Report no.: University of Aberdeen Business School Working Paper Series
2006-07
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.
URI: http://hdl.handle.net/2164/96
ISSN: ISSN 0143-4543
Appears in Collections:Management Studies research
All research

SFX Query

Items in AURA are protected by copyright, with all rights reserved, unless otherwise indicated.

 


The University of Aberdeen
King's College
Aberdeen
AB24 3FX
Tel: +44 (0)1224-272000