To ensure that the urban rail transit network timetables serve the passenger demand better, a flexible departing scheme was developed to improve the synchronization performance. Departure times with even headways were taken as the benchmark points, and the actual departure times were allowed to vary around the benchmark points within a certain range. Then, a synchronization optimization model with flexible departure headways was proposed to maximize the number of transfer-synchronized passengers in a network. Considering that the model includes an enormous amount of binary variables, an efficient genetic algorithm was designed to solve the model within limited time. The departure phase of each line with even headways and the flexibility of the departure time of each train were chosen as genes to form the chromosome. Finally, experiments were carried out and results showed that the genetic algorithm performed well and the method could improve the number of synchronized passengers significantly compared with the even-headway timetable that a flexibility of 10% in the even headway corresponded to an 11.85% increment in the number of synchronized passengers. The synchronized timetable with high transfer efficiency of a large-scale network could be quickly by the proposed method.