El problema del viajante aplicado a la red logística de Amazon en Sevilla

Equation Chapter 1 Section 1 Proyecto Fin de Máster Ingeniería Industrial El problema del viajante aplicado a la red logística de Amazon en Sevilla. Autor: Javier Rojas Eugui Tutor: Manuel Ordóñez Sánchez Dpto. Matemática Aplicada II Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2020 III Proyecto Fin de Máster Ingeniería Industrial El problema del viajante aplicado a la red logística de Amazon en Sevilla. Autor: Javier Rojas Eugui Tutor: Manuel Ordóñez Sánchez Profesor Titular de Universidad Dpto. de Matemática Aplicada II Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2020 V Proyecto Fin de Máster: El problema del viajante aplicado a la red logística de Amazon en Sevilla. Autor: Javier Rojas Eugui Tutor: Manuel Ordóñez Sánchez El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2020 El Secretario del Tribunal VII A mis abuelos, que ya descansan en la casa del Padre. AMDG. IX Resumen El objeto de este trabajo es la aplicación del problema del viajante a la red logística de la zona oeste de Sevilla, mediante el empleo de tres algoritmos: Ramificación y Poda, Programación Dinámica y el algoritmo de Christofides. A través de éstos se optimizará el caso en el que un vehículo proveniente del centro logístico de Amazon en Dos Hermanas tenga que servir a todos los pueblos de la zona oeste de la capital hispalense, una única vez. Respondiendo, así, a la necesidad de reducción de costes de esta multinacional del comercio electrónico en una zona de Sevilla congestionada por el tráfico. XVII ÍNDICE DE FIGURAS Figura 1: Jeff Bezos, fundador de Amazon. ......................................................................................... 2 Figura 2: Organigrama de Amazon. [8] ............................................................................................. 10 Figura 3: Distribución de ingresos de Amazon en 2018. Fuente https://www.bbc.com/mundo/noticias-48909676 ................................................................................... 12 Figura 4: El círculo virtuoso de Bezos. Fuente: Amazon.com ......................................................... 16 Figura 5: Círculo virtuoso de Bezos desde el punto de vista logístico. Fuente [15]. ...................... 17 Figura 6: Ejemplo de centro de recepción [17]. ................................................................................. 20 Figura 7: Recreación del centro logístico de Amazon en Dos Hermanas (Sevilla). ....................... 21 Figura 8: Circunvalación exterior de Sevilla. Tramos acabados e inacabados. Fuente: Wikipedia.commons. ................................................................................................................................ 22 Figura 9: Vías de congestión metropolitana [21]............................................................................... 24 Figura 10: Ejemplo típico de un mosaico de corte para una sola lámina en la industria del vidrio. [26] ............................................................................................................................................................. 31 Figura 11: ‘Traveler Sound Player’, regulador de canciones............................................................ 33 Figura 12: “The Icosian Game”. Fuente: Royal Irish Academy Library en Twitter.com .............. 34 Figura 13. Pseudocódigo del algoritmo de Floyd-Warshall. Fuente: https://resources.mpiinf.mpg.de/ ................................................................................................................................................. 35 Figura 14: Grafo en el cual el viajante tendrá que visitar el nodo B al menos dos veces. Fuente: http://web.mit.edu/ .................................................................................................................................... 36 Figura 15: Subtours para un problema de 5 ciudades. Fuente: chegg.com ...................................... 42 Figura 16: Grafo completo. Fuente Wikipedia Commons. ............................................................... 45 Figura 17: Ejemplo de mínimo árbol de cobertura. [38] ................................................................... 46 Figura 18: Problema de los siete puentes de Königsberg [40].......................................................... 47 Figura 19: Pseudo código del algoritmo de la fuerza bruta. .............................................................. 50 Figura 20: Algoritmo que resuelve El problema del camino mínimo. ............................................. 51 Figura 21: Diagrama de casos para el Teorema 1. Fuente: Elaboración propia. ............................. 54 Figura 22: Ramificación en profundidad para un problema de 5 nodos. Fuente [42] ..................... 62 Figura 23: Pseudo algoritmo de Branch and Bound. ......................................................................... 65 Figura 24: Pseudo código del algoritmo de Held y Karp para el TSP. Fuente [28]. ....................... 66 Figura 25: Pseudo algoritmo de árbol de menor coste. ..................................................................... 69 Figura 26. Un 1-emparejamiento perfecto para un grafo de 6 nodos. [45] ...................................... 70 Figura 27: Dado un grafo completo 𝐺 de 10 nodos se aplica el algoritmo de Christofides para hallar una solución al TSP del grafo 𝐺. Fuente [46] ......................................................................................... 72 Figura 28: Mapa de la zona oeste de Sevilla. ..................................................................................... 74 Figura 29: Resolución del problema de los 23 nodos con el algoritmo de Branch and Bound. ..... 78 Figura 30: Resolución del problema de los 23 nodos con el algoritmo de Christofides. ................ 81 XIX ÍNDICE DE TABLAS Tabla 1: Identificación de las vías de acceso a Sevilla [21]. ............................................................. 23 Tabla 2: Principales órdenes de complejidad. Fuente: www.cs.us.ess/~jalonso ............................. 57 Tabla 3: Resultados para diferentes instancias del problema............................................................ 83 Tabla 4: Relación del Problema de Christofides con la solución óptima del problema .................. 83 XXI Notación A ∪ B La unión de A y B A ∩ B la intersección de A y B ⊆ Es subconjunto de ∈ Pertenece a ∉ No está contenido en Min{} Mínimo de un conjunto : Tal que | Tal que ≤ Menor o igual ≥ Mayor o igual \ Menos (diferencia de conjuntos) | | Valor absoluto ∃ Existe ∄ No existe 1 AMAZON, EL GRAN “MINORISTA” GLOBAL mazon es una empresa estadounidense dedicada principalmente al comercio electrónico con sede en Seattle, Washington, fundada en 1994 por Jeff Bezos. Actualmente, es la empresa con mayor valor de marca a nivel mundial según el informe global de BrandZ [1] con un valor de 315.505 millones de dólares y con unos beneficios netos en 2019 de 3.268 millones de dólares. Comenzó siendo un vendedor de libros online y ha pasado a vender todo tipo de artículos: “De la A al Z”, lema de la compañía. También, ha llegado a desarrollar su propia gama de productos con marca Amazon entre los que destacan sus libros electrónicos Kindle (propiedad de Amazon), la plataforma de publicación de libros, películas y música CreateSpace; servicios informáticos para todo tipo de empresas, Amazon Web Services, y dispositivos electrónicos que caminan hacia el hogar inteligente, Alexa. Esta variedad de productos, servicios y empresas que conforman Amazon, evidencian la importancia que debe tener la gestión de la logística y de los productos en la compañía. Por una parte, la logística es el grueso de la empresa, es la base sobre la que se sustenta desde los inicios la compañía y de donde procede el mayor volumen de negocio. Por otra parte, la cartera de productos propios se integra en esta logística y le da una identidad a la propia marca, es decir, pasa de ser un intermediario, a ser una empresa con sus propios productos y servicios que afianzan la importancia de la compañía en la mentalidad de sus clientes. A “En el mundo antiguo, dedicabas un 30% de tu tiempo en crear un gran servicio y un 70% en difundirlo. En el nuevo tiempo, eso se invierte.” - Jeff Bezos - 1.1 Historia 1.1.1 Jeff Bezos, la mente detrás de Amazon Se podría decir que la historia de Amazon comienza con la propia historia de Jeff Bezos y de las influencias y cualidades que éste ha tenido a lo largo de su vida. Una de las influencias más notorias fue la de su abuelo materno, Lawrence Preston Gise. Trabajó en el DARPA (Defense Advanced Research Projects Agency), de donde surgieron las bases ARPANET, bases a su vez de Internet; lo que proporcionó familiaridad a Bezos con la gran herramienta del siglo XXI [2]. Por otra parte, se graduó en Ciencias de la Computación e Ingeniería Eléctrica en la universidad de Priceton en 1986. Allí fue miembro de la “Phi Beta Kappa” y fue elegido para “Tau Beta Pi”, la sociedad de honor en ingeniería más antigua de Estados Unidos. También en Priceton fue presidente de la asociación de alumnos “Students for the Exploration and Development of Space” (SEDS), dedicada a la promoción de la exploración espacial y el desarrollo de proyectos de Ingeniería. Lo que, en resumidas cuentas, hace ver que fue un alumno destacado y con gran interés y declinación por el mundo moderno que se conoce a día de hoy y que, por aquel entonces, se estaba gestando. Al salir de Priceton trabajó en diferentes compañías: Fitel, empresa emergente de telecomunicaciones; Bankers Trust, una importante banca estadounidense y, finalmente, en D. E. Shaw & Co., gestora de inversiones especialista en desarrollar modelos matemáticos para descubrir anomalías en el mercado, en donde Bezos ascendería rápidamente en muy poco tiempo [3] Figura 1: Jeff Bezos, fundador de Amazon. 3 1.1.2 Amazon, su historia En D. E. Shaw & Co Bezos con tan solo cuatro años en la empresa, ascendió al cargo de vicepresidente y fue el encargado de buscar oportunidades de negocio para la compañía. Fue en esta posición en la que él comenzó a gestar la idea de Amazon; vio que el mundo de Internet estaba abriendo un nuevo territorio donde ampliar la empresa, por lo que pensó en una lista de 20 productos que se podían vender en Internet, ya que el acceso a éste estaba creciendo en un 2300% anualmente, vio la ocasión y decidió dejar D. E. Shaw & Co, para fundar su propia empresa. De esa lista, Jeff decidió vender libros, porque eran universales, porque eran baratos y porque había millones de títulos que se podían vender. Aunque ya había negocios parecidos, se diferenció de la competencia con la promesa de vender cualquier libro a cualquier lugar. Fundó su negocio en el garaje de su casa con el nombre de Cadabra, aunque a finales de 1994 cambió el nombre por Amazon, oficialmente abrió sus puertas el dieciséis de julio de 1995. En menos de 30 días ya generaba unos ingresos de más de 20.000 dólares por semana y en pocos meses ya vendía en cada estado de Estados Unidos y en más de 45 países. Al final del año había contratado cerca de 250 empleados. [4] En 1995, Bezos recibe una inversión de 8 millones de dólares por parte de Kleiner Perkins, cuyos retornos eran superiores al 55000% para el año siguiente Un año después Amazon ya tenía suscritos 180.000 clientes y para octubre de 1997, ya contaba con alrededor de 1.000.000. Sus ingresos crecieron de 15.7 millones de dólares en 1996 a 610 millones en 1998. [2] [5] En 1997, Amazon se hace pública cotizando en bolsa con un precio de 18$ por acción. Aunque el crecimiento de los beneficios fue inusualmente lento, no consiguió beneficio hasta 2001 con un margen de cinco millones de dólares y con más de mil millones de ingresos. En 1998 la empresa expandió su negocio y comenzó a vender música y vídeos, al mismo tiempo que adquiría otras empresas como PlanetAll, Junglee y Bookpages.co.uk (más tarde se convertiría en Amazon UK). Para 1999, ya vendía juguetes, videojuegos, software y productos electrónicos entre otros. Además de expandir su negocio aumentando la variedad de productos que vendía, Bezos decidió adquirir empresas diferentes y aumentar su cartera de servicios. En 2006 nace Amazon Web Services (AWS), una plataforma computacional que ofrecía servicios de almacenamiento en línea, así como otros servicios, que generalmente no iban dirigidos directamente a los usuarios finales, sino que ofrecía a sus clientes funcionalidades que pudieran usar en el desarrollo de sus aplicaciones para así mejorar la calidad de servicio de los consumidores. Los clientes de este servicio eran principalmente pequeñas empresas, ya que les permitía no tener que ser propietarias de sus propios equipos informáticos gracias 1.2 Organización y jerarquía El diseño organizacional de Amazon se caracteriza por ser de estructura mecanicista, es decir, muy riguroso y altamente controlado, debido principalmente, al gran tamaño que tiene y al elevado número de empleados del que dispone. En ella las decisiones están en su mayoría centralizadas y ligadas a una jerarquía con una cadena de mando claramente definida. También destaca por su división en departamentos altamente especializados y, sobre todo, por la casi completa estandarización de todos los puestos de trabajo. Esto último supone que las funciones de un empleado en un determinado puesto estén muy definidas, es decir, compuestas por un conjunto de reglas y procedimientos del que es complicado salir. Del mismo modo, los flujos de información y de toma de decisiones también están estandarizados. Este diseño jerárquico consta de un equipo directivo formado por dos directores ejecutivos, tres vicepresidentes senior y un controlador mundial, que reportan directamente al CEO, Jeff Bezos. A su vez, se encuentra una segmentación funcional divida en siete áreas: Plataforma, Administración del producto masivo, Tecnología de Información, Administración y Finanzas, Recursos Humanos y, finalmente, Operaciones Legales. También se podría añadir el último segmento Amazon Studios & Prime Video. [8] Figura 2: Organigrama de Amazon. [8] En un nivel más general, Amazon tiene un órgano fundamental que lo gestiona, llamado Consejo de Administración de Amazon, compuesto por diez expertos a nivel mundial en gran variedad de industrias y comercios. Entorno a este consejo se encuentran tres órganos o comités que asisten al Consejo: Comité de Auditoría, Comité de Nominación y Gobierno Corporativo y Comité de Desarrollo y Compensación de Liderazgo. A pesar de tener una estructura organizacional mecanicista, es decir, jerárquica y centralizada, Jefe Ejecutivo (Bezos F.) Segmentos Plataforma Administración del producto masivo Tecnología de Información Administración y Finanzas Recursos Humanos Operaciones Legales CEO del Cliente CEO de Amazon del servicio web Vicepresidente & CFO 11 Amazon se caracteriza también por ser una empresa flexible, que se adapta a los cambios globales e incluso que los promueve debido a su potencial innovador. Dicha flexibilidad se sostiene principalmente en la figura de Bezos y a su capacidad de visión de negocio. Esta sinergia entre Jeff Bezos y la estructura organizacional centrada en su persona permite a Amazon ser una empresa adaptativa. [8] 1.2.1 Cultura de la organización La organización de Amazon se ve impregnada en una cultura fundamentada en tres pilares principales: 1. Alto grado de centralización del cliente. 2. Reducción al máximo de los costes de la compañía. 3. Innovación constante y mejora continua. En cuanto al primer punto, desde el comienzo de la compañía la misión fue centralizarse en el cliente, en palabras de Jeff Bezos: “Nuestra visión es ser la empresa más centrada en el cliente de la tierra: construir un lugar donde las personas puedan encontrar y descubrir todo lo que quieran comprar en línea”. Esto da a entender que el enfoque al cliente implica desde la perspectiva de la compañía un dominio global del comercio electrónico, la mayor oferta de productos en todo el mundo y un alcance que llegue a todos los puntos de la Tierra. En cuanto al segundo punto, como en el análisis que se hizo en el apartado 1.1.3, Amazon no comenzó a percibir sus primeros beneficios hasta seis años después de haber fundado la empresa, a pesar de que sus ingresos fueran millonarios desde el comienzo. Esto deja ver el elevado coste que ha tenido siempre la compañía, por lo tanto, es claro que la reducción de éste haya sido y sea siempre un punto fundamental donde centrar sus esfuerzos. Finalmente, con respecto a la Innovación constante, ya lo dice la cita de Jeff Bezos al comienzo de este capítulo: “En el mundo antiguo, dedicabas un 30% de tu tiempo en crear un gran servicio y un 70% en difundirlo. En el nuevo tiempo, eso se invierte.” La innovación es clave del éxito en toda compañía y es fundamental, en el caso de Amazon, para mantener el liderazgo. A más se innova, más se diferencia de la competencia y a más se diferencia, más competitivos se es. 1.3 Modelo de negocio 1.3.1 Propuesta de valor El negocio principal de Amazon es la venta, almacenamiento y distribución de productos al por menor (B2C) a través de su tienda online y su Marketplace. También ofrece otros servicios como Amazon Prime, Amazon Web Servicies (B2B) y Kindle Store Kindle Store entre otros. 1.3.2 Fuente de ingresos En este negocio tan variado la distribución de los ingresos es la que se puede apreciar en la Figura 3, siendo la más importante, y la que hasta la fecha lo ha sido siempre, su tienda online y Marketplace, seguida de AWS y luego de sus servicios que requieren subscriciones como Amazon Prime o Amazon Video. Figura 3: Distribución de ingresos de Amazon en 2018. Fuente https://www.bbc.com/mundo/noticias- 48909676 La tienda online de Amazon se refiere a todos los productos vendidos directamente por la compañía, mientras el Marketplace recoge a todos aquellos productos vendidos por terceros. Por lo tanto, no es de extrañar que la mayor parte de los ingresos de Amazon venga de la tienda online, ya que en este el margen de beneficio es mayor que en el Marketplace. Por otro lado, es importante remarcar que, aunque los beneficios por el Marketplace sean menores, la cantidad de productos vendida por terceros es mayor. En 2019 las ventas de los productos vendidos en el Marketplace ascendieron a 200.000 millones de dólares, mientras que las ventas de Amazon como vendedor directo fueron de 135.000 millones, es decir un 60% vendido por terceros y 40% por la empresa de Bezos. En el Gráfico 6 se 13 puede ver la evolución de la proporción de productos propios de Amazon y los productos de otros vendedores vendidos en la página web Amazo.com, desde 1999, año en qué la compañía comenzó a vender por primera vez productos de otros vendedores, hasta la actualidad. [12] Gráfico 6. Porcentaje histórico de relación de productos vendidos por Amazon y en el Marketplace 1.3.3 Estructura de los costes Con respecto a los costes de Amazon, la mayor parte corresponde al coste de ventas, seguido a la logística, transporte y almacenamiento de vehículos. Estos han ido creciendo a medida que lo han hecho los ingresos, tanto los costes operativos como los de investigación y desarrollo, así como el coste de cumplimiento. El coste de ventas es el mayor que tiene Amazon, en el que se incluye: el precio de compra de todos los productos que adquiere el consumidor final, el coste del transporte tanto a la entrada como a la salida de los centros logísticos, el coste de almacenamiento y clasificación, el coste de marketing, y, finalmente los costes digitales que dan soporte a estos productos. Los costes de transporte son lo que en proporción más están creciendo, debido a los nuevos servicios que se están ofreciendo y a la disminución paulatina del tiempo de entrega. El coste de cumplimiento se refiere a todos aquellos asociados a la contratación del personal, a los procesos de pagos y a las operaciones en sus centros logísticos norteamericanos e internacionales, en las tiendas físicas y en los “Costumer Service Centers”. En los costes de procesos de pago también se incluye los pertenecientes a AWS, aunque el resto de los costes asociados a este servicio se incluye en los de Investigación y desarrollo. Los costes de tecnología y contenido (Investigación y desarrollo, I+D) incluyen los asociados al personal encargado de desarrollar nuevas tecnologías para la empresa, los encargados de dar soporte a la infraestructura tecnológica y también a todos los costes que implica el AWS (servidores, equipos, centros de datos, etc.). Los costes de Marketing son aquellos asociados a la publicidad y aquellos dirigidos a mantener el personal de los departamentos de marketing y de ventas. Finalmente, se encuentran los costes generales y administrativos y otros gastos generales. [13] 1.3.4 Actividades, socios y recursos Las principales actividades de Amazon se pueden clasificar en tres: logística, servicios online y productos propios. Dentro de logística se encuentra la clasificación, el transporte y el almacenamiento de los productos vendidos o gestionado a través de la página web. Dentro de los servicios online destacan todas aquellas actividades dirigidas a mantenerlos y darles soporte. Por otro lado, las actividades que abarcan los productos propios son el diseño, desarrollo, producción, búsqueda de proveedores, marketing, etc., que permiten que el producto salga a la venta. En cuanto a los socios de Amazon los más importantes son los que se encuentran aguas abajo de la venta del producto y se refiere a las partes externas a la empresa involucradas en el desempeño de su actividad. Entran dentro de este grupo los vendedores, las empresas de logística, las empresas manufactureras encargadas de producir los productos propios de Amazon como Alexa, Kindle, la gama Amazon Basics, Presto, etc., u otros proveedores. [8] Por último, en los recursos de Amazon entra todo aquello propio a la empresa que permite la actividad principal. Por ejemplo, la infraestructura: almacenes, centros logísticos, servidores, equipos, etc. También se pueden encontrar las patentes pertenecientes a la marca. Un ejemplo de una de ellas fue el proceso de compra de “1-Click”, creado en 1997 y expirado como patenten en 2017, que permitía al consumidor final evitar todos los procesos de compra y con solo un clic pagar y hacer que el producto se enviara a su casa. 1.3.5 Canales, segmentación y relación con los clientes. El principal canal de Amazon, y casi único, es su página web o el conjunto de páginas que forman Amazon Inc. Desde el comienzo Amazon nació como una plataforma de venta online y es así como sigue siendo a día de hoy. Prácticamente todos sus servicios (AWS, Kindle, venta de productos) se realizan a través de su página web. Solo se salva las tiendas físicas que se están comenzando a abrir: Amazon Go. 15 La primera se abrió en 2016 en su sede en Seattle y ya cuenta con más 500 tiendas solo para su marca Whole Foods. Este tipo de marca se encuentra dentro de las siete categorías de tiendas físicas que tiene la compañía, cuatro son para compra de comida, siendo la más importante la ya mencionada. Aunque, estos negocios están en fase embrionaria y todavía no han despegado, supone un primer acercamiento de Amazon al comercio minorista. [14] En cuando al modo en que Amazon se relaciona con sus clientes, destaca principalmente el servicio Amazon Prime, a partir del cual el consumidor obtiene servicios tales como envío gratuito, ofertas en días como Prime Day, subscripciones gratuitas en Twitch, o acceso al catálogo de vídeos online Amazon Video. También permite la relación entre los clientes mediante las opiniones sobre los productos y la opción de plantear dudas a otros clientes o directamente al proveedor en caso de ser un vendedor externo. Finalmente, los clientes de Amazon se pueden clasificar en empresas, consumidores finales, vendedores, desarrolladores y creadores de contenido. • Consumidores finales: Fueron los primeros clientes de Amazon y siguen siendo su principal fuente de ingresos; estos consumidores son los que le dan a Amazon la etiqueta de minorista (B2C), aunque poco a poco se está convirtiendo en algo más que eso. A estos clientes se les sirve a través la página web y de las tiendas físicas, dónde Amazon les ofrece productos propios y de terceros. • Vendedores: El lugar en Amazon para estos clientes es el Marketplace, mediante el que las diferentes empresas venden sus propios productos. Para este grupo también existe un servicio de fidelización Fulfillment by Amazon, donde no solo una empresa vende sus productos a través de Amazon, sino que, además, la gestión física de dichos productos la realiza Amazon mediante su infraestructura, centros logísticos y personal. • Empresas y desarrolladores: En este punto no se incluyen las empresas que venden productos a través de Amazon, sino aquellas que contratan sus servicios de AWS. Estos son contratados por compañías y desarrolladores que buscan sus amplios servicios de computación, almacenamiento y bases de datos entre otros. • Creadores de contenido: En este segmento de clientes se encuentran autores, músicos, pequeñas productoras de películas, desarrolladores de aplicaciones y otros tipos de publicadores que crean y quieren vender sus propias creaciones. 1.4 Logística y Operaciones de Amazon En este apartado se hará un breve análisis de cómo Amazon lleva a cabo su actividad y cuáles son los objetivos que la determinan. También se presentarán proyectos destacados, actuales o futuros, que darán una visión más profunda sobre este punto. La finalidad de este análisis es entender cómo el problema matemático se materializa, es decir, qué infraestructura hay detrás, sobre qué pilares se sustenta y qué objetivos persigue. 1.4.1 Objetivos - The Bezos Virtuous Cycle Los objetivos de la logística de Amazon se engloban dentro del llamado The Bezos Virtuous Cycle (El círculo virtuoso de Bezos, Figura 4), un círculo virtuoso o ‘volante de inercia’ (flywheel) empresarial aplicado a la forma de proceder de Amazon. Este fue desarrollado por Jeff Bezos en 2001, como explica Jeff Wilke, y desde entonces ha sido la estrategia de marketing de la empresa. Figura 4: El círculo virtuoso de Bezos. Fuente: Amazon.com Se puede decir que el ciclo comienza con la experiencia de compra de cliente, si este considera que ha sido una gran experiencia atraerá por el boca a boca a más consumidores, lo que provocará un incremento del tráfico de consumo. En este punto la empresa podría vender única y exclusivamente sus productos ganando así más margen de beneficio, aunque también lo podría aprovechar empleando su infraestructura para permitir a terceros comercializar sus productos. Optando por esta última oportunidad y sirviéndose del aumento de tráfico, se consigue atrae a más vendedores, que quieran vender sus productos en Amazon para darles más visibilidad, y también se consigue que los ingresos de la empresa crezcan, aunque en un primer momento sean menores que si vendiera únicamente sus productos. Consecuentemente, a mayor número de vendedores, mayor variedad de productos se venderán en el Marketplace y, por lo tanto, mejor experiencia de compra tendrá el cliente, llegando así al comienzo 17 del círculo virtuoso. Por otro lado, si aumentan los beneficios la compañía podrá optar por dos vías, o distribuye la mayor parte de la ganancia entre sus accionistas o la utiliza para aumentar y mejorar la infraestructura de la empresa. Claramente, optando por la segunda opción se crea un segundo círculo virtuoso. La mejora de su infraestructura abarca dos objetivos. El primero es el de mantener y adaptarse al crecimiento del negocio, es decir, cuando aumentan el tráfico de compras y el número de vendedores es soporte logístico debe ser mayor, lo que implicará una inversión. El segunda es el de mejora, este punto es el que alimenta y genera un segundo círculo virtuoso, ya que una apuesta en la infraestructura reduce a la larga el coste logístico o incluso permite generar nuevos servicios (por ejemplo: Amazon Prime o entrega rápida en menos de 48 horas), la reducción del precio y la mejora de servicio conducirán a un aumento de la experiencia del cliente. Desde el punto de vista logístico el círculo virtuoso se puede desengranar de la siguiente manera (Figura 5): una mayor demanda implica un mayor caudal de productos en movimiento, lo que provocará la necesidad de aumentar la flota y una mayor utilización de esta y por consiguiente, se reducirá el coste de utilización, se reducirán los precios y crecerá la demanda. También, aumentará las solicitudes de mejores servicios, por lo que se deberá aumentar no solo la eficiencia, si no también la mejora de la calidad de la entrega. Lo que se traducirá, también, en un crecimiento de la demanda. Figura 5: Círculo virtuoso de Bezos desde el punto de vista logístico. Fuente [15]. 1.4.2 Funcionamiento Para poder llevar a cabo la principal actividad de Amazon y alcanzar los objetivos planteados en el apartado anterior, es fundamental tener un sistema logístico estructurado y bien definido. Se debe tener en cuenta que, en un día con alta demanda, Amazon puede gestionar una media de 35 pedidos por segundo, de donde se deduce que la infraestructura logística debe ser robusta si se quiere llegar a cubrir las necesidades del cliente correctamente. 1.4.2.1 Pedidos, robots y “caos organizado” En el desarrollo en Amazon de una red logística robusta juega un papel fundamental el grado de automatización de sus almacenes, planificados según la teoría del “caos organizado”. Este tipo de planificación no organiza los artículos por categoría o por temática, como lo puede estar un supermercado, sino que los productos se encuentran ubicados al azar a lo largo y ancho del almacén. “Así los recogedores de pedidos siempre tienen el producto cerca. Además, el sistema calcula a la ruta más corta y se optimiza el recorrido. Es el caos organizado, pero siempre sabemos dónde está el producto en cualquier momento”, según explica Fred Pattje, director de Operaciones de Amazon España [16]. Esto también hace que se reduzcan las probabilidades de que un robot recogedor se equivoque al tener que escoger entres dos productos similares, ya que cada artículo se encuentra rodeados de otros diferentes. Estos robots, serán los encargados de entregar los pedidos a los trabajadores, ahorrando así 1’2 km de distancia recorrida a cada empleado. En este proceso, son primero estos últimos los encargados de indicar a los robots el lugar de los nuevos productos, para que más tardes, puedan gestionarlo según el pedido de los clientes. Una vez el empleado recibe por parte del robot el conjunto de artículos que conforman el pedido, se empaqueta y se sitúa en una cinta transportadora que lo procesa y clasifica según sus características. Dependiendo de esta clasificación, el producto se gestionará a través de una empresa logística un otra. 1.4.2.2 Organización del centro logístico Se podría dividir en dos grandes partes el centro logístico de Amazon, la primera el punto de recepción del material y el segunda el del procesado y envío de pedidos. En el primero se realiza un control de calidad, se toman medidas de los artículos, se pesan y se les realiza fotos que son cargadas a la web. La segunda parte, se sigue el procedimiento explicado en el apartado anterior: se envía los pedidos empleando el uso de robots, cintas transportadoras y clasificadoras. En resumen, el esquema que sigue un producto es el siguiente: Recepción de nuevos productos, procesamiento, almacenamiento, recepción de pedidos, selección de productos que componen el pedido, empaquetamiento, asignación del pedido según sus características, envío a centros de clasificación, procesado en centros de clasificación, asignación de envío en última milla y recorrido de la última milla hasta el cliente. 1.4.3 Tipos de instalaciones La red logística de Amazon está compuesta por un estado del arte de tecnología y gran variedad de edificios de diferente tipo y tamaño, que dan soporte a todo el negocio y que hacen posible la entrega de pedidos a los clientes: 19 1. Centros logísticos “clasificables”: en ellos se gestionan todo lo relacionado con la logística asociada a los pedidos del cliente. Se almacenan productos, se empaquetan y se distribuyen buscando optimizar la eficiencia y eficacia, es decir, maximizando la satisfacción en la experiencia de compra del cliente. Pueden albergar hasta 1500 empleados y van asociados a marcados procesos de automatización, como el caso de los Robots, explicado en el apartado anterior. También, existen departamentos de mejora continua que buscan reducir desperdicios en la cadena de valor. 2. Centros logísticos “clasificables”: pueden ser más grande que los anteriores y están enfocados en productos grandes que no pueden ser clasificados de manera automática por robots como en el caso anterior. Va dirigido especialmente a artículos grandes de jardín, muebles, etc. 3. Centros de clasificación: reciben exclusivamente paquetes (pedidos consolidados) que deben ser enviados a centros de entrega. En estos centros, los pedidos son clasificados teniendo en cuenta el lugar y el tiempo requerido de entrega y según esto se almacenan en un camión u otro. 4. Centros especializados: procesan artículos de determinadas categorías que suelen sufrir picos de demanda. También son los centros que absorben los excesos de pedidos en campañas de gran flujo de compras como La Navidad o el Black Friday. 5. Centros de entrega: Se sitúan muy cerca del consumidor final, de manera que los pedidos puedan ser repartidos rápidamente, sirven de apoyo para recorrer la última milla 6. Centros de recepción (Figura 7). Son los que reciben grandes cantidades de productos por parte de los vendedores o proveedores. En ellos estos productos se envían en diferentes cantidades a los centros logísticos según la demanda en cada uno de ellos. 27 2 -EL PROBLEMA DEL VIAJANTE, ESTADO DEL ARTE l problema del viajante, conocido por sus siglas en inglés como el TSP (Travelling salesman problem), consiste en dado un conjunto de nodos o ciudades, unidos entre sí por arcos, tratar de encontrar el camino más corto que pase por todos los nodos solo una vez y cuyo punto final e inicial sea el mismo. Un problema parecido fue propuesto por los matemáticos Sir William Rowan Hamilton y Thomas Kirkman, donde se puede apreciar en un juego creado por el primero de ellos, W.R. Hamilton, llamado “The Icosian Game” que consistía en definir un ciclo Hamilton a través de las aristas y vértices de un dodecaedro visitando única y exclusivamente una vez cada vértice. Por otra parte, el TSP, apareció por primera vez en un libro de viajes editado en Alemania, donde se mencionaba y definía el problema, pero sin llegar a recibir ningún enfoque ni trato matemático. Este tratamiento matemático del problema fue desarrollado por Karl Menger en Viena y Harvard en los años 30 del siglo pasado. Más tarde, el TSP fue promovido por Merril Flood y Hassler Whitney gracias a su relación con RAND Corporation. [22]. Esto último, sumado a su facilidad de formulación y su gran complejidad (NP-Hard o NP-Completo) hizo que el estudio del problema del viajante se popularizara en los años venideros. El “Travelling Salesman Problem” puede ser formulado de diferentes maneras, una de las más E “Así como el hierro se oxida por falta de uso, también la inactividad destruye el intelecto.” - Leonardo Da Vinci - conocidas e importantes es la de Miller, Tucker y Zemlin [23]: dado un número de ciudades 𝑛 donde 𝑐𝑖𝑗 es la distancia entre cada una de ellas se define la variable dicotómica 𝑥𝑖𝑗como: 𝑥𝑖𝑗={1 𝑠𝑖 𝑒𝑙 𝑐𝑎𝑚𝑖𝑛𝑜 𝑒𝑠𝑐𝑜𝑔𝑖𝑑𝑜 𝑣𝑎 𝑑𝑒 𝑙𝑎 𝑐𝑖𝑢𝑑𝑎𝑑 𝑖 𝑎 𝑙𝑎 𝑐𝑖𝑢𝑑𝑎𝑑 𝑗 0 𝑒𝑛 𝑜𝑡𝑟𝑜 𝑐𝑎𝑠𝑜 (1) También se define la variable binaria 𝑢𝑖 para 𝑖=1…𝑛, quedando la formulación del problema de la siguiente manera: Minimizar: ∑ ∑ 𝑐𝑖𝑗𝑥𝑖𝑗 𝑛 𝑗=1,𝑗≠𝑖 𝑛 𝑖=1 (2) Sujeto a: ∑ 𝑥𝑖𝑗=1 𝑛 𝑖=1,𝑖≠𝑗 𝑗=1…𝑛 (3) ∑ 𝑥𝑖𝑗=1 𝑛 𝑗=1,𝑗≠𝑖 𝑖=1…𝑛 (4) 𝑢𝑖−𝑢𝑗+𝑛𝑥𝑖𝑗<𝑛−1 2≤𝑖≠𝑗≤𝑛 (5) 1≤𝑢𝑖≤𝑛−1 2≤𝑖≤𝑛 (6) 𝑢𝑖∈ℤ 𝑖=2…𝑛 (7) 𝑥𝑖𝑗∈{1,0} 𝑖,𝑗=1…𝑛 (8) 𝑐𝑖𝑗>0 𝑖,𝑗=1…𝑛 (9) La función (2) es la función objetivo y minimiza el camino del viajante, las restricciones (3) y (4) obligan a que cada ciudad sea visitada una única vez y a que se salga siempre de la que se es visitada, respectivamente. Mientras que las restricciones (5) y (6) evitan que se creen subtours entres el conjunto de ciudades. 29 2.1 Aplicaciones reales Aunque el problema definido por el TSP es ya de por sí útil, también se pueden encontrar diferentes aplicaciones del mismo que lo hacen aún más versátil. A continuación, se muestran varios planteamientos del problema cuya aplicación puede o no modificar el problema inicial, siendo siempre como referencia el TSP. 2.1.1 Ruta de vehículos Es parecido al TSP, pero en lugar de tener un solo viajante se tiene una flota de vehículos que parten y vuelven a un mismo punto. De manera que todos los nodos sean visitados una única vez por uno de los 𝑘 vehículos. De esta forma, para visitar un conjunto de 𝑛 ciudades será necesario un número de 𝑘 rutas. Por lo tanto, el objetivo del problema podrá ser minimizar la distancia total recorrida por el conjunto de vehículos o bien minimizar el número de vehículos empleados. Además, a este problema se le suelen añadir restricciones que impidan que un solo vehículo visite todos los nodos, ya que en ese caso nos encontraríamos frente al TSP. Una de las restricciones más comunes es la de la capacidad, donde cada vehículo tiene que servir cierta cantidad de bienes a las diferentes ciudades no pudiendo superar una capacidad máxima de artículos entregados 𝐶. También existen restricciones temporales, es decir, a cada nodo se le asocia una ventana temporal, fuera de la cual no podrá ser visitado. 2.1.2 Optimización de circuitos impresos de PCB Se parte de una placa PCB donde ya se tiene distribuidos todos los módulos y puntos de conexión y a partir de aquí nacen dos problemas a optimizar. El primero de ellos se trata del orden de perforación, donde cada posición que debe ser perforado equivaldría a una ciudad en el problema del viajante, por lo que el objetivo es que la máquina perforadora haga el recorrido mínimo, lo que a escalas industriales supondría un importante ahorro de costes. El segundo de ellos consiste en conectar todos los puntos de la placa con sus respectivos chips (al menos dos a dos) de manera que la cantidad de cable empleado sea la mínima sin que, además, haya ninguna interferencia entre ellos. [24] 2.1.3 Minimizar gasto del empapelado de una pared Presentado por Garfinkel [25] en 1977, este problema consiste en dado un rollo de empapelar de longitud 𝑊 y una pared de alto 𝑤 se deben cortar 𝑛 hojas para empapelar la pared (entendiéndose que con un único rollo es suficiente), de manera que 𝑛=𝑖𝑛𝑡𝑒𝑔𝑒𝑟 (𝑊 𝑤). Suponiendo que el corte de la hoja i comienza en la posición 𝑠𝑖 y que el corte final termina en la posición 𝑓𝑖, se tiene que: 𝑓𝑖=𝑠𝑖+𝑙𝑖 𝑖=1…𝑛 (10) Donde la longitud de 𝑙𝑖 equivale a 𝑙𝑖 veces el patrón que sigue el estampado del papel. Por otra parte, la cantidad de papel que se pierde tras cortar la hoja j después de la hoja i es: 𝑐𝑖𝑗=𝑠𝑗−𝑓𝑖 𝑖,𝑗=1…𝑛 (11) Suponiendo que el rollo finaliza en la posición 𝑓0, tras la última hoja el rollo debe acabar en el mismo punto de partida 𝑠0=𝑓0. Esto hace que se le añada una hoja más adicional al problema, por lo tanto, la dimensión sería de (𝑛+1) ciudades y su resolución consistiría en minimizar 𝑐𝑖𝑗, que es equivalente a la distancia en el TSP original. 2.1.4 Secuenciación de trabajos Este problema consiste en secuenciar 𝑛 trabajos en una misma máquina, donde el cambio de un trabajo a otro implica un tiempo de preparación 𝑐𝑖𝑗. Para lo que se trata de minimizar la suma total de tiempos de preparación, de manera que se reduzcan los tiempos muertos que no aportan valor al producto final. Dada una permutación de 𝑆 con un determinado orden de 𝑛 trabajos, el tiempo para realizar todos los trabajos será: ∑(𝑐𝑖𝑆(𝑖) 𝑛 𝑖=0 +𝑝𝑖𝑆(𝑖))=∑𝑐𝑖𝑆(𝑖) 𝑛 𝑖=0 +∑𝑝𝑗 𝑛 𝑖=0 𝑖,𝑗=1…𝑛 (12) En la práctica, esta aplicación del problema suele seguir la variante asimétrica del TSP, ya que no es lo mismo pasar del trabajo A al B, que del B al A. Un caso práctico sería que para realizar el trabajo A se requieren altas temperaturas mientras que, para el B bajas. Si el tiempo de calentar es diferente al de enfriar, el resultado sería un TSP asimétrico. 2.1.5 Reducción de la dispersión de pedidos en la industria del vidrio Otra aplicación del TSP interesante y parecida a la anterior es la propuesta por Madsen [26]. En las industrias que emplean láminas grandes para ser cortadas (como es en la industria del vidrio) y formar otras piezas más pequeñas, que serán las que compre el cliente, se dan principalmente dos tipos de problemas. El primero es la optimización del espacio de la lámina, con el fin de evitar desperdicios. En la industria del vidrio el proceso de corte tiene tres etapas, la primera es la división de la lámina en varias secciones, la segunda es cortar transversalmente la lámina en varias partes y, por último, cada parte es reducida por uno ser sus laterales, de manera que se hayan definido las tres dimensiones de la pieza, como se muestra en la Figura 10. El segundo problema, y menos conocido, es evitar que el 31 pedido de un cliente sea dividido en varias láminas. Es decir, si un cliente hace un pedido de varias piezas, es posible que no todas se hagan en la misma lámina y que por optimizar los desperdicios, las piezas estén dispersas en el conjunto de láminas. Este problema adquiere mucha importancia en la industria del vidrio, ya que es muy difícil almacenar las piezas. No pueden ser almacenadas en grandes pilas, sino que deben ser almacenadas individualmente, lo que supone un alto coste de tiempo y espacio. Por lo tanto, reducir el número de láminas entre las que se distribuye un pedido es fundamental. Ambos objetivos no tienen por qué ser contradictorios. Se puede primero optimizar la colocación de las piezas de todos los pedidos en el conjunto de láminas y en un segundo momento, secuenciar las láminas para reducir la distribución de piezas de un mismo pedido. Esto es, que si el pedido 𝑘 tiene piezas en las láminas 𝑖 y 𝑗, éstas deberían fabricarse consecutivamente para que el tiempo que esté el pedido k fabricándose sea el mínimo posible. Figura 10: Ejemplo típico de un mosaico de corte para una sola lámina en la industria del vidrio. [26] A la problemática de la secuenciación se le puede aplicar el TSP. En el problema se intenta que cada vez que la fabricación de un pedido ha comenzado, este no sea interrumpido. Esto se traduce en reducir las discontinuidades que se producen cuando la pieza de un pedido se fabrica en una lámina y en la siguiente no se hace ninguna pieza perteneciente al mismo pedido. Se define como 𝑐𝑖𝑗 el número de pedidos en la lámina 𝑖 que no se fabrican en la lámina 𝑗. Se define 𝑥𝑖𝑗 como una variable de decisión que vale 1 si la lámina 𝑗 se fábrica inmediatamente después de la lámina 𝑖. Ejemplo 2.1: Se tienen cuatro láminas entre las que se distribuyen siete pedidos: Pedidos asociados a cada lámina Lámina nº 1: 1 3 4 6 2: 1 2 4 6 3: 1 2 5 7 4: 2 3 5 7 Según esta distribución la matriz de costes debería quedar de la siguiente manera: 𝐶=[∞ 1 1 ∞ 3 3 2 3 3 2 3 3 ∞ 1 1 ∞] De manera que 𝑐23=2 indica que dos pedidos de la lámina 2 no continúan fabricándose cuando la lámina 3 se ha producido inmediatamente después de la dos, concretamente los trabajos son el 4 y el 6. Para la secuencia 𝑆={1,2,3,4} se tiene que: Lámina 1: 1 3 4 6 Lámina 2: 1 2 4 6 Lámina 3: 1 2 5 7 Lámina 4: 2 3 5 7 El cuadrado significa que el pedido k ha sido interrumpido tras el cambio de lámina. Para este ejemplo han sido cuatro las veces que se han interrumpido pedidos, aunque solo uno sufre una discontinuidad, el 3. Aunque la matriz 𝑐𝑖𝑗 recoja el número de veces que un pedido no se fábrica en la siguiente lámina, 𝑁0, y no el número de discontunidades que un pedido sufre, 𝑁𝐷, es lo mismo minimizar ambos números: 𝑁0=𝑁𝐷+ 𝑛ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑝𝑒𝑑𝑖𝑑𝑜𝑠− 1 Por lo tanto, el problema de reducción de dispersión de pedidos se construirá cambiando la función objetivo del TSP (ecuación (2)) y sustituyéndola por las (13) y (14): Minimizar: 𝑁0 (13) 𝑁0=∑ ∑ 𝑐𝑖𝑗𝑥𝑖𝑗 𝑛 𝑗=1,𝑗≠𝑖 𝑛 𝑖=1 𝑖,𝑗=1,…,𝑛 (14) 33 2.1.6 Generación de listas de reproducción según similitudes Un enfoque interesante del TSP es el usado por Phole, Pampalk y Widmer [27], el problema consiste en ordenar una lista de reproducción según las similitudes musicales entre canciones. Es decir, en un móvil se tienen 𝑛 canciones y en el momento de escuchar las canciones, cuando se acabe una, se quiere comenzar con otra que sea parecida musicalmente, de manera que el cambio no sea brusco. En la Figura 11 se puede ver como resultaría el modulador de la lista de reproducción. Girando la rueda se seleccionaría una canción, donde según la longitud del recorrido de la rueda, la diferencia con la canción actual será mayor o menor. Es decir, la rueda se mueve por la secuencia óptima o la que más se acerque al óptimo y va seleccionando canciones en función de su posición. Para que el cambio entre canción y canción no sea brusco, la ‘distancia’ que las separas debe ser lo mínimo, entendiéndose distancia por el parecido musical entre canción y canción. Figura 11: ‘Traveler Sound Player’, regulador de canciones. Para este problema la formulación es idéntica a la del TSP, lo novedoso es la forma en la que se construye la matriz de distancias 𝑐𝑖𝑗. A cada canción (ciudad) 𝑛 se le asocia un MFCC (Mel Frequency Cepstral Coefficients, en español: Coeficientes Cepstrales en las Frecuencias de Mel), coeficientes que representan el habla según la percepción auditiva humana. Una vez hecho esto, se representa los MFCCs en un modelo de mezcla gaussiana (GMM). Un GMM es un modelo probabilístico que asigna a cada observación un clúster, maximizando la probabilidad a posteriori de que el componente pertenezca a dicho clúster. Partiendo del GMM, se calcula la distancia en el gráfico entre la canción 𝑖 y la canción 𝑗, y este valor se asigna a la matriz 𝑐𝑖𝑗. 2.2 Variantes del TSP En este apartado se verán seis variantes del TSP. Algunas se obtienen realizando pequeños cambios en el problema original, mientras que otras tienen un poco más de complejidad. 2.2.1 Minimizar el camino hamiltoniano El problema original del camino hamiltoniano consiste en encontrar un ciclo en un conjunto de grados que incluya a todos los nodos del mismo; llamado así en referencia al inventor del juego “The Icosian Game”, explicado en la introducción del apartado 2. Este se puede considerar una variante del TSP donde la distancia 𝑐𝑖𝑗 de los arcos adyacentes a un nodo escogido es 0 y para aquellos no incluidos en el ciclo es 1, de manera que se penaliza la exclusión de nodos para encontrar un camino hamiltoniano. Figura 12: “The Icosian Game”. Fuente: Royal Irish Academy Library en Twitter.com Como muestran Lawler et al. [28] existen otras modificaciones a este problema. Una variante de este consistiría en quitar la restricción de acabar y termina siempre en el mismo punto. Lo cual se podría solucionar añadiendo una columna y filas (𝑛+1)-ésima de valor 0 a la matriz de distancias 𝑐𝑖𝑗. Si en cambio, se quisiera comenzar en un nodo determinado 𝑠 y terminar en otro 𝑡, habría que sustituir las ciudades 𝑠 y 𝑡 por otra con ciudad 𝑢. De esta forma el número de ciudades sería igual a (𝑛−1), quedando la nueva matriz de distancias 𝑐𝑖𝑗 ′ de la siguiente manera: 𝑐𝑖𝑗 ′={𝑐𝑠𝑗 𝑠𝑖 𝑖=𝑢 𝑐𝑖𝑡 𝑠𝑖 𝑗=𝑢 𝑐𝑖𝑗 𝑒𝑛 𝑜𝑡𝑟𝑜 𝑐𝑎𝑠𝑜 𝑖,𝑗=1…(𝑛−1) () De la misma forma, si se quisiera empezar en la ciudad 𝑠 y acabar en cualquier otra, solo habría que poner a 0 las entradas del nodo 𝑠, es decir toda la columna 𝑠 de la matriz 𝑐𝑖𝑗. Por último, también 35 se podría hacer lo contario, es decir, impedir que 𝑠 sea el punto de inicio o final. Para ello, habría que crear una ciudad copia, que será llamada 𝑡, de manera que, en la matriz de distancias, 𝑐𝑖𝑠 y 𝑐𝑡𝑗 fueran números lo suficientemente grandes como para que nunca fueran incluidos por la función objetivo. 2.2.2 TSP con ciudades repetidas Otra variante simple del TSP sería incluyendo la posibilidad de poder visitar una ciudad más de una vez, en lugar de una única sola vez como plantea el problema original. Parta ello, se sustituye la matriz 𝑐𝑖𝑗 por la matriz 𝑐’𝑖𝑗, donde: 𝑐’𝑖𝑗= la distancia más corta del camino entre los nodos 𝑖 y 𝑗 (incluyendo en estos caminos otros posibles nodos). Para el cálculo de 𝑐′𝑖𝑗 se puede usar el algoritmo de Floyd-Warshall [29], que consiste en la comparación de las distancias de la matriz 𝑐𝑖𝑗 para obtener el camino más corto, aunque sea pasando por otros vértices. Este algoritmo presenta un orden de complejidad 𝑂(𝑛3) y su pseudo código es el siguiente: Figura 13. Pseudocódigo del algoritmo de Floyd-Warshall. Fuente: https://resources.mpi-inf.mpg.de/ Este tipo de versión del problema del viajante es fundamental para aquellos grafos en los que para visitar un nodo y salir de él es estrictamente necesario pasar por otro al menos dos veces. En la Figura 14 se observa un ejemplo, donde para llegar al nodo A es necesario pasar antes por el nodo B. FloydWarshall() for k = 1 to n do for i=1 to n do for j=1 to n do d(i,j)=min{d(i,j),d(i,k)+d(k,j)} end end end • En el subtour de la derecha se puede ver que a máquina 2 se le asigna el operario 4 y el operario 2 es asignado a la máquina 4. Figura 15: Subtours para un problema de 5 ciudades. Fuente: chegg.com Claramente, esta solución en el problema del viajante carecería de sentido físico. 2.3.2 La restricción del subtour Para poder forzar al problema anterior a que no se generen subtours se pueden introducir diferentes restricciones, por ejemplo, la desarrollada por Dantzig et al. [34]: ∑∑𝑥𝑖𝑗≤|𝑆|−1 𝑗∈𝑆𝑖∈𝑆 (43) ∑∑𝑥𝑖𝑗≥1 𝑗∈𝑆 𝑖∈𝑆 (44) Donde se define 𝑆 como un subconjunto no vacío de 𝑁={1,…,𝑛} y |𝑆| el cardinal del subconjunto 𝑆. Para el ejemplo de la Figura 15, se puede observar cómo ambos subtours incumplen las restricciones (43) y (44), donde 𝑆={1,3,5} 𝑜 {2,4}. En el primer subconjunto, el cardinal es 3, por lo que la restricción (43) se incumple, ya que el sumatorio de todos los arcos que unen los vértices del subconjunto también es igual a 3; por lo que se incumple la inecuación; esto mismo ocurre para el segundo subconjunto. En la restricción (44), en el lado izquierdo de la inecuación, se puede observar que el sumatorio cuenta todos los arcos salientes del subconjunto 𝑆, por lo que un número mayor que 0 en el resultado del sumatorio confirma la inexistencia de subtours en el subconjunto evaluado. No obstante., el principal problema de estas restricciones es su elevado número, ya que será igual al cardinal del conjunto potencia de N menos dos (excluyen el subconjunto vacío de N y el subconjunto igual a N). Es decir, el número de restricciones sería igual a 2|N|−2, donde |N|=𝑛. Una variación más compacta de estas restricciones es la propuesta por Miller, Tucker & Zemlin [23], que es la presentada en el apartado 2, ecuación (5). 𝑢𝑖−𝑢𝑗+𝑛𝑥𝑖𝑗<𝑛−1 2≤𝑖≠𝑗≤𝑛 (5) 43 En ella se toma arbitrariamente el vértice 1 como punto de partida, de ahí que 𝑖 y 𝑗 estén comprendidos entre 2 y 𝑛. Por otro lado, 𝑢𝑖 y 𝑢𝑗 son números reales arbitrarios que impedirán la creación de subtours. Si se vuelve a tomar como ejemplo el subtour izquierdo de la Figura 15, los valores de 𝑢𝑖 quedarían: 𝑢2=0 y 𝑢4=1 por lo que para ir del vértice 4 al 2 la inecuación se incumpliría. Se comprueba entonces, que el único vértice que puede ser el inicial y final es el 1 y que para que se cumpliera la inecuación, el vértice 2 y 4 deberían estar en el primer subconjunto. Es importante recalcar que el número de restricciones disminuye a (𝑛−1)2. Una variante del TSP, presentada también por Miller et al. Miller y que aprovecha la ecuación anterior es aquella en la que se permiten subtours que parten todos del vértice 1 y para los que hay un límite máximo de 𝑝 ciudades que puede abarcar. Para ello la ecuación quedaría del siguiente modo: 𝑢𝑖−𝑢𝑗+𝑝𝑥𝑖𝑗≤𝑝−1 2≤𝑖≠𝑗≤𝑛 (5) Por otra parte, sería necesario modificar las restricciones (3) y (4) para que desde la ciudad 1 pudieran partir diferentes subtours. Por lo que las restricciones que las sustituirían quedarían de la siguiente manera, respectivamente. ∑ 𝑥𝑖𝑗=1 𝑛 𝑖=1,𝑖≠𝑗 𝑗=2…𝑛 (45) ∑ 𝑥𝑖𝑗=1 𝑛 𝑗=1,𝑗≠𝑖 𝑖=2…𝑛 (46) 2.3.3 El problema de la asignación cuadrática Este problema consiste en situar 𝑛 instalaciones o departamentos en 𝑛 posiciones. Fue presentado por primera vez por Koopmans y Beckmann [35], y para su planteamiento se deben tener en cuenta tres matrices que recogen las características del problema: • La matriz de flujo 𝑓𝑖𝑗, que define el flujo entre una instalación ℎ y otra 𝑘, en la práctica este flujo puede corresponder a unidades de materiales, personas, electrones, precio, etc. • La matriz de distancias 𝑑ℎ𝑘, que define la distancia que hay entre la posición ℎ y la 𝑘. • La matriz de costes de instalación 𝑐𝑖𝑗ℎ𝑘, que recoge el coste total de asignar la instalación 𝑖 en la posición 𝑘 y la instalación 𝑗 en la posición ℎ. De esta forma las restricciones del problema y la función objetivo quedarían de la siguiente manera: Minimizar: ∑∑∑∑𝑐𝑖𝑗ℎ𝑘𝑥𝑖ℎ𝑥𝑗𝑘 𝑛 𝑘=1 𝑛 ℎ=1 𝑛 𝑗=1 𝑛 𝑖=1 (47) Sujeto a: ∑𝑥𝑖ℎ=1 𝑛 ℎ=1 𝑖=1…𝑛 (48) ∑𝑥𝑖ℎ=1 𝑛 𝑖=1 ℎ=1…𝑛 (49) 𝑐𝑖𝑗ℎ𝑘=𝑓𝑖𝑗𝑑ℎ𝑘 𝑖,𝑗,ℎ,𝑘=1…𝑛 (50) 𝑥𝑖ℎ∈{0,1} 𝑖,ℎ=1…𝑛 (51) Donde 𝑥𝑖ℎ es una variable binaria que valdrá 1 en caso de que la instalación 𝑗 se instale en la posición ℎ y 0 en caso contrario. En la práctica este problema se puede utilizar, por ejemplo, para el diseño de aeropuertos en los que para los transbordos se querrá reducir la distancia total recorrida entre terminales por la suma total de pasajeros. En este caso los pasajeros que van de la terminal A a la B serán recogidos en la matriz de flujo, mientras que la distancia entre la posición E y la posición W, lugar donde se sitúan las terminales respectivamente, será recogida en la matriz de distancia. Un ejemplo parecido se puede utilizar para situar los departamentos de un hospital, donde los pacientes tendrán que pasar de un médico a otro según su patología. Aunque también puede aplicarse para el diseño de una fábrica, en la que se reducirá el tiempo de transporte de productos semielaborados o también para el diseño de circuitos electrónicos, en el que el precio de los conectores varía según el dispositivo que haya que conectar. 2.3.4 El problema del camino más largo En el apartado 2.2.2 se vio como dado un grafo 𝐺 que contenía un conjunto de nodos 𝑁, unidos entre sí por un conjunto de arcos 𝐴, se podía calcular la distancia mínima entre dos vértices mediante el algoritmo de Floyd y Warshall, cuyo orden de complejidad era de 𝑂(𝑛3). En el problema que se discute en este apartado el objetivo es el opuesto, se pretende buscar el camino más largo para llegar 45 del nodo 𝑖 al nodo 𝑗. Aunque, pueda parecer trivial o igual que complejo que el problema del camino más corto, en realidad se trata de un algoritmo NP-hard. Esto se puede comprobar reduciendo el problema a la búsqueda del camino crítico donde cada arco tiene el mismo valor (1, por ejmplo), por lo que el problema se reduce a la búsqueda de un camino hamiltoniano en el grafo 𝐺. El simple problema de decisión, es decir, indicar si existe o no un camino hamiltoniano con al menos 𝑘 vértices en dicho grafo, siendo 𝑘≤𝑛, es ya de por sí un problema NP-hard. [36], lo que convierte al problema del camino más largo también con la misma complejidad. Por otra parte, es claro, que si el 𝐺 es un grafo completo (Figura 16, muestra un grafo completo en el que cada vértice está conectado a todos los demás mediante un arco), el presente problema es un TSP, dónde en vez de buscar el camino mínimo se busca el máximo. Una correcta transformación del TSP en el problema del camino más largo consistiría en cambiar la matriz de costes 𝑐𝑖𝑗 en la matriz 𝑐𝑖𝑗 ′, cambiar el objetivo de la función a ‘maximizar’ y aplicar la variante del problema del TSP en la que se quiere ir del nodo 𝑠 al nodo 𝑡 (explicado en el apartado 2.2.1). La transformación consistirá en 𝑐𝑖𝑗 ′=𝑀−𝑐𝑖𝑗, donde 𝑀 es lo suficientemente grande como para que no existan distancias negativas. [37] Figura 16: Grafo completo. Fuente Wikipedia Commons. 2.3.5 Árbol de cobertura mínimo Un árbol de cobertura mínimo consiste en un subconjunto de arcos conectados y con un peso asociado a cada uno en un grafo no dirigido y conexo que conecta a todos los nodos, de manera que no se genere ningún ciclo y que la suma de todos los pesos de los arcos que componen el subconjunto sea mínima. Es decir, encontrar un árbol de cobertura en el grafo 𝐺 cuya suma de pesos sea la mínima posible. El problema de encontrar un árbol de cobertura se puede asimilar al de encontrar un camino hamiltoniano. De hecho, todo camino hamiltoniano es un árbol de cobertura y todo árbol de cobertura es un camino hamiltoniano en el que se permite que un nodo tenga más de dos conexiones con otros nodos. De esta manera, si encontrar un árbol de cobertura es una relajación del camino hamiltoniano, también encontrar un árbol de cobertura mínimo es una relajación del problema del viajante, al que se le quita la misma restricción que para el caso anterior. Figura 17: Ejemplo de mínimo árbol de cobertura. [38] Para entender mejor este problema, se puede observar la Figura 17, en la que se ve la solución al problema del árbol de cobertura mínimo, con los respectivos pesos de cada arco. El peso total de la solución es de 37 y se hace un solo cambio se comprueba que la solución no es única: si se elimina el arco (𝑏,𝑐) y se sustituye por el arco (𝑎,ℎ) la solución al problema sigue valiendo lo mismo. 2.3.6 El problema del cartero chino El matemático chino Mei-Ko Kawn [39] se hizo la pregunta de dado conjunto de calles que deben recibir un servicio postal y un cartero que debe hacer una ruta pasando por todas ellas y acabar en el mismo punto de partida, se debe buscar la ruta mínima. Es decir, dado un grafo 𝐺 (𝑉,𝐴) , siendo 𝐴 el conjunto de los arcos que unen los vértices, se deben recorrer todos los arcos pertenecientes a 𝐴. Este problema en la práctica se puede aplicar a más situaciones. Por ejemplo, a la recogida de nieve en las calles, a la recogida de basura o limpieza de calles, a la inspección de tuberías o cables, etc. El problema del cartero chino (CPP, Chinese Postman Problem) y sus variantes tienen su origen en el análisis de Euler [40] a un puzle muy popular en su época conocido como El problema de los puentes de Königsberg. Consistía en atravesar todos los siete puentes de Königsberg (Figura 18) solo y exclusivamente una vez. Euler resolvió el problema (aunque no llegó a demostrarlo del todo) 47 afrimando que un ciclo existe en un grafo si y solo sí cada vértice está conectado a un número de aristas par. Esto se pueden entender lógicamente pensando que, al llegar a un vértice por un arco, debe existir otro por el que salir. De esta manera, se define un ciclo que atraviesa todos los arcos de un nodo exactamente una sola vez como Ciclo euleriano. Cuando cada arco tiene un peso y el objetivo es encontrar un ciclo euleriano relajado con el camino mínimo, el problema es el CPP, aunque en éste la restricción de visitar una sola vez cada arco se relaja a visitarlo al menos una. Figura 18: Problema de los siete puentes de Königsberg [40]. El problema del cartero chino se puede formular matemáticamente como, dado un grafo 𝐺(𝑉,𝐴), donde 𝑣 es un conjunto de vértices 𝑛, 𝐴 es un conjunto de arcos que une dichos vértices, y cada arco (𝑖,𝑗) que conecta el vértice 𝑖 con el vértice 𝑗 tiene un coste asociado 𝑐𝑖𝑗 mayor o igual que cero, 𝑥𝑖𝑗 es el número de veces que un arco se emplea en la ruta para conectar todos los arcos 𝐴, se intenta encontrar la ruta óptima que minimice la distancia total recorrida. Minimizar: ∑ ∑ 𝑐𝑖𝑗𝑥𝑖𝑗 𝑛 𝑗=1,𝑗≠𝑖 𝑛 𝑖=1 (52) Sujeto a: ∑𝑥𝑖𝑘 𝑛 𝑖=1 −∑𝑥𝑘𝑗 𝑛 𝑗=1 =0 𝑘=1…𝑛 (53) 𝑥𝑖𝑗+𝑥𝑗𝑖≥1 𝑖,𝑗=1…𝑛 (54) 𝑥𝑖𝑗≥0 𝑖,𝑗=1…𝑛 (55) 49 2.4 Algoritmos brutos y complejidad del TSP Para solucionar problemas de optimización combinatoria es fundamental el uso de algoritmos. Entendiéndose estos como un conjunto de pasos que se van ejecutando uno detrás de otro y que resuelven un problema según unos datos de partida. En este apartado se verán dos algoritmos que resuelven el TSP, el primero para el TSP puro y el segundo para un caso especial de este, y otro que resuelve el problema del camino más corto, visto en el apartado 2.2.2. Por último, se hará un breve estudio de la complejidad de los algoritmos. 2.4.1 Algoritmo de fuerza bruta El problema del TSP se puede definir como una pregunta y un conjunto de datos necesarios para responderla. Por lo que el problema podría ser representado de la siguiente manera: De esta forma, un algoritmo para resolver el TSP, debe recibir como datos de entrada el número n y la matriz C y deberá devolver como dato de salida un camino mínimo que una todos los puntos, de manera que se pueden definir como un a permutación cíclica. Un algoritmo sencillo, aunque extremadamente ineficiente, es el de fuerza bruta. Consiste en calcular la longitud de todos los caminos posibles, es decir, de todas las permutaciones cíclicas del conjunto de nodos N, compararlos y obtener así el mínimo de todos ellos, siento esta la solución final. El pseudo código de este algoritmo se muestra en la Figura 19. DATOS: Número entero 𝑛≥3, matriz 𝑛× 𝑛 𝐶=(𝑐𝑖𝑗), donde cada 𝑐𝑖𝑗 es un número real mayor o igual que 0. PREGUNTA: ¿Qué permutación 𝜋 de los números enteros que van de 1 a 𝑛 minimiza la suma de ∑𝑐𝑖𝜋(𝑖) 𝑛 𝑖=1 ? Figura 19: Pseudo código del algoritmo de la fuerza bruta. 2.4.2 Algorimto del camino mínimo Otro algoritmo de programación dinámica es el presentado en la Figura 20, que resolverá el problema de la ruta mínima, definido esquemáticamente de la siguiente manera: La principal restricción que se elimina es la necesidad de visitar todos y cada uno de los nodos. Por lo que para su resolución se definirán otras variables que permiten construir una solución de manera más eficiente. Se define coste[𝑗,𝑖] como la distancia recorrida desde la ciudad 1 hasta la ciudad i, pasando por todos los nodos menores o iguales que j. Donde 𝑖≠1 y 𝑗≥1. Por otra parte, se hace uso en el algoritmo de una variante de la ecuación (57), en la que se busca el camino más corto desde la ciudad 1 hasta la ciudad i con un número de nodos menor o igual que j, como se muestra en la ecuación coste[𝑗,𝑖]=min{coste[𝑗−1,𝑖],min 𝑘≠𝑖,1{coste[𝑗−1,𝑘]+𝑐𝑘𝑖} } (56) * Entrada: Número entero 𝑛≥3, matriz 𝑛×𝑛 𝐶=(𝑐𝑖𝑗), donde cada 𝑐𝑖𝑗 es un número real mayor o igual que 0. * Salida: El camino más corto que uno todos los nodos 𝑁, que empieza en 1 y acaba en n. comienzo for todas las permutaciones cíclicas 𝜋 de {1,…,𝑛} do coste = ∑𝑐𝑖𝜋(𝑖) 𝑛 𝑖=1 ; if coste < min then min = coste mejor_camino = 𝜋 finaliza if finaliza for salida mejor_camino finaliza algoritmo DATOS: Número entero 𝑛≥3, matriz 𝑛×𝑛 𝐶=(𝑐𝑖𝑗), donde cada 𝑐𝑖𝑗 es un número real mayor o igual que 0. PREGUNTA: ¿Cuál es el camino más corto para ir de la ciudad 1 a la n? 51 Para buscar la distancia mínima entre 1 e i se compara todos los caminos con un número de nodos menor o igual que 𝑗−1 y se obtiene un camino cuya penúltima ciudad en visitar es k. Si el camino resultante es mejor que el actual, se actualiza el mejor camino actual con la solución recién obtenida, hecho esto se aumenta el número j y se vuelve a realizar el mimo procedimiento hasta que 𝑗=𝑛. Figura 20: Algoritmo que resuelve El problema del camino mínimo. 2.4.3 El TSP pequeño Este método fue presentado por Gabovich [41] y consiste en resolver el TSP cuando la matriz de costes 𝐶 de dimensión 𝑛×𝑛 es considerada pequeña. Se define matriz pequeña 𝑛×𝑛 si existen los * Entrada: Número entero 𝑛≥3, matriz 𝑛×𝑛 𝐶=(𝑐𝑖𝑗), donde cada 𝑐𝑖𝑗 es un número real mayor o igual que 0. * Salida: El camino más corto que empieza en 1 y acaba en n. begin for 𝑖=2,3,…,𝑛 do coste[1, i] = 𝑐1𝑖; mejor_camino[1, i] = (1,i); end for 𝑖=2,3,…,𝑛 do for 𝑖=2,3,…,𝑛 do coste[j,i] = min k≠1,i{coste[j−1,k]+𝑐𝑘𝑖}; se estable k como la ciudad para la que el coste es mínimo; mejor_camino[j,i] = (mejor_camino[j-1,k], i) end if coste[j−1,i]<coste[j,i] then coste[j,i]=coste[j−1,i] mejor_camino[j,i]= mejor_camino[j−1,i]; end end salida mejor_camino[𝑛−1,𝑛] end Gráfico 7: Comparativa de los órdenes de magnitud para diferentes funciones. Fuente: https://www.campusmvp.es/ En cuanto al algoritmo del camino mínimo, el bucle principal se itera (𝑛−1)2 veces, y dentro de este se encuentra el de la búsqueda de mínimo que se itera un máximo de (𝑛−1) veces, por lo que el orden de complejidad del algoritmo se puede establecer como 𝑂(𝑛). Finalmente cabe destacar, que no para todos los algoritmos es fácil calcular su grado de complejidad. De hecho, para muchos, este depende considerablemente de los datos de entrada que reciba. De esta forma, se pueden establecer tres parámetros que caractericen la complejidad de este tipo de algoritmos: el caso mejor, el caso peor y el caso promedio. El caso mejor es aquella casuística del algoritmo en la que el número de operaciones es el menor de los posibles, el caso peor es aquel para el que el número de operaciones es máximo y el caso promedio corresponde a la media todos los posibles casos. Para este último se debe desarrollar una distribución de probabilidad para todas las casuísticas del problema y en algunos casos puede suponer una gran dificultad el propio modelado de la distribución. 59 3 ALGORITMOS ESCOGIDOS unque el TSP sea un problema difícil de resolver, con una complejidad NP-Hard y que a día de hoy siga sin haberse encontrado una manera de resolverlo en un tiempo polinomial, existen algoritmos que reducen la complejidad de este. Entre las características fundamentales del algoritmo se encuentran: • La eficacia para encontrar una solución óptima o cercana a la óptima. • La eficiencia para obtenerla, es decir, la complejidad. • La sencillez del algoritmo. Aunque este punto pueda parecer trivial, cuando se mejoran, estudian y desarrollan algoritmo, la sencillez es fundamental a la hora de analizarlo. Permite, adaptarlo, descubrir errores y optimizarlo Estos tres objetivos no suelen darse al mismo tiempo, por lo que siempre se deberá buscar un equilibrio en función de la naturaleza del problema que el algoritmo intente resolver. En este apartado se estudiará primero el conocido algoritmo de Branch and Bound, más adelante, un algoritmo de fuerza bruta conocido por Programación Dinámica y Finalmente, se tratará el algoritmo de Christofides, actualmente la heurística con tiempo polinomial que más se acerca al ´óptimo para el TSP. A “Los grandes algoritmos son la poesía de la computación.” - Francis Sullivan - 3.1 Algoritmo de Branch and Bound El origen del algoritmo de Branch and Bound o Ramificación y Poda para el TSP tiene su origen en Dantizing et al. [34]. El algoritmo rompe el conjunto de todas las posibles soluciones y las divide incrementalmente en pequeños subconjuntos. Para cada subconjunto se calcula un límite mínimo (bound) de las distancias o coste del mejor camino de las soluciones que abarque. Estos límites los va usando el algoritmo como guía para dividir las soluciones, a medida que se van dividiendo se encontrará un camino cuyo bound es menor que o igual que todos los bound del resto de soluciones. Este último camino será entonces, óptimo. Los subconjuntos de soluciones o caminos son representados como nodos de un árbol y el proceso de división de soluciones como la ramificación de un árbol. De ahí, el nombre de ramificación y poda. En general para cualquier algoritmo de Branch and Bound se sigue un esquema a través del cual se llega a una solución. Para un problema cualquiera 𝑃se define 𝑣(𝑃) como el valor de la solución óptima de 𝑃. Las características principales de un algoritmo de Ramificación y poda para un problema de optimización discreta 𝑃 de la forma min{𝑓(𝑥)|𝑥∈𝑆} son: 1. Una relajación de 𝑃. Por ejemplo, un problema 𝑅 de la forma min{𝑔(𝑥)|𝑥∈𝑇}, tal que 𝑆⊆𝑇 y para toda 𝑥,𝑦∈𝑆, 𝑓(𝑥)<𝑓(𝑦) implica que 𝑔(𝑥)<𝑔(𝑦). 2. Una norma o regla que seguir para el proceso de ramificación. Por ejemplo, una regla que consista en romper o dividir un conjunto de soluciones factibles 𝑆𝑖 del subproblema 𝑃𝑖 en subconjuntos más pequeños 𝑆𝑖1,…,𝑆𝑖𝑞, tal que ⋃𝑆𝑖𝑗 𝑞 𝑗=1 =𝑆𝑖. 3. El cálculo de una cota mínima o bound. Por ejemplo, un procedimiento para encontrar 𝑣(𝑅𝑖) para cada relajación 𝑅𝑖 de cada subproblema 𝑃𝑖. 4. Una procedimiento o regla para la selección de un subproblema. Por ejemplo, una regla para escoger el siguiente subproblema que deberá ser procesado y calculado. 3.1.1 Relajación y cálculo de la cota mínima o bound Un concepto útil para la construcción de cotas mínimas es el de reducción de matrices, que se puede utilizar como una relajación del problema, 𝑅. Si una constante, ℎ, es subtraída o restada a cada elemento de una fila de la matriz de costes 𝑐𝑖𝑗, el coste de cualquier camino según la nueva matriz 𝑐𝑖𝑗 ′ será al menos menor que ℎ con respecto a la matriz antigua. Esto es porque cada solución o camino debe contener al menos uno, y solo un elemento de dicha fila. De esta forma, aunque se hayan cambiado los costes relativos, una solución óptima en la nueva matriz también lo es en la antigua. Este proceso de restar a cada fila una constante ℎ, equivalente al elemento más pequeño de la fila, 61 se le conoce como reducción de la fila. Una matriz compuesta por elementos no negativos y con al menos un 0 encada matriz o cada columna es llamada matriz reducida, y pude ser obtenida, por ejemplo, reduciendo filas y columnas. Si 𝑐(𝜋)es el coste de un camino en una matriz de costes antes de ser reducida, 𝑐1(𝜋)el nuevo coste para la matriz reducida y ℎ la suma de constantes que reducen la matriz, entonces: 𝑐1(𝜋)=𝑐(𝜋)+ℎ Ya que la matriz reducidad no contiene elementos no negativos, ℎ se puede utilizar como una cota o límite mínimo para el coste de la solución 𝜋 de la matriz de coste original. Ejemplo Para un TSP con cinco ciudades se muestra el proceso de reducción de la matriz de costes y el resultado correspondiente: Matriz original 𝑐𝑖𝑗 con reducción de filas: 10 20 30 10 11 10 20 0 1 2 15 16 4 2 13 14 2 0 2' 3 5 2 4 1 3 0 2 3 19 6 18 3 16 3 15 0 4 16 4 7 6 14 0 3 2 ij ij cc →          →          = → → =      →          →      Se obtiene así que la cota obtenida por la reducción de filas, ℎ𝑓, es igual a 21. Matriz reducida por filas con reducción de columnas: 10 20 0 1 10 17 0 1 13 14 2 0 12 11 2 0 '' 1 3 0 2 0 3 0 2 16 3 15 0 15 3 12 0 14 0 3 2 13 0 0 2 1 0 3 0 0 ij ij cc                   = → =                         Se obtiene así que la cota obtenida por la reducción de columnas, ℎ𝑐, es igual a 4. Por lo tanto, la cota ℎ de la matriz reducida se obtiene: ℎ=ℎ𝑐+ℎ𝑓 Finalmente, se puede decir que al ser ℎ=25 no existirá ninguna solución menor que 25. Este cáculo de la matriz reducida se corresponde con la regla para el cálculo de un límite mínimo del apartado anterior (apartado 3.1), donde 𝑣(𝑅𝑖) corresponde al valor de ℎ y 𝑆𝑖 abarca todas las posibles soluciones del problema. 3.1.2 Proceso de ramificación La división de las soluciones en subconjuntos de éstas se representa como la ramificación de un árbol, como se muestra en la Figura 22. El primer nodo contiene todas las posibles soluciones y corresponde al punto de partida del viajante, sería el nivel 0; habrá tantos niveles como ciudades tenga el problema. Desde ahí se llega al nivel 1, que corresponde con la primera ciudad que visita el viajante. Sucesivamente se llegará hasta el nivel 𝑛, que corresponderá con la última ciudad por visitar. Un proceso de ramificación en profundización consiste en comprobar las cotas mínimas de cada subconjunto de soluciones profundizando en los niveles, es decir, primero se llega hasta el último nivel para un subconjunto de soluciones (hasta quedarse solo con una) y luego se explora el resto de los subconjuntos, desde el nivel 𝑛 hasta el primero. En la Figura 22 primero se ha visitado el subconjunto de ciudades 𝑆𝐵 en las que A y B son las primeras ciudades en ser visitadas, luego el 𝑆𝐵𝐶 (visitando primero A, B y luego C), a continuación, el 𝑆𝐵𝐶𝐷 y finalmente el 𝑆𝐵𝐶𝐷𝐸. Es decir, primero se ha llegado a la solución para la permutación 𝑆𝐵𝐶𝐷𝐸 y luego se ha ido explorando el resto de las soluciones. Figura 22: Ramificación en profundidad para un problema de 5 nodos. Fuente [42] Se puede ver que en este apartado se ha definido la segunda regla del apartado (apartado 3.1), la correspondiente a la ramificación de los subconjuntos de soluciones. Por ejemplo, 𝑆𝐵=𝑆𝐵𝐶+𝑆𝐵𝐷+ 𝑆𝐵𝐸. Es decir, la división de un subcojunto de soluciones en el problema de TSP, consiste en obligar y en restringir la siguiente ciudad en ser visitada, dejando el orden del resto de ciudades por ser visitadas libre. 63 3.1.3 Cálculo de la cota mínima para ramas de niveles superiores En el apartado 3.1.1 se ha visto como reducir la matriz completa 𝑐𝑖𝑗 sin haber visitado todavía ninguna ciudad, pero cuando se visita una ciudad, se debe calcular una nueva cota mínima. Es decir, visitar una ciudad implica un nuevo subproblema y por lo tanto una nueva cota. Se continúa el ejemplo anterior para mostrar este cálculo. Ejemplo Partiendo de la matriz 𝑐𝑖𝑗 ′ se decide visitar primero el nodo 1 y luego el nodo 4. Para ello la matriz deberá ser modificada y a la nueva matriz le corresponderá un nuevo valor de reducción. Cuando se visita un nodo 𝑗 desde un nodo 𝑖 se establecen todos los elementos de la fila 𝑖 y la columna 𝑗 como infinito. De esta manera la nueva matriz quedaría: (1) (2) 10 17 0 1 12 11 2 0 12 11 0 '' 0 3 0 2 0 3 2 15 3 12 0 15 3 12 0 13 0 0 2 13 0 0 ij ij cc  →                          →= =                        De esta manera la nueva matriz 𝑐𝑖𝑗 (2)′puede volver a ser reducid, ya que si se sutituye un 0 por infinito el nuevo mínimo de la columna o fila varía. En este caso, no existe ningún nuevo mínimo, por lo que ℎ(2)=0. Por lo tanto, el cálculo de la nueva cota sería igual a la constante de la matriz reducida anterior, más el de la nueva, más la nueva distancia recorrida. Es decir: 𝑈14=ℎ(1)+𝑐14 (1)′+ℎ(2)=25+0+0=25 El procedimiento sería el mismo si del nodo 4 se quisiera ir al 2: (2) (3) 12 11 0 12 11 0 '' 0 3 2 0 2 15 3 12 0 13 0 0 13 0 ij ij cc                                →= =          →                        Donde, de nuevo no se puede reducir más la matriz y ℎ(3)=0. En este caso, se calcula la cota inferior del siguiente nivel, partiendo de la cota del nivel anterior: 𝑈142=𝑈14+ℎ(3)+𝑐42 (2)′=25+0+3=28 Esta cota se interpreta como: si se quiere visitar primera la ciudad 1, luego la ciudad 4, luego la ciudad 2 y finalmente la 3 y la 5, estas dos últimas sin orden definido, al menos costará 28. De esta forma se calcula cualquier cota para cualquier subproblema 𝑇𝑆𝑃𝑖𝑞. 3.1.4 Regla de selección de subproblemas Como se ya se ha comentado, el algoritmo divide el problema en subproblemas. En el 𝑇𝑆𝑃𝑖𝑞 un subproblema 𝑖𝑞 consiste en establecer el nodo 𝑖 como el inicial y en otro subconjunto 𝑆𝑖𝑞 de nodos visitados, de manera que el orden de visita del subconjunto del resto de nodos sin visitar, 𝐴\𝑆𝑖𝑞, quede por determinar. Así, para cada subconjunto de nodos 𝑆𝑖𝑞 existe un subproblema 𝑇𝑆𝑃𝑖𝑞. El primer paso, como se ha comentado en el apartado anterior, es calcular el valor del primer subconjunto en el nivel 𝑛 (en la Figura 22, el primer subconjunto de nivel 𝑛 es el {𝐴,𝐵,𝐶,𝐷,𝐸}) y dicho valor se establece como la cota mínima hasta el momento. Para el siguiente paso se deberá escoger otro subconjunto de soluciones o subproblema que deberá ser evaluado y comparado con la cota mínima. Para ello primero se bajará al nivel (𝑛−1) y se evaluará por orden alfabético o de menor a mayor los nodos que queden por visitar en dicho nivel. Si en ese nivel ya se han visitado todos los nodos, se bajará al nivel (𝑛−2) y así sucesivamente hasta haber evaluado todos los niveles. Nótese que para el nivel 𝑛 y (𝑛−1) solo existe una permutación de ciudades. Sin embargo, para el nivel (𝑛−2), existirán dos, una por cada ciudad sin visitar. Por ejemplo, en la Figura 22, en el nivel (𝑛−2) para el subconjunto {𝐴,𝐵,𝐶} existen dos ciudades por ser visitadas: 𝐷 y 𝐸, y por lo tanto dos permutaciones: {𝐴,𝐵,𝐶,𝐷,𝐸} y {𝐴,𝐵,𝐶,𝐸,𝐷}. 3.1.5 Algoritmo Finalmente, teniendo en cuenta la relajación del problema mediante matrices reducidas, la obtención de la cota mínima mediante la constante sobrante de reducir la matriz y la regla de ramificación en profundización, se puede establecer un algoritmo de Branch and Bound. Este se muestra en la Figura 23. 65 Figura 23: Pseudo algoritmo de Branch and Bound. 1. Inicializar Se añade el TSP completo a la lista de subproblemas y se define la cota mínima 𝑈=∞ 2. Selección del subproblema a. Si la lista de subproblemas está vacía → Fin, el camino asociado con 𝑈 es óptimo (si 𝑈=∞, no existe solución). b. Si la lista está llena, se escoge un subproblema 𝑇𝑆𝑃𝑖 y se elimina este de la lista. 3. Cota mínima Se resuelve la relajación (matriz reducida) 𝑅𝑖 del problema 𝑇𝑆𝑃𝑖, es decir, se calcula su cota mínima 𝑣(𝑅𝑖), siendo 𝐿𝑖 el valor obtenido. a. Si 𝐿𝑖≥𝑈, se vuelve al paso 2. b. Si 𝐿𝑖<𝑈 y la solución es equivalente a un nuevo camino o ruta se establece 𝑈←𝐿𝑖. Si la solución no equivale a un camino completo se sube de nivel y se pasa al paso 4. 4. Reducción Se eliminan todos los arcos que deriven de 𝑇𝑆𝑃𝑖 cuya inclusión sobrepase la cota mínima. 5. Ramificación Se ramifica el problema 𝑇𝑆𝑃𝑖 y se generan el resto de los subproblemas que derivan de este 𝑇𝑆𝑃𝑖1,…, 𝑇𝑆𝑃𝑖𝑞, estos se incluyen en la lista. Se vuelve al paso 2. 3.2 Algoritmo de Programación Dinámica Este algoritmo es de tipo fuerza bruta pero más eficiente que el algoritmo explicado en el apartado 2.4.1. Desarrollado por Held y Karp [43] este encuentra para cada ciudad 𝑖 el camino más corto desde la ciudad 1 hasta la ciudad 𝑖 visitando todos los nodos del subconjunto 𝑁={2,…,𝑛}. Una vez se hayan encontrado estos caminos, por comparación se encuentra fácilmente el camino óptimo, tal como se muestra en la Figura 24. Figura 24: Pseudo código del algoritmo de Held y Karp para el TSP. Fuente [28]. Para calcular el camino mínimo de 1 hasta 𝑖, el algoritmo resuelve el problema construyendo paso a paso la solución final. Para 𝑆⊆{2,3,…,𝑛} y 𝑖∈𝑆, se define (𝑆,𝑖) como un camino que finaliza en el nodo 𝑖 y que visita una única vez todos los nodos contenidos en 𝑆 y ningún otro más. También, * Entrada: Número entero 𝑛≥3, matriz 𝑛×𝑛 𝐶=(𝑐𝑖𝑗), donde cada 𝑐𝑖𝑗 es un número real mayor o igual que 0. * Salida: El camino más corto que uno todos los nodos 𝑁, que empieza en 1 y acaba en n. comienzo for 𝑖=2,3,…,𝑛 do coste[{i},i] = 𝑐1𝑖; mejor_camino[{i},i] = (1,i); end for 𝑖=2,3,…,𝑛−1 do for each 𝑆⊆{2,3,…,n} con |𝑆|=𝑗 for each 𝑖∈𝑆 do coste[S,i] = min k∈S−{1}{coste[S−{i},𝑘]+𝑐𝑘𝑖}; se estable k como la ciudad para la que el coste es mínimo; mejor_camino[S,i] = (mejor_camino[S-{i},k], i) end end coste_minimo = min k≠1{coste[S−{I},𝑘]+𝑐𝑘𝑖}; se estable k como la ciudad para la que el coste es mínimo; mejor_ruta = mejor_camino[{2,3,…,n},𝑘] en output mejor_ruta finaliza algoritmo 67 se define coste[S,i] como la distancia recorrida por la ruta mínima de (𝑆,𝑖). Por lo tanto, coste[S,i] satisface la siguiente ecuación cuando |𝑆|≥2: coste[𝑆,𝑖]= min 𝑘∈𝑆−{1}{coste[𝑆−{𝑖},𝑘]+𝑐𝑘𝑖} (57) En el lado derecho de la ecuación (57) se calcula el mínimo de todos los caminos de (𝑆−{𝑖},𝑘) sumado a la distancia entre 𝑘 e 𝑖, donde 𝑆−{𝑖} es el subconjunto 𝑆 excluyendo la ciudad 𝑖 y 𝑘 es una ciudad perteneciente a 𝑆−{𝑖}. En el primer bucle del algoritmo se obtienen los costes para la permutación 𝑆=(1,𝑖), siendo |𝑆|= 2. En el siguiente bucle, mediante la ecuación (57) se construye paso a paso la permutación óptima con el camino mínimo de (𝑆,𝑖) hasta que 𝑖 sea igual a 𝑛, momento en el cual se sale del bucle. Para este momento ya se habrán calculado las rutas mínimas de (𝑆,𝑖) siendo |𝑆|=𝑛. Finalmente, una vez se tienen las rutas mínimas se comparan todas ellas sumando al coste[𝑆,𝑖] la distancia entre 𝑖 y 1, 𝑐𝑘𝑖, obteniéndose de esta forma el camino mínimo {(𝑆,𝑘),1}, siendo 𝑘 la última ciudad en ser visitada. Este tipo de técnica algorítmica en la que se va solucionando cada vez problemas más grandes para llegar a una solución mayor es conocida como programación dinámica. 3.2.1 Complejidad Para el algoritmo de programación dinámica el rendimiento es menor, la mayor complejidad del algoritmo reside en la obtención del subconjunto 𝑆⊆{2,3,…,𝑛}, que puede ser cualquiera dentro del conjunto {2,3,…,𝑛} siempre y cuando |𝑆|=𝑗. Esta operación se encuentra dentro de un bucle que se repite 𝑛−1 veces. Por otra parte, la búsqueda del subconjunto 𝑆 contiene otros bucles que se encargan de buscar el mínimo para cada elemento de 𝑆 y que se repite 𝑗 veces, hasta un máximo de 𝑛−1 veces por lo que el número de operaciones quedaría de la siguiente manera: ∑(𝑛−1 𝑗) 𝑛−1 𝑗=2 𝑗2≤2𝑛−1(𝑛−1)2 (58) El lado derecho de la inecuación (58) es el límite máximo que podría tener el algoritmo para 𝑗= 𝑛−1, El sumatorio del coeficiente binomial se puede calcular a partir de la ecuación de Newton: (𝑥+𝑦)𝑛=∑(𝑛 𝑘) 𝑛 𝑘=0 𝑥𝑛−𝑘𝑦𝑘 (59) 4.1 Nodos En este problema los nodos representan los pueblos de la zona oeste de Sevilla, se han cogido todos aquellos a 20 km a la redonda del centro geográfico de la ciudad: en total 22 pueblos. Como punto de partida se ha tomado el centro logístico de Amazon en el parque empresarial Megapark de Dos Hermanas, entre la SE-3205, la SE-3206 y la A-4, con futura salida directa a la SE-40. Viene marcado en la Figura 28 con una equis en rojo. Figura 28: Mapa de la zona oeste de Sevilla. Contando con el depósito, el número de nodos del problema, 𝑛, es de 23. Los pueblos incluidos son: Amazon SVQ, Gelves, San Juan de Aznalfarache, Camas, Santiponce, Tomares, Sanlúcar la Mayor, Castilleja de la Cuesta, Palomares del Río, Castilleja de Guzmán, Mairena del Aljarafe, Bormujos, Valencina de la Concepción, Gines, Salteras, Almensilla, Espartinas, Bollullos de la Mitación, Benacazón, Villanueva del Ariscal, Olivares y Umbrete. 75 4.2 Arcos Los arcos del problema son las conexiones entre los pueblos. Estas conexiones pueden ser directas o indirectas, es decir, que se puede pasar a través de un pueblo para llegar a otro sin que el algoritmo dé por visitado el pueblo intermedio. Esta técnica se emplea para los grafos incompletos y está explicada en el apartado 2.2.2. En este apartado se explicaba que en aquellos grafos en los que existan nodos no conectados con otros, se puede relajar el problema, calculando el camino mínimo entre un nodo y otro (problema resuelto por el algoritmo de Floyd-Warshall [29]). De esta forma el problema, se ha modelado como un grafo conexo, donde todos los nodos están conectados entre sí. Claramente, las conexiones están representadas por carreteras, autopistas o autovías. 4.3 Matriz de costes Para el presente Proyecto, se ha querido dar un enfoque distinto a la unidad de medida empleada en el problema. Normalmente, se tienen en cuenta tres unidades básicas: tiempo, distancia y dinero. En el caso de las carreteras, se puede introducir una variable más que represente el estado de la carretera o el tipo de esta. Esto quiere decir que no es lo mismo ir por una autopista que por una carretera nacional. Normalmente, las vías grandes suelen estar más descongestionadas y en mejor estado, lo que implica un ahorro de tiempo, coste e incluso distancia por la velocidad de circulación. En ese sentido, se ha querido reforzar el peso de este tipo de carreteras en el Proyecto, de manera que el empleo de éstas tenga un impacto menor en la función de costes que el empleo de las carreteras nacionales o comarcales. Por lo tanto, la variable escogida, es una modificación de la longitud real a través de carreteras entre dos pueblos de manera que, se define: • 𝑤𝑖𝑗 como la distancia recorrida a través de carretera comarcal o nacional entre el pueblo 𝑖 y el pueblo 𝑗. • 𝑣𝑖𝑗 como la distancia recorrida a través de autopista o autovía entre el pueblo 𝑖 y el pueblo 𝑗. • 𝑑𝑖𝑗 como la longitud real a través de carreteras o autopistas entre el pueblo 𝑖 y el pueblo 𝑗. • 𝑐𝑖𝑗 como la distancia virtual empleada en el problema del Proyecto entre el pueblo 𝑖 y el pueblo 𝑗. De esta forma la relación entre las distancias es la siguiente: 𝑑𝑖𝑗=𝑤𝑖𝑗+𝑣𝑖𝑗 𝑖,𝑗=1,…,𝑛 (61) 𝑐𝑖𝑗=2𝑤𝑖𝑗+𝑣𝑖𝑗 𝑖,𝑗=1,…,𝑛 (62) Es decir, como se puede ver en la ecuación (62), se ha utilizado le ha dado el doble de penalización al empleo de carreteras comarcales o nacionales. La matriz de costes se adjunta en el Anexo I. 77 5 RESULTADO Y CONCLUSIONES unque, un algoritmo dé un resultado óptimo, o ni siquiera dé una solución para le problema en cuestión, siempre provee datos que sirven para entender mejor el problema que se esté intentando resolver. De los algoritmos presentado en este Proyectos, dos son heurísticos y uno es de fuerza bruta, cada uno tiene sus ventajas y sus inconvenientes, pero todas aportan algo al entendimiento del problema. La complejidad de la formulación de una heurística puede ralentizar el ordenador, aunque la sencillez de un algoritmo de fuerza bruta también. Del mismo modo, la sutileza de otro algoritmo puede proveer resultados en muy poco tiempo, pero pueden darse malas (o no cercanas al óptimo) soluciones. Este es uno de los grandes equilibrios que se buscan en los desarrollos algoritmos, entre la simpleza y la complejidad, la precisión en detrimento de la velocidad, o la rapidez a costa de la bondad de la solución. Con los tres algoritmos presentados, este equilibrio o estas diferencias entre unos y otros se puede observar perfectamente. En este apartado se analizarán las soluciones obtenidas por el algoritmo en dos grafos diferentes: uno con 23 nodos y otro con 11. Se hará una breve comparación de los mismos, enumerando las ventajas e inconveniente de cada uno. Se verán principalmente tres datos de entrada: La secuencia, la distancia virtual recorrida y el tiempo real empleado, que servirá a modo de comparativa. A “Mide lo que es medible, y haz medible lo que no lo es” - Galileo Galilei - 5.1 Resultados del algoritmo de Branch and Bound Este algoritmo se caracteriza por su equilibrado balance entre la bondad de la solución y el tiempo empleado en alcanzarla. 5.1.1 Caso de 23 nodos Para el caso de los 22 pueblos y el centro logístico de Amazon en Dos Hermanas el algoritmo llega a la siguiente solución: ['Amazon SVQ1', 'Gelves ', 'San Juan de Aznalfarache ', 'Mairena del Aljarafe ', 'Palomares del Río ', 'Almensilla ', 'Bollullos de la Mitación ', 'Umbrete ', 'Benacazón ', 'Sanlúcar la Mayor ', 'Olivares ', 'Villanueva del Ariscal ', 'Espartinas ', 'Salteras ', 'Gines ', 'Bormujos ', 'Castilleja de la Cuesta ', 'Castilleja de Guzmán ', 'Valencina de la Concepción ', 'Santiponce ', 'Camas ', 'Tomares ', 'Amazon SVQ1'] Esta secuencia provee un coste de 212’7 km virtuales, con un tiempo de ejecución de 938.8700778 segundos. Figura 29: Resolución del problema de los 23 nodos con el algoritmo de Branch and Bound. 79 5.1.2 Caso de 12 nodos Con el objetivo de comparar también los algoritmos para problemas más pequeños, se estudia su comportamiento para el caso de doce nodos. Este es un subproblema del problema anterior para el que solo se tienen en cuenta las once primeras ciudades: Gelves, San Juan de Aznalfarache, Camas, Santiponce, Tomares, Sanlúcar la Mayor, Castilleja de la Cuesta, Palomares del Río, Castilleja de Guzmán, Mairena del Aljarafe y Bormujos. Además del centro logístico de Amazon: Amazon SVQ. El comportamiento del algoritmo en este punto es proporcional al anterior, sobre todo, en cuanto a tiempo se refiere. Este ha sido de 102.1581888 segundos y a alcanzado el óptimo con una distancia virtual de 166.7 km. La secuencia obtenida es ['Amazon SVQ1', 'San Juan de Aznalfarache ', 'Mairena del Aljarafe ', 'Palomares del Río ', 'Gelves ', 'Santiponce ', 'Camas ', 'Castilleja de Guzmán ', 'Castilleja de la Cuesta ', 'Bormujos ', 'Sanlúcar la Mayor ', 'Tomares ', 'Amazon SVQ1'] 5.1.3 Caso de 16 nodos Para cuando el número de pueblos es 15, el problema muestra una singularidad, existen casos en los que la obtención del óptimo no llega hasta que se han explorado todos o casi todos los subproblemas 𝑇𝑆𝑃𝑖𝑞. Esto provoca que la complejidad del algoritmo en su peor caso se mayor, aumentando así el tiempo de ejecución. Este ha sido el caso en el que el número de nodos es 16, para el que el algoritmo ha hallado una solución con un recorrido virtual de 196’45km. En un tiempo de 2785’682 segundos, lo que muestra la gran singularidad del presente caso. Por último, la ruta encontrada es la siguiente, que es la óptima: ['Amazon SVQ1', 'Gelves ', 'San Juan de Aznalfarache ', 'Mairena del Aljarafe ', 'Palomares del Río ', 'Almensilla ', 'Sanlúcar la Mayor ', 'Salteras ', 'Gines ', 'Bormujos ', 'Castilleja de la Cuesta ', 'Castilleja de Guzmán ', 'Valencina de la Concepción ', 'Santiponce ', 'Camas ', 'Tomares ', 'Amazon SVQ1'] 5.2 Resultados del algoritmo de Programación Dinámica Este algoritmo, como ya se adelantó en el Capítulo 3, apartado 3.2.1, su complejidad es bastante alta, es decir, no es de tipo polinomial, lo que implica que en ocasiones se requiera de tiempos desmesurados para llegar a la solución exacta. 5.2.1 Caso de 23 nodos En este caso se ha podido comprobar la imposibilidad del algoritmo para llegar a una solución en un tiempo razonable (mayor de un día). En línea con lo dicho anteriormente, la complejidad de este algoritmo aumenta exponencialmente a medida que lo hace el número de nodos del problema que intenta resolver. Esto hace que la capacidad computacional del ordenador donde se esté ejecutando deba ser lo suficientemente grande como para que se pueda obtener una solución exacta en un tiempo razonable. No por ello este algoritmo deja de perder valor, pues a mostrado buenas soluciones para problemas de menor envergadura. 5.2.2 Caso de 12 nodos Para un caso menor, al contario que, en el caso de 23 nodos, el resultado es mejor que en el algoritmo anterior, el de Branch and Bound. La solución es la misma, el óptimo, pero en un tiempo cien veces menor: 1.1030643999 segundos. La secuencia obtenida es: ['Amazon SVQ1', 'San Juan de Aznalfarache ', 'Mairena del Aljarafe ', 'Palomares del Río ', 'Gelves ', 'Santiponce ', 'Camas ', 'Castilleja de Guzmán ', 'Castilleja de la Cuesta ', 'Bormujos ', 'Sanlúcar la Mayor ', 'Tomares ', 'Amazon SVQ1'] 5.2.3 Caso de 16 nodos Para este caso la solución obtenida es la óptima en un tiempo breve. Concretamente, la solución es la misma que para el algoritmo de Branch and Bound, la óptima. La longitud del camino es de 196,45 km y el tiempo empleado es de 26’186 segundos, es decir, cien veces más rápido que el de Branch and Bound. 81 5.3 Resultados del algoritmo de Christofides Este algoritmo destaca por ser el más rápido de los tres, a continuación, se verán los resultados que lo confirman. 5.3.1 Caso de 23 nodos Para el mayor caso de los dos, el algoritmo de Christofides da la siguiente secuencia: ['Amazon SVQ1', 'Tomares ', 'Camas ', 'Bormujos ', 'Castilleja de la Cuesta ', 'Gines ', 'Espartinas ', 'Salteras ', 'Villanueva del Ariscal ', 'Olivares ', 'Umbrete ', 'Benacazón ', 'Sanlúcar la Mayor ', 'Bollullos de la Mitación ', 'Almensilla ', 'Palomares del Río ', 'Mairena del Aljarafe ', 'San Juan de Aznalfarache ', 'Castilleja de Guzmán ', 'Valencina de la Concepción ', 'Santiponce ', 'Gelves ', 'Amazon SVQ1'] El tiempo que ha tardado en obtener dicho resultado es de 0.0501314 segundos, y la distancia virtual recorrida en km es de 262’7, mayor que el algoritmo de Branch and Bound. Por último, se muestra en la Figura 30. A simple vista se puede ver que la solución es menos bondadosa que en el algoritmo de Branch and Bound, llegando a pasar por un pueblo no visitado sin llegar a visitarlo. No obstante, en otros puntos del mapa, especialmente más hacia el Sur, sí muestra un comportamiento más bondadoso. Figura 30: Resolución del problema de los 23 nodos con el algoritmo de Christofides. 5.3.2 Caso de 12 nodos En este caso la solución de Christofides también vuelve a ser rápida, tarda un tiempo de 0’0495193 segundos con un coste mínimo de 182’2 km. La secuencia obtenida es la siguiente: ['Amazon SVQ1', 'Tomares ', 'Castilleja de la Cuesta ', 'Bormujos ', 'Sanlúcar la Mayor ', 'Castilleja de Guzmán ', 'Santiponce ', 'Camas ', 'San Juan de Aznalfarache ', 'Mairena del Aljarafe ', 'Palomares del Río ', 'Gelves ', 'Amazon SVQ1']. Nótese que, efectivamente, el algoritmo de Christofides cumple con la relación de la solución hallada con la solución óptima. Concretamente, para este caso, la secuencia mostrada por el algoritmo es de 1’093 veces superior a la óptima, habiéndola hallado en un tiempo 1’047 veces mayor que para el de Programación dinámica y 2’59 veces mayor que el de Branch and Bound. 5.3.3 Caso de 16 nodos Por último, se muestra el caso de los 15 pueblos más el centro logístico de Amazon. La solución obtenida es una secuencia cuyo recorrido es de 214’85 km virtuales en un tiempo de 0’1044 segundos. Es decir, se obtiene una solución 1’235 veces peor que la óptima en un tiempo de ejecución 250’92 veces menor que para el de Programación Dinámica. Por otra parte, la solución obtenida sigue esta secuencia: ['Amazon SVQ1', 'Gelves ', 'San Juan de Aznalfarache ', 'Camas ', 'Santiponce ', 'Tomares ', 'Sanlúcar la Mayor ', 'Castilleja de la Cuesta ', 'Palomares del Río ', 'Castilleja de Guzmán ', 'Mairena del Aljarafe ', 'Bormujos ', 'Valencina de la Concepción ', 'Gines ', 'Salteras ', 'Almensilla ', 'Espartinas ', 'Bollullos de la Mitación ', 'Benacazón ', 'Villanueva del Ariscal ', 'Olivares ', 'Umbrete '] Se muestra claramente la rapidez de este algoritmo a pesar de no llegar al óptimo, lo que supone una elección segura frente a problemas de grandes dimensiones. 83 5.4 Comparativa Como se menciona al comienzo del capítulo los tres algoritmos pueden dar una buena imagen del equilibrio entre eficiencia y eficacia, variando según la cantidad de datos procesados. Por ejemplo, para el algoritmo de Programación Dinámica es muy complicado llegar a una solución exacta para grandes entradas del problema en tiempos de amplitud pequeña, ya que el orden de complejidad es exponencial. Sin embargo, tal como se puede apreciar en la Tabla 3 da muy buenos resultados para instancias del problema pequeñas, es decir, es un algoritmo muy bueno para caso en los que el problema contenga muy pocos vértices. En cuanto al algoritmo de Branch and Bound, es un algoritmo que busca el óptimo para instancias del problema mayores, aunque a un precio temporal elevado. Es decir, para una solución óptima es necesario emplear un tiempo considerablemente alto en la resolución del algoritmo. También se puede ver el caso en el que el algoritmo resuelve una mala instancia de datos (Tabla 3) y en el que el tiempo de ejecución se dispara, como es el caso del subproblema de 16 nodos. Un punto fuerte de este algoritmo es la versatilidad que tiene, se le pueden añadir diferentes tipos de cálculo de límites, estrategias de elección de subproblemas y diferentes formas de ramificación para mejorarlo. Tabla 3: Resultados para diferentes instancias del problema. Si se pretende hallar soluciones en un corto período de tiempo, el mejor algoritmo es el de Christofides, para todas las estancias del problema ha dado soluciones menores que tres media partes de la solución óptima. Para el de 12 nodos la solución ha sido de 1,09 veces la solución óptima, mientras que, para la instancia completa del problema, la solución dada por Christofides era de 1,235 veces el óptimo (Tabla 4). Esto muestra un gran equilibrio entre eficacia y eficiencia, que se mantienen constante y polinomial a lo largo del dominio de los posibles problemas. Tabla 4: Relación del Problema de Christofides con la solución óptima del problema Distancia (km) Tiempo (s) Distancia (km) Tiempo (s) Distancia (km) Tiempo (s) Distancia (km) Tiempo (s) Branch and Bound 78,6 0,1009 166,700 102,1582 196,45 2785,6820 212,7 938,870 Programación Dinámica 78,6 0,0408 166,700 1,1031 196,45 26,1865 - - Christofedes 81,0 0,0390 182,200 0,0495 214,85 0,1044 262,7 0,050 6 nodos 12 nodos 16 nodos 23 nodos 6 nodos 12 nodos 23 nodos 16 nodos Christofides/Óptima 1,030534351 1,092981404 1,09366251 1,235072873 [42] C.-Y. (. Huang, C.-Y. Lai y K.-T. (. Cheng, «Chapter 4 - Fundamentals of algorithms,» de Electronic Design Automation, L. Wang, Y. Chang y K. (. Cheng, Edits., Boston, Morgan Kaufmann, 2009, pp. 173 - 234. [43] M. Held y R. M. Karp, «A Dynamic Programming Approach to Sequencing Problems,» vol. 10, Society for Industrial and Applied Mathematics, 1962, pp. 199-200. [44] N. Christofides, «Worst-case analysis of a new heuristic for the travelling salesman problem,» Technical Report, Pittsburgh, Pennsylvania, 1976. [45] S. Jaeger, «Recovering Dynamic Information from Static, Handwritten Word Images,» 12 1998. [46] F. J. Veiga Losada, «Trabajo de Fin de Máster: El problema del viajante.,» Santiago de Compostela, 2013. [47] G. D. Valle, «Amazon 2-day shipping: why packages sometimes arrive later,» Vox.com, 24 Abril 2019. [En línea]. Available: https://www.vox.com/thegoods/2019/4/23/18508093/amazon-prime-two-day-shipping. [48] F. Howard, «La cadena logística de Amazon.com,» Driv.in, 20 Septiembre 2017. [En línea]. Available: https://blog.driv.in/es/la-cadena-logistica-de-amazon-com/. [49] R. E. Burkard, «Travelling Salesman and Assignment Problems: A Survey,» de Discrete Optimization I, Annals of Discrete Mathematics, vol. 4, P. L. Hammer, E. L. Johnson y B. H. Korte, Edits., Elsevier, 1979, pp. 193-215. [50] A. H. Land y A. G. Doig, «An Automatic Method of Solving Discrete Programming Problems,» Econometrica, vol. 28, nº 3, pp. 497-520, 1960. 91 ANEXO I: MATRIZ DE COSTES CodMun 41038 41044 41086 41021 41089 CodMun Municipio Amazon SVQ1 Gelves San Juan de Aznalfarache Camas Santiponce 41038 Amazon SVQ1 024 20 23,8 25,7 41044 Gelves 24 0 8,4 13 13,8 41086 San Juan de Aznalfarache 20 8,4 0 13,2 15 41021 Camas 23,8 13 13,2 0 10,8 41089 Santiponce 25,7 13,8 15 10,8 0 41093 Tomares 20 11 6,8 5,6 12,5 41087 Sanlúcar la Mayor 41,7 35,1 29,8 26,1 31,9 41029 Castilleja de la Cuesta 22,9 11,5 12,4 7,2 13 41070 Palomares del Río 35 17,4 13,2 31,9 29,2 41028 Castilleja de Guzmán 29 14,8 18,4 7,6 13,4 41059 Mairena del Aljarafe 24,4 11,2 4 10 18,4 41017 Bormujos 25,7 13,2 10 9,6 15,3 41096 Valencina de la Concepción 33,4 26,6 22,8 11,8 10,4 41047 Gines 27,4 15,3 16,1 11,8 16,2 41085 Salteras 39,2 32,4 39,2 17,8 19 41010 Almensilla 43,2 26,8 20,8 28,9 33,4 41040 Espartinas 34,8 28 23,5 19,8 25,6 41016 Bollullos de la Mitación 35,4 16,8 23,3 19,8 25,4 41015 Benacazón 38,1 31,6 20,4 22,5 28,3 41098 Villanueva del Ariscal 39,3 32,6 43,5 24,6 29,9 41067 Olivares 52,3 45,7 40,2 27,6 28,8 41094 Umbrete 32,7 26,2 20,8 17,1 22,9 93 CodMun 41093 41087 41029 41070 41028 CodMun Municipio Tomares Sanlúcar la Mayor Castilleja de la Cuesta Palomares del Río Castilleja de Guzmán 41038 Amazon SVQ1 20 41,7 22,9 35 29 41044 Gelves 11 35,1 11,5 17,4 14,8 41086 San Juan de Aznalfarache 6,8 29,8 12,4 13,2 18,4 41021 Camas 5,6 26,1 7,2 31,9 7,6 41089 Santiponce 12,5 31,9 13 29,2 13,4 41093 Tomares 0 25,3 6,4 21 12,2 41087 Sanlúcar la Mayor 25,3 0 25,1 37,55 31,3 41029 Castilleja de la Cuesta 6,4 25,1 0 12,8 6,1 41070 Palomares del Río 21 37,55 12,8 0 28 41028 Castilleja de Guzmán 12,2 31,3 6,1 28 0 41059 Mairena del Aljarafe 9,8 32,5 12,2 11,6 21,3 41017 Bormujos 9,4 25,7 4,4 17,8 10 41096 Valencina de la Concepción 16,7 29,2 12 29,4 4,8 41047 Gines 10,7 25,4 4,9 23,2 9,2 41085 Salteras 22,4 22 18 35,2 12 41010 Almensilla 26,4 33,55 24,9 9,6 28,6 41040 Espartinas 10,7 13 14,8 34,4 19,4 41016 Bollullos de la Mitación 18,7 20,4 15,1 22,6 20,8 41015 Benacazón 21,4 10 17,8 33 23,5 41098 Villanueva del Ariscal 23,5 16,4 19,4 37,2 24 41067 Olivares 33,2 13 27,8 48,7 21,8 41094 Umbrete 16 13,6 12,4 27,8 17,8 CodMun 41059 41017 41096 41047 41085 CodMun Municipio Mairena del Aljarafe Bormujos Valencina de la Concepción Gines Salteras 41038 Amazon SVQ1 24,4 25,7 33,4 27,4 39,2 41044 Gelves 11,2 13,2 26,6 15,3 32,4 41086 San Juan de Aznalfarache 410 22,8 16,1 39,2 41021 Camas 10 9,6 11,8 11,8 17,8 41089 Santiponce 18,4 15,3 10,4 16,2 19 41093 Tomares 9,8 9,4 16,7 10,7 22,4 41087 Sanlúcar la Mayor 32,5 25,7 29,2 25,4 22 41029 Castilleja de la Cuesta 12,2 4,4 12 4,9 18 41070 Palomares del Río 11,6 17,8 29,4 23,2 35,2 41028 Castilleja de Guzmán 21,3 10 4,8 9,2 12 41059 Mairena del Aljarafe 0 9,4 20,8 14,6 26,6 41017 Bormujos 9,4 0 13,8 7,6 19,6 41096 Valencina de la Concepción 20,8 13,8 0 8,6 21,8 41047 Gines 14,6 7,6 8,6 0 13,6 41085 Salteras 26,6 19,6 21,8 13,6 0 41010 Almensilla 17,8 21 33,2 24 36,2 41040 Espartinas 22 15 20,2 10,4 7,8 41016 Bollullos de la Mitación 23,4 16 24,2 14,6 27,2 41015 Benacazón 25,8 18,8 26,8 17,4 29,2 41098 Villanueva del Ariscal 26,6 19,6 22,6 15,2 22,6 41067 Olivares 36,6 28,6 17,6 23,4 17,6 41094 Umbrete 20,8 11 21,8 12 27 CodMun 41010 41040 41016 41015 41098 CodMun Municipio Almensilla Espartinas Bollullos de la Mitación Benacazón Villanueva del Ariscal 41038 Amazon SVQ1 43,2 34,8 35,4 38,1 39,3 41044 Gelves 26,8 28 16,8 31,6 32,6 41086 San Juan de Aznalfarache 20,8 23,5 23,3 20,4 43,5 41021 Camas 28,9 19,8 19,8 22,5 24,6 41089 Santiponce 33,4 25,6 25,4 28,3 29,9 41093 Tomares 26,4 10,7 18,7 21,4 23,5 41087 Sanlúcar la Mayor 33,55 13 20,4 10 16,4 41029 Castilleja de la Cuesta 24,9 14,8 15,1 17,8 19,4 41070 Palomares del Río 9,6 34,4 22,6 33 37,2 41028 Castilleja de Guzmán 28,6 19,4 20,8 23,5 24 41059 Mairena del Aljarafe 17,8 22 23,4 25,8 26,6 41017 Bormujos 21 15 16 18,8 19,6 41096 Valencina de la Concepción 33,2 20,2 24,2 26,8 22,6 41047 Gines 24 10,4 14,6 17,4 15,2 41085 Salteras 36,2 7,8 27,2 29,2 22,6 41010 Almensilla 0 24,6 10,2 22,6 27,4 41040 Espartinas 24,6 0 15,6 17,4 5,2 41016 Bollullos de la Mitación 10,2 15,6 0 13 18 41015 Benacazón 22,6 17,4 13 022 41098 Villanueva del Ariscal 27,4 5,2 18 22 0 41067 Olivares 37,9 14,2 28,5 20,6 5,6 41094 Umbrete 17,8 14 8,4 11,6 10,4 CodMun 41067 41094 CodMun Municipio Olivares Umbrete 41038 Amazon SVQ1 52,3 32,7 41044 Gelves 45,7 26,2 41086 San Juan de Aznalfarache 40,2 20,8 41021 Camas 27,6 17,1 41089 Santiponce 28,8 22,9 41093 Tomares 33,2 16 41087 Sanlúcar la Mayor 13 13,6 41029 Castilleja de la Cuesta 27,8 12,4 41070 Palomares del Río 48,7 27,8 41028 Castilleja de Guzmán 21,8 17,8 41059 Mairena del Aljarafe 36,6 20,8 41017 Bormujos 28,6 11 41096 Valencina de la Concepción 17,6 21,8 41047 Gines 23,4 12 41085 Salteras 17,6 27 41010 Almensilla 37,9 17,8 41040 Espartinas 14,2 14 41016 Bollullos de la Mitación 28,5 8,4 41015 Benacazón 20,6 11,6 41098 Villanueva del Ariscal 5,6 10,4 41067 Olivares 023 41094 Umbrete 23 0