Synchronization of bus timetabling

Authors

Omar J. Ibarra-Rojas
Yasmin A. Rios-Solis

Document Type

Journal Article

Publication Date

2012

Subject Area

mode - bus, operations - coordination, operations - scheduling, place - north america, infrastructure - interchange/transfer

Keywords

Bus timetabling, Synchronization, Passenger transfer, Bus bunching, NP-hard, Feasible solution space

Abstract

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.

Rights

Permission to publish the abstract has been given by Elsevier, copyright remains with them.

Comments

Transportation Research Part B Home Page:

http://www.sciencedirect.com/science/journal/01912615

Recommended Citation

Ibarra-Rojas, O.J., & Rios-Solis, Y.A. (2012). Synchronization of bus timetabling. Transportation Research Part B: Methodological, Vol. 46, (5), pp. 599-614.