Hybrid algorithm for route design on bus rapid transit systems

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.