03 Distribution Flashcards
Elemente eines Branch and Bound
Lösungsbaum Knoten Branching Bounds (Schranken) Ausloten eines Knotens
Aufgabe des “Branching”
Bestimmt, welche Lösungsbestandteile fixiert und in welcher Reihenfolge Teilprobleme betrachtet werden
Strategien des Branching
Breitensuche: Es werden zunächst alle Knoten einer Ebene verzweigt
Tiefensuche: Es wird auf jeder Ebene immer genau ein Knoten ausgewählt und vollständig verzweigt. bevor die Knoten der nächsten Ebene verzweigt werden
Was ist der Upper Bound
Globale obere Schranke für die optimale Lösung.
Bei Minimierungsproblemen die “schlechteste” Lösung.
Initialer Upper Bound kann zB durch heuristische Verfahren geliefert werden.
Was ist der Lower Bound
Lokale untere Schranke für die optimale Lösung eines (Teil-) Problems.
Bei Minimierungsproblemen die “lokale bestmögliche” Lösung.
Relaxation
Vergrößert die Menge der zulässigen Lösungen, ohne die Zielfunktionswerte der Lösungen von X zu verschlechtern. Bspw. durch Weglassen von NB oder LP-Relaxationen
Def.: Ausloten von Knoten
Einen Knoten aus der Betrachtung ausschließen
Voraussetzungen zum Ausloten von Knoten
- Lower Bound eines Knotens größer als der globale Upper Bound ist (Minimierungsproblem)
- Für ein Teilproblem kann keine gültige Lösung gefunden werden
Def.: Auslieferungs- und Tourenplanung
Optimierung des Fahrzeugeinsatzes von Fahrzeugflotten durch Zuordnung von Fahrzeugen zu Kunden und Lieferzeitpunkten
Systematisierung von Tourenplanungsproblemen (Matrix Fahrzeugkapazität und Anzahl Fahrzeuge)
Fahrzeugkapazität ist NICHT KNAPP:
Ein Fahrzeug: Travelling-Salesman Problem
Mehrere Fgz: Unkapazitiertes Vehicle Routing Problem
Fahrzeugkapazität ist KNAPP
Ein Fahrzeug: –
Mehrere Fzg: Vehicle Routing Problem
Verschiedene Metriken der Entfernungsmessung
> Euklidische Distanz
> Manhattan Distanz
Def. Standort
Geographischer Ort, an dem ein Betrieb Güter erstell
Def. Standortplanung
Zielgerichtete Bewertung und Auswahl von Standorten
Def. Standortfaktor
Standortspezifische Einflussgröße, die den Erfolg des Unternehmens determiniert
Beispiel Quantitative Standortfaktoren
Transportkosten Errichtungskosten Personalkosten Standortabhängige Finanzierungskosten Grund- und Gewerbesteuer
