Parts | Days | Selection | Search | Updates | Downloads | Help
SOE: Fachverband Physik sozio-ökonomischer Systeme
SOE 16: Networks: From Topology to Dynamics III (with BP, DY)
SOE 16.1: Talk
Wednesday, March 16, 2011, 15:30–15:45, GÖR 226
Traveling Salesman Problem with Clustering — •Johannes Josef Schneider1, Thomas Bukur2, and Antje Krause2 — 1Department of Physics, Mathematics, and Computer Science, Johannes Gutenberg University of Mainz, Staudinger Weg 7, 55099 Mainz, Germany — 2Fachhochschule Bingen -- University of Applied Sciences, 55411 Bingen, Germany
In the original traveling salesman problem, the traveling salesman has the task to find the shortest closed tour through a proposed set of nodes, touching each node exactly once and returning to the initial node at the end. For the sake of the tour length to be minimized, nodes close to each other might not be visited one after the other but separated in the tour. However, for some practical applications, it is useful to group nodes to clusters, such that all nodes of a cluster are visited contiguously. Here we present an approach which leads to an automatic clustering with a clustering parameter governing the sizes of the clusters.
[1] Johannes J. Schneider, Thomas Bukur, and Antje Krause, Traveling Salesman Problem with Clustering, J. Stat. Phys. 141, 767-784, 2010.