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

<p>A method of heuristically solving large and extremely large traveling salesman problems is suggested. The solver is a specific genetic algorithm producing approximately shortest routes the fastest of known heuristics without losing much in accuracy. The method consists in parallelizing the problem by clustering its nodes and finding the best route passing through the centroids of the clusters. The open-loop subroutes of the clusters are connected via specific nodes. These specific nodes referred to as connectors are determined as those for which the distance to the depot is maximal and the distance to the cluster of the following subproblem is minimal. Thus, a bunch of smaller open-loop problems is solved instead of solving the whole (closed loop) problem. Extremely large problems should be clustered manually by imposing a mesh of rotated square cells. In this case, the connectors should be determined manually as well. A connector can also be approximated by a node which is the closest to the line connecting the centroids of the two clusters. The suggested parallelization can produce a very significant speedup depending on how many processor cores are simultaneously available. The factual speedup by the parallelization depends on the availability of processor cores, memory, and the processor clock frequency. The efficiency of the parallelization is maintained for a few hundred to a few million nodes by any number of clusters being less than the size of the average cluster.</p>
</abstract>

A method of heuristically solving large and extremely large traveling salesman problems is suggested. The solver is a specific genetic algorithm producing approximately shortest routes the fastest of known heuristics without losing much in accuracy. The method consists in parallelizing the problem by clustering its nodes and finding the best route passing through the centroids of the clusters. The open-loop subroutes of the clusters are connected via specific nodes. These specific nodes referred to as connectors are determined as those for which the distance to the depot is maximal and the distance to the cluster of the following subproblem is minimal. Thus, a bunch of smaller open-loop problems is solved instead of solving the whole (closed loop) problem. Extremely large problems should be clustered manually by imposing a mesh of rotated square cells. In this case, the connectors should be determined manually as well. A connector can also be approximated by a node which is the closest to the line connecting the centroids of the two clusters. The suggested parallelization can produce a very significant speedup depending on how many processor cores are simultaneously available. The factual speedup by the parallelization depends on the availability of processor cores, memory, and the processor clock frequency. The efficiency of the parallelization is maintained for a few hundred to a few million nodes by any number of clusters being less than the size of the average cluster.

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

Applied Computer Systems

This work is licensed under the Creative Commons Attribution 4.0 International License.

A method of heuristically solving large and extremely large traveling salesman problems is suggested. The solver is a specific genetic algorithm producing...

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

Publié en ligne: 29 janv. 2024

Pages: 189 - 202

DOI: https://doi.org/10.2478/acss-2023-0019

Mots clés
Approximately shortest route, centroids, clustered subproblems, genetic algorithm, parallelization, route length, traveling salesman problem

© 2023 Vadim Romanuke, published by Sciendo

This work is licensed under the Creative Commons Attribution 4.0 International License.

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

Publié en ligne: 29 janv. 2024

Pages: 189 - 202

DOI: https://doi.org/10.2478/acss-2023-0019

Mots clésApproximately shortest route, centroids, clustered subproblems, genetic algorithm, parallelization, route length, traveling salesman problem

© 2023 Vadim Romanuke, published by Sciendo

This work is licensed under the Creative Commons Attribution 4.0 International License.

Mots clés
Approximately shortest route, centroids, clustered subproblems, genetic algorithm, parallelization, route length, traveling salesman problem