sukzessive Entscheidungsfindung Flashcards
Urbane Tourenplanung
Grundlagen
- Services mit einer Fahrzeugflotte
- Operative Ebene: Ressourcen gegeben
- Tourenplanung:
- Zuordnung von Kunden zu Fahrzeugen
- Reihenfolgeplanung
- Privatkunden
- Kostenintensiver Teil der Supply Chain
- Hohe Kundenerwartung
- Anwendungsgebiete:
- Warentransport
- Personentransport
- Dienstleistungen beim Kunden
- Stochastizität durch die unsicheren Einflüsse, wenn Unsicherheit zu groß soll man dynamisch planen
- Dynamik
Trend: stochastische dynamische Tourenplanung
Stochastizität: unvollständige Information, Unsicherheit hauptsächlich durch: fahrzeiten, Kundenbedarf, kundenanfragen und Service-Zeiten beim Kunden
Dynamik Grundlagen
=Sukzessive Kontrolle und Anpassung durch die Steuerung
- Unterschiedliche Planung je Anwendungsgebiet
- Statische Planung:
- Umplanung nicht möglich
- Umsetzung eines a-priori Planes
- Beispiel: Bus
- Dynamische Planung:
- Hoher Einfluss von Unsicherheit erfordert Umplanung
- Adaptionen von Tourenplänen
- Beispiel: Paketdienst im Stadtverkehr
Dynamischer Entscheidungsprozess
- Exogener Informationsprozess
- Folge an Zuständen
- Entscheidungen pro Zustand
- Kosten/Nutzen pro Entscheidung
Beispiel: Unterscheidung von 2 Fällen –> Durchführung initiale Tour oder Umplanung
Motivation: Verkehrsmanagement
- Steuert Verkehrsflüsse in der Stadt
- Ziele:
- Effiziente Mobilität ermöglichen
- Gesellschaftliche und politische Vorgaben
- Emissionen
- Lautstärke
- Abgase
- EU-Regulation zu Stickoxiden
- Stationen an Hotspots messen Stickoxide
Verfahren in Fallstudie: Intitiale Verteilung: vehicle Routing problem mit Zeitlimit, Für jedes Fahrzeug zu jeden Entscheidungszeitpunkt: Zur Matrixerstellung: Dijkstra-Algorithmus –> Lösen eines offenen Traveling Salesman Problems:
Standardproblem der statischen Tourenplanung
- Depot, Kunden, Fahrzeuge
- Nebenbedingungen: Kapazität
- Zielfunktion: Min Fahrzeit
- Entscheidung
- Zuordnung von Kunden zu Fahrzeugen
- Reihenfolge der Kunden pro Fahrzeug
- Modellierung:
- Gemischt-ganzzahlige Programmierung
- Lösung: Tourenplan
- Keine Abbildung zeitlicher Entwicklung
Markov Entscheidungsprozess
Komponenten:
- Entscheidungs-Zustand 𝑆𝑘 ∈ 𝐒
- Entscheidungen 𝑥 ∈ 𝑋
- Nutzen 𝑅 𝑆𝑘,𝑥 ∈ℝ
- Zustand nach Entscheidung 𝑆𝑘𝑥 ∈𝐒×𝑋
- Stochastischer Übergang 𝜔𝑘 ∈𝐒×𝑋×𝐒
- Übergangswahrscheinlichkeiten ℙ: 𝐒×𝑋×𝐒 →[𝟎,𝟏]
Eine Entscheidungspolitik ordnet jedem Zustand eine Entscheidung zu
Zusammenfassung Dynamik
- Motivation und Definition: Stochastische Dynamische Tourenplanung
- Fallstudie: Dynamische Reaktionen auf Änderungen der Verkehrssteuerung erlauben kürzere Routen
- Modellierung: Markov Entscheidungsprozess