An empirical computational study of genetic algorithms to solve order based problems: an emphasis on TSP and VRPTC
II Lawrence John Schmitt · 1994
This study explores the potential of genetic algorithms (GA) to solve order based problems with particular emphasis on solving the traveling salesman problem (TSP) and the time constrained vehicle routing problem (VRPTC). As a result of a thorough review of current literature, several issues related to developing GA to solve ordering problems are uncovered. An in-depth, empirically valid computational study using an a-priori statistical design is conducted to determine the best combination of parameter settings and design decisions to use when building GA to solve ordering problems. This test was conducted using the GA Testing System (GATS) developed as part of this effort. A suite of real world problems selected from literature and the TSPlib 1.2 were solved with 144 different GA designed to solve the tsp (GA-TSP), also developed as part of this study. More than 5,000 problems were solved by GA-TSP during this phase of the study. The results of the GA-TSP test were used to develop a GA to solve the VRPTC (GA-VRPTC). To evaluate GA-VRPTC, a set of VRPTC were solved and the results were compared with the results obtained when solving the same set of problems using traditional algorithms. We find that GA-VRPTC performs well in terms of solution quality; however, the amount of CPU time required to solve these problems exceeded that used by traditional methods by several orders of magnitude. After reporting and analyzing the results of the GA-VRPTC test, suggestions for further improvement and extensions are made.