Abstract
Generalized Traveling Salesman Problem (GTSP) is one of the challenging combinatorial optimization problems in a lot of applications. In general, GTSP is more complex than Traveling Salesman Problem (TSP). In this paper, a novel hybrid chromosome genetic algorithm (HCGA), in which the hybrid binary and integer codes are adopted, is proposed as an improvement of generalized chromosome genetic algorithm (GCGA). In order to examine the effectiveness of HCGA, 16 benchmark problems are simulated. The experimental results show that HCGA can perform better than GCGA does in solving GTSP.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Henry-Labordere, A.L.: The record balancing problem: A dynamic programming solution of a generalized traveling salesman problem. RAIRO B 2, 43–49 (1969)
Saksena, J.P.: Mathematical model of scheduling clients through welfare agencies. CORS Journal 8, 185–200 (1970)
Srivastava, S.S.S., Kumar, R.C.G., Sen, P.: Generalized traveling salesman problem through n sets of nodes. CORS Journal 7, 97–101 (1969)
Easwaran, M., Pitt, J., Poslad, S.: The agent service brokering problem as a generalized travelling salesman problem. In: Proceedings of the Third Annual Conference on Autononlous Agents, Seattle WA, USA, pp. 414–415 (1999)
Laporte, G., Asef-Vaziri, A., Sriskandarajah, C.: Some applications of the generalized traveling salesman problem. J. Oper. Res. Soc. 47, 1461–1467 (1996)
Wu, C.G., Liang, Y.C., Lee, H.P., Lu, C.: Generalized chromosome genetic algorithm for generalized traveling salesman problems and its applications for machining. Physical Review E 70, 016701 (2004)
Fischetti, M., Salazar, J.J., Toth, P.: Branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Operations Research 45(3), 378–394 (1997)
Laporte, G., Nobert, Y.: Generalized traveling salesman through n sets of nodes: an integer programming approach. INFOR 21, 61–75 (1983)
Laporte, G., Mercure, H., Nobert, Y.: Generalized traveling salesman problem through n sets of nodes: the asymmetrical cases. Discrete Appl. Math. 18, 185–197 (1987)
Fischetti, M., Salazar, J.J., Toth, P.: A branch-and-cut algorithm for the symmetric generalized traveling salesman problem, Working paper, University of Bologna (1993)
Fischetti, M., Salazar, J.J., Toth, P.: The symmetric generalized traveling salesman polytope. Networks 26, 113–123 (1995)
Renaud, J., Boctor, F.F.: An efficient composite heuristic for the symmetric generalized traveling salesman problem. European Journal of Operational Research 108, 571–584 (1998)
Noon, C.E., Bean, J.C.: An efficient transformation of the generalized traveling salesman problem. INFOR 31, 39–44 (1993)
Lien, Y., Ma, E., Wah, B.W.S.: Transformation of the generalized traveling salesman problem into the standard traveling salesman problem. Information Science 74, 177–189 (1993)
Dimitrijevic, V., Saric, Z.: An efficient transformation of the generalized traveling salesman problem into the traveling salesman problem on digraphs. Information Science 102, 105–110 (1997)
Reinelt, G.: TSPLIB. A traveling salesman problem library. ORSA Journal on Computing 3(4), 376–384 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Huang, H., Yang, X., Hao, Z., Wu, C., Liang, Y., Zhao, X. (2005). Hybrid Chromosome Genetic Algorithm for Generalized Traveling Salesman Problems. In: Wang, L., Chen, K., Ong, Y.S. (eds) Advances in Natural Computation. ICNC 2005. Lecture Notes in Computer Science, vol 3612. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11539902_16
Download citation
DOI: https://doi.org/10.1007/11539902_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28320-1
Online ISBN: 978-3-540-31863-7
eBook Packages: Computer ScienceComputer Science (R0)