OR-Tools ist Open-Source-Software für die kombinative Optimierung, die aus einer Vielzahl von möglichen Lösungen die beste Lösung für ein Problem sucht. Hier sind einige Beispiele für Probleme, die mit OR-Tools gelöst werden können:
- Fahrzeugrouten: Finde optimale Routen für Fahrzeugflotten, die Pakete unter Berücksichtigung bestimmter Einschränkungen abholen und liefern (z.B. „Dieser Lkw kann nicht mehr als 10.000 kg halten“ oder „alle Lieferungen müssen innerhalb von zwei Stunden erfolgen“.
- Planung: Finden Sie den optimalen Zeitplan für eine komplexe Reihe von Aufgaben, von denen einige vor anderen, auf einer festen Gruppe von Maschinen oder anderen Ressourcen ausgeführt werden müssen.
- Bin Packing: Verpacken Sie so viele Objekte unterschiedlicher Größe wie möglich in einer festen Anzahl von Klassen mit maximaler Kapazität.
In den meisten Fällen haben Probleme dieser Art eine Vielzahl möglicher Lösungen – zu viele, damit ein Computer sie alle durchsuchen kann. Um dies zu vermeiden, verwendet OR-Tools modernste Algorithmen, um die Suche einzugrenzen und eine optimale Lösung zu finden.
ODER-Tools enthalten folgende Matherechner:
- Einschränkungsprogrammierung
- Eine Reihe von Techniken zur Suche nach umsetzbaren Lösungen für ein Problem, das als Einschränkungen ausgedrückt wird (z.B. kann ein Raum nicht gleichzeitig für zwei Ereignisse verwendet werden oder die Entfernung zu den Nutzpflanzen muss kleiner als die Länge des Schlauchs sein oder es können nicht mehr als fünf Serien gleichzeitig aufgezeichnet werden).
- Lineare und gemischte Ganzzahlen
- Das lineare Optimierungstool Glop ermittelt den optimalen Wert einer linearen Zielfunktion anhand linearer Ungleichheiten als Einschränkungen (z.B. weisen Sie Jobs Jobs zu oder ermittelt die beste Zuweisung einer Reihe von Ressourcen bei gleichzeitiger Kostenminimierung). Glop und die Programmiersoftware SCIP mit gemischter Ganzzahl sind auch über den Optimierungsdienst von Google Apps Script verfügbar.
- Fußwegführung
- Eine spezielle Bibliothek zur Ermittlung der besten Fahrzeugrouten unter Berücksichtigung von Einschränkungen.
- Grafikalgorithmen
- Code zum Suchen der kürzesten Pfade in Diagrammen, Mindestkostenflüssen, Maximalflüssen und linearen Summenzuweisungen.
Im nächsten Abschnitt erhalten Sie einen schnellen Einstieg in die Verwendung von OR-Tools.