Abstract

This thesis develops mathematical programming models which integrate network design (ND) and line frequency setting (LFS) phases. These appear in transport planning studies that extend an existing urban public transportation system (UPTS) and are suitable for underground and rapid transit systems. The ND phase extends the working UPTS, taking as inputs the locations of candidate stretches and stations on the new lines, as well as construction costs which cannot exceed the available infrastructure budget. Regarding the LFS phase, frequencies and vehicles are assigned to functioning and newly built lines, providing that they do not exceed resource capacities and the time horizon. The developed models take into account the type of service patterns that may operate on the lines of the transport system. They include local services, where vehicles halt at every node in the line, and express services, in which vehicles halt at only a subset of nodes in the line. A passenger assignment model allows solving, simultaneously, the ND and LFS phases under a system optimum point of view. The combined model has two variants: one which deals with inelastic demand and another which faces elasticities in demand. The latter originates from changes in the modal choice proportions of travelers and may result from modifications in the public transport system. The former does not take into account competition among several modes of transportation and it is formulated as a mixed-integer linear programming problem. In contrast, the latter allows passengers to travel via two modes of transportation: public transport and private car. It is formulated as a mixed-integer linear bi-level programming problem (MILBP) with discrete variables only in the upper level. In both models, a complementary network is used to model transfers among lines and to reach the passenger¿s origin and/or destination nodes when the constructed UPTS does not cover them. The model with inelastic demand is initially solved by means of the commercial solver CPLEX under three different mathematical formulations for the ND phase. The first two are exact approaches based on extensions of Traveling Salesman Problem formulations for dynamic and static treatment of the line¿s subtours, whereas the last one is an approximation inspired by constrained k-shortest path algorithms. In order to deal with large-sized networks, a quasi-exact solution framework is employed. It consists of three solving blocks: the corridor generation algorithm (CGA), the line splitting algorithm (LSA), and a specialized Benders decomposition (SBD). The LSA and CGA are heuristic techniques that allow skipping some of the non-polynomial properties. They are related to the number of lines under construction and the number of feasible corridors that can be generated. As for the SBD, it is an exact method that splits the original mathematical programming problem into a series of resolutions, composed of two mathematical problems which are easier to solve. Regarding the elastic demand variant, it is solved under the same framework as the specialized Benders decomposition adaptation for solving MILBP, which results from this variant formulation. The inelastic demand variant is applied to two test cases based on underground network models for the cities of Seville and Santiago de Chile. Origin destination trip matrices and other parameters required by the models have been set to likely values using maps and published studies. The purpose of these networks is to test the models and algorithms on realistic scenarios, as well as to show their potentialities. Reported results show that the quasi-exact approach is comparable to approximate techniques in terms of performance. Regarding the elastic demand variant, the model is more complex and can be applied only to smaller networks. Finally, some further lines of research for both modeling and algorithmic issues are discussed.