An Enhanced Genetic Algorithm for the Generalized Traveling Salesman Problem
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.
Keywords:
genetic algorithms, traveling salesman, generalized, nearest neighborDownloads
References
M. Mitchell, An Introduction to Genetic Algorithms, MIT Press, 1998 DOI: https://doi.org/10.7551/mitpress/3927.001.0001
D. Whitley, “A genetic algorithm tutorial”, Statistics and Computing, Vol. 4, No. 2, pp. 65–85, 1994 DOI: https://doi.org/10.1007/BF00175354
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 DOI: https://doi.org/10.1080/03155986.1983.11731885
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 DOI: https://doi.org/10.1287/opre.45.3.378
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 DOI: https://doi.org/10.1016/S0278-6125(03)90018-5
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 DOI: https://doi.org/10.1006/jagm.2000.1096
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 DOI: https://doi.org/10.1016/j.ejor.2004.09.057
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 DOI: https://doi.org/10.1016/j.ipl.2007.03.010
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 DOI: https://doi.org/10.1016/j.egypro.2012.02.101
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 DOI: https://doi.org/10.1016/S0020-0255(96)00084-9
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 DOI: https://doi.org/10.1016/j.ejor.2012.01.011
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 DOI: https://doi.org/10.1016/j.cor.2009.05.004
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 DOI: https://doi.org/10.1016/j.pnsc.2008.03.028
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 DOI: https://doi.org/10.1057/jors.1996.190
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 DOI: https://doi.org/10.1109/ICCP.2010.5606458
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 DOI: https://doi.org/10.1007/978-3-642-16054-7_5
G. Gutin, D. Karapetyan, “A Memetic Algorithm for the Generalized Traveling Salesman Problem”, Natural Computing, Vol. 9, No. 1, pp. 47-60, 2010 DOI: https://doi.org/10.1007/s11047-009-9111-6
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 DOI: https://doi.org/10.1145/2001576.2001643
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 DOI: https://doi.org/10.1016/j.amc.2009.10.027
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 DOI: https://doi.org/10.3844/ajassp.2007.932.937
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 DOI: https://doi.org/10.1016/S0020-0255(99)00026-2
Downloads
How to Cite
License
Authors who publish with this journal agree to the following terms:
- Authors retain the copyright and grant the journal the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) after its publication in ETASR with an acknowledgement of its initial publication in this journal.
