Parallelization of the Traveling Salesman Problem by Clustering its Nodes and Finding the Best Route Passing through the Centroids

[1] D.-Z. Du and P. M. Pardalos, Handbook of Combinatorial Optimization. New York, NY, USA: Springer, 1998. https://doi.org/10.1007/978-1-4613-0303-9 Search in Google Scholar

[2] O. Cheikhrouhou and I. Khouf, “A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy,” Computer Science Review, vol. 40, May 2021, Art. no. 100369. https://doi.org/10.1016/j.cosrev.2021.100369 Search in Google Scholar

[3] B. Golden, L. Bodin, T. Doyle, and W. Stewart, Jr., “Approximate traveling salesman algorithms,” Operations Research, vol. 28, no. 3, pp. 633–846, May–June 1980. https://doi.org/10.1287/opre.28.3.694 Search in Google Scholar

[4] A. Colorni, M. Dorigo, F. Maffioli, V. Maniezzo, G. Righini, and M. Trubian, “Heuristics from nature for hard combinatorial optimization problems,” International Transactions in Operational Research, vol. 3, no. 1, pp. 1–21, Jan. 1996. https://doi.org/10.1016/0969-6016(96)00004-4 Search in Google Scholar

[5] A. Hertz and M. Widmer, “Guidelines for the use of meta-heuristics in combinatorial optimization,” European Journal of Operational Research, vol. 151, no. 2, pp. 247–252, Dec. 2003. https://doi.org/10.1016/S0377-2217(02)00823-8 Search in Google Scholar

[6] L. Kota and K. Jarmai, “Mathematical modeling of multiple tour multiple traveling salesman problem using evolutionary programming,” Applied Mathematical Modelling, vol. 39, no. 12, pp. 3410–3433, June 2015. https://doi.org/10.1016/j.apm.2014.11.043 Search in Google Scholar

[7] R. L. Haupt and S. E. Haupt, Practical Genetic Algorithms. Hoboken, NJ, USA: John Wiley & Sons, 2003. https://doi.org/10.1002/0471671746 Search in Google Scholar

[8] C. Archetti, L. Peirano, and M. G. Speranza, “Optimization in multimodal freight transportation problems: A Survey,” European Journal of Operational Research, vol. 299, no. 1, pp. 1–20, May 2022. https://doi.org/10.1016/j.ejor.2021.07.031 Search in Google Scholar

[9] L. D. Chambers, The Practical Handbook of Genetic Algorithms. Boca Raton, FL, USA: Chapman and Hall/CRC, 2000. Search in Google Scholar

[10] J. Li, Q. Sun, M. Zhou, and X. Dai, “A new multiple traveling salesman problem and its genetic algorithm-based solution,” in 2013 IEEE International Conference on Systems, Man, and Cybernetics, Manchester, UK, 2013, pp. 627–632. Search in Google Scholar

[11] P. A. Miranda, C. A. Blazquez, C. Obreque, J. Maturana-Ross, and G. Gutierrez-Jarpa, “The bi-objective insular traveling salesman problem with maritime and ground transportation costs,” European Journal of Operational Research, vol. 271, no. 3, pp. 1014–1036, Dec. 2018. https://doi.org/10.1016/j.ejor.2018.05.009 Search in Google Scholar

[12] X. Wu, J. Lu, S. Wu, and X. Zhou, “Synchronizing time-dependent transportation services: Reformulation and solution algorithm using quadratic assignment problem,” Transportation Research Part B: Methodological, vol. 152, pp. 140–179, Oct. 2021. https://doi.org/10.1016/j.trb.2021.08.008 Search in Google Scholar

[13] N. Cabrera, J.-F. Cordeau, and J. E. Mendoza, “The doubly open park-and-loop routing problem,” Computers & Operations Research, vol. 143, July 2022, Art. no. 105761. https://doi.org/10.1016/j.cor.2022.105761 Search in Google Scholar

[14] T. Huang, Y.-J. Gong, S. Kwong, H. Wang, and J. Zhang, “A niching memetic algorithm for multi-solution traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol. 24, no. 3, pp. 508–522, June 2020. https://doi.org/10.1109/TEVC.2019.2936440 Search in Google Scholar

[15] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182–197, Apr. 2002. https://doi.org/10.1109/4235.996017 Search in Google Scholar

[16] C. L. Valenzuela and A. J. Jones, “Evolutionary divide and conquer (I): A novel genetic approach to the TSP,” Evolutionary Computation, vol. 1, no. 4, pp. 313–333, Dec. 1993. https://doi.org/10.1162/evco.1993.1.4.313 Search in Google Scholar

[17] C.-N. Fiechter, “A parallel tabu search algorithm for large traveling salesman problems,” Discrete Applied Mathematics, vol. 51, no. 3, pp. 243–267, Jul. 1994. https://doi.org/10.1016/0166-218X(92)00033-I Search in Google Scholar

[18] M. Manfrin, M. Birattari, T. Stützle, and M. Dorigo, “Parallel ant colony optimization for the traveling salesman problem,” in Ant Colony Optimization and Swarm Intelligence. ANTS 2006. Lecture Notes in Computer Science, M. Dorigo, L. M. Gambardella, M. Birattari, A. Martinoli, R. Poli, and T. Stützle, Eds., vol. 4150. Springer, Berlin, Heidelberg, 2006, pp. 224–234. https://doi.org/10.1007/11839088_20 Search in Google Scholar

[19] J. Schneider, C. Froschhammer, I. Morgenstern, T. Husslein, and J. M. Singer, “Searching for backbones – an efficient parallel algorithm for the traveling salesman problem,” Computer Physics Communications, vol. 96, no. 2–3, pp. 173–188, Aug. 1996. https://doi.org/10.1016/0010-4655(96)00062-8 Search in Google Scholar

[20] C. L. Valenzuela and A. J. Jones, “Evolutionary divide and conquer (I): A novel genetic approach to the TSP,” Evolutionary Computation, vol. 1, no. 4, pp. 313–333, Dec. 1993. https://doi.org/10.1162/evco.1993.1.4.313 Search in Google Scholar

[21] D. Blackman and S. Vigna, “Scrambled linear pseudorandom generators,” arXiv:1805.01407, 2018. https://doi.org/10.48550/arXiv.1805.01407 Search in Google Scholar

[22] B. Widynski, “Squares: a fast counter-based RNG,” arXiv:2004.06278, 2020. https://doi.org/10.48550/arXiv.2004.06278 Search in Google Scholar

[23] G. R. Harik, F. G. Lobo, and D. E. Goldberg, “The compact genetic algorithm,” IEEE Transactions on Evolutionary Computation, vol. 3, no. 4, pp. 287–297, Nov. 1999. https://doi.org/10.1109/4235.797971 Search in Google Scholar

[24] A. Shafiee, M. Arab, Z. Lai, Z. Liu, and A. Abbas, “Automated process flowsheet synthesis for membrane processes using genetic algorithm: role of crossover operators,” in Computer Aided Chemical Engineering, Z. Kravanja and M. Bogataj, Eds., vol. 38. Elsevier, 2016, pp. 1201–1206. https://doi.org/10.1016/B978-0-444-63428-3.50205-8 Search in Google Scholar

[25] D. Thierens, “Scalability problems of simple genetic algorithms,” Evolutionary Computation, vol. 7, no. 4, pp. 331–352, Dec. 1999. https://doi.org/10.1162/evco.1999.7.4.331 Search in Google Scholar

[26] R. Kneusel, Random Numbers and Computers. Switzerland: Springer International Publishing AG, 2018. https://doi.org/10.1007/978-3-319-77697-2 Search in Google Scholar

[27] V. V. Romanuke, “Speedup of the k-means algorithm for partitioning large datasets of flat points by a preliminary partition and selecting initial centroids,” Applied Computer Systems, vol. 28, no. 1, pp. 1–12, June 2023. https://doi.org/10.2478/acss-2023-0001 Search in Google Scholar

[28] D. Arthur and S. Vassilvitskii, “How slow is the k-means method?” in Proceedings of the Twenty-Second Annual Symposium on Computational Geometry (SCG’06), Jun. 2006, pp. 144–153. https://doi.org/10.1145/1137856.1137880 Search in Google Scholar

[29] R. B. Arantes, G. Vogiatzis, and D. R. Faria, “Learning an augmentation strategy for sparse datasets,” Image and Vision Computing, vol. 117, Jan. 2022, Art. no. 104338. https://doi.org/10.1016/j.imavis.2021.104338 Search in Google Scholar

[30] O. N. Almasi and M. Rouhani, “A geometric-based data reduction approach for large low dimensional datasets: Delaunay triangulation in SVM algorithms,” Machine Learning with Applications, vol. 4, Jun. 2021, Art. no. 100025. https://doi.org/10.1016/j.mlwa.2021.100025 Search in Google Scholar

[31] TSP Test Data, Feb. 2009. [Online]. Available: https://math.uwaterloo.ca/tsp/data/index.html Search in Google Scholar

[32] D. Chan and D. Mercier, “IC insertion: an application of the travelling salesman problem,” International Journal of Production Research, vol. 27, pp. 1837–1841, Oct. 1988. https://doi.org/10.1080/00207548908942657 Search in Google Scholar

[33] R. Kumar and Z. Luo, “Optimizing the operation sequence of a chip placement machine using TSP model,” IEEE Transactions on Electronics Packaging Manufacturing, vol. 26, no. 1, pp. 14–21, Jan. 2003. https://doi.org/10.1109/TEPM.2003.813002 Search in Google Scholar

[34] P. Ball, “DNA computer helps travelling salesman,” Nature, Jan. 2000. https://doi.org/10.1038/news000113-10 Search in Google Scholar

[35] M. Caserta and S. Voß, “A hybrid algorithm for the DNA sequencing problem,” Discrete Applied Mathematics, vol. 163, part 1, pp. 87–99, Jan. 2014. https://doi.org/10.1016/j.dam.2012.08.025 Search in Google Scholar

[36] M. Aicardi, D. Giglio, and R. Minciardi, “Determination of optimal control strategies for TSP by dynamic programming,” in 2008 47th IEEE Conference on Decision and Control, Cancun, Mexico, Dec. 2008, pp. 2160–2167. https://doi.org/10.1109/CDC.2008.4739290 Search in Google Scholar

[37] I. M. Ross, R. J. Proulx, and M. Karpenko, “An optimal control theory for the traveling salesman problem and its variants,” arXiv:2005.03186, 2020. https://doi.org/10.48550/arXiv.2005.03186 Search in Google Scholar