Synchronization of bus timetabling

Omar Jorge Ibarra-Rojas

doi:10.1016/j.trb.2012.01.006

2012-06-01

202

PRE

Omar Jorge Ibarra-Rojas *

Rios-Solis, Yasmin A.

DOI：10.1016/j.trb.2012.01.006

原文链接

摘要

En 中文

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. (C) 2012 Elsevier Ltd. All rights reserved.

Keyword:

Bus timetabling

Synchronization

Passenger transfer

Bus bunching

NP-hard

Feasible solution space