In this seminar, we will study literature on various incarnations of shortest path problems, such as:

  • constrained shortest paths
  • passenger routing in public transport networks
  • routing for electric vehicles on road networks


Final schedule:

Thu09.00Mingyang LiuConnection Scan Algorithm
Thu10.00Yurong DingRound-Based Public Transit Routing
Thu11.00Daniel JentschFrequency-Based Search for Public Transit
Thu12.00Christoph GrafeCustomizable Contraction Hierarchies
Fri09.00Denghua LeiFast Routing in Very Large Public Transportation Networks using Transfer Patterns
Fri10.00Celine NoeckelBidirectional A* Search on Time-Dependent Road Networks
Fri11.00Sarah RothIntriguingly Simple and Efficient Time-Dependent Routing in Road Networks
Fri12.00Richard LützkeEfficient Computation of Shortest Paths in Time-Dependent Multi-Modal Networks
Fri14.00Nilofar RahmatiOptimal Route Planning for Electric Vehicles in Large Networks
Fri15.00Andre KraussFormal-Language-Constrained Path Problem
Fri16.00Antonia ChmielaSolving resource constrained shortest path problems with LP-based methods
Fri17.00Bastian SchröpfModeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles
Schedule & Location: 
  • First meeting: April 17, 10 am, ZIB lecture hall 2005
  • Second meeting: May 15, 10 am, ZIB seminar room 2006
  • Talks: July 19 and 20, ZIB lecture hall 2005

There will be an after-seminar evening event on July 20.


Requirements & Formalities: 

Students should have some background in graph theory ( e.g. Discrete Mathematics I at FU).

Some papers require knowledge about linear programming.

On May 15, you are supposed to give a short, introductionary talk (at most 5 minutes) on your topic.

The seminar itself will take place on July 19 and 20. Talks should be prepared for 45 minutes, so that a duration of 60 minutes including questions is not exceeded.

For obtaining the credit points, you are also required to hand in a short summary of your talk (please use LaTeX, 5-8 pages). The summary should be sent by e-mail to your advisor (Niels, Pedro or Ricardo) no later than August 19, 2018.



Prof. Dr. Ralf BorndörferZIB 
Dr. Niels LindnerZIB 3007lindnerzib.deChmiela, Ding, Jentsch, Lei, Liu
Pedro Maristany de las CasasZIB 3003maristanyzib.deGrafe, Noeckel, Rahmati, Schröpf
Ricardo EulerZIB 3023eulerzib.deKrauss, Lützke, Roth, Wang