iTIXIOptimierungsprojekt 2013

Fahrwegoptimierung

http://sourceforge.net/projects/itixi/

Version Datum Author Status Kommentar

1.1g 15.11.2012 Martin Jonasse In Arbeit Initial-Dokument.

 2.0a  28.11.2012 Martin Jonasse In Arbeit Erweitert mit Vektor-Grafik 

 2.0d  13.12.2012 Martin Jonasse In Arbeit Erweitert mit Lesitungsmerkmale

 2.0d  25.12.2012 Martin Jonasse In Arbeit Erweitert mit Optimierungs Messwerte

 3.0 20.01.2013 Martin Jonasse In Arbeit Erweitert mit FAHRPLAN

 3.1 17.04.2013 Martin Jonasse Bereit Datei von Proof of Concept in Fahrwegoptimierung umgenennt

 3.2 31.07.2013 Martin Jonasse Bereit  Logo angepasst, Software Anforderungen hinzugefügt

         

Historie

FahrwegoptimierungOptimierungsprojekt 2013

• Fahrwegoptimierung ist ein Software Algorithmus, der den günstigsten Touren für alle bereitgestellten Fahrzeuge berechnet.

• “Günstigsten” kann sein:– Wenigsten kilometer gesamt (Wirtschaftliches Ziel)– Bestmögliche Auslastung der Fahrer (Wirtschaftliches Ziel für Zivilschützer)– Etc.

• Der “multi-vehicle routing problem with time window” (m-VRPTW) Algorithmus wird in den nachfolgende Slides kurz erläutert.

Adressenliste ListeOptimierungsprojekt 2013

Adressen

• Alle Abhol- und Ziel-Adressen sind in ein Datenbank erfasst:– Mitglied-Adressen– OVI-Adressen

(Ort von Interesse)

• Jede Adresse enthält “Strasse Nummer”, “Ort” und GPS Koordinaten (Google Maps ).

Fahrbereitschafts ListeOptimierungsprojekt 2013

Fahrbereitschaft• Welche Fahrzeuge sind

verfügbar (Anzahl Sitze, Anzahl Rollstühle).

• Welche Fahrzeuge fahren zuerst (Disposition), und sind welchen Schicht und Fahrer zugeordnet.

• Eine Routing-Liste (Fahrauftrag) wird für jedes Fahrzeug individuell erstellt (automatisiert).

Holding ListeOptimierungsprojekt 2013

• Touren:– Alle Touren einer Schicht

• Tour:– Definiert durch Abhol-Zeitpunkt– Definiert durch zwei Adressen

• Route(km, dauer): – Definiert durch Google Maps.

• Schicht: – Einsatz-Zeitraum (von – bis) für

Fahrer. – Beginnt und endet an ein

bestimmten Ort (Depot).

Zeit

Ko

ord

ina

ten

Schicht

Routing ListeOptimierungsprojekt 2013

• Alle Routen-Varianten werden in einen rekursiven Algorithmus berechnet und die Route mit den optimale Kosten ermittelt.

• Eine Route ist die optimalste1) Summe der machbaren Touren zwischen Anfang und Ende des Schichtes (Depot-Depot).

• Ein Leerfahrt verbindet zwei Touren:

– Leerfahrt (Länge(km) & Dauer(hr))

– Wartezeit (Dauer(hr))

– Machbarkeit ist gegeben, wenn die Wartezeit > 5 Minuten, und die Fahrstrecke > 0.1 km ist.

Depot, Anfang Schicht

Depot, Ende Schicht

LeerfahrtLeerfahrt

TourTour

Nicht machbarNicht machbar

1) Optimalste variante = die meiste Kunden pro Schicht, mit wenigsten Leerfahrkm.2) Routen: ca. 8 Millionen Nodes errechnet bei 18 Fahrzeuge und 70 Bestellungen

FahrauftragOptimierungsprojekt 2013

FahrplanOptimierungsprojekt 2013

FahrkarteOptimierungsprojekt 2013

LeistungsmerkmaleOptimierungsprojekt 2013

• Fahrdauer und Fahrkilometer abgefragt in Google Maps.

• Zeitzuschlag für

– Einsteigen (+3 Minuten)

– Aussteigen (+3 Minuten)

– Rechtzeitiges Eintreffen beim Kunde (+5 Minuten vorher)

• Routen – Optimierung (Wirtschaftlichkeit / Auslastung Fahrer)

• Erweiterungen (geplant):

– Sammel-Aufträge mit >1 Kunde mit gemeinsame Abholort oder Zielort

– Individuelle Zuschläge pro Kunden (z.B. Rollstuhl, +10 minuten)

– Zeit und Ortsabhängige Zuschläge (z.B. Zug, Baar, Cham, Mo – Fr, 16h – 19h)

Software AnforderungenOptimierungsprojekt 2013

Non-funtional requirements:

•Systemnah in C++(Windows) bzw. GCC(LINUX) geschrieben.

•Die neue Software muss zwingend in der Produktions-Umgebung des Providers unterstützt werden.

•Maximal 1 Minute Laufzeit für eine Optimierung von ein Schicht mit 100 Fahraufträge und 20 Fahrzeuge.

Functional requirements (SRS-Liste.xls:F-110):

•Schnittstellen zu Symfony2 mit PHP 5.4 iTIXI Applikation.

•Angestossen durch Disponentin (Funktionspunkt).

•Optimierung kann leicht durch ein Administrator verändert werden.

•Algorithmus muss mehrere „Tabu“ aus der SRS-Liste unterstützen:– Unverträglichkeit zwischen Fahrer und Fahrgast

– Fahrer die keine Rollstühle befördern wollen

– Etc. (z.B. aber nicht abschliessend)

AppendixOptimierungsprojekt 2013

• Optimierungs-Varianten• Optimierung, Clustering• Optimierung, Kunden/Fahrt• Optimierung, Kilometer/Fahrt

Optimierungs-VariantenOptimierungsprojekt 2013

Zwei Optimierungs-Varianten stehen im Vordergrund:

(1) Max Kunden, min Leerfahrtkm

(2) Max Kunden, max Fahrtkm

Beide Varianten sind neutral bezüglich der Anzahl Fahrzeuge die benötigt werden (nur von Fahrziele und Abholzeiten abhängig).

Variante (1) schneidet 10% besser ab betreffend gefahrene Kilometer (Minderkosten: Benzin und Service-Intervalle).

Ökologisch equivalent mit das Pflanzen von 416..832 Bäume

Optimierung, ClusteringOptimierungsprojekt 2013

Optimierung, Kunden/FahrtOptimierungsprojekt 2013

Max Kunden, min Leerfahrtkm

Horitontal (x): Fahrzeug LaufnummerVertikal (y): Anzahl Kunden (max, durchschnitt, min)Proben: 12 Schichten

Durchschnittswerte:Fahrzeuge 15.3 Fahrzeuge/ Schicht (102.0%)Fahrtkm 603.3 km/SchichtLeerfahrtkm: 461.2 km/ Schicht (100%)Total: 1065 km/ Schicht (100%) 57.8 Kunden/ Schicht

Max Kunden, max Fahrtkm

Horitontal (x): Fahrzeug LaufnummerVertikal (y): Anzahl Kunden (max, durchschnitt, min)Proben: 12 Schichten

Durchschnittswerte:Fahrzeuge 15.0 Fahrzeuge/ Schicht (100%)Fahrtkm 605.0 km/SchichtLeerfahrtkm: 559.2 km/ Schicht (121.0%)Total: 1164 km/ Schicht (109.4%) 57.9 Kunden/ Schicht

Optimierung, Kilometer/FahrtOptimierungsprojekt 2013

Max Kunden, min LeerfahrtkmMax Kunden, max Fahrtkm

ENDE