Aplicación de algoritmos exactos y heurísticos al problema del viajante visible en la red logística de Amazon en Sevilla

Proyecto Fin de Carrera Ingeniería de Telecomunicación Formato de Publicación de la Escuela Técnica Superior de Ingeniería Autor: F. Javier Payán Somet Tutor: Juan José Murillo Fuentes Dep. Teoría de la Señal y Comunicaciones Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2013 Trabajo Fin de Grado Grado en Ingeniería en Tecnologías Industriales Aplicación de algoritmos exactos y heurísticos al problema del viajante visible en la red logística de Amazon en Sevilla Autor: Mercedes Arévalo Suárez Tutor: Manuel Ordoñez Sánchez Dpto. Matemática Aplicada II Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2021 Trabajo Fin de Grado Grado en Ingeniería en Tecnologías Industriales Aplicación de algoritmos exactos y heurísticos al problema del viajante visible en la red logística de Amazon en Sevilla Autor: Mercedes Arévalo Suárez Tutor: Manuel Ordoñez Sánchez Dpto. Matemática Aplicada II Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2021 Trabajo Fin de Grado: Aplicación de algoritmos exactos y heurísticos al problema del viajante visible en la red logística de Amazon en Sevilla Autor: Mercedes Arévalo Suárez Tutor: Manuel Ordoñez Sánchez El tribunal nombrado para juzgar el trabajo arriba indicado, compuesto por los siguientes profesores: Presidente: Vocal/es: Secretario: acuerdan otorgarle la calificación de: El Secretario del Tribunal Fecha: A mi familia, por su apoyo incondicional A mis amigos, por estar siempre presentes cualquiera la ocasión A Manuel Ordoñez, por su ayuda e interés para que esto saliera adelante A mi abuela Maruja, para ella me faltan palabras Resumen El problema del viajante es, desde hace muchas décadas, uno de los problemas de optimización más estudiados, a pesar de la aparente simplicidad de su enunciado. En este trabajo, se presenta aplicado a una cuestión de actualidad, la necesidad de las empresas de logística de optimizar sus rutas de reparto, máxime ante el aumento de pedidos online como consecuencia de la pandemia de COVID-19. Para ello, se presentará la red logística de Amazon en Sevilla, estudiando el caso en que un vehículo debe visitar cada uno de los pueblos seleccionados de un determinado distrito de la provincia una única vez, siendo su origen y final el centro logístico de la empresa en Dos Hermanas. Este procedimiento se aplicará de manera individual a los distritos Sur y Oeste (Aljarafe), y de manera conjunta a la comarca Noreste, permitiendo así observar la diferencia de comportamiento con conjuntos de mayor tamaño y, por tanto, con mayores distancias entre ellos. Pudiendo ser atacado por diferentes líneas, en este análisis se optará por comparar los resultados de aplicar algoritmos aproximados y metaheurísticos, por el método del vecino más próximo y colonia de hormigas, respectivamente. III 1 Introducción La llegada de Internet y los smartphones ha creado un cambio revolucionario en la manera de comprar. El e-commerce, o comercio electrónico, se define como la compra y venta de bienes y servicios a través de una red electrónica, principalmente Internet, donde los clientes acceden a una plataforma online donde realizar sus pedidos, cuyos cobros y pagos se gestionan de manera completamente electrónica. Estas transacciones comerciales se producen bien de empresa a empresa (B2B), de empresa a consumidor (B2C), de consumidor a consumidor o de consumidor a empresa; introduciendo en el mercado la novedad de ofrecer los bienes y servicios directamente al cliente sin intermediarios a través de una página web. [26] La historia del comercio electrónico empezó hace más de 40 años, paralelamente a la historia de Internet. El desarrollo del intercambio electrónico de datos en la década de los 60 preparó el camino para el comercio electrónico, pero no fue hasta mediados de los 90 que la llegada de la red informática mundial (más conocida como "WWW", por sus siglas en inglés) y los grandes avances en el ámbito del uso comercial de Internet dieron el impulso definitivo y permitieron la creación de las primeras plataformas e-commerce, como Amazon o eBay, en las que se profundizará más adelante. Siguiendo la historia del comercio electrónico hasta la actualidad, y con el comercio B2C como principal centro de estudio, es evidente que ha adquirido una importancia vital. El número de personas que utilizan los sitios web ha aumentado considerablemente, y lo continúa haciendo, siendo la introducción de los smartphones uno de los principales aceleradores. La figura 1.1, que muestra la evolución del volumen de negocio del comercio electrónico en España, respalda esta afirmación. El comercio electrónico ofrece a sus usuarios numerosos beneficios como una amplia variedad de productos, ahorro de tiempo, la entrega rápida de productos y las numerosas ofertas disponibles en Internet, por lo que resulta indudable que el número de usuarios continuará aumentando. [26] En este sentido, merece la pena mencionar la evolución de la sociedad, pues mientras antaño Internet fue una novedad por explorar para la población, en la actualidad ya existe toda una generación nacida en una era digital madurada. Conocida como generación Z (1997-2010), se define como digital nativa, pues ha sido altamente influenciada por la interacción online y la conectividad a Internet desde una edad muy temprana. Esta generación domina el uso de Internet y los smartphones, considerándola una zona de confort y, por consiguiente, con mayor tendencia a emplear este medio para sus compras. En efecto, representan el 40% de los consumidores electrónicos, y no harán más que aumentar. [7] Aun siendo un hecho incuestionable la tendencia creciente del número de usuarios del e-commerce desde hace años, cabe destacar el impulso recibido por la situación excepcional presente. La pandemia de COVID-19 cambió el mundo de manera repentina. El confinamiento se impuso y la humanidad se vio obligada a parar, no solo limitando el ocio, sino también las actividades más 1 2Capítulo 1. Introducción 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 1 2 3 4 5 ·104 Figura 1.1 Volumen de negocio del comercio electrónico B2C en España (millones de €). básicas y esenciales, pues el miedo al contagio instaba a evitar el contacto con otras personas. Estas circunstancias convirtieron al comercio electrónico en el gran aliado de los ciudadanos, pues permitía adquirir todos los productos que normalmente se compran en tiendas tradicionales sin la necesidad de salir de casa. Así, la naturaleza del negocio cambió por completo. Según la investigación llevada a cabo por Jílková et Al. [ 22 ], el comportamiento de los clientes se vio influenciado tanto por la pandemia en sí misma, como por las restricciones gubernamentales de cada país. Consumidores de todas las cohortes generacionales estudiadas, desde la Silenciosa (1928- 1945) hasta la Alfa (2011 – presente), declararon haber adquirido bienes y servicios digitalmente en mayor proporción durante la crisis de COVID-19, si bien la del Baby Boom (1946-1964) fue la principal impulsora del crecimiento del comercio electrónico. Hubo un cambio considerable hacia el gasto digital, ya que el 43% de todos los encuestados había comprado en línea desde que comenzó la crisis COVID-19, en comparación con el 12% antes de la crisis. Este crecimiento concentrado tiene sentido considerando, como se ha indicado anteriormente, que generaciones más recientes, como la Z o incluso la Y (1983 – 1996), ya tenían un cierto hábito de compra electrónica y margen de crecimiento era menor. Asimismo, los efectos del coronavirus difieren según la naturaleza de los productos. Es decir, aunque el comercio digital creció considerablemente, el impacto del COVID-19 en algunos productos es muy alto, pero en otros no tanto. Además, no todos ellos reciben un impacto positivo. [9] A nivel de industria, la revolución del e-commerce ha generado una cantidad infinita de nuevas oportunidades. Permite a los negocios tradicionales y de menor tamaño adquirir una posición competitiva, si bien no exento de dificultades, pues supone un enorme reto logístico[ 24 ]. La logística en el comercio electrónico es el nexo entre vendedor y cliente, sustituyendo junto a la página web, al tradicional punto de venta físico. Una gestión eficaz y eficiente de la cadena de suministro es, por tanto, fundamental para el éxito de las empresas que se dedican al comercio electrónico [ 13 ]. Para lograr ese objetivo, desempeñan un papel esencial los nuevos avances tecnológicos como Internet de las Cosas, Big Data y Cloud Computing que mejoran la logística a nivel de sistema, de operaciones o de toma de decisiones, permitiendo proceder a tiempo real y de manera inteligente. [35] Considerando todos estos aspectos, se aprecia fácilmente el notable cambio que ha sufrido el sector en las últimas décadas, pues ya no es solo un tradicional eslabón de la cadena productiva 1.1 Amazon 3 que optimizar para reducir gastos, sino también un extenso área de innovación para conseguir una mejor calidad de servicio y, alcanzar así una mayor satisfacción del cliente. La fusión de ambos objetivos daría la definición del problema logístico del e-commerce actualmente, la necesidad de reducir gastos de transporte a la par que de aumentar la calidad del servicio al cliente. En relación a la satisfacción del consumidor, destacamos el papel del transporte. Los envíos gratuitos son clave, siendo valorados con un 74,4% como relevantes, seguido del tiempo de entrega (62,9%) y la posibilidad de seguimiento del envío (60,9%), según el último estudio de la ONTSI [ 33 ]. Estos datos muestran la exigencia real que padece el sector en cuanto a eficacia y eficiencia, pues el fracaso en estos aspectos puede provocar el descenso de ventas en el futuro. Es por ello que muchas empresas prefieren externalizar este servicio y subcontratar proveedores logísticos que lo gestionen. Estos operadores ofrecen desde la gestión de la última milla exclusivamente (First Party Logistics, 1PL), hasta una administración integral que se encarga del transporte, el almacenaje y la organización de ambas actividades (Third Party Logistics, 3PL). Aunque es una buena manera de aliviar las responsabilidades de una empresa, estudios muestran que las empresas deberían evitar la subcontratación de la logística si su rendimiento se basa en una ventaja competitiva debida a una capacidad y unas competencias logísticas sólidas a nivel interno [ 13 ]. Aquí entra en acción el gigante Amazon que, considerada como la empresa más poderosa del mundo, es todo un ejemplo en lo que a capacidades de logística y distribución se refiere. 1.1 Amazon Amazon fue fundada en 1994 en Bellevue, una ciudad periférica de Seattle en el estado de Washington, Estados Unidos, con el nombre primitivo de Cadabra. Jeff Bezos, un joven graduado en Ingeniería Eléctrica y Ciencias de la Computación por la Universidad de Princeton vaticinó el éxito en que se convertiría Internet y comenzó a ofrecer un catálogo de libros en línea. Fue un comienzo difícil, marcado por la percepción de inseguridad que existía sobre la compra online, pero que logró salvar con la financiación de familiares y amigos y con una visión y misión claramente definidas de lo que quería conseguir: ser una empresa que vendiera de todo y que permitiera a la gente de todo el mundo encontrar cualquier cosa que quisieran dentro de un mismo lugar al menor precio razonable y con el mejor servicio al cliente. [3] [10] Ese comienzo como puro vendedor de libros pronto quedó atrás, la compañía pronto comenzó a incorporar más productos a su catálogo, hasta llegar a ofrecer todo tipo de productos, como hace referencia en su lema: “De la A a la Z”. Más allá de eso, Amazon también destaca por alterar industrias bien establecidas a través de la innovación tecnológica y la escala masiva, abarcando casi todos los sectores [ 11 ]. Ha desarrollado, entre otros, su propia gama de productos marca Amazon, como el asistente virtual Alexa o su lector de libros electrónicos Kindle, y servicios, como la plataforma de computación Amazon Web Services o la plataforma de streaming Prime Video [ 5 ]. Paralelamente, las fusiones y adquisiciones han actuado también como un instrumento clave en su estrategia de crecimiento. Actualmente posee más de 40 subsidiarias entre las que se incluyen, por ejemplo, Audible, Goodreads, IMDb o Twitch [ 4 ]. Así, según el último informe global de 2021 de la consultora Kantar BrandZ, Amazon mantiene el liderazgo por tercer año consecutivo como la empresa con mayor valor de marca a nivel mundial: 683.9 billones de dólares, un 64% más que en 2020, crecimiento debido en gran medida a la pandemia de COVID-19. [34] La fama de espíritu disruptivo recién mencionada que se atribuye a Amazon se debe a en concreto a cuatro aspectos en torno a los que gira toda la política de la empresa: [8] •Customer centric •Employee centric •Centros logísticos 4Capítulo 1. Introducción •Distribución logística El primero de ellos hace referencia al hecho todas las acciones, proyectos e inventos, comienzan y terminan teniendo presente al cliente, con la idea de ofrecer algo cada vez mejor, y así afianzarlos. El segundo aspecto también pone como foco a la persona, pero esta vez el trabajador, reconociéndolo como el factor más importante de la cadena de valor. Cuando la empresa aumenta la producción y satisfacción de sus empleados, estos se implican más en aumentar la satisfacción de los clientes. En Amazon se estandarizan los procesos, para hacer el trabajo de los equipos más fácil y eficiente. Optimizando los procesos, la empresa logra realizar envío más rapidos, reducción de costes, y por consiguiente, pueden ofrecer los productos a los clientes a precios más bajos. Los dos últimos puntos ponen el foco en el ámbito logístico, y aunque todo está concebido como un buen engranaje para alcanzar el éxito, son estos dos los que técnicamente más tienen relación con el presente proyecto, y en los que Amazon destaca por la innovación que aplica en ellos. En primer lugar, hay que hacer notar que Amazon no cuenta con almacenes, sino centros logísticos, diseñados y equipados para realizar todo el proceso logístico, desde almacenaje y preparación hasta empaquetado y envío de cualquier tipo de producto. Estos centros cuentan con un sistema de gestión de stocks que al contrario que se podría suponer está basado en el “caos organizado”. Esta colocación optimiza el proceso de recogida de los pedidos, es decir, que el operario realice el menor recorrido posible para coger todos los artículos seleccionados, pues para conseguir productos de diferentes tipos no tiene que vistar diferentes zonas, sino que puede encontarlo todo en la misma. El concepto de “caos”, por tanto, hace referencia al hecho de que los productos no están divididos por categorías. El de “organizado”, proviene del hecho de que este desorden es relativo, pues el sistema de gestión de stock implantado conoce perfectamente las ubicaciones de todos los productos en el centro. A fecha de enero de 2020, Amazon contaba con 175 centros logísticos entre Europa y Estados Unidos. Esto constituye otra estrategia, con un mayor número de centros logísticos consigue estar más cerca de sus clientes, que así podrán recibir sus pedidos más rapidamente. El éxito en esta implementación está en que todos los centros se conectan como una gran red, y un potente sistema automatizado propio comprueba los stocks y asigna el pedido al centro más cercano. Esto es lo que ha permitido desarrollar servicios como “Prime Now”, con entregas ultrarrápidas. Por último, se hace alusión a la distribución logística. Siempre puntero en innovación, Amazon fue de las primeras empresas en impulsar la transformación digital de los negocios y de la ventas minoristas. Con un mercado mucho más sólido en este sentido, actualmente Amazon ha conseguido volver a romper el paradigma fusionando lo digital con lo físico. Así, cuando no encuentra el canal de distribución adecuado lo inventa, lo que ha llevado a la aparición de novedades como “Amazon Go, tienda física con tecnología avanzada que opera sin necesidad de personal; “Amazon Lockers, taquillas que operan con códigos de un solo uso que el cliente puede elegir como dirección de envío evitando la necesidad de tener que estar físicamente; entre otros. No cabe duda alguna de que Amazon es todo un referente en el ámbito logístico, sin embargo, también es importante entender que este es un modelo que muy difícilmente podrían imitar otras empresas, por la inmesa inversión que supone. Amazon cuenta con una posición privilegiada fruto de un trabajo impecable por parte de su fundador, que es considerado por muchos como “la mente maestra de la logística moderna”. 2 El problema del viajante, estado del arte El problema del viajante, conocido por sus siglas en inglés como el TSP (Traveling Salesman Problem) es el problema de optimización combinatoria más famoso del conjunto NP-hard. Su enunciado, aparentemente simple, esconde un campo de estudio y aplicaciones increíblemente amplio: Dado un número n de ciudades y sus distancias intermedias, ¿cuál es la ruta más corta, que pase por cada ciudad exactamente una vez, y tenga origen y final en el mismo lugar? [28] 2.1 Historia Como disciplina matemática, la optimización combinatoria es relativamente joven. No fue hasta 1950, con el desarrollo de la programación lineal y de enteros, y el interés al alza en el campo de la investigación operativa que se estableció un marco común para interpretar estos problemas. Al estudiar su historia, uno se da cuenta de que, en un principio, existían numerosas líneas de investigación independientes, de índoles muy variadas. La causa de esta diversidad se debe a que son problemas que descienden de la práctica y se han ido atacando a diario. No es difícil imaginar que, desde sociedades muy primitivas, encontrar caminos cortos para buscar comida, por ejemplo, ha sido esencial. Así, el TSP está presente en el día a día, al planificar compras o visitas turísticas, o cuando un médico o un transportista planifican su recorrido. [32] Centrando la atención en su origen matemático propiamente dicho, es difícil fijar una fecha concreta. Una guía para viajeros alemana publicada en 1832, ya incluía una mención explícita al problema, aún sin tratamiento de matemático del mismo. Sin embargo, todavía habría que esperar un siglo, hasta la década de 1930, para ver el término “Travelling Salesman Problem” aparecer en la comunidad científica. Fue entonces cuando matemáticos de Viena y Harvard estudiaron la forma general del problema. Destaca aquí el papel de Karl Menger, quien realizó la definición del TSP, considerando el obvio algoritmo de fuerza bruta, y observando la no optimalidad de la heurística del vecino más próximo, del que se hablará más adelante. Durante los años 1950 a 1960, el problema ganó popularidad entre las comunidades científicas de Europa y Estados Unidos. En 1954, el equipo compuesto por George Dantzing, Ray Fulkerson y Selmer M. Johnson, expresaron el problema como Programación Lineal en Enteros y desarrollaron para solucionarlo el método de Planos Cortantes. Así, consiguieron resolver una instancia con 49 ciudades, encontrando el camino óptimo que minimizaba su coste, y dieron un empujón muy notable a futuras investigaciones en ese campo. [32] El siguiente acontecimiento relevante, no se produciría hasta 1971. Los investigadores de IBM, Michael Held y Richard M. Karp, resolvieron un problema con 64 nodos distribuidos aleatoriamente en una región cuadrada, cuyos costes de viaje eran considerados como la distancia en línea recta 5 6Capítulo 2. El problema del viajante, estado del arte entre cada par de puntos. Además, demostraron que el Problema del Ciclo de Hamilton era un problema NP-completo, lo cual implica que el TSP sea un problema NP-hard, lo que evidencia la dificultad computacional para encontrar soluciones óptimas. Desde entonces, no han parado de producirse abrumadores avances. En 1987, los equipos de los matemáticos Padberg y Rinaldi, alcanzaron rutas óptimas para 532 ciudades de Estados Unidos, y Grötschel y Holland para 666 localizaciones en el mundo. En 1991, de nuevo Padberg y Rinaldi alcanzaron el óptimo para 2392 nodos en un problema de perforación. En 1992, Vasek Chvátal y William J.Cook resolvieron un problema de perforado con 3038 nodos mediante una larga red de ordenadores en paralelo. En 1998, este mismo equipo llegó al itinerario óptimo para un problema de 13509 ciudades en Estados Unidos. Posteriormente, también encontraron una ruta óptima para 24978 ciudades por Suecia en 2004; y en 2009, para una instancia de 85900 ciudades. [25] Este crecimiento exponencial en el número de ciudades consideradas en el problema se debió a la aplicación del código de ordenador ‘Concorde’ a partir de 1992. Un código de más de 130.000 líneas en C, que sigue vigente en la actualidad, y en el que profesionales de este campo siguen trabajando para mejorarlo. La progresión comentada se observa gráficamente en la figura 2.1. [6] 1950 1955 1960 1965 1970 1975 1980 1985 1990 1995 2000 2005 2010 0 2 4 6 8 ·104 Figura 2.1 Hitos de instancias resueltas TSP. 2.2 Complejidad Como ya se ha mencionado, a pesar de la simplicidad de su enunciado, el TSP es un problema que se incluye dentro del conjunto NP-hard. Esta dificultad radica en que el número de posibles soluciones aumenta significativamente al aumentar el tamaño de la muestra (n). En problemas de pequeña dimensión, es razonable pensar que con unos sencillos cálculos y comparaciones es fácil alcanzar la mejor solución sin invertir mucho tiempo. Sin embargo, al analizar matemáticamente este asunto se entiende rápidamente la complejidad del mismo. Dados n nodos, como el origen es conocido de antemano, quedan (n−1) lugares entre los que calcular una ruta. Llegados a la primera parada, quedarían (n−2) puntos entre los que elegir, y así sucesivamente, hasta llegar de nuevo al origen. Siguiendo la teoría combinatoria, aplicamos la permutación para calcular el número de ordenaciones posibles: [31] 2.3 Descripción del TSP 7 P(n−1) = (n−1)!(2.1) Aplicando esta sencilla fórmula al problema resuelto en 1954 por Dantzing, Fulkerson y Johnson, consistente de 49 ciudades, se concluye que cuenta con 1,24 ∗1061 opciones posibles. Es decir, para un problema que no es excesivamente grande, la cantidad de posibilidades es enorme. Calculando para el problema con mayor número de instancias resuelto (85900) se alcanza infinito. Evidentemente, esto es inabarcable, por eso se buscan algoritmos que reduzcan estas cifras astronómicas. Esta es la razón por la que el TSP ha alcanzado una posición tan importante en la teoría de la complejidad. De acuerdo a esta teoría, los problemas para los que existe un algoritmo de resolución polinomialmente acotado son clasificados como P, de tiempo polinómico. Esto quiere decir que exista un polinomio p tal que, para cada entrada de tamaño n , el algoritmo termine en no más de p(n) pasos, y por ende, en un tiempo. Por otro lado, un problema se encuentra dentro del conjunto NP si, y solo si, puede resolverse mediante un algoritmo no determinístico en tiempo polinomial, en otras palabras, que sea posible comprobar en un tiempo razonable si una respuesta al problema es correcta o no. [20] Resulta obvio, por tanto, decir que todo problema tipo P se puede considerar también NP. Del mismo modo, se podría pensar que entonces no cualquier problema del tipo NP puede ser también P. Sin embargo, no se ha conseguido demostrar aún y por ello no se da por verdadero. Por otro lado, sí se ha demostrado que muchos de los problemas denominados “NP-hard” son computacionalmente equivalentes. En otras palabras, un algoritmo polinómico que resuelva uno de estos problemas, podría resolver también cualquier otro incluido en la misma categoría. Este asunto que podría parecer insignificante lleva mucho tiempo abierto, y es uno de los siete problemas del milenio. Tal es el interés en este campo, que incluso el Instituto Clay ha ofrecido un millón de dólares a quien desarrolle un algoritmo eficiente para el TSP o consiga demostrar la no existencia del mundo.[1] 2.3 Descripción del TSP El TSP puede ser descrito según la teoría de grafos de la siguiente manera: “Sea G= (N,A) un grafo completo, donde N=1,...,n es el conjunto de nodos o vértices y A es el conjunto de arcos. Los nodos i=2,...,n se corresponden con los clientes a visitar mientras que el nodo 1 es considerado la ciudad de origen y destino. A cada arco (i,j) se le asocia un valor no negativo di j que representa la distancia del vértice i al j . El uso de los arcos (i,i) no está permitido, por lo que se impone que dii =0∀i∈N”. [21] En otras palabras, se concluye que el TSP se define sobre un grafo con costes 1 asociados a los arcos y el objetivo es encontrar un circuito hamiltoniano de coste mínimo. Según el tipo de grafo se distinguen dos problemas: •ATSP o TSP asimétrico : El grafo G es dirigido, es decir, los arcos tienen un sentido único tal que el arco (i,j) comienza en i y termina en j . Aplicado al TSP, esto implica que la matriz de distancias es asimétrica y la distancia de ida no tiene porqué coincidir con la de vuelta. •STSP o TSP simétrico : El grafo G es no dirigido, en otras palabras, los arcos conectan los nodos en ambos sentidos. Matemáticamente esto implica que di j =dji∀(i,j)∈A y por tanto en el TSP, la matriz de distancias es simétrica y el camino de ida coincide con el de vuelta. 1 Por la definición realizada del TSP, la distancia equivale también al coste mencionado en el desarrollo de este trabajo, pues es lo que se quiere minimizar y el valor asociado a los arcos. 8Capítulo 2. El problema del viajante, estado del arte 2.4 Formulación de la programación lineal en enteros del TSP El TSP puede ser formulado de numerosas maneras, hasta ocho de acuerdo a a. J. Orman y H. P. Williams [ 30 ]. A continuación, se presenta un modelo de los más conocidos e importantes, desarrollado por Miller, Tucker y Zemlin en 1960 [ 27 ]: dado un número de ciudades n donde di j es la distancia entre cada una de ellas se define la variable dicotómica xi j como: xi j =(1,si el camino escogido va de la ciudad ia la j 0,en otro caso (2.2) También se define la variable binaria ui para i=1,...,n , quedando la formulación del problema de la siguiente manera: Minimizar: n ∑ i=1 n ∑ j=1,j6=i di jxi j (2.3) Sujeto a: n ∑ i=1,i6=j xi j =1j=1,...,n(2.4) n ∑ j=1,j6=i xi j =1i=1,...,n(2.5) ui−uj+nxi j <n−1 2 ≤i6=j≤n(2.6) 1<ui<n−1 2 ≤i≤n(2.7) ui∈Zi=2,...,n(2.8) xi j ∈ {1,0}i,j=1,...,n(2.9) di j >0i,j=1,...,n(2.10) La función 2.3 es la función objetivo y minimiza el camino del viajante, las restricciones 2.4 y 2.5 obligan a que cada ciudad sea visitada una única vez y a que se salga siempre de la visitada, respectivamente. Las restricciones 2.6 y 2.7 evitan que se creen subtours entre el conjunto de ciudades del problema. 2.5 Variantes Algunas de las variaciones del TSP estudiadas en la literatura se han originado a partir de diversas aplicaciones del mismo, reales o potenciales. En este apartado, se tratarán algunas de esas variaciones que pueden ser reformuladas como TSP mediante transformaciones relativamente simples. [19] 2.5.1 MAX TSP Tiene como objetivo encontrar un circuito hamiltoniano de coste máximo. Se puede resolver como TSP reemplazando cada coste por su inverso aditivo, al que es posible añadir una constante grande 2.6 Aplicaciones 9 para exigir que los costes de las aristas sean no negativos, sin afectar a las soluciones óptimas del problema. 2.5.2 TSP de cuello de botella (BTSP) En este caso, el fin es encontrar una ruta en G tal que el mayor coste de aristas en el recorrido sea lo menor posible. Este problema puede formularse como un un TSP con costes de aristas exponencialmente grandes. Este problema fue definido por C. Garkinfel y Gilbert, y se formula fácilmente modificando la función objetivo del TSP a la siguiente expresión: max{di jxi j,1≤i,j≤n,i6=j}(2.11) 2.5.3 TSP con múltiples visitas (TSPM) El propósito de esta variante es encontrar una ruta tal que el viajante comience en un nodo dado de G , visite cada nodo al menos una vez, y vuelva al nodo de origen minimizando la distancia total recorrida. Para transformar este problema en TSP, habrá que sustituir los costes de las aristas por las distancias del camino más corto en G . Si existieran en G ciclos negativos el TSPM sería ilimitado. 2.5.4 TSP con múltiples viajantes (m-TSP) La solución del problema consiste en encontrar las rutas de los m agentes viajeros, teniendo en cuenta que cada ruta empieza y termina en el depósito y además cada nodo puede ser visitado una única vez, el objetivo es minimizar el costo total de visitar todos los clientes. [29] 2.5.5 TSP con ventanas de tiempo Para cada arco (i,j) de G , sea di j el coste y ti j el tiempo de trayecto, y para cada nodo i de G venga dado {ai,bi,si} donde ai≤bi y 0≤si≤bi−ai . La cantidad si representa el tiempo del servicio en el nodo i y el trabajo en este nodo debe ser completado en el intervalo temporal [ai,bi] . Si el viajante llega al nodo i antes de ai , deberá esperar hasta ai . Así el TSP con ventanas de tiempo trata de encontrar el circuito hamiltoniano en Gsatisfaciendo la restricción recién planteada. 2.6 Aplicaciones El problema definido por el TSP capta interés por ser un problema relativamente simple de describir, pero difícil de resolver desde el punto de vista de la optimización. Además de esto, existen importantes casos prácticos que se pueden formular como TSP y muchos otros son generalizaciones del mismo, lo que lo hace aun más interesante y versátil. Se presentan algunos ejemplos a continuación para, aun dejando muchos atrás, poder apreciar la diversa naturaleza de los mismos. [2] 2.6.1 Perforación de circuitos impresos (PCB) Para conectar un conductor de una capa con otro de otra, o para posicionar las clavijas de circuitos integrados, es necesario perforar agujeros en la placa. Estos agujeros pueden ser de diferentes tamaños, por lo que la máquina tendría que cambiar el cabezal de perforación volviendo a la caja de herramientas. Para ahorrar tiempo, este procedimiento se realiza perforando todos los agujeros del mismo diámetro de una vez, para así minimizar el número de cambios. Por ello, el problema de perforación puede ser visto como una serie de TSPs, uno por cada agujero de diferente tamaño, donde las ‘ciudades’ son la posición inicial y el conjunto de agujero que perforar con un mismo cabezal. La ‘distancia’ entre dos ciudades viene dada por el tiempo que tarda la máquina en moverse de una posición a otra, y así se trataría de minimizar el tiempo de viaje para la herramienta de perforación. 16 Capítulo 4. Algoritmos escogidos Se define la probabilidad de transición de una ciudad ia otra jpor la hormiga kcomo pk i j(t) =    [τi j(t)]α·[ηi j]β ∑k∈Jk(r)[τik(t)]α·[ηik]β,si j∈Jk(r) 0,en otro caso (4.5) Gracias a la visibilidad y a la actualización de la feromona aumenta la probabilidad de escoger el camino más corto y el algoritmo converge hacia una solución óptima o cercana al óptimo del problem. Ser una selección estocástica permite que el algoritmo explore otras regiones del espacio aún sin explorar, huyendo así de óptimo locales. Los pasos que definen al algoritmo son los siguientes: 1. Se inicializan los datos, como por ejemplo, ∆τi j ,donde c es una constante cualquiera. 2. Las mhormigas generan msoluciones. 3. Se actualiza la feromona, según las msoluciones del paso 2. 4. Se vuelve al paso 2 si no se ha cumplido el criterio elegido para terminar el algoritmo. 5. Fin del algoritmo. 4.2.3 ACS, Ant Colony System Un año más tarde de la publicación del ASO, Dorigo y Gambardella presentan una evolución del mismo conocida como Ant Colony System. En este nuevo algoritmo, que parte de las mismas ecuaciones y nomenclatura que el original, se introducen tres grandes cambios que se definen a continuación. [15] 4.2.3.1 Exploración o explotación Se entiende por explotación el aprovechamiento, por parte del algoritmo, del conocimiento acumulado en la variable feromona (ri j) para buscar en la cercanía de las mejores soluciones alcanzadas hasta el momento, puesto que en los arcos pertenecientes a estas rutas existirá una mayor cantidad de feromona.La exploración se define como la búsqueda de nuevas regiones del espacio. Ambos conceptos se recogen en la siguiente ecuación: j=(arg maxk∈Jk(r)([τik(t)]α·[ηik]β),si q<q0(Explotación) S,en otro caso (Exploración) (4.6) donde q es una variable aleatoria uniformemente distribuida tal que (1<q<0) y q0 un parámetro del problema que también se define entre (1<q0<0) . Por otro lado, S es una variable aleatoria seleccionada según la ecuación 4.5, es decir, si j=S entonces la ciudad j vendrá escogida según la probabilidad pi j dada por esa misma ecuación. El parámetro q0 determina la importancia relativa de la explotación sobre la exploración, de acuerdo a lo definido en la ecuación 4.6. 4.2.3.2 Actualización global de la feromona En esta evolución del algoritmo antes presentado, la feromona se actualiza según la mejor solución encontrada hasta el momento tal que se sustituye la ecuación 4.3 por la que se propone a continuación: ∆τi j =(1 Lgb ,si el arco ai j pertenece a la mejor solución encontrada hasta el momento) 0,en otro caso (4.7) donde Lgb equivale a la longitud de la mejor solución encontrada 4.2 Algoritmos Colonia de Hormigas, ACO 17 4.2.3.3 Actualización local de la feromona Esta modificación hace referencia al hecho de que, en cada iteración, cada vez que una hormiga k pasa por el arco aij la feromona rij asociada a dicho arco es modificada de acuerdo a la siguiente expresión: rrs = (1−γ)rrs +γ∆rrs (4.8) donde γ es un parámetro tal que 0<γ<1 y ∆rrs =r0 . La constante r0 es la cantidad de feromona inicial en cada arco ai j y se calcula tras iniciar una solución general. 5 Adaptación al problema de Amazon en Sevilla Una vez presentado el fondo teórico del problema del viajante, antes de aplicar cualquier metodología de resolución al problema presente en caso del centro logístico de Amazon en el parque empresarial Megapark de Dos Hermanas, es necesario desarrollar un grafo G del mismo que lo represente. Se modela así el problema de acuerdo con el ya mencionado enunciado esencial del TSP: “Sean N ciudades de un territorio. El objetivo es encontrar una ruta que, comenzando y terminando en una ciudad concreta, pase una sola vez por cada una de las ciudades y minimice la distancia recorrida por el viajante.” En este caso, el vehículo saldrá del centro logístico de Amazon en Dos Hermanas, y recorrerá los pueblos asignados en cada caso, regresando posteriormente de nuevo al punto inicial. Tratándose efectivamente del puro problema del viajante, se minimizará la distancia con la obligatoriedad de visitar cada pueblo una sola vez como única restricción. 5.1 Nodos Según lo mencionado anteriormente, en este trabajo se estudia en primer lugar el TSP para los distritos que colindan con la ciudad de Sevilla. Distinguimos Sevilla Sur, Aljarafe (Oeste), y zona Noreste, en la que se fusionan dos comarcas para lograr un escenario mayor. Dentro de cada una de ellas se elegirán un número n de nodos. Esta división del problema permite comparar resultados para casos de distritos en que los municipios están cercanos entre sí (menores de 25 Km), y otros en los que hay que asumir distancias bastante mayores (superiores a 75 Km), así como observar si el número de nodos afecta de alguna manera al algoritmo. En todos los casos se han elegido pueblos entre 10.000 y 40.000 habitantes, es decir, con cierta relevancia respecto a su distrito. La variedad final lleva a contar con pueblos a tan sólo 10 Km de distancia y otros con hasta 100 Km hacia el centro logístico que actúa como origen y centro neurálgico del problema. Se listan a continuación los municipios considerados en el problema, haciendo recuento del número de nodos, n, para cada caso, sin incluir el depósito: •Origen y destino: Amazon SVQ1 • Noreste (11 nodos): Alcalá del Río, La Algaba, Arahal, Brenes, Cantillana, Écija, Estepa, Guillena, Marchena, Osuna, La Puebla de Cazalla. • Oeste (5 nodos): Bollullos de la Mitación, Gelves, Gines, La Puebla del Río, Sanlúcar la Mayor 19 20 Capítulo 5. Adaptación al problema de Amazon en Sevilla • Sur (4 nodos): Las Cabezas de San Juan, Lebrija, Morón de la Frontera, Los Palacios y Villafranca. 5.2 Arcos Se considera arcos a las conexiones entre municipios, que pueden ser directas o indirectas. Por indirectas se entiende aquellas que obligan a pasar por un nodo para llegar a otro por no estar el primero completamente conectado con todos los del grafo. En estos casos, es posible atravesar un pueblo para llegar a otro y que no sea considerado como visitado por el algoritmo. En este trabajo, el problema se modela como un grafo conexo, donde todos los nodos están conectados entre sí, aunque podría pasar que el algoritmo decida usar una ruta indirecta si la considera óptima. Haciendo referencia de nuevo al caso de estudio presentado, se observa con facilidad que los arcos están representados por vías de circulación como carreteras, autopistas o autovías. 5.3 Matriz de costes Tal y como ya se ha mencionado anteriormente, el TSP pretende hallar la ruta mínima para visitar un número n de ciudades una única vez, con origen y final en la misma ciudad. Por este motivo, es evidente que será necesario calcular una matriz de distancias entre todos los municipios a considerar en una ruta, en la que cada elemento di j , representa la distancia entre el pueblo i y el pueblo j . Se supondrá una matriz simétrica, es decir, el camino de ida es igual que el de vuelta, o expresándolo matemáticamente: di j =dji. Esta matriz de costes será suficiente para el algoritmo del vecino más próximo, sin embargo, en el algoritmo de colonia de hormigas habrá que considerar otras variables. Existen diferentes tipos de vías de circulación: caminos, carreteras, autovías y autopistas, cada una de distintas calidades y con diferentes límites de velocidad establecidos. Por ello, en este algoritmo incluiremos una variable que sopese este aspecto, esta será la conocida feromona. Para el presente caso, se han establecido valores constantes, dependientes del tipo de vía, y no se actualizarán como se plantea en el algoritmo original. Los valores más altos representan mejor condición, y los más bajos, peor, de manera que queda como sigue: •A-92: ν=0,3 •A-4: ν=0,2 •Resto de vías: ν=0,1 Las matrices de costes empleadas en este estudio están adjuntas en el Anexo 1. 5.4 Definición de la experimentación Una vez conocidos los datos iniciales del problema, se procederá al desarrollo del propio algoritmo. A continuación, se detalla el método de actuación para cada uno de los casos. En este estudio se ha trabajado con la herramienta Microsoft Excel, en la que se han elaborado las matrices que serán objeto de análisis para resolver el problema planteado. Todo el procedimiento puede ser encontrado en el anexo A. 5.4.1 Algoritmo vecino más próximo Como ya se ha explicado, el procedimiento de este algoritmo es sencillo, simplemente desde el origen se decide el próximo destino en base a la matriz de distancias mencionada en el apartado 5.3, 5.4 Definición de la experimentación 21 eligiendo el municipio ubicado a menor distancia. Cada vez que se llegue a un nuevo pueblo, se repite el mismo procedimiento. Es importante recordar el enunciado del TSP, que dice que cada parada de la ruta se visitará una única vez. Por ello, cada vez que lleguemos a un municipio, ese se eliminará definitivamente de la ruta, pues ya se habrá cumplido la misión. 5.4.2 Algoritmo colonia de hormigas Basado en el comportamiento natural de las hormigas, que siguen el rastro químico de sus compañeras como modo de comunicar la existencia de una fuente de alimento, este algoritmo requerirá establecer un sistema de recompensas que lleve a la convergencia del mismo. Como se explica en el apartado 5.3 se aplicarán unas feromonas constantes en función del tipo de vía. En el primer paso, se parte de la matriz de distancias. Haciendo la inversa de cada elemento se llega a al concepto de visibilidad antes mencionado η(i,j) = 1 d(i,j)(5.1) Partiendo del resultado anterior, entra ahora en juego la feromona. Continuando con el procedimiento, se obtiene una primera matriz de probabilidades que guiará a las ‘hormigas’ en su búsqueda. p1(i,j) = η(i,j)∗ν(i,j)(5.2) Finalmente, y dado que el algoritmo se retroalimenta, se realiza una nueva iteración de acuerdo a la fórmula siguiente: -> No entiendo bien por qué se realizan dos iteraciones p2(i,j) = p1(i,j)∗1 ∑n i=1p1(i)(5.3) Una vez obtenida esta segunda matriz de probabilidad, se procede de manera muy similar al algoritmo del vecino más próximo, salvo que en este caso se buscará la mayor probabilidad. 6 Resultados El objetivo principal del estudio de problemas como el TSP es el desarrollo de nuevas técnicas de resolución, es decir, algoritmos, que calculen una solución óptima o aproximada para cada instancia del problema dado. Naturalmente, no todos los algoritmos que alcanzan un óptimo tienen el mismo rendimiento, y por ello resulta lógico que algoritmos que llegan solo a soluciones aproximadas, pero no necesariamente óptimas, compensen este inconveniente mejorando el comportamiento computacional. [23] En consecuencia, los resultados de un algoritmo, independientemente de si la solución se acerca o no al óptimo del problema en que se aplica, siempre aportarán una nueva visión para entender mejor el problema que se pretende resolver o el método empleado en ello. Por esta razón, el desarrollo de algoritmos busca siempre encontrar el equilibrio entre el coste computacional y la exactitud del resultado, y esta será el punto de vista desde el que se analizará el resultado. Se presentan a continuación los resultados obtenidos en el presente proyecto, para cada uno de los distritos mediante ambos algoritmos. 6.1 Distrito Sur Para el caso del distrito Sur, que cuenta con un total de 5 nodos divididos en 4 pueblos y el centro logístico de Amazon y por ambos métodos se obtiene la siguiente solución: [‘Amazon SVQ1, ‘Los Palacios y Villafranca’, ‘Las Cabezas de San Juan’, ‘Lebrija’, ‘Morón de la Frontera’, ‘Amazon SVQ1’] La distancia total recorrida para este caso es de 200,1 km. Una explicación a la igualdad en el resultado, es que el método del vecino más próximo funciona mejor en muestras de menor tamaño. 23 24 Capítulo 6. Resultados Figura 6.1 Ruta resultante para el distrito Sur. 6.2 Distrito Aljarafe Para el distrito Aljarafe sucede lo mismo que en el caso anterior, es decir, ambos métodos alcanzan el mismo resultado. En este caso, la distancia total recorrida es de 102,5 km, aunque aquí no aplica comparar las distancias porque no se trata de los mismos pueblos. No obstante, sí cabe destacar que el hecho de añadir un nuevo nodo no afecta al comportamiento del vecino más próximo, si bien es verdad que una muestra total de 6 nodos sigue siendo pequeña. Además en este distrito las comunicaciones entre pueblos son por vías de buena calidad, lo que hace que la influencia del algoritmo de colonia de hormigas sea menor. [‘Amazon SVQ1’, ‘Gelves’, ‘La Puebla del Río’, ‘Bollullos de la Mitación’, ‘Gines’, ‘Sanlúcar la Mayor’, ‘Amazon SVQ1’] Figura 6.2 Ruta resultante para el distrito Aljarafe. 6.3 Distrito Noreste 25 6.3 Distrito Noreste 6.3.1 Algoritmo vecino más próximo La ruta obtenida por la heurística del vecino más próximo se presenta a continuación: [‘Amazon SVQ1’, ‘La Algaba’, ‘Alcalá del Río’, ‘Guillena’, ‘Brenes’, ‘Cantillana’, ‘Arahal’, ‘Marchena’, ‘La Puebla de Cazalla’, ‘Osuna’, ‘Estepa’, ‘Écija’, ‘Amazon SVQ1] La distancia total recorrida por esta trayectoria es de 364,9 km. Figura 6.3 Ruta resultante para el distrito Noreste por el método del vecino más próxima. 6.3.2 Algoritmo colonia de hormigas Mediante el algoritmo de colonia de hormigas se llega a otra solución. En este caso, la distancia total alcanza los 452,3 km. [‘Amazon SVQ1’, ‘La Algaba’, ‘Alcalá del Río’, ‘Guillena’, ‘Brenes’, ‘Cantillana’, ‘Écija’, ‘Osuna’, ‘La Puebla de Cazalla’, ‘Arahal’, ‘Marchena’, ‘Estepa’, ‘Amazon SVQ1] 32 Capítulo A. Tablas Excel A.2 Distrito Aljarafe Figura A.3 Datos distrito Aljarafe. A.2 Distrito Aljarafe 33 Figura A.4 Algoritmo de colonia de hormigas para el distrito Aljarafe. 34 Capítulo A. Tablas Excel A.3 Distrito Noreste 35 A.3 Distrito Noreste Figura A.5 Datos distrito Noreste. 36 Capítulo A. Tablas Excel Figura A.6 Algoritmo de colonia de hormigas para el distrito Noreste. A.3 Distrito Noreste 37 Figura A.7 Comparación de resultados para el distrito Noreste. Bibliografía [1] Rules for the millennium prizes. [2] Traveling salesman problem, theory and applications, 2012. [3] Hatem Mohammed Alshmrani, An analytical view of amazon success in the worldwide, Life Science Journal 18 (2021). [4] Amazon, Subsidiaries | amazon.jobs. [5] , Who we are. [6] David L. Applegate, Robert E. Bixby, Vašek Chvátal, William Cook, Daniel G. Espinoza, Marcos Goycoolea, and Keld Helsgaun, Certification of an optimal tsp tour through 85,900 cities, Operations Research Letters 37 (2009). [7] Risca Fitri Ayuni, The online shopping habits and e-loyalty of gen z as natives in the digital era, Journal of Indonesian Economy and Business 34 (2019). [8] Beetrack, Logística de amazon: Analizando al gigante, 1 2020. [9] Anam Bhatti, Hamza Akram, Hafiz Muhammad Basit, Ahmed Usman Khan, Syeda Mahwish, Raza Naqvi, and Muhammad Bilal, E-commerce trends during covid-19 pandemic, International Journal of Future Generation Communication and Networking 13 (2020). [10] Richard L Brandt, One click: Jeff bezos and the rise of amazon.com, Penguin, 2011. [11] Per Bylund, Amazon’s lesson about disruption: Rattle any market you can, 8 2017. [12] Alicia Cirilia Riojas Cañari, Conceptos, algoritmo y aplicación al problema de las n – reinas. heurística y metaheurística., 2005. [13] Jay Joong-Kun Cho, John Ozment, and Harry Sink, Logistics capability, logistics outsourcing and firm performance in an e-commerce market, International Journal of Physical Distribution Logistics Management 38 (2008). [14] Marco Dorigo and Luca Maria Gambardella, Ant colonies for the travelling salesman problem, BioSystems 43 (1997). [15] ,Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation 1(1997). 39 40 Bibliografía [16] Marco Dorigo, Vittorio Maniezzo, and Alberto Colorni, Ant system: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics 26 (1996). [17] Irina Dumitrescu and Thomas Stützle, Combinations of local search and exact algorithms, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2611 (2003). [18] Google, Google maps. [19] Gregory Gutin and Abraham Punnen, The traveling salesman problem and its variations, ... of Combinatorial Optimization: Problems and ... (2007). [20] The Clay Mathematics Institute, The Clay Mathematics Institute, and The Clay Mathematics Institute, The millenium prize problems, 2014. [21] Nicolas Isoart and Jean Charles Régin, Integration of structural constraints into tsp models, vol. 11802 LNCS, 2019. [22] Petra Jílková and Petra Králová, Digital consumer behaviour and ecommerce trends during the covid-19 crisis, 2021. [23] Hans Kellerer, Ulrich Pferschy, and David Pisinger, Knapsack problems, 2004. [24] Abdul Gaffar Khan, Electronic commerce: A study on benefits and challenges in an emerging economy, Type: Double Blind Peer Reviewed International Research Journal Publisher: Global Journals Inc 16 (2016). [25] Uroš Klanšek, Using the traveling salesman problem solution for optimal route scheduling in construction management, Organization, Technology and Management in Construction: An International Journal (2011). [26] Baskaran Menaka and Keloth Seethal, Recent trends in e-commerce, Shanlax International Journal of Commerce 6(2018), 40–44. [27] C. E. Miller, R. A. Zemlin, and A. W. Tucker, Integer programming formulation of traveling salesman problems, Journal of the ACM (JACM) 7(1960). [28] Dhinaharan Nagamalai, Ashok Kumar, and Annamalai Annamalai (eds.), Advances in computational science, engineering and information technology, vol. 225, Springer International Publishing, 2013. [29] Eliana Toro Ocampo, Rubén Bolaños, and Mauricio Granada Echeverri, Solución del problema de múltiples agentes viajeros resuelto mediante técnicas heurísticas, Scientia et Technica 19 (2014). [30] AJ Orman and H Paul Williams, A survey of different integer programming formulations of the travelling salesman problem, Optimisation, econometric and financial analysis, Springer, 2007, pp. 91–104. [31] Abraham Punnen, FrancoiS Margot, and Santosh Kabadi, Tsp heuristics: domination analysis and complexity, Algorithmica 35 (2003), no. 2, 111–127. [32] Alexander Schrijver, On the history of combinatorial optimization (till 1960), 2005. [33] Alberto Urueña, María Pilar Ballestero, Raquel Castro, Santiago Cadenas, Menchu Maira, and Eva Prieto, El comercio electrónico b2c en españa 2019, 11 2020. Bibliografía 41 [34] David Walter, Kantar brandz 2021 most valuable global brands, 2021. [35] Ying Yu, Xin Wang, Ray Y. Zhong, and George Q. Huang, E-commerce logistics in supply chain management: Practice perspective, vol. 52, 2016.