An approximate dynamic programming approach for designing train timetables

Abstract

Traditional approaches to solving the train timetabling problem—the optimal allocation of when each train arrives and departs each station—have relied on Mixed-Integer Programming (MIP) approaches. We propose an alternative formulation for this problem based on the modeling and algorithmic framework of approximate dynamic programming. We present a Q-learning algorithm in order to tractably solve the high-dimensional problem. We compare the performance of several variants of this approach, including discretizing the state and the action spaces, and continuous function approximation with global basis functions. We demonstrate the algorithms on two railway system cases, one minimizing energy consumption subject to punctuality constraints, and one maximizing capacity subject to safety constraints. We demonstrate that the ADP algorithm converges rapidly to an optimal solution, and that the number of iterations required increases linearly in the size of the rail system, in contrast with MIP approaches whose computation time grows exponentially. We also show that an additional benefit to the ADP approach is the intuition gained from visualizing the Q-factor functions, which graphically capture the intuitive tradeoffs between efficiency and constraints in both examples.