Benders decomposition-based optimization of train departure frequencies in metro networks

Abstract

Timetables determine the service quality for passengers and the energy consumption of trains in metro systems. In metro networks, a timetable can be made by optimizing train departure frequencies for different periods of the day. Typically, the optimization problem that arises from optimizing train departure frequencies in metro networks involves integer variables, which can cause the problem to be computationally too complex for real-time applications. The main objective of this thesis is to reduce the computational complexity of optimizing train departure frequencies in metro networks while maintaining a relatively accurate solution.

In this thesis, we first apply classical Benders decomposition to optimize train departure frequencies in a metro network considering time-varying passenger demands. Subsequently, we apply an $\epsilon$-optimal Benders decomposition approach to reduce the computational complexity further. A simulation-based case study using a grid metro network illustrates the performance of the two Benders decomposition-based approaches.

The simulation results show that the classical Benders decomposition approach significantly reduces the computational burden of optimizing train departure frequencies in metro networks. Moreover, the $\epsilon$-optimal Benders decomposition approach can further reduce the computation time when the problem size increases of the optimization problem when compared to the classical Benders decomposition approach while maintaining an acceptable level of performance.