Synchronization of bus timetabling

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

Transportation Research Part B: Methodological, 2012, vol. 46, issue 5, 599-614

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.

Keywords: Bus timetabling; Synchronization; Passenger transfer; Bus bunching; NP-hard; Feasible solution space (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (40)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261512000070
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:46:y:2012:i:5:p:599-614

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2012.01.006

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().