Hybrid Algorithm for Route Design on Bus Rapid Transit Systems

Jose L. Walteros (), Andrés L. Medaglia () and Germán Riaño ()
Additional contact information
Jose L. Walteros: Centro para la Optimización y Probabilidad Aplicada (COPA), Departamento de Ingeniería Industrial, Universidad de los Andes, Bogotá, Colombia
Andrés L. Medaglia: Centro para la Optimización y Probabilidad Aplicada (COPA), Departamento de Ingeniería Industrial, Universidad de los Andes, Bogotá, Colombia
Germán Riaño: Centro para la Optimización y Probabilidad Aplicada (COPA), Departamento de Ingeniería Industrial, Universidad de los Andes, Bogotá, Colombia

Transportation Science, 2015, vol. 49, issue 1, 66-84

Abstract: In recent years, well-designed bus rapid transit (BRT) systems have become a real alternative to more expensive rail-based public transportation systems around the world. However, once the BRT system is operational, its success often depends on the routes offered to passengers. Thus, the bus rapid transit route design problem (BRTRDP) is the problem of finding a set of routes and frequencies that minimizes the operational and passenger costs (travel time) while simultaneously satisfying the system’s technical constraints, such as meeting the demands for trips, bus frequencies, and lane capacities. To address this problem, we propose a mathematical formulation of the BRTRDP as a mixed-integer program (MIP) with an underlying network structure. However, because of the vast number of routes, solving the MIP via branch and bound is out of reach for most practical instances. Hence, we propose a decomposition strategy that, given a certain set of routes, decouples the route selection decisions from the BRT system performance evaluation. The latter evaluation is done by solving a linear optimization problem using a column generation scheme. We embedded this decomposition strategy in a hybrid genetic algorithm (HGA) and tested it in 14 instances ranging from 5 to 40 stations with different BRT system topologies. The results show that in 8 of 14 problems, the HGA was able to obtain a solution that is provably optimal within 0.20%. Additionally, in 4 of 14 instances, HGA obtained the optimal solution.

Keywords: bus rapid transit systems; public transit network design; bus routing; urban logistics; matheuristics; genetic algorithms (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2013.0478 (application/pdf)

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:inm:ortrsc:v:49:y:2015:i:1:p:66-84

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().