Vorlesung 11 Flashcards
1
Q
TSP: Struktur (3+1)
A
Traveling Salesman Problem:
- Handelsreisender muss j Kunden besuchen
- jeder Kunde wird genau einmal besucht
- Start und Zielpunkt sind Depot
- -> minimiere zurückgelegte Distanz
2
Q
TSP: Optimierungsmodell - Zielfunktion
A
min sum(i–>J) sum(j–>J) eij * xij
3
Q
TSP: Nearest Neighbour
A
wähle Ort, der noch nicht besucht ist, mit dem kleinsten Abstand
(Kreuzungen möglich –> nicht optimal)
4
Q
TSP: Cheapest Insertion
A
Plane unter allen noch nicht eingeplanten Standorten denjenigen, an der derjenigen Stelle ein, der die Tour am wenigsten verlängert
5
Q
Bin Packing Problem: First Fit Decrease
A
- Güter absteigend der Größe nach sortieren
2. nimm erste Gut das in Behälter passt und leg ein, dann nimm nächstes bis nichts mehr passt
6
Q
Tourenplanung 3 Schritte (und Hinweise)
A
- Erzeuge Ausgangslösung
- Berechne Kostenänderungen durch zusammenlegen
- ## Ende wenn keine weitere Einsparung mehr möglichStelle Tabelle mit Kostenänderungne in deren Reihenfolge auf, dann betrachte machbare Lösungen (bedenke Fahrzeugkapazität)
7
Q
TSP: Nebenbedingung - Kunde wird angefahren
A
…
8
Q
TSP: Nebenbedingung - Position des Kunden auf Rundreise
A
…
