An Enhanced Genetic Algorithm for the Generalized Traveling Salesman Problem

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
Volume: 7 | Issue: 6 | Pages: 2260-2265 | December 2017 | https://doi.org/10.48084/etasr.1570

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 neighbor

Downloads

Download data is not yet available.

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

[1]
H. Jafarzadeh, N. Moradinasab, and M. Elyasi, “An Enhanced Genetic Algorithm for the Generalized Traveling Salesman Problem”, Eng. Technol. Appl. Sci. Res., vol. 7, no. 6, pp. 2260–2265, Dec. 2017.

Metrics

Abstract Views: 793
PDF Downloads: 235

Metrics Information
Bookmark and Share