Transport- und Tourenplanung VL11

Question 1

Systematisierung und Probleme

Answer 1

1. Reihenfolge
Ein Fahrzeug mit unendlicher Kapazität
Traveling Salesman Problem
2. Beladung
von mehreren Fahrzeugen
Bin Packing Problem

–> Tourenplanung (Vehicle Routing Problem)

Question 2

Traveling Salesman Problem (TSP)

Answer 2

• 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 Kilometer

Question 3

Traveling Salesman Problem Lösungsverfahren

Answer 3

• kleine Probleme –> Branch and Bound –> Optimale Lösung

- Große Probleme –> Heuristiken –> Gute Lösungen

Question 4

Bin Packing

First Fit Algorithmus

Answer 4

• Die Lösung ist abhängig von der Reihenfolge, in der die Güter angeboten werden

Idee:
• Große Güter sind schwer einzupacken
• Sortieren die Güter beginnend mit dem größten, in absteigender Reihenfolge
• Wenden dann den First Fit Algorithmus an!
–> First Fit Decreasing Algorithmus