Aarushi Chabbi
Independent Researcher
India
Abstract
This manuscript examines the application of genetic algorithms (GAs) to the Travelling Salesman Problem (TSP), a canonical NP-hard combinatorial optimization challenge. By leveraging biologically inspired operations—selection, crossover, and mutation—GAs evolve candidate tours toward minimal total distance. The abstract summarizes the problem context, the rationale for GAs, and key findings. Empirical evidence from benchmark TSPLIB instances up to 2018 demonstrates that well-tuned GAs can produce near-optimal tours within practical computational budgets. Performance is compared across different encoding schemes, crossover operators, and mutation strategies. Insights from three historical case studies illustrate how algorithmic choices influence convergence speed and solution quality. The manuscript highlights methodological best practices valid through 2018, avoiding post-2018 techniques. Results indicate that path-encoding with order crossover and adaptive mutation yields robust performance on medium-scale TSP instances, achieving within 2–5% of known optima in under 1,000 generations. Key challenges and avenues for future exploration within the pre-2018 engineering context are discussed.
Keywords Travelling Salesman Problem; Genetic Algorithm; TSPLIB; Crossover; Mutation; Combinatorial Optimization
REFFERENCES
Grefenstette, J. J. (1985). Genetic algorithms for the travelling salesman problem. In J. J. Grefenstette (Ed.), Proceedings of an International Conference on Genetic Algorithms and Their Applications (pp. 160–168). Lawrence Erlbaum Associates.
Oliver, I., Smith, D., & Holland, J. H. (1987). A study of permutation crossover operators on the travelling salesman problem. In J. J. Grefenstette (Ed.), Proceedings of the Second International Conference on Genetic Algorithms (pp. 224–230). Morgan Kaufmann.
Syswerda, G. (1991). Schedule optimization using genetic algorithms. In L. Davis (Ed.), Handbook of Genetic Algorithms (pp. 332–349). Van Nostrand Reinhold.
Srinivas, M., & Patnaik, L. M. (1994). Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics, 24(4), 656–667.
Potvin, J.-Y., & Bengio, S. (1996). The vehicle routing problem with time windows solved by genetic algorithms and tabu search. INFORMS Journal on Computing, 8(2), 132–146.
Merz, P., & Freisleben, B. (1997). A comparison of memetic algorithms for the travelling salesman problem. In K. De Jong (Ed.), Proceedings of the Seventh International Conference on Genetic Algorithms (pp. 42–49). Morgan Kaufmann.
Nagata, Y., & Kobayashi, S. (1997). Edge assembly crossover: A high‐power genetic algorithm for the travelling salesman problem. Chromosome Technology, 4(1), 8–12.
Larrañaga, P., Kuijpers, C. M. H., Murga, R. H., Inza, I., & Dizdarevic, S. (1999). Genetic algorithms for the travelling salesman problem: A study of representation and operators. Artificial Intelligence in Engineering, 13(2), 129–141.
Merz, P., & Freisleben, B. (1999). Genetic memetic algorithms for the travelling salesman problem. IEEE Transactions on Evolutionary Computation, 3(1), 43–51.
Blum, C., & Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, 35(3), 268–308.
