Synchronization of bus timetabling

Timetable generation is a subproblem of bus network strategic planning, in which the departure time of each trip is determined. We study the bus network of Monterrey, Mexico, which is similar to those of other cities in Latin America. It is a large bus network where passenger transfers must be favored, almost evenly spaced departures are sought, and bus bunching of different lines must be avoided. We formulate the timetabling problem of this network with the objective of maximizing the number of synchronizations to facilitate passenger transfers and avoid bus bunching along the network. We define these synchronizations as the arrivals of two trips with a separation time within a time window to make a flexible formulation. This flexibility is a critical aspect for the bus network, since travel times vary because of reasons such as driver speed, traffic congestion, and accidents. By proving that our problem is NP-hard we answer a 10-year-old open question about the NP-hardness of similar problems present in literature. Next, we analyze the structural properties of the feasible solution space of our model. This analysis leads to a preprocessing stage that eliminates numerous decision variables and constraints. Moreover, this preprocessing defines feasible synchronization and arrival time windows that are used in a new metaheuristic algorithm. Empirical experimentation shows that our proposed algorithm obtains high-quality solutions for real-size instances in less than one minute.