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 designing train departure frequencies for different periods of the day, which is typically formulated as a mixed-integer linear programming (MILP) problem. In this paper, we first apply Benders decomposition to optimize the departure frequencies considering time-varying passenger origin-destination demands in metro networks. An ϵ -optimal Benders decomposition approach is subsequently used to reduce the solution time further. The performance of both methods is illustrated in a simulation-based case study using a grid metro network. The results show that both the classical Benders decomposition approach and the ϵ -optimal Benders decomposition approach can significantly reduce the computation time for the optimization of train departure frequencies in metro networks. In addition, the ϵ -optimal Benders decomposition approach can further reduce the solution time compared to the classical Benders decomposition approach when the problem scale increases while maintaining an acceptable level of performance. ... Read more