An Enhanced Genetic Algorithm for the Generalized Traveling Salesman Problem

H. Jafarzadeh; N. Moradinasab; M. Elyasi

doi:10.48084/etasr.1570

Authors

H. Jafarzadeh Department of Systems and Information Engineering, University of Virginia, Charlottesville, Virginia, USA
N. Moradinasab Department of Industrial Engineering, Tarbiat Modares University, Tehran, Iran
M. Elyasi Department of Industrial Engineering, Ozyegin University, Istanbul, Turkey

DOI:

https://doi.org/10.48084/etasr.1570

Keywords:

genetic algorithms, traveling salesman, generalized, nearest neighbor

Abstract

The generalized traveling salesman problem (GTSP) deals with finding the minimum-cost tour in a clustered set of cities. In this problem, the traveler is interested in finding the best path that goes through all clusters. As this problem is NP-hard, implementing a metaheuristic algorithm to solve the large scale problems is inevitable. The performance of these algorithms can be intensively promoted by other heuristic algorithms. In this study, a search method is developed that improves the quality of the solutions and competition time considerably in comparison with Genetic Algorithm. In the proposed algorithm, the genetic algorithms with the Nearest Neighbor Search (NNS) are combined and a heuristic mutation operator is applied. According to the experimental results on a set of standard test problems with symmetric distances, the proposed algorithm finds the best solutions in most cases with the least computational time. The proposed algorithm is highly competitive with the published until now algorithms in both solution quality and running time.

References

M. Mitchell, An Introduction to Genetic Algorithms, MIT Press, 1998

D. Whitley, “A genetic algorithm tutorial”, Statistics and Computing, Vol. 4, No. 2, pp. 65–85, 1994

G. Laporte, Y.Nobert, “Generalized traveling salesman problem through n-sets of nodes–An integer programming approach”, Information Systems and Operational Research, Vol. 21, No. 1, pp. 61-75, 1983

G. Laporte, H. Mercure, Y. Nobert, “Finding the shortest Hamiltonian circuit through n clusters: a lagrangean relaxation approach”, Gongressus Numerantium, Vol. 48, pp. 277-290, 1985

M. Fischetti, J. J. S. Gonzalez, P. Toth, “A Branch-and-cut Algorithm for the symmetric Generalized Traveling Salesman Problem”, Operations Research, Vol. 45, No. 3, pp. 378-394, 1997

K. Castelino, R. D'Souza, P. K. Wright, “Tool-path optimization for minimizing airtime during machining”, Journal of Manufacturing Systems, Vol. 22, No. 3, 173-180, 2002

P. Slavik, “On the approximation of the generalized traveling salesman problem”, Rapport technique, Department of Computer Science, 1997

N. Garg, G. Konjevod, R. Ravi, “A poly logarithmic approximation algorithm for the group Steiner tree problem”, Journal of Algorithms, Vol. 37, No. 1, pp. 66–84, 2000

L. Snyder, M. S. Daskin, “A random-key genetic algorithm for the generalized traveling salesman problem”, European journal of operational research, Vol. 174, pp. 38-54, 2006

X. H. Shi, Y. C. Liang, H. P. Lee, C. Lu, Q. X. Wang, “Particle swarm optimization-based algorithms for TSP and generalized TSP”, Information Processing Letters; Vol. 103, No. 5, pp. 169–76, 2007

K. Jun-man, Z. Yi, “Application of an Improved Ant Colony Optimization on Generalized Traveling Salesman Problem”, Energy Procedia, Vol. 17, Part A, pp. 319-325, 2012

J. Silberholz, B. Golden, “The generalized traveling salesman problem: a new genetic algorithm approach”, Extending the Horizons: Advances in Computing, Optimization and Decision Technologies, pp. 37:165–81, 2007

V. Dimitrijevic, Z. Saric, “An efficient transformation of the generalized traveling salesman problem into the traveling salesman problem on digraphs”, Information Sciences, Vol. 102, No. 1-4, pp.105-110, 1997

D. Karapetyan, G. Gutin, “Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem”, European Journal of Operational Research, Vol. 219, No. 2, pp. 234-251, 2012

B. Bontoux, C. Artigues, Dominique Feillet, “A Memetic Algorithm with a large neighborhood crossover operator for the Generalized Traveling Salesman Problem”, Computers& Operations Research, Vol. 37, No. 11, pp. 1844-1852, 2010

J. H. Yang, X. H. Shi, M. Marchese, “An ant colony optimization method forgeneralized TSP problem”, Progress in Natural Science, Vol. 18, No. 11, pp. 1417–1422, 2008

G. Laporte, A. Asef-Vaziri, C. Sriskandarajah, “Some applications of the generalized traveling salesman problems”, Journal of the Operational Research Society, Vol. 47, No. 12, pp. 1461-1467, 1996

O. Matei, P.C. Pop, “An efficient genetic algorithm for solving the generalized traveling salesman problem”, 6th IEEE International Conference on Intelligent Computer Communication and Processing, pp. 87-92, 2010

P. C. Pop, O. Matei, C. Sabo, “A new Approach for Solving the Generalized Traveling Salesman Problem”, HM 2010, Lecture Notes in Computer Science, Vol. 6373, pp. 62-72, 2010

G. Gutin, D. Karapetyan, “A Memetic Algorithm for the Generalized Traveling Salesman Problem”, Natural Computing, Vol. 9, No. 1, pp. 47-60, 2010

P. C. Pop, S.Lordache, “A Hybrid Heuristic Approach for Solving the Generalized Traveling Salesman Problem”, GECCO, Association for Computing Machinery, pp.481-488, 2011

M. Fatih Tasgetiren, P. N. Suganthan, Q. K. Pan, “An ensemble of discrete differential evolution algorithms for solving the generalized traveling salesman problem”, Applied Mathematics and Computation, Vol. 215, No.9, pp. 3356–3368, 2010

P. C. Pop, “New Integer Programming Formulations of the Generalized Traveling Salesman Problem”, American Journal of Applied Sciences, Vol. 4, No. 11, pp. 932-937, 2007

L. Qu, R, Sun, A” synergetic approach to genetic algorithm for solving traveling salesman problem”, Information Sciences, Vol. 117, No. 3-4, pp. 267-283, 1999