Konzeptionierung und Implementierung einer Metaheuristik für das Electric Vehicle Scheduling Problem mit mehreren Depots

Betreuer: Nils Olsen, Prof. Dr. Natalia Kliewer

Zielgruppe: Masterstudierende

Voraussetzungen: Programmierkenntnisse

Art der Arbeit: konzeptionell; methodisch

Kurzbeschreibung: In den letzten Jahren ist eine zunehmende Elektromobilisierung des Verkehrs zu beobachten, die sich auch auf den öffentlichen Personennahverkehr (ÖPNV) auswirkt. ÖPNV-Betriebe sehen sich neuen Herausforderungen gegenüber, die nun in der Fahrzeugeinsatzplanung berücksichtigt werden müssen. So gilt es sowohl die begrenzte Reichweite von E-Fahrzeugen als auch die Möglichkeit zur Wiederaufladung bzw. zum Austausch der Batterie bei der Erstellung eines kostenminimalen Umlaufplans zu berücksichtigen. Wir bezeichnen dieses Problem als Electric Vehicle Scheduling Problem (EVSP). Es handelt sich um ein NP-schweres Problem, das mit exakten Ansätzen bisher nicht für Instanzen realer Größe gelöst werden kann. Häufig werden deshalb heuristische oder metaheuristische Verfahren zur Berechnung einer möglichst guten Lösung eingesetzt.

Ziel dieser Arbeit ist es, eine Metaheuristik für das EVSP mit mehreren Depots zu entwickeln. Ausgehend von einem Literaturüberblick, soll eine geeignete Metaheuristik zunächst konzeptioniert und schließlich auch implementiert werden. Es stehen verschiedene reale Instanzen zur Verfügung, die zum Testen des Verfahrens verwendet werden können. Anhand der Testergebnisse soll die Eignung der Heuristik evaluiert und kritisch beurteilt werden.

Literaturhinweise:

  1. Adler, J. D. (2014). Routing and Scheduling of Electric and Alternative-Fuel Vehicles. Dissertation, Arizona State University. Verfügbar unter http://repository.asu.edu/attachments/134788/content/Adler_asu_0010E_13619.pdf
  2. Li, J.-Q. (2014). Transit Bus Scheduling with Limited Energy. Transportation Science, 48, 521-539. Verfügbar unter http://pubsonline.informs.org/doi/abs/10.1287/trsc.2013.0468
  3. Dréo, J., Petrowski, A., Siarry, P. & Taillard, E. (2006). Metaheuristics for hard optimization: Methods and Case Studies. Springer-Verlag Berlin Heidelberg.
  4. Michalewicz, Z., & Fogel, D. B. (2004). How to solve it: modern heuristics. Springer.

 

icon3_department_wirtschaftsinformatik
Visit www.or2017.de ...