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.