Bicycles routes in traffic light networks

We report on work in progress on the question of finding good paths for bicycles in a traffic network with (possibly coordinated) traffic lights. While the standard dynamic shortest path problem in time-dependent networks with cyclic time windows is known to be easy, we study the related problem of finding routes that keep a small number of stops.  We show that the problem is strongly NP-hard for paths and trails, whereas it is weakly NP-hard for walks. We give a pseudo-polynomial algorithm for this third option. Further, we report about ongoing work on designing algorithms for the case of variable speeds and the employment of appropriate power consumption and recovery models for bicycles for the above formulated problem.

Joint work with Markus Rogge, Robert Scheffler & Martin Strehler.