Performance characteristics of alternative genetic algorithmic approaches to the traveling salesman problem using path representation: An empirical study

The potential of Genetic Algorithmic (GA) approaches for solving order-based problems including the Traveling Salesman Problem (TSP) is recognized in a number of recent studies. By applying various GAs, these studies developed a set of unresolved GA design and configuration issues. The purpose of this study is to resolve the conflicting GA design and configuration issues by (1) concentrating on the classical TSP; and (2) developing, implementing, and testing a complete set of alternative GA configurations; 144 GAs are developed and evaluated by solving 5000 TSPs. A carefully designed statistical experimental plan accompanied by rigorous statistical analysis isolates the most promising configurations and identifies their effect on solution time and quality. Although the emphasis is on the TSP, the final results are applicable to other order-based problems that use sequence encoding.