Eine der häufigsten Optimierungsaufgaben ist die Fahrzeugroute, bei der die besten Routen für eine Fahrzeugflotte, die eine Reihe von Standorten besucht, ermittelt werden soll. In der Regel bezeichnet „beste“ Routen mit der geringsten Gesamtentfernung oder den geringsten Kosten. Hier einige Beispiele für Routingprobleme:
- Ein Paketzustelldienst möchte Fahrern Routen für die Lieferung zuweisen.
- Ein Kabel-TV-Unternehmen möchte Technikern Routen für hauseigene Anrufe zuweisen.
- Ein Mitfahrdienst möchte Fahrern Routen zuweisen, um Fahrgäste ein- und aussteigen zu lassen.
Das bekannteste Problem bei der Routenplanung ist das Problem der Kunden mit einem Reisenden: Es kann die kürzeste Route für Vertriebsmitarbeiter finden, die Kunden an verschiedenen Standorten besuchen und zum Ausgangspunkt zurückkehren muss. Ein TSP kann durch eine Grafik dargestellt werden, in der die Knoten den Standorten entsprechen und die Kanten (oder Bögen) die direkte Reise zwischen Standorten angeben. Das folgende Diagramm zeigt beispielsweise einen TSP mit nur vier Standorten, die mit A, B, C und D bezeichnet sind. Die Entfernung zwischen zwei beliebigen Orten wird durch die Zahl neben dem Rand angegeben, der sie verbindet.
Wenn Sie die Entfernungen aller möglichen Routen berechnen, sehen Sie, dass die kürzeste Route ACDBA ist, für die die Gesamtstrecke 35 + 30 + 15 + 10 = 90 beträgt.
Je mehr Standorte vorhanden sind, desto schwieriger wird das Problem. Im Beispiel oben gibt es nur sechs Routen. Wenn es jedoch zehn Standorte (ohne Startpunkt) gibt, beträgt die Anzahl der Routen 362880. Für 20 Standorte wird die Nummer in 2432902008176640000 erhöht. Mit einer umfassenden Suche aller möglichen Routen wird garantiert die kürzeste ermittelt, aber dies ist für alle Standorte bis auf kleine Sätze rechenintensiv. Bei größeren Problemen sind Optimierungstechniken erforderlich, um den Lösungsbereich intelligent zu durchsuchen und eine optimale (oder nahezu optimale) Lösung zu finden.
Eine allgemeinere Version des TSP ist das Vehicle Routing Problem (VRP), bei dem mehrere Fahrzeuge vorhanden sind. In den meisten Fällen gelten für VRPs Einschränkungen: Beispielsweise können Fahrzeuge das maximale Gewicht oder Volumen der Objekte haben, die sie mitnehmen können, oder Fahrer müssen die Orte zu bestimmten, vom Kunden angeforderten Zeitfenstern besuchen.
OR-Tools können viele Arten von VRPs lösen, einschließlich der folgenden:
- Problem mit einem Reisenden, das klassische Routenproblem, bei dem es nur ein Fahrzeug gibt.
- Problem mit der Routenplanung: Eine Verallgemeinerung des TSP mit mehreren Fahrzeugen.
- VRP mit Kapazitätseinschränkungen, bei denen Fahrzeuge eine maximale Kapazität für die Elemente haben, die sie transportieren dürfen.
- VRP mit Zeitfenstern, bei denen die Fahrzeuge die Standorte in bestimmten Zeitintervallen anfahren müssen.
- VRP mit Ressourceneinschränkungen, z. B. Speicherplatz oder Personal zum Be- und Entladen von Fahrzeugen im Depot (dem Ausgangspunkt für die Routen).
- VRP mit abgebrochenen Besuchen, wenn die Fahrzeuge nicht alle Standorte anfahren, aber eine Strafe für jeden ausgelassenen Besuch zahlen müssen.
Einschränkungen bei der Lösung von Problemen mit der Routenplanung
Probleme mit der Routenplanung sind grundsätzlich nicht lösbar: Die Dauer der Lösung nimmt mit der Größe des Problems exponentiell zu. Bei ausreichend großen Problemen kann es Jahre dauern, bis OR-Tools (oder andere Routingsoftware) die optimale Lösung gefunden haben. Daher gibt OR-Tools manchmal Lösungen zurück, die zwar gut, aber nicht optimal sind. Ändern Sie die Suchoptionen für den Matherechner, um eine bessere Lösung zu finden. Ein Beispiel finden Sie unter Suchstrategie ändern.