scientific article; zbMATH DE number 4031431
[For the entire collection see Zbl 0627.00024.] Bei einer optimalen Travelling-Salesman-Tour werden bei zwei Transformationen des Datensatzes die Bedingungen untersucht, unter denen die Optimalität der Rundreise erhalten bleibt. Unter den Knoten des Datensatzes wird ein Knoten der optimalen Tour gestrichen (Kontraktion), und zu den n Knoten des Datensatzes wird ein zusätzlicher Knoten hinzugefügt (Expansion). Diese Art der Untersuchung erstreckt sich auf symmetrische Distanzmatrizen, wobei abstrakte Datensätze und euklidische Datensätze betrachtet werden. Im euklidischen Fall werden allgemeine Aussagen zur Gestalt der optimalen Tour und eine schnelle Heuristik hergeleitet.
- Optimal arcs for the traveling salesman problem
- Optimization of a 532-city symmetric traveling salesman problem by branch and cut
- Tours for the traveling salesman
- Nonoptimal Edges for the Symmetric Traveling Salesman Problem
- Improvements to the Or-opt heuristic for the symmetric travelling salesman problem
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3771995)