Prozess der Entscheidungsunterstützung

Question 1

Tourenplanung in der City-Logistik

Answer 1

• E-Commerce-Angebote setzen die verlässliche Auslieferung der Produkte beim Kunden voraus
• City-Logistik-Serviceprovider führen die Auslieferung durch
• Voraussetzung: Anwendungssystem, welches die Tourenplanung unterstützt
• Rahmenbedingungen
  
  • Kundenanforderungen nehmen zu
  • Auslastung der Infrastruktur schwankt (→Stau)
• Konzeption des Anwendungssystems
  
  • Welche Daten sind erforderlich, wie können sie erhoben und für die Tourenplanung eingesetzt/aggregiert werden?
  • Welche Methoden sind für die städtische Tourenplanung geeignet?
  • Integration von Daten und Methoden im Tourenplanungssystem
• Problemcharakteristika:
  
  • Fahrzeug
  • Kunden
  • Kommunizierte Zeitfenster
  • Tageszeitabhängige Fahrzeiten
• Anwendungensbeispiele:
  
  • Lieferdienste
  • Dienstleistungen beim Kunden
  • Personentransport

Modell-Skizzen:

• Datenmodell:
  
  • Tageszeitabhängige Fahrzeiten zwischen Kunden (inklusive Depot)
  • Zeitabhängige Distanzmatrix
• Entscheidungsmodell:
  
  • Zielfunktion: Minimiere Fahrzeit/Kosten
  • Nebenbedingungen:
    
    • Alle Kunden werden bedient
    • Routing-Bedingungen (Subtour-Elimination, etc.)
• Entscheidungsvariablen: Fahrt zwischen Kunde i und j zum Zeitpunkt t

Question 2

Datenerhebung im Verkehr - EInführung

Answer 2

• Eine verlässliche Tourenplanung setzt die Erhebung und Bereitstellung typischer Fahrzeiten voraus
• Generelle Daten zur Verkehrsinfrastruktur sind in digitalen Karten verfügbar (→Technologie-Vorlesung)
• Informationen zur Verkehrsqualität, d.h. zu typischen Fahrzeiten, lassen sich Telematik-basiert großflächig erheben
• Entsprechende Verfahren der Tourenplanung können so typische Fahrzeiten berücksichtigen

Standardverfahren zur Ermittlung der Verkehrsqualität

• Datenerhebung an wenigen, wichtigen Punkten des Verkehrsnetzes →Kalibrierung verkehrstechnischer Modelle
• Hohe Erhebungskosten
• Ableitung von Fahrzeiten aufwändig und modellseitig problematisch
• Detaillierte Infrastrukturdaten sind nicht flächendeckend verfügbar

Telematikbasierte Verkehrsdatenerhebung (floating car data)

• Erweiterung der Standardansätze durch automatisierte Verkehrsdatenerhebung
• Neuere Ansätze erlauben die direkte Ableitung von Fahrzeiten
  
  • speziell präparierte Fahrzeugflotte (Fleischmann et al. 2004)
  • „Road Timetable“ (Eglese et al. 2006, Maden et al. 2010)
  • „Floating Car Data“ (DLR, Lorkowski et al. 2005)

Question 3

Floating Car Data

Answer 3

• Zur Ermittlung von typischen Fahrzeiten ist es notwendig Reisezeiten über einen längeren Zeitraum zu beobachten
• Mit Hilfe von Bewegungsverläufen von einzelnen Fahrzeugen können individuelle Reisegeschwindigkeiten abgeleitet werden
• Beim Floating-Car-Data-Ansatz (FCD) werden Fahrzeuge instrumentalisiert, um Verkehrsdaten zu erheben. Diese Fahrzeuge „schwimmen“ bereits im Verkehr „mit“ und übermitteln ihre individuellen Reisezeiten
• Die Nutzung einer umfangreichen FCD-Flotte führt zu einem Gesamtbild typischer Fahrzeiten in einem Untersuchungsgebiet

FCD: Fahrzeuge als im Verkehr mit schwimmende Sensoren
Taxi-FCD: Projekt des DLR Berlin, Institut für Verkehrssystemforschung

• Die Beobachtung von Einzelgeschwindigkeiten im Floating-Car-Data-Ansatz:
  
  • Erfassung der Taxi-Positionen
  • Projektion auf das Straßennetz
  • Ermittlung der Geschwindigkeiten
  • Abbildung auf Straßensegmente (Link)

Question 4

Datenanalyse mit Data Mining

Answer 4

• Knowledge Discovery: Data mining is the process of discovering interesting knowledge from large amounts of data stored either in databases, data warehouses, or other information repositories.
• Standard: Kalibrierung von Verkehrsflussmodellen
• Hier: Analyse und Aggregation umfangreicher Mengen von FCD mit Data Mining für die Verwendung in der Tourenplanung
• Analyse großer, empirisch erhobener Datenmengen:
  
  • Kleine Datenmengen –> Statistik, Explorative Datenanalyse
  • Große Datenmengen, neue Probleme:
    
    • Speicherung und Zugang zu den Daten
    • Inwieweit sind die Daten repräsentativ?
    • Laufzeit und Speicherplatz
    • Ist ein offensichtlicher Zusammenhang Zufall?
    • Standardansätze der Statistik teilweise ungeeignet
• Beziehungen und Aggregate:
  
  • Im Data Mining Informationsmodelle und Informationsmuster
  • Z.B. Lineare Gleichungen, Baumstrukturen, Cluster, Muster in Zeitreihen
• Beobachtete Daten:
  
  • Daten werden zunächst aus anderen Gründen erhoben –> Ziele des Data Mining spielen i.d.R. keine Rolle bei der Datenerhebung
  • Z.B. FCD: werden eigentlich zum Flottenmanagement des Taxi Unternehmens eingesetzt
  • Gegenteil: Experimentell erzeugte Daten (oft in Statistik)
• Neu:
  
  • Ergebnisse der Data-Mining-Analyse sollten neu für den Nutzer sein Verständlichkeit:
  • “Neuheit” als Maß allein ist nicht ausreichend, um Ergebnisse zu bewerten
  • Evtl. werden einfache Beziehungen komplexen vorgezogen

Question 5

Erhebung und Reinigung von (empirischen) Rohdaten

Answer 5

• Bereitstellung eines geeigneten Datensatzes für Data-Mining-Verfahren
• Data Integration: Integration von FCD-Rohdaten (Verkehrsdaten) und einer digitalen Karte (Infrastrukturdaten)
• Data Cleaning: Untersuchung der Einträge auf Konsistenz, Vollständigkeit und fehlende Werte, Ausreißer
• Raum-Zeit-Analyse: Visualisierung der erhobenen Daten mit Geografischen Informationssystemen
• Welche Messwerte stellen Ausreißer oder fehlerhafte Messwerte dar?
• Generelle Definition im Stadtverkehr schwierig, da eine Vielzahl von Einflüssen auf die Erhebung der Fahrzeit einwirkt (z.B. Lichtsignalanlagen, Bushalte, Fußgänger, Auslieferverkehr, …)

Question 6

1. Aggregationsstufe: von ROhdaten zu Planungsdaten

Answer 6

Aus Fahrzeugdaten:

• 1. Festlegung der Gesamt- anzahl der Zeitfenster W (oft: 24 x 7)
• 2. Berechnung mittlerer Geschwindigkeiten
• für Link l
• in Zeitfenster w
• aus Einzelgeschwindigkeiten vlwi

–> kommt so zu Fahrzeitmatritzen

Question 7

2. Aggregationsstufe: Idee & Ergebnis der Clusteranalyse

Answer 7

• 1. Aggregationsstufe führt zu umfangreichem Planungsdatensatz
     * Aber: Mathematische Modelle arbeiten effizienter auf vereinfachten Datensätzen
     * Idee: Entwicklung der typischen Verkehrsqualität ähnelt sich auf vielen Strecken!
     * ➔Ermittlung der typischen Verkehrsqualität für jede Strecke (Normalisierung der Geschwindigkeitswerte)
     * ➔Clusteranalyse zur Gruppierung von Strecken mit ähnlicher Verkehrsqualität

Prinzip der Clusteranalyse

• Cluster = Sammlung von Datenobjekten, die sich ähnlich sind
• Im Data Mining Bestandteil der “Deskriptiven Modellierung”
• Hauptzwecke (Methode des nicht überwachten Lenens)
  
  • Auffinden von Mustern in einer Verteilung sowie von interessanten Beziehungen zwischen Attributen
  • Datenreduktion: Nutze Cluster als Repräsentanten für die zugrundeliegenden Datensätze
• Verfahren: Dichtebasiert, Partitionsbasiert, k-means

2. Aggregationsstufe: Ergebnis der Clusteranalyse

• Ergebnis der Clusteranalyse: Tagesspezifische Gewichtungsfaktoren zur Justierung von Mittelwerten
• 0 = schlechte Verkehrsqualität →hohe Fahrzeit
• 1 = gute Verkehrsqualität →geringe Fahrzeit

Question 8

Evaluation und Anwendung

Answer 8

• Bewertung mittlerer Reisezeiten (“überlastet”, “freier Verkehrsfluss”, …)
• Aggregierter, zeitlicher und räumlicher Überblick über die Entwicklung der Verkehrsqualität
• Grundlage für Experteninterviews (→Validierung durch Verkehrsexperten)

Evaluationsarten

• zeitliche Evaluation: Visualisierung der typischen Reisezeiten im zeitlichen Überblick (24 Stunden) und als räumlicher Überblick (für jeweils 1 Stunde)
• räumliche Evaluation: Durchschnitt von 3 Jahren 30% aller Strecken sind “überlastet”

Question 9

Zeitabhängiges Traveling Salesman Problem

Answer 9

• Traveling Salesman Problem: Ein Handlungs- reisender besucht eine fest vorgegebene Anzahl von Städten jeweils genau einmal. Am Ende der Reise kehrt er wieder zum Ursprungsort zurück.
• Hier: In welcher Reihenfolge soll die Auslieferung an die Kunden vorgenommen werden, so dass diese verlässlich und kostenminimal beliefert werden können?
• Gesucht: Reihenfolge der Kunden, die die Fahrzeit minimiert und gleichzeitig eine zuverlässige Belieferung erlaubt (→tageszeitabhängige Fahrzeiten)

Modellierung der Zeitabhängigkeiten

• Tageszeitabhängige Fahrzeiten werden modelliert, indem man die “Kosten” einer Kante abhängig vom Startzeitpunkt auf der Kante angibt
• Ein möglicher Ansatz:
  
  • − Berechne viele “statische” Probleme mit unterschiedlichen Kantengewichten
  • − Füge diese geeignet zusammen
• Klassischer Ansatz: Vervielfachung des Netzwerks der Zeitreihe entsprechend
• FIFO: Fahrzeuge auf derselben Kante können sich nicht überholen
• FIFO Netzwerke stellen sicher, dass − Warten nie nützlich ist − Teilwege kürzester Wege wieder kürzeste Wege sind
• Statische Verfahren für die Berechnung kürzester Wege (→Dijkstra) können so einfach angepasst werden

Question 10

Tourenplanung für ein Fahrzeug

Answer 10

• Zeitabhängiges Traveling-Salesman-Problem (TDTSP): Bestimme die optimale Reihenfolge der Auslieferung für eine gegebene Abfahrtszeit
• Besuche den Knoten als nächsten, der derzeit mit kürzester Fahrzeit zu
  erreichen ist
• Simples Nachschlagen der Fahrzeit in zeitabhängiger Distanzmatrix
• Ermittle Einfügeposition und Knoten so, dass jeweils eine minimale Verspätung
  am Depot entsteht
• Aufwändiger als im Falle statischer Fahrzeiten
• Bediene alle Kunden zunächst in Pendeltouren und verschmelze diese
  so, dass eine große Einsparung erzielt wird
• Statische Berechnung von Savings widerspricht zeitabhängigen Fahrzeiten

Question 11

Zusammenfassung

Answer 11

• Die verlässliche Tourenplanung im städtischen Güterverkehr beruht auf…
  
  • …empirischen Verkehrsdaten, die geeignet zu erheben sind (→telematikbasierte Datenerhebung)
  • …der Filterung, Reinigung, Aggregation und Evaluation der empirischen Verkehrsdaten (→Data Mining)
  • …der Integration der Planungsdaten in angepasste Verfahren der Tourenplanung (→zeitabhängiges Traveling Salesman Problem)
  • …die Rücküberführung in explizite Navigationsanweisungen (→Dissaggregation mittels zeitabhängiger kürzester Wege)