Vorlesung 11 Flashcards
Was beschreibt das Traveling Salesman Problem (TSP)
- Ein Handelsreisender muss 𝐽Kunden besuchen
- Die Standorte der Kunden sind bekannt
- Die Entfernungen zwischen den Standorten sind bekannt
- Jeder Kunde wird genau einmal besucht
- Start und Zielpunkt sind identisch
Ziel: Minimiere die Anzahl gefahrener Kilomete
sehr aufwendige Möglichkeit der Lösung vom TSP
alle möglichen Lösungen vergleichen
- sehr aufwenig - sehr viele Möglichekieten
TSP
NB um kurzzyklen zu vermeiden
yi -yj + 1 <= J * (1- xij)
für alle i,j = 1,2,… J
je (2) Pro & Cons
Optimales Verfahren vs. Heuristik
Optimales Verfahren
+ genaue, sichere beste Lösung
+ hohe realibilität
- sehr aufwenidig
- geringer Mehrwert bei sehr vielen Optionen
Heuristik
+ Schnell, ressourcen sparend
+ ähnlich zu optimaler Lösung
- nicht optimal
- verzerrung
Wann sollte man optimale Verfahren,
wann heuristiken verwenden
Optimale Verfahren
keine Probleme
Heuristiken
sehr große Probleme
Erkläre Nearest Neighbour
Pro / Contra (1)
Wähle den Ort mit dem kleinsten Abstand, der noch nicht besucht wurde.
+ sehr einfach
- stark vereinfachend
Erkläre Cheapest insertion Heuristik
Knoten wählen, dass Kosten so gering wie möglich erhöht werden.
1 Iteration: günsigster Weg vom Lager hin & zurück
2 Iteration: alle Knoten durch probieren: Vor oder Nach letzten Knoten einfügen? Günstigste nehmen
Weitere Optimierung vom TSP
durch Paarweise vertauschung
Bin Packing
First Fit erklären
keine Sortierung,
1 Behälter solange auffüllen bis voll
2 Behälter etc
Bin Packing
First Fit Descreasing
Sortierung
erst groß dann klein
und dann so wie bei First Fit
Savings Algorithmus
Idee erklären und Zielfunktion
von Pendeltouren zu verkettungen
Differenzen durch kombination errechen
ZF = sum eoi + sum ei0 - detaij
