Standort

DE, Karlsruhe
PTV Planung Transport Verkehr AG

Abschlussarbeit im Bereich Algorithm Engineering

Deine Aufgaben

Algorithmen zur Verkehrsumlegung (traffic assignment) sind ein unverzichtbarer Bestandteil von softwarebasierter Verkehrsplanung und werden in nahezu allen größeren Städten weltweit eingesetzt. Aufgabe einer Verkehrsumlegung ist es, auf Basis einer gegebenen Verkehrsnachfrage in Form von Quelle-Ziel-Matrizen die Routenwahl der Verkehrsteilnehmer vorherzusagen.

Die häufigste Grundannahme dabei ist, dass jeder Verkehrsteilnehmer seine eigene Reisezeit (oder allgemeiner: Kosten, in die neben der Reisezeit beispielsweise auch die Länge des Weges oder Maut eingehen können) zu minimieren versucht. Mit einer einfachen Many-To-Many-Kurzwegsuche ist es aber nicht getan, da die Reisezeit auf den Kanten abhängig vom Fluss ist. Stattdessen kann es für jede Quelle-Ziel-Beziehung mehrere verwendete Wege geben – der gesuchte Verkehrszustand ist dann erreicht, wenn alle verwendeten Wege die gleichen Kosten haben. Die Aufgabe der Verkehrsumlegung lässt sich als ein Optimierungsproblem auf Graphen formulieren.

In den letzten Jahrzehnten sind verschiedene Arten von Algorithmen zur Lösung des Problems entwickelt worden. Viel Aufsehen hat dabei vor ein paar Jahren das Verfahren TAPAS erregt: Traffic Assignment by Paired Alternative Segments. TAPAS brachte eine ganze Reihe von neuen Ideen und hat bessere Konvergenzeigenschaften als klassische Algorithmen, die im Wesentlichen auf iterierten Kurzwegsuchen basieren.

In der Literatur wurde TAPAS bislang allerdings nur auf vergleichsweise kleinen Verkehrsnetzen (maximal 40000 Kanten) betrachtet. In ersten Experimenten auf großen Verkehrsnetzen (1 Million Kanten) oder sehr zugestauten Verkehrsnetzen zeigt sich, dass die guten Konvergenzeigenschaften teilweise verloren gehen. Außerdem steigt die Laufzeit deutlich an.

Im Rahmen dieser Arbeit sollen basierend auf einer prototypischen Implementierung verschiedene Analysen und Erweiterungen an TAPAS vorgenommen werden.
  • Es soll untersucht werden, warum die Konvergenz des Verfahrens in späteren Iterationen in großen und zugestauten Verkehrsnetzen abflacht.
  • Es soll untersucht werden, welche Auswirkungen verschiedene kleinere Modifikationen des Verfahrens auf Laufzeit und Konvergenz haben.
  • Die Bausteine, aus denen TAPAS besteht, sind in sich inhärent seriell. Es soll untersucht werden, wie sich das Verfahren modifizieren lässt, sodass wesentliche Teile parallel ablaufen können, und welche Auswirkungen das auf die Konvergenz hat.

Dein Profil

  • Gute Kenntnisse in C++, idealerweise Erfahrung mit paralleler Programmierung (z.B. TBB)
  • Gute Kenntnisse in (parallelen) Algorithmen und Datenstrukturen
  • Grundkenntnisse in mathematischer Optimierung
  • Bereitschaft, sich selbständig in ein komplexes Thema einzulesen

PTV. The mind of movement.

Wir planen und optimieren weltweit alles, was Menschen und Güter bewegt.
PTV Software macht Mobilität effizienter, sicherer und umweltfreundlicher. Unsere Lösungen unterstützen unsere Kunden in der Transportlogistik, der Verkehrsplanung und im Verkehrsmanagement. Werde Teil eines Teams, das die Welt bewegt.

PTV als Arbeitgeber

In diesem Video erfährst du mehr zur Beschäftigung von Studierenden bei der PTV Group.
 

Benefits

  • Flexible Arbeitszeiten
  • Weiterbildung an der PTV-Academy
  • Fitnesscenter am Hauptsitz Karlsruhe
Silke Schindel

Human Resources
Business Partner