World TSP (beendet)

Das Travelling Salesman Problem (TSP) ist sehr einfach zu beschreiben und doch sehr schwer zu lösen: Wenn ein Vertreter eine bestimmte Anzahl von Orten auf seiner Verkaufstour jeweils genau einmal besuchen und danach zu seinem Heimatort zurückkehren will, welches ist dann die kürzeste Route über alle Orte? Dabei sind alle Paare von Entfernungen zwischen je zwei Orten bekannt.

Prinzipiell lässt sich das Problem sehr einfach durch das Berechnen sämtlicher möglicher Routen lösen. In der Praxis steht dem aber eine extrem schnell wachsende Anzahl von möglichen Routen entgegen. So sind zum Beispiel bei 16 Orten bereits 653.837.184.000 verschiedene Routen möglich.

Deshalb beschränken sich Algorithmen zur Lösung des Problems für große Mengen von Orten auch darauf, eine möglichst gute, aber nicht unbedingt optimale Lösung zu liefern.

Die Universität von Princeton hat einen Wettbewerb ausgeschrieben, bei dem es darum geht, das Travelling Salesman Problem für 1.904.711 Orte zu lösen. Dabei handelt es sich um sämtliche bewohnten Ortschaften der Erde. Die Daten dafür stammen von der National Imagery and Mapping Agency sowie dem Geographic Names Information System (GNIS). Jeder Ort ist dabei mit Länge und Breite verzeichnet. Die Entfernung wird als kürzeste Entfernung auf der Erdoberfläche gemessen, wobei die Erde als ideale Kugel angenommen wird.

Die beste bisher bekannte Lösung dieses Problems wurde von Keld Helsgaun gefunden und hat eine Länge von 7.518.528,361 Kilometern. Außerdem ist bekannt, dass die Mindestlänge der Tour 7.510.666,782 Kilometer betragen muss (untere Schranke). Ziel dieses Projektes ist es, einen neuen Rekord für die Berechnung der Strecke aufzustellen.

Siehe auch:

• TSP
• Genetic TSP

Projektübersicht

World TSP
Name	World TSP
Kategorie	Mathematik
Ziel	Aufstellen eines neuen Rekords für das Travelling Salesman Problem
Kommerziell	nein
Homepage	offline, hier Archive.org Link

Es ist uns leider nicht bekannt, wo auf der Welt dieses Projekt zu Hause ist.

Projektstatus

Projektstatus
Status	beendet
Beginn	23.05.2003
Ende	31.07.2003

Projektlinks

(nicht mehr online)

Hintergrundinfos	www.theneoproject.com/main.asp?PageRequest=ABOUTTSP
Anmelden	www.theneoproject.com/main.asp?PageRequest=DOWNLOADS
FAQ	www.theneoproject.com/main.asp?PageRequest=FAQS
Statistiken	tnp.redirectme.net
Mailingliste/Forum	www.theneoproject.com/main.asp?PageRequest=FORUM

Clientprogramm

Betriebssysteme

	Windows
	Linux
	DOS
	BSD
	Solaris
	Java (betriebssystemunabhängig)

Client-Eigenschaften

Funktioniert auch über Proxy
Normal ausführbares Programm
Als Bildschirmschoner benutzbar
Kommandozeilenversion verfügbar
Personal Proxy für Work units erhältlich
Work units auch per Mail austauschbar
Quellcode verfügbar
Auch offline nutzbar
Checkpoints

Besonderheiten des Clients

• Voraussetzung für das Betreiben des Clients ist die Installation des .NET-Frameworks von Microsoft.
• Der Client basiert auf künstlicher Intelligenz. Er lernt aus jeder seiner berechneten Routen hinzu und versucht, diese im nächsten Anlauf zu verbessern.
• Nach der Installation lädt der Client ca.10 MB an Positionsdaten für die verschiedenen Orte aus dem Netz.
• Insgesamt belegt der Client extrem viel Speicherplatz (>100 MB) auf der Festplatte.
• Die Uploads des Programms können bis zu 6 MB groß sein.

Veröffentlichte Versionen

• 27.06.2003: 2.0.25

• 02.06.2003: 2.0.22

• 25.05.2003: 2.0.0

Screenshots

• 

  Installation (1/5) - Angabe sämtlicher Benutzerdaten

• 

  Installation (2/5) - Download des benötigten Kernels

• 

  Installation (3/5) - Nach dem Download des eigentlichen Rechenkerns werden noch zusätzlich ca. 10 MB an Positionsdaten heruntergeladen.

• 

  Installation (4/5) - Die heruntergeladenen Positionsdateien werden mit einer Checksumme überprüft.

• 

  Installation (5/5) - Zu guter Letzt werden die Positionsdaten entpackt und belegen dann knapp 60 MB auf der Platte.

• 

  Initiale Route - Der Client berechnet nach der Installation eine initiale Route. Während dieser Zeit (1 bis 2 Stunden) ist die Festplatte im Dauerzugriff.

• 

  Optimierung der Route - Nachdem die erste Route festgelegt wurde, versucht der Client immer wieder, sie zu optimieren.