LogisticsLab/TSP
Das Programm LogisticsLab/TSP dient zur Lösung von Rundfahrt- und Duchfahrtproblemen für
symmetrische und asymmetrische Entfernungen zwischen den anzufahrenden Orten.
Das TSP (Traveling Salesman Problem) oder Rundfahrtproblem wird dadurch charakterisiert,
dass eine bestimmte Anzahl von Orten nacheinander aufzusuchen ist. Von den vielen möglichen
Reihenfolgen muss diejenige gefunden werden, die ein bestimmtes Kriterium (Gesamtstrecke, -kosten oder -dauer)
minimiert. Es gelten folgende Bedingungen:
- Alle Orte müssen auf einer zusammenhängenden Route angefahren werden.
- Jeder Ort muss aufgesucht werden.
Es existieren allerdings auch Probleme, bei denen alle Knoten besucht werden müssen, aber
die Rückkehr zum Startknoten nicht erfolgen soll. Derartige Aufgaben werden Durchfahrtprobleme
oder offene Rundreiseprobleme genannt und können grundsätzlich in folgende vier Arten unterschieden werden:
- Durchfahrtprobleme mit fixiertem Start- und Endknoten,
- Durchfahrtprobleme mit fixiertem Start- und freiem Endknoten,
- Durchfahrtprobleme mit fixiertem End- und freiem Startknoten,
- Durchfahrtprobleme mit freiem Start- und Endknoten.
Zur Lösung des Rundreise- und des Durchfahrtproblems steht LogisticsLab/TSP zur Verfügung. Mit dieser Software können
vielfältige Varianten des symmetrischen bzw. asymmetrischen Rundreise- bzw. Durchfahrtproblems in vollständigen und
nicht vollständigen Graphen abgebildet und mittels heuristischer Lösungsverfahren gelöst werden.
