Algorithmen Logistik Zusammenfassung keijsjsjsj jsjsns PDF

Preview

Summary

Ndjjs kdkkdjs djcjnv djnnu jnd sks s ocm coks sl mc cpxm cl md sl...

Description

Algorithmen f¨ ur Logistik Henry Haustein

Toplogische Sortierung https://de.wikipedia.org/wiki/Topologische_Sortierung Ziel: Graphen topologisch sortieren, dass heißt f¨ ur jeden Pfeil von Knoten i nach Knoten j muss gelten: i < j. Idee hinter dem Algorithmus: Start bei einer Quelle, diese bekommt die kleinste Zahl. Dann entfernt man diese Quelle und mit ihr auch alle Pfeile zu nachfolgenden Knoten. In dem verbleibenden Knoten sucht man wieder eine Quelle und gibt ihr die n¨achstgr¨oßere Zahl usw. Wenn der Graph einen Zyklus enth¨ alt, wird man irgendwann keine Quelle mehr finden, hat aber nicht alle Knoten neu nummeriert. In diesem Fall ist der Graph nicht topologisch sortierbar. Kann man alle Knoten neu nummerieren, so ist der Graph topologisch sortierbar. Beispiel: Gegeben sei der Graph 1

3

2

4

5

Iteration k

Quelle Qk

Kanten, die Quelle enthalten E~Qk

neue Nummer

restlicher Graph nach Entfernung der Quelle ~ k+1 Vk+1 , E

0

1

{(1, 2), (1, 3), (1, 4)}

1

V1 = {2, 3, 4, 5}, ~ 1 = {(3, 4), (4, 2), (4, 5)} E

1

3

{(3, 4)}

2

2

4

{(4, 2), (4, 5)}

3

3

2

∅

4

4

5

∅

5

V2 = {2, 4, 5}, ~ 2 = {(4, 2), (4, 5)} E ~3 = ∅ V3 = {2, 5}, E ~4 = ∅ V4 = {5}, E ~5 = ∅ V5 = ∅, E

Wissenswertes: In fr¨ uhen Zeiten der Programmierung war es notwendig, voneinander abh¨angige Quelltextdateien in der richtigen Reihenfolge zu kompilieren. Daf¨ur wurde unter UNIX-artigen Systemen wie Linux und Mac das Kommandozeilenprogramm tsort entwickelt, das eine topologische Sortierung vornimmt. Die Abh¨angigkeiten werden in der Form von hLeerzeicheni nach eingegeben. F¨ ur das obige Beispiel s¨ahe die Eingabe wie folgt aus:

1

1 2 3 4 5 6 7 8

ts or t 1 3 > 1 4 > 1 2 > 3 4 > 4 2 > 4 5 > Ende

und liefert als Ergebnis 1,3,4,5,2, dass heißt in dieser Reihenfolge sollten die Knoten nummeriert werden.

Kruskal-Algorithmus https://de.wikipedia.org/wiki/Algorithmus_von_Kruskal Ziel: Finden eines Minimalger¨ ustes Idee hinter dem Algorithmus: Joseph Kruskal beschreibt seinen Algorithmus wie folgt: F¨ uhre den folgenden Schritt so oft wie m¨oglich aus: W¨ahle unter den noch nicht ausgew¨ahlten Kanten von G (dem Graphen) die k¨ urzeste Kante, die mit den schon gew¨ahlten Kanten keinen Kreis bildet. Das heißt man startet mit einem leeren Ger¨ ust ohne Kanten und f¨ ugt aus dem Graphen die Kanten mit den kleinsten Gewichten hinzu, sodass kein Zyklus im Graph entsteht. Der Algorithmus stoppt genau dann, wenn man n − 1 Kanten in seinem Ger¨ust hat. Beispiel: Gegeben sei der Graph 1 2

6

6 4

7

2

5

4

6

5

3

3 2

1 4

2

Iteration k

Kante mit kleinstem Kantengewicht ek

Gewicht dieser Kante c(ek )

Kanten im Ger¨ ust E ∗

Anzahl der Kanten im Ger¨ ust |E ∗ |

1

[3, 4]

1

{[3, 4]}

1

2

[4, 5]

2

{[3, 4], [4, 5]}

2

3

[1, 6]

2

{[3, 4], [4, 5], [1, 6]}

3

4

[3, 5]

2

5

[2, 3]

4

{[3, 4], [4, 5], [1, 6], [2, 3]}

4

6

[4, 6]

4

{[3, 4], [4, 5], [1, 6], [2, 3], [4, 6]}

5

Ger¨ ust w¨ urde Zyklus enthalten

Σ 13

Prim-Algorithmus https://de.wikipedia.org/wiki/Algorithmus_von_Prim Ziel: Finden eines Minimalger¨ ustes Idee hinter dem Algorithmus: selbe Idee wie beim Algorithmus von Kruskal, nur knoten- statt kantenorientiert. Man startet mit einem beliebigen Knoten im Ger¨ ust und f¨ ugt nun solange Kanten mit kleinem Kantengewicht zum Ger¨ ust hinzu, bis man alle Knoten im Ger¨ ust hat. Logischerweise f¨ ugt man eine Kante nur dann hinzu, wenn sie einen neuen Knoten ins Ger¨ ust bringt, sonst h¨atte man Zyklen im Ger¨ ust. Beispiel: Gegeben sei der Graph 1 2

6

6 4

7

2

5

4

6

5

3

3 2

1 4

Wir wollen mit Knoten 3 starten.

3

Knoten W im Ger¨ ust vorher

verf¨ ugbare Knoten V vorher

Kante mit kleinstem Gewicht, die W erweitern w¨ urde

Knoten W im Ger¨ ust nachher

verf¨ ugbare Knoten V nachher

Kanten im Ger¨ ust E ∗

{3}

{1, 2, 4, 5, 6}

[3, 4]

{3, 4}

{1, 2, 5, 6}

{[3, 4]}

{3, 4}

{1, 2, 5, 6}

[4, 5]

{3, 4, 5}

{1, 2, 6}

{[3, 4], [4, 5]}

{3, 4, 5}

{1, 2, 6}

[4, 6]

{3, 4, 5, 6}

{1, 2}

{[3, 4], [4, 5], [4, 6]}

{3, 4, 5, 6}

{1, 2}

[6, 1]

{1, 3, 4, 5, 6}

{2}

{[3, 4], [4, 5], [4, 6], [6, 1]}

{1, 3, 4, 5, 6}

{2}

[3, 2]

{1, 2, 3, 4, 5, 6}

∅

{[3, 4], [4, 5], [4, 6], [6, 1], [3, 2]}

Dijkstra-Algorithmus https://de.wikipedia.org/wiki/Dijkstra-Algorithmus Ziel: Finden des k¨ urzesten Weges von einem Startknoten zu allen anderen Knoten Idee hinter dem Algorithmus: Der Algorithmus hat eine Menge an Knoten M , zu denen er bereits den k¨ urzesten Weg kennt. Der n¨achste Knoten, der zu dieser Menge hinzugef¨ ugt wird, ist der, der den k¨ urzesten Weg zum Startknoten hat. Detailliertere Beschreibung: Wir starten beim Startknoten und schauen uns dessen Nachfolger an und deren Kantengewicht an. Von diesen Nachfolgern f¨ ugen wir den Knoten zu M hinzu, dessen Kantengewicht am kleinsten ist. Die Menge M enth¨ alt jetzt 2 Knoten. Nun schauen wir uns alle Nachfolger (die noch nicht im M sind) von den 2 Knoten in M an und berechnen die Distanz zum Startknoten. Von diesen ganzen Nachfolgern f¨ ugen wir den zu M hinzu, dessen Weg zum Startknoten am k¨ urzesten ist usw. Beispiel: Gegeben sei der Graph 5 1

5

2 3

4

2

4

3

4

1

5

Wir suchen die k¨ urzeste Verbindung von Knoten 1 zu allen anderen Knoten. d ij gibt den direkten Weg (k) von i nach j; dij ist der Weg von i u ¨ber k nach j . Iteration k

Menge an bekannten Knoten Mk

”unbekannte” Nachfolger aller Knoten in M

Distanz zu allen diesen Nachfolgern vom Startknoten

1

{1}

N (1) = {2, 3}

d 12 = 5, d 13 = 4

2

{1, 3}

N (1) = {2}, N (3) = {2, 5}

d 12 = 5, d12 = 7, d 15 = 5

3

{1, 2, 3}

N (2) = {4, 5}, N (3) = 5

d14 = 10, d 15 = 9, d15 = 5

4

{1, 2, 3, 5}

N (2) = {4}

(2) d14 = 10

5

{1, 2, 3, 4, 5}

∅

4

(3)

(2)

(2)

(3)

Die k¨ urzeste Distanz zu allen Knoten von Knoten 1 sind die unterstrichenden Werte in der Tabelle, also d 1 = (0, 5, 4, 10, 5).

Verfahren von Bellmann https://de.wikipedia.org/wiki/Bellman-Ford-Algorithmus Ziel: Finden des k¨ urzesten Weges von einem Startknoten zu allen anderen Knoten, wenn der Graph zyklenfrei ist. Idee hinter dem Algorithmus: Wenn ein Graph zyklenfrei ist, so kann er topologisch sortiert werden. Wir arbeiten die Knoten in aufsteigender Reihenfolge ab und schauen uns f¨ur jeden Knoten die Vorg¨ anger an. Bei einer topologischen Sortierung haben wir uns bereits alle Vorg¨anger angeschaut und kennen den k¨ urzesten Weg zu jedem dieser Vorg¨anger. Damit k¨onnen wir nun auch den k¨ urzesten Weg zum aktuell betrachteten Knoten ermitteln. Beispiel: Gegeben sei der Graph 2 1

3

2

6

3

1

4

5

5 Wir suchen die k¨ urzeste Verbindung von allen Knoten zu Knoten 1 . Distanz der Vorg¨ anger zum Startknoten

Distanz von Knoten j zum Startknoten

Knoten j

Vorg¨ anger des Knotens V (j)

1

∅

2

{1}

d 11 = 0

d 12 = 3

3

{2}

d 12 = 3

d13 = 9

4

{1, 3}

d 11 = 0, d13 = 9

5

d 11 = 0

(2)

(2) d 13

{3}

=9

(2)

(2,3)

d 14 = 2, d14 (2,3) d15

= 10

= 14

Tipelalgorithmus https://de.wikipedia.org/wiki/Algorithmus_von_Floyd_und_Warshall Ziel: Finden des k¨ urzesten Weges von jedem Knoten zu jedem Knoten. Idee hinter dem Algorithmus: Iteration u ¨ber alle Knoten im Graphen, die sowohl Vorg¨anger als auch Nachfolger haben (also weder Quellen noch Senken sind). Es wird zwischen jedem Vorg¨anger und jedem Nachfolger versucht einen Weg zu finden. Wenn es schon einen Weg zwischen einem Vorg¨anger und einem Nachfolger gibt, u ¨berpr¨ uft man, ob dieser Weg durch einen Umweg u ¨ber den aktuell betrachteten Knoten k¨ urzer ist. Wenn es diesen Weg noch nicht gibt, kann man ihn neu hinzuf¨ ugen. Hier wird diese Idee an einem Beispiel in 16 Minuten erkl¨art: https://www.youtube.com/watch?v=8qi06lDiU6I. Beispiel: Gegeben sei der Graph

5

4

1

4 2

5

1

3 2

3 2

Umwege u ¨ber Quelle 1 und Senke 4 k¨onnen entfallen. betrachteter Knoten

Vorg¨ anger

Nachfolger

2

{1, 3}

{3}

Distanz zwischen Vorund Nachg¨ anger mit/ohne Umweg (2) d 13 = 2 vs. d 13 = 8 (2)

d 33 = 0 vs. d 33 = 5 (3) d 12 = 5 vs. d 12 = 4 (3)

{1, 2}

3

d 14 = 4 vs. d 14 = 3

{2, 4}

(3)

d 22 = 0 vs. d 22 = 5 (3)

d 24 = ∞ vs. d24 = 4 An den Stellen, wo der Umweg besser ist, muss man die Entfernungsmatrix D des Ausgangsgraphen updaten. Selbiges gilt auch f¨ ur die Vorg¨angermatrix W . So ergibt sich dann D

1

2

3

4

W

1

2

3

4

1

0

4

2

3

1

1

3

1

3

2

∞

0

3

4

2

∞

2

2

3

3

∞

2

0

1

3

∞

3

3

3

4

∞

∞

∞

0

4

∞

∞

∞

4

Vogel’sche Approximationsmethode https://de.wikipedia.org/wiki/Vogelsche_Approximationsmethode Ziel: heuristische L¨ osung eines Transportproblems Idee hinter dem Algorithmus: F¨ ur jede Produktionsst¨atte und jeden Abnehmer wird ein Einsparpotential als Differenz der zwei niedrigsten Transportkosten bestimmt. Die Produktionsst¨atte/der Abnehmer mit dem h¨ochsten Einsparpotential wird angeschaut und dessen produzierte Waren/angeforderte Waren am billigsten transportiert. Anschließend werden die Bedarfe und produzierten Waren der anderen Abnehmer/Produktionsst¨atten neu berechnet und der Algorithmus beginnt von vorne, nur dass jetzt bei dem Einsparpotential die gerade behandelte Produktionsst¨atte/Abnehmer nicht mehr betrachtet wird. Beispiel: Gegeben seiden zwei Produktionsst¨atten mit den Kapazit¨aten 11 und 13, sowie 3 Abnehmer mit den Bedarfen 6, 4 und 14.

6

A1

A2

A3

Kapazit¨at

Strafkosten

P1

60

40

30

11

10

P2

20

35

55

13

15

Bedarf

6

4

14

Strafkosten

40

5

25

A1

A2

A3

Kapazit¨at

Strafkosten

P1

60

40

30

11

10

P2

20 6

35

55

7

20

Bedarf

0

4

14

5

25

Strafkosten A1

A2

A3

Kapazit¨at

P1

60

40

30 11

0

P2

20 6

35

55

7

Bedarf

0

4

3

A1

A2

A3

Kapazit¨at

P1

60

40

30 11

0

P2

20 6

35 4

55

3

Bedarf

0

0

3

A1

A2

A3

Kapazit¨at

P1

60

40

30 11

0

P2

20 6

35 4

55 3

0

Bedarf

0

0

0

Verfahren des besten Nachfolgers f¨ ur Traveling Salesman Problems https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden und insbesondere f¨ ur den Algorithmus https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden#Er%C3%B6ffnungsverfahren Ziel: Heuristik f¨ ur das Finden eines k¨ urzesten Weges, alle Knoten eines Graphen zu besuchen und wieder zum Ausgangsknoten zur¨ uckzukommen. Idee hinter dem Algorithmus: Einfach zum n¨achsten Nachfolger laufen.

Sweep-Algorithmus Original-Paper: https://www.jstor.org/stable/169591, kurze Erkl¨arung: https://aktienundsweep. wordpress.com/2012/02/17/der-sweep-algorithmus-in-der-logistik/ Ziel: Tourenplanung

7

Idee hinter dem Algorithmus: Die Kunden liegen um das Depot verstreut und m¨ ussen abgefahren werden. Dabei sortiert man die Kunden nach Polarwinkel, damit man in einer Tour m¨oglichst nur Kunden hat, die ungef¨ahr in der selben Richtung vom Depot aus liegen. Man f¨ahrt solange Kunden an, bis die Transportkapazit¨at nicht mehr f¨ ur den n¨achsten Kunden ausreicht. Die n¨achste Tour startet dann bei genau diesem Kunden. Beispiel: Gegeben sei die Folgende Karte mit Depot in (0,0) und den Standorten der Kunden. 30 ME 3

50 ME 4 60 ME

2

5

1

100 ME 6

30 ME

80 ME

7

8 70 ME

9 60 ME

Tourenplan mit einer maximalen Transportkapazit¨at von 150 ME. 1. Tour: 0 - 1 - 2 - 0 2. Tour: 0 - 3 - 4 - 5 - 0 3. Tour: 0 - 6 - 7 - 0 4. Tour: 0 - 8 - 9 - 0

8

70 ME...