Coordinación y dimensionamiento de flota de drones en problemas TSP a través de Python

Equation Chapter 1 Section 1 Trabajo Fin de Grado Grado en Ingeniería de Tecnologías Industriales Coordinación y dimensionamiento de flota de drones en problemas TSP a través de Python Autor: Francisco Javier Gómez Lozano Tutor: José Miguel León Blanco Dpto. Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2021 iii Trabajo Fin de Grado Grado en Ingeniería de Tecnologías Industriales Coordinación y dimensionamiento de flota de drones en problemas TSP a través de Python Autor: Francisco Javier Gómez Lozano Tutor: José Miguel León Blanco Profesor Contratado Doctor Dpto. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2021 v Agradecimientos A mi familia por su apoyo incondicional. A José Miguel por su total implicación y entrega en el proyecto. Resumen El éxito empresarial se podría resumir a su extremo como la forma de conseguir máximas ganancias minimizando los costes. En el día a día de muchas empresas, esos costes lo forman mayoritariamente aquellos empleados en logística. Con el objetivo de minimizarlos, surgieron dos problemas que hoy en día pueden definirse como clásicos: Traveling Salesman Problem y Vehicle Routing Problem. Una de sus grandes peculiaridades, y el motivo por lo que se han asentado como base de estudio de otros problemas de optimización, es que, a pesar de su fácil comprensión, para dimensiones considerables estos problemas son irresolubles de forma exacta. Es por ello por lo que se emplean diferentes algoritmos de aproximación al óptimo, ya sean propios de estos problemas (heurísticas) como otros de corte genérico (metaheurísticas). Dentro del sector de la distribución, el uso de los drones para el reparto se ha convertido en una de las líneas de trabajo con mayor potencial para revolucionar el sector. Abordaremos la implementación del reparto llevado a cabo por un camión y un dron, de manera conjunta, así como la extensión del problema a varios drones, resolviendo un caso concreto y analizando los resultados obtenidos, con el objetivo final de dimensionar la flota de drones óptima. vii Abstract Business succes can be summed up in a nutshell as the way to maximize profits minimizing costs. In the day-to-day business of many companies, these costs are mainly incurred by those employed in logistics. In order to minimise these costs, two problems arose that today can be defined as classics: Traveling Salesman Problem and Vehicle Routing Problem. One of their great peculiarities, and the reason why they have become the basis for the study of other optimization problems, is that, in spite of their easy comprehension, for considerable dimensions these problems are unsolvable in an exact way. This is why different algorithms are used to approximate the optimum, whether they are specific to these problems (heuristics) or others of a generic nature (metaheuristics). Within the distribution sector, the use of drones for delivery has become one of the lines of work with the greatest potential to revolutionize the sector. Therefore, we will discuss how to deploy a drone to assist some target customers on a truck route, ending by extending the problem to multiple drones, exposing for a specific case the optimal drone fleet size. Índice Agradecimientos v Resumen vi Abstract viiii Índice viiiii Índice de Tablas x Índice de Figuras xi Notación xii 1 Introducción 1 2 Problemas de Rutas 3 2.1. Traveling Salesman Problem 3 2.1.1. ¿A qué clase de complejidad pertenece el TSP? 5 2.1.1.1. Tipo P 5 2.1.1.2. Tipo NP 5 2.1.1.3. Tipo NP-Hard 6 2.1.2. Modelización y formulación 7 2.1.3. Variantes del TSP 8 2.1.3.1. Multiple Traveling Salesman Problem 8 2.1.3.2. Traveling Salesman Problem with Time Windows 9 2.1.3.3. Probabilistic Traveling Salesman Problem 9 2.2. Vehicle Routing Problem 9 2.2.1. Variantes del VRP 10 2.2.1.1. VRP Homogéneo 11 2.2.1.1.1. Distance VRP 11 2.2.1.1.2. VRP with Time Windows 11 2.2.1.1.3. VRP with Backhauls 12 2.2.1.1.4. Split Delivery VRP 12 2.2.1.2. VRP Heterogéneo 12 2.2.1.2.1. Periodic VRP 12 2.2.1.2.2. Multi-Trip VRP 13 2.2.1.2.3. Multi-Objective VRP 13 3 Nuestro Problema 15 3.1. The flying sidekick TSP 16 3.1.1. Modelización y formulación 16 3.1.2. Heurística FSTSP 19 3.1.3. Cuantificación de la flota de drones 20 ix 4 Algoritmos Clásicos de Resolución 23 4.1. Métodos Exactos 23 4.1.1. Algoritmo de fuerza bruta 23 4.1.2. Programación Dinámica 23 4.1.3. Programación Entera 24 4.2. Heurísticas 25 4.2.1 Greedy Algorithm 25 4.2.2 Nearest Neighbor 25 4.2.3 Nearest Insertion 26 4.2.4. Christofides Algorithm 26 4.2.5. K-Optimal Algorithm 26 4.3. Metaheurísticas 27 4.3.1. Metaheurísticas de Búsqueda Local 27 4.3.2. Metaheurísticas Bioinspiradas 28 5 Nuestros Algoritmos 32 5.1. Genetic Algorithm 32 5.2. Ant Colony Optimization 34 6 Resultados y Conclusión 38 6.1. Método de resolución 38 6.1.1 Características destacables 39 6.2. Resultados 40 6.2.1 Resultados del GA 41 6.2.2 Resultados del ACO 44 6.3. Conclusiones 46 Referencias 48 Anexo 52 Problemas de Rutas 4 ciudades) encontrar el trayecto de menor coste (ya sea en términos de distancia o tiempo) en el cual se visiten todos y cada uno de los nodos una sola vez, regresando finalmente al nodo inicial. Figura 2-1. Ejemplo TSP[8] Antes de entrar en profundidad en la problemática, hagamos una pequeña retrospección a sus inicios. Aunque previamente, en un manual alemán para viajantes de 1832, se había abordado el problema, no fue hasta 1857 cuando se hace su primera formulación matemática, de la mano del matemático irlandés William Rowan Hamilton a través de su Icosian Game. El juego consistía en un dodecaedro regular cuyo objetivo era visitar cada uno de los veinte vértices que formaban el poliedro, una sola vez cada uno y acabando en el vértice de partida. Al ciclo formado al acabar dicho juego se le denominó ciclo hamiltoniano. Obviamente, el juego no consistía en encontrar la ruta óptima, pero se puede considerar el TSP como el ciclo hamiltoniano de menor longitud en un grafo, lo cual supuso el punto de partida para el estudio del problema en cuestión.[9]–[11] Figura 2-2. Ciclo Hamiltoniano. [12] Figura 2-3. Juego Icosiano.[10] Aunque el origen del estudio del problema concreto no está del todo claro, parece que no fue hasta la década de 1930 cuando el matemático austríaco Karl Menger estudió y definió por primera vez directamente dicho problema, denominándolo Problema del Mensajero[13]. Este problema consistía en encontrar la mínima longitud de la unión de un conjunto de puntos, sabiendo previamente 5 Coordinación y dimensionamiento de flota de drones en problemas TSP a través de Python la longitud entre cada par de puntos. Para su resolución, consideró el algoritmo de “fuerza bruta”, que básicamente se trata de probar todas las combinaciones posibles hasta encontrar la mejor. Como veremos más adelante, para una dimensión del problema no excesivamente grande, la utilización de dicho algoritmo es, sencillamente, inviable. A pesar de que la acuñación del término Traveling Salesman Problem pertenece al matemático estadounidense Hassler Whitney, el mérito de la promulgación y difusión del TSP, dentro de la comunidad matemática, recae sobre el matemático estadounidense Merrill Flood[14], quien, gracias a su estudio del TSP tratando de encontrar la optimalidad en rutas escolares, presentó la problemática en la Corporación RAND, cuya reputación y autoridad hizo que se ampliase exponencialmente la popularidad del problema, siendo esta corporación el centro intelectual de los estudios sobre el TSP en aquella época. Desde ese momento, infinidad de estudios, realizados por científicos de toda índole, han versado sobre el problema en cuestión, otorgando al TSP el estatus de ser uno de los problemas más famosos de la matemática computacional. 2.1.1 ¿A qué clase de complejidad pertenece el TSP? [15] La teoría de la complejidad computacional siendo un apartado dentro de la teoría de computación, basa su estudio en la clasificación y asignación de las distintas problemáticas computacionales, en función de la dificultad para su resolución. Asignar el TSP a un tipo de problema puede resultar más confuso de lo que cabría esperar pues, la simple diferenciación entre problemas P y NP es un estudio denso y arduo. No concierne dentro del alcance de este trabajo el abordar dicha disyuntiva, por lo que me limitaré a definir brevemente los distintos tipos, explicar a cuál pertenece el TSP y por qué. 2.1.1.1 Tipo P Los problemas de complejidad P son aquellos problemas de decisión que pueden ser resueltos en tiempo polinómico a través de la entrada por una máquina de Turing determinista. En otras palabras, cuando el problema en cuestión puede ser resuelto en un tiempo polinómico, entendiendo por tal el formado por una función polinómico utilizando las variables implicadas. Hablamos de los problemas más sencillos o abordables. 2.1.1.2 Tipo NP Siguiendo con la definición utilizada en P, los problemas tipo NP son aquellos que pueden ser resueltos en un tiempo polinómico por una máquina de Turing no determinista. Dando una definición más coloquial, un problema NP es aquel cuya solución puede ser verificada en un tiempo polinomial. Dentro de la categoría de problemas NP, encontramos los que se conocen como NP-complete. Un problema es NP-complete si dicho problema pertenece al conjunto de problemas NP y, además, cualquier problema NP es transformable al primero. Para afirmar que un problema es NP-complete, bastaría con que fuese equivalente a otro y, de forma automática, lo sería a todos los ya demostrados. Problemas de Rutas 6 Figura 2-4. Clases de complejidades.[16] Esta clase de problema es considerada como la más compleja de todas, en el cual aún no se ha encontrado ningún problema que la valide. 2.1.1.3 Tipo NP-hard A pesar de la similitud en el nombre, esta clase de complejidad no pertenece al conjunto NP. Se podría definir un problema NP-hard como aquel que, dando una máquina oráculo de este (máquina abstracta capaz de resolver ciertos problemas de decisión en una simple operación), todos los demás problemas en NP pueden ser resueltos en un tiempo polinomial. Los problemas NP-hard son al menos tan costosos como un problema NP-complete, pero no tienen por qué pertenecer al conjunto de problemas NP. Dicho de otro modo, los problemas NP- complete serían la intersección entre los problemas NP y los NP-hard El TSP pertenece a esta clase de problemas. Pero ¿por qué? ¿por qué no NP-complete? La respuesta podría ser tan sencilla como que el TSP no puede pertenecer al conjunto de problemas NP. Retomando la defición coloquial de los problemas NP, decíamos que son aquellos cuya solución puede verificarse en un tiempo polinomial. Supongamos que partimos de una potencial solución de un problema TSP de cuatro nodos. La única forma de saber si nuestra solución es la óptima sería comparándola con cada una de las combinaciones posibles, 6 en nuestro ejemplo ((N-1)! combinaciones para el caso general, siendo N el número de nodos). Puede parecer asequible su comparación, pero ¿y si partimos de 10 nodos? ¿y de 100? Por poner un sencillo ejemplo, si aplicásemos un TSP a las escasas 8 capitales de provincia andaluzas, una situación bastante verosímil, tendríamos que resolver un total de 5.040 combinaciones, surgiendo un problema que, aunque aún sea factible obtener la solución de manera exacta, se torna bastante más complicado. Obviamente, la comprobación de que la solución de un TSP, de una dimensión no necesariamente muy grande, es la óptima, no podría hacerse en un tiempo polinomial, por lo que el TSP no pertenece al conjunto de problemas NP, siendo un problema NP-hard. La dificultad implícita en estos problemas insta a la necesidad de abrir un abanico de posibilidades en cuanto a algoritmos de resolución se refiere, siendo fundamental la inclusión de algoritmos heuríticos y metaheurísticos de los cuales obtendríamos soluciones aproximadas en un 7 Coordinación y dimensionamiento de flota de drones en problemas TSP a través de Python tiempo razonable. Hablaremos de todo ello en los próximos capítulos. 2.1.2 Modelización y formulación[17] A lo largo de los años, el TSP ha sido modelizado y formulado de diversas formas, adaptándose a las características intrínsecas de la variante objeto. Nosotros expondremos una de las formulaciones más comunes y sencillas del problema, la cual nos sirva a modo de ejemplo explicativo. Antes de comenzar, cabe destacar los dos tipos de TSP clásicos en cuanto a estructura se refiere: • Simétrico: El coste entre dos nodos es el mismo independientemente del sentido. Tomando por nodos un conjunto de ciudades, la distancia de la ciudad i a la ciudad j será la misma que de la j a la i. En esta casuística, la matriz de costes es simétrica. • Asimétrica: El coste entre dos nodos puede diferir en función del sentido en el que se visiten. La distancia de la ciudad i a la j no tiene por qué ser la misma que de la j a la i, e incluso puede que uno de los dos trayectos no sea posible. En este caso, la matriz de costes será asimétrica. Abordaremos una formulación del problema asimétrico. Para ello previamente debemos definir una serie de términos, de acuerdo con la teoría de grafos: Tenemos un grafo G = (V, A, C), donde V es el conjunto de vértices del grafo, A el conjunto de aristas y C es la matriz de costes (cij es el coste de ir de i a j) y n el número de nodos. Definimos también un ciclo simple aquel en el que el vértice inicial del mismo coincide con el final, siendo cada vértice visitado una única vez. El ciclo hamiltoniano, ya definido previamente, sería el ciclo simple que visita cada uno de los vértices. En este punto, tratamos de localizar el ciclo hamiltoniano de menor coste. Comencemos con las variables de decision del problema. Denominamos xij a la variable que representa la arista que conecta el vértice i con el j, tomando el valor de 1 si esa arista es parte de la solución final del problema y 0 en caso contrario. A modo de inicialización, cada cii tomarán valores muy grandes, para así asegurarnos que la arista que va desde un nodo hasta sí mismo nunca será parte de la solución del problema. Llegados a este punto, la función objetivo del problema sería la siguiente: min∑∑𝑐𝑖𝑗𝑥𝑖𝑗 𝑛 𝑗=1 𝑛 𝑖=1 Cuyas restricciones que implican que a cada vértice llegará una única arista y de cada vértice saldrá una única arista son las siguientes: ∑𝑥𝑖𝑗 =1 𝑛 𝑗=1 ∑𝑥𝑗𝑖 =1 𝑛 𝑖=1 Problemas de Rutas 8 En este punto surge un problema el cual las restricciones definidas hasta el momento no consiguen solventar: la creación de lazos o subconjuntos. Nótese que si dentro de un mismo grafo se crean varios subciclos en los cuales se cumplen las restricciones de entrada y salida única en cada vértice, no hay ninguna restricción que se incumpla hasta el momento, pero no define el TSP. Por ello, debemos incluir ciertas restricciones que obliguen a romper esos posibles lazos. Una forma de hacerlo sería a través de la inclusión de nuevas variables de decisión denominadas ui. Estas variables representan el momento de la solución en el que el vértice i es visitado, pudiendo tomar valores de 2 a n, reservando el valor 1 al nodo de partida (lo que sería el almacén). Con ello, tendríamos la siguiente restricción: 𝑢𝑖−𝑢𝑗≤(n−1)(1−𝑥𝑖𝑗)−1 En el caso de que xij pertenezca a la solución, nos quedaría 𝑢𝑖 – 𝑢𝑗≤−1, lo cual se cumple ya que el nodo i se visita justo antes que el nodo j. En caso contrario, llegaríamos a 𝑢𝑖 – 𝑢𝑗≤ 𝑛−2, inecuación que se cumple para todos los posibles valores de ui y uj por lo que la inecuación se cumple. En el caso de la existencia de lazos, esta restricción no podría cumplirse ya que no podría establecerse una secuencia de visitas a los nodos por no estar relacionados entre sí. 2.1.3 Variantes del TSP[18] Pronto, tras la acuñación del TSP y su posterior estudio, se hizo evidente que el problema era adaptabale a una infinidad de situaciones, con sus características específicas, así como la propia evolución que sufrió a medida que el paso del tiempo iba generando nuevas necesidades. A continuación, se detallan algunas de esas variables 2.1.3.1 Multiple Traveling Salesman Problem[19] Se podría considerar esta variante como precusor del VRP, el cual se abordará más adelante en este mismo capítulo. Como adelanto, si considerásemos los vehículos propios del VRP con capacidad infinita o lo suficientemente grandes como para que la capacidad no suponga una restricción del problema, entonces mTSP y VRP coincidirían. Definimos el Multiple Traveling Salesman Problem (mTSP) como aquel en el que habiendo una serie de nodos (ejemplifiquémoslos como ciudades) y un conjunto m de “salesmen”, obtengamos las distintas rutas recorridas por todos los vendedores, de modo que todas las ciudades sean visitadas por un único vendedor, siendo el coste del trayecto el mínimo posible. 9 Coordinación y dimensionamiento de flota de drones en problemas TSP a través de Python Figura 2-5. mTSP[20] 2.1.3.2 Traveling Salesman Problem with Time Windows[21] Partamos, de nuevo, del TSP clásico. Contamos con un conjunto de nodos (que, de nuevo, ejemplificamos como ciudades y así lo mantendremos a lo largo de la explicación de las distintas variantes), y necesitamos conocer la ruta de menor coste en la que recorramos todos las ciudades una sola vez. En lo que difiere el Traveling Salesman Problem with Time Windows (TSPTW) es que cada nodo consta de un instante de “apertura” (denominado ai) y de “cierre” (bi). Bajo estos términos, el problema incluye la restricción de que cada ciudad i debe ser visitada en el intervalo de tiempo creado entre ai y bi. En el caso en que la ciudad sea visitada antes del instante ai, nuestro vendedor deberá esperar, con el correspondiente aumento del coste, hasta dicho instante, siendo imposible la visita a la ciudad en un instante posterior a bi. Dicha variante puede ser combinada con el mTSP, con la única diferencia de que el problema constará de más de un vendedor. 2.1.3.3 Probabilistic Traveling Salesman Problem En el Probabilistic Traveling Salesman Problem (PTSP), añadimos una nueva diferencia que, de igual modo, es combinable con las anteriores. En este caso, la consecución de la ruta de menor coste debe tener en cuenta que cada ciudad lleva asociada una probabilidad de que en ellas haya o no un consumidor que dé sentido a la visita. 2.2 Vehicle Routing Problem A medida que la sociedad iba evolucionando, surgieron numerosos nuevos conflictos, los cuales debían ser solventados aplicando nuevas herramientas o reiventando las ya existentes. Del mismo modo, el TSP se generalizó añadiendo nuevas condiciones o restricciones, creando un nuevo tipo de problema el cual, desde su primera formulación hace más de 50 años, se convirtió en uno de los principales problemas de la Investigación Operativa. El Problema de Enrutamiento de Vehículos (VRP por sus siglas en inglés Vehicle Routing Problemas de Rutas 10 Problem) consiste en encontrar las rutas óptimas entre uno o varios depósitos o almacenes y un conjunto de ciudades (nodos), constando dichas rutas con el depósito como punto común y final del problema y siendo visitadas cada ciudad una única vez. Queda claro, desde este punto, que el VRP es una extensión del TSP. Figura 2-6. Solución de VRP[22] Como ya hicimos en la explicación del TSP, antes de detallar de manera concisa las características del VRP, veamos de manera superficial sus orígenes. No fue hasta 1959 cuando los matemáticos estadounidenses George Dantzig y John Ramser formularon matemáticamente por primera vez esta problemática, en su célebre “The Truck Dispatching Problem”[23]. Para ello, aplicaron el problema a la entrega de combustible por parte de una flota N de camiones a una serie de estaciones de servicios, partiendo de un único terminal. Con este fin propusieron una formulación de programación lineal de la cual obtuvieron una solución cercana a la óptima. La importancia que recae sobre dicho estudio no es únicamente la resolución de un VRP de dimensión considerable, sino la utilización de métodos de resolución tales como Branch and bound, el cual abordaremos en profundidad más adelante, así como la demostración de que, a pesar de la complejidad de los problemas de optimización combinatoria, su resolución era posible.[24] Destacar además que el VRP se trata de un problema NP-hard, cuya explicación es análoga a la ya expuesta en el caso del TSP. 2.2.1 Variantes del VRP[18] Desde el nacimiento del problema, al igual que con el TSP, surgieron una infinidad de variantes del mismo cuya finalidad era dar respuesta a las distintas situaciones reales a las que se podría enfrentar el mismo. 11 Coordinación y dimensionamiento de flota de drones en problemas TSP a través de Python El TSP generalizado, conocido como VRP o CVRP (Capacited VRP) introduce la primera característica esencial de los problemas de enrutamiento de vehículos y es que la capacidad de la flota de vehículos comienza a ser una restricción más del problema, pues no es infinita. Con lo cual, queda definido el CVRP como un problema que busca la obtención de una serie de rutas, cuya suma de costes entre los nodos que la forman sea mínima, siendo cada nodo visitado una única vez por un único vehículo y la suma de las demandas de cada nodo no excede la capacidad intrínseca del vehículo. Como ya sucedía en el TSP, podríamos diferenciar entre el CVRP simétrico, en el cual el coste de ir de la ciudad i a la ciudad j es el mismo que el de la ciudad j a la i, y el CVRP asimétrico, donde esta igualdad no tiene por qué cumplirse. Figura 2-7. Variantes TSP-VRP[18] A raíz de dicho problema inicial surgen dos grandes familias, las cuales a su vez tienen numerosas ramificaciones con características propias. Nos adentraremos a continuación a explicar las características propias de cada familia, así como a mostrar algunos casos concretos a modo de ejemplos. 2.2.1.1 VRP Homogéneo Los problemas pertenecientes a la familia del VRP Homogéneo comparten una serie de características comunes en las que todas las ciudades o nodos controlan un mismo recurso. En función de los recursos controlados tendremos un tipo de problema. Procederemos a explicar algunos de ellos. 2.2.1.1.1 Distance VRP En este caso, la restricción se produce en la máxima longitude admissible de cada ruta. Dicho de otro modo, la suma de distancias entre los distintos nodos que forman una ruta no puede exceder un tamaño de longitude máximo de la ruta, establecido previamente. En el supuesto de que, además de dicha restricción exista una limitación en la capacidad de los vehículos como la previamente explicada, el problema pasaría a llamarse DCVRP. 2.2.1.1.2 VRP with Time Windows Restricción ya abordada en el TSP con Ventana de tiempos, el VRPTW, incluye la novedad de que cada consumidor debe ser visitado en un interval de tiempo establecido previamente, siendo Problemas de Rutas 12 imposible la visita al mismo una vez que dicho interval finalice y con la correspondiente penalización de espera en el caso de que se visite antes de que comience el intervalo Figura 2-8. VRP with Time Windows[25] En función de las características de esas ventanas de tiempo, encontramos a su vez nuevas variantes, como la VRPTD, en las que el intervalo es completamente rígido, VRPMTW, en la cual los intervalos de tiempo de los distintos nodos no son de la misma dimensión, o el VRPSTW, donde los límites de los intervalos no son completamente rígidos. 2.2.1.1.3 VRP with Backhauls En esta casuística abreviada como VRPB, los clientes pueden devolver ciertas mercancías al vehículo, por lo que antes de visitar a un cliente cuyo deseo sea devolver una mercancía hay que tener en cuenta si en ese momento el vehículo tiene la capacidad necesaria para ello. Un caso extremo sería aquel en el que para que una mercancía pueda ser recogida, primero han de realizarse todas las entregas de la ruta. En este caso quedan diferenciados dos tipos de clientes, los que van a recoger un pedido o los que van a entregarlos. 2.2.1.1.4 Split Delivery VRP Relajación del VRP en el cual se permite que un mismo nodo sea visitado por distintos vehículos, bajo la condición de que dicha operación reduzca el coste total. 2.2.1.2 VRP Heterogéneos En la familia de los VRP Heterogéneos, se hace referencia a componentes desiguales en los que los distintos nodos controlan recursos distintos. Algunos ejemplos son los siguientes: 2.2.1.2.1 Periodic VRP A diferencia del VRP donde el periodo de planificación es de un único día, en el PVRP dicho periodo se extendiende a M días 13 Coordinación y dimensionamiento de flota de drones en problemas TSP a través de Python 2.2.1.2.2 Multi-Trip VRP En este caso, un mismo vehículo dentro del periodo de planificación puede llevar a cabo varias rutas, por lo que no solo hay que tener en cuenta el diseño intrínseco de las rutas, sino además la disponibilidad de los diversos vehículos. 2.2.1.2.3 Multi-Objective VRP Consiste en utilizar diferentes objetivos, ya sean referentes a las rutas, a los arcos, a los nodos o a los recursos, y obtener la solución en función del cómputo de objetivos. Nuestro Problema 20 Figura 3-2. FSTSP Heurística[26] El pseudo código propuesto en el Artículo y desarrollado en este TFG en el Anexo 1, muestra la implantación de lo que pretende reflejar esta imagen. Partimos de la ruta óptima del camión, calculada a través de distintos algoritmos que serán la temática de los dos prócimos capítulos del TFG. A su vez, tenemos definido los nodos a los que el dron le es factible visitar. Para cada cliente potencialmente visitable por el dron, el código debe realizar un estudio de los costes que te supondrá la visita del dron, o el movimiento en el orden de visita de un determinado cliente, en contraposición con el ahorro o ganancias que genera. En caso de un ahorro mayor que el coste, se implementará dicho movimiento. Con este objetivo, se desarrollarán una serie de funciones, las cuales procedo a explicar brevemente, siendo desgranadas a través de comentarios en el propio código: • Código principal del FSTSP: En él, se produce la unión de las distintas funciones, efectuando un bucle que tenga en cuenta todos los posibles nodos a visitar por el dron. • calcSavings: Calcula el ahorro de eliminar un cliente j de la ruta del camión. Destacar la posibilidad de un ahorro negativo. • calcCostTruck: Coste de insertar un cliente j en otro punto de la ruta del camión. • calcCostUAV: Coste de que, efectivamente sea el dron quien visite al cliente j. • performUpdate: Una vez decidido que hacer con el cliente j, debemos actualizar todas las entradas del algoritmo, ya sea las distintas subrutas del camión, la ruta genérica, el tiempo de llegada del camión a cada nodo, etc. 3.1.3 Cuantificación de la flota de drones Una vez elaborada la implementación del FSTSP, nos percatamos a través de los resultados obtenidos, los cuales se encuentran en detalle en el último capítulo de este TFG, que, en ocasiones, el dron se encuentra envuelto en distintas subrutas dentro de las cuales existen clientes potencialmente visitables, a su vez, por drones. En este sentido, llegamos a un punto en el que la heurística FSTSP sólo desarrolla su máximo potencial para problemáticas muy específicas, siendo, en el problema genérico, muchos clientes visitados por el camión cuando un dron podría realizar esa tarea. En ese punto observamos que la adaptación de la heurística FSTSP al uso de varios drones podría generar unos beneficios bastante interesantes. Tal es así que, el mismo Chase Murray, esta vez junto a Ritwik Raj aborda dicha disyuntiva en otro artículo, “The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones”[33]. Cabe resaltar que nuestra implementación en Python con el uso de varios drones se aleja de la empleada por Murray y Raj. Nuestro cometido ha sido, el readaptar el FSTSP para varios drones, de manera simplificada. Utilizaremos, no obstante, el artículo a modo de fuente de información. El mayor problema al ir introduciendo progresivamente más drones a la ecuación es la necesidad de una coordinación constante dron-camión y dron-dron. Y no únicamente nos referimos a lo expuesto anteriormente de la necesidad de que el camión se localice en los nodos donde despegan/aterrizan 21 Coordinación y dimensionamiento de flota de drones en problemas TSP a través de Python todos los drones, sino que se antoja fundamental calcular la autonomía del dron, sabiendo el incremento de tiempo que supone la recogida y preparación de otros drones. Al mismo tiempo, conseguir que cada cliente sea visitado una única vez cuando contamos con más de un dron, se convierte en una tarea cuanto menos compleja. Figura 3-3. TSP con diferentes tamaños de flota de drones[33] En el código que se muestra en el Anexo 1, desarrollamos la implementación de un número n de drones para el problema TSP, relajando en algunos aspectos las restricciones temporales y de coordinación. No obstante, lo que resulta interesante, a nivel conceptual, es la cuantificación de la flota de drones. Aunque el reparto de drones, pensado para trayectos cortos, supone un ahorro en costes con respecto al reparto tradicional de camiones, no es tan sencillo el saber el tamaño óptimo de la flota de drones para una dimensión concreta del problema. Puede ocurrir que, para un conjunto de nodos relativamente pequeño, con clientes situados a distancias cortas entre sí, sobredimensionemos el problema de forma que un cierto número de drones ni siquiera sea necesario su uso o, utilizándolos, no supongan un ahorro tal que merezca la pena tenerlo. Sin llegar abarcar el tema económico, sí que abordaremos distintos tamaños de flota de drones para varios problemas distintos, analizando las ventajas y desventajas de emplear más o menos drones. Nuestro Problema 22 23 4 ALGORITMOS CLÁSICOS DE RESOLUCIÓN Una vez abordado tanto el problema TSP como el VRP en profundidad, resulta evidente la complejidad del mismo. Un problema de relativamente fácil compresión pero de una dificultad capital en cuanto a su resolución, pues el número de combinaciones va creciendo a ritmo de (N-1)!. Pero, ¿cómo se puede resolver? La pregunta tiene una respuesta un tanto más extensa de lo que cabría esperar. Surgen entonces tres grandes grupos o familias de algoritmos de resolución, los cuales, a su vez, tienen sus propias características y sus campos de aplicación. 4.1 Métodos exactos[34] Los métodos exactos pretenden encontrar la mejor solución del problema, en nuestro caso, la ruta o rutas óptimas en las que se visiten todos y cada uno de los nodos una única vez. En nuestro caso particular, como ya se ha explicado, al ser un problema de complejidad NP-hard, su aplicación se encuentra cuanto menos limitada, aunque dentro de los mismos algunos tienen un alcance mayor que otros. 4.1.1 Algoritmo de Fuerza Bruta[35] Quizás, el más simple y robusto de los que se someterán a estudio. El algoritmo trata de encontrar la mejor solución del problema a través de la comprobación de todas y cada una de las combinaciones posibles. Como ya se ha explicado con anterioridad, este método resulta útil para un número muy limitado de nodos pues, creciendo las combinaciones posibles a ritmo de (N-1)/2!, en el momento que llegamos a un número de nodos no excesivamente grande, su uso resulta inviable. Al ser la mayoría de situaciones en las que se aplican el TSP y el VRP de una dimension mayor de la necesitada por el algoritmo de fuerza bruta, en la práctica este algoritmo es poco utilizado. 4.1.2 Programación Dinámica[36] La Programación Dinámica, desarrollada por Richard Bellman en la década de 1950, se basa en descomponer el problema original en diversos subproblemas de manera recursiva, almacenando las soluciones de los mismos. De este modo, si al evaluar futuros subproblemas estos coinciden con subproblemas que ya habían sido solucionados con anterioridad, se podrán utilizar directamente dichas soluciones, ahorrando coste computacional y tiempo de resolución del algoritmo. Con el objetivo previamente descrito, se producen relajaciones del problema original, de modo que los diferentes subproblemas sean similares entre sí y tengan utilidad. De forma similar al algoritmo de fuerza bruta, la aplicación de la programación dinámica al TSP se limita a un número muy reducido de nodos, por lo que tampoco resulta uno de los métodos más Algoritmos Clásicos de Resolución 24 utilizados de resolución. 4.1.3 Programación Entera En ciertos problemas, como pueden ser el caso del TSP y el VRP, las variables de decision deben ser valores enteros, denominándose Problemas de Programación Entera si es la única diferencia con respecto a los problemas de programación lineal, o, en caso de que solo algunas variables tengan la necesidad de ser valores enteros, se trataría de los Problemas de Programación Entera-Mixta. Ya que, como hemos dicho, el TSP y el VRP pueden quedar enmarcados dentro de este subconjunto de problemas, las distintas soluciónes clásicas del subconjunto en cuestión son válidas para conseguir la resolución buscada. Figura 4-1. Simplificación visual de la técnica de Branch-and-Bound[37] Para este tipo de problemas, la técnica más común es aquella denominada Branch-and-Bound. Técnica surgida y refinada entre 1960 y 1970, además de ampliamente utilizada y estudiada, genera una solución exacta del problema actuando de la siguiente manera: • En primer lugar, divide el problema en subproblemas cada vez más pequeños en los que se pueda evaluar la función objetivo de manera más rápida (branch). • Acotando cómo de buena puede ser la solución óptima y descartando los diversos subconjuntos en los que la optimalidad no se produzca (bound) Posteriormente, en la década de 1980, la utilización de los planos de corte supuso una mejora técnica del Branch and Bound, denominada Branch-and-Cut, en la cual, gracias al corte de distintas ramas del árbol de decision generado, se produce un importante ahorro en tiempo computacional con respecto al Branch and Bound. Si bien es cierto que estas técnicas pueden ser aplicadas para una mayor dimension del problema tratado, la naturaleza NP-Hard del TSP hace que los métodos exactos sean inoperables para dimensiones más cercanas a la realidad del problema, por lo que deben buscarse distintas vías de resolución. 25 Coordinación y dimensionamiento de flota de drones en problemas TSP a través de Python 4.2 Heurísticas[38] Si flexibilizamos el objetivo de conseguir la optimalidad, dado el coste computacional a medida que aumentamos el número de nodos, aparecen una serie de algoritmos, únicamente utilizables para este problema particular, los cuales generan una solución buena, la cual no garantiza ser la óptima, pero alcanzable a un coste mucho menor. Estos algoritmos son muy interesantes de cara a buscar soluciones para TSP o VRP de tamaños mayor, más cercanos a los que nos podemos encontrar en el día a día. A pesar de la gran cantidad de heurísticas existentes, expondremos algunas de ellas a modo de ejemplo: 4.2.1 Greedy Algorithm[39] Este nombre engloba a un conjunto de algoritmos con unas características específicas, el cual si que es reutilizable para algún otro problema distinto al TSP, aunque es en éste donde encuentra una solución más cercana a la óptima. La aplicación del algoritmo parte de la ordenación de los distintos nodos o ciudades a visitar, por pares de nodos a menor distancia. Siguiendo esta dinámica, el greedy algorithm siempre elige la mejor solución en cada iteración. Continuaríamos uniendo las ciudades, siempre buscando la menor distancia entre ellas, hasta que lleguemos a un ciclo cerrado en el que se incluyan todas las ciudades del problema. Figura 4-2. Greedy Algorithm[40] 4.2.2 Nearest Neighbor[41] El Nearest Neighbor Algorithm (NN) es un caso particular de los algoritmos greedy. En el partimos de una ciudad o nodo específico del problema y, desde el mismo, vamos eligiendo como próximo nodo a visitar el que se encuentra a menor distancia del nodo precursor, de forma iterativa. Aún dando una buena solución del problema, el principal inconveniente de esta heurística se localiza al final del algoritmo, cuando quedan pocas ciudades a visitar y, teniendo en cuenta la limitación de que cada ciudad sólo puede ser visitada una vez, nos vemos obligados a recorrer distancias muy grandes en estas uniones finales. Definiendo la complejidad temporal como la cantidad de tiempo necesaria para ejecutar un algoritmo, estimada a través del número de operaciones elementales que emplea el algoritmo en cuestión, suponiendo un valor constante del tiempo empleado en las operaciones a realizar. En este sentido, el número de cálculos necesarios no crecerá más rápido que n2 (complejidad temporal O(n2)). Algoritmos Clásicos de Resolución 26 4.2.3 Nearest Insertion Volvemos a una técnica similar a NN. En este punto, partimos de un ciclo o tour, formado por un número escaso de nodos. El algoritmo trata de localizar el nodo cuya inserción suponga el menor coste possible. En otras palabras, trata de localizar la ciudad más cercana a cualquiera de las ciudades que forman el tour, para así insertarla en el mismo. De igual modo que en el caso anterior, dichas inserciones se irán repitiendo de forma iterativa aumentando el tamaño del ciclo inicial, hasta que finalmente obtendríamos un ciclo que incluyese a todas las ciudades. Al igual que ocurriría en el algoritmo NN, el algoritmo NI consta de una complejidad temporal de O(n2). 4.2.4 Christofides Algorithm[42] El algoritmo de Christofides garantiza una aproximación de, como máximo, 3/2 veces mayor de la ruta óptima. Desarrollado en 1976 por el professor Nicos Christofides, este algoritmo, a pesar de la demostración de cuanto es capaz de acercarse a la solución óptima, suele utilizarse como un método de búsqueda de una solución inicial a la cual practicarle otras heurísticas de mejora, u otros métodos exactos como los expuestos en el 4.1. Figura 4-3. Christofides Algorithm.[42] Dicho algoritmo se basa en la satisfacción, por parte de la función de costes de los distintos arcos entre nodos, de la desigualdad triangular, teorema de la geometría euclidiana que expone que, para cualquier triángulo, la suma de dos cualesquiera de los lados es siempre mayor que el lado restante. Para poder efectuar el algoritmo, la matriz de distancia entre ciudades debe ser simétrica. En este caso, la complejidad temporal es de O(n4). 4.2.5 K-Optimal Algorithm Un problema es denominado k-óptimo si no es posible mejorarlo intercambiando entre sí unos k arcos. Este tipo de algoritmos conllevan una complejidad temporal de O(nk). En función del número de arcos a intercambiar, surgen una serie de algoritmos con características específicas, como podría ser el 2-Opt Algorithm, el cual lo realiza intercambiando dos arcos cualesquiera, si este intercambio produce una mejora de la solución, partiendo de la afirmación 27 Coordinación y dimensionamiento de flota de drones en problemas TSP a través de Python de que, si dos de los arcos se cruzan entre sí, esa solución jamás será la óptima del problema. En este punto, cabe resaltar el Lin-Kernighan Heuristic, el cual es un algoritmo que trata de mejorar un k-tour inicial. Para ello, hace uso de secuencias de los algoritmos 2-Opt, 3-Opt, etc, con el fin de escapar de mínimos locales. Además, con el objetivo de llegar a la solución más cercana a la óptima del problema, permite que ciertos tours intermedios tengan un coste mayor que el coste inicial, algo no permitido en el algoritmo 2-Opt, por ejemplo. 4.3 Metaheurísticas[43] Como última clase de algoritmos de resolución de problemas, aparecen las metaheurísticas, de gran utilidad en la práctica. Las metaheurísticas son aquellos algoritmos generales adaptables a una gran variedad de problemas. Las claras ventajas que le otorgan la maleabilidad que les caracteriza genera a su vez un detriment en la optimalidad de la solución, por ello se considera que lo que consiguen en una aproximación. Su ejecución se realiza de forma iterativa y es habitual que vayan acompañados de otros algoritmos de optimización. Las metaheurísticas constan de unas características que las colocan como grandes candidatas para la resolución de problemas de optimización en la práctica. Su fácil implementación en cuanto a codificación se refiere y su bajo coste computacional hacen de estos algoritmos uno de los grupos más estudiados y de más interés en la actualidad. Como ya se ha indicado, estas ventajas contrastan con su escasa garantía de optimalidad, tratándose de algoritmos probabilísticos, cuyo sustento teórico es relativamente pobre. En función de su principal característica o de la inspiración del algoritmo, nos encontramos distintas familias de metaheurísticas. A continuación, procederemos a exponer dichas metaheurísticas, a excepción de dos de las más estudiadas y conocidas, como serían Genetic Algorithm y Ant Colony Optimization. Explicaremos estos dos algoritmos en un capítulo aparte, pues serán los utilizados para conseguir la ruta óptima del camión de nuestro problema, antes de someterlo al algoritmo de asignación de drones. Serán explicados al detalle en el próximo capítulo. 4.3.1 Metaheurísticas de Búsqueda Local[44] Este tipo de metaheurísticas se basan en partir de una solución incial, donde, en su proceso iterativo, realizan una serie de movimientos de mejora a sus soluciones vecinas, otorgándoles las metaheurísticas un amplio abanico de actuación. Dentro de esta familia, la metaheurística más conocida es la denominada Búsqueda Tabú. La clave diferencial de la Búsqueda Tabú con respecto a las demás metaheurísticas de su familia es la facultad de memoria que se le otorga, la cual le permite escaper de óptimos locales. Una vez que el algoritmo detecta una potencial solución del problema, ésta se almacena es un espacio de memoria “tabú”, de modo que el algoritmo no podrá volver a dicha solución. Es una forma de proporcionarle una especie de “inteligencia” al algoritmo, de modo que no itere una y otra vez sobre el mismo óptimo local. Algoritmos Clásicos de Resolución 28 Figura 4-4. Diagrama de Flujos de la Búsqueda Tabú La Búsqueda Tabú es ampliamente utilizada para la resolución de los problemas TSP. Dentro de esta familia de metaheurísticas aparece otra de gran aplicación como es el Recocido Simulado. Método descrito de forma independiente por Scott Kirkpatrick, C. Daniel Gelatt y Mario P. Vecchi en 1983 y por Vlado Černý en 1985, recibe su nombre debido a las similitudes con dicho proceso. El proceso de recocido se basa en el calentamiento a altas temperaturas del material en cuestión, para luego enfriarlo de manera controlada a través de una tasa α, lo cual le otorga una serie de propiedades. En este algoritmo partimos de una solución inicial aleatoria. A continuación, a través de cada iteración, se propone una nueva solución también aleatoria. Llegados a este punto tendríamos dos posibles escenarios: que la nueva solución sea mejor que la anterior, la cual se aceptaría; que la nueva solución sea peor, en cuyo caso se acepta como nueva solución del problema en función de una probabilidad que va disminuyendo a medida que avanzamos en las iteraciones. La gran ventaja que otorga este algoritmo es su facilidad para escapar de óptimos locales. 4.3.2 Metaheurísticas Bioinspiradas[45], [46] Particle Swarm Optimization (PSO), la metaheurística más conocida dentro de esta familia, 29 Coordinación y dimensionamiento de flota de drones en problemas TSP a través de Python consiste en modelar cada robot del sistema de enjambre robótico como una partícula. Se trata de una técnica de computación evolutiva paralela, desarrollada en 1995. Esto significa que el conocimiento de cada paso de iteración se transfiere y se utiliza en el siguiente paso de cálculo. Cada partícula inicia la búsqueda del espacio de búsqueda asignado en una posición aleatoria o, alternativamente, en una posición especificada con una velocidad aleatoria. A continuación, se desplaza por el área de búsqueda cambiando iterativamente su posición y velocidad. En cada paso, las partículas miden el valor de la función objetivo en su posición y lo comparan con su mejor experiencia personal, así como con la mejor experiencia global de las mediciones que se han realizado. Al ajustar su velocidad para el siguiente paso, se tienen en cuenta estas mediciones y los incrementos de conocimiento. Como este procedimiento se repite para cada paso de iteración y para cada partícula, resulta un comportamiento de enjambre inteligente. Los parámetros de ajuste influyen en el impacto de las velocidades parciales. La siguiente fórmula explica matemáticamente el comportamiento de las partículas. Figura 4-5. Fórmula matemática PSO La siguiente ilustración muestra el movimiento de una sola partícula de forma gráfica. Las contribuciones de cada parte de la fórmula se representan en verde. El primer término (I) es la velocidad anterior de la partícula multiplicada por un factor. El segundo término (II) considera la mejor velocidad personal de la partícula y la aporta a la velocidad total para la siguiente iteración. El tercer término (III), por último, tiene en cuenta la mejor posición global y aporta este conocimiento a la velocidad total de la partícula. Figura 4-6. Descripción Gráfica PSO 𝑣𝑖+1,𝑗+1 = 𝑤𝑣𝑖𝑗 + 𝑐1𝑞 𝑥𝑖𝑗 𝑝𝑏 − 𝑥𝑖𝑗 ∆𝑡 + 𝑐2𝑟 𝑥𝑗𝑠𝑏 − 𝑥𝑖𝑗 ∆𝑡 Nuestros Algoritmos 36 Figura 5-4. Posible diagrama de flujos de ACO[60] 37 Coordinación y dimensionamiento de flota de drones en problemas TSP a través de Python Resultados y Conclusión 38 6 RESULTADOS Y CONCLUSIÓN 6.1 Método de resolución Antes de abordar los resultados obtenidos tras la experimentación a través tanto del GA como del ACO, aunque se definieron en el capítulo de Nuestro Problema, explicaremos con mayor detalle las funciones del código, con el fin de entender en profundidad como se consigue los resultados mencionados. El código consta de una serie de conceptos que se erigen como fundamentales para su desarrollo. Uno de ellos, las subrutas, constan a su vez de dos clases, las subrutas asociadas a un dron (aquella que comienzan en el cliente donde despega el dron y termina en el cliente en el cual aterriza) y las subrutas en las que no constan ningún dron en vuelo a lo largo de las mismas. Tal y como se expresó en el capítulo de Nuestro Problema, el código desarrollado para varios drones es una adaptación del pseudocódigo propuesto por Murray para un único dron, alejándonos de su propuesta para múltiples drones. Realizar esta adaptación entra en claro conflicto con las subrutas, pues cada dron dispondrá de diferentes de ellas, generando un resultado final fruto de la superposición de las subrutas de los distintos drones. Para solucionar esta situación, generamos un diccionario de Python con tantas “keys” como número de drones n estudiemos. En este sentido, en función del dron elegido para el movimiento, se modificarán las subrutas únicamente asociadas a dicho dron, generando una solución fidedigna del problema. • calcSavings: Como ya se comentó, esta función tiene como objetivo el cálculo del ahorro que se produce en la ruta del camión cuando extraemos un cliente j. Para conseguirlo, simplemente se calcula tanto el tiempo empleado por el camión en recorrer todos los nodos, incluyendo a j como el mismo tiempo excluyendo a j, siendo la diferencia de ambos tiempos el ahorro producido en la ruta del camión. Es importante tener en cuenta que este ahorro puede ser negativo, en el caso de que el coste de ir del cliente anterior a j al posterior de forma directa sea muy elevado. En este caso, no se ejecutará el código principal para dicho cliente, pues sabremos con certeza que no será rentable el cambio. • calCostTruck: En esta función se obtiene el coste de insertar al cliente j, atendido por el camión, en una posición distinta de la ruta del mismo. Una vez que los drones comiencen a atender clientes, la ruta del camión tras la eliminación de dichos clientes puede no ser la óptima, pues la calculada mediante las metaheurísticas era para todo el conjunto de clientes. Por ello, se estudia el posible coste de insertar al cliente en diferentes posiciones de la ruta del camión. La función tiene en cuenta que, para que dicho cambio pueda ser factible, los costes del 39 Coordinación y dimensionamiento de flota de drones en problemas TSP a través de Python movimiento deben ser menores que los ahorros generados en calcSavings, así como que la autonomía del dron en vuelo sea suficiente para hacer frente a dicho cambio sin que se agote su batería antes de llegar a su destino. • calCostUAV: De manera similar a lo explicado en la función anterior, se trata de obtener el coste asociado a que un cliente j sea atendido por un dron k. Una vez se obtengan los puntos de despegue y aterrizaje del dron, debe comprobarse que éste tiene la autonomía suficiente para realizar dicho trayecto. Resaltar la inclusión en el coste el tiempo empleado en la recogida del dron por parte del transportista, así como el tiempo que tarda en prepararlo para su despegue. • performUpdate: Una vez que se ha encontrado el movimiento o cambio que genera mayores ahorros al camión, es hora de actualizar las distintas subrutas, así como la ruta del camión, eliminando al cliente j en caso de que este sea atendido por un dron o cambiándolo de posición si así se requiere. Con este objetivo surge la variable booleana servedbyUAV, la cual tendrá el valor “True” cuando el cliente sea visitado por el dron y “False” en caso contrario. • Código principal: Para cada dron y para cada subruta del dron, comprobamos los distintos movimientos posibles asociados al cliente j de estudio. Comparamos todos los ahorros generados, eligiendo el de mayor valor, aplicándole a dicho dron y movimiento la función performUpdate. 6.1.1 Características destacables Como último paso antes de abordar la base de datos utilizada y los resultados obtenidos, se expondrán algunas licencias y simplificaciones adquiridas. En primer lugar, realizaremos el estudio asumiendo que no todos los clientes son factibles de ser visitados por drones, debido a que dichos clientes se encuentren en zonas de imposible acceso para los drones, que los paquetes a entregar sean demasiado pesados, etc. La elección personal de los clientes potenciales a ser visitados por drones es completamente aleatoria, quedando fuera del alcance de este TFG las consideraciones expuestas previamente. Por otro lado, aunque el código generado sea completamente determinista, la solución inicial de partida consta de un componente pseudoaleatorio, pues se obtiene a través de metaheurísticas. Por ello, a fin de una correcta experimentación, realizamos veinte iteraciones para cada metaheurísticas. En cuanto a las simplificaciones, hay dos factores a comentar. Primero, hemos obviado el depósito o almacén, el cual debería ser un punto fijo al inicio y final de toda la ruta. En segundo lugar, una vez que se comprueba que el dron tiene autonomía suficiente para realizar un determinado movimiento, aceptamos que este permanece factible a lo largo del tiempo, a pesar de que otras operaciones puedan aumentar el tiempo de vuelo requerido para el dron. La exclusión de dichas simplifaciones quedan como futuras líneas de estudio de este proyecto. Resultados y Conclusión 40 6.2 Resultados Los clientes a estudiar se obtienen de la web GitHub[59], los cuales quedan expresados en la siguiente tabla: Tabla 6-1. Clientes Clientes X Y 110 0 238 94 383 27 429 99 548 71 695 61 754 18 873 21 947 76 10 99 47 11 87 94 12 44 76 13 83 61 14 27 29 15 29 11 16 40 52 17 56 24 18 80 13 19 63 82 20 79 69 21 71 61 22 92 30 23 54 47 24 36 12 25 2 9 26 85 66 27 99 9 28 18 58 29 92 80 30 16 80 31 36 30 32 63 85 33 56 15 34 34 69 35 39 97 36 38 34 37 43 86 38 692 39 82 21 40 97 23 41 24 49 42 53 76 43 91 9 44 59 1 45 95 42 46 63 35 47 53 35 48 45 76 49 82 76 41 Coordinación y dimensionamiento de flota de drones en problemas TSP a través de Python Contamos con un total de 49 clientes, de los cuales únicamente 20 serán visitables por drones: 0, 5, 7, 10, 11, 12, 14, 15, 16, 23, 25, 27, 29, 30, 33, 36, 40, 44, 45 y 47. Para la aplicación del algoritmo, requerimos de convertir los datos de los clientes de modo que se indique la distancia relativa entre cada par de ellos. Con el fin de que concuerde con el dato utilizado que indica el tiempo requerido en la preparación del dron por parte del transportista, asumimos como igual la distancia como las unidades de tiempo empleadas en llegar del cliente i al j. Dicha conversión la realizamos a través del código basedatos, que se encuentra también en el anexo. 6.2.1 Resultados del GA Tomando diferentes semillas de números pseudoaleatorios, los resultados obtenidos tomando con rutas iniciales del camión trayectos generados por GA son los que se muestran en la tabla 6-2, en la cual se indica lo siguiente, por columnas de izquierda a derecha: iteraciones del algoritmo; ruta del camión tras la aplicación del GA, sin haber aún aplicado el algoritmo de inclusión de los drones; coste inicial para dicha ruta inicial del camión (en color verde aparece el mejor resultado, así como en rojo el peor); número de drones sometidos a estudios, con una tamaño máximo de flota de tres drones; los clientes visitados por alguno de los drones; porcentaje de clientes visitados por algún dron con respecto a los clientes potencialmente visitables, 20 en nuestro caso (de igual modo aparece en verde el mayor porcentaje y en rojo el menor); coste final tras la inclusión de los drones, con la misma distribución de colores mencionada en columnas anteriores; ahorro generado por la inclusión de los drones, calculado con la resta entre el coste de la ruta inicial y el coste tras la aparición de los drones, destacando en verde el máximo ahorro producido; número de drones utilizados con respecto a los disponibles paras los distintos tamaños de flota; y, por último, los clientes a los que se les ha cambiado de posición dentro de la ruta del camión. Resultados y Conclusión 42 Tabla 6-2. Resultados GA Iteraciones Ruta camión Coste inicial Drones Clientes visitados por dron %drones Coste final Ahorro Drones utilizados Cambio pos 1 45, 5, 12, 33, 15, 0 30% 839 74 Todos 2 45, 5, 12, 33, 15, 0,16, 25, 10, 14, 29 55% 779 134 Todos 3 45, 5, 12, 33, 15, 0,16, 25, 10, 14, 29,47 60% 775 138 Todos 1 45, 5, 33, 15, 0, 16, 10 35% 936 78 Todos 2 45, 5, 33, 15, 0, 16, 10, 44, 7, 40, 27, 29, 47 65% 845 169 Todos 3 45, 5, 33, 15, 0, 16, 10, 44, 7, 40, 27, 29, 47 65% 845 169 Sólo 1 y 2 1 45, 12, 36, 11, 15, 0, 25 35% 1059 81 Todos 2 45, 12, 36, 11, 15, 0, 25,10, 7, 14, 27, 29 60% 981 159 Todos 3 45, 12, 36, 11, 15, 0, 25,10, 7, 14, 27, 29 60% 981 159 Sólo 1 y 2 1 5, 11, 0, 25, 10, 44 30% 991 38 Todos 2 5, 11, 0, 25, 10, 44, 7, 14, 47 45% 937 92 Todos 30 3 5, 11, 0, 25, 10, 44, 7, 14, 47 45% 937 92 Sólo 1 y 2 30 1 12, 33, 0, 10, 44, 14, 27 35% 888 154 Todos 40 2 12, 33, 0, 10, 44, 14, 27, 29 40% 885 157 Todos 40 3 12, 33, 0, 10, 44, 14, 27, 29 40% 885 157 Sólo 1 y 2 40 1 45, 5, 12, 33, 36, 11, 25 35% 835 57 Todos 2 45, 5, 12, 33, 36, 11, 25, 0, 10, 23, 30, 27 60% 762 130 Todos 44 3 45, 5, 12, 33, 36, 11, 25, 0, 10, 23, 30, 27,29 65% 759 133 Todos 44 1 5, 12, 33, 0, 16 25% 883 47 Todos 2 5, 12, 33, 0, 16,25, 10, 44, 40, 27 50% 791 139 Todos 3 5, 12, 33, 0, 16,25, 10, 44, 40, 27 50% 791 139 Sólo 1 y 2 1 5, 12, 33, 11, 0 25% 878 69 Todos 2 5, 12, 33, 11, 0,16, 10, 23, 14, 30, 29 55% 818 129 Todos 3 5, 12, 33, 11, 0,16, 10, 23, 14, 30, 29 55% 818 129 Sólo 1 y 2 1 45, 5, 12, 33, 15, 0, 25 35% 874 104 Todos 16 2 45, 5, 12, 33, 15, 0, 25,10, 44, 14, 40, 27 60% 713 265 Todos 16 3 45, 5, 12, 33, 15, 0, 25,10, 44, 14, 40,27 60% 713 265 Todos 16 1 5, 0, 16, 25, 10, 44, 23 35% 965 74 Todos 30 2 5, 0, 16, 25, 10, 44, 23,14, 30, 40, 27, 29 60% 884 155 Todos 47 3 5, 0, 16, 25, 10, 44, 23,14, 30, 40, 27, 29 60% 884 155 Sólo 1 y 2 47 1 45, 5, 12, 33, 36, 15 30% 846 112 Todos 25 2 45, 5, 12, 33, 36, 15,0, 16, 25, 10, 27 55% 771 187 Todos 3 45, 5, 12, 33, 36, 15,0, 16, 25, 10, 30,23, 14, 40, 27 75% 717 241 Todos 1 5, 12, 33, 0, 25, 10, 47 35% 1003 137 Todos 36 2 5, 12, 33, 0, 25, 10, 47,44, 7, 14, 40, 29 60% 873 267 Todos 27,36 3 5, 12, 33, 0, 25, 10, 47,44, 7, 14, 40, 29 60% 873 267 Sólo 1 y 2 27,36 1 45, 5, 12, 36, 11, 15, 0 35% 952 69 Todos 2 45, 5, 12, 36, 11, 15, 0,16, 25, 10, 23, 14 60% 867 154 Todos 3 45, 5, 12, 36, 11, 15, 0,16, 25, 10, 23, 14,30, 27, 29, 47 80% 818 203 Todos 1 5, 11, 0, 16, 25 25% 918 35 Todos 2 5, 11, 0, 16, 25,10, 23, 14, 30, 40, 27 55% 820 133 Todos 47 3 5, 11, 0, 16, 25,10, 23, 14, 30, 40, 27,47 60% 817 136 Todos 1 45, 5, 12, 0, 25, 10, 27 35% 910 94 Todos 2 45, 5, 12, 0, 25, 10, 27,14, 29 45% 881 123 Todos 3 45, 5, 12, 0, 25, 10, 27,14, 29 45% 881 123 Sólo 1 y 2 1 5, 33, 15, 0, 16, 10 30% 812 89 Todos 30 2 5, 33, 15, 0, 16, 10,7, 23, 14, 30, 40, 27 60% 726 175 Todos 3 5, 33, 15, 0, 16, 10, 7, 23, 14, 30, 40, 27, 29 65% 723 178 Todos 1 45, 5, 12, 33, 36, 11, 0 35% 931 84 Todos 2 45, 5, 12, 33, 36, 11, 0, 16, 25, 10, 44, 7, 14, 40 70% 810 205 Todos 47, 30 3 45, 5, 12, 33, 36, 11, 0, 16, 25, 10, 44, 7, 14, 40, 27, 29 80% 772 243 Todos 47, 30 1 45, 5, 33, 15, 0, 25, 10 35% 970 68 Todos 2 45, 5, 33, 15, 0, 25, 10, 7, 23, 14, 30, 29 60% 861 177 Todos 3 45, 5, 33, 15, 0, 25, 10, 7, 23, 14, 30, 29 60% 861 177 Sólo 1 y 2 1 45, 5, 12, 33, 0, 25, 30 35% 885 129 Todos 2 45, 5, 12, 33, 0, 25, 30, 10, 14, 40 50% 827 187 Todos 3 45, 5, 12, 33, 0, 25, 30, 10, 14, 40 50% 827 187 Sólo 1 y 2 1 45, 5, 12, 33, 11, 15, 0, 16 40% 1050 85 Todos 23 2 45, 5, 12, 33, 11, 15, 0, 16, 25, 10, 23, 27, 47 65% 985 150 Todos 3 45, 5, 12, 33, 11, 15, 0, 16, 25, 10, 23, 27, 47 65% 985 150 Sólo 1 y 2 1140 [11, 36, 29, 33, 15, 20, 19, 48, 18, 34, 1, 31, 40, 24, 0, 32, 28, 10, 5, 26, 42, 6, 23, 14, 13, 30, 35, 46, 22, 12, 9, 44, 39, 45, 3, 37, 27, 16, 7, 43, 17, 38, 2, 21, 25, 41, 4, 8, 47] 1029 [46, 6, 43, 32, 24, 0, 22, 31, 41, 4, 8, 11, 2, 38, 17, 7, 42, 26, 39, 21, 12, 25, 19, 20, 45, 16, 23, 14, 3, 1, 37, 29, 27, 35, 13, 40, 33, 47, 36, 34, 10, 28, 48, 5, 44, 9, 18, 15, 30] 913 [18, 45, 38, 2, 5, 12, 20, 33, 1, 3, 34, 36, 11, 4, 22,15, 46, 24, 0, 43, 16, 17, 26, 42, 25, 19, 48, 10, 28, 9,44,21 39, 7, 6, 32, 23, 14, 13, 30, 35, 40, 27, 37, 29, 8, 47, 41, 31] 1014 [13, 30, 46, 45, 12, 25, 48, 19, 5, 44, 2, 22, 4, 8, 11, 33, 15, 17, 26, 42, 7, 6, 32, 23, 0, 14, 24, 29, 37, 3, 36, 41, 20, 31, 18, 47, 27, 35, 16, 43, 38, 39, 21, 9, 28, 10, 34, 1, 40] 930 [22, 15, 40, 46, 16, 23, 14, 0, 24, 13, 30, 35, 32, 6, 7, 38, 39, 26, 42, 45, 27, 29, 37, 3, 33, 4, 19, 28, 25, 44, 9, 2, 21, 17, 43, 10, 18, 8, 41, 1, 34, 36, 11, 47, 31, 48, 5, 12, 20] 947 [23, 35, 15, 33, 4, 41, 12, 19, 31, 18, 20, 9, 44, 21, 39, 7, 32, 6, 0, 24, 14, 30, 13, 40, 27, 37, 3, 29, 8, 11, 22, 45, 2, 5, 25, 48, 28, 10, 34, 1, 36, 47, 42, 26, 17, 38, 16, 46, 43] 1042 [12, 48, 31, 41, 33, 22, 46, 9, 5, 25, 19, 10, 28, 2, 38, 7, 24, 0, 15, 18, 34, 1, 36, 4, 8, 20, 45, 23, 14, 40, 35, 30, 13, 27, 3, 37, 29, 47, 11, 16, 6, 32, 43, 17, 21, 39, 26, 42, 44] 892 [8, 29, 37, 3, 1, 34, 47, 4, 11, 36, 31, 18, 20, 46, 6, 17, 42, 9, 5, 19, 48, 10, 28, 12, 45, 22, 15, 33, 27, 40, 30, 13, 24, 0, 14, 32, 43, 23, 35, 16, 7, 39, 38, 2, 26, 21, 44, 25, 41] 958 [35, 30, 16, 23, 14, 40, 1, 3, 37, 29, 27, 33, 22, 42, 26, 39, 9, 44, 21, 2, 6, 32, 43, 17, 38, 7, 45, 46, 13, 24, 0, 20, 48, 28, 10, 5, 12, 25, 41, 4, 47, 36, 11, 8, 19, 31, 18, 34, 15] 1140 [28, 25, 19, 31, 48, 22, 45, 38, 17, 42, 26, 46, 33, 47, 41, 34, 3, 1, 36, 37, 13, 30, 35, 9, 44, 20, 40, 27, 29, 18, 12, 2, 21, 39, 7, 43, 23, 0, 24, 14, 4, 8, 11, 15, 6, 32, 16, 5, 10] 978 [15, 16, 32, 43, 35, 29, 37, 3, 34, 1, 36, 19, 48, 10, 18, 31, 47, 11, 41, 21, 9, 28, 12, 20, 45, 40, 27, 25, 5, 44, 2, 38, 39, 42, 26, 17, 7, 30, 13, 14, 0, 24, 23, 6, 46, 22, 8, 4, 33] 1039 [5, 25, 28, 10, 41, 4, 46, 16, 7, 38, 2, 21, 39, 26, 42, 0, 24, 35, 13, 23, 14, 32, 17, 9, 44, 12, 19, 31, 22, 30, 40, 27, 29, 11, 47, 37, 34, 36, 8, 48, 18, 3, 1, 33, 15, 6, 43, 45, 20] 1004 [13, 35, 2, 7, 16, 14, 23, 6, 46, 28, 10, 31, 20, 19, 12, 25, 48, 41, 34, 36, 11, 8, 33, 27, 40, 30, 32, 43, 17, 39, 26, 42, 38, 45, 21, 44, 9, 5, 18, 4, 15, 0, 24, 37, 29, 3, 1, 47, 22] 901 [28, 10, 31, 18, 41, 8, 4, 40, 27, 33, 3, 34, 1, 36, 47, 11, 29, 37, 46, 45, 9, 5, 19, 44, 21, 2, 38, 14, 23, 13, 24, 0, 35, 30, 16, 22, 15, 7, 43, 32, 6, 17, 42, 26, 39, 20, 12, 25, 48] 1021 [47, 4, 18, 48, 25, 5, 19, 41, 8, 37, 1, 34, 3, 29, 33, 22, 23, 30, 35, 27, 40, 15, 2, 20, 12, 28, 10, 45, 46, 32, 16, 7, 38, 6, 13, 14, 24, 0, 43, 42, 26, 39, 17, 21, 44, 9, 31, 36, 11] 953 [14, 24, 0, 43, 7, 2, 21, 9, 12, 20, 31, 18, 41, 25, 48, 5, 44, 39, 17, 38, 42, 26, 45, 46, 22, 29, 37, 3, 11, 33, 40, 35, 16, 32, 6, 13, 27, 34, 1, 36, 47, 10, 28, 19, 4, 8, 15, 30, 23] 1014 [45, 2, 20, 41, 8, 4, 11, 47, 1, 36, 18, 31, 19, 25, 10, 28, 12, 5, 48, 34, 3, 37, 33, 29, 27, 24, 0, 23, 43, 14, 13, 7, 42, 26, 17, 40, 15, 9, 44, 21, 38, 39, 22, 30, 35, 6, 32, 16, 46] 1135 [39, 7, 45, 16, 6, 25, 19, 20, 31, 18, 41, 47, 36, 1, 34, 8, 11, 4, 22, 21, 38, 17, 14, 24, 0, 2, 44, 9, 5, 30, 13, 29, 37, 3, 48, 28, 10, 12, 15, 35, 23, 42, 26, 43, 32, 40, 27, 33, 46] 1015 [27, 15, 22, 45, 32, 6, 14, 23, 16, 46, 47, 8, 4, 11, 2, 26, 39, 21, 38, 7, 41, 31, 18, 44, 9, 28, 10, 48, 19, 5, 12, 25, 20, 35, 13, 40, 24, 0, 30, 43, 42, 17, 33, 1, 34, 36, 3, 29, 37] 1038 [18, 1, 34, 37, 3, 36, 11, 47, 41, 15, 22, 45, 16, 6, 32, 7, 43, 39, 26, 42, 17, 14, 23, 30, 46, 8, 33, 35, 13, 40, 27, 29, 4, 28, 10, 20, 12, 25, 9, 44, 2, 0, 24, 38, 21, 5, 48, 19, 31] 2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15 18 17 20 19 43 Coordinación y dimensionamiento de flota de drones en problemas TSP a través de Python Como inicio de análisis de los resultados obtenidos, observamos que el mayor coste de las rutas iniciales del camión, extraídas directamente del GA, es de 1.140 unidades temporales, por las 892 u.t. del mínimo coste. Asimismo, observamos un coste promedio del TSP clásico de 1.005,15 u.t. con una desviación típica de 74,25 u.t., parámetros que serán relevantes para la comparación con los resultados del ACO. Resulta importante resaltar que en una primera instancia se comenzó el estudio para una flota máxima de cuatro drones. Debido a la dimensión del problema tratado (49 nodos), escasas veces era utilizado el cuarto dron, no porporcionándonos información relevante para la experimentación, por lo que se decidió limitarlo a tres drones máximo. Figura 6-1. Ejemplo de visita del cliente 47 por el dron 1 en Python En el caso de que únicamente utilicemos un dron, resulta reseñable el porcentaje de clientes visitados por el dron con respecto a los potencialmente visitables, el cual es de media aproximadamente un 35%, teniendo incluso mínimos del 25%. Diferente situación se presenta para dos y tres drones, donde dicho porcentaje ronda de media el 60% con máximos de hasta 80%. En la última columna de la tabla se muestran los clientes que han sido cambiados de posición dentro de la ruta del camión. Bajo este concepto podemos observar que, normalmente, se producen mayores ahorros visitando un cliente con el dron que cambiando dicho cliente de posición. Esto lo podemos ver por ejemplo en la iteración 14, donde para dos drones el cliente 47 no podía ser visitado por ninguno de ellos, por estar ambos en vuelo, por lo que se decide cambiarlo de posición. En cambio, al sumar el tercer dron, éste si puede visitarlo produciéndose un ahorro mayor. El mayor ahorro, de 267 u.t., se produce en la iteración donde el coste inicial de la ruta del camión era mayor. Para concluir, observamos que, de las 20 experimentaciones realizadas, en 12 de ellas el tercer dron no es requerido, constando, en promedio, un ahorro de únicamente 7,7 u.t. si se utilizan tres drones en lugar de dos, frente al ahorro de 88,15 u.t. si se utilizan tres drones en vez de uno o de 80,45 u.t. de dos drones en lugar de uno. Teniendo en cuenta los costes de adquisición de un dron, mantenimiento, baterías, licencias, etc, que quedan fuera del alcance de este TFG, a la vista de los resultados, para este dimensionamiento del problema lo más lógico sería la utilización de dos drones para el reparto a los clientes. Figura 6-2. Ejemplo resultados en Python para dos drones Resultados y Conclusión 44 6.2.2 Resultado del ACO Tabla 6-3. Resultados ACO Iteraciones Ruta camión Coste inicial Drones Clientes visitados por dron %drones Coste final Ahorro Drones utilizados Cambio pos 1 45, 5, 0, 25, 10 25% 565 43 Todos 27 2 45, 5, 0, 25, 10, 7, 27, 29 40% 538 70 Todos 3 45, 5, 0, 25, 10, 7, 27, 29 40% 538 70 Sólo 1 y 2 1 45, 5, 33, 15, 0 25% 593 51 Todos 2 45, 5, 33, 15, 0, 25, 10, 7, 14, 40 50% 550 94 Todos 3 45, 5, 33, 15, 0, 25, 10, 7, 14, 40 50% 550 94 Sólo 1 y 2 1 45, 5, 0, 16 20% 599 30 Todos 2 45, 5, 0, 16, 25, 10, 40, 27, 29 45% 534 95 Todos 3 45, 5, 0, 16, 25, 10, 40, 27, 29 45% 534 95 Todos 1 45, 12, 33, 15, 0, 10 30% 573 58 Todos 2 45, 12, 33, 15, 0, 10, 7, 23, 14, 40 50% 528 103 Todos 3 45, 12, 33, 15, 0, 10, 7, 23, 14, 40 50% 528 103 Sólo 1 y 2 1 45, 12, 15, 0 20% 630 33 Todos 2 45, 12, 15, 0, 10, 7, 23, 14 40% 564 99 Todos 27, 40 3 45, 12, 15, 0, 10, 7, 23, 14, 40, 27 50% 540 123 Todos 1 45, 5, 33, 15, 0, 25 30% 609 33 Todos 2 45, 5, 33, 15, 0, 25, 10, 7, 29 45% 552 90 Todos 3 45, 5, 33, 15, 0, 25, 10, 7, 29 45% 552 90 Sólo 1 y 2 1 45, 5, 15, 0, 16 25% 603 35 Todos 2 45, 5, 15, 0, 16, 25, 10, 27, 29 45% 563 75 Todos 3 45, 5, 15, 0, 16, 25, 10, 27, 29 45% 563 75 Sólo 1 y 2 1 45, 12, 33, 15, 0 25% 571 69 Todos 29 2 45, 12, 33, 15, 0, 10, 7 35% 556 84 Todos 29 3 45, 12, 33, 15, 0, 10, 7 35% 556 84 Sólo 1 y 2 29 1 45, 5, 0, 16, 25 25% 598 35 Todos 2 45, 5, 0, 16, 25, 10, 44, 40 40% 579 54 Todos 3 45, 5, 0, 16, 25, 10, 44, 40, 27, 29 50% 540 93 Todos 1 45, 0, 16, 25, 10 25% 566 59 Todos 2 45, 0, 16, 25, 10, 7, 40, 27, 29 45% 511 114 Todos 3 45, 0, 16, 25, 10, 7, 40, 27, 29 45% 511 114 Sólo 1 y 2 1 45, 5, 33, 15, 40 25% 535 48 Todos 2 45, 5, 33, 15, 40, 0, 25 35% 525 58 Todos 3 45, 5, 33, 15, 40, 0, 25, 10, 7, 27 50% 498 85 Todos 1 45, 5, 36, 15 20% 569 33 Todos 2 45, 5, 36, 15, 0, 25, 10 35% 547 55 Todos 3 45, 5, 36, 15, 0, 25, 10, 7, 40, 27 50% 501 101 Todos 1 45, 12, 33, 15, 0, 10 30% 556 52 Todos 2 45, 12, 33, 15, 0, 10, 7 35% 516 92 Todos 3 45, 12, 33, 15, 0, 10, 7 35% 516 92 Todos 1 45, 12, 33, 15, 0 25% 577 55 Todos 2 45, 12, 33, 15, 0, 10, 7, 23 40% 557 75 Todos 3 45, 12, 33, 15, 0, 10, 7, 23, 14, 30, 29 55% 518 114 Todos 1 45, 12, 33, 15, 0, 10 30% 556 60 Todos 2 45, 12, 33, 15, 0, 10, 7 35% 516 100 Todos 3 45, 12, 33, 15, 0, 10, 7 35% 516 100 Sólo 1 y 2 1 45, 5, 33, 0, 16 25% 533 48 Todos 2 45, 5, 33, 0, 16, 25, 10, 40, 27 45% 494 87 Todos 3 45, 5, 33, 0, 16, 25, 10, 40, 27, 29 50% 457 124 Todos 1 45, 12, 33, 0, 10 25% 533 62 Todos 2 45, 12, 33, 0, 10, 7, 40, 27 40% 509 86 Todos 3 45, 12, 33, 0, 10, 7, 40, 27 40% 509 86 Sólo 1 y 2 1 45, 5, 33, 36, 15, 25 30% 565 39 Todos 2 45, 5, 33, 36, 15, 25, 0, 10, 7 45% 527 77 Todos 3 45, 5, 33, 36, 15, 25, 0, 10, 7 45% 527 77 Sólo 1 y 2 1 45, 5, 36, 15 20% 545 85 Todos 2 45, 5, 36, 15, 0, 25, 10, 40 40% 501 129 Todos 3 45, 5, 36, 15, 0, 25, 10, 40, 7, 27 50% 476 154 Todos 1 45, 5, 12, 33, 0, 10 30% 582 53 Todos 2 45, 5, 12, 33, 0, 10, 44, 7, 23, 14, 40 55% 531 104 Todos 3 45, 5, 12, 33, 0, 10, 44, 7, 23, 14, 40 55% 531 104 Sólo 1 y 2 629 [10, 48, 19, 25, 12, 5, 9, 44, 21, 39, 26, 42, 17, 38, 2, 7, 45, 16, 6, 32, 43, 23, 14, 0, 24, 13, 30, 35, 46, 22, 15, 40, 27, 33, 11, 47, 8, 4, 41, 18, 31, 36, 1, 34, 3, 29, 37, 20, 28] 631 [45, 46, 16, 6, 32, 43, 17, 38, 2, 21, 39, 26, 42, 7, 44, 9, 5, 25, 12, 19, 48, 28, 10, 31, 18, 41, 8, 47, 11, 4, 33, 15, 22, 35, 30, 13, 23, 14, 0, 24, 40, 27, 29, 37, 3, 34, 1, 36, 20] 608 [28, 10, 48, 19, 25, 12, 5, 9, 44, 21, 39, 26, 42, 17, 38, 2, 7, 45, 46, 16, 6, 32, 43, 23, 14, 0, 24, 13, 30, 35, 40, 27, 33, 4, 8, 47, 11, 41, 18, 31, 36, 1, 34, 3, 29, 37, 15, 22, 20] 644 [34, 1, 36, 11, 47, 8, 4, 41, 31, 18, 48, 28, 10, 20, 19, 25, 12, 5, 9, 44, 21, 39, 26, 42, 17, 38, 2, 7, 45, 46, 16, 6, 32, 43, 23, 14, 13, 30, 35, 15, 22, 0, 24, 40, 27, 33, 29, 37, 3] 638 [35, 30, 13, 40, 27, 33, 11, 47, 8, 4, 41, 18, 31, 48, 28, 10, 20, 19, 25, 12, 5, 9, 44, 21, 39, 26, 42, 17, 38, 2, 7, 16, 6, 32, 43, 23, 14, 0, 24, 29, 37, 3, 34, 1, 36, 15, 22, 46, 45] 640 [22, 46, 45, 16, 6, 32, 43, 7, 38, 2, 21, 39, 26, 42, 17, 44, 9, 5, 25, 12, 19, 48, 28, 10, 31, 18, 41, 8, 47, 11, 4, 33, 36, 1, 34, 3, 29, 37, 27, 40, 15, 35, 30, 13, 24, 0, 14, 23, 20] 663 [13, 30, 35, 15, 22, 46, 16, 6, 32, 43, 7, 38, 2, 21, 39, 26, 42, 17, 44, 9, 5, 25, 12, 19, 48, 28, 10, 31, 18, 41, 8, 47, 11, 4, 33, 27, 40, 29, 37, 3, 34, 1, 36, 20, 45, 24, 0, 14, 23] 642 [8, 29, 37, 3, 1, 34, 47, 4, 11, 36, 31, 18, 20, 46, 6, 17, 42, 9, 5, 19, 48, 10, 28, 12, 45, 22, 15, 33, 27, 40, 30, 13, 24, 0, 14, 32, 43, 23, 35, 16, 7, 39, 38, 2, 26, 21, 44, 25, 41] 583 [3, 1, 34, 36, 47, 11, 8, 4, 41, 18, 31, 10, 28, 48, 19, 25, 12, 20, 5, 9, 44, 21, 39, 26, 42, 17, 38, 2, 7, 45, 46, 16, 6, 32, 43, 23, 14, 0, 24, 13, 30, 35, 15, 22, 33, 40, 27, 29, 37] 602 [48, 19, 25, 12, 5, 9, 44, 21, 39, 26, 42, 17, 38, 2, 7, 45, 46, 16, 6, 32, 43, 23, 14, 0, 24, 13, 30, 35, 15, 22, 20, 28, 10, 31, 18, 41, 8, 47, 11, 4, 33, 27, 40, 29, 37, 3, 1, 34, 36] 633 [21, 39, 26, 42, 17, 38, 2, 7, 16, 6, 32, 43, 23, 14, 0, 24, 13, 30, 35, 46, 45, 22, 15, 40, 27, 33, 8, 47, 11, 4, 41, 18, 31, 36, 1, 34, 3, 29, 37, 10, 28, 48, 19, 25, 12, 20, 5, 9, 44] 625 [16, 6, 32, 43, 23, 14, 0, 24, 13, 30, 35, 46, 45, 22, 15, 40, 27, 33, 11, 47, 8, 4, 41, 18, 31, 36, 1, 34, 3, 29, 37, 20, 12, 25, 19, 48, 28, 10, 5, 9, 44, 21, 39, 26, 42, 17, 38, 2, 7] 616 [39, 26, 42, 17, 38, 2, 21, 44, 9, 5, 25, 12, 19, 48, 28, 10, 31, 18, 41, 8, 47, 11, 4, 33, 15, 22, 46, 45, 16, 6, 32, 43, 23, 14, 0, 24, 13, 30, 35, 40, 27, 29, 37, 3, 34, 1, 36, 20, 7] 581 [37, 3, 34, 1, 36, 11, 47, 8, 4, 41, 18, 31, 48, 28, 10, 20, 19, 25, 12, 5, 9, 44, 21, 39, 26, 42, 17, 38, 2, 7, 45, 16, 6, 32, 43, 23, 14, 0, 24, 13, 30, 35, 46, 22, 15, 40, 27, 33, 29] 608 [2, 38, 17, 42, 26, 39, 21, 44, 9, 5, 25, 12, 19, 48, 28, 10, 31, 18, 41, 8, 47, 11, 4, 33, 15, 22, 46, 16, 6, 32, 43, 23, 14, 0, 24, 13, 30, 35, 40, 27, 29, 37, 3, 34, 1, 36, 20, 45, 7] 632 [14, 23, 30, 35, 46, 45, 16, 6, 32, 43, 7, 38, 2, 21, 39, 26, 42, 17, 44, 9, 5, 25, 12, 19, 48, 28, 10, 31, 18, 41, 8, 47, 11, 4, 33, 15, 22, 20, 36, 1, 34, 3, 29, 37, 27, 40, 13, 0, 24] 630 [9, 44, 21, 39, 26, 42, 17, 38, 2, 7, 45, 46, 16, 6, 32, 43, 23, 14, 0, 24, 13, 30, 35, 15, 22, 20, 12, 25, 19, 48, 28, 10, 18, 31, 41, 8, 47, 11, 4, 33, 27, 40, 29, 37, 3, 1, 34, 36, 5] 635 [22, 46, 45, 16, 6, 32, 43, 7, 17, 38, 2, 21, 39, 26, 42, 9, 44, 5, 25, 12, 19, 48, 28, 10, 31, 18, 41, 8, 47, 11, 4, 33, 15, 35, 30, 13, 14, 23, 0, 24, 40, 27, 29, 37, 3, 34, 1, 36, 20] 595 [26, 42, 17, 7, 38, 2, 21, 39, 44, 9, 5, 25, 12, 19, 48, 28, 10, 31, 18, 41, 4, 8, 47, 11, 36, 34, 1, 3, 37, 29, 27, 40, 33, 15, 22, 46, 45, 16, 6, 32, 43, 23, 14, 0, 24, 13, 30, 35, 20] 604 [41, 8, 47, 11, 4, 33, 15, 22, 46, 16, 6, 32, 43, 23, 14, 0, 24, 13, 30, 35, 40, 27, 29, 37, 3, 1, 34, 36, 18, 31, 48, 19, 25, 12, 5, 9, 44, 21, 39, 26, 42, 17, 38, 2, 7, 45, 20, 28, 10] 2 1 4 3 6 5 8 7 10 9 12 11 20 19 14 13 16 15 18 17 45 Coordinación y dimensionamiento de flota de drones en problemas TSP a través de Python La estructura de la tabla 6-3, en la cual se muestran los resultados tras la aplicación del ACO para la obtención de las rutas iniciales, es idéntica a la tabla 6-2, explicada anteriormente. Como ya hicimos en el caso del GA, analicemos primero los resultados de la ruta del camión, previa inclusión de drones. En este caso, el mayor coste de entre las rutas obtenidas es de 663 u.t. frente a las 581 u.t. del menor coste. Además, según ACO, en promedio el camión tarda en visitar todos los clientes aproximadamente 622 u.t., con una desviación típica entre las muestras seleccionadas de aproximadamente 21,55 u.t. Estos resultados ponen de manifiesto la primera conclusión que conseguimos a través del algoritmo, y es que el Algoritmo de Colonia de Hormigas obtiene mejores resultados que el Algoritmo Genético para un TSP clásico, sobre la base de datos de estudio. Por ello, en promedio, el costo aplicando el ACO es de aproximadamente 400 u.t. menos, además de producirse una menor fluctuación entre las distintas iteraciones. Figura 6-3. Ejemplo ruta del camión con ACO Cabe destacar el bajo número de clientes a los cuales se les cambia de posición dentro de la ruta del camión con respecto a los mismos tras emplear GA. Al ser capaz el ACO de obtener mejores resultados que el GA, esto implica que el trayecto del camión resultante se encuentra más próximo al óptimo del problema, por lo que será más complicado encontrar cambios en las posiciones de los clientes que disminuyan el coste final. Misma explicación encontramos como respuesta a la bajada en cuanto a porcentaje de clientes visitados por drones con respecto a los potencialmente visitables. Como podemos observar, para dos o tres drones como máximo se visitan el 55% de los clientes a los que el dron puede acceder, frente al 80% obtenido con el GA. Asimismo, para un único dron, se dan mínimos de hasta un 20%. El mayor ahorro producido es de 154 u.t., considerablemente menor a las 267 u.t. del GA, lo cual se puede explicar, al igual que en los párrafos anteriores, por una mejor aproximación inicial por parte del ACO Anexo 52 ANEXO • Basedatos: #Algoritmo para mostrar los datos como la diferencia relativa entre los clientes, siendo a una lista con las X de los clientes, y b una con las Y mapa=[] n=49 for x in range(0,n): mapa.append([]) for x in range(0,n): for y in range(0,n): numero=math.sqrt((a[x]-a[y])**2+(b[x]-b[y])**2) redondeado=round(numero) mapa[x].append(redondeado) • calcSavings: def calcSavings(j): #Calcularemos el ahorro de quitar j de la ruta de camiones de un modo distinto al calculado en el código para un solo dron, debido a que se complica en exceso para varios drones ttruck_savings=[] truckRoutes_savings= truckRoutes[:] #Copiamos la ruta del camión en una nueva lista y eliminamos el cliente j truckRoutes_savings.remove(j) #Calculamos los tiempos de llegada a cada nodo sin el cliente j for i in range(0,len(truckRoutes_savings)): if (i==0): ttruck_savings.append(0) else: a=ttruck_savings[i-1]+t[truckRoutes_savings[i-1]][truckRoutes_savings[i]] ttruck_savings.append(a) #Los savings serán la diferencia entre el coste de llegar al último nodo con o sin j savings= ttruck[-1]-ttruck_savings[-1] 53 Coordinación y dimensionamiento de flota de drones en problemas TSP a través de Python return savings • calCostTruck: #Calcula el coste de insertar j en una posición distinta de la ruta del camión def calCostTruck (j,subruta): #Vemos cuales son los nodos de inicio y fin de la subruta, necesarios para el calculo posterior de ver si la autonomía del dron es suficiente a=subruta[0] maxsavings=0 iprima=0 kprima=0 servedbyUAV = False indicea=truckRoutes.index(a) b=subruta[-1] indiceb=truckRoutes.index(b) #El for calcula el coste de meterlo entre x y x+1, de la ruta for x in range(indicea,indiceb): cost=t[truckRoutes[x]][j]+t[j][truckRoutes[x+1]]-t[truckRoutes[x]][truckRoutes[x+1]] #Primero hay que comprobar que lo que te gastas es menor de lo que te ahorras if (cost<savings): #Comprobamos que el UAV puede seguir volando ese tiempo if (ttruck[indiceb]-ttruck[indicea]+cost<=e): #y vemos si la diferencia entre ahorro y coste es mayor que el máximo ahorro, haciendo rentable la operación if(savings-cost>maxsavings): servedbyUAV=False maxsavings=savings-cost iprima=truckRoutes[x] kprima=truckRoutes[x+1] return maxsavings,j,iprima,kprima , servedbyUAV • calCostUAV: #calCostUAV calcula el coste de servir al cliente j con un dron Anexo 54 def calCostUAV(j,subruta): #Nodos de inicio y fin de la subruta, similar a calcCostTruck iprima=0 kprima=0 servedbyUAV=True a=subruta[0] maxsavings=0 indicea=truckRoutes.index(a) b=subruta[-1] indiceb=truckRoutes.index(b) #Doble for porque no sólo hay que tener en cuenta al inmediatamente después de x, sino todos los índices mayores que x for x in range(indicea,indiceb): for y in range(indicea,indiceb+1): #Para todo "x" que preceda a "y", siendo "j" distinto a "x" e "y" if (x<y and truckRoutes[y]!=j and truckRoutes[x]!=j): #Comprobamos si el dron tiene autonomía para ir al cliente "j" if (t[truckRoutes[x]][j]+t[j][truckRoutes[y]]<=e): #Tiempo que se tarda en llegar al nodo k (el situado en y en la ruta) si quitamos j: tprimay tprimay=0 for z in range(0,y): if j!= truckRoutes[z] and j!= truckRoutes[z+1]: tprimay += t[truckRoutes[z]][truckRoutes[z+1]] elif j== truckRoutes[z+1]: tprimay += t[truckRoutes[z]][truckRoutes[z+2]] # Después calculamos costes con esos máximos y comparamos savings y cost de forma muy similar a la anterior función cost=max(0,max((tprimay-ttruck[x])+sr,t[truckRoutes[x]][j]+t[j][truckRoutes[y]]+sr)- (tprimay-ttruck[x])) if savings-cost > maxsavings: maxsavings=savings-cost servedbyUAV=True iprima=truckRoutes[x] kprima=truckRoutes[y] return maxsavings,j,iprima,kprima, servedbyUAV 55 Coordinación y dimensionamiento de flota de drones en problemas TSP a través de Python • performUpdate: def performUpdate (j,kprima,iprima, servedbyUAV,inicio_subrutasUAV,indicef): #Tenemos que saber si el cliente "j" será visitado por un UAV o si se cambio su posición en la ruta, a través de la variable servedbyUAV #Todo lo realizaremos para el dron indicef, el dron con mayor ahorro del código principal if servedbyUAV==True: #Elimino el nodo "j" de los nodos pendientes de estudio del dron Cprimecopia.remove(j) newSubRoute=[] newSubRoute2=[] #Genero la subruta for h in range(truckRoutes.index(iprima),truckRoutes.index(kprima)+1): if (truckRoutes[h]!=j): newSubRoute.append(truckRoutes[h]) print("La nueva subruta asociada al vuelo del dron",indicef,"es",newSubRoute,"y el dron visita al cliente",j) #En el caso de que los nodos inicial y final de la nueva subruta sean dos puntos intermedios de la ruta del camión, se generan 3 subrutas, dos no visitadas por dron y una que sí, ahora genero la subruta de los nodos posteriores al nodo final de la nueva sub ruta final=truckRoutes[-1] for z in range(truckRoutes.index(kprima)+1,truckRoutes.index(final)+1): if (truckRoutes[z]!=j): newSubRoute2.append(truckRoutes[z]) #Elimino de las subrutas el nodo con el dron, y todos los elementos de las nuevas subrutas truckRoutes.remove(j) for l in newSubRoute: for y in range(0,len(subrutas.get(indicef))): if (l in subrutas.get(indicef)[y]): subrutas.get(indicef)[y].remove(l) for k in subrutas.keys(): for y in range(0,len(subrutas.get(k))): if (j in subrutas.get(k)[y]): subrutas.get(k)[y].remove(j) Anexo 56 for x in newSubRoute2: for y in range(0,len(subrutas.get(indicef))): if (x in subrutas.get(indicef)[y]): subrutas.get(indicef)[y].remove(x) #Añado la nueva subruta sin dron, las ordenaré posteriormente if newSubRoute2!=[]: subrutas.get(indicef).append(newSubRoute2) #Añado la nueva subruta a las subrutas subrutas.get(indicef).append(newSubRoute) #Genero una lista con todos los primeros nodos de las subrutas que tienen asociado un UAV. Contiene también los clientes visitados por el dron inicio_subrutasUAV[indicef].append(newSubRoute[0]) clientes_UAV[indicef].append(j) #Elimino posibles subrutas vacías, por si el punto de aterrizaje del dron es el punto final de la ruta del camión for z in range(0,len(subrutas.get(indicef))-1): if subrutas.get(indicef)[z] == []: subrutas.get(indicef).remove(subrutas.get(indicef)[z]) else: #Elimino la j de la actual truck sub route for k in range(0,len(subrutas)): for y in range(0,len(subrutas.get(k))): if (j in subrutas.get(k)[y]): subrutas.get(k)[y].remove(j) #La inserto entre i prima y k prima, sabiendo que son consecutivas if (kprima in subrutas.get(k)[y]): subrutas.get(k)[y].insert(subrutas.get(k)[y].index(kprima),j) #Elimino el cliente j de donde estaba en la ruta del camión y lo inserto en la nueva posición truckRoutes.remove(j) truckRoutes.insert(truckRoutes.index(kprima), j) #Borro la anterior ttruck y genero la nueva for i in range(0,len(ttruck)): for j in range(0,len(ttruck)): if (ttruck !=[]): 57 Coordinación y dimensionamiento de flota de drones en problemas TSP a través de Python ttruck.remove(ttruck[i]) for i in range(0,len(truckRoutes)): if (i==0): ttruck.append(0) else: a=ttruck[i-1]+t[truckRoutes[i-1]][truckRoutes[i]] ttruck.append(a) return • Inicialización: decision=[] #Cprime: Clientes visitables por el dron. Cprime = [45,5,12,33,36,11,15,0,16,25,10,44,7,23,14,30,40,27,29,47] ttruck= #Lista de tiempos de llegada a cada nodo maxsavings=0 savings=0 sr=2 #Valor adoptado para simular el coste temporal de recoger el dron y prepararlo para su despegue por parte del transportista. e=150 #Valor adoptado como autonomía del dron n=#Número de drones inicio_subrutasUAV=[] clientes_UAV=[] for x in range(0,n): inicio_subrutasUAV.append([]) for x in range(0,n): clientes_UAV.append([]) Cprimecopia= Cprime[:] print("Clientes a los que puede ir el dron",Cprimecopia) #Debido a que tenemos diferentes drones con distintas subrutas, tenemos que crear un diccionario de dimensión igual al número de drones, donde iremos sumando las distintas subrutas generadas en función del dron subrutas={} for x in range(0,n): subrutas[x]=[truckRoutes[:]] Anexo 58 • Código principal: for j in [45,5,12,33,36,11,15,0,16,25,10,44,7,23,14,30,40,27,29,47]: print ("Cliente a estudiar su visita con el dron",j) #Aplico la función calcSavings para calcular los ahorros calcSavings(j) savings=calcSavings(j) if (savings>0): #Por cada dron, evalúo si puedo servir al cliente con el dron o si puedo cambiarlo de posición en la ruta del camión. #Posteriormente, me quedo con el cambio del dron que suponga mayor ahorro for k in subrutas.keys(): for x in range(0,len(subrutas.get(k))): #Para cada subruta, suponiendo que los ahorros son positivos, si la subruta tiene un dron asociado y el cliente "j" no está en la subruta if (subrutas.get(k)[x][0] in inicio_subrutasUAV[k]) and j not in subrutas.get(k)[x]: calCostTruck(j,subrutas.get(k)[x]) maxsavings_if=calCostTruck(j,subrutas.get(k)[x])[0] iprima_if=calCostTruck(j,subrutas.get(k)[x])[2] kprima_if=calCostTruck(j,subrutas.get(k)[x])[3] servedbyUAV_if=calCostTruck(j,subrutas.get(k)[x])[4] #Si la subruta no tiene un dron asociado elif subrutas.get(k)[x][0] not in inicio_subrutasUAV[k]: calCostUAV(j,subrutas.get(k)[x]) maxsavings_else=calCostUAV(j,subrutas.get(k)[x])[0] iprima_else=calCostUAV(j,subrutas.get(k)[x])[2] kprima_else=calCostUAV(j,subrutas.get(k)[x])[3] servedbyUAV_else=calCostUAV(j,subrutas.get(k)[x])[4] #Para varias subrutas tengo que comprobar qué opción me da mayores ganancias if (maxsavings_if>maxsavings_else) and savings>0: maxsavings=maxsavings_if iprima=iprima_if kprima=kprima_if servedbyUAV= servedbyUAV_if 59 Coordinación y dimensionamiento de flota de drones en problemas TSP a través de Python print("Se ha cambiado al cliente",j,"de posición") decision.append([maxsavings,iprima,kprima,servedbyUAV]) elif savings>0: maxsavings=maxsavings_else iprima=iprima_else kprima=kprima_else servedbyUAV=servedbyUAV_else decision.append([maxsavings,iprima,kprima,servedbyUAV]) maximo=0 #En la lista decision he ido incluyendo sublistas cuyo primer elemento es los ahorros asociados al movimiento del dron del índice en cuestión #Tomo el de mayor ahorro for f in range(0,len(decision)): if decision[f][0]>maximo: indicef=f maximo=decision[f][0] maxsavings=decision[indicef][0] iprima=decision[indicef][1] kprima=decision[indicef][2] servedbyUAV=decision[indicef][3] if (maxsavings>0): performUpdate(j, kprima, iprima, servedbyUAV, inicio_subrutasUAV,indicef) maxsavings=0 maxsavings_else=0 maxsavings_if=0 for k in subrutas.keys(): for x in range(0,len(subrutas.get(k))): if subrutas.get(k)[x]==[]: subrutas.get(k).remove(subrutas.get(k)[x]) print ("Clientes que quedan como posibles visitas del dron",Cprimecopia) print("Nueva ruta del camión:",truckRoutes) print("Nuevos tiempos de llegada a cada nodo del camión",ttruck) print("Nodos de inicios de las subrutas en función del dron",inicio_subrutasUAV) print("Clientes visitados por drones",clientes_UAV) #Aquí ordeno las subrutas de modo que sigan la misma secuencia de la ruta del camión original Anexo 60 lista=[] for x in range(0,len(subrutas.get(indicef))): i_sub=truckRoutes.index(subrutas.get(indicef)[x][0]) lista.append([i_sub,subrutas.get(indicef)[x]]) lista.sort() for z in range (0,len(lista)): subrutas.get(indicef).remove(lista[z][1]) subrutas.get(indicef).insert(z, lista[z][1]) decision.clear() print("Las nuevas subrutas en función de los drones",subrutas,"\n") 61 Coordinación y dimensionamiento de flota de drones en problemas TSP a través de Python