Traveling salesman problem parallelization by solving clustered subproblems

• Autorzy: Romanuke Vadim

Identyfikatory

DOI

10.2478/fcds-2023-0020

• Języki publikacji: EN

Abstrakty

EN

A method of parallelizing the process of solving the traveling salesman problem is suggested, where the solver is a heuristic algorithm. The traveling salesman problem parallelization is fulfilled by clustering the nodes into a given number of groups. Every group (cluster) is an open-loop subproblem that can be solved independently of other subproblems. Then the solutions of the respective subproblems are aggregated into a closed loop route being an approximate solution to the initial traveling salesman problem. The clusters should be enumerated such that then the connection of two “neighboring” subproblems (with successive numbers) be as short as possible. For this, the destination nodes of the open-loop subproblems are selected farthest from the depot and closest to the starting node for the subsequent subproblem. The initial set of nodes can be clustered manually by covering them with a finite regular-polygon mesh having the required number of cells. The efficiency of the parallelization is increased by solving all the subproblems in parallel, but the problem should be at least of 1000 nodes or so. Then, having no more than a few hundred nodes in a cluster, the genetic algorithm is especially efficient by executing all the routine calculations during every iteration whose duration becomes shorter.

Słowa kluczowe

EN

traveling salesman problem; clustered subproblems; transition nodes; parallelization; route length; genetic algorithm

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2023
• Tom: Vol. 48, No. 4
• Strony: 453--481
• Opis fizyczny: Bibliogr. 29 poz., rys., tab.

Twórcy

autor

Romanuke Vadim

• Polish Naval Academy, Gdynia, Poland

Bibliografia

• [1] Archetti C., Peirano L., Speranza M. G., Optimization in multimodal freight transportation problems: A Survey, European Journal of Operational Research, 299 (1), 2022, 1-20.
• [2] Bosch R., Herman A., Continuous line drawings via the traveling salesman problem, Operations Research Letters, 32 (4), 2004, 302-303.
• [3] Chambers L. D., The Practical Handbook of Genetic Algorithms, Chapman and Hall/CRC, 2000.
• [4] Cheikhrouhou O., Khoufi I., A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy, Computer Science Review, 40, 2021, Article ID 100369.
• [5] Colorni A., Dorigo M., Maffioli F., Maniezzo V., Righini G., Trubian M., Heuristics from nature for hard combinatorial optimization problems, International Transactions in Operational Research, 3 (1), 1996, 1-21.
• [6] Cormen T. H., Leiserson C. E., Rivest R. L., Stein C., Chapter 23: Minimum Spanning Trees, in: Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001, pp. 561-579.
• [7] Du D.-Z., Pardalos P. M., Handbook of Combinatorial Optimization, New York, NY, USA, Springer, 1998.
• [8] Fiechter C.-N., A parallel tabu search algorithm for large traveling salesman problems, Discrete Applied Mathematics, 51 (3), 1994, 243-267.
• [9] Gower J. C., Ross G. J. S., Minimum spanning trees and single linkage cluster analysis, Applied Statistics, 18 (1), 1969, 54-61.
• [10] Graham R. L., Hell P., On the history of the minimum spanning tree problem, Annals of the History of Computing, 7 (1), 1985, 43-57.
• [11] Hartigan J. A., Wong M. A., Algorithm AS 136: A k-means clustering algorithm, Journal of the Royal Statistical Society, Series C, 28 (1), 1979, 100-108.
• [12] Haupt R. L., Haupt S. E., Practical Genetic Algorithms, John Wiley & Sons, 2003.
• [13] Hertz A., Widmer M., Guidelines for the use of meta-heuristics in combinatorial optimization, European Journal of Operational Research, 151 (2), 2003, 247-252.
• [14] Honda K., Nagata Y., Ono I., A parallel genetic algorithm with edge assembly crossover for 100,000-city scale TSPs, 2013 IEEE Congress on Evolutionary Computation, June 20-23, 2013, Cancún, México, pp. 1278-1285.
• [15] https://en.wikipedia.org/wiki/Concorde_TSP_Solver.
• [16] https://www.math.uwaterloo.ca/tsp/concorde/.
• [17] https://www.math.uwaterloo.ca/tsp/data/ml/monalisa.html.
• [18] Király A., Abonyi J., Redesign of the supply of mobile mechanics based on a novel genetic optimization algorithm using Google Maps API, Engineering Applications of Artificial Intelligence, 38, 2015, 122-130.
• [19] Kneusel R., Random Numbers and Computers, Springer International Publishing, 2018.
• [20] Kota L., Jarmai K., Mathematical modeling of multiple tour multiple traveling salesman problem using evolutionary programming, Applied Mathematical Modelling, 39 (12), 2015, 3410-3433.
• [21] Macgregor J. N., Ormerod T., Human performance on the traveling salesman problem, Perception & Psychophysics, 58 (4), 1996, 527-539.
• [22] Manfrin M., Birattari M., Stützle T., Dorigo M., Parallel ant colony optimization for the traveling salesman problem, in: Dorigo M., Gambardella L. M., Birattari M., Martinoli A., Poli R., Stützle T. (eds.), Ant Colony Optimization and Swarm Intelligence. ANTS 2006. Lecture Notes in Computer Science, vol. 4150. Springer, Berlin, Heidelberg, 2006, pp. 224-234.
• [23] Miranda P. A., Blazquez C. A., Obreque C., Maturana-Ross J., Gutierrez-Jarpa G., The bi-objective insular traveling salesman problem with maritime and ground transportation costs, European Journal of Operational Research, 271 (3), 2018, 1014-1036.
• [24] Press W. H., Teukolsky S. A., Vetterling W. T., Flannery B. P., Section 16.1. Gaussian Mixture Models and k-Means Clustering, in: Numerical Recipes: The Art of Scientific Computing (3rd edition), New York, NY, Cambridge University Press, 2007.
• [25] Romanuke V. V., Division-by-q dichotomization for interval uncertainty reduction by cutting off equal parts from the left and right based on expert judgments under short-termed observations, Foundations of Computing and Decision Sciences, 45 (2), 2020, 125-155.
• [26] Romanuke V. V., Hard and soft adjusting of a parameter with its known boundaries by the value based on the experts’ estimations limited to the parameter, Electrical, Control and Communication Engineering, 10, 2016, 23-28.
• [27] Santini A., Viana A., Klimentova X., Pedroso J. P., The probabilistic travelling salesman problem with crowdsourcing, Computers & Operations Research, 142, 2022, Article ID 105722.
• [28] Schneider J., Froschhammer C., Morgenstern I., Husslein T., Singer J. M., Searching for backbones — an efficient parallel algorithm for the traveling salesman problem, Computer Physics Communications, 96 (2-3), 1996, 173-188.
• [29] Sofianopoulou S., Mitsopoulos I., A review and classification of heuristic algorithms for the inventory routing problem, International Journal of Operational Research, 41 (2), 2021, 282-298.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).