<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>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.</p>
</abstract>

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.

Traveling salesman problem parallelization by solving clustered subproblems

Foundations of Computing and Decision Sciences

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"Traveling salesman problem parallelization by solving clustered subproblems"}

A method of parallelizing the process of solving the traveling salesman problem is suggested, where the solver is a heuristic algorithm. The traveling salesman...

Traveling salesman problem parallelization by solving clustered subproblems

Publié en ligne: 21 déc. 2023

Pages: 453 - 481

Reçu: 20 août 2022

Accepté: 14 mai 2023

DOI: https://doi.org/10.2478/fcds-2023-0020

Mots clés
traveling salesman problem, clustered subproblems, transition nodes, parallelization, route length, genetic algorithm

© 2023 Vadim Romanuke, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Traveling salesman problem parallelization by solving clustered subproblems

Publié en ligne: 21 déc. 2023

Pages: 453 - 481

Reçu: 20 août 2022

Accepté: 14 mai 2023

DOI: https://doi.org/10.2478/fcds-2023-0020

Mots cléstraveling salesman problem, clustered subproblems, transition nodes, parallelization, route length, genetic algorithm

© 2023 Vadim Romanuke, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Mots clés
traveling salesman problem, clustered subproblems, transition nodes, parallelization, route length, genetic algorithm