El problema de diseño de redes de tránsito rápido (metros, cercanías, autobuses en plataforma reservada y cerrada, etc) consiste en, conocida una demanda de movilidad en una zona urbana o metropolitana, determinar las estaciones y las conexiones entre las mismas. El tema suele ser muy complejo, ya que intervienen distintos especialistas (ingenieros, economistas, geólogos, etc.), autoridades y grupos sociales. Los distintos agentes que intervienen en la planificación se pueden agrupar en tres categorías: agencias de transporte, usuarios y empresas (constructoras y explotadoras). Esta gama de agentes a menudo implica la necesidad de tener en cuenta distintos criterios que deben coexistir dentro de un mismo proyecto. Las expectativas son distintas: así como las autoridades representadas por las agencias de transporte desean que la utilidad de las redes sea lo más amplia posible, los usuarios buscan minimizar el tiempo dedicado al viaje, y las empresas tienen como prioridad la optimización de costes de construcción y de operación para maximizar sus beneficios. El método empleado por las constructoras para localizar el trazado de una línea de tránsito rápido consiste en determinar corredores por los que circula el tráfico, unirlos y considerar un pequeño número de alternativas para posteriormente compararlas desde distintos puntos de vista. Los modelos de programación matemática permiten considerar un gran número de opciones y, en particular, algunas que no reproducen los patrones de movilidad existentes pero que resultan ventajosos a los usuarios. En el diseño de redes de metro hay que tener en cuenta que el modo de transito rápido va a competir con otros modos de transporte como son los medios privados y públicos. Normalmente, el usuario escoge el medio que le reporte mayor utilidad, dentro de la cual se pueden considerar distintos atributos: el precio, la seguridad o el confort. No obstante, debido a que el usuario suele realizar el mismo viaje diario, el más importante suele ser el tiempo de recorrido. Por tanto, los problemas de diseño de redes de tránsito rápido son muy complejos al intervenir tanto distintos agentes como la conducta de los usuarios, dando lugar a problemas NP-duros desde el punto de vista computacional. Por otra parte, la construcción de líneas de metro supone un coste muy elevado y no siempre es posible satisfacer completamente la demanda por lo que, incluso recién inauguradas, sufren la congestión y el amontonamiento de pasajeros. Los modelos matemáticos considerados hasta el momento asumen la competencia con otros modos de transporte en condiciones de no congestión. De hecho, la demanda real captada puede variar al degradarse la utilidad de los posibles usuarios debido a la congestión. En este sentido, se pueden clasificar en cuatro grupos los motivos de degradación de la utilidad esperada: i) congestión y amontonamiento en los accesos o en los andenes ii) espera de un segundo, tercer o sucesivos trenes iii) tiempos de parada en las estaciones mayores que los nominales debido a la gran afluencia de viajeros iv) sobreocupación en los vagones. Los efectos de estos motivos suelen aparecer en horas punta, con ocasión de eventos especiales, y cuando ocurren perturbaciones a la operativa nominal. Por otra parte, el intervalo entre dos trenes consecutivos y el tamaño de estos tiene una cota inferior (dos o tres minutos en el mejor de los casos, y de seis a diez vagones), por lo que las condiciones técnicas no permiten una ampliación de la capacidad por hora de la línea. Sin embargo, puede ser interesante, a la hora de realizar un análisis coste/beneficio, efectuar un estudio de la sensibilidad sobre la pérdida de usuarios respecto a la variación en la frecuencia. En áreas metropolitanas densamente pobladas, los estudios empíricos han determinado que la sobreocupación dentro de los vehículos de tránsito ha empeorado cada vez más en los últimos años. El hacinamiento crónico dentro de los vehículos no sólo es causado por la falta de infraestructura física, sino también por la provisión inadecuada de servicios o por una planificación basada en un modelo matemático inadecuado. 2 En este trabajo se va a considerar el problema de la localización del trazado de una línea de tránsito rápido que maximice el número de viajes captados, teniendo en cuenta los distintos efectos de la sobreocupación. A la hora de diseñar la localización de la línea, se van a tener en cuenta los condicionantes anteriormente descritos. El principal objetivo de un sistema de tránsito rápido es mejorar la movilidad de la población. Idealmente, una red debe estar diseñada para proporcionar tiempos de viaje cortos a un elevado número de pasajeros, respetando restricciones técnicas, legislativas y presupuestarias. Para ello, se van a introducir funciones que modelen cada uno de esos efectos. El modelado se va a efectuar mediante programación matemática entera mixta y, dada la complejidad computacional, se realizará una experiencia numérica de tamaño pequeño. The design problem for rapid transit networks (metros, commuter trains, buses on a reserved and closed platform, etc.) consists of knowing a demand for mobility in an urban or metropolitan area, determining the stations and the connections between them. The issue is usually very complex, since different specialists (engineers, economists, geologists, etc.), authorities and social groups are involved. The different agents involved in planning can be grouped into three categories: transport agencies, users and companies (builders and operators). This range of agents often implies the need to take into account different criteria that must coexist within the same project. The expectations are different: just as the authorities represented by the transport agencies want the usefulness of the networks to be as wide as possible, the users seek to minimize the time spent on the journey, and the companies have the optimization of construction and operating costs as a priority to maximize the profits. The method used by construction companies to locate the layout of a rapid transit line consists of determining corridors through which traffic circulates, joining them and considering a small number of alternatives to later compare them from different points of view. Mathematical programming models allow us to consider a large number of options and, in particular, some that do not reproduce existing mobility patterns but are advantageous to users. In the design of metro networks, it must be taken into account that the rapid transit methods will compete with other modes of transportation such as private and public means. Normally, the user chooses the mode that provides the greatest utility, within which different attributes can be considered: price, safety or comfort. However, since the user usually makes the same daily trip, the most important is usually the travel time. Therefore, rapid transit network design problems are very complex, as different agents and user behavior intervene, giving rise to NP-hard models from the computational point of view. On the other hand, the construction of metro lines entails a very high cost and it is not always possible to fully satisfy the demand, which is why, even just inaugurated, they suffer from congestion and overcrowding of passengers. The models considered so far assume competition with other transportation modes under non-congested conditions. In fact, the real demand captured can vary as the usefulness of potential users is degraded due to congestion. In this sense, the reasons for the degradation of the expected utility can be classified into four groups: i) congestion and crowding at the entrances or on the platforms ii) waiting for a second, third or successive trains iii) stop times at the stations greater than nominal due to the large flow of travelers iv) overcrowding in wagons. The effects of these reasons usually appear at peak times, on the occasion of special events, and when disturbances to nominal operations occur. On the other hand, the interval between two consecutive trains and the size of these has a lower limit (two or three minutes in the best of cases, and from six to ten wagons), so the technical conditions do not allow an extension of the hourly capacity of the line. However, it may be interesting, when carrying out a cost/benefit analysis, to carry out a study of the sensitivity of the loss of users with respect to the variation in frequency. In densely populated metropolitan areas, empirical studies have found that overcrowding within transit vehicles has gotten worse in recent years. Chronic overcrowding inside vehicles is not only caused by the lack of physical infrastructure, but also by the inadequate provision of services or by planning based on an inadequate mathematical model. In this work, the problem of locating the layout of a rapid transit line that maximizes the number of trips captured, taking into account the different effects of overcrowding, will be considered. When designing the location of the line, the conditions described above will be taken into account. The 4 main objective of a rapid transit system is to improve the mobility of the population. Ideally, a network should be designed to provide short travel times to a high number of passengers, while respecting technical, legislative and budgetary constraints. To do this, functions that model each of these effects will be introduced. The modeling will be done through integer or mixed-integer mathematical programming and, given the computational complexity, a small numerical experiment will be carried out. Universidad de Sevilla. Doble Máster en MAES-Máster Universitario en Matemáticas (MAES-MUM)