8
Optimierung von Distributionsnetzwerken (Subject) / Vorlesung Abschnitt 2 (Lesson)
Vorlesung Abschnitt 2
This lesson was created by Pyro_X.
This lesson is not released for learning.
- Standortprobleme in der Ebene (z.B.Weber) finden Anwendungen wenn... (5 Bedingungen): a) Fixkosten standortunabhängig b) flächenmäßige Ausdehnung von Facilities irrelevant c) jeder Ebenenpunkt zulässiger Standort ist d) wenig Vorstellung über mögliche Standorte bestehen (keine Vorlieben) e) Distanzen gut zur Approximation der Transportkosten genutzt werden können (->Greenfield Ansatz häufig benutzt um „potentielle“ Standorte zu finden, untere Schranken für Kosten zu ermitteln, danach diskrete bzw. Netzwerkmodelle einzusetzen.)
- Grundannahmen der diskreten gemischt-ganzzahligen Optimierungs (MIP) Standortmodelle sind: - Menge potentieller Standorte gegeben. - Menge zu versorgender Kunden- bzw. Absatzregionen liegt ebenfalls fest - Nachfragemengen unabhängig von der Standortwahl - Transportkosten proportional zur transportierten Menge; (eine lineare Beziehung zwischen Transportentfernungen und Transportkosten ist dagegen nicht entscheidend) - Variable Depotkosten linear mit dem Volumen der umzuschlagenden Mengen (economies of scale also nicht berücksichtigt) - Fixkosten der Depots unabhängig! (von Anzahl, Größe & co).
- Welche zwei Lösungsverfahren für das CFLP und CFLPSS wurden vorgestellt?(Vorlesung): a) Auf Lagrange-Relaxation beruhende Verfahren! (erfolgreich) b) Primale Heuristiken 1. Lokationsentscheidung ist primär (Add/Drop/Swap) 2. Danach Subproblem der Allokationsentscheidung
- Beschreibe das UFLP verbal; was ist die Problemstellung, und was die Zielsetzung? Problemstellung: Auswahl von Standorten (J) und Allokation der Nachfragemengen/-Orte (K). (Theoretisch kann bei jedem KundenKnoten auch ein Standort entstehen) Ziel: Gesamtkosten bestehend aus Fixkosten für Standorte und variablen Versorgungskosten (Allokationskosten) minimieren. -> Trade off
- Was versteht man unter der single assignement property des unkapazitierten Facility Location Problems? Auch wenn die Entscheidungsvariablen xij nicht als binär angenommen werden,so besitzt das unkapazitierte Facility Location Problem immer eine optimaleLösung, in der jeder Kunde i vollständig dem jeweils günstigsten geoöffneten Lagerzugeordnet ist. single assignment property.
- Definitionen/Merkmale für das Optimierungsproblem VRP (Vehicle Routing Problem) Bestimme eine oder mehrere Touren, die vom Depot ausgehen und dort enden (Rundtouren) so, dass: a) Jeder Kunde einmal bedient wird (Bedarf di wird erfüllt), b) die Fahrzeugkapazität C für jedes Fahrzeug eingehalten wird (homogener Fuhrpark), c) ggf. weitere Restriktionen eingehalten werden (Kundenzeitfenster [ai, bi] und d) Eine Zielfunktion minimiert wird.
- 5 Problemklassen für das VRP (nach Domschke u. Scholl): 1) Capacitated Vehicle Routing Problem (CVRP) Jeder Kunde (Knoten) muss bedient werden, Kapazität C von F Fahrzeugen. (Bsp: Paketdient) 2) CVPR mit Zeitrestriktion Maximal Fahrzeit T pro Route (Bsp: Apothekenbelieferung) 3) VRP mit Zeitfenstern (VRPTW) (Bsp: Briefkastenentleerung) 4) Capacitated Chinese Postman Problem (CCPP) Alle Kanten bedienen! (Bsp: Briefzustellung, Winterdienst, Müllentsorgung) 5) Capacitated Arc Routing Problem (CARP) wie 4) Kapazitätsbeschränkung für Fahrzeuge bzw. Tour -> Teilmengen von Kanten enstehen. (Bsp: Briefzustellung, Winterdienst, Müllentsorgung)
- Nenne Verbesserungsverfahren für TSP / VRP: 2-opt*k-optOr-OptCROSSλ-Interchange
Advertisement