Bi-Weekly Talk: Björn Tauer: Waiting for Trains: Complexity Results

Wednesday, October 30, 2019, 10:30am

Location: RWTH Aachen University, Department of Computer Science - Ahornstr. 55, building E3, room 9u10

 

 

Waiting for Trains: Complexity Results

We introduce a model for train routing on railway systems. Trains route through a network over time from a start to an end depot. They occupy consecutive nodes and edges corresponding to their length and block each other. We study the case where the depots are part of the network (internal) and the case where the depots are not part of the network (external). The problem is a generalization of packet routing without buffers. We consider two different kinds of optimization problems. In the first, trains are only allowed to wait on predefined paths and in the second, trains are additionally allowed to shunt, i.e., change direction. In both cases, we are interested in minimizing the overall makespan. For waiting instances, we find np-hardness results even on unidirectional paths. We also show $W[1]$-hardness and lower bounds on the running time using the Exponential Time Hypothesis. For shunting instances, we show pspace-completeness results on simple grid tracks and reuse the previously shown np-hardness results. We present a polynomial time algorithm for a special subclass of unidirectional paths.

(Joint work with UnRAVeL members Dennis Fischer, Janosch Fuchs, Laura Vargas Koch and Stephan Zieger)