8th International Conference on Computational Management Science - CMS 2011, Neuchâtel (Switzerland). 28-30 abril 2011
Summary:
We present a timetabling model to design tactical operation strategies robust to possible delays, based on the modeling and algorithmic framework of approximate dynamic programming. The objective is to efficiently dimension time slacks to ensure certain punctuality level. Both, the state space and the action space are highly multidimensional. We present a Q-learning algorithm and compare the performance of discretizing the state and the action spaces with several alternative continuous function approximation techniques, including approximation with basis functions and mesh-free techniques. Compared to a Mixed-Integer Programming (MIP) approach, where the classical decomposition algorithms cannot be directly used to solve this non-convex problem, this framework enables efficient computation of problems with high dimensionality. The algorithms have been tested in some railway systems study cases. The objective is to design robust, efficient train timetables for different railway systems. The efficiency is measured in terms of use of the capacity, energy consumption, etc., while the robustness is guaranteed since the model includes constraints to ensure a minimum punctuality level.
Publication date: April 2011.
Citation:
Peña, M., Webster, M., Ramos, A., Adeyemo, A., An approximate dynamic programming approach for designing train timetables with punctuality constraints, 8th International Conference on Computational Management Science - CMS 2011, Neuchâtel (Switzerland). 28-30 April 2011.
IIT-11-145A_abstract
