Modelos y algoritmos para el problema del viajante: Una aplicación en planificación socio sanitaria

Traballo Fin de Grao Modelos y algoritmos para el problema del viajante. Una aplicación en planificación socio sanitaria. Dafne Lucía Arias Vilaboa 2020/2021 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA GRAO DE MATEMÁTICAS Traballo Fin de Grao Modelos y algoritmos para el problema del viajante. Una aplicación en planificación socio sanitaria. Dafne Lucía Arias Vilaboa JULIO 2021 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA Trabajo propuesto Área de Conocimiento: Estadística e Investigación Operativa Título: Modelos y algoritmos para el problema del viajante. Una aplicación en planificación socio sanitaria. Breve descripción del contenido: En este trabajo se estudia el problema clásico del TSP desde dos enfoques. Primeramente desde su relación con la matemática discreta y en particular con los grafos ponderados, por lo cual se hará una revisión de conceptos y resultados en este contexto. El segundo enfoque enmarca el problema del viajante, TSP, dentro de la programación lineal y entera, de modo que se presentará el modelo de programación del TSP y algoritmos de resolución representativos. En la última parte del trabajo se presentan los denominados problemas de rutas de vehículos, VRP, como una extensión del TSP con restricciones adicionales. Se presentarán modelos del VRP con restricciones de capacidad, flota heterogénea y ventanas de tiempo. Esta teoría se aplicará a un problema práctico de la vida real: se considerará un centro de día de la ciudad de Lugo, orientado al cuidado de personas mayores y se va a estudiar la optimización de las salidas programadas de los usuarios con destino a sus domicilios teniendo en cuenta las restricciones relativas a características de movilidad de los usuarios y los distintos tipos de furgonetas disponibles en la empresa. Junto con la teoría anterior, para la resolución del problema se hará uso del lenguaje de modelado AMPL y del solucionador GUROBI. iii Índice general Resumen VII 1. Introducción a la teoría de grafos 1 2. Problema del viajante de comercio 9 2.1. Unpocodehistoria ............................... 9 2.2. Descripción del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2.1. Algunas aplicaciones prácticas del TSP . . . . . . . . . . . . . . . . 15 2.3. Métodosexactos ................................. 16 2.3.1. Ramificación y acotación . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4. Algoritmos heurísticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4.1. Búsquedatabú .............................. 18 3. Problemas de rutas de vehículos 25 3.1. Unpocodehistoria ............................... 25 3.2. Elproblema.................................... 26 3.3. Formulación matemática del problema . . . . . . . . . . . . . . . . . . . . . 27 3.4. VariantesdelVRP ................................ 29 3.5. Métodosderesolución .............................. 31 4. Una aplicación socio sanitaria 33 4.1. Introducción.................................... 33 4.2. Elproblema.................................... 34 4.3. Datosdelproblema................................ 35 4.4. Descripción de las variables y parámetros . . . . . . . . . . . . . . . . . . . 37 4.5. Resolución del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.5.1. Formulación matemática . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.5.2. Método de resolución . . . . . . . . . . . . . . . . . . . . . . . . . . 40 v vi ÍNDICE GENERAL 4.6. Optimización de la distancia . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.6.1. Casode6rutas.............................. 41 4.6.2. Casode5rutas.............................. 44 4.6.3. Casode4rutas.............................. 46 4.6.4. Conclusiónfinal ............................. 46 4.7. Optimización del tiempo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.7.1. Casode6rutas.............................. 47 4.7.2. Casode5rutas.............................. 49 4.7.3. Casode4rutas.............................. 51 4.7.4. Conclusiónfinal ............................. 52 4.8. Resultadofinal .................................. 53 Lista de apéndices 57 A. Tablas de datos 57 A.1. Direcciones de los usuarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 A.2.Distanciaentrenodos .............................. 59 A.3.Tiempoentrenodos ............................... 61 B. Código AMPL 63 B.1.Problema ..................................... 63 B.2. Fichero de los datos de distancias . . . . . . . . . . . . . . . . . . . . . . . . 65 B.3. Fichero de los datos de tiempos . . . . . . . . . . . . . . . . . . . . . . . . . 67 B.4.Ficherodeejecución ............................... 69 Bibliografía 71 Resumen El problema del viajante de comercio y su extensión, el problema de rutas de vehículos, son dos de los problemas de optimización combinatoria de clase NP-duros más estudiados a lo largo del tiempo. Su importancia se debe a que estos problemas cuentan con una gran cantidad de aplicaciones prácticas y el hecho de que sean problemas fáciles de entender pero con una resolución compleja ha motivado su gran investigación. El objetivo de este trabajo es abordar el estudio de ambos problemas. En el primer capítulo se realizará una revisión bibliográfica de conceptos importantes sobre la teoría de grafos. A continuación, en el segundo capítulo se estudia el TSP así como sus múltiples aplicaciones y métodos de resolución, tanto exactos como heurísticos. Por otro lado, en el tercer capítulo se estudia el VRP de manera similar. En el capítulo final, se presenta una aplicación práctica de todo lo expuesto anteriormente. Nos centramos en el estudio de un problema que presenta un centro de día de la ciudad de Lugo y que se puede modelar siguiendo el esquema de una variante del TSP. Para su resolución se hace uso del modelador AMPL y del solucionador Gurobi a través del servidor de optimización NEOS. Abstract The travelling salesman problem (TSP) and its extent, the vehicle routing problem (VRP) are two of the most studied problems in the combinatorial optimization of NP-hard class throughout time. Its importance is due to their wide range of practical applications and the fact that they are easy to understand. However, their complex resolution has motivated research in this field. The aim of this paper is analysing the study of both problems. In the first chapter, important graph theory concepts will be reviewed. In the second chapter, the TSP will be studied alongside with its multiple applications as well as exact and heuristic resolution methods. In the third chapter, the VRP will be studied likewise. In the final chapter, a vii 6CAPÍTULO 1. INTRODUCCIÓN A LA TEORÍA DE GRAFOS Este ejemplo de multigrafo es una motivación de los problemas de minimización de rutas que veremos más adelante. Definición 1.12. Una cadena euleriana de un multigrafo Ges una cadena que contiene cada arista de Gexactamente una vez. Un grafo se llama euleriano si contiene una cadena euleriana cerrada. Teorema 1.13 (Teorema de Euler).Un multigrafo G= (V, E, J)es Euleriano si y sólo si las siguientes afirmaciones son equivalentes: a) G es conexo. b) Cada vértice de G tiene grado par. Demostración. Siguiendo la referencia [19] veremos que estas condiciones son necesarias. Por una parte si el grafo no es conexo no hay ninguna cadena cerrada que recorra todos los nodos y, además, en cualquier cadena cerrada tendremos que el número de aristas incidentes en cada nodo es par. La suficiencia se prueba por inducción en el número de aristas de G: - Para n= 0, un multigrafo con 0 aristas que verifica a) y b) tendrá un único nodo y será euleriano. - Para n6= 0. Supongamos ahora que tenemos un multigrafo Gverificando a) y b) y tal que todos los multigrafos con menos aristas que Gque verifiquen a) y b) son eulerianos. Elijamos ahora un vértice ide Gy empecemos en él una cadena cerrada de aristas de G, que nunca repita dos veces la misma arista; claramente, b) nos asegura que esto será posible. Ahora, eliminemos de Glas aristas de esta cadena. Si ya no queda ninguna arista, entonces tendremos una cadena euleriana. En otro caso, tendremos una o más componentes conexas (subgrafos conexos de G). Para cada nodo hemos eliminado una cantidad par de aristas incidentes en él, con lo que cada componente conexa verificará a) y b) y, por inducción, será euleriana. Ahora podemos crear una cadena euleriana en Gconcatenando las distintas cadenas eulerianas con la cadena de partida, apoyándonos en a). Proposición 1.14. Las anteriores afirmaciones también son equivalentes a la siguiente: El conjunto de aristas de Gse puede dividir en ciclos. Definición 1.15. Un circuito hamiltoniano en un grafo Ges un circuito que contiene a todos los vértices de G(por ser circuito, solo podrá repetir el primer nodo, que coincidirá con el último). Un grafo que contiene un circuito hamiltoniano se llama grafo hamiltoniano. 7 Aunque las cadenas de Euler y los ciclos hamiltonianos tienen definiciones similares son conceptos bastante diferentes. Supongamos que tenemos un grafo Gen el que cada arista tiene asociado un coste, por ejemplo, el tiempo que se tarda en atravesar dicha arista, y tenemos que encontrar un circuito hamiltoniano que minimice el tiempo que se tarda en recorrer todos los nodos del grafo. Nos encontramos ante uno de los problemas más fundamentales en la teoría de grafos, el problema del viajante de comercio (TSP) del que hablaremos extensamente en el siguiente capítulo. Capítulo 2 Problema del viajante de comercio En este capítulo se realiza una revisión bibliográfica sobre el problema del viajante de comercio. Comenzamos con una introducción histórica del problema y a continuación se describirá junto con algunas aplicaciones y métodos de resolución. 2.1. Un poco de historia El problema del viajante del comercio, en inglés Traveling Salesman Problem (TSP), es uno de los problemas de optimización combinatoria NP-duros más importantes, y por tanto, más ampliamente estudiado. El hecho de que sea un problema fácil de entender y a la vez no se haya encontrado una solución general ha hecho que sea uno de los pocos problemas contemporáneos en matemáticas que ya forma parte de la cultura popular. La simplicidad del TSP, junto con su profunda dificultad, lo convierte en una plataforma ideal para desarrollar ideas y técnicas para poder atacar problemas computacionales en general. El origen del problema del transporte no está del todo claro, ya que no existe ningún documento oficial donde aparezca el nombre del creador. El problema aparece por primera vez en un trabajo publicado por Karl Menger en 1932 [30], bajo el nombre de El problema del mensajero, el cual consistía en encontrar el camino de mínima longitud de manera que uniésemos todos los puntos de un conjunto cuya distancia era conocida. Más adelante, en 1949, en Estados Unidos, se publicó el primer informe usando el nombre “traveling salesman problem” como un problema de optimización numérica, [42]. De forma paralela, a pesar de no conocer quien introdujo este problema en el mundo matemático, su principal difusor fue Merrill Flood. Empezó a investigar sobre el mismo en la Universidad de Princenton. A raíz de sus investigaciones, aparecieron nuevos trabajos e investigadores, como por ejemplo Koopmans, que versionó el TSP al “Problema de los 48 9 10 CAPÍTULO 2. PROBLEMA DEL VIAJANTE DE COMERCIO estados” de Hassler Whitney, cuando trataba de encontrar una ruta del autobús escolar en Virginia. En 1948, Jonh Williams convenció a Flood para que difundiese y popularizase el TSP en la RAND Corporation con el objetivo de crear retos intelectuales para motivar el estudio de modelos fuera de la teoría de grafos. Durante esos años la popularidad del problema fue creciendo entre el círculo de científicos de Europa y Estados Unidos, pero no fue hasta 1954 cuando Dantzig, Fulkerson y Johnson lo publicaron en su obra, [13]. En esta, lo expresaron como un problema de Programación Lineal Entera y desarrollaron el “método de los Planos de Corte” para su resolución, con el que resolvieron el problema para 49 ciudades, una por cada estado de Estados Unidos y Washington, creando un recorrido óptimo y probando que no era posible construir otro recorrido mejor. Otro acontecimiento interesante tuvo lugar en 1972, cuando Richard M. Karp demostró que el Problema del ciclo de Hamilton era un problema NP-Completo, y como consecuencia el TSP sería un problema NP-Duro. Más adelante, en 1987, Grötschel, Padberg, Rinaldi y otros matemáticos consiguieron resolver el problema para 2392 ciudades usando el método de Planos de Corte y Ramificación y Acotación. En los 90, Applegate, Bixby, Chvátal y Cook desarrollaron un programa, llamado Concorde TSP Solver [1], con el cual se resolvió el problema de 33810 ciudades en 2005 y el actual récord en 2006 con 85900 ciudades. En la Tabla 2.1 observamos la evolución de las investigaciones aumentando el número de ciudades. Es importante destacar la última solución, debido a que ha sido el TSP más grande que se ha resuelto de forma óptima. Como se ha dicho, en 2006 se encontró una solución para un problema de 85900 ciudades. En este caso era una aplicación del TSP a un problema de minimización del tiempo total que empleaba un láser en la elaboración de chips. Las ciudades eran, en este caso, las ubicaciones de interconexiones y el peso de las aristas señalaban el coste de pasar de una interconexión a otra [1]. En 2016, Hans Mittelmann creó un Servidor NEOS para Concorde, que es capaz de resolver problemas tipo TSP simétricos de forma online, [37]. Actualmente existen varios retos abiertos relativos al TSP, uno de los cuales es el “Monalisa TSP Challenge” que podemos encontrar en [35]. Consiste en encontrar la solución óptima para un TSP de 100000 ciudades, de manera que al unirlas mediante una línea continua representan el dibujo de la Mona Lisa de Leonardo da Vinci, como se puede ver en la Figura 2.1. Encontrar una solución óptima para este TSP establecería un nuevo récord mundial. La mejor solución hasta el momento se encontró en 2012 pero no es la óptima. Para motivar su búsqueda se ofrece una recompensa de $1000 a la persona que 2.1. UN POCO DE HISTORIA 11 consiga mejorarla. Figura 2.1: “Monalisa TSP Challenge” En la página web [34] se pueden encontrar otros ejemplos muy interesantes de arte y figuras construidas mediante la resolución de TSP. AÑO AUTORES NÚMERO CIUDADES 1954 G. Dantzig, R. Fulkerson, S. Johnson 49 1971 M. Held , R.M. Karp 64 1975 P.M. Camerini, L. Fratta, F. Maffioli 67 1977 M. Grötschel 120 1980 H. Crowder, M.W. Padberg 318 1987 M. Padberg , G. Rinaldi 532 1987 M. Grötschel , O. Holland 666 1991 M. Padberg , G. Rinaldi 2392 1994 D. Applegate, R. Bixby, V. Chvátal, W. Cook 7397 1998 D. Applegate, R. Bixby, V. Chvátal, W. Cook 13509 2001 D. Applegate, R. Bixby, V. Chvátal, W. Cook 15112 2004 D. Applegate, R. Bixby, V. Chvátal, W. Cook 18512 2004 D. Applegate, R. Bixby, V. Chvátal, W. Cook, K. Helsgaun 24978 2005 W. Cook, D. Espinoza, M. Goycoolea 33810 2006 D. Applegate, R. Bixby, V. Chvátal, W. Cook 85900 Tabla 2.1: Evolución histórica del tamaño del TSP resuelto. 12 CAPÍTULO 2. PROBLEMA DEL VIAJANTE DE COMERCIO 2.2. Descripción del problema El problema del viajante consiste en encontrar la ruta más corta que debe realizar un comercial de forma que recorra un conjunto de nciudades, empezando y finalizando en la misma, de modo que la única ciudad que visita más de una vez es la de partida. Este problema lo podemos expresar de forma matemática usando la teoría de grafos. El problema se traduciría en encontrar el circuito hamiltoniano de menor peso en un grafo ponderado de nnodos. Los nodos representan las ciudades, las aristas son las conexiones entre las ciudades y los pesos de las aristas representan, por ejemplo, la distancia que las separa o el tiempo que se tarda en llegar de una ciudad a otra. Habitualmente trabajaremos con grafos completos, es decir, cada par de vértices siempre está conectado por una arista, de esta manera, podemos construir la matriz de costes asociada a nuestro problema. En caso de que no existiese el camino entre un par de ciudades, se añade una arista larga para completar el grafo, sin que esta afecte al recorrido óptimo. La matriz de costes es de la forma C=         c11 c12 · · · c1n c21 c22 · · · c2n . . .. . ..... . . cn1cn2· · · cnn         , donde cada coeficiente cij representa el coste de viajar desde la ciudad ia la ciudad j. Observación 2.1.Es interesante diferenciar si el TSP es simétrico o asimétrico. El problema será simétrico si el peso de la arista (i, j)es el mismo que el peso de la arista (j, i), es decir, si nos encontramos en un grafo no dirigido. Si el grafo es dirigido, la matriz de costes no tendrá por qué ser necesariamente simétrica. Observación 2.2.Para un conjunto de nnodos tenemos n!rutas posibles. Aunque lo podemos simplificar, ya que, como es un circuito circular el nodo de partida podría ser cualquiera, entonces tendríamos (n−1)! rutas. Además, si estamos ante un grafo no dirigido, cada arista se podría recorrer en ambos sentidos, reduciendo entonces las rutas a la mitad. Tendríamos finalmente (n−1)! 2rutas posibles. Si el TSP es asimétrico, puede no existir caminos en ambas direcciones, por ejemplo, no todas las calles son de doble sentido. Aún así, el número de rutas crece exponencialmente, ya que, para un TSP de 10 ciudades, existen 10! = 3628800 rutas, pero simplificando tendríamos (10−1)! 2= 181440 rutas diferentes. 2.2. DESCRIPCIÓN DEL PROBLEMA 13 En la Figura 2.2 podemos ver un ejemplo de un TSP, donde se ha buscado el circuito hamiltoniano de menor coste posible. Es decir, el recorrido de menor peso de manera que se unan todos los nodos. En este caso, el coste asociado a ese ciclo hamiltoniano es de 6 unidades. 1 1 1 1 1 1 6 3 5 3 4 4 9 Figura 2.2: Solución de un TSP. En la Figura 2.3 se puede ver, de forma sencilla, la existencia de un camino asimétrico. El recorrido en coche desde el Parlamento de Galicia a Plaza Roja no es el mismo que el recorrido desde Plaza Roja al Parlamento de Galicia. Esto es debido al sentido de las calles que recorremos. (a) Recorrido del Parlamento a Plaza Roja. (b) Recorrido de Plaza Roja al Parlamento. Figura 2.3: Un camino asimétrico entre dos lugares de Santiago. 14 CAPÍTULO 2. PROBLEMA DEL VIAJANTE DE COMERCIO Matemáticamente, definimos el problema del viajante como un sistema de optimización lineal entero. La primera formulación matemática fue realizada en el siglo XIX por W.R. Hamilton y T. Kirkman. Actualmente, las tres formulaciones más comunes son la de DantzigFulkerson-Jonhson (DFJ), la de Miller-Tucker-Zemlin (MTZ) y la formulación basada en el flujo de redes. La principal diferencia entre ellas es la definición de la restricción encargada de que no se formen subciclos. A pesar de ser matemáticamente equivalentes, su rendimiento es diferente ya que estamos ante un problema computacionalmente complejo. De aquí en adelante utilizaremos la formulación MTZ [31] por ser la que tiene mejor rendimiento y obtiene resultados de forma más eficiente a medida que aumentan los nodos del problema. Definición 2.3 (TSP-Formulación MTZ).Sea C= (cij)una matriz de costes, donde cij representa el coste de ir del nodo ial nodo jpara i, j = 1, ..., n, es decir, el peso de la arista (i, j). Se trata de resolver el siguiente problema de optimización: m´ın n X i=1 n X j=1,i6=j xij ·cij (2.1) sujeto a: n X i=1,i6=j xij = 1 j= 1, . . . , n (2.2) n X j=1,i6=j xij = 1 i= 1, . . . , n (2.3) ui−uj+n·xij ≤n−1 2 ≤i6=j≤n(2.4) donde xij =   1,si la ruta incluye la arista del nodo ial j 0,en otro caso yuies una variable entera que representa, para cada nodo, el número de nodos que le precede en el ciclo creado. La ecuación (2.1) es la función objetivo del problema. La ecuación (2.2) garantiza que solo se llegue a cada ciudad una vez. La ecuación (2.3) garantiza que solo se salga de cada ciudad una vez. La ecuación (2.4) obliga a que todas las ciudades se conecten por un solo camino y no varios, además anula la formación de ciclos. 2.2. DESCRIPCIÓN DEL PROBLEMA 15 Observación 2.4.En el caso de que no se pudiese ir de un nodo a otro, esa arista tendría coste infinito. Es decir, si no existe (ˆ i, ˆ j)entonces cˆ iˆ j=∞. Observación 2.5.La diferencia entre la formulación MTZ y DFJ consistiría en cambiar la restricción (2.4) por la (2.5) que definimos a continuación: X i∈SX i6=j,j∈S xij ≤ |S| − 1∀S({1,· · · , n}, card(S)≥2.(2.5) 2.2.1. Algunas aplicaciones prácticas del TSP El problema del viajante ha sido ampliamente estudiado debido a que la mayoría de las investigaciones están motivados por problemas de la vida real. Las aplicaciones del TSP son muy extensas, desde las más simples, como puede ser la optimización de las rutas de los buses escolares que estudió Flood [14] en los años cuarenta o el reparto de mercancías o correo, hasta algunas más complejas como son los problemas de scheduling o la secuenciación del genoma. A continuación vemos algunas aplicaciones del TSP en la vida real: Rutas turísticas y viajes de negocios. Es la aplicación más obvia, puesto que se corresponde directamente con la definición del TSP. Al planear un viaje se busca la manera más eficiente para conocer todos los puntos de interés del lugar que visitamos. Aunque mucha gente no sea consciente, se está haciendo uso del TSP. Problemas de scheduling. Quizás el área de aplicación del TSP más estudiada sea la secuenciación y programación de máquinas. Los problemas de scheduling consisten en organizar un conjunto de operaciones, con una cantidad limitada de recursos. Deben satisfacer una serie de restricciones y el objetivo suele ser la minimización de tiempo. Son problemas que aparecen a menudo en los procesos de producción y organización de las empresas. Redes y telecomunicaciones. El TSP se ha usado para colocar cables de forma estratégica y así suministrar energía para garantizar las conexiones de fibra óptica en los hogares. Red de recolección de residuos. Ha sido una de las primeras aplicaciones prácticas del problema. 22 CAPÍTULO 2. PROBLEMA DEL VIAJANTE DE COMERCIO Iteración K= 1 Se elige invertir la ligadura 3-4 Ligaduras rotas 2-3 y 4-5 Ligaduras agregadas 2-4 y 3-5 Lista tabú 2-4 y 3-5 Nueva solución de prueba 1-2-4-3-5-6-7-1 Distancia 130 Hemos reducido un coste de 8 unidades. Buscamos otra solución vecina que pueda mejorar la solución de prueba actual. Iteración K= 2 Se elige invertir la secuencia 3-5-6 Ligaduras rotas 4-3 y 6-7 (no están en la L.T) Ligaduras agregadas 4-6 y 3-7 Lista tabú 2-4, 3-5, 4-6 y 3-7 Nueva solución de prueba 1-2-4-6-5-3-7-1 Distancia 128 El algoritmo intenta escapar de ese óptimo local buscando nuevas soluciones, aunque empeoren la distancia. Nos movemos hacia el mejor vecino inmediato aunque la distancia sea mayor. En este caso, debido a la limitada cantidad de ligaduras que posee el problema, solamente tenemos dos vecinos inmediatos. En este caso serán: Se elige invertir 6-5-3. Daría como resultado la solución de prueba de la iteración K=2 y el valor de la distancia sería 130. Está prohibido volver a esta solución porque las ligaduras 4-6 y 3-7 están en la lista tabú. Se elige invertir 3-7. Daría como resultado una solución peor, aumentando la distancia a 132. Es la única opción que se puede elegir al descartar la anterior. Iteración K= 3 Se elige invertir la ligadura 3-7 Ligaduras rotas 5-3 y 7-1 Ligaduras agregadas 5-7 y 3-1 Lista tabú 4-6, 3-7, 5-7 y 3-1 Nueva solución de prueba 1-2-4-6-5-7-3-1 Distancia 132 2.4. ALGORITMOS HEURÍSTICOS 23 En esta iteración, como el tamaño de la lista tabú es cuatro, se eliminaron las dos ligaduras más antiguas, en este caso 2-4 y 3-5. Esta nueva solución de prueba tiene cuatro vecinos inmediatos. En este caso serán: Se elige invertir 2-4-6-5-7. Daría como resultado la solución de prueba 1-7-5-6-4-2-3-1 y el valor de la distancia sería 130, un resultado peor que en la solución de prueba de la iteración K=2. Se elige invertir 6-5. Daría como resultado la solución de prueba 1-2-4-5-6-7-3-1 y el valor de la distancia sería 138. Se descarta esta solución porque las ligaduras utilizadas están en la última lista tabú. Se elige invertir 5-7. Daría como resultado la solución de prueba 1-2-4-6-7-5-3-1 y el valor de la distancia sería 126. De momento es la mejor solución de prueba. Se elige invertir 7-3. Daría como resultado la solución de prueba 1-2-4-6-5-3-7-1 y el valor de la distancia sería 128. Se descarta esta solución porque las ligaduras utilizadas están en la última lista tabú. En este momento, solo podríamos decidir entre la primera y la tercera opción. Se elegirá la tercera por ser la mejor solución de las dos. Iteración K= 4 Se elige invertir la ligadura 5-7 Ligaduras rotas 6-5 y 7-3 Ligaduras agregadas 6-7 y 5-3 Lista tabú 5-7, 3-1, 6-7 y 5-3 Nueva solución de prueba 1-2-4-6-7-5-3-1 Distancia 126 En esta última iteración se han eliminado las dos ligaduras más antiguas de la lista tabú, que son 4-6 y 3-7. La nueva solución de prueba 1-2-4-6-7-5-3-1 tiene la mejor distancia entre todas las que hemos calculado. Esta solución es, en realidad, la solución óptima. Las soluciones vecinas inmediatas están descartadas ya por estar las ligaduras en la lista tabú o por ser soluciones ya visitadas. Como no existe otro vecino inmediato, la regla de detención da por finalizado el algoritmo, siendo la solución calculada en la iteración K=4 la óptima. En la figura 2.5 se representa la solución final. 24 CAPÍTULO 2. PROBLEMA DEL VIAJANTE DE COMERCIO 1 2 3 4 5 67 Distancia= 126 24 20 24 6 20 14 18 Figura 2.5: Solución del problema. Capítulo 3 Problemas de rutas de vehículos Tanto los problemas del viajante como los de rutas de vehículos han sido los problemas más estudiados a lo largo del tiempo en Investigación Operativa. Por un lado, en el capítulo anterior, hemos visto que el problema del viajante, TSP, se basa en encontrar la ruta de distancia mínima, partiendo de un lugar y regresando al mismo de modo que un comercial visite a cada uno de sus clientes y regrese a su punto de partida. Por otro lado, el problema de rutas de vehículos, en inglés Vehicle Routing Problem (VRP), tiene como objetivo encontrar el conjunto de rutas, de menor coste, para que la flota de vehículos de una empresa reparta entre sus clientes una mercancía de manera que los repartidores salgan desde el almacén de la empresa, satisfagan todas las necesidades de sus clientes y vuelvan al almacén. Es fácil darse cuenta que ambos problemas están muy relacionados entre sí. El VRP surge como una extensión del TSP para un determinado caso en el que existe una flota de vehículos y la capacidad de los vehículos es limitada, por lo que, sería necesario realizar varias rutas. De la misma manera que con el TPS, encontrar una solución óptima para el VRP se considera un problema NP-duro, ya que, no es posible resolverlo en un tiempo polinómico. Casi siempre se recurre a usar métodos heurísticos o meta-heurísticos, debido a que en problemas de gran tamaño, cómo los de la vida real, suelen dar muy buenos resultados. Entre las diversas referencias sobre el VRP debemos destacar los libros [45], [18] y [9], ya que han sido las principales fuentes de este capítulo. 3.1. Un poco de historia Las primeras referencias y aplicaciones prácticas en el campo del VRP aparecen por primera vez en un artículo escrito por Dantzig y Ramser en 1959 [11], donde tratan de 25 26 CAPÍTULO 3. PROBLEMAS DE RUTAS DE VEHÍCULOS encontrar, planteando una aproximación algorítmica, una solución para un problema de reparto de gasolina. Este problema tenía como objetivo encontrar el conjunto de rutas óptimas para que una flota de camiones abasteciese de gasolina, desde un único depósito, a una gran cantidad de estaciones de servicio. En concreto se encontró la solución para 20 estaciones. Desde que Dantzig y Ramser introdujeron el VRP, muchos matemáticos empezaron a estudiarlo de forma masiva. En 1960, Miller, Tucker y Zemlin [31], dan una formulación formal al TSP con múltiples vehículos, casi similar a la definición de VRP. Más adelante, en 1964, Clarke y Wright [8] mejoraron la aproximación de Dantzig y Ramser utilizando una aproximación “greedy” conocida como algoritmo de ahorros. 3.2. El problema El problema de rutas de vehículos es un problema de optimización combinatoria cuyo objetivo es encontrar el conjunto de rutas de mínimo coste para que una empresa satisfaga las demandas de sus clientes, saliendo y regresando del mismo depósito. Para poder definir un problema de rutas de vehículos necesitamos los siguientes elementos: 1. La existencia de un depósito o conjunto de depósitos. 2. Un conjunto de demandas, es decir, clientes. 3. Una flota de vehículos para su transporte. DEPÓSITO Ruta1 Ruta2 Ruta3 Ruta4 Figura 3.1: Representación de un VRP. 3.3. FORMULACIÓN MATEMÁTICA DEL PROBLEMA 27 En la Figura 3.1 se representa un esquema básico para un VRP. De un depósito central, deben partir una flota de vehículos que tienen que satisfacer las demandas de sus clientes y volver al depósito. El objetivo del VRP es encontrar el conjunto de rutas que minimicen los costes de transporte. 3.3. Formulación matemática del problema A continuación, definimos los conjuntos, parámetros y variables utilizados para poder modelar el problema de forma matemática. V={0,1, . . . , n}es el conjunto de vértices que representan las ubicaciones del problema. N={1, . . . , n}es el conjunto de clientes. i= 0 representa el almacén o depósito. A={(i, j)/i, j ∈V, i 6=j}es el conjunto de aristas que unen los vértices. C= (cij)es la matriz que representa los costes de desplazamiento entre el nodo iy el nodo jcon (i, j)∈A. M= (1, . . . , m)es el conjunto de vehículos de los que disponemos (suponemos que todos generan los mismos costes). Qrepresenta la capacidad máxima de los vehículos (supongamos flota homogénea). qi, i ∈Nrepresenta la demanda de cada cliente, es decir, la cantidad de mercancía que debemos suministrarle. δ+(i) = {j∈V, (i, j)∈A}yδ−(j) = {i∈V, (i, j)∈A}representan los conjuntos de aristas elegidas, de salida y de entrada en los vértices respectivamente. 28 CAPÍTULO 3. PROBLEMAS DE RUTAS DE VEHÍCULOS A partir de la formulación del TSP se construye la siguiente formulación para el VRP. m´ın n X i=0 n X j=0 m X k=1 cij ·xijk (3.1) sujeto a X k∈MX j∈δ+(i) xijk = 1 i∈N(3.2) X i∈δ−(j) xijk −X i∈δ+(j) xjik = 0 j∈N, k ∈M(3.3) X j∈δ+(0) x0jk = 1 k∈M(3.4) X i∈δ−(0) xi0k= 1 k∈M(3.5) X i∈N qiX j∈δ+(i) xijk ≤Q k ∈M(3.6) uik −ujk +n·xijk ≤n+ 1 i, j ∈N, K ∈M(3.7) donde xi,j,k =   1,si se va desde el nodo ial nodo jcon el vehículo k∈M 0,en otro caso yuik ≥0y enteras La ecuación (3.1) representa la función objetivo del VRP. La ecuación (3.2) garantiza que cada cliente solo puede ser visitado una única vez por un único vehículo. La ecuación (3.3) representa la conservación del flujo, es decir, si un vehículo visita a un cliente este vehículo también debe abandonarlo. La ecuación (3.4) garantiza que todos los vehículos tienen que partir desde el almacén. La ecuación (3.5) garantiza que todos los vehículos deben de acabar sus rutas en el almacén. La ecuación (3.6) indica que se tiene que respetar la capacidad máxima de los vehículos. La ecuación (3.7) garantiza que no se formen ciclos indeseados. 3.4. VARIANTES DEL VRP 29 3.4. Variantes del VRP Como hemos comentado antes, el gran interés de los investigadores matemáticos sobre las diferentes variantes del VRP no solo está motivado por su gran dificultad en cuanto a la optimización combinatoria, sino también, por su gran importancia en las aplicaciones prácticas. En esta sección se hace un resumen de las variantes del VRP más importantes, siguiendo las referencias [18] y [22]. Para su clasificación debemos tener en cuenta las características de los depósitos, clientes y la flota de vehículos ya que darán lugar a las diferentes restricciones del VRP. Estas restricciones transformarán el problema original en variantes específicas con un método de resolución propio. Algunas de estas características son: La capacidad limitada de los vehículos. Las características de nuestra flota de vehículos (homogénea o heterogénea, ver Obs. 3.1). Los costes que lleva asociado cada vehículo (por ejemplo, no consumirá lo mismo una moto, un avión o un trailer). La capacidad limitada de los depósitos. La ubicación de los depósitos. Las franjas horarias en las que debe de ser visitado cada cliente. La cantidad de puntos de suministro con los que contamos. La existencia de variables aleatoria (variación diaria del número de clientes, las demandas, ... ). Horarios o entregas periódicas de los clientes. Observación 3.1.Cuando tenemos una flota de vehículos donde todos poseen las mismas características, es decir, la misma capacidad y los mismos costes asociados se dice que tenemos una flota homogénea. Si hay diferencias en las características decimos que tenemos una flota heterogénea. Para resumir, siguiendo el trabajo de Toth y Vigo [45] se representan en la Tabla 3.1, las variantes del VRP más comunes. 30 CAPÍTULO 3. PROBLEMAS DE RUTAS DE VEHÍCULOS NOMBRE DE LA VARIANTE PARTICULARIDAD AVRP (Asymmetric VRP) El coste de desplazamiento entre dos puntos depende del sentido de recorrido. CVRP (Capacitated VRP) El vehículo tiene una capacidad limitada. FRP (Fixed Routes Problem) Una vez se han fijado las rutas no se pueden cambiar durante un tiempo. FSMVRP (Fleet Size and Mix VRP) La flota de vehículos es ilimitada y diversa. Cada tipo de vehículo tiene un coste fijo o costes variables homogéneos. DCVRP (Distance Constrained VRP) La distancia total recorrida o el número de clientes visitados está fijada de antemano. DVRP (Dynamic VRP) Algunos parámetros varían en función del tiempo. MCVRP (Multi Compartment VRP) Los vehículos están organizados mediante compartimentos. Transportan varios productos pero estos deben de ir en compartimentos separados. MDVRP (Multiple Depot VRP) Existe un conjunto de depósitos y los vehículos tienen un depósito origen y depósito destino fijados. OVRP (Open VRP) Algunos vehículos de la flota no necesitan terminar en el depósito. PVRP (Periodic VRP) Hay un tiempo establecido para atender las necesidades de cada cliente. VRPLC (VRP with Length Constraint) Está establecida una distancia máxima para cada ruta. VRPMT (VRP with Multiple Travel) Cada vehículo puede realizar más de una ruta en un cierto período de tiempo. VRPPC (VRP with Precedent Constraints) Existen relaciones de precedencia. Antes de visitar a un cliente, se debe visitar un grupo de ellos. VRPPD (VRP with Pickups and Deliveries) El vehículo debe de recoger mercancía en un punto y llevarla a otro. VRPSD (VRP with Split Delivery) Si se necesitan varios vehículos para satisfacer las demandas de un cliente. La mercancía puede estar dividida en varios vehículos que van por diferentes rutas. VRPSF (VRP with Satellite Facilities) Si existen depósitos intermedios sin necesidad de volver al depósito inicial para recargar mercancía. Tabla 3.1: Algunas variantes importantes del VRP. 3.5. MÉTODOS DE RESOLUCIÓN 31 3.5. Métodos de resolución Como se ha comentado al inicio del capítulo, para resolver el VRP casi siempre se recurre al uso de métodos heurísticos o meta-heurísticos ya que nos permiten encontrar soluciones casi óptimas en tiempos computacionales razonables. Los problemas de rutas de vehículos, en general, tienen un gran historial de implementaciones meta-heurísticas exitosas. A continuación, siguiendo la referencia [18], citaremos y explicaremos brevemente la idea principal de las meta-heurísticas más populares para la resolución de este tipo de problemas. Optimización por colonias de hormigas. Este método meta-heurístico se inspiró en una metáfora natural: “los mecanismos de comunicación y cooperación entre hormigas para encontrar la ruta más corta desde el hormiguero hasta las fuentes de alimento”. En este caso en particular, el medio de comunicación de las hormigas es el rastro de feromonas que desprenden al desplazarse. De esta manera, cada vez que una hormiga encuentra un rastro de feromonas continua por él, intensificando así la cantidad de feromonas del camino. Esto llama la atención de otras hormigas, atraídas por la sustancia, aumentando el número de hormigas que circulan por ese camino. De esta manera se encontraría el camino más corto puesto que el rastro de feromonas se intensificaría en dicho camino. Este algoritmo utiliza el mismo procedimiento. Se construye un conjunto de soluciones iniciales aleatorio y mediante un proceso iterativo se van incorporando elementos en la solución parcial. En cada paso se calcula la cantidad de feromonas, cuantas más feromonas hay, más posibilidades existen de que sea la mejor solución. Las feromonas de las hormigas representan la memoria del algoritmo. Algoritmo de ahorro de Clarke and Wright. Como se comenta anteriormente, este algoritmo fue uno de los primeros métodos heurísticos creados para resolver el VRP y a día de hoy es, sin duda, el algoritmo más utilizado para su resolución. La idea principal del algoritmo es calcular el ahorro que supone unir dos puntos que no están en la misma ruta en la solución factible inicial. Mediante una comparación de ahorros se construye la ruta de menor coste. Algoritmos genéticos. Estos algoritmos nace inspirándose en la teoría de la evolución darwiniana. La idea principal consiste en imitar la manera en la que las especies evolucionan y se adaptan a su entorno, siguiendo la teoría darwiniana de selección natural. Se parte de una población inicial de individuos que representan un conjunto 38 CAPÍTULO 4. UNA APLICACIÓN SOCIO SANITARIA son problemas NP-duros, por lo tanto necesitamos un solucionador potente. AMPL es capaz de expresar en notación algebraica problemas de optimización como los de programación lineal y resolverlos gracias a los diferentes solucionadores de los que dispone. Este programa nos permite representar de forma sencilla problemas de minimización o maximización, dando la función objetivo y las diferentes restricciones. Con ayuda de los solucionadores con los que cuenta resuelve el problema dado. En este caso usaremos el solucionador Gurobi. Para programar en AMPL se puede optar por dos maneras diferentes, mediante la terminal propia, con la licencia académica, o mediante el servidor NEOS, que es un servicio gratuito en Internet, con base en la Universidad de Wisconsin en Madison, que se utiliza para resolver problemas de optimización numérica. El servidor NEOS proporciona acceso a numerosos solucionadores de última generación que se ejecutan en computadoras de alto rendimiento distribuidas por todo el mundo. Uno de los solucionadores más potentes para la resolución de problemas a gran escala es Gurobi. Está especializado en problemas de programación lineal (LP), problemas de programación lineal entera mixta (MILP) y problemas de programación cónica de segundo orden (SOCP). Para su resolución utiliza algoritmos de ramificación y acotación. Gurobi es un solucionador de última generación para programación matemática. 4.5. RESOLUCIÓN DEL PROBLEMA 39 4.5.1. Formulación matemática A continuación vamos a escribir la formulación matemática como un problema de programación lineal: m´ın X i,j∈N∪{0},v∈V,r∈R xi,j,v,r ·cij (4.1) sujeto a X j∈N,v∈V x0,j,v,r = 1 ∀r∈R(4.2) X i∈N,v∈V xi,0,v,r = 1 ∀r∈R(4.3) X j∈N∪{0},v∈V,r∈R xi,j,v,r = 1 ∀i∈N(4.4) xi,i,v,r = 0 ∀i∈N∪ {0}, ∀v∈V, ∀r∈R(4.5) X j∈N∪{0} xi,j,v,r −X j∈N∪{0} xj,i,v,r = 0 ∀i∈N, ∀v∈V, ∀r∈R(4.6) ui,v,r −uj,v,r +n·xi,j,v,r ≤n−1∀i, j ∈N, ∀v∈V, ∀r∈R(4.7) xi,j,1,r = 0 ∀i∈N∪ {0}, ∀j∈ {1, .., s},∀r∈R(4.8) X i∈N,j∈N∪{0} xi,j,1,r ≤7∀r∈R(4.9) X i∈{1,..,s},j∈N∪{0} xi,j,2,r ≤2∀r∈R(4.10) X i∈{1+s,..,n},j∈N∪{0} xi,j,2,r ≤4∀r∈R(4.11) 40 CAPÍTULO 4. UNA APLICACIÓN SOCIO SANITARIA donde xi,j,v,r =   1,si el vehículo vva por la ruta rdesde el nodo ial nodo j 0,en otro caso. La ecuación (4.1) es nuestra función objetivo. La ecuación (4.2) indica que cada ruta debe de empezar siempre en el nodo 0, es decir, el Centro de día. La ecuación (4.3) indica que cada ruta debe de acabar siempre en el nodo 0. La ecuación (4.4) indica que se deben de recoger a todos los usuarios. La ecuación (4.5) indica que no se pueden formar lazos. La ecuación (4.6) refleja la conservación de flujo (sólo se puede llegar y salir de la dirección de un usuario cada vez). La ecuación (4.7) indica que no se pueden formar ciclos improcedentes. La ecuación (4.8) indica que en el vehículo 1no pueden ir sillas. La ecuación (4.9) indica que la capacidad del vehículo 1son 7 usuarios. La ecuación (4.10) indica que en el vehículo 2sólo caben 2sillas. La ecuación (4.11) indica que en el vehículo 2caben a lo sumo 4 usuarios sentados. 4.5.2. Método de resolución Al tratarse de un problema de rutas de vehículos, que es una extensión del TSP, usaremos el método exacto de ramificación y acotación implementado por el solucionador Gurobi. Como ya hemos explicado, para modelar este problema de optimización lineal entera usaremos el programa AMPL, ya que es compatible con los mejores algoritmos de programación lineal conocidos a día de hoy y su gran efectividad viene impulsada por la separación del modelo por un lado, los datos por otro y los comandos a ejecutar por otro. Para trabajar con NEOS necesitamos crear 3archivos: 1. El primer archivo será el modelo, donde se define el problema, la función objetivo y las restricciones. Consultar apéndice B.1 2. En el segundo archivo se proporcionan los datos del problema. En nuestro caso, iremos modificando el número de rutas y a veces quitando nodos para encontrar la solución óptima. Hemos escritos dos ficheros, en el apéndice B.2 se representan los datos de distancias en kilómetros y en el apéndice B.3 se representan los datos de tiempo en minutos. 3. En el tercer archivo se proporcionan los comandos a ejecutar, es decir, una vez dado el problema y los datos, se escriben las órdenes de resolución. En el apéndice B.4 se presentan 3 archivos que utilizaremos en función de lo que necesitemos en cada momento. 4.6. OPTIMIZACIÓN DE LA DISTANCIA 41 Los resultados obtenidos son enviados a la dirección de correo electrónico aportada por el usuario, facilitando así su recolección. Antes de continuar, introducimos el concepto de “gap” ya que es un dato muy relevante a la hora de comparar las soluciones obtenidas. El método de ramificación y acotación termina cada iteración con una cota superior, S, y una cota inferior, I, para el valor del objetivo en el óptimo. El textitgap absoluto (absmipgap) representa la diferencia, en valor absoluto, de esas dos cotas. El textitgap relativo (relmipgap) representa el textitgap absoluto dividido por el valor absoluto de la cota superior, es decir, expresado,si lo multiplicamos por cien, en tanto por cien. 4.6. Optimización de la distancia En este apartado modelamos el problema usando los datos relativos a las distancias, medidos en kilómetros. Primero se prueba para el caso de 6 rutas y se van realizando modificaciones. Para comprobar la mejora de los resultados se va aumentando el tiempo de trabajo del solucionador Gurobi. Para la comparación de las soluciones se ha utilizado el tercer fichero del apéndice B.3. ya que esta opción es una combinación de las dos anteriores y nos permite comparar, dando los resultados del gap, como de buenas son las soluciones obtenidas. En las salidas podemos ver el número de variables y restricciones del problema, los nodos explorados en el proceso de ramificación y acotación o el número de veces que se aplica como subrutina el algoritmo del simplex. Por medio de una tabla mostraremos, de forma más visual, la solución obtenida. 4.6.1. Caso de 6 rutas La empresa habitualmente realizaba 6 viajes, por ese motivo empezamos modelando el problema para el caso de 6 rutas. A continuación se explican las salidas recibidas más importantes. Hemos probado con varios tiempos de ejecución hasta llegar a soluciones que merecen la pena. SALIDA 1 DE AMPL, 6 rutas y tiempo 21600s. Presolve eliminates 1140 constraints and 1224 variables. Adjusted problem: 7836 variables: 42 CAPÍTULO 4. UNA APLICACIÓN SOCIO SANITARIA 7524 binary variables 312 linear variables 8150 constraints, all linear; 52044 nonzeros 332 equality constraints 7818 inequality constraints 1 linear objective; 7512 nonzeros. Gurobi 9.1.1: timelim 21600 bestbound 1 threads=4 Gurobi 9.1.1: time limit with a feasible solution; objective 80.6 208519878 simplex iterations 6915385 branch-and-cut nodes absmipgap = 3.42, relmipgap = 0.0424 No basis. No dual variables returned. Interpretación: NoRUTA VEHÍCULO USUARIOS NoUSUARIOS 1 2 0→19 →2→25 →26 →1→9→06 2 1 0→18 →4→12 →11 →23 →13 →06 3 1 0→21 →10 →24 →15 →17 →16 →8→07 4 2 0→22 →3→6→5→7→05 5 2 0→14 →01 6 1 0→20 →01 GAP = 0.0424 TOTAL DE KMS RECORRIDOS: 80.6 Tabla 4.1: Rutas de la salida 1 con 6 rutas y tiempo límite 21600s. SALIDA 2 DE AMPL, 6 rutas y tiempo 28800s. Presolve eliminates 1140 constraints and 1224 variables. Adjusted problem: 7836 variables: 7524 binary variables 4.6. OPTIMIZACIÓN DE LA DISTANCIA 43 312 linear variables 8150 constraints, all linear; 52044 nonzeros 332 equality constraints 7818 inequality constraints 1 linear objective; 7512 nonzeros. Gurobi 9.1.1: timelim 28800 bestbound 1 threads=4 Gurobi 9.1.1: time limit with a feasible solution; objective 80.6 102788813 simplex iterations 3320925 branch-and-cut nodes absmipgap = 3.95, relmipgap = 0.049 No basis. No dual variables returned. Interpretación: NoRUTA VEHÍCULO USUARIOS NoUSUARIOS 1 2 0→19 →2→25 →26 →1→9→06 2 1 0→18 →4→12 →11 →23 →13 →06 3 1 0→21 →10 →24 →15 →17 →16 →8→07 4 2 0→22 →3→6→5→7→05 5 2 0→14 →01 6 1 0→20 →01 GAP = 0.049 TOTAL DE KMS RECORRIDOS: 80,6 Tabla 4.2: Rutas de la salida 2 con 6 rutas y tiempo límite 28800s. Conclusiones: Después de realizar varias pruebas, vemos que nos da las mismas rutas y con un valor del gap bastante pequeño. Se ha intentado conseguir un textitgap de 0.01 pero no ha sido posible ya que se excede el tiempo máximo permitido para la resolución de este problema. Entonces podemos concluir, que si queremos realizar 6 rutas, la mejor solución posible será la representada en las tablas 4.1 y 4.2. El valor mínimo de la función objetivo será 80,6 km. 44 CAPÍTULO 4. UNA APLICACIÓN SOCIO SANITARIA 4.6.2. Caso de 5 rutas En el apartado anterior podemos ver que dos de las rutas dadas sólo llevarían a un usuario. Vamos a ver que ocurre si decidimos reducir una ruta. SALIDA 1 DE AMPL, 5 rutas y tiempo 21600s. Presolve eliminates 950 constraints and 1020 variables. Adjusted problem: 6530 variables: 6270 binary variables 260 linear variables 6796 constraints, all linear; 43370 nonzeros 281 equality constraints 6515 inequality constraints 1 linear objective; 6260 nonzeros. Gurobi 9.1.1: timelim 21600 bestbound 1 threads=4 Gurobi 9.1.1: time limit with a feasible solution; objective 79.2 140310794 simplex iterations 3705334 branch-and-cut nodes absmipgap = 5.2, relmipgap = 0.0788 No basis. No dual variables returned. Interpretación: NoRUTA VEHÍCULO USUARIOS NoUSUARIOS 1 2 0→13 →21 →1→9→23 →05 2 2 0→22 →3→25 →26 →2→24 →06 3 1 0→14 →01 4 1 0→20 →11 →19 →6→5→7→10 →07 5 1 0→18 →4→12 →15 →17 →16 →8→07 GAP = 0.0788 TOTAL DE KMS RECORRIDOS: 79.2 Tabla 4.3: Rutas de la salida 1 con 5 rutas y tiempo límite 21600s. 4.6. OPTIMIZACIÓN DE LA DISTANCIA 45 SALIDA 2 DE AMPL, 5 rutas y tiempo 28800s. Presolve eliminates 950 constraints and 1020 variables. Adjusted problem: 6530 variables: 6270 binary variables 260 linear variables 6796 constraints, all linear; 43370 nonzeros 281 equality constraints 6515 inequality constraints 1 linear objective; 6260 nonzeros. Gurobi 9.1.1: timelim 28800 bestbound 1 threads=4 Gurobi 9.1.1: time limit with a feasible solution; objective 79.2 150832850 simplex iterations 3992759 branch-and-cut nodes absmipgap = 5.13, relmipgap = 0.0648 No basis. No dual variables returned. Interpretación: NoRUTA VEHÍCULO USUARIOS NoUSUARIOS 1 2 0→13 →21 →1→9→23 →05 2 2 0→22 →3→25 →26 →2→24 →06 3 1 0→14 →01 4 1 0→20 →11 →19 →6→5→7→10 →07 5 1 0→18 →4→12 →15 →17 →16 →8→07 GAP = 0.0648 TOTAL DE KMS RECORRIDOS: 79.2 Tabla 4.4: Rutas de la salida 2 con 5 rutas y tiempo límite 28800s. 46 CAPÍTULO 4. UNA APLICACIÓN SOCIO SANITARIA Conclusiones: Después de realizar varias pruebas, se pude apreciar que el valor del gap en la salida 2 es menor que en la salida 1. Se ha intentado aumentar el tiempo de ejecución para obtener un valor del gap más pequeño pero no ha sido posible ya que se excede el tiempo máximo permitido. Entonces podemos concluir, que realizando 5 viajes se reduce el valor de la función objetivo a 79,2 km. Aunque es una disminución pequeña, se trata de la disminución diaria por lo que finalmente, en el cómputo mensual supone un ahorro interesante. Las mejor solución es la dada en las tablas 4.3 y 4.4. 4.6.3. Caso de 4 rutas Al programar el problema con 4 rutas nos da error, lo cual es obvio, debido a que los usuarios que tienen contratado el servicio de transporte son 23 válidos y 3 inválidos. Tendríamos que hacer mínimo dos viajes con la furgoneta mixta, de manera que fueran 2 inválidos + 4 válidos en un viaje y 1 inválido + 4 válidos en el segundo viaje. Un total de 11 usuarios en la furgoneta mixta. Por otro lado, en la otra furgoneta quedarían por realizar dos rutas, con 7 usuarios en cada una, siendo un total de 14 usuarios. Entonces habríamos llevado a sus domicilios a 11 + 14 = 25 usuarios. En el caso de que algún día uno de los usuarios no acudiese al centro se podrían realizar 4 rutas en vez de 5. Como se puede observar en los apartados anteriores, hay una ruta que lleva a un sólo usuario, el 14. Prescindir de esta ruta sería la forma más sencilla para realizar solamente 4 rutas. 4.6.4. Conclusión final Como acabamos de explicar, el diseño de rutas óptimo sería el de la tabla 4.3, con un valor mínimo de la función objetivo de 79,2 km, siendo el conjunto de rutas de la tabla 4.5 la mejor solución encontrada. NoRUTA VEHÍCULO USUARIOS NoUSUARIOS 1 2 0→13 →21 →1→9→23 →05 2 2 0→22 →3→25 →26 →2→24 →06 3 1 0→14 →01 4 1 0→20 →11 →19 →6→5→7→10 →07 5 1 0→18 →4→12 →15 →17 →16 →8→07 TOTAL DE KMS RECORRIDOS: 79.2 Tabla 4.5: Solución final para la optimización de distancia. 4.7. OPTIMIZACIÓN DEL TIEMPO 47 4.7. Optimización del tiempo En este apartado modelamos el problema usando los datos relativos al tiempo, medidos en minutos. Utilizamos un procedimiento similar al caso de optimización de distancias. Empezamos probando para el caso de 6 rutas y vamos realizando modificaciones y comparaciones de soluciones. Para comprobar la mejora de los resultados se va aumentando el tiempo de trabajo del solucionador Gurobi. Para la comparación de las soluciones se ha utilizado el tercer fichero del apéndice B.3. ya que esa opción es una combinación de las dos anteriores y nos permite comparar, dando los resultados del gap, como de buenas son las soluciones obtenidas. 4.7.1. Caso de 6 rutas La empresa habitualmente realizaba 6 viajes, por ese motivo empezamos modelando el problema para el caso de 6 rutas. A continuación se explican las salidas más importantes recibidas. Hemos probado con varios tiempos de ejecución hasta llegar a soluciones que merecen la pena. SALIDA 1 DE AMPL, 6 rutas y tiempo 21600s: Presolve eliminates 1140 constraints and 1224 variables. Adjusted problem: 7836 variables: 7524 binary variables 312 linear variables 8150 constraints, all linear; 52044 nonzeros 332 equality constraints 7818 inequality constraints 1 linear objective; 7488 nonzeros. Gurobi 9.1.1: timelim 21600 bestbound 1 threads=4 Gurobi 9.1.1: time limit with a feasible solution; objective 154 173640916 simplex iterations 3662456 branch-and-cut nodes absmipgap = 6, relmipgap = 0.039 54 CAPÍTULO 4. UNA APLICACIÓN SOCIO SANITARIA En la Figura 4.4 se representan las rutas de la mejor solución obtenida para la optimización de tiempo. Son las correspondientes a la Tabla 4.10. CENTRO DE DÍA 1 2 3 4 5 6 78 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Figura 4.4: Representación de la mejor solución para la optimización del tiempo. Como se puede observar, las rutas no son las mismas. Para finalizar optaríamos por la optimización de distancias, ya que estas no suelen variar, sin embargo, la optimización del tiempo está sujeta a muchas otras variables, por ejemplo atascos, semáforos, por lo que sería menos precisa. Apéndices 55 Apéndice A Tablas de datos A.1. Direcciones de los usuarios En la Tabla A.1 se representan las direcciones de los usuarios del centro utilizadas para la resolución del problema. Estos datos fueron cedidos por la empresa. Las direcciones son reales ya que el proyecto fue aplicado en la empresa pero los nombres han sido modificados para preservar la identidad de los usuarios. Observación A.1.Los usuarios que usan silla de ruedas se corresponden con los nodos 1, 2 y 3 para facilitar el manejo de datos en el código de programación. 57 58 APÉNDICE A. TABLAS DE DATOS NOMBRE DIRECCIÓN SILLA DE RUEDAS Salida Centro de día Rúa da Pomba, 7 Usuario 1 Maricarmen V. Rúa Consello de Europa, 4 Sí Usuario 2 Ángel A. Ronda das Mercedes, 43 Sí Usuario 3 Aldara A. Rúa Camiño da Vila, 15 Sí Usuario 4 Pepa L. Rúa Flor de Malva, 42 Usuario 5 Andrés G. Ronda das Fontiñas, 97 Usuario 6 Lucía R. Ronda das Fontiñas, 142 Usuario 7 Pablo R. Ronda das Fontiñas, 89 Usuario 8 Alba C. Camiño de Romay, 7 Usuario 9 Noelia C. Rúa Consello de Europa, 4 Usuario 10 Laura A. San Roque, 25 Usuario 11 Paula M. Avenida da Coruña, 369 Usuario 12 Yolanda A. Avenida da Coruña, 427 Usuario 13 Elena A. Marqués de Hombreiro, 94 Usuario 14 Mónica A. Monte Pena Rubia, 12 Usuario 15 María A. Mazoy, 13 Usuario 16 Susa G. Rúa da Aguia, 18 Usuario 17 Marta F. Rúa Tres Marías, 75 Usuario 18 Lourdes C. Rúa Aceroleiro, 13 Usuario 19 Xosé María Rúa General Tella, 4 Usuario 20 Natalia G. Rúa Doña Urraca, 19 Usuario 21 Sara Ronda do Carmen, 19 Usuario 22 María G. Rúa Evaristo Correa Calderón, 8 Usuario 23 Paula A. Rúa Tui, 27 Usuario 24 Marta B. Rúa Adolfo Suárez, 15 Usuario 25 Uxía Coeses Fontemaior, 2 Usuario 26 Pepe G. Coeses Fontemaior, 1 Tabla A.1: Direcciones de los usuarios. A.2. DISTANCIA ENTRE NODOS 59 A.2. Distancia entre nodos En la Tabla A.2 se representan las distancias, medidas en kilómetros, entre las direcciones de los usuarios. Estos datos han sido obtenidos con la aplicación Google Maps a partir de las direcciones dadas en la Tabla A.1. Además se ha empleado una aplicación llamada Map Marker para situar gráficamente los puntos en el plano. 60 APÉNDICE A. TABLAS DE DATOS KM C.D Us.1 Us.2 Us.3 Us.4 Us.5 Us.6 Us.7 Us.8 Us.9 Us.10 Us.11 Us.12 Us.13 Us.14 Us.15 Us.16 Us.17 Us.18 Us.19 Us.20 Us.21 Us.22 Us.23 Us.24 Us.25 Us.26 C.D 0 4.6 5.9 7.1 3.6 6 5.4 6.1 5.5 4.6 4.7 3.8 3.6 2.1 0.65 9.1 5.5 5 1.7 3.8 0.9 3 0.95 2.5 5.4 18 18.5 Us.1 3.2 0 2.1 4.6 8.1 2.9 3 3 4.2 0 2 41 5.6 2.9 3.4 8.5 4.3 4.1 3.9 2.1 2.9 1.8 2.7 2.6 2.7 15 15.5 Us.2 6.1 2.1 0 2.8 8.7 1.2 1.3 1.2 3.5 2.1 1.5 3.7 4.9 5.5 6.6 8.4 3.5 3.7 4.3 2 3.3 2.2 3.2 3.1 2.3 15 15.5 Us.3 4.1 4.9 2.8 0 4.8 1.8 1.8 1.8 3.1 4.9 1.8 4.8 4.6 3.8 4.4 8.7 3.1 3.3 5.1 3.5 3.7 4 3.6 3.9 2.7 16 16.5 Us.4 4,2 6,6 5.1 4,8 0 4,1 4,2 4,1 2,7 6,6 4,1 0,65 0,4 4,6 2,4 5,9 2,7 2,9 0,65 6,1 1,8 3,4 1,8 1,9 3,4 21 21,5 Us.5 6 3,5 1,4 1,6 4 0 0,4 0,03 2,3 3,5 0,5 4 3,8 3 3,5 7,2 2,3 2,5 4,2 2,7 2,9 3,1 2,8 2,6 1,9 18 18,5 Us.6 3,5 3,1 0,95 1,9 4,2 0,27 0 0,3 2,6 3,1 0,65 4,3 4 3,3 3,8 7,5 2,6 2,8 5 3 3,2 3,5 3,1 29 2,2 16 16,5 Us.7 3,2 3,4 1,3 1,6 3,9 0,35 0,23 0 2,3 3,4 0,45 4 3,7 3 3,5 7,2 2,3 2,5 4,2 2,7 2,9 3,1 2,8 2,6 1,9 18 18,5 Us.8 3,4 4,5 3,5 3,2 2,7 2,5 2,5 2,5 0 4,5 2,5 2,7 2,5 3,1 3,9 5,2 0,3 0,55 2,9 2,8 3,4 3,3 3 2,7 1,8 19 19,5 Us.9 3,2 0 2,1 4,6 8,1 2,9 3 3 4,2 0 2 4,1 5,6 2,9 3,4 8,5 4,3 4,1 3,9 2,1 2,9 1,8 2,7 2,6 2,7 15 15,5 Us.10 2,6 3,6 2,2 2,2 4,1 1,2 1,2 1,2 2,4 3,6 0 2,3 2,6 2,3 2,8 6,7 2,2 2,5 2,7 2 2,2 2,8 2,1 1,9 0,9 19 19,5 Us.11 4,5 6,8 5,1 4,8 0,7 4,2 4,2 4,2 2,8 6,8 4,2 0 0,2 4,8 2,4 6 2,8 2,5 1,1 2,7 1,8 3,4 1,7 1,9 3,5 22 22,5 Us.12 4,2 6,6 4,9 4,6 0,45 3,9 3,9 3,9 2,5 6,6 3,9 0,2 0 4,6 2,6 5,7 2,5 2,7 0,95 3,1 2 5,2 1,9 2,1 3,2 22 22,5 Us.13 0,65 2,6 3,8 4,7 4,2 4,7 3,4 4,7 2,6 2,6 2,9 4,5 4,2 0 0,95 9,8 2,6 2,8 2 1,8 1,2 1,1 1,2 1,1 3,3 17 17,5 Us.14 1,6 5,1 8,1 8,8 3,9 7,7 6,3 8,9 6,4 5,1 4 4,2 3,9 2,9 0 9,5 6,3 6,6 1,4 4,1 0,7 3,8 0,8 2 7 19 19,5 Us.15 9,7 9,3 8,4 8,6 5,9 7,4 7,4 7,4 5,2 9,3 7,4 6 5,7 10 11 0 5,3 4,8 6,7 7,7 7,2 11 7,1 7,3 6,1 23 23,5 Us.16 3,4 4,5 3,5 3,2 2,7 2,5 2,6 2,6 0,3 4,5 2,5 2,6 2,5 3,2 4 5,3 0 0,4 3 2,9 3,1 3,3 3 3 1,8 19 19,5 Us.17 3,6 4,6 3,7 3,4 2,8 2,7 2,7 2,7 0,55 4,6 2,7 2,8 2,6 3,3 4,1 4,8 0,4 0 3,1 3 3,5 3,5 3,1 2,9 1,6 18 18,5 Us.18 2 5,5 6,1 5,8 0,65 5,1 4,5 5,1 3 5,5 5,1 0,9 1,4 3,3 1,6 6,9 3,7 3,9 0 2,5 1,3 3 1,4 1,5 3,7 20 20,5 Us.19 2,9 1,4 2,1 3 3,8 1,9 2 2 3,2 1,4 1,6 3,1 4,7 2,7 3,2 7,5 3,2 3,2 3,6 0 2,6 1,5 2,5 2,4 1,7 16 16,5 Us.20 1,6 4 4,4 5,1 1,5 4,4 4 4 3 4 4,4 1,3 2,3 3 0,9 7,8 3,1 3,2 1,1 2,4 0 2,8 0,6 1,3 3,3 19 19,5 Us.21 3 1,4 2,7 4,5 4,6 3,5 2,8 3,6 4,1 1,4 1,8 3,9 6,2 2,8 3,3 8,4 4 4,1 3,7 2 2,7 0 2,6 2,5 2,6 16 16,5 Us.22 1,5 5,4 4,2 2,7 2,5 4,6 4,1 4,7 3,2 5,4 4,6 1,7 1,9 2,8 0,8 7,2 3,3 3,4 1,3 2,4 0,2 3,9 0 1,4 4 19 19,5 Us.23 1,2 2,5 2,8 3,9 2,6 3,2 3,3 3,3 1,9 2,5 2,9 1,8 2,1 0,9 1,1 6,9 2,1 2 1,6 1,1 0,6 1,1 0,5 0 2,6 18 18,5 Us.24 3 4,1 3,1 2,8 3,4 2,1 2,1 2,1 1,8 4,1 2,1 3,5 3,2 2,7 3,3 5,8 1,8 1,5 3 2,4 2,7 2,9 2,6 2,3 0 21 21.5 Us.25 18 15 15 17 20 16 19 18 20,5 15 19 21 20 17 18 24 20 22 20 17 19 18 19 18 21,5 0 0,5 Us.26 18,5 15,5 15,5 17,5 21,5 16,5 19,5 18,5 21 15,5 19,5 21,5 20,5 17,5 18,5 24,5 20,5 22,5 20,5 17,5 19,5 18,5 19,5 18,5 22 0,5 0 Tabla A.2: Tabla de distancias (en kilómetros). A.3. TIEMPO ENTRE NODOS 61 A.3. Tiempo entre nodos En la Tabla A.3 se representan los tiempos, medidos en minutos, entre las direcciones de los usuarios. Estos datos han sido obtenidos con la aplicación Google Maps a partir de las direcciones dadas en la Tabla A.1. Se han recogido entre las 19h y las 20:30h, para que fuesen lo más realistas posibles, ya que el tráfico varía a lo largo del día. 62 APÉNDICE A. TABLAS DE DATOS MIN C.D Us.1 Us.2 Us.3 Us.4 Us.5 Us.6 Us.7 Us.8 Us.9 Us.10 Us.11 Us.12 Us.13 Us.14 Us.15 Us.16 Us.17 Us.18 Us.19 Us.20 Us.21 Us.22 Us.23 Us.24 Us.25 Us.26 C.D 0 11 15 15 5 13 13 13 10 11 15 7 5 5 3 13 10 15 5 8 3 8 3 8 15 18 19 Us.1 9 0 8 11 11 9 9 9 11 0 6 13 13 7 10 18 11 11 12 6 8 4 7 8 8 17 18 Us.2 12 6 0 5 9 3 4 3 8 6 5 11 10 6 8 14 7 8 12 6 8 5 8 9 6 15 16 Us.3 11 13 6 0 5 4 4 4 5 13 5 8 7 9 11 11 5 6 9 8 9 9 9 8 4 16 17 Us.4 6 9 10 8 0 8 8 8 6 9 8 3 1 6 7 9 6 6 2 9 5 10 5 6 6 19 20 Us.5 13 10 4 2 7 0 1 0 5 10 2 8 7 8 11 13 5 6 10 8 9 8 9 8 4 15 16 Us.6 11 8 2 4 8 1 0 1 5 8 4 9 8 9 11 13 6 6 11 8 11 9 10 9 5 17 18 Us.7 10 9 3 3 7 1 1 0 5 9 2 8 7 9 11 12 5 5 10 7 9 8 9 8 4 16 17 Us.8 10 12 8 5 5 5 5 6 0 12 6 6 4 9 11 9 1 2 7 7 9 9 9 8 4 20 21 Us.9 9 0 8 11 11 9 9 9 11 0 6 13 13 7 10 18 11 11 12 6 8 4 7 8 8 17 18 Us.10 9 9 5 5 8 4 4 4 6 9 0 7 8 7 10 12 6 5 9 6 7 8 7 6 3 19 20 Us.11 8 9 10 8 2 8 8 8 5 9 9 0 0 6 8 9 6 6 2 9 5 9 5 6 6 20 21 Us.12 7 10 9 7 1 7 7 8 5 10 8 1 0 5 8 8 5 5 3 9 6 7 6 6 6 19 20 Us.13 2 6 10 10 5 11 11 9 9 6 8 5 5 0 3 13 8 8 6 6 4 2 4 4 9 17 18 Us.14 5 9 12 13 7 13 15 14 13 9 9 8 7 6 0 15 11 11 4 10 2 9 2 6 12 20 21 Us.15 15 20 14 11 9 13 13 13 9 20 14 10 9 13 15 0 9 8 11 14 14 15 14 14 10 22 22 Us.16 10 12 7 6 5 5 6 6 1 12 6 6 5 9 11 9 0 2 7 7 9 8 8 8 4 19 20 Us.17 11 12 7 6 6 6 6 6 2 12 7 7 5 9 11 8 2 0 8 8 9 8 9 8 4 18 19 Us.18 6 11 10 9 2 9 10 10 8 11 10 3 3 7 5 10 7 7 0 7 4 7 4 4 7 19 20 Us.19 8 4 8 8 11 7 7 7 9 4 6 10 10 7 9 14 9 9 10 0 7 4 7 7 6 18 19 Us.20 6 10 12 10 4 11 11 12 8 10 11 5 5 7 3 12 8 8 4 6 0 7 2 4 8 19 20 Us.21 9 4 7 9 12 9 7 8 10 4 6 10 11 7 9 15 10 10 10 5 7 0 6 6 6 16 16 Us.22 5 10 13 11 8 11 13 11 9 10 12 6 6 6 3 14 8 8 4 7 1 8 0 5 9 19 20 Us.23 4 7 9 9 8 9 9 9 7 7 9 6 7 3 4 14 7 6 6 4 1 3 1 0 7 19 20 Us.24 9 11 6 5 6 5 4 5 3 11 5 6 6 8 6 10 3 4 8 6 7 7 7 7 0 17 18 Us.25 19 18 17 16 19 18 19 16 20 18 19 20 20 17 19 25 19 20 19 18 20 19 20 20 20 0 0,5 Us.26 19 19 17 17 20 19 19 17 21 19 20 21 21 18 20 25 20 21 20 19 21 20 21 21 21 0,5 0 Tabla A.3: Tabla de tiempos (en minutos). Apéndice B Código AMPL B.1. Problema En el fichero aquí mostrado escribiremos la formulación del problema que queremos resolver. Indicamos las variables, la función objetivo y las restricciones de nuestro problema. set Nordered;# Conjunto de usuarios (el nodo 0 representa el centro de día). param n:= card(N); # Nú mero de usuarios . param s >=0; # Nú mero de usuarios que usan silla de ruedas ( siempre los colocamos como los s primeros en el fichero de datos ). set R ordered ;# Conjunto de rutas . set Vordered;# Conjunto de veh í culos ( disponemos de 2 veh í culos ; el primero para 7 vá lidos y el segundo para 2 sillas y 4 vá lidos ). param C{i in N union {0} , j in N union {0}} >= 0; # Tiempos. var X{i in N union {0} , j in N union {0} , v in V,r in R}binary;# variable binaria que vale 1 si el veh ículo v en la ruta r va de un centro/usuario i al centro /usuario j. var U{i in N,v in V,r in R} >= 0; # Variable auxiliar que se usa al poner las restricci ón para que no se formen ciclos improcedentes . 63 Bibliografía [1] Applegate, D.L., Bixby, R.E., Chvátal, V. and Cook, W.J. (2006). The Traveling Salesman Problem: A Computational Study. Princeton University Press, cop. [2] Applegate, D.L., Bixby, R.E., Chvátal, V. and Cook, W.J. (2011). The Traveling Salesman Problem. Princeton University Press, cop. [3] Aynos, A. y de Pinto, L. El problema del viajante de comercio: análisis teórico y estrategias de resolución. Universidad Carlos III, Madrid. [4] Bailer-Jones, C.A.L., Rybizki, J., Fouesneau, M., Mantelet, G. and Andrae, R. (2018) Estimating distances from parallaxes IV: Distances to 1.33 billion stars in Gaia. Data relase 2. Astronomical Journal, Vol 156, 58. Max Planck Institute for Astronomy, Heidelberg, Germany. [5] Bazaraa, M., Jarvis, J.J. and Sherali, H. (2011). Programación lineal y flujo en redes. México, Limusa. [6] Calviño, A. (2011). Cooperación en los problemas del viajante (TSP) y de rutas de vehículos (VRP): una panorámica. Tesis del Máster Interuniversitario en Técnicas Estadísticas. Universidad de la Coruña, Universidad de Santiago de Compostela y Universidad de Vigo. [7] Campos Laclaustra, J. (1995). Estructuras de datos y algoritmos. Zaragoza, Prensas Universitarias de Zaragoza. [8] Clarke, G. and Wright, J.R. (1964). Scheduling of Vehicle Routing Problem from a Central Depot to a Number of Delivery Points. Operations Research, Vol 12, 568-581. [9] Cordeau, J.F., Laporte, G., Savelsbergh, M.W.P and Vigo, D. (2007). Transportation. HandBooks in Operations Research and Management Science. Vol 14, 367-428. Amsterdam, Elsevier. 71 72 BIBLIOGRAFÍA [10] Dantzig, G.B. (1963). Linear Programming and Extensions. Pricenton, Pricenton University Press. [11] Dantzig, G.B. and Ramser, J.H. (1959). The Truck Dispatching Problem. Management Science, Vol 6, n.1, 80-91. [12] Dantzig, G.B., Fulkerson, D.R. and Johnson, S.M. (1954). On a linear programming combinatorial approach to the traveling-salesman problem. Operations Research, Vol 7, 58-66. [13] Dantzig, G.B., Fulkerson, D.R. and Johnson, S.M. (1954). Solution of a large scale traveling salesman problem. Operations Research, Vol 2, 393-410. [14] Flood, M.M. (1956). The traveling salesman problem. Operations Research, Vol 4, 61-75. [15] Flores Cabezas, X.A. (2014). Problemas del Milenio: P vs NP. Revista de divulgación. Asociación Amarum, Vol 1, 1-15. [16] Fourer, R., Gay, D. and Kernighan, B. (2003). AMPL. A modeling language por mathematical programming. Canada, Thomson Learning. [17] García, J.J., Hontoria, E. and Aleksovski, D. (2015). El problema del viajante de comercio: Búsqueda de soluciones y herramientas asequibles. Revista electrónica de comunicaciones y trabajos de ASEPUMA. Vol 16, 117-133. [18] Golden, B., Raghavan, S. and Wasil, E. (2008). The vehicle routing problem: latest advances and new challenges. New York, Springer. [19] González Diaz, J. (2020). Apuntes de la materia Programación Lineal e Enteira. Curso 2020-2021. Universidad de Santiago de Compostela. [20] Gutin, G. and Punnen, A. (2007). The traveling salesman problem and its variations. New York, Springer. [21] Hillier, F.S. and Lieberman, G.J. (2010). Introducción a la investigación de operaciones. México, Mc Graw Hill. Novena edición. [22] Irnich, S., Toth, P. and Vigo, D. (2014). Chapter 1: The Family of Vehicle Routing Problems. Researchgate.net. Artículo disponible en: https://www.researchgate.net/publication/284529903_Chapter_1_The_Family_of _Vehicle_Routing_Problems (Visitada 30 de junio de 2021) BIBLIOGRAFÍA 73 [23] Jungnickel, D. (2012). Graphs, Networks and Algorithms. New York, Springer. [24] Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G. and Shmoys, D.B. (1985). The Traveling Salesman Problem. New York, John Wiley and Sons. [25] Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G. and Shmoys, D.B. (1991). The Traveling Salesman Problem: A guided tour of combinatorial optimization. New York, John Wiley and Sons. [26] Little, J., Murky, K., Sweedney, D. and Karel, C. (1963). An algorithm for traveling salesman problem. Operations Research, Vol 11, 972-989. [27] Manber, U. (1989). Introduction to Algorithms. A Creative Approach. Addison-Wesley. [28] Mencía Castellana, R. (2017). Tesis doctoral: Metaheurísticas para problemas de scheduling con múltiples recursos. Universidad de Oviedo, Dep. Informática. [29] Méndez, I. (2018). Modelización y heurísticas para un problema de planificación de tareas en una empresa de atención a personas dependientes. Tesis del Máster Interuniversitario en Técnicas Estadísticas. Universidad de la Coruña, Universidad de Santiago de Compostela y Universidad de Vigo. [30] Menger, K. (1932). Das botenproblem. Ergebnisse Eines Mathematischen Kolloquiums, Vol 2, 11-12. [31] Miller, C.E., Tucker, A.W. and Zemlin, R.A. (1960). Integer Programming Formulations and Traveling Salesman Problems. Journal of Association for Computing Machinery, Vol 7, 326-329. [32] Moreno Soto, F. (2016). Cómo la naturaleza nos muestra una solución a algunos problemas difíciles: el recocido simulado. Números: Revista de Didáctica de las Matemáticas. http://www.sinewton.org/numeros. ISSN: 1887-1984. Vol 92, julio 2016, 35-48. [33] Página web oficial de AMPL: https://ampl.com/ (Visitada 23 de junio de 2021) [34] Página web de Arte mediante la resolución de TSP: https://www2.oberlin.edu/math/faculty/bosch/tspart-page.html (Visitada 27 de junio de 2021) [35] Página web del Monalisa TSP Challenge: http://www.math.uwaterloo.ca/tsp/data/ml/monalisa.html (Visitada 21 de junio de 2021) 74 BIBLIOGRAFÍA [36] Página web oficial de NEOS: https://neos-server.org/neos/ (Visitada 23 de junio de 2021) [37] Página web oficial del Solver CONCORDE: http://www.math.uwaterloo.ca/tsp/concorde/index.html (Visitada 23 de junio de 2021) [38] Página web oficial del solver GUROBI: https://www.gurobi.com/ (Visitada 23 de junio de 2021) [39] Página web del TSP Star Tours: http://www.math.uwaterloo.ca/tsp/star/index.html (Visitada 27 de junio de 2021) [40] Página web de la Universidad de Waterloo: http://www.math.uwaterloo.ca/tsp/index.html (Visitada 28 de junio de 2021) [41] Reinelt, G. (1994). The Traveling salesman: computational solutions for TSP applications. Berlin, Springer-Verlag. [42] Robinson, J.B. (1949). On the Hamiltonian game (a traveling-salesman problem). Rand Corporation. [43] Rocha, L.B., González, C. and Orjuela, J. (2011). Una revisión al estado del arte del problema de ruteo de vehículos. Evolución histórica y métodos de solución. Artículo de revisión. Universidad Districtal José de Caldas. Ingeniería, Vol 2, n 2. [44] Rodríguez Pérez, J. (2012). Caracterización, modelado y determinación de las rutas de la flota en una empresa de rendering. Disponible en: http://bibing.us.es/proyectos/abreproy/70319/fichero/Jorge+Rodriguez+Perez _TRABAJO+FIN+DE+MASTER.pdf [45] Vigo, D. and Toth, P. (2002). The vehicle routing problem. Philadelphia, Society for Industrial and Applied Mathematics.