Buffl

4 - Transportsysteme

JM
by Jan M.

Dijkstra-Algorithmus

  • Kreise stellen bestimmte Stationen im Transportnetz dar (z.B. Städte in einem Land)

  • Pfeile (Kanten) stellen die Verkehrsverbindung dar

  • die Zahlen an den Kanten stellen die Entfernung oder die Kosten bei bei dem entsprechendem Verkehrsweg anfallen dar

  • man wählt immer den Pfad, der in der aktuellen Situation den größten Fortschritt verspricht

  • Ausgehend vom Ausgangsknoten, in diesem Fall Knoten A, werden in einem ersten Schritt alle Kanten betrachtet, die zu anderen Knoten führen, hier zu den Knoten B, E, D und F.

  • Die jeweiligen Kosten (Kantengewichte) werden in die erste Zeile der Tabelle eingetragen .

  • Der mit den geringsten Kosten erreichbare Knoten ist Knoten E. Daher kann dieser Knoten auch schon fixiert werden.

    • In der Tabelle wird daher auch schon einmal die ganze Spalte des Knotens E ausgefüllt.

    • Zugleich wird dieser Knoten in geeigneter Weise markiert, in diesem Fall durch Umrandung im Graphen.

    • E wird anschließend in der Besuchsreihenfolge festgehalten

  • Im nächsten Schritt wird wieder geschaut, welcher weg am “günstigsten” ist, dafür muss der neue Weg auf die bisherigen Kosten addiert werden

  • die Werte werden dann in der zweiten Zeile addiert

  • wird sich für ein Pfad zu einem Knoten entschieden, zu dem auch andere Pfade hinführen würden, werden diese gestrichen, wenn sie teurer sind, da sie ein Umweg wären.

  • Die Werte der im aktuellen Schritt nicht untersuchten Knoten werden in die aktuelle Zeile der Tabelle übertragen

  • Wenn Werte doppelt vorkommen, wird sich zufällig entschieden. Computeralgorithmen würden in solchen fällen wahrscheinlich den ersten Wert nehmen, deshalb sollen wir es auch so machen.

  • Wenn von einem Knoten keine weiteren Wege weg führen, man also sozusagen in einer “Sackgasse” ist, werden einfach die Werte der übrigen Spalten in die Zeile übernommen



Lösung:



Vergleiche Savings Algorithmus und Sweep Algorithmus miteinander nach folgenden Kriterien

  • Vorgehensweise

  • Startpunkt

  • Tourenzuordnung

  • Reihenfolgebestimmung

  • Rechenaufwand

  • Lösungsqualität

  • Flexibilität

  • Typische Anwendung


Der Savings-Algorithmus und der Sweep-Algorithmus werden beide zur Lösung von Tourenplanungsproblemen (z. B. beim Lieferverkehr) eingesetzt, insbesondere bei Varianten des Traveling Salesman Problems (TSP) mit Kapazitätsgrenzen (sog. CVRP – Capacitated Vehicle Routing Problem). Sie haben das gleiche Ziel, aber unterschiedliche Herangehensweisen und Stärken.

Kriterium

Savings-Algorithmus

Sweep-Algorithmus

Vorgehensweise

Verbindet Kunden mit dem größten Einsparpotenzial („Savings“) zu Touren.

Dreht eine Linie durch den Kundenraum und bildet Touren in Winkelsegmenten.

Startpunkt

Ausgangspunkt ist meist das Depot, Einsparungen werden aus Entfernungen berechnet.

Beginnt mit einem Kunden in einem bestimmten Winkelbereich.

Tourenzuordnung

Kunden werden paarweise auf Basis der größten Einsparung verbunden.

Kunden werden in Gruppen eingeteilt, basierend auf räumlicher Lage.

Reihenfolgebestimmung

Reihenfolge wird durch Tourenzuordnung bereits festgelegt.

Reihenfolge muss separat innerhalb der Touren bestimmt werden.

Rechenaufwand

Höher – insbesondere bei vielen Kunden, weil alle möglichen Einsparungen geprüft werden.

Gering – einfache geometrische Methode mit weniger Rechenaufwand.

Lösungsqualität

Oft bessere Gesamtlösungen (kürzere Gesamtstrecke), aber auch fehleranfällig bei schlechter Startlösung.

Schneller, aber teils schlechtere Lösungen bei ungünstiger Geometrie.

Flexibilität

Gut bei unregelmäßigen Kundenverteilungen.

Gut bei kreisförmig um das Depot liegenden Kunden.

Typische Anwendung

Wenn Genauigkeit und Optimierung im Vordergrund stehen.

Wenn Geschwindigkeit und einfache Implementierung gefragt sind.

Oft werden beide kombiniert: Sweep zum Erzeugen einer Startlösung, Savings oder andere Verfahren zur Verbesserung.

!!! Kann ich mir als Klausuraufgabe vorstellen, erst Sweep anwenden und dann innerhalb einer Tour den Savings Algorithmus zur Ermittlung der optmialen Route

Author

Jan M.

Information

Last changed