Diseño de redes de ferrocarril: cobertura por pares vs. cobertura por modos

TRABAJO FIN DE M ´ ASTER M´aster Universitario en Formaci´on del Profesorado de Educaci´on Secundaria Obligatoria, Bachillerato, Formaci´on Profesional y Ense˜nanza de Idiomas y M´aster Universitario en Matem´aticas Dise˜no de redes de ferrocarril: cobertura por pares vs. cobertura por nodos Antonio Jes´us Varo Borrego Tutor acad´emico: Federico Perea Rojas-Marcos Curso 2023-2024 Sevilla, 2 de Febrero de 2024 Resumen En los ´ultimos a˜nos, se ha observado un creciente inter´es y esfuerzo en la construcci´on, mejora y expansi´on de redes de transporte r´apido, impulsado por la creciente demanda de viajes, congesti´on del tr´afico, la necesidad de reducir la contaminaci´on y el consumo de energ´ıa. Este fen´omeno responde a la insostenibilidad de los combustibles f´osiles en el transporte personal. Sin embargo, el dise˜no de estas redes presenta desaf´ıos considerables. Las infraestructuras son dif´ıciles de modificar, y la participaci´on de diversos agentes, como pol´ıticos, ciudadanos e ingenieros provocan una dificultad a˜nadida para resolver el problema. Los dise˜nos urban´ısticos de las ciudades tienen un impacto sobre la planificaci´on de la red al igual que la red sobre el desarrollo urban´ıstico de la ciudad, esto hace que sea importante un buen estudio. Las inversiones en estas redes son muy altas, por lo que hay que definir muy bien los objetivos que se quieren alcanzar basados en las necesidades de la poblaci´on y todo lo que rodea la construcci´on de una red de transporte r´apido. Es por ello que se buscan modelos matem´aticos cada vez m´as cercanos a la realidad, aunque esto conlleva una superior complejidad computacional que en muchos casos no es posible solventar. Los objetivos mas habituales dentro de la literatura en este campo son el maximizar la poblaci´on cubierta por las estaciones y el de maximizar la cobertura de la demanda origendestino, entre otros. Para llegar a estos objetivos se plantean diversos modelos algor´ıtmicos, entre ellos los modelos de programaci´on lineal entera que ser´an la base de los modelos planteados en este trabajo. En este Trabajo de Fin de M´aster propondremos dos modelos, el modelo 1 buscar´a la maximizaci´on de la cobertura de la demanda origen-destino cubierta por la red. El modelo 2, tendr´a como funci´on objetivo el maximizar la poblaci´on cubierta por las estaciones. Tambi´en se propondr´a una modificaci´on del modelo 2 con el fin de obtener distintas redes en poco tiempo. Posteriormente, tomaremos datos experimentales con el objetivo de comprobar el comportamiento de cada uno de los modelos, tanto en t´erminos de la bondad de la soluci´on, como en t´erminos de la complejidad computacional. Se comparar´an las redes obtenidas en cada modelo, observando cuanto se acercan a la red ´optima del otro modelo en t´erminos de la funci´on objetivo. El principal objetivo es que el modelo d´e la mejor soluci´on posible, en t´erminos de la cobertura de la demanda origen-destino, en un tiempo razonable. Abstract In recent years, there has been growing interest and effort in the construction, improvement, and expansion of rapid transit networks, driven by increasing travel demand, traffic congestion, the need to reduce pollution, and energy consumption. This phenomenon is a response to the unsustainable nature of fossil fuels in personal transportation. However, the design of these networks bring up significant challenges. These infrastructures are difficult to modify, and the involvement of various stakeholders, including politicians, citizens, and engineers, adds complexity to the problem-solving. City urban designs impact network planning, just as the network influences city development, highlighting the importance of thorough studies. This networks need substantial financial investment, so it is essential to have clear objectives based on population needs, and surrounding factors must be defined in the construction of rapid transit networks. Hence, there is a pursuit of mathematical models that closely represent reality, despite the increased computational complexity that is sometimes impossible to sol- ve. Common objectives in the literature include maximizing station-covered population and maximizing coverage of origin-destination demand. This study will conduct an analysis of solutions, focusing on maximizing the population covered by stations versus maximizing the coverage of origin-destination demand by the network. Two models will be proposed, each targeting one of these objectives. Using experimental data, the performance of each model will be evaluated in terms of computational complexity and solution quality. Network outcomes from each model will be compared to assess how closely they approach the optimal network of the other model in terms of the objective function. The primary goal is for the model to provide the best possible solution in a reasonable amount of time. ´ Indice general 1. Introducci´on 3 2. Dise˜no de Redes 7 2.1. Construcci´on de la red . . . . . . . . . . . . . . . . . . . . . . 8 2.1.1. Objetivos ......................... 9 2.1.2. Localizaci´on de redes de transporte r´apido: modelos .......................... 13 3. Modelos para el dise˜no de Redes 16 3.1. Modelo1.............................. 16 3.1.1. Datos y notaci´on . . . . . . . . . . . . . . . . . . . . . 17 3.1.2. Variables.......................... 17 3.1.3. Funci´on objetivo y restricciones . . . . . . . . . . . . . 18 3.2. Modelo2.............................. 20 3.2.1. Datos y notaci´on . . . . . . . . . . . . . . . . . . . . . 20 3.2.2. Variables.......................... 21 3.2.3. Funci´on objetivo y restricciones . . . . . . . . . . . . . 21 3.2.4. Modificaci´on del modelo 2 . . . . . . . . . . . . . . . . 21 3.2.5. PostModelo........................ 22 1 4. Entorno tecnol´ogico 24 4.1. AMPL............................... 24 4.1.1. Solver ........................... 27 4.2. Python............................... 28 5. Resultados experimentales 29 5.1. An´alisis por nodos . . . . . . . . . . . . . . . . . . . . . . . . 37 6. Conclusiones 40 6.1. Dificultades encontradas . . . . . . . . . . . . . . . . . . . . . 41 7. Anexos 43 7.1. C´odigos empleados . . . . . . . . . . . . . . . . . . . . . . . . 43 7.1.1. Generaci´on de datos en Python . . . . . . . . . . . . . 43 7.2. ModelosAMPL.......................... 46 7.2.1. Modelo1 ......................... 46 7.2.2. Modelo 2 modificado . . . . . . . . . . . . . . . . . . . 47 2 Cap´ıtulo 1 Introducci´on En los ´ultimos a˜nos, se ha dedicado mucho esfuerzo a la construcci´on, mejora o expansi´on de las redes de transporte r´apido. Este fen´omeno est´a motivado por el aumento en la demanda de viajes, la congesti´on del tr´afico en las ciudades, la creciente longitud de los trayectos, la necesidad de reducir el consumo de energ´ıa y la contaminaci´on [Gendreau et al. (1995)], adem´as de la insostenibilidad del consumo de combustibles f´osiles de los transportes personales. Este dise˜no de redes se encuentra muchas dificultades o problemas a tratar, debido a que estas infraestructuras no son de f´acil modificaci´on y que hay muchos agentes involucrados. Dentro de estos agentes tenemos el factor humano, donde encontramos los pol´ıticos, ciudadanos, ingenieros..., generando un conflicto de intereses entre ellos. Otro agente que encontramos son los dise˜nos urban´ısticos de la ciudad y el impacto que tendr´a esta red sobre ´el. A la hora de construir una nueva red de transporte r´apido es importante prestar especial atenci´on a la inversi´on necesaria en el proceso de construcci´on debido a su elevado coste y que, como hemos dicho antes, estas infraestructuras no pueden modificarse f´acilmente en un corto plazo. Esto hace que en ciudades 3 donde ya tienen una red, su principal inversi´on radica en la construcci´on de nuevas l´ıneas que mejoren la red ya existente. Finalmente, tambi´en encontramos el agente matem´atico que para abordar el problema con la mayor exactitud necesitar´a de gran n´umero de restricciones, lo que complica mucho el modelo. Esto se ver´a con mayor detenimiento en los cap´ıtulos posteriores. Esta dificultad provoca que, en muchos casos, no sea realista la aplicaci´on directa de los modelos matem´aticos. Algunos autores [Laporte et al. (2011b)] han observado con el an´alisis de las redes existentes y planificadas que los organizadores de los proyectos de redes de transporte r´apidos utilizan poco o nada la investigaci´on operativa. En el Cap´ıtulo 2 veremos como se ha tratado este problema con los distintos modelos encontrados en la literatura. Para ello ser´a necesario introducir unas nociones previas: Teor´ıa de grafos. La principal herramienta que se utiliza a la hora del dise˜no de redes es la teor´ıa de grafos. Un grafo G(N, A) es un conjunto finito de objetos llamados nodos (N) y aristas (A) que unen pares de estos nodos, esta uni´on representa una relaci´on binaria entre los elementos. Esta uni´on puede ser dirigida o no dirigida, seg´un si la relaci´on es rec´ıproca o no. A estas aristas se les puede asignar un valor num´erico o pesos, que seg´un el contexto describir´an distintos valores como costes, distancias, capacidad... Optimizaci´on combinatoria. Para la resoluci´on de estos problemas de redes es necesario tener conocimientos de optimizaci´on combinatoria. ´ Esta se centra en encontrar la mejor soluci´on dentro del conjunto de soluciones factibles. Depen- 4 Figura 2.1: Ejemplos de dise˜nos de rueda y de estrella. Fuente: [Laporte et al. (1997)] Figura 2.2: Ejemplos de dise˜nos “U and cross” y de circunferencia. Fuente: [Laporte et al. (1997)] Figura 2.3: Ejemplos de dise˜nos de cuadr´ıcula y triangular. Fuente: [Laporte et al. (1997)] 11 Muchos de los estudios actuales analizan las redes en t´ermino de robustez ante la presencia de fallos ya sean fortuitos o provocados. Debido a esto se ha visto aumentado el inter´es del conocimiento de las propiedades estructurales de los sistemas, tomando la teor´ıa de grafos como herramienta para estudiar estas propiedades desde un punto de vista m´as abstracto. Alguno de estos indicadores son mencionados por [Laporte et al. (2015)], el coeficiente de agrupamiento C y la longitud del camino caracter´ıstico L. Para ello, dado el grafo, toma dij como la distancia topol´ogica entre dos v´ertices (el menor n´umero de aristas para ir de un v´ertice al otro). C=3×n´umero de tri´angulos n´umero de tripletas conectadas. Se entiende como tripletas a tres v´ertices donde al menos uno de ellos est´a conectado a los otros dos, y tri´angulo a tres v´ertices donde cada uno est´a unidos directamente a los otros dos. L=1 |V|(|V| − 1) X i=j dij. Esta expresi´on de la distancia media del camino m´as corto (longitud del camino caracter´ıstico), se puede adaptar a una red m´etrica. Para ello reemplazaremos esta expresi´on por una de la eficiencia global y local, ver [Latora y Marchiori (2001)]. Eg(G) = 2 |V|(|V| − 1) X i<j 1 dij yEl(G) = 1 |V|X vi∈V Eg(Gi), donde Gies el subgrafo de los vecinos de vi. 12 2.1.2. Localizaci´on de redes de transporte r´apido: modelos Los proyectos de construcci´on de las redes de transporte r´apido se pueden clasificar en tres grupos: La planificaci´on de una primera l´ınea. La planificaci´on de varias l´ıneas simult´aneas desde cero. Ampliaci´on de una red ya existente. Localizaci´on de una l´ınea El problema de localizaci´on de una l´ınea en un sistema de tr´ansito r´apido se basa en buscar los caminos y las estaciones id´oneas. Desde el punto de vista de la teor´ıa de grafos, el problema consiste en seleccionar el camino entre dos nodos eligiendo nodos intermedios que se tomar´an como estaciones, optimizando el objetivo sujeto a ciertas restricciones. Esto lo observamos cuando nuestra red se encuentra sobre la superficie, pues las conexiones est´an sujetas al urbanismo propio de cada ciudad, mientras que en las construcciones de redes subterr´aneas podemos tomar un enfoque de red continua. El primer intento real de resolver este problema lo podemos encontrar en [Dufourd et al. (1996)] teniendo en cuenta una distancia m´axima y m´ınima entre estaciones y un n´umero m´aximo de ellas, con el objetivo de maximizar la poblaci´on cubierta por las estaciones. Posteriormente [Bruno et al. (1998)] propone este mismo problema desde un criterio m´as realista, maximizando la cobertura de viajes que proporciona la l´ınea. Con el fin de buscar m´as realismo en los modelos, muchos autores consideran la presencia de determinados medios de transporte alternativos, como podemos ver en [Laporte et al. (2005)] 13 donde presenta un modelo cuyo objetivo es maximizar la cobertura de la demanda origen-destino, con el transporte privado como principal competidor. Localizaci´on de una red Consideraremos ahora el problema de localizar una red de transporte r´apido desde cero o extender una red ya existente. El primer intento de modelizar y resolver el problema de la red de transporte r´apido la encontramos en [Laporte et al. (2007)], donde da una aproximaci´on computacionalmente tratable dividiendo el problema en tres fases: 1. Seleccionar estaciones claves debido a la gran afluencia de poblaci´on (aeropuertos, hospitales, campus universitarios...) o ´areas muy pobladas alejadas del centro de la ciudad. 2. Conectar las estaciones claves con el n´ucleo principal de la red. 3. Ubicar estaciones intermedias en las rutas de la segunda fase. En este mismo art´ıculo, se presenta un modelo de programaci´on lineal entera cuyo objetivo es maximizar la cobertura de viajes con la presencia de un medio de transporte alternativo. Posteriormente, en 2009, con el objetivo de obtener un modelo que interprete mejor el comportamiento del usuario, [Marin y Garcia R´odenas (2009)] introduce una funci´on “logit” con el fin de distribuir los viajeros entre aquellos que usan el transporte r´apido y aquellos que usan el transporte privado. Para seguir manteniendo la linealidad del problema realizan una interpolaci´on lineal a trozos de la funci´on logit. Algunas de las investigaciones m´as recientes, tratan de valorar la robustez de la red desde el punto de vista de la teor´ıa de juegos [Laporte et al. (2010)] o dando rutas alternativas en caso de interrupci´on en la v´ıa [Laporte et al. (2011a)]. 14 Localizaci´on de estaciones El problema de localizar las estaciones, es distinto si nos encontramos en el caso de construir una l´ınea desde cero, o si estamos en el caso de ampliaci´on de una red existente. En el primer caso, muchas de las localizaciones atraer´an gran volumen de pasajeros y ser´an candidatas a estaciones. Las dem´as estaciones deber´an ser colocadas con la ayuda de herramientas anal´ıticas. Por otro lado, si ya tenemos una red dada, aparece el problema de localizar eficientemente las nuevas estaciones. El objetivo prioritario es atraer tantos viajeros como sea posible, analizando la poblaci´on que vive en un c´ırculo centrado en cada estaci´on. Aunque las distancias andando no son eucl´ıdeas, esta medida de la atractividad de la estaci´on es buena. Como se propone en [Laporte et al. (2005)] se puede tomar una probabilidad de atracci´on de la estaci´on en funci´on de la cercan´ıa y esta no tiene por que ser con la distancia eucl´ıdea, tambi´en puede ser con la distancia Manhattan. Figura 2.4: Estaci´on con zonas de captaci´on. Fuente: [Laporte et al. (2005)] 15 Cap´ıtulo 3 Modelos para el dise˜no de Redes En este cap´ıtulo veremos dos modelos matem´aticos para el dise˜no de redes de transporte r´apido. Estos modelos de localizaci´on son muy complejos computacionalmente en situaciones realistas, por lo que se evaluar´an con bases de datos tratables. Para estos modelos consideraremos, conocidos los tiempos de viaje entre las potenciales localizaciones de las estaciones, que todas las localizaciones pueden ser unidas, las demandas de viajes de cada una de las posibles estaciones a otra y el tiempo de transporte por un medio de transporte alternativo. 3.1. Modelo 1 Este modelo se basa en el descrito en [Laporte et al. (2011a)], y en ´el se buscar´a maximizar la utilidad de la red, en el sentido que sea usada por el mayor n´umero de pasajeros. 16 3.1.1. Datos y notaci´on En primer lugar, tenemos una red subyacente G= (N, A) no dirigida asociada al problema, con N={1, ..., n}el conjunto de posibles localizaciones de estaci´on y A⊆ {(i, j)∈N×N:i=j}el conjunto de posibles conexiones entre las estaciones. Definimos el conjunto W⊆ {(k, l)∈N×N}como el conjunto de pares origen destino. Cada nodo itiene asociado un coste de construcci´on de la estaci´on Ci. Cada arco (i, j) tiene asociado un tiempo de viaje tij y un coste de construcci´on de la conexi´on de Cij. Cada par (k, l)∈Wtiene asociado el tiempo de viaje de kalmediante un medio de transporte alternativo ukl y una demanda de viaje de kalde gkl. Tambi´en tendremos un coste m´aximo de la red Cm´ax. 3.1.2. Variables Todas las variables usadas en este modelo son binarias. Tendremos unas variables que nos permiten decidir qu´e estaciones y conexiones se construyen. ´ Estas son yi= 1 si se construye la estaci´on iyxij = 1 si se construye la conexi´on (i, j). Por otro lado, tenemos una variable fkl ij = 1 que toma valor 1 si la demanda (k, l)∈Wusa el arco de la red (i, j). Esta variable nos permite controlar que el flujo de pasajeros sea equilibrado en cada nodo. Finalmente, una variable zkl = 1 si la demanda (k, l)∈Wes captada por nuestra red. Consideraremos que un par (k, l) es captado por la red si el tiempo que emplea utilizando dicha red es inferior al tiempo que necesitar´ıa utilizando el medio alternativo de transporte ukl. 17 3.1.3. Funci´on objetivo y restricciones El objetivo de nuestro problema ser´a maximizar la demanda captada, es decir, m´ax X (k,l)∈W gklzkl.(3.1) Las restricciones que nos encontramos son: Restricci´on de presupuesto, ya que no disponemos de dinero ilimitado. ´ Esta ser´a que la suma de los costes multiplicados por la variable si se construye estaci´on y conexi´on debe ser menor que el presupuesto Cm´ax: X (i,j)∈A Cijxij +X i∈N Ciyi≤Cm´ax (3.2) Restricciones de dise˜no de la red: xij =xji ∀(i, j)∈A(3.3) xij ≤yi∀(i, j)∈A(3.4) yi≤X j∈N:(i,j)∈A xij +X j∈N:(j,i)∈A xji ∀i∈N(3.5) X i∈N yi≤X (i,j)∈A xij 2+ 1 (3.6) La restricci´on (3.3) nos indica que si se construye una conexi´on tambi´en se ha construido la de sentido inverso, d´andole el car´acter de no dirigido al grafo. La restricci´on (3.4) nos refleja que si se construye una conexi´on, se deben construir las estaciones inicio y fin de esa conexi´on. La restricci´on (3.5) nos asegura que si hemos construido una estaci´on, al menos debe tener una conexi´on con otra estaci´on. Finalmente, tenemos la restricci´on (3.6) basada en la restricci´on de estructura de ´arbol que encontramos en algunos modelos de dise˜nos de redes con l´ıneas como en [Laporte et al. (2011a)] con el fin de obtener al menos una l´ınea principal, pero realizamos una relajaci´on permitiendo subciclos dentro de la red. 18 Restricciones de flujo: estas restricciones est´an dirigidas a que si para ir de kalse pasa por ientonces tiene que entrar y salir de i, y si ies terminal entonces solo entra o solo sale. X j∈N:(i,j)∈A fkl ij −X j∈N:(j,i)∈A fkl ji =                      zkl si i =k −zkl si i =l 0 caso contrario ∀(k, l)∈W, ∀i∈N (3.7) Restricciones de localizaci´on: ´estas se usar´an para relacionar las variables xeycon zyf. Estas restricciones son: 2zkl ≤yk+yl∀(k, l)∈W(3.8) fkl ij +fkl ji ≤xij ∀(i, j)∈A, ∀(k, l)∈W(3.9) X i∈N:(i,l)∈A fkl il ≤yl∀(k, l)∈W(3.10) X j∈N:(k,j)∈A fkl kj ≤yk∀(k, l)∈W(3.11) La restriccion (3.8) nos dice que, si se capta la demanda de kalentonces hay que construir las estaciones kyl. La restricci´on (3.9) nos indica que, si se usa la conexi´on (i, j) o la (j, i), n´otese que no se pueden usar las dos, para ir de kalentonces hay que construir la conexi´on. Finalmente, las restricciones (3.10) y (3.11) nos relacionan la construcci´on de estaci´on con la presencia de flujo en la red, imponiendo que si se construye la estaci´on en el origen o destino del par puede salir o entrar flujo, y por el contrario si no se construye, no puede salir ni entrar flujo. 19 Restricci´on de elecci´on: esta se basar´a en comparar el tiempo de tr´ansito mediante la red creada respecto al medio de transporte alternativo X (i,j)∈A tijfkl ij ≤ukl ∀(k, l)∈W(3.12) En ella se suman los tiempos de transporte de todas las conexiones implicadas en la ruta y se compara con el tiempo del medio de transporte alternativo. 3.2. Modelo 2 Este modelo es una simplificaci´on del modelo 1, en el que para aligerar el coste computacional se eliminan todas las variables y restricciones que involucran el controlar el tr´ansito de la demanda 3.2.1. Datos y notaci´on Al igual que en el modelo 1, tenemos una red subyacente G= (N, A) no dirigida asociada al problema, con N={1, ..., n}el conjunto de posibles localizaciones de estaci´on y A⊆ {(i, j)∈N×N:i=j}el conjunto de posibles conexiones entre las estaciones Cada nodo itiene asociado un coste de construcci´on de la estaci´on Ci, y una poblaci´on cubierta por la estaci´on de hi. Cada arco (i, j) tiene asociado un tiempo de viaje tij, un coste de construcci´on de la conexi´on de Cij y el coste m´aximo de la red Cmax. 20 Finalmente, se ejecuta el archivo .run como el ejemplo de la Figura 4.3 introduciendo el solver elegido, el modelo y conjunto de datos a resolver y los resultados que se desean obtener. Estos resultados se ver´an reflejados en la consola o extra´ıdos en alg´un archivo externo. Figura 4.3: Ejemplo de resoluci´on con AMPL y archivo.run. 4.1.1. Solver Para la resoluci´on de los problemas es necesario elegir el solver a utilizar. Existe una gran variedad de solvers donde cada uno trata el modelo de programaci´on lineal entera de una manera distinta. Por ello elegir el solver adecuado permite obtener soluciones m´as r´apidas. El solver escogido es CBC, ya que es el que mejores resultados ha dado entre los solver libres probados (HiGHS, GCG, scip, CBC). El solver CBC (COIN-OR Branch and Cut) es un solver libre de programaci´on lineal entera que trabaja con el solver CLP (COIN-OR Linear Programming) y la librer´ıa CGL (COIN-OR cut Generator Library). Como 27 su nombre indica, este solver se basa en el m´etodo Branch and Cut de resoluci´on de los problemas lineales enteros. Para ello se har´a uso del solver CLP para resolver el problema lineal y de la librer´ıa CGL para obtener los cortes del algoritmo Branch and Cut. 4.2. Python Python es un lenguaje de programaci´on de alto nivel y de prop´osito general, es decir, su utilidad no se limita a un solo tipo campo de aplicaci´on, lo que le hace ser muy vers´atil a la hora de trabajar con ´el. Entre sus ventajas destaca la legibilidad del c´odigo frente a otros lenguajes del mismo car´acter y la licencia de c´odigo abierto que tiene para gran variedad de plataformas. Aunque es posible trabajar directamente desde la consola, nosotros haremos uso del editor Spyder a trav´es del navegador Anaconda, que da acceso a gran n´umero de editores. Spyder es un editor de c´odigo abierto disponible para gran cantidad de plataformas que permite el lenguaje Python, mostr´andote los resultados en la misma pantalla del editor. Figura 4.4: Ejemplo de ejecuci´on de un c´odigo en Python. 28 Cap´ıtulo 5 Resultados experimentales En este cap´ıtulo se presentar´an los resultados obtenidos a la hora de implementar los modelos 1 y el 2 modificado, posteriormente compararemos los resultados tanto num´ericos como en tiempo de ejecuci´on. Para ello obtendremos datos generados aleatoriamente en Python y compararemos la eficacia de los dos modelos. Los primeros datos que utilizaremos para evaluar los modelos son los siguientes: Nuestra red subyacente (red de posibles estaciones y posibles enlaces) es el grafo completo de 10 nodos, 1 23 4 5 6 7 8 9 10 29 con la matriz de distancias asociada (la generaci´on de estos datos se ha realizado tomando valores aleatorios entre 1 y 1000 y haciendo la matriz sim´etrica con el c´odigo Python del anexo). t=                 0 202 250 293 159 180 211 251 143 170 202 0 51 217 158 30 249 74 53 263 250 51 0 235 27 148 55 221 96 208 293 217 235 0 18 148 37 79 258 175 159 158 27 18 0 97 13 67 107 269 180 30 148 148 97 0 232 191 22 219 211 249 55 37 13 232 0 197 282 23 251 74 221 79 67 191 197 0 164 114 143 53 96 258 107 22 282 164 0 117 170 263 208 175 269 219 23 114 117 0                 Supondremos que el tiempo entre las conexiones por el medio alternativo es el doble que el tiempo de conexi´on directa por nuestra red y el coste de construcci´on de la conexi´on es 20 veces el tiempo entre las conexiones. Tenemos una matriz de demandas Origen-Destino (la generaci´on de estos datos se ha realizado tomando valores aleatorios entre 1 y 10000 con el c´odigo Python del anexo). g=                 0 1533 7457 9514 5108 4948 2322 8624 2858 3971 1952 0 4590 7311 9697 645 1626 4823 239 8270 9534 6489 0 5401 8883 5182 5789 9905 7623 5791 853 4649 2163 0 7093 713 237 5498 335 9059 3929 6306 1647 2489 0 4119 5875 218 3750 6550 9690 1319 2038 3931 967 0 8277 9744 6682 5047 2371 8488 6194 5094 5518 8115 0 1397 209 9735 3260 1279 4619 2502 4368 4260 8608 0 7744 2958 5369 4919 6335 307 2707 1284 9206 7209 0 6888 3886 646 6832 8767 1418 921 4366 3071 2206 0                 Para la obtenci´on de las hiydisumaremos por filas y por columnas la matriz de demandas obteniendo el n´umero de habitantes y n´umero de demandas de ir al sitio i. 30 Supondremos un presupuesto de 20000 u.m. y un coste de apertura de las estaciones de (4085,3891,4092,4386,3535,4779,3281,4396,4088,3216) respectivamente, generados tomando aleatoriamente valores entre 3000 y 5000 con el c´odigo Python del anexo. Aplicando el modelo 1 obtenemos un resultado de la demanda captada por la red de 71174, adem´as obtenemos la red ´optima en un tiempo de 100 segundos. 1 23 4 5 6 7 8 9 10 Por otro lado, con el modelo 2 mejorado evaluando para cada α=k 100 con k= 0 . . . 100 obtenemos 101 redes, pero gran cantidad de ellas se repiten, quedando 4 redes distintas. El tiempo de ejecutar las 101 redes es de 19 segundos y el de eliminar las repetidas 0.01 segundos 1 23 4 5 6 7 8 9 10 Figura 5.1: 0 ≤α≤0.11 1 23 4 5 6 7 8 9 10 Figura 5.2: 0.12 ≤α≤0.58 31 1 23 4 5 6 7 8 9 10 Figura 5.3: 0.59 ≤α≤0.73 1 23 4 5 6 7 8 9 10 Figura 5.4: 0.74 ≤α≤1 Fijando las variables xeyen cada una de las redes obtenidas y evaluando el modelo 1 obtenemos unos resultados de captaci´on de demanda de 54082 para la primera red (Figura 5.1), 69265 para la segunda (Figura 5.2), 68248 para la tercera (Figura 5.3) y 66934 para la cuarta (Figura 5.4). La ejecuci´on del modelo 1 con las variables fijadas ha tenido una duraci´on de 0.25 para cada una de las redes. En la siguiente tabla se indican los resultados obtenidos, adem´as a˜nadiremos una columna con la bondad de estos resultados con la medida RPD1. Red Demanda captada RPD Tiempo Modelo 1 71174 100s 0≤α≤0.11 54082 24.01 % 0.12 ≤α≤0.58 69265 2.68 % 20s 0.59 ≤α≤0.73 68248 4.11 % (c´omputo total) 0.74 ≤α≤1 66934 5.95 % Cuadro 5.1: Resultados obtenidos para 10 estaciones potenciales. 1Relative Percentage Deviation(RPD)= Demanda captada 1−Demanda captada 2 Demanda captada 1 ×100 % 32 La red con mejor cobertura de demanda se acerca mucho al valor ´optimo (69265 viajeros captados, a un 2.68 % de la red ´optima encontrada por el modelo 1) y en un tiempo 5 veces inferior, el c´omputo de todas las redes del segundo modelo, ya que cada una de ella se obtiene en menos de 1 segundo. Sin embargo, el potencial de este modelo 2 modificado reside en problemas con una cantidad de estaciones potenciales mayor, ya que el tiempo de ejecuci´on del modelo modificado no se incrementa tanto como los del modelo 1. Para ver esto, tomaremos unos datos de 26 estaciones potenciales con sus respectivas demandas, tiempos y costes generados aleatoriamente con Python como en los datos anteriores y fijamos el coste m´aximo en 50000 u.m. Con estos datos obtenemos, con el modelo 1, una red con una demanda captada de 845606 en un tiempo de 17400 segundos= 4 horas 50 minutos, resuelto con el solver comercial Gurobi, ya que con el solver libre CBC se supera el l´ımite de tiempo, fijado en 8 horas. La red ´optima se muestra en la Figura 5.5 12 7 9 10 12 1415 161718 21 25 Figura 5.5: Red ´optima del Modelo 1 para 26 estaciones potenciales. 33 Por otro lado, ejecutando el modelo 2 modificado obtenemos y eliminamos las redes repetidas en un tiempo de 45 segundos. Quedando solo 5 redes distintas. Obteniendo la demanda captada por cada una de las redes, obtenemos unos resultados de 252824 para 0 ≤α≤0.1, de 818674 para 0.11 ≤α≤0.34, de 830351 para 0.35 ≤α≤0.55, de 816096 para 0.56 ≤α≤0.79 y de 819976 para 0.8≤α≤1 en un tiempo de computaci´on del modelo 1 con las variables x, y fijadas de 8 segundos para cada red. Lo que nos da un tiempo total de computaci´on del modelo de 45 segundos + 40 segundos= 1 minuto 25 segundos. En la siguiente tabla podemos ver un resumen de los resultados obtenidos, adem´as de la medida de bondad RPD. Red Demanda captada RPD Tiempo Modelo 1 845606 4h 50min 0≤α≤0.10 252824 70.10 % 0.11 ≤α≤0.34 818674 3.18 % 1 min 25 seg 0.35 ≤α≤0.55 830351 1.80 % (c´omputo total) 0.56 ≤α≤0.79 816096 3.48 % 0.8≤α≤1 819776 3.05 % Cuadro 5.2: Resultados obtenidos para 26 estaciones potenciales. Tomamos la mejor red del modelo 2 modificado, es decir 0.35 ≤α≤0.55 y nos queda la red siguiente. 34 12 7 9 10 1415 17 21 25 8 19 23 Figura 5.6: Mejor red del Modelo 2 modificado para 26 estaciones potenciales. Comparando las dos redes resultantes, como observamos en la Figura 5.7, vemos que el modelo 1 tiene 4 conexiones no compartidas (azul), el modelo 2 modificado tiene otras 4 conexiones no compartidas (rojo) y las restantes 8 conexiones son compartidas por las dos redes (negro), por lo que vemos que el resultado es bastante similar. Adem´as, el total de viajes captados con esta red est´a a tan solo un 1.80 % de la red ´optima. 12 7 9 10 12 1415 161718 21 25 8 19 23 Figura 5.7: Comparaci´on de las redes de los dos modelos. 35 Nos podr´ıamos preguntar que ocurrir´ıa si en vez de calcular el modelo cada α=k 100 lo calculamos en intervalos m´as peque˜nos, por ejemplo α=k 1000, probamos con los datos anteriores y de las 1001 redes obtenidas, nos quedamos con las mismas 5, pero ahora con los intervalos del αm´as ajustados ([0,0.106], [0.107,0.348], [0.349,0.550], [0.551,0.793], [0.794,1]), sin embargo, este aumento de la cantidad de redes generadas supone un coste computacional muy alto (450 s), por lo que perdemos la principal ventaja de este modelo, su rapidez sin mejorar la mejor red encontrada con los 101 αdistintos. Por otro lado, podemos ver como se comportan ambos modelos al modificar el presupuesto de construcci´on de la red, tanto de bondad de la soluci´on del modelo 2 modificado, como su utilidad en conforme del tiempo. En la siguiente tabla veremos el resultado ´optimo del modelo 1, el mejor resultado del modelo 2 modificado y la bondad en t´erminos de RPD del resultado del modelo 2 modificado respecto a la del modelo 1, entre par´entesis tendremos los tiempos totales de ejecuci´on de cada uno de los modelos. Presupuesto (Cm´ax) Modelo 1 Modelo 2 modificado RPD 40000 540088 (20720s) 532773 (100+15s) 1.35 % 45000 686886 (18276s) 677022 (80+28s) 1.43 % 50000 845606 (17400) 830351 (45+40s) 1.80 % 55000 1019250 (17442s) 961762 (40+40s) 5.64 % 60000 1182560 (16329s) 805453 (30+48s) 31.88 % 65000 1409630 (8543s) 1051520 (27+75s) 25.46 % 100000 2860240 (2894s) 1916200 (17+90s) 33.00 % 1083319780 (63s) Cuadro 5.3: Resultados obtenidos para 26 estaciones potenciales seg´un presupuesto (tiempos con gurobi el modelo 1 y con CBC el modelo 2). 36 Cap´ıtulo 7 Anexos 7.1. C´odigos empleados 7.1.1. Generaci´on de datos en Python Generaci´on de las t,uyCa # -*- coding: utf-8 -*- """ @author: avaro """ import os import numpy as np def generar_matriz_enteros(tama~no): matriz = np.random.randint(1, 301, size=(tama~no, tama~no)) matriz = np.triu(matriz, k=1) matriz = matriz + matriz.T return matriz def guardar_matriz_en_dat(matriz, ruta_archivo): with open(ruta_archivo, ’w’) as file: # Agregar n´umeros del 1 al tama~no de la matriz en la primera l´ınea file.write("param t:=[*,*]:") for i in range(1, len(matriz) + 1): file.write(f’ {i}’) file.write(":=\n") # Agregar la matriz con sus valores for i, fila in enumerate(matriz): file.write(f’{str(i+1)}’) 43 for valor in fila: file.write(f’ {valor}’) file.write(’\n’) file.write(";\n") def multiplicar_matriz_por_dos(matriz): return matriz * 2 def multiplicar_matriz_por_veinte(matriz): return matriz * 20 if __name__ == "__main__": tama~no_matriz = 10 nombre_archivo = "matriz.dat" nombre_archivo2 = "matriz2.dat" nombre_archivo20 = "matriz20.dat" # Generar matriz de enteros entre 1 y 1000 matriz_resultante = generar_matriz_enteros(tama~no_matriz) # Establecer la diagonal a cero np.fill_diagonal(matriz_resultante, 0) # Obtener la ruta del escritorio escritorio = os.path.join(os.path.expanduser(’~’), ’Desktop’) # Unir la ruta del escritorio con el nombre del archivo ruta_completa = os.path.join(escritorio, nombre_archivo) ruta_completa2 = os.path.join(escritorio, nombre_archivo2) ruta_completa20 = os.path.join(escritorio, nombre_archivo20) # Guardar en formato .dat para AMPL en el escritorio guardar_matriz_en_dat(matriz_resultante, ruta_completa) # Multiplicar la matriz por dos y guardar en un segundo archivo matriz_multiplicada_por_dos = multiplicar_matriz_por_dos(matriz_resultante) guardar_matriz_en_dat(matriz_multiplicada_por_dos, ruta_completa2) # Multiplicar la matriz por veinte y guardar en un tercer archivo matriz_multiplicada_por_veinte = multiplicar_matriz_por_veinte(matriz_resultante) guardar_matriz_en_dat(matriz_multiplicada_por_veinte, ruta_completa20) Generaci´on de g import os import numpy as np def generar_matriz_enteros(tama~no): matriz = np.random.randint(1, 10000, size=(tama~no, tama~no)) #matriz = np.triu(matriz, k=1) matriz = matriz return matriz def guardar_matriz_en_dat(matriz, ruta_archivo): 44 with open(ruta_archivo, ’w’) as file: # Agregar n´umeros del 1 al tama~no de la matriz en la primera l´ınea file.write("param t:=[*,*]:") for i in range(1, len(matriz) + 1): file.write(f’ {i}’) file.write(":=\n") # Agregar la matriz con sus valores for i, fila in enumerate(matriz): file.write(f’{str(i+1)}’) for valor in fila: file.write(f’ {valor}’) file.write(’\n’) file.write(";\n") if __name__ == "__main__": tama~no_matriz = 10 nombre_archivo = "matriz1.dat" # Generar matriz de enteros entre 1 y 1000 matriz_resultante = generar_matriz_enteros(tama~no_matriz) # Establecer la diagonal a cero np.fill_diagonal(matriz_resultante, 0) # Obtener la ruta del escritorio escritorio = os.path.join(os.path.expanduser(’~’), ’Desktop’) # Unir la ruta del escritorio con el nombre del archivo ruta_completa = os.path.join(escritorio, nombre_archivo) # Guardar en formato .dat para AMPL en el escritorio guardar_matriz_en_dat(matriz_resultante, ruta_completa) Generaci´on de las Cs import os import random def generar_lista_aleatoria(n): lista = [f"param Cs:={random.randint(3000, 5000)}"] for i in range(2, n + 1): lista.append(f"{i} {random.randint(3000, 5000)}") return lista n = 10 # Puedes ajustar el valor de n seg´un tus necesidades resultado = generar_lista_aleatoria(n) # Obtener la ruta completa del escritorio escritorio = os.path.join(os.path.expanduser(’~’), ’Desktop’) # Guardar la lista en el archivo coste.dat en el escritorio ruta_archivo = os.path.join(escritorio, ’coste.dat’) 45 with open(ruta_archivo, ’w’) as archivo: for elemento in resultado: archivo.write(elemento + ’\n’) 7.2. Modelos AMPL 7.2.1. Modelo 1 Modelo1.mod reset; param rate; param N; set Sta:={1..N}; set Arc:={i in Sta, j in Sta:i<>j}; set SemiArc:={i in Sta, j in Sta:i<j}; param C_{max}; #Coste maximo param Cs{Sta}; #Coste construccion estacion param Ca{Arc}; #Coste construccion arco param g{Arc}; #Numero de pasajeros Demanda por pares param u{Arc}; #Utilidad transito alternativo param t{Arc}; #Tiempo que tarda en recorrer el arco param h{i in Sta}=sum{(i,j) in Arc} g[i,j]; var y{Sta}binary; #Si se abre la estacion var x{Arc}binary; #Si se usa el arco i,j var f{Arc,Arc}binary; #Si la demanda de i a j pasa por el arco k,l var z{Arc}binary; #Si la demanda de i a j es capturada por nuestra red maximize objetivo: sum{(i,j) in Arc} g[i,j]*z[i,j]; s.t. coste: sum{(i,j) in SemiArc} Ca[i,j]*x[i,j]+sum{i in Sta} Cs[i]*y[i]<=C_{max}; #Dise~no s.t. construccion{(i,j) in Arc}: x[i,j]<=y[i]; s.t. construccion3{(i,j) in Arc}: x[i,j]-x[j,i]==0; s.t. construccion2: sum{i in Sta} y[i]<= (sum{(i,j) in Arc} x[i,j])/2 +1; s.t. construccion4{i in Sta}: y[i]<=sum{(i,j) in Arc} (x[i,j]+x[j,i]); #Conservacion flujo s.t. conservacion{(i,j) in Arc, k in Sta: k<>i and k<>j}: sum{m in Sta: k<>m} f[i,j,k,m]-sum{o in Sta: k<>o} f[i,j,o,k]==0; s.t. conservacion2{(i,j)in Arc}: sum{m in Sta: i<>m} f[i,j,i,m]-sum{o in Sta: i<>o} f[i,j,o,i]==z[i,j]; s.t. conservacion3{(i,j)in Arc}: sum{m in Sta: j<>m} f[i,j,j,m]-sum{o in Sta: j<>o} f[i,j,o,j]==-z[i,j]; #Localizacion s.t. uso{(i,j) in Arc}: 2*z[i,j]<=y[i]+y[j]; s.t. tramos{(i,j) in Arc, (k,l) in Arc}: f[i,j,k,l]+f[i,j,l,k]<=x[k,l]; s.t. tramos2{(i,j) in Arc}: sum{(i,k) in Arc} f[i,j,i,k]<=y[i]; s.t. tramos3{(i,j) in Arc}: sum{(k,j) in Arc} f[i,j,k,j]<=y[j]; 46 #Eleccion modo s.t. eleccion{(i,j)in Arc}: sum{(k,l) in Arc} f[i,j,k,l]*t[k,l]<=u[i,j]; modelo1.run reset; option solver CBC; model MODELO1.mod; data DATOS26.dat; solve; display C_{max}; display x; display y; display {i in Sta:y[i]>=0.9}; display {(i,j) in Arc:x[i,j]>=0.9}; display objetivo; display sum{i in Sta} h[i]*y[i]; display _solve_time; display _total_solve_time; 7.2.2. Modelo 2 modificado Modelo3.mod (Generaci´on de las redes) reset; param N; param rate; set Sta:={1..N}; set Arc:={i in Sta, j in Sta:i<>j}; set SemiArc:={i in Sta, j in Sta:i<j}; param C_{max}; #Coste maximo param Cs{Sta}; #Coste construccion estacion param Ca{Arc}; #Coste construccion arco param g{Arc}; #Numero de pasajeros Demanda por pares param u{Arc}; #Utilidad transito alternativo param t{Arc}; #Tiempo que tarda en recorrer el arco param h{i in Sta}=sum{(i,j) in Arc} g[i,j]; param d{j in Sta}=sum{(i,j) in Arc} g[i,j]; var y{Sta}binary; #Si se abre la estacion var x{Arc}binary; #Si se usa el arco i,j maximize objetivo: sum{i in Sta} (rate*h[i]+(1-rate)*d[i])*y[i]; s.t. coste: sum{(i,j) in SemiArc} Ca[i,j]*x[i,j]+sum{i in Sta} Cs[i]*y[i]<=C_{max}; #Dise~no 47 s.t. construccion{(i,j) in Arc}: x[i,j]<=y[i]; s.t. construccion3{(i,j) in SemiArc}: x[i,j]-x[j,i]<=0; s.t. construccion3b{(i,j) in SemiArc}: x[i,j]-x[j,i]>=0; s.t. construccion6{j in Sta}: y[j]<=sum {(i,j) in Arc} (x[i,j]+x[j,i]); s.t. construccion2: sum{i in Sta} y[i]<= (sum{(i,j) in Arc} x[i,j])/2 +1; Modelo3.run (Obtenci´on de las redes) reset; option solver CBC; model MODELO3.mod; data DATOS26.dat; let rate:=0; for {1..101}{ solve; display rate>>resultado26.txt; display rate; display objetivo; display {i in Sta:y[i]>=0.8}>>resultado26.txt; display {(i,j) in Arc:x[i,j]>=0.8}>>resultado26.txt; let rate:=rate+0.01;} display _solve_time; display _total_solve_time; Modelo1modi.mod (Modelo1 con las variables fijadas) var f{Arc,Arc}binary; #Si la demanda de i a j pasa pro el arco k,l var z{Arc}binary; #Si la demanda de i a j es capturada por nuestra red maximize objetivo2: sum{(i,j) in Arc} g[i,j]*z[i,j]; #Conservacion flujo s.t. conservacionm{(i,j) in Arc, k in Sta: k<>i and k<>j}: sum{m in Sta: k<>m} f[i,j,k,m]-sum{o in Sta: k<>o} f[i,j,o,k]==0; s.t. conservacion2m{(i,j)in Arc}: sum{m in Sta: i<>m} f[i,j,i,m]-sum{o in Sta: i<>o} f[i,j,o,i]==z[i,j]; s.t. conservacion3m{(i,j)in Arc}: sum{m in Sta: j<>m} f[i,j,j,m]-sum{o in Sta: j<>o} f[i,j,o,j]==-z[i,j]; #Localizacion s.t. usom{(i,j) in Arc}: 2*z[i,j]<=y[i]+y[j]; s.t. tramosm{(i,j) in Arc, (k,l) in Arc}: f[i,j,k,l]+f[i,j,l,k]<=x[k,l]; s.t. tramos2m{(i,j) in Arc}: sum{(i,k) in Arc} f[i,j,i,k]<=y[i]; s.t. tramos3m{(i,j) in Arc}: sum{(k,j) in Arc} f[i,j,k,j]<=y[j]; #Eleccion modo s.t. eleccionm{(i,j)in Arc}: sum{(k,l) in Arc} f[i,j,k,l]*t[k,l]<=u[i,j]; Modelo3b.run (Ejecuci´on del modelo1 con las variables fijadas) reset; option solver CBC; 48 model MODELO3.mod; data DATOS26.dat; let rate:=0; solve; display rate; display objetivo; display {i in Sta:y[i]>=0.8}; display {(i,j) in Arc:x[i,j]>=0.8 and i<j}; fix y; fix x; model MODELO1modi.mod; objective objetivo2; solve; display rate; display objetivo2; unfix x; unfix y; display _solve_time; display _total_solve_time; 49 Bibliograf´ıa [Bruno et al. (1998)] Bruno, G., Ghiani, G., & Improta, G. (1998). A multimodal approach to the location of a rapid transit line. European Journal of Operational Research, 104(2), 321-332. [Dufourd et al. (1996)] Dufourd, H., Gendreau, M., & Laporte, G. (1996). Locating a transit line using tabu search. Location Science, 4(1-2), 1-19. [Gendreau et al. (1995)] Gendreau, M., Laporte, G., & Mesa, J. A. (1995). Locating rapid transit lines. Journal of Advanced Transportation, 29(2), 145-162. [Latora y Marchiori (2001)] Latora, V., & Marchiori, M. (2001). Efficient behavior of small-world networks. Physical review letters, 87(19), 198701. [Laporte et al. (1997)] Laporte, G., Mesa, J. A., & Ortega, F. A. (1997). Assessing the efficiency of rapid transit configurations. Top, 5(1), 95-104. [Laporte et al. (2002)] Laporte, G., Mesa, J. A., & Ortega, F. A. (2002). Locating stations on rapid transit lines. Computers & Operations Research, 29(6), 741-759. 50 [Laporte et al. (2005)] Laporte, G., Mesa, J. A., Ortega, F. A., & Sevillano, I. (2005). Maximizing trip coverage in the location of a single rapid transit alignment. Annals of Operations Research, 136, 49-63. [Laporte et al. (2007)] Laporte, G., Mar´ın, ´ A., Mesa, J. A., & Ortega, F. A. (2007). An integrated methodology for the rapid transit network design problem. In Algorithmic Methods for Railway Optimization: International Dagstuhl Workshop, Dagstuhl Castle, Germany, June 20-25, 2004, 4th International Workshop, ATMOS 2004, Bergen, Norway, September 16-17, 2004, Revised Selected Papers (pp. 187- 199). Springer Berlin Heidelberg. [Laporte et al. (2010)] Laporte, G., Mesa, J. A., & Perea, F. (2010). A game theoretic framework for the robust railway transit network design problem. Transportation Research Part B: Methodological, 44(4), 447-459. [Laporte et al. (2011a)] Laporte, G., Marin, A., Mesa, J. A., & Perea, F. (2011). Designing robust rapid transit networks with alternative routes. Journal of advanced transportation, 45(1), 54-65. [Laporte et al. (2011b)] Laporte, G., Mesa, J. A., Ortega, F. A., & Perea, F. (2011). Planning rapid transit networks. Socio-Economic Planning Sciences, 45(3), 95-104. [Laporte et al. (2015)] Laporte, G., & Mesa, J. A. (2015). The design of rapid transit networks. Location science, 581-594. [Marin y Garcia R´odenas (2009)] Mar´ın, ´ A., & Garc´ıa-R´odenas, R. (2009). Location of infrastructure in urban railway networks. Computers & Operations Research, 36(5), 1461-1477. 51 [Vuchic (2005)] Vuchic V.R. (2005) Urban transit operations, planning and economics. Hoboken, New Jersey, Wiley 52