Auf einem gewichteten Graphen den Pfad minimaler Gesamtgewichtssumme zwischen zwei Knoten finden — in den Varianten Single-Source-Single-Destination, Single-Source-All-Destinations oder All-Pairs. Grundlegendes Graphen-OR-Problem; klassische Algorithmen sind Dijkstra, Bellman-Ford, Floyd-Warshall. Der in der modernen Industrie am häufigsten aufgerufene OR-Algorithmus.
Kurz gesagt
Kommt Ihnen das bekannt vor?
- Wir sind ein inländischer Paket-Routing-Anbieter — für 5.000-50.000 Pakete pro Tag benötigen wir zeitkürzeste Routen vom Zentrallager zu Kundenadressen; wir brauchen Multi-Kriterien-Optimierung über Zeit, Distanz und Treibstoff.
- Wir betreiben einen städtischen Field-Service mit 10-50 Fahrzeugen (Klempner, Elektriker, Reparatur weißer Ware, HLK); wir berechnen Kunde-zu-Kunde-Fahrtzeiten und wollen eine verkehrsbewusste Rechen-Engine.
- Wir sind eine kommunale Verkehrsleitstelle; wir wollen eine Brücke zwischen Echtzeit-Verkehrsdaten und dem statischen Kartennetzwerk, um verkehrsbewussten Kürzester-Pfad für Rettungsdienste (Krankenwagen, Feuerwehr, Polizei) bereitzustellen.
- Wir sind Telekommunikations-Backbone-Netzplaner; wir berechnen den Paketweiterleitungspfad mit der geringsten Latenz zwischen zwei Switches (oder zwei POPs); Routingprotokolle wie OSPF (Open Shortest Path First) führen diese Berechnung darunter aus.
- Wir sind Lieferketten-Planer; in einem Fabrik-Hafen-Lager-Kunde-Netzwerk benötigen wir die günstigsten Flusskosten zwischen jedem Knotenpaar (All-Pairs-Shortest-Path) — über multimodale Transportoptionen.
- Wir sind Mautstreckenbetreiber oder Spediteur; für Fernverkehrsrouting führen wir einen Drei-Kriterien-Kürzester-Pfad (Treibstoff + Maut + Fahrstunden) aus; statischer Graph reicht nicht, wir suchen zeitabhängigen Kürzester-Pfad.
- Unser Software-Team begann mit einer direkten Dijkstra-Implementierung, aber Echtzeit-Anfragen auf großen Graphen (1M+ Knoten, landesweites Straßennetz) sind zu langsam — wir prüfen vorverarbeitungsbasierte (Contraction Hierarchies) Lösungen.
Warum es wichtig ist
Wie wird es gelöst?
Technische Tiefe
Wie wird es gelöst?
Technische TiefeIn einem Satz: Gegeben Knoten (Kreuzungen) + gewichtete Kanten (Distanz/Zeit), nutze Dijkstra, wenn Kanten nicht-negativ sind (in jedem Schritt den nächsten Nachbarn wählen und Nachbar-Distanzen aktualisieren), Bellman-Ford, wenn negative Kanten möglich sind, Floyd-Warshall, wenn eine All-Pairs-Distanzmatrix nötig ist — jedes Verfahren garantiert das Optimum.
Dieses Problem wird in der Operations-Research-Literatur (Disziplin, die Mathematik und Computer für Geschäftsentscheidungen einsetzt) als Shortest Path Problem (SPP — Kürzester-Pfad-Problem) untersucht — das grundlegende Graphen-OR-Problem, 60+ Jahre Reife. Drei Hauptvarianten: Single-Source-Single-Destination (ein Punkt zu Punkt), Single-Source-All-Destinations (von einer Quelle zu allen Zielen), All-Pairs (jedes Paar). Klassische Grundalgorithmen stammen aus den späten 1950ern und 1960ern: Dijkstra für nicht-negative Kanten, Bellman-Ford für negative Kanten, Floyd-Warshall für All-Pairs; moderne vorverarbeitungsbasierte Contraction Hierarchies erreichen Sub-Millisekunden-Abfragezeit auf landesweiten Straßennetzen. Drei Stufen:
1. Modellierung. Eingabedaten: (a) Graphstruktur — Knotenmenge V (Kreuzungen, Standorte, Switches), Kantenmenge E (Straßen, Verbindungen), Kantengewichte w(u,v) (Distanz, Zeit, Kosten, Latenz), gerichtet (Einbahnstraße) oder ungerichtet (Zweirichtung), Kantengewichte nicht-negativ oder ggf. negativ, mit oder ohne negative Zyklen, (b) Anfragetyp — Single-Point-to-Point (Quelle s, Ziel t), Single-Source-All-Destinations (Quelle s, Ziel V), All-Pairs (jedes i,j-Paar), (c) Dynamik — Graphgewichte statisch, zeitabhängig (Verkehr abhängig von der Tageszeit) oder mit Echtzeit-Updates (Unfälle, Wetter), (d) Multi-Kriterien — Single-Objective (nur Zeit) oder Multi-Objective (Zeit + Distanz + Treibstoff + Maut); Multi-Objective mit Pareto-optimalen Pfaden oder gewichteter Summe, (e) Bedingungen — Straßentyp-Verbote (LKW darf bestimmte Straßen nicht befahren, Krankenwagen ausgenommen), Zeitfenster (Arbeitszeiten), Kapazität (zu transportierende Last). Entscheidungsvariablen: Kantenfolge auf dem Graphen (s → … → t), Per-Kante-Variable “auf-dem-Pfad-oder-nicht”. Ziel: minimale Summe der Kantengewichte.
2. Solver-gesteuerte Entscheidung. Algorithmenwahl hängt von Graph und Anfragetyp ab:
(a) Dijkstra — nicht-negative Kanten, Single-Source. Gierig (Greedy — in jedem Schritt die lokal beste Wahl): in jedem Schritt den unbesuchten Knoten mit kleinster vorläufiger Distanz aus einer Prioritätswarteschlange ziehen und Distanzen seiner Nachbarn aktualisieren. Binary-Heap-Implementierung O((V+E)logV), Fibonacci-Heap O(E + V logV). In der Praxis: Single-Source-Single-Destination / Single-Source-All-Destinations, kleine-mittlere statische Graphen (1K-100K Knoten).
(b) Bellman-Ford — unterstützt negative Kanten. Relaxation (Re-Check jeder Kante auf “gibt es jetzt einen kürzeren Pfad”) über alle Kanten V-1 mal. Komplexität O(VE). Erkennung negativer Zyklen: wenn in Iteration V weiterhin eine Aktualisierung auftritt, existiert ein negativer Zyklus, und der kürzeste Pfad ist undefiniert. Einsatz: Graphen mit negativen Kanten (Finanzarbitrage, Netzwerkfluss-Rückfluss), Distance-Vector-Routingprotokolle.
(c) Floyd-Warshall — All-Pairs, kleiner Graph. Dynamische Programmierung: O(V³) Zeit, O(V²) Speicher. In der Praxis: V ≤ 1.000 Knoten, wenn All-Pairs benötigt wird. Unterstützt negative Kanten (ohne Zyklen).
(d) A — heuristik-geführter Single-Point-to-Point.* Zielgerichtete Variante von Dijkstra; eine Heuristik h(v) (z.B. euklidische / Großkreis-Distanz) leitet Knotenprioritäten. Hart, Nilsson und Raphael (1968). In der Praxis: Single-Source-Single-Destination auf geographischen Straßennetzwerken, Spielkarten-Pfadfindung. Im Durchschnitt schneller als Dijkstra; wenn die Heuristik zulässig ist (h ≤ wahre Distanz), ist Optimum garantiert.
(e) Bidirektionale Suche. Dijkstra/A* vorwärts von der Quelle und rückwärts vom Ziel ausführen; stoppen, wenn sich die zwei Suchen treffen. Typischerweise 2-4x schneller als einrichtungs-Dijkstra.
(f) Contraction Hierarchies (Geisberger et al. 2008) — modern vorverarbeitungsbasiert für landesweite Straßennetze. Graph wird einmal vorverarbeitet (Knoten werden in hierarchischer Reihenfolge ‘kontrahiert’, Abkürzungen hinzugefügt); jede nachfolgende Anfrage in Sub-Millisekundenzeit beantwortet. Feldstandard für Echtzeitnavigation auf landesweiten (10M+ Kanten) Straßennetzen. ALT (A*, Landmarks, Triangle inequality), Transit Node Routing und Hub Labels sind weitere moderne vorverarbeitungsbasierte Methoden.
(g) Zeitabhängiger Kürzester-Pfad — verkehrsbewusst. Kantengewichte sind Funktionen der Zeit w(u,v,t); Fahrtzeit hängt von Abfahrtszeit t ab. Statisches Dijkstra wird verallgemeinert; wenn die FIFO-Eigenschaft gilt (spätere Abfahrt — keine frühere Ankunft), ist das Problem polynomial. In der Praxis: eine durch Verkehrsprognosedaten gespeiste Routing-Engine.
(h) Stochastischer Kürzester-Pfad. Kantengewichte sind Zufallsvariablen (z.B. Verkehrsverteilung); Erwartungswert- oder risikobereinigter (CVaR) Kürzester-Pfad; Polychronopoulos-Tsitsiklis (1996).
3. Feldintegration. Ausgabe ist dreischichtig: (a) operativ — Adresse-zu-Adresse-Routenanzeige in der Fahrer-Mobil-App / Paket-Lieferroute / Field-Service-Techniker-App, integriert mit Navigation, (b) Planung — die Kürzester-Pfad-Matrix wird als Subroutine unter VRP/TSP-Optimierung in täglicher Routenplanungssoftware aufgerufen, (c) strategisch / analytisch — Lieferketten-Netzwerkanalyse, Telekom-Netz-Engpassberichte, All-Pairs-Distanz-/Zeit-Matrix für Entscheidungsunterstützung. Upstream-Integration: ERP (Bestelladressen), TMS (Transport Management System), Kartendienst (Geocoding + Straßennetzwerkdaten), Verkehrsdaten-Service (Echtzeit-Prognose), Flotten-Tracking-GPS-Daten. Quartalsweises Operations-Komitee: Kürzester-Pfad-Anfragevolumen, durchschnittliche Anfragezeit, Verkehrsprognose-Drift (real vs. Plan), Routenänderungsrate (Recompute-Auslöser).
Alternativen
Manuell + Kartendienst + Fahrererfahrung
KostenlosKartendienst Free Tier, null Entwicklungskosten
Für wen geeignet: Kleinbetrieb (1-10 Fahrzeuge/Tag), 10-50 Stopps/Fahrzeug, bekannte statische Routen
- + Null Software-Investition
- + Fahrer-Feldwissen zählt
- + Telefonbasierte Echtzeit-Verkehrsreaktion
- − Keine Optimum-Garantie, intuitive Fahrerroute bläht Distanz um 15-30% auf
- − Keine Multi-Kriterien-Berechnung (Zeit + Treibstoff + Maut)
- − Keine Datenerfassung — Leistung wird nicht gemessen
- − Über 10 Fahrzeuge wird Planerkapazität überschritten
Kartendienst-API + interne Integration
cloudPro-Anfrage-Preise; €0,003-0,01/Anfrage, bei 50K Paketen/Tag ergibt das €2K-7K/Monat
Für wen geeignet: Mittelbetrieb (50-500 Fahrzeuge, 50K-500K Stopps/Tag), verkehrsbewusste Anfragen gewünscht
- + Reife Verkehrsdaten integriert
- + Adress-Geocoding integriert
- + API einfach zu konsumieren, kurze Entwicklungszeit
- − Pro-Anfrage-Kosten werden bei hohem Volumen teuer
- − Algorithmus ist eine Blackbox, Kontrolle begrenzt
- − Anbieter-Lock-in (Kartendienstvertrag)
- − Skaliert nicht für All-Pairs- / große-Matrix-Anfragen
Open-Source-Straßennetzwerk-Engine + eigene Server
Open SourceLizenz kostenlos; interne Entwicklung + Server 6-12 Wochen oder €80K-250K Beratung + €15K-50K/Jahr Infrastruktur
Für wen geeignet: Betrieb mit Tech-Team, hohes Anfragevolumen (1M+/Tag), spezialisierte Bedingungen (LKW-Straßentypverbote)
- + Keine Lizenzkosten, keine Pro-Anfrage-Gebühr
- + Algorithmenwahl unter eigener Kontrolle (Dijkstra, A*, Contraction Hierarchies)
- + Spezialisierte Bedingungen (LKW-Zugang, Krankenwagen-Ausnahme) einbettbar
- + Datenhoheit bleibt intern
- + 30+ TR-Dissertationen (YÖK) als Referenzimplementierungen verfügbar
- − Straßennetzwerkdaten (OpenStreetMap-Qualität) erfordern periodische Updates
- − Verkehrsdaten erfordern einen separaten Anbieter
- − Interner OR-Spezialist + Infrastruktur-Team nötig
- − Akademischer Prototyp zu Produktion: 3-6 Monate
Internationale Routing- / TMS-Plattform
Enterprise€300K-2M Lizenz + €100K-500K/Jahr Wartung
Für wen geeignet: Großbetrieb (500+ Fahrzeuge, Multi-Site, 1M+ Stopps/Tag), volle TMS-Integration
- + Reifes Kürzester-Pfad + VRP-Modul integriert
- + Multi-Kriterien (Zeit + Kosten + Treibstoff + Maut) Standard
- + Zeitabhängige + stochastische Varianten unterstützt
- + Verkehrsdienst im Paket enthalten
- − Hohe Lizenz + lange (12-24 Monate) Einführung
- − Lokale Straßennetzwerk-Kalibrierung verlängert das Projekt
- − Algorithmus ist Blackbox — Vorverarbeitungsparameter-Kontrolle begrenzt
- − Hohes Single-Supplier-Lock-in-Risiko
Empfehlung
Im Gespräch fragen
- Welchen Ansatz nutzt der Kürzester-Pfad-Algorithmus — Dijkstra (Binary-Heap, Fibonacci-Heap), A*, bidirektionale Suche, Contraction Hierarchies, ALT? Wie groß ist die durchschnittliche Anfragezeit auf einem landesweiten Straßennetzwerk (10M+ Kanten)?
- Werden negative Kanten unterstützt (Bellman-Ford)? Gibt es Erkennung negativer Zyklen? In welchen Szenarien (Finanzarbitrage, Rückfluss) wird auf Bellman-Ford zurückgegriffen?
- Ist zeitabhängiger (verkehrsbewusster) Kürzester-Pfad unterstützt? Aus welcher Quelle stammen Verkehrsdaten, in welcher Frequenz (5-Min, 15-Min, stündlich)? Ist die FIFO-Eigenschaft garantiert?
- Woher stammen Straßennetzwerkdaten (OpenStreetMap, kommerzieller Kartendienst, nationales Straßenverzeichnis)? Wie ist der Datenaktualisierungszyklus? Wie werden Straßentypen (Autobahn, geteilte Straße, Stadt, Schwerverkehr) als Bedingungen modelliert?
- Ist All-Pairs-Kürzester-Pfad (Floyd-Warshall, Johnson) unterstützt, bis zu welcher Größe (wieviele Knoten)? Wie wird die All-Pairs-Distanzmatrix für eine Lieferketten-Netzwerkanalyse erzeugt?
- Ist Multi-Kriterien (Zeit + Distanz + Treibstoff + Maut) Optimierung unterstützt — gewichtete Summe oder Pareto-optimale Pfade? Können Multi-Objective-Parameter vom Nutzer eingestellt werden?
- Welcher Einsparungsbericht kann in einem Pilot mit realen operativen Daten (8-12 Wochen) gegenüber der vorherigen manuellen / bestehenden Systemroute erstellt werden — Treibstoff, Lieferzeit, Fahrerstunden, Routenänderungsrate?
- Wenn der Vertrag endet, in welchem Standardformat (GeoJSON, GraphML, CSV) können wir Straßennetzwerkdaten, Verkehrskalibrierungsdaten, Anfragehistorie und Routenarchiv exportieren?
Technische Details
Anmerkung des Herausgebers
In der Alltagssprache heißt dieses Problem “Kürzester Weg”, “Routenberechnung” oder “Navigation”. In der akademischen Literatur ist der kanonische Name Shortest Path Problem (SPP), das grundlegende Graphen-OR-Problem. Edsger Dijkstra (1959) definierte in einem zweiseitigen Numerische Mathematik-Papier einen polynomialen Algorithmus für Graphen mit nicht-negativen Kanten — dieses Papier zählt zu den meistzitierten der Informatik. Richard Bellman (1958) führte in Quarterly of Applied Mathematics den negativ-kanten-fähigen Bellman-Ford ein. Robert Floyd (1962) entwickelte in Communications of the ACM Algorithmus 97 (ein einseitiges Papier) All-Pairs Floyd-Warshall. Ahuja, Magnanti und Orlin (1993) Network Flows ist das kanonische Lehrbuch. Moderne vorverarbeitungsbasierte Ansätze (Geisberger et al. 2008 — Contraction Hierarchies) liefern Sub-Millisekunden-Anfragezeit auf landesweiten Straßennetzen.
Unterschied zu #068 (TSP): TSP ist das Tour-über-alle-Knoten-Problem — jeden der N Knoten genau einmal besuchen und zum Start zurückkehren, NP-schwer, das grundlegende kombinatorische Optimierungsproblem. Shortest Path ist das Single-Point-to-Point oder Single-Source-All-Destinations-Problem — polynomial (Dijkstra O((V+E)logV), Bellman-Ford O(VE), Floyd-Warshall O(V³)). Die Komplexitätslücke ist groß: für einen 1.000-Knoten-Graphen endet Dijkstra in Millisekunden, TSP läuft Stunden-Tage. TSP ruft Shortest Path als Subroutine auf: die paarweise Distanzmatrix wird durch Shortest Path berechnet, dann löst TSP das Tour-Problem auf der Matrix.
Unterschied zu #069 (CVRP): CVRP ist kapazitäres Flottenrouting — mehrere Fahrzeuge, kapazitätsbeschränkt, Kunden gemeinsam bedient. CVRP ruft Shortest Path als Subroutine auf: Kunde-zu-Kunde- und Lager-zu-Kunde-Distanzen werden durch Shortest Path berechnet, dann löst CVRP das Fahrzeug-Kunde-Zuordnungs- + Routensequenzproblem. In diesem Stack spielt Shortest Path die Rolle “fülle die Graphgewichtsmatrix” und CVRP die Rolle “Fahrzeug-Kunde-Zuordnung + Sequenzierung”.
Unterschied zu #002 (VRPTW): VRPTW ist Flottenrouting mit Zeitfenstern — mehrere Fahrzeuge, Kapazitäts- + Zeitfenster-Bedingungen. VRPTW ruft ebenfalls Shortest Path als Subroutine auf. Wenn zeitabhängiger Kürzester-Pfad in VRPTW eingebettet wird, entsteht verkehrsbewusstes Flottenrouting.
Im Feld am häufigsten übersehener Punkt: Erkennung negativer Kanten oder negativer Zyklen. Der Praktiker verwendet Dijkstra in jedem Fall; aber bei negativen Kosten (z.B. Rabatt auf eine Verbindung, Kapitalrückzahlung, Rückfluss-Rabatt, eine negative logarithmische Kante in einem Währungsarbitrage-Zyklus) ist Dijkstra nicht optimal — es liefert ein stillschweigend falsches Ergebnis. Bellman-Ford ist nötig. Bei negativem Zyklus ist der kürzeste Pfad undefiniert (der Zyklus kann unbegrenzt durchlaufen werden, jede Schleife reduziert die Summe). In vielen Finanzarbitrage- / Netzwerkfluss- / Rückfluss-Szenarien geschieht dieser Fehler stillschweigend. Bellman-Ford erkennt einen negativen Zyklus, wenn in Iteration V weiterhin eine Aktualisierung auftritt.
Zweiter übersehener Punkt: Wahl der algorithmischen Komplexität. Der Praktiker sagt “Dijkstra funktioniert überall”; aber auf einem landesweiten Straßennetz (10M+ Kanten) dauert eine einzige klassische Dijkstra-Anfrage Sekunden — nicht akzeptabel für Echtzeitnavigation. Moderne vorverarbeitungsbasierte Ansätze (Contraction Hierarchies — Geisberger et al. 2008, Transit Node Routing, Hub Labels) liefern Sub-Millisekunden-Anfragezeit; Vorverarbeitung ist einmalig (Stunden-Tage), jede nachfolgende Anfrage schnell. Dritter übersehener Punkt: Statische-Graph-Annahme. Verkehr ändert sich in Echtzeit; Shortest Path auf statischem Graph weist “Optimum für 14:00” aus, bricht aber zur Rush Hour um 17:00 zusammen. Zeitabhängiger Kürzester-Pfad (Kantengewicht als Zeitfunktion) oder Rolling-Horizon-Recompute ist unverzichtbar.
Schritt-für-Schritt-Pfad für KMU
Phase 1 — Erst messen, dann planen. Mindestens 6 Monate Anfrage-/Routendaten: tägliches Anfragevolumen (wieviele A-B-Anfragen, wieviele All-Pairs-Anfragen), durchschnittliche Anfragezeit, Verkehrsprognose-Drift (geplante vs. tatsächliche Zeit), Routenänderungsrate (Recompute-Auslöser). Straßennetzwerk-Inventar: Quelle (Kartendienst, OpenStreetMap, eigener Bestand), Qualität (Abdeckung, Aktualität, Kantengewichtstyp — Distanz / Zeit / Kosten), Straßentyp (Autobahn, geteilt, Stadt, Schwerverkehr-Zugang). Verkehrsdatenquelle: keine / im Kartendienstpaket / separater Anbieter / eigene GPS-Flottendaten.
Phase 2 — Die Algorithmusmatrix erstellen. Anfrageprofil: mehrheitlich Single-Point-to-Point, Single-Source-All-Destinations, All-Pairs-Analyse? Negativ-Kanten- / Negativ-Zyklus-Szenarien (Finanzarbitrage, Rückfluss)? Graphgröße: 1K, 10K, 100K, 1M, 10M+ Knoten? Anfragezeit-Anforderung: Sub-Millisekunde (Echtzeit-Navigation), Sekunden (Planung), Minuten (strategische Analyse)? Algorithmus aus dieser Matrix wählen: Dijkstra (klein-mittel, nicht-negativ), Bellman-Ford (negative Kanten), Floyd-Warshall (klein All-Pairs), A* (geographisches Straßennetz), Contraction Hierarchies (landesweit Echtzeit).
Phase 3 — Pilot. 8-12 Wochen. Eine Teilmenge der Operation (z.B. die geschäftigste Region oder das anfrageintensivste Kundensegment) auf der neuen Kürzester-Pfad-Engine; die Entscheidung bleibt beim Planer / Fahrer, die Engine empfiehlt. Erfolgskriterium vorher schriftlich: in der Pilotregion Treibstoff -10% Minimum, Lieferzeit -15% Minimum, Anfragezeit erfüllt Echtzeitanforderung.
Phase 4 — Rollout. 6-12 Monate für volle Operation + Verkehrsdienstintegration + Rolling-Horizon-Recompute. Quartalsweises Operations-Komitee: Kürzester-Pfad-Anfragevolumen, durchschnittliche Anfragezeit, Verkehrsprognose-Drift, Routenänderungsrate, Netzwerk-Engpass-Bericht (All-Pairs-Analyse).
Risiken — was schiefgehen kann
Verkehrsprognose-Drift (Statischer-Graph-Risiko). Shortest Path auf statischem Graph spiegelt reale Verkehrsbedingungen nicht wider; das kritischste Risiko. Zu Stoßzeiten dauert die als “optimal” berechnete Route real länger. Lösung: zeitabhängiger Kürzester-Pfad (Kantengewicht als Zeitfunktion) + Verkehrsdienst (5-15-Min-Aktualisierung) + Rolling-Horizon-Recompute (alle 15-30 Minuten oder eventgetriggert — Unfall, Sperrung).
Echtzeit-Update-Verzögerung. Wenn Straßensperrungs-, Unfall- oder Verkehrsevent-Daten spät an die Kürzester-Pfad-Engine gelangen, empfiehlt die Engine eine unwissentlich gesperrte Straße — der Fahrer fährt dorthin, kehrt um, doppelte Kosten. Lösung: eventgesteuerte Neuberechnung, Echtzeit-Verkehrsevent-Benachrichtigung in der Fahrer-Mobil-App, Alternative-Routen-Vorschlag.
Straßensperrung / Verbot unbekannt. Wenn (statische) Straßennetzwerkdaten nicht periodisch aktualisiert werden, sind Neubau, saisonale Sperrungen und Schwerverkehrsverbote unbekannt; die Engine produziert nicht ausführbare Routen. Lösung: 3-6-Monats-Straßennetzwerk-Aktualisierungszyklus, Fahrer-Feldfeedback (eine “Straße gesperrt”-Meldung in der Mobil-App), LKW-spezifische Straßennetz-Schicht für Schwerverkehr.
Single-Supplier-Routingsoftware / Kartendienst-Lock-in. Ohne Vertragsklausel für “jährlicher Standard-Format-Export (GeoJSON, GraphML, CSV) von Straßennetzwerkdaten, Verkehrskalibrierungsdaten, Anfragehistorie und Routenarchiv” bedeutet ein Ausstieg den Verlust jahrelang gesammelter operativer Daten und Kalibrierungsgedächtnis. Der Vertrag muss explizit Straßennetzwerk-Datenhoheit, Verkehrskalibrierungs-Parameter-Export und standardformatigen Output für die Anfrage-API abdecken.
Lösungsmethode — technische Sicht
| Ansatz | Typische Größe | Lösezeit | Negative Kanten? |
|---|---|---|---|
| Dijkstra naïv (O(V²)) | Klein, V ≤ 1.000 | Millisekunden | Nein |
| Dijkstra Binary-Heap (O((V+E)logV)) | Mittel, V ≤ 100K | ms-Sekunden | Nein |
| Dijkstra Fibonacci-Heap (O(E + VlogV)) | Mittel-groß, V ≤ 1M | Sekunden | Nein |
| Bellman-Ford (O(VE)) | Klein-mittel, negativ-kanten | Sekunden-Minuten | Ja, erkennt negativen Zyklus |
| Floyd-Warshall (O(V³)) | Klein All-Pairs, V ≤ 1.000 | Sekunden-Minuten | Ja (kein Zyklus) |
| Johnson (O(V² logV + VE)) | Mittel All-Pairs, dünn | Minuten | Ja |
| A* (heuristik-geführt) | Geographisches Straßennetz, Punkt-zu-Punkt | ms-Sekunden | Nein |
| Bidirektionales Dijkstra/A* | Punkt-zu-Punkt, großer Graph | ms-Sekunden | Nein |
| Contraction Hierarchies | Landesweites Straßennetz | Sub-Millisekunde (Vorverarbeitung Stunden) | Nein |
| Zeitabhängiges Dijkstra | Verkehrsbewusstes Straßennetz | ms-Sekunden | Nein |
Zielfunktionswahl:
- Ziel 1 — Minimale Gesamtzeit: Geschwindigkeitsorientiert; typisch für Navigation, Rettungsdienste, Paketlieferung.
- Ziel 2 — Minimale Gesamtdistanz: Treibstoff + Fahrzeugverschleiß orientiert; typisch für Fernverkehr.
- Ziel 3 — Minimale Gesamtkosten: Gewichtete Summe aus Treibstoff + Maut + Fahrstunden.
- Ziel 4 — Multi-Kriterien (Pareto-Optimum): Kompromiss aus Zeit + Kosten + Treibstoff; Entscheider wählt von der Pareto-Front.
Multi-Objective: gewichtete Summe (am häufigsten) oder hierarchisch (zuerst Zeit, dann Kosten, dann Treibstoff) oder Pareto-optimale Pfade (für fortgeschrittene Entscheidungsunterstützung).
Kürzester-Pfad-Varianten — feldabhängig:
- Klassisches Dijkstra (1959): Nicht-negative Kanten, Single-Source, foundational.
- Bellman-Ford (1958): Negativ-kanten-fähig, Erkennung negativer Zyklen, Distance-Vector-Routing.
- Floyd-Warshall (1962): All-Pairs, kleiner Graph, dynamische Programmierung.
- A (Hart-Nilsson-Raphael 1968):* Heuristik-geführter Punkt-zu-Punkt, geographische Straßennetze.
- Contraction Hierarchies: Landesweites Straßennetz, vorverarbeitungsbasiert, Echtzeit.
- Zeitabhängiger Kürzester-Pfad: Verkehrsbewusst, Kantengewicht als Zeitfunktion.
- Stochastischer Kürzester-Pfad (Polychronopoulos-Tsitsiklis 1996): Unsichere Kantengewichte, risikoangepasst.
- Ressourcenbeschränkter Kürzester-Pfad (RCSP): Zusätzliche Ressourcenbedingungen (Treibstoff, Zeitfenster); erscheint als Pricing-Subproblem in Column-Generation-VRP.
Akademische Quellen
In der Frontmatter der Seite unter sources aufgelistet.
Quellen
- Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271. Grundlegendes zweiseitiges Papier; eines der meistzitierten Papiere der Informatik.
- Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90. Grundlegende Referenz für Bellman-Ford auf Graphen mit negativen Kanten.
- Floyd, R. W. (1962). Algorithm 97: Shortest path. Communications of the ACM, 5(6), 345. Kanonische einseitige Quelle des All-Pairs-Floyd-Warshall.
- Ahuja, R. K., Magnanti, T. L. und Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall. Kanonisches Lehrbuch der Netzwerkflüsse und Kürzester-Pfad-Bereich.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L. und Stein, C. (2009). Introduction to Algorithms (3. Aufl.). MIT Press. Lehrreferenz für Dijkstra / Bellman-Ford / Floyd-Warshall.
- Geisberger, R., Sanders, P., Schultes, D. und Delling, D. (2008). Contraction hierarchies: Faster and simpler hierarchical routing in road networks. Experimental Algorithms (WEA 2008), LNCS 5038, 319-333. Moderner vorverarbeitungsbasierter Algorithmus für landesweite Straßennetzwerke.
- Hart, P. E., Nilsson, N. J. und Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. Gründungspapier des A*-Algorithmus.
- YÖK Thesis Center — Stichwort: ’en kısa yol’ oder ‘Dijkstra’ oder ‘graf algoritması’ — 30+ Dissertationen aus TR-Akademia. tez.yok.gov.tr
Glossar
- Shortest Path Problem
- Grundlegendes Graphen-OR-Problem, den Pfad minimaler Gesamtgewichtssumme zwischen zwei Knoten auf einem gewichteten Graphen zu finden (Single-Source-Single-Destination, Single-Source-All-Destinations oder All-Pairs); polynomiale Algorithmen Dijkstra (1959), Bellman-Ford (1958), Floyd-Warshall (1962).
- Dijkstra Algorithm
- Polynomialer Algorithmus von Edsger Dijkstra (1959) für Single-Source-Shortest-Path auf Graphen mit nicht-negativen Kantengewichten; gierig — extrahiere den unbesuchten Knoten mit kleinster vorläufiger Distanz aus einer Prioritätswarteschlange und relaxiere seine Nachbarn; O((V+E) log V) mit Binary-Heap.
- MIP
- Optimierungsmodell, bei dem ein Teil der Entscheidungsvariablen ganzzahlig sein muss (z. B. Anzahl LKW, Anzahl Schichten).
- VRP
- Die Entscheidung, welche Fahrzeuge — ausgehend von einem oder mehreren Depots — welche Kunden in welcher Reihenfolge anfahren.
Ähnliche Probleme
Ein Fahrzeug, viele Stopps — in welcher Reihenfolge fahre ich alle an, damit die Gesamtstrecke minimal ist?
Sie betreiben einen Servicetechniker mit 8-15 Kundenbesuchen pro Tag (Klima, Aufzug, Weißware), einen Einzelfahrzeug-Lieferantenbesuch eines Vertrieblers oder eine PCB-Bohrmaschine, die 500-5.000 Bohrungen in Reihenfolge bringt. Alle stehen vor derselben Kernfrage: gegeben N Punkte, in welcher Reihenfolge fährt das einzige Fahrzeug oder der Kopf jeden Punkt an und kehrt zum Start zurück. Bei falscher Reihenfolge verbrennt das Servicefahrzeug 80-200 TRY/Tag extra an Kraftstoff und Fahrerstunden, die PCB-Linie braucht 15-30% länger pro Bauteil und der letzte Kunde verpasst sein Lieferfenster. Bei 50 Stopps liegt die handgemachte Reihenfolge 20-40% über dem wahren Minimum; mit wachsender Stoppzahl summiert sich die Lücke der Bauchgefühl-Reihenfolge.
Mehrere Fahrzeuge, viele Kunden — welches Fahrzeug in welcher Reihenfolge, Kapazität nicht überschritten, Gesamtstrecke minimal?
Ein Distributor oder Lieferant, der täglich von einem Depot aus 10-100 Kunden beliefert (Lebensmittel, Getränke, Wasser, B2B-Ersatzteile); feste Fahrzeugkapazität (2-5 t, 30 m³), bekannte Bestellmengen je Kunde, flexible Lieferzeit. Jeden Morgen drei Fragen: wie viele Fahrzeuge fahren heute los, welches Fahrzeug bedient welche Kunden, in welcher Reihenfolge — Kapazität nicht überschritten, Gesamtstrecke minimiert. Ein Disponent schafft 15-25 Kunden im Kopf; darüber sinkt die Routenqualität, Kunden derselben Region landen auf zwei Fahrzeugen, 1-2 Fahrzeuge pro Tag fahren unnötig zusätzlich. 10-25 % der Gesamtstrecke und 1-2 Fahrzeuge pro Tag hängen von der Planqualität ab; Kraftstoff + Fahrer machen 30-50 % der Betriebskosten aus.
Mehrere Werke, mehrere Kunden — Wie viel liefert jedes Werk an jeden Kunden, damit die Gesamtfracht minimal wird?
Für Lebensmittel-, Verpackungs- oder Textil-KMU, die wöchentlich aus 3-8 Werken oder Regionallagern an 20-100 Kunden liefern. Die wöchentliche Entscheidung lautet: welches Werk schickt wie viel an welchen Kunden, bei festen Werkkapazitäten, festgelegten Kundenbedarfen und je Werk-Kunde-Paar unterschiedlichen Stückkosten (Entfernung + Fahrzeugtyp + Vertrag). Ziel ist die niedrigste Gesamtfrachtrechnung über das Netz. Die Faustregel 'nächstgelegenes Werk' oder 'das machen wir schon immer so' kostet gegenüber einer systematischen Zuweisung typischerweise 10-20% zusätzlichen Diesel- und Fahrzeugaufwand.