Efficient decomposition method for the stochastic optimization of public transport schedules

We propose a new method to optimize public transport schedules by minimizing the waiting time during transfers. Using ticket validation data to construct a realistic scenario-based model of the waiting times, our goal is to design shifts of the current schedules that reduce the overall expected waiting time. For that we propose a parallel local search heuristic that exploits the structure of the problem to efficiently explore a large number of possible schedules. Compared to previous approaches, our algorithm should allow to both treat more transfers (bigger cities) and more scenarios (ensuring a better generalization). We provide promising preliminary results on transit data collected from Nancy, France.