Bereiche | Tage | Auswahl | Suche | Downloads | Hilfe

AKSOE: Physik sozio-ökonomischer Systeme

AKSOE 14: Urbane Systeme und Verkehrsdynamik II

AKSOE 14.3: Vortrag

Dienstag, 12. März 2002, 15:00–15:30, H8

Ein Handlungsreisender im Stau — •Johannes Schneider¹ und Johannes Bentner² — ¹School of Engineering and Computer Science, The Hebrew University of Jerusalem, Givat Ram, Jerusalem 91904, Israel — ²Fakultät Physik, Universität Regensburg, D-93040 Regensburg

Das Problem des Handlungsreisenden besteht darin, die kürzeste geschlossene Rundreise durch eine vorgegebene Menge von Orten zu finden, wobei die Abstände zwischen den einzelnen Orten konstant vorgegeben sind. Variieren die Abstände während des Tages, z.B. wegen eines Staus in der Innenstadt zu gewissen Zeiten, so erhält man das komplexere Time-dependent Traveling Salesman Problem. Wir werden anhand eines einfachen Beispiels auf der Grundlage des Problems der 127 Biergärten in Augsburg und Umgebung aufzeigen, wie der Handlungsreisende seine Tour verändert, um den Staubereichen zu entgehen, und wie die Optimierung eines derartigen Problems mit Simulated Annealing abläuft.