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.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:uct/oai:localhost:11427/22268 |
| Date | January 1988 |
| Creators | Höck, Barbar Katja |
| Contributors | Stewart, Theodor J |
| Publisher | University of Cape Town, Faculty of Science, Department of Statistical Sciences |
| Source Sets | South African National ETD Portal |
| Language | English |
| Detected Language | English |
| Type | Master Thesis, Masters, MSc |
| Format | application/pdf |
Page generated in 0.0015 seconds