Finding the shortest tour visiting all given points at least ones belongs to the most
famous optimization problems until today [travelling salesman problem (TSP)]. Optimal
solutions exist formany problems up to several ten thousand points. Themajor difficulty in
solving larger problems is the required computational complexity. This shifts the research
from finding the optimum with no time limitation to approaches that find good but
sub-optimal solutions in pre-defined limited time. This paper proposes a new approach
for two-dimensional symmetric problems with more than a million coordinates that is able
to create good initial tours within few minutes. It is based on a hierarchical clustering
strategy and supports parallel processing. In addition, a method is proposed that can
correct unfavorable paths with moderate computational complexity. The new approach
is superior to state-of-the-artmethods when applied to TSP instances with non-uniformly
distributed coordinates.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:84437 |
| Date | 30 March 2023 |
| Creators | Strutz, Tilo |
| Publisher | Frontiers Research Foundation |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, doc-type:article, info:eu-repo/semantics/article, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | 2296-9144, 652417 |
Page generated in 0.002 seconds