Abstract
As the generalization of TSP (Travelling Salesman Problem), TSPN (TSP with Neighborhoods) is closely related to several important real-world applications. However, TSPN is significantly more challenging than TSP as it is inherently a mixed optimization task containing both combinatorial and continuous components. Different from previous studies where TSPN is either tackled by approximation algorithms or formulated as a mixed integer problem, we present a hybrid framework in which metaheuristics and classical TSP solvers are combined strategically to produce high quality solutions for TSPN with arbitrary neighborhoods. The most distinctive feature of our solution is that it imposes no explicit restriction on the shape and size of neighborhoods, while many existing TSPN solutions require the neighborhoods to be disks or ellipses. Furthermore, various continuous optimization algorithms and TSP solvers can be conveniently adopted as necessary. Experiment results show that, using two off-the-shelf routines and without any specific performance tuning efforts, our method can efficiently solve TSPN instances with up to 25 regions, which are represented by both convex and concave random polygons.
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
Similar content being viewed by others
References
Applegate, D., Bixby, R., Chvátal, V., Cook, W.: The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton (2007)
Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45, 753–782 (1998)
Larrañaga, P., Kuijpers, C., Murga, R., Inza, I., Dizdarevic, S.: Genetic algorithms for the travelling salesman problem: a review of representations and operators. Artif. Intell. Rev. 13, 129–170 (1999)
Helsgaun, K.: An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126, 106–130 (2000)
Alatartsev, S., Stellmacher, S., Ortmeier, F.: Robotic task sequencing problem: a survey. J. Intell. Robot. Syst. 80, 279–298 (2015)
Arkin, E.M., Hassin, R.: Approximation algorithms for the geometric covering salesman problem. Discret. Appl. Math. 55, 197–218 (1994)
Mitchell, J.: A PTAS for TSP with neighborhoods among fat regions in the plane. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 11–18 (2007)
Elbassioni, K., Fishkin, A., Sitters, R.: Approximation algorithms for the Euclidean traveling salesman problem with discrete and continuous neighborhoods. Int. J. Comput. Geom. Appl. 19, 173–193 (2009)
Chan, T., Elbassioni, K.: A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics. Discret. Comput. Geom. 46, 704–723 (2011)
Dumitrescu, A., Tóth, C.: Constant-factor approximation for TSP with disks (2016). arXiv:1506.07903v3 [cs.CG]
Gentilini, I., Margot, F., Shimada, K.: The travelling salesman problem with neighborhoods: MINLP solution. Optim. Methods Softw. 28, 364–378 (2013)
Yuan, B., Orlowska, M., Sadiq, S.: On the optimal robot routing problem in wireless sensor networks. IEEE Trans. Knowl. Data Eng. 19, 1252–1261 (2007)
Chang, W., Zeng, D., Chen, R., Guo, S.: An artificial bee colony algorithm for data collection path planning in sparse wireless sensor networks. Int. J. Mach. Learn. Cybern. 6, 375–383 (2015)
Random 2D Polygon Code. http://stackoverflow.com/questions/8997099/algorithm-to-generate-random-2d-polygon
CMA-ES Source Code. https://www.lri.fr/~hansen/cmaes_inmatlab.html
Hansen, N., Ostermeier, A.: Completely derandomized self-adaptation in evolution strategies. Evol. Comput. 9, 159–195 (2001)
TSPSEARCH. http://www.mathworks.com/matlabcentral/fileexchange/35178-tspsearch
Kirk, D., Hwu, W.: Programming Massively Parallel Processors: A Hands-on Approach. Morgan Kaufmann, San Francisco (2012)
Jones, T., Forrest, S.: Fitness distance correlation as a measure of problem difficulty for genetic algorithms. In: Proceedings of 6th International Conference on Genetic Algorithms, pp. 184–192 (1995)
Acknowledgement
This work was supported by Natural Science Foundation of Guangdong Province (No. 2014A030310318) and Research Foundation of Shenzhen (No. JCYJ20160301153317415).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Yuan, B., Zhang, T. (2017). Towards Solving TSPN with Arbitrary Neighborhoods: A Hybrid Solution. In: Wagner, M., Li, X., Hendtlass, T. (eds) Artificial Life and Computational Intelligence. ACALCI 2017. Lecture Notes in Computer Science(), vol 10142. Springer, Cham. https://doi.org/10.1007/978-3-319-51691-2_18
Download citation
DOI: https://doi.org/10.1007/978-3-319-51691-2_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-51690-5
Online ISBN: 978-3-319-51691-2
eBook Packages: Computer ScienceComputer Science (R0)