Wer Tourenoptimierung nicht als fertiges Produkt kauft, sondern in die eigene Systemlandschaft baut, landet bei einer überschaubaren Zahl offener Bibliotheken. Sie sind ausgereift, kostenlos und gut dokumentiert. Sie unterscheiden sich aber erheblich – und bei einer davon steht in der Lizenz ein Satz, der kommerzielle Nutzung ausschließt.
Google OR-Tools
Lizenz Apache 2.0, also uneingeschränkt kommerziell nutzbar. Die aktuelle Fassung ist v9.15 vom Januar 2026.
Was drin ist: Fünf Metaheuristiken plus Automatik – Greedy Descent, Guided Local Search, Simulated Annealing, Tabu Search, Generic Tabu Search. Dazu siebzehn Startheuristiken, darunter Savings und Parallel Savings. Guided Local Search ist der Standard; Google bezeichnet sie im Quellcode als „generally the most efficient metaheuristic for vehicle routing".
Restriktionen: Kapazitäten und beliebige kumulierende Größen über Dimensionen, Zeitfenster, Pickup-and-Delivery, optionale Stopps mit Strafkosten, Fahrerpausen, mehrere Depots und fahrzeugindividuelle Start- und Endpunkte, Ressourcengruppen wie Laderampen.
Was man wissen muss. Drei Dinge überraschen in Projekten regelmäßig:
- Das Zeitlimit ist standardmäßig praktisch unendlich. Die Metaheuristiken beenden sich nicht selbst. Wer kein Limit setzt, wartet.
- OR-Tools rechnet keine Entfernungen. Die Distanzmatrix oder Fahrzeitfunktion kommt von außen – aus OSRM, Valhalla oder einem eigenen Netz.
- Es gibt keine Optimalitätsgarantie. Google schreibt in der Dokumentation selbst: „For sufficiently large problems, it could take OR-Tools (or any other routing software) years to find the optimal solution."
Leistung. Hier ist Vorsicht geboten. Die einzige öffentlich dokumentierte Gegenüberstellung stammt vom Projekt PyVRP (Stand Mai 2024, OR-Tools v9.10): mittlere Abweichung zur besten bekannten Lösung von 4,42 Prozent bei CVRP, 9,38 Prozent bei VRPTW. PyVRP selbst kam auf 0,31 beziehungsweise 0,65 Prozent.
Diese Zahlen sind mit Vorbehalt zu lesen: PyVRP wird von einem Unternehmen entwickelt, das eine kommerzielle Enterprise-Version verkauft – es ist die Messung eines Wettbewerbers. Dafür spricht: Die Skripte sind offen, und die Methodik wurde nach öffentlicher Kritik überarbeitet, wobei sich die OR-Tools-Werte deutlich verbesserten.
Eine gern kolportierte Behauptung stimmt übrigens nicht: OR-Tools hat an der 12. DIMACS Implementation Challenge nicht teilgenommen. In den offiziellen Ergebnislisten taucht es weder bei CVRP noch bei VRPTW auf.
VROOM
Lizenz BSD 2-Clause, ebenfalls uneingeschränkt kommerziell nutzbar. Aktuell v1.15.0 vom März 2026.
Was drin ist – und was nicht. VROOM wird häufig als „Ruin-and-Recreate"-Solver beschrieben. Das stimmt nicht. Im Quellcode findet sich eine Variante der Solomon-I1-Konstruktionsheuristik, gefolgt von einem festen Satz lokaler Suchoperatoren, darunter Vidals SWAP*-Nachbarschaft. Eine LNS-Komponente gibt es nicht. Die Diversifikation steuert man über einen Explore-Level von 0 bis 5.
Restriktionen: Kapazitäten auf beliebigen Metriken, mehrere Zeitfenster je Auftrag, Service- und Rüstzeiten, Skills (ein Auftrag ist einem Fahrzeug nur zugeordnet, wenn dessen Fähigkeiten die geforderten enthalten), Prioritäten von 0 bis 100, Fahrerpausen, Arbeitszeiten je Fahrzeug, offene Touren, maximale Aufgabenzahl, maximale Fahrzeit und Distanz. Ein Planungsmodus meldet Verstöße, statt die Rechnung scheitern zu lassen. Als Routing-Engine kommen OSRM, Openrouteservice oder Valhalla in Frage.
Leistung. VROOM veröffentlicht eigene Benchmarks – vorbildlich transparent:
- VRPTW (Solomon, 56 Instanzen à 100 Aufträge): Median +1,12 Prozent, Mittel +1,63 Prozent, Median 382 ms
- CVRP (CVRPLIB, 189 Instanzen, 15 bis 1.000 Aufträge): Median +0,68 Prozent, Mittel +1,30 Prozent, Median 505 ms
- PDPTW (Li & Lim): Median +0,00 Prozent
Zwei Einschränkungen stehen auf derselben Seite: Bei CVRP wurden nur bei 90,5 Prozent der Instanzen alle Aufträge zugeordnet – die Abweichungen beziehen sich auf die vollständig gelösten. Und die längste Rechnung dauerte 110,1 Sekunden.
Das ist relevant, weil die kommerzielle Projektseite mit „Complex route optimization in milliseconds" wirbt. Der eigene Benchmark des Projekts zeigt im schlechtesten Fall knapp zwei Minuten. Wir halten uns an die Projektzahlen.
LKH und LKH-3
Und hier das Lizenzdetail, das entscheidend ist. Auf beiden Projektseiten steht wörtlich:
„The code is distributed for academic and non-commercial use. The author reserves all rights to the code."
Es gibt keine OSI-Lizenz und keine Erlaubnis zur kommerziellen Nutzung. Wer LKH in ein Produkt einbaut, das er verkauft oder betreibt, braucht eine gesonderte Vereinbarung mit dem Autor. LKH als „Open Source" zu bezeichnen, ist in diesem Punkt irreführend.
Fachlich ist LKH beeindruckend. Keld Helsgaun schreibt auf der Projektseite, LKH habe für alle bislang gelösten Probleme optimale Lösungen erzeugt, darunter eine Instanz mit 109.399 Städten, und die besten bekannten Lösungen für großmaßstäbliche Instanzen verbessert, bis hin zu einer mit 1.904.711 Städten. Ein unabhängiger Benchmark von Hans Mittelmann (Juli 2026) zeigt auf TSPLIB-Instanzen Abweichungen von 0 bis 0,09 Prozent.
LKH-3 (aktuell 3.0.14, Juni 2026) deckt rund fünfzig eingeschränkte Varianten ab, darunter CVRP, CVRPTW, PDPTW und VRPB – technisch, indem es sie in symmetrische TSP-Probleme überführt und Restriktionen über Straffunktionen behandelt. Eine veröffentlichte aggregierte Kennzahl „LKH-3 liegt X Prozent über dem Bestwert bei CVRP" existiert allerdings nicht; der technische Bericht enthält nur Einzelinstanzen.
Zwei weitere, die man kennen sollte
HGS-CVRP (MIT-Lizenz) ist der Referenzalgorithmus für CVRP. Bemerkenswert ist die Ehrlichkeit der Projektdokumentation:
„This code version has been designed and calibrated for medium-scale instances with up to 1,000 customers. It is not designed in its current form to run very-large scale instances (e.g., with over 5,000 customers)."
PyVRP (MIT-Lizenz) ist gut dokumentiert und schneidet in Benchmarks stark ab. Zwei Hinweise: Der Fachartikel von 2024 beschreibt eine hybride genetische Suche, die aktuelle Dokumentation eine iterierte lokale Suche – das Verfahren wurde gewechselt. Und Fahrerpausen sind eine kostenpflichtige Enterprise-Funktion. Für die Abbildung europäischer Lenk- und Ruhezeiten ist das erheblich; OR-Tools und VROOM haben Pausen in der freien Version.
Was das für ein eigenes Projekt bedeutet
Eine nüchterne Zusammenfassung:
- Für die meisten Projekte ist OR-Tools die pragmatische Wahl. Apache-2.0, breite Restriktionsabdeckung, Pausen inklusive, große Community. Die Benchmark-Werte sind schlechter als bei spezialisierten Solvern – im Betrieb entscheidet das selten.
- VROOM ist attraktiv, wenn Skills, Prioritäten und mehrere Zeitfenster je Auftrag gebraucht werden und man eine schlanke HTTP-Schnittstelle mit direkter OSRM- oder Valhalla-Anbindung will.
- LKH scheidet für kommerzielle Nutzung ohne Sondervereinbarung aus. Das ist eine Rechts-, keine Geschmacksfrage.
- Keine dieser Bibliotheken rechnet Ihr Wegenetz. Das Straßennetz, die Fahrzeugprofile und die Fahrzeiten sind eigene Arbeit – und in der Praxis der aufwendigere Teil. Was dabei zu beachten ist, steht bei Custom Routing.
Der Solver ist der kleinste Teil eines Tourenplanungsprojekts. Der große Teil ist das Modell: welche Regeln gelten, welche Daten stimmen, welche Fahrzeuge dürfen wohin. Wer dort sauber arbeitet, kommt mit jeder der genannten Bibliotheken weit.
Wie sich Routing-Engine, Solver und Distanzmatrix zu einem eigenen Dienst zusammensetzen, beschreibt der Leitfaden Routing- und Optimierungs-API. Die Abgrenzung zwischen fertigem Produkt und eigenem Modell steht unter Tourenplanung Software.
Quellen
- Google OR-Tools, Quelldateien
routing_enums.protoundrouting.h, sowie developers.google.com/optimization/routing (Apache-2.0) - Cuvelier, T.; Didier, F.; Furnon, V.; Gay, S.; Mohajeri, S.; Perron, L. (2023): OR-Tools' Vehicle Routing Solver. ROADEF 2023.
- VROOM-Projekt, Benchmark-Seite und Quellcode. github.com/VROOM-Project/vroom (BSD 2-Clause)
- Helsgaun, K. (2000): An effective implementation of the Lin–Kernighan traveling salesman heuristic. EJOR 126(1), S. 106–130. doi.org/10.1016/S0377-2217(99)00284-2
- Helsgaun, K. (2017): An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems. Technischer Bericht, Roskilde Universität.
- Wouda, N. A.; Lan, L.; Kool, W. (2024): PyVRP: A High-Performance VRP Solver Package. INFORMS Journal on Computing 36(4), S. 943–955. doi.org/10.1287/ijoc.2023.0055
- Vidal, T. (2022): Hybrid genetic search for the CVRP. Computers & Operations Research 140, 105643. doi.org/10.1016/j.cor.2021.105643
- Mittelmann, H. (2026): Concorde, Hexaly, and LKH on TSPLIB, Stand 28. Juli 2026.