A Hybrid Framework for Heuristic Research: The Travelling Salesperson Problem

The research community is confusing research and development: with competitive experiment suited only for the latter. This realisation led to the call for the revision of the current TSP heuristic investigation framework which researchers believe is biased towards development frameworks. However, despite the wide spread debate on the subject, minimum attempts to correct the situation have been done may be due to lack of necessary information required to implement heuristic research frameworks. This thesis, therefore, develops and implements a hybrid TSP heuristic research framework which amalgamates the two frameworks. The implementation process involves conducting heuristic experiments and classification, developing a novel data analysis tool and hybrid metaheuristic and statistically comparing heuristic performances to determine the best heuristic and its features. Surveys on the TSP implemented heuristics and variants and investigation frameworks applied are conducted. The heuristic classification develops a standard scheme and its classifying templates. A thorough statistical comparison of heuristic performances produces results that prompt debatable remarks. One of them is that heuristics tend to reach an absorption stage during the search for the global optimum solution and thus require a mechanism to drag them out of the trapping search space. The other remark is that the ANOVA assumptions are irrelevant. The reliability analysis reveals that heuristic performances are unpredictable. The Simulated Annealing is the best heuristic. However, other metaheuristics can not be dismissed because they performed statistically the same in many cases. The work designs a Hybrid Erosion And Deposition (HEAD) metaheuristic. The new discovery employs the Tabu Search, Simulated Annealing, Ant Colony, constructive heuristic, central management and erosion and deposition dynamics. These features are amalgamated into a three phased loop (Evaluation, Development and Improvement) which improves the initial solution developed by the constructive heuristic. This thesis develops a hybrid heuristic research framework. It also contributes towards
clarification of the misconception between research and development frameworks, thus, making available the vital information hindering the implementation of research
frameworks. This study suggests that more scientific researches should be conducted in statistical data analysis, violation of ANOVA assumptions and application of matrix instances.