Show simple item record

dc.contributor.authorLamb, John Douglasen
dc.date.accessioned2006-12-04T13:17:44Z
dc.date.available2006-12-04T13:17:44Z
dc.date.issued2006
dc.identifier.issnISSN 0143-4543
dc.identifier.urihttp://hdl.handle.net/2164/96
dc.description.abstractA 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.en
dc.format.extent158976 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoenen
dc.relation.ispartofseriesUniversity of Aberdeen Business School Working Paper Seriesen
dc.relation.ispartofseries2006-07en
dc.subjecttouren
dc.subjectcycle, centre, eccentricity, cyclelengthen
dc.titleInsertion Heuristics for Central Cycle Problemsen
dc.typeWorking Paperen
dc.contributor.institutionUniversity of Aberdeen, Business School, Management Studiesen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record