Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
An examination of heuristic algorithms for the travelling salesman problem
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...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
Department of Statistical Sciences
2016
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613268469612544 |
|---|---|
| access_status_str | Open Access |
| author | Höck, Barbar Katja |
| author2 | Stewart, Theodor J |
| author_browse | Höck, Barbar Katja Stewart, Theodor J |
| author_facet | Stewart, Theodor J Höck, Barbar Katja |
| author_sort | Höck, Barbar Katja |
| collection | Thesis |
| description | 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. |
| format | Thesis |
| id | oai:open.uct.ac.za:11427/22268 |
| institution | University of Cape Town (South Africa) |
| language | eng |
| last_indexed | 2026-06-10T12:33:26.520Z |
| license_str | Not specified — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from UCTD — University of Cape Town Open Access Repository |
| publishDate | 2016 |
| publishDateRange | 2016 |
| publishDateSort | 2016 |
| publisher | Department of Statistical Sciences |
| publisherStr | Department of Statistical Sciences |
| record_format | dspace |
| source_str | UCTD — University of Cape Town Open Access Repository |
| spelling | oai:open.uct.ac.za:11427/22268 An examination of heuristic algorithms for the travelling salesman problem Höck, Barbar Katja Stewart, Theodor J Mathematical Statistics Operations Research 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. 2016-10-24T03:48:17Z 2016-10-24T03:48:17Z 1988 Master Thesis Masters MSc http://hdl.handle.net/11427/22268 eng application/pdf Department of Statistical Sciences Faculty of Science University of Cape Town |
| spellingShingle | Mathematical Statistics Operations Research Höck, Barbar Katja An examination of heuristic algorithms for the travelling salesman problem |
| thesis_degree_str | Master's |
| title | An examination of heuristic algorithms for the travelling salesman problem |
| title_full | An examination of heuristic algorithms for the travelling salesman problem |
| title_fullStr | An examination of heuristic algorithms for the travelling salesman problem |
| title_full_unstemmed | An examination of heuristic algorithms for the travelling salesman problem |
| title_short | An examination of heuristic algorithms for the travelling salesman problem |
| title_sort | examination of heuristic algorithms for the travelling salesman problem |
| topic | Mathematical Statistics Operations Research |
| url | http://hdl.handle.net/11427/22268 |
| work_keys_str_mv | AT hockbarbarkatja anexaminationofheuristicalgorithmsforthetravellingsalesmanproblem AT hockbarbarkatja examinationofheuristicalgorithmsforthetravellingsalesmanproblem |