An examination of heuristic algorithms for the travelling salesman problem

Simple item page
dc.contributor.advisorStewart, Theodor Jen_ZA
dc.contributor.authorHöck, Barbar Katjaen_ZA
dc.date.accessioned2016-10-24T03:48:17Z
dc.date.available2016-10-24T03:48:17Z
dc.date.issued1988en_ZA
dc.description.abstractThe role of heuristics in combinatorial optimization is discussed. Published heuristics for the Travelling Salesman Problem (TSP) were reviewed and morphological boxes were used to develop new heuristics for the TSP. New and published heuristics were programmed for symmetric TSPs where the triangle inequality holds, and were tested on micro computer. The best of the quickest heuristics was the furthest insertion heuristic, finding tours 3 to 9% above the best known solutions (2 minutes for 100 nodes). Better results were found by longer running heuristics, e.g. the cheapest angle heuristic (CCAO), 0-6% above best (80 minutes for 100 nodes). The savings heuristic found the best results overall, but took more than 2 hours to complete. Of the new heuristics, the MST path algorithm at times improved on the results of the furthest insertion heuristic while taking the same time as the CCAO. The study indicated that there is little likelihood of improving on present methods unless a fundamental new approach is discovered. Finally a case study using TSP heuristics to aid the planning of grid surveys was described.en_ZA
dc.identifier.apacitationHöck, B. K. (1988). <i>An examination of heuristic algorithms for the travelling salesman problem</i>. (Thesis). University of Cape Town ,Faculty of Science ,Department of Statistical Sciences. Retrieved from http://hdl.handle.net/11427/22268en_ZA
dc.identifier.chicagocitationHöck, Barbar Katja. <i>"An examination of heuristic algorithms for the travelling salesman problem."</i> Thesis., University of Cape Town ,Faculty of Science ,Department of Statistical Sciences, 1988. http://hdl.handle.net/11427/22268en_ZA
dc.identifier.citationHöck, B. 1988. An examination of heuristic algorithms for the travelling salesman problem. University of Cape Town.en_ZA
dc.identifier.ris TY - Thesis / Dissertation AU - Höck, Barbar Katja AB - The role of heuristics in combinatorial optimization is discussed. Published heuristics for the Travelling Salesman Problem (TSP) were reviewed and morphological boxes were used to develop new heuristics for the TSP. New and published heuristics were programmed for symmetric TSPs where the triangle inequality holds, and were tested on micro computer. The best of the quickest heuristics was the furthest insertion heuristic, finding tours 3 to 9% above the best known solutions (2 minutes for 100 nodes). Better results were found by longer running heuristics, e.g. the cheapest angle heuristic (CCAO), 0-6% above best (80 minutes for 100 nodes). The savings heuristic found the best results overall, but took more than 2 hours to complete. Of the new heuristics, the MST path algorithm at times improved on the results of the furthest insertion heuristic while taking the same time as the CCAO. The study indicated that there is little likelihood of improving on present methods unless a fundamental new approach is discovered. Finally a case study using TSP heuristics to aid the planning of grid surveys was described. DA - 1988 DB - OpenUCT DP - University of Cape Town LK - https://open.uct.ac.za PB - University of Cape Town PY - 1988 T1 - An examination of heuristic algorithms for the travelling salesman problem TI - An examination of heuristic algorithms for the travelling salesman problem UR - http://hdl.handle.net/11427/22268 ER - en_ZA
dc.identifier.urihttp://hdl.handle.net/11427/22268
dc.identifier.vancouvercitationHöck BK. An examination of heuristic algorithms for the travelling salesman problem. [Thesis]. University of Cape Town ,Faculty of Science ,Department of Statistical Sciences, 1988 [cited yyyy month dd]. Available from: http://hdl.handle.net/11427/22268en_ZA
dc.language.isoengen_ZA
dc.publisher.departmentDepartment of Statistical Sciencesen_ZA
dc.publisher.facultyFaculty of Scienceen_ZA
dc.publisher.institutionUniversity of Cape Town
dc.subject.otherMathematical Statisticsen_ZA
dc.subject.otherOperations Researchen_ZA
dc.titleAn examination of heuristic algorithms for the travelling salesman problemen_ZA
dc.typeMaster Thesis
dc.type.qualificationlevelMasters
dc.type.qualificationnameMScen_ZA
uct.type.filetypeText
uct.type.filetypeImage
uct.type.publicationResearchen_ZA
uct.type.resourceThesisen_ZA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
thesis_sci_1988_hock_barbar_katja.pdf
Size:
2.95 MB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Masters