Abstract

Nowadays, urban transportation networks face challenges such as a rapid increase in urban population, city sprawl, and the use of private vehicles. To guarantee adequate mobility, it is crucial to develop efficient public transportation networks. In this thesis we focus our attention in the design of hub-line location problems (HLLP) to address the problems of designing efficient public transit networks.
First, we present an extension of the HLLP where we integrate gravity models to incorporate demand elasticity into an optimization model. This extension is denoted as the profit-oriented hub line location problem with elastic demand (ED-HLLP). We propose mixed-integer formulations, including a nonlinear mathematical model, and a path-based linear model. The linear formulations assign variables to each possible in the hub-line. A smart enumeration mechanism is provided to create all possible candidate paths. Finally, we also present a computational experience that evaluates the strengths and limits of these formulations.
Second, we introduce a column generation-based algorithm and a hybrid matheuristic that combines column generation with local search to address the ED-HLLP for large-sized problems, to better cope with the combinatorial nature of the number variable of the linear model. Computational experiments show that the proposed approaches are more robust and provide optimal and near-optimal solutions for all problems in our study when compared to the method introduced in ED-HLLP. Furthermore, we conduct a case study in the metropolitan area of Montreal to show the applicability and relevance of the proposed heuristic in a real-world context.
Third, we further extend the ED-HLLP to incorporate additional decisions on the services provided at the hub-nodes. We assume that the demand model is sensitive to both travel times, and quality of service, and our optimization model aims at maximizing the total profit derived from time savings while offering enhanced mobility services. A mixed-integer programming formulation is proposed, and a case study in Montreal is conducted to show the effectiveness of the proposed model.