University of Aberdeen

AURA - Aberdeen University Research Archive

View Item 
  •   AURA Home
  • 5 - All Research
  • All research
  • View Item
  •   AURA Home
  • 5 - All Research
  • All research
  • View Item
  •   AURA Home
  • 5 - All Research
  • All research
  • View Item
      JavaScript is disabled for your browser. Some features of this site may not work without it.

      Insertion Heuristics for Central Cycle Problems

      View/Open
      ISSN 0143-06-07.pdf (155.2Kb)
      Publication date
      2006
      Author
      Lamb, John Douglas
      Metadata
      Show full item record
      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
      Collections
      • All research

      Browse

      All of AURACommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects
      Top of Page
      • AURA Home
      • Accessibility
      • PURE
      • Digital Resources
      • Library, Special Collections & Museums
      • Take-Down Notice
      • Send Feedback
      • Contact Us
         
       
      Library, Special Collections and Museums logo
      The Sir Duncan Rice Library
      University of Aberdeen
      Bedford Road
      Aberdeen
      AB24 3AA

      Tel: +44 (0)1224 273330
      Email: library@abdn.ac.uk
       
         

      Share and keep up to date

      FacebookTwitterWordpress

      • AURA Home
      • Accessibility
      • PURE
      • Digital Resources
      • Library, Special Collections & Museums
      • Take-Down Notice
      • Send Feedback
      • Contact Us