A column-generation-based approach for solving the bus rapid transit route design problem

Abstract

Bus rapid transit systems have been gaining popularity all over the world. They constitute an alternative for urban transportation systems by providing reserved lanes for buses and thus improving transportation times. Nonetheless, there are several intrinsic strategic and operational problems that need to be addressed. In this work we focus on developing mathematical and computational tools to support the problem of designing the routes to be operated on the system and their frequencies. This document is composed of two chapters. In the first chapter, we present the preliminary topics that are required to have a better understanding of the subsequent sections. This chapter is divided into four sections containing topics on convex analysis, Linear, Integer and Combinatorial Optimization, Solution Methodologies and Complexity Theory. In the second chapter, we present the main results of the capstone project in the format of a research article. In particular, we present the literature review, problem definition and a new formulation for the Bus Rapid Transit Route Design Problem. Then, we introduce a column-generation-based approach to solve large-scale instances of the LP relaxation of the formulation and show some computational experiments to test the proposed approach.