Optimización de transportes de reparables en el sector aeronáutico

Trabajo de Fin de Máster Optimización de transportes de reparables en el sector aeronáutico Autor: Antonio Blanch Rodríguez Tutor: Antonio Javier Gallego Len Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2023 Trabajo de Fin de Máster Máster en Ingeniería Industrial Optimización de transportes de reparables en el sector aeronáutico Autor: Antonio Blanch Rodríguez Tutor: Antonio Javier Gallego Len Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2023 A mi familia y a mi pareja, por hacerlo todo tan fácil i Resumen En el presente trabajo se analiza el flujo de materiales y equipos reparables de una Empresa Aeronáutica desde un almacén central situado en España hacia diferentes centros reparadores en Inglaterra, y viceversa. El objetivo es reducir el tiempo de tránsito total de estos equipos tanto en su trayecto a reparar como en el retorno una vez reparado, intentando no incrementar el coste. Para ello, se resuelven los problemas de ubicación óptima de un centro de distribución teniendo en cuenta la ubicación geográfica y demanda de los centros reparadores, y posteriormente un problema de rutado de vehículos. Para este segundo problema, se lleva a cabo un extenso estudio del estado del arte y se define el problema como un VRPPD, que se resuelve mediante métodos heurísticos. Para evaluar la bondad de la solución propuesta, se lleva a cabo un análisis exhaustivo de los tiempos de tránsito y costes logrados con esta solución, simulando las rutas que se deben llevar a cabo durante un año. iii Abstract This project analyses the flow of repair parts of an Aeronautical Company from a central warehouse located in Spain to different repair centres in England, and back. The objective is to reduce the total lead time of this materials both on its journey to repair and on its return once repaired, trying not to increase the cost. To achieve this, the problems of optimal location of a distribution centre, taking into account the geographical location and demand of the repair centres, and then a problem of vehicle routing are solved. For this second problem, an extensive state-of-the-art study is carried out and the problem is defined as a VRPPD, which is solved using heuristic methods. To evaluate the goodness of the proposed solution, an exhaustive analysis of the lead times and costs achieved with this solution is made, simulating the routes to be carried out during a year. xi Acrónimos y abreviaciones 3PL Third Party Logistics 4PL Fourth Party Logistics ADR Accord européen relatif au transport des marchandises Dangereuses par Route AOG Aircraft On Ground AWB Air Waybill BL Bill of Landing BR Business Rule CEDI CEntro de DIstribución CMR Convention relative au contrat de transport international de Marchandises par Route CVRP Capacited VRP DUA Documento Único Administrativo DVRP Distance VRP EAR Export Administration Regulations HazMat Hazardous Material InCoTerms International Commercial Terms ITAR International Traffic in Arms Regulations Loc-ID Location ID LT Lead Time MDVRP Multiple Depot VRP PL Proveedor Logístico PN Part Number PVRP Periodic VRP RN Repair Notification RTN Routine SDVRP Split Delivery VRP SVRP Stochastic VRP TR Transport Request TSP Traveling Salesman Problem UE Unión Europea VBA Visual Basic for Applications VRP Vehicle Routing Problem VRPB VRP with Backhauls VRPPD VRP with Pickup and Delivery VRPSF VRP with Satellite Facilities VRPTW VRP with Time Windows 1 1 INTRODUCCIÓN 1.1 Objetivos El principal objetivo del presente trabajo es analizar y diseñar una solución para el transporte de materiales y equipos reparables de una Empresa Aeronáutica desde un almacén central situado en España hacia diferentes centros reparadores en Inglaterra, y viceversa. Para ello, se va a analizar el estado actual de este flujo de transportes, tanto en el ámbito económico como a nivel de tiempos de tránsito (Lead Times). Una vez llevado a cabo este análisis, se propondrán diferentes soluciones, diseñando un algoritmo heurístico que ayude a la óptima gestión de la red de transporte. Además, se definirán en base a datos de costes y tiempos de entrega, parámetros como el tamaño de la flota, la frecuencia o el tipo de transporte. Figura 1.1. Modelos militares a) Airbus A400M y b) Boeing C-17 1.2 Alcance La Empresa Aeronáutica a estudio desea mejorar los tiempos de sus servicios postventa, aspirando a reducirlos un 20%. Dentro de todo el flujo del material, el transporte tiene un alto impacto en estos tiempos, por lo que se propone reducir el Lead Time de transporte en un 30%. Este proyecto se centrará en la reducción del Lead Time de transporte de elementos reparables y reparados, más concretamente aquellos que vayan o vuelvan de centros reparadores situados en Reino Unido, ya que son actualmente los más altos en relación con la distancia al almacén central. El resultado del proyecto debe ser una solución de compromiso entre el extra coste que la empresa debe asumir y los tiempos de tránsito obtenidos, pero en cualquier caso se debe superar el 30% de reducción de LT sin incrementar más del 5% el coste de transporte. Introducción 2 1.3 Principales Stakeholders del Proyecto Al ser un proyecto en el que se involucran multitud de partes interesadas (también llamadas stakeholders), los intereses de cada uno de ellos y el papel que juegan de cara a alcanzar el objetivo deben ser tenidos en cuenta, y por ello es importante identificarlos. Los principales stakeholders del proyecto son:  El equipo logístico de la Empresa Aeronáutica  El equipo de finanzas de la Empresa Aeronáutica  El operador logístico del 4PL  Los operadores logísticos de los diferentes 3PLs  El almacén central de la Empresa Aeronáutica  Los diferentes Centros Reparadores que trabajan para la Empresa Aeronáutica 1.4 Estructura del Trabajo El trabajo está estructurado en 8 grandes capítulos, orientados a lograr los objetivos descritos previamente a la vez que se exponen gradualmente los conceptos y métodos utilizados. En primer lugar, se llevará a cabo una breve introducción al entorno aeronáutico, centrado en la gestión de materiales y más concretamente en los flujos de transporte para servicios postventa. Posteriormente, se expone el problema concreto que debemos resolver, comparando la situación previa al estudio (AS-IS) y las posibles alternativas que pueden ayudarnos a lograr un escenario que cumpla los objetivos marcados (TO-BE). Una vez definido el problema y expuestas las posibles soluciones, dividimos la resolución del mismo en dos fases. La primera trata de encontrar la ubicación óptima para la colocación de un centro de distribución, usando métodos numéricos y teniendo en cuenta factores ambientales y económicos. En la segunda fase, y una vez definido el punto del que partirán los vehículos, se trata de resolver un problema de rutado de vehículos. En este capítulo se lleva a cabo una exploración del contexto histórico y del estado del arte tanto de los tipos de problemas de rutado de vehículo, para encontrar el que más se ajuste a la solución que queremos implantar, como de los métodos de resolución. Una vez modelado el problema y elegido los métodos de resolución, se procede a diseñar una aplicación en VBA para resolver el mismo. Para evaluar la idoneidad de la solución y la aportación del proyecto a mejorar el desempeño tanto económico como en relación a los tiempos de la Empresa Aeronáutica, se lleva a cabo un análisis comparando los datos del AS-IS y del TO-BE. Por último, se resumen los principales logros del proyecto y se exponen las conclusiones del mismo, poniendo también el foco en posibles trabajos futuros relacionados que pudieran mejorar la solución obtenida. 3 3 Optimización de transportes de reparables en el sector aeronáutico 2 CONTEXTO En este capítulo se describirán los diferentes flujos de materiales que se llevan a cabo en una Empresa Aeronáutica. Hay que distinguir los flujos de Producción de aquellos de Servicios, que son los que nos afectan en este trabajo. Los flujos de Producción son todos aquellos movimientos de material (transportes) que son necesarios para asegurar el abastecimiento de materiales y equipos para la producción de aviones de serie. Sin embargo, los flujos de Servicios son aquellos que abastecen de materiales y equipos a los aviones una vez son entregados a cliente, es decir, son transportes de materiales para servicios post-venta. La gestión de ambos flujos es independiente y es llevada a cabo por departamentos diferentes, aunque es posible buscar sinergias en soluciones de transporte entre ambos. En los dos casos, el servicio de transporte está subcontratado, y no es la Empresa Aeronáutica la que lleva a cabo los movimientos de material por sus propios medios, como se explicará con detalle en la sección 2.2 (Estructura de los Proveedores Logísticos). Con la gestión del transporte subcontratada de esta forma, cuando se quiera solicitar un transporte de mercancía, será necesario crear un requerimiento de transporte (TR, por las siglas de Transport Request en inglés) que será el identificador único del mismo, independientemente del transportista que lo lleve a cabo. Esta referencia se refiere al envío, no solo al material. En otras palabras, un material que deba ser enviado desde el cliente al almacén central de la Empresa Aeronáutica, y de este almacén central al centro reparador, tendrá dos TRs, uno por cada transporte, a pesar de ser el mismo material. Por otra parte, un TR podrá contener varios materiales, siempre que el origen y el destino sea el mismo. Esta práctica es conocida como consolidación, y lleva consigo multitud de ventajas frente a tener un TR por cada material, como puede ser la menor gestión que es necesaria, la mejor trazabilidad o la posibilidad de optimizar los costes de transporte. En este capítulo se tratará de describir el proceso completo de transporte para cualquier origen, destino y tipo de material, desde la creación del TR en origen hasta la recepción del material en destino, incluyendo todos los procesos administrativos y logísticos que puedan ser necesarios entre medias. 2.1 Flujo de materiales El flujo de materiales y equipos para Servicios (aquellos que dan soporte al cliente una vez el avión ha salido de la factoría y ha sido entregado) puede dividirse entre Repuestos y Reparables. A continuación se describen las características de cada uno de ellos: 2.1.1 Repuestos Los Repuestos o Spare Parts son materiales nuevos que son enviados al cliente para reemplazar a otro que es defectuoso. En este caso, el material defectuoso no es reparado, sino que se cambia por otro que nunca ha sido reparado ni ensamblado en ningún otro avión. El flujo de materiales, en este caso, suele ser el siguiente: la Empresa Aeronáutica compra diferentes Part Contexto 4 Numbers (P/N) nuevos a diferentes proveedores o suppliers y los almacena en su Almacén Central. Este transporte desde proveedor al almacén puede llevarse a cabo mediante los medios del supplier o mediante los medios de la Empresa Aeronáutica (aunque subcontrate este servicio), dependiendo del Incoterm acordado en el contrato (ver sección 2.3). Cuando un cliente requiera de ese P/N, este se le enviará directamente desde el Almacén Central, lo que reduce los tiempos logísticos y hace posible una mejor gestión. Además, el paso por almacén asegura un control de calidad que no se llevaría a cabo en caso de que fuese el supplier el que enviase directamente al cliente. Figura 2.1. Flujo de Spares Además de para reemplazar equipos o partes defectuosas, un cliente puede comprar Spare Parts para actualizar la versión de su avión o para hacerse con su propio stock de repuestos, y así disponer de los materiales al momento en que los requiera. 2.1.2 Reparables A diferencia de los Spare Parts, las Reparables son materiales que sí han sido previamente montados en el avión. Para llevar a cabo reparaciones, mejoras o reajustes, estos materiales o equipos se desensamblan del avión y son enviados con una Repair Notification (RN) al almacén central de la Empresa Aeronáutica, donde se evalúan los daños y se redireccionan al Centro Reparador más adecuado. Este transporte es el objeto de estudio en este trabajo, así como el transporte de vuelta desde Centro Reparador hasta el Almacén Central una vez el equipo ha sido reparado. Una vez allí, el equipo de Calidad del almacén se encarga de verificar que el material cumple los estándares de calidad tanto física como documentalmente, y se envía de nuevo al cliente para que pueda volver a montarlo en su avión. Figura 2.2. Flujo de Repairs 5 5 Optimización de transportes de reparables en el sector aeronáutico Otra posibilidad para llevar a cabo este flujo completo es evitar el paso intermedio por el almacén central y que el cliente le envíe el material directamente al Centro Reparador y este también se lo devuelva directamente. Este tipo de flujo lleva consigo algunas ventajas, pero también algunos inconvenientes, por lo que solo se debe llevar a cabo en casuísticas particulares donde las ventajas superen a los inconvenientes. La principal ventaja de esta práctica, llamada Direct Shipment, es la reducción de tiempos logísticos al pasar de 4 a 2 transportes. Sin embargo, algunos inconvenientes que pueden surgir son los siguientes:  Imposibilidad de verificar la calidad, por lo que sólo será posible para clientes en los que exista un equipo de la Empresa Aeronáutica en sus instalaciones.  Menor posibilidad de consolidación, ya que habrá muchas más combinaciones de orígenes-destinos.  Problemas aduaneros, ya que los materiales del cliente son importados y reexportados por la Empresa Aeronáutica en el proceso normal, y en este caso tendrían que ser importados y reexportados por los Centros Reparadores, asumiendo las tasas y aranceles correspondientes.  Menor control de la documentación y facturas. 2.2 Estructura de los Proveedores Logísticos En esta sección se describirá la estructura de los diferentes Operadores Logísticos que intervienen en el proceso de transporte. Esta estructura se divide en diferentes Proveedores Logísticos (PL), que se clasifican según los servicios que desempeñen los diferentes operadores logísticos y su grado de externalización. En la siguiente figura se pueden identificar los cuatro niveles de Proveedores Logísticos de esta estructura: Figura 2.3. Estructura de Proveedores Logísticos  1PL: Es el eslabón más bajo de la pirámide y hace referencia a la compañía (o persona individual) que tiene su propio vehículo o flota de vehículos y es capaz de transportar material de un lugar a otro. Los proveedores logísticos de este nivel suelen ser agencias de transporte que son subcontratadas por otras empresas (generalmente 2PL), de manera que ellos se encargan de la compra y manutención de la flota, así como de la gestión de los conductores, pero no se hacen cargo de almacenajes ni otras Contexto 6 operaciones logísticas de mayor nivel. Para los propósitos de este texto, la Empresa Aeronáutica no tendrá contacto con estos proveedores logísticos, dejando que los PL de mayor nivel puedan subcontratar los servicios que vean necesarios.  2PL: Este nivel engloba el transporte de material desde un área geográfica a otra, ya sea por carretera, mar, aire, etc. Este eslabón puede ser, por ejemplo, una pequeña empresa de mensajería, una compañía ferroviaria, una aerolínea o cualquier otra compañía de transporte en un segmento específico de la cadena logística. La principal diferencia con respecto a los 1PL es que el 2PL trabaja en un ámbito más amplio y se encarga de coordinar la flota y las operaciones de transporte, aunque los servicios que ofrezca sean similares. Es muy habitual que los 3PL subcontraten a distintos 2PL en función de la zona geográfica, el tipo de transporte, la disponibilidad y otros factores. Al igual que en el caso anterior, la Empresa Aeronáutica no contratará directamente a los 2PL, sino que dejará esta gestión al 3PL, aunque la solución propuesta implique una coordinación entre ambos.  3PL: En este nivel se incluyen las principales empresas de transporte y logística, ya sea con su propia flota o mediante subcontratación a un 2PL, y con espacio de almacenaje. La capacidad de almacenaje les permite disponer de los materiales más cerca del cliente final y, por tanto, entregar en menor tiempo. También les permite usar sus almacenes como cross-dock (muelle cruzado) y hacer uso de diferentes 2PLs o diferentes redes del mismo. Este nivel también incluye soluciones de software informático logístico y servicios de análisis, para seguir y rastrear el estado de entrega de los distintos envíos. Esta logística de terceros proporciona todos los servicios mencionados y también gestiona cualquier obstáculo o inconveniente que surja durante el proceso, liberando a los 2PL de estos procesos. Los 3PL, al ser operadores de más alto nivel, ofrecen soluciones personalizadas según las necesidades de la empresa contratante, de sus clientes y del tipo de negocio que llevan a cabo. Como estos acuerdos suelen ser a largo plazo, el operador logístico puede ir aprendiendo de la logística de su cliente e ir adaptando y optimizando sus procesos. Este suele ser un trabajo conjunto y el análisis que se va a llevar a cabo en este trabajo es un ejemplo del mismo.  4PL: A diferencia de los 3PL, el 4PL no lleva a cabo el transporte físico, sino que actúa como gestor y supervisor de las operaciones logísticas. En algunas ocasiones, la propia empresa contratante puede actuar como 4PL, pero en empresas grandes como es este caso, se suele subcontratar este servicio a un operador logístico externo que se encargue de asignar cada TR que crea el almacén al 3PL más adecuado teniendo en cuenta las necesidades del cliente, la prioridad del envío, el tipo de transporte y 7 7 Optimización de transportes de reparables en el sector aeronáutico teniendo en cuenta ciertas restricciones como la documentación y el tipo de material a transportar. 2.3 Incoterms Los Incoterms son los términos y condiciones de una transacción internacional de compraventa y estipulan cuándo y dónde se produce la transferencia del riesgo y la obligación del coste, quién es responsable en cada punto del transporte y otros factores relacionados con dichas transacciones. El término Incoterm es la abreviatura de "International Commercial Terms". Los Incoterms fueron creados por la ICC (International Chamber of Commerce) en 1936 y son revisados normalmente cada 10 años para actualizarlos, renovarlos y sustituir términos que hoy en día ya no se utilicen. Actualmente, los más actualizados son los de 2020, y para diferenciar las distintas versiones estos términos van acompañados de un número que indica la actualización de ese término en concreto. Los Incoterms vienen determinados por:  Dónde y cuándo se produce la transferencia de riesgo y responsabilidad del vendedor al comprador.  Lugar de entrega  Responsabilidad de contratar y pagar el transporte y el seguro  Gestión de la documentación por cada parte Según los términos del Incoterm, se identifican tres grupos:  F/E: Recogida en el país de origen  C: Responsabilidad compartida, llega al país de destino (aeropuerto/puerto marítimo)  D: Entrega al cliente La Figura 2.4 muestra los distintos Incoterms en su versión más actualizada. Para cada Incoterm y en cada punto, se diferencia la responsabilidad en términos de coste y en términos de riesgo, ya que puede no ser la misma para algunos casos. A continuación se describen los Incoterms más usados en este negocio, para un envío desde el almacén central a un Centro Reparador o Cliente:  FCA: En este caso, la única responsabilidad de la Empresa Aeronáutica sería despachar el material en el almacén y prepararlo para el transporte (embalaje, trincaje y correcta identificación). Además, si el envío es extracomunitario debe encargarse de la generación de la documentación de exportación.  DAP: Además de lo expuesto en el ejemplo del envío con Incoterm FCA, ahora es responsabilidad de la Empresa Aeronáutica el transporte. Podría hacerlo por sus propios medios, pero en este caso se subcontrata a un 3PL para que lleve a cabo el transporte hacia destino. Una vez en las aduanas acordadas con el cliente o centro reparador, es responsabilidad del consignatario hacer el despacho aduanero, aunque el transporte desde las aduanas hasta el punto de entrega vuelve a llevarlo a cabo el Contexto 14 información esencial sobre la carga.  Requisitos de Seguridad: Establece medidas específicas para la manipulación, carga y descarga de materiales peligrosos, incluyendo capacitación y equipo de protección personal para el personal involucrado. Los materiales peligrosos se dividen en nueve clases principales, y cada una debe ir identificada con al menos una de las etiquetas de la Figura 2.7. Figura 2.7. Clases de materiales peligrosos según su clase  Explosivos (Clase 1)  Gases (Clase 2)  Líquidos Inflamables (Clase 3)  Sólidos Inflamables (Clase 4)  Sustancias Comburentes (Clase 5)  Sustancias Tóxicas e Infecciosas (Clase 6)  Materiales Radioactivos (Clase 7)  Corrosivos (Clase 8)  Sustancias Peligrosas Diversas (Clase 9) 2.9 Bussiness Rules Cuando se genera una petición de transporte (TR), esta se debe asignar a un 3PL entre todos los que tengan relación contractual con la Empresa Aeronáutica. Esta asignación se basa tanto en el coste del envío como en el tiempo de tránsito ofrecido, cumpliendo siempre los requerimientos del tipo de envío seleccionado. Ya que muchos de los flujos son recurrentes para la mayoría de empresas, las principales rutas de transporte ya han 15 15 Optimización de transportes de reparables en el sector aeronáutico sido analizadas con anterioridad para elegir con antelación la opción más ventajosa, de manera que cuando se genera un TR ya se puede saber qué 3PL debe asignarlo. Las reglas y lógicas que dictan esta elección son denominadas Business Rules y son diseñadas en conjunto entre el 4PL y el cliente para optimizar sus costes y su performance. Los criterios de estas reglas se basan en los siguientes inputs:  Origen  Destino  Peso  Volumen  Prioridad  Clasificación Militar Para realizar cada una de estas reglas es posible agrupar las diferentes direcciones pre-establecidas. De esta manera, por ejemplo, podemos decir que todos los envíos que salgan cualquier ubicación en Madrid y que vayan a Francia para unos criterios de peso, volumen, prioridad y clasificación determinados, se asignen a un 3PL determinado. Si no se hiciese uso de este tipo de agrupaciones que dan lugar a regiones, el número de reglas sería excesivamente alto, ya que existirían n2 combinaciones posibles, siendo n el número de ubicaciones existentes, que se multiplicarían por todas las combinaciones de peso, volumen, prioridad y clasificación militar. Por ejemplo, suponiendo que existen 2000 ubicaciones diferentes y que el TR puede ser RTN o AOG, Civil o Militar y el peso menor o mayor de 300 kg, se deberían definir 32 millones de business rules, algo totalmente inmanejable. Como se comentaba anteriormente, por ejemplo, todas las ubicaciones de Madrid podrían agruparse en una región y todos los LOC-ID de Francia en otra. Sin embargo, se pueden crear regiones más pequeñas para definir BRs, por ejemplo, para el norte y para el sur de Francia, o incluso se pueden crear regiones que incluyan LOC-IDs de diferentes lugares pero que tengan características comunes (por ejemplo, los almacenes o plantas que participan en Programas comunes, o los centros de reparación de una determinada zona, dejando en otra región ubicaciones con proximidad geográfica pero a los que se aplican diferentes BRs). 2.10 Visual Basic for Applications (VBA) Visual Basic for Applications es un lenguaje de programación diseñado por Microsoft y disponible para su uso con el paquete Microsoft Office, aunque suele ser especialmente útil cuando se utiliza adjunto a Excel. Este lenguaje de programación apareció por primera vez en la versión Excel 97 y se convirtió en un entorno para el desarrollo de software potente, funcional y flexible. Los programas creados en este lenguaje se denominan Macros (del griego μακρο, que significa grande), que es una abreviatura de macroinstrucción, y consiste en una secuencia ordenada de instrucciones que se ejecutan cuando el usuario lo decide o cuando se produce un evento durante el uso de Excel. Suele usarse para llevar a Contexto 16 cabo la automatización de tareas repetitivas, sin embargo, al ser un lenguaje de programación muy completo e incorporar muchas funciones que forman parte de los lenguajes de programación estándar, también es posible diseñar programas o módulos complejos que interactúen con una hoja de Excel. Figura 2.8. Logotipo VBA En este proyecto se utilizará VBA como lenguaje de programación para todos los algoritmos que se diseñen, ya que nos aporta las siguientes ventajas:  Fácil interacción con Microsoft Excel, donde se encuentra la base de datos con la que vamos a trabajar y donde vamos a representar los resultados.  Accesible a la mayoría de empresas y trabajadores, ya que forma parte del paquete Office.  Con capacidad suficiente para procesar los algoritmos que se analizan en este proyecto en tiempos aceptables. 17 17 Optimización de transportes de reparables en el sector aeronáutico 3 DESCRIPCIÓN DEL PROBLEMA 3.1 Análisis del AS-IS Dentro de los flujos de materiales descritos en el apartado anterior, en este proyecto nos centraremos en los reparables que se envían desde el Almacén Central a centros reparadores ubicados en Inglaterra. Este flujo es especialmente interesante para su estudio ya que en el mercado no existen muchas alternativas rápidas y económicas que puedan dar una solución óptima al problema. Siguiendo las alternativas de transporte descritas en el Capítulo 2.6, se analizarán los pros y los contras de cada una de las opciones posibles:  Vehículo dedicado: esta es la opción que se usa para transportes en AOG, ya que son los más rápidos pero a la vez los más costosos. La operativa en este caso es simple, ya que la documentación de exportación se hace teniendo en cuenta la matrícula del vehículo dedicado y la recogida tiene lugar en cuanto el DUA está listo. Se suelen usar furgonetas o furgones que puedan circular sin restricciones para llegar lo antes posible a destino.  Ruta: es la alternativa para flujos donde el volumen es alto, la urgencia es media/baja y los destinos son siempre los mismos. Como veremos a continuación, la Empresa Aeronáutica hace uso de una gran cantidad de centros reparadores diferentes (cada uno especializado en unas piezas en particular) y si analizamos el volumen semanal, veremos un volumen alto en general pero bajo para cada centro reparador en particular. Esto hace que la ruta como tal no sea una opción viable ya que el tiempo que tardaría en hacer todas las paradas sería incluso superior al de llegar desde España a Inglaterra.  Grupaje: esta opción es la que se usa actualmente para envíos rutinarios, ya que el coste es relativamente bajo. Sin embargo, los Lead Times que ofrecen los diferentes 3PL son excesivamente altos para los tiempos que serían aceptables por cliente, por lo que el objetivo del proyecto sería dejar de usar esta opción incrementando el coste lo mínimo. Además, existe la dificultad añadida de que si se quiere hacer la pre-importación automática se debe conocer la matrícula dos días antes de la salida para poder incluirla en el DUA. Hay que tener en cuenta que en este tipo de transportes, los materiales van cambiando de vehículo y que la matrícula que debe figurar en el DUA es la del que cruza la frontera, que en algunas ocasiones es imposible de conocer. Esto ralentiza aún más el Lead Time total.  Cross-docking: esta opción es interesante para este tipo de flujo ya que nos permitiría aprovechar las ventajas de la ruta (bajo coste y tránsito bajo, solo sumando tiempos de espera al día de salida) y las de transporte semi-dedicados para llevar a cabo lo conocido como “última milla”. Además, si se consigue usar siempre el mismo o los mismos vehículos, nos permitiría usar siempre la misma matrícula y por lo tanto se podría hacer la pre-importación con esta. En la actualidad, los flujos tanto de ida como de vuelta a los centros reparadores se gestionan de la siguiente manera: Descripción del Problema 18  Flujo de Almacén Central a Centro Reparador: los AOG se gestionan con vehículos dedicados y los RTN se gestionan mediante grupaje. Para poder hacer la pre-importación, se tiene un acuerdo con un 3PL que asegura la misma matrícula para el paso por la frontera si los envíos salen siempre el mismo día. Es decir, además de los altos LT del grupaje, hay que sumar que solo salen del Almacén Central una vez a la semana. De esta manera, en el peor de los casos que es que un TR esté listo justo el día después del día de salida, el Lead Time será: 2 días de generación de DUA, 6 días de espera a la salida y 8 días de tránsito, lo que sumaría 16 días. Ciudad Latitud Longitd ISLE OF WIGHT 50,67 -1,33 WIMBORNE 51,54 -0,21 SOUTHEND-ON-SEA 51,54 0,71 OXFORDSHIRE 51,83 -1,25 GLOUCESTER 51,87 -2,25 BRISTOL 51,46 -2,6 COVENTRY 52,41 -1,51 CRAWLEY 51,11 -0,18 WOLVERHAMPTON 52,58 -2,13 BRIDPORT 50,73 -2,76 LONDON 51,51 -0,13 POOLE 50,74 -1,95 HEREFORD 52,06 -2,72 MARLOW 51,57 -0,78 LUTON 51,88 -0,42 TITCHFIELD 50,85 -1,24 PORTSMOUTH 50,8 -1,08 ESSEX 51,77 0,46 WATERHEAD 53,55 -2,07 YEOVIL 50,94 -2,63 REDDITCH 52,31 -1,94 LEIGHTON BUZZARD 51,92 -0,66 WEST SUSSEX 50,94 -0,53 VERWOOD, DORSET 50,87 -1,87 CHELTENHAM 51,9 -2,07 HANFORTH 53,35 -2,22 MARSTON 58, -2,49 BLACKPOOL 53,82 -3,06 SUSSEX 50,94 -0,06 BASILDON, ESSEX 51,57 0,45 CORNWALL 50,42 -4,75 CHRISTCHURCH 50,74 -1,78 FAREHAMHAMPHIRE 50,85 -1,18 SOUTHALL 51,51 -0,38 Tabla 3.1. Ubicación de los centros reparadores (en grados decimales) 19 19 Optimización de transportes de reparables en el sector aeronáutico  Flujo de Centro Reparador a Almacén Central: en este caso la gestión es prácticamente igual, aunque al no tener que hacer pre-importación a la vuelta hace que las recogidas de grupaje puedan realizarse en cuanto el material y su documentación esté lista. De esta manera, los AOG tendrán un LT de 2 días en vehículo dedicado al igual que en la ida, y los RTN tendrán un LT de 10 días. Los centros reparadores con los que trabaja esta Empresa Aeronáutica se muestran en la Tabla 3.1, y en la siguiente figura se muestra la ubicación en el mapa Inglaterra de cada uno de estos puntos Figura 3.1. Representación gráfica de las ubicaciones de los centros reparadores 3.2 Posibles soluciones para el TO-BE Aunque los costes de transporte para la opción elegida en el AS-IS son económicos y siempre existe la posibilidad de pagar más por un transporte urgente, los Lead Times de los TRs en RTN son excesivos y provocan penalizaciones y quejas de clientes y proveedores. A continuación se plantea la alternativa que estudiaremos en adelante en este proyecto y, si bien los costes se incrementarán, puede ser la opción más óptima que equilibre coste y Lead Time si se diseña de manera correcta. La solución propuesta consiste en establecer una frecuencia de salida de un vehículo dedicado desde el Almacén Central hacia un punto determinado en Inglaterra. Este punto, que se determinará en el Capítulo 4 de acuerdo con la ubicación de todos los centros reparadores para calcular su ubicación óptima, será el centro de consolidación y a él llegarán todos los materiales reparables desde el Almacén Central, desde donde se llevarán a reparto por medio de un número determinado de camionetas con una frecuencia también determinada que se calculará en el Capítulo 6 según la demanda. El flujo de materiales reparados será el mismo pero al contrario, pudiendo aprovechar las furgonetas que se usan para repartir a destino final (haciendo la “última milla”) y la vuelta del vehículo que salió de España de vuelta. Por lo tanto, las variables a determinar en este problema serán las siguientes:  La ubicación óptima del centro de distribución en función de la ubicación de los centros reparadores  La frecuencia de la ruta del almacén central al centro de distribución y viceversa  La frecuencia de salida a reparto final  La cantidad de vehículos usados para llevar a cabo el reparto final Descripción del Problema 20 21 21 Optimización de transportes de reparables en el sector aeronáutico 4 UBICACIÓN DEL CENTRO DE DISTRIBUCIÓN 4.1 Metodología Para determinar cuál es la ubicación óptima del centro de distribución, tendremos en cuenta la Tabla 3.1 con las coordenadas de cada centro reparador. Además, también tendremos en cuenta la demanda de cada uno de los centros, de manera que aunque un centro esté muy alejado del centro de distribución, si la frecuencia con la que hay que ir es baja, el total de kilómetros que se recorrerán a largo plazo será menor. En la literatura podemos encontrar diferentes modelos para determinar esta ubicación óptima, si bien tratándose de un problema con una alta variabilidad y distancias cortas, podemos usar la ubicación obtenida por el algoritmo como una aproximación o un rango de área más favorable. Para este caso, los modelos de localización continua (conocidos también como modelos en el plano) pueden servirnos para esta primera aproximación. Estos modelos se caracterizan por dos atributos principales:  El espacio de solución es continuo, de manera que cualquier punto del plano es una solución potencial. Al buscar un punto de partida, esto no representa un problema ya que podemos determinar la ubicación del centro de distribución en un lugar cercano al obtenido.  La distancia se mide como la trayectoria lineal o euclidiana, asumiendo que el error debido al trazado de las carreteras no es alto. Como la mayoría de centros reparadores se encuentran a las afueras de las ciudades, podemos tomar esta hipótesis como válida ya que evitaremos los trazados irregulares de calles urbanas y el tráfico. Los modelos de localización continua o planos utilizan las coordenadas de los centros reparadores para hallar una localización (x,y) óptima que genere la mínima suma de las distancias entre las instalaciones y los puntos de demanda (centros reparadores). Estos métodos son matemáticos y sencillos de modelar, ya que analizan la demanda y la ubicación de las instalaciones ya existentes en el área geográfica. Para calcular las distancias, el cálculo más adecuado sería usando el método de Haversine o semiverseno, que tiene en cuenta la curvatura de la tierra. Esta distancia esférica se calcula mediante las siguientes fórmulas: 𝑎=sin2(∆𝜑 2)+cos⁡(𝜑1)∙cos⁡(𝜑2)∙𝑠𝑒𝑛2(∆𝛿 2) (4.1) 𝑐 =2∙atan2(√𝑎,√1−𝑎) (4.2) 𝑑ℎ=𝑅∙𝑐 (4.3) Donde φ es la latitud, δ la longitud, R el radio terrestre y d la distancia esférica. Sin embargo, como las distancias a calcular son pequeñas, asumiremos un pequeño error calculando todas las distancias como lineales o euclidianas, mediante la siguiente fórmula: Ubicación del Centro de Distribución 22 𝑑𝑒=√∆𝜑2+∆𝛿2 (4.4) Siendo ∆φ es la diferencia de latitud, ∆δ la diferencia de longitud, y d la distancia euclidiana. Para llevar a cabo la búsqueda del punto más óptimo, utilizaremos el Método del Centro de Gravedad. Utilizando este método, asumimos que la mejor ubicación del centro de distribución sería cerca del centro de gravedad de un cuerpo imaginario en el que cada punto origen-destino tuviera como densidad este producto. Las coordenadas se obtendrán mediante las siguientes ecuaciones: 𝑥𝑘=∑𝑙𝑖𝑥𝑖 𝑛 𝑖=1 ∑𝑙𝑖 𝑛 𝑖=1 (4.5) 𝑦𝑘=∑𝑙𝑖𝑦𝑖 𝑛 𝑖=1 ∑𝑙𝑖 𝑛 𝑖=1 (4.6) 𝑑𝑖=√(𝑥𝑖−𝑥𝑘)2+(𝑦𝑖−𝑦𝑘)2 (4.7) Donde xi e yi son las coordenadas de cada centro reparador, li es el volumen de la demanda y di es la distancia del centro reparador i al centro de distribución xk,yk. Existe otro método, llamado Método de Webber cuyo objetivo es encontrar un punto que minimice los costes de transporte (la distancia) desde el nuevo centro de distribución hasta los ya existentes mediante iteraciones. El objetivo de este otro método es determinar la ubicación (x,y) del centro de distribución minimizando la suma del producto de cada la distancia y volumen de demanda. Mediante iteraciones, se busca el mínimo de la siguiente función objetivo: 𝑚𝑖𝑛⁡𝐹 =∑𝑙𝑖𝑑𝑖(𝑥,𝑦) 𝑛 𝐼=1 (4.8) Siendo y di es la distancia del centro reparador i al centro de distribución, calculada según la expresión (4.7). 4.2 Algoritmo A continuación se llevará a cabo el cálculo del punto óptimo para la ubicación del centro de distribución. Las coordenadas de cada centro reparador se toman de la Tabla 3.1, y las demandas semanales se tomarán de la siguiente tabla: 23 23 Optimización de transportes de reparables en el sector aeronáutico Ciudad Nº de TRs ida Nº de TRs vuelta Total ISLE OF WIGHT 1,3 1,2 2,5 WIMBORNE 1,8 1,5 3,2 SOUTHEND-ON-SEA 1,2 0,6 1,8 OXFORDSHIRE 0,7 0,0 0,8 GLOUCESTER 3,8 0,5 4,3 BRISTOL 1,3 1,3 2,5 COVENTRY 2,2 0,7 2,9 CRAWLEY 1,4 0,6 2,0 WOLVERHAMPTON 1,3 0,6 1,9 BRIDPORT 1,0 0,6 1,5 LONDON 0,9 0,6 1,5 POOLE 0,6 0,1 0,7 HEREFORD 1,6 0,1 1,6 MARLOW 1,3 0,6 1,9 LUTON 0,6 0,6 1,3 TITCHFIELD 0,5 0,6 1,1 PORTSMOUTH 1,5 0,7 2,2 ESSEX 0,7 0,5 1,2 WATERHEAD 1,1 0,5 1,6 YEOVIL 1,1 0,5 1,7 REDDITCH 0,6 0,5 1,1 LEIGHTON BUZZARD 0,8 0,5 1,3 WEST SUSSEX 0,9 0,1 0,9 VERWOOD, DORSET 2,5 2,5 5,1 CHELTENHAM 1,0 0,6 1,6 HANFORTH 0,9 1,4 2,3 MARSTON 1,0 0,1 1,1 BLACKPOOL 0,5 0,0 0,6 SUSSEX 1,5 0,0 1,5 BASILDON, ESSEX 1,2 0,0 1,3 CORNWALL 1,4 0,6 1,9 CHRISTCHURCH 0,7 0,3 1,0 FAREHAM-HAMPHIRE 1,3 1,0 2,3 SOUTHALL 1,4 0,6 2,0 Tabla 4.1. Volúmenes de demanda de los centros reparadores Puede llamar la atención que la “demanda” la y “oferta”, entendidas como el número de TRs que el centro reparador recibe (reparables) y que el centro reparador expide (reparados), respectivamente, no sean iguales. Lo lógica dicta que todos los equipos y piezas que se reciben luego son enviados de vuelta reparados con otro TR, sin embargo, hay un par de factores que hacen que estos volúmenes no sean iguales:  En algunos casos, tanto en el Almacén Central como en el centro reparador se pueden enviar varios materiales juntos que en el flujo inverso puedan viajar de manera separada (con TRs diferentes). Por ejemplo, desde el Almacén Central se envían 3 equipos diferentes bajo un mismo TR, sin embargo el tiempo de reparación de cada uno de ellos es diferente por lo que el centro reparador irá enviando cada uno según los vaya reparando, haciendo que lo que a la ida era un TR a la vuelta sean 3. Ubicación del Centro de Distribución 30 tecnológico o el de la logística, por lo que la disponibilidad de suelo industrial es muy alta. Con 4 puntos valoramos a Swindon ya que, a pesar de ser una ciudad con menor extensión y población, ha sido siempre conocida por su sólida base industrial y su historia en la fabricación, aunque ha experimentado una transformación en su economía en las últimas décadas, alejándose de la manufactura pesada hacia sectores más ligeros y la tecnología. Con 2 puntos valoraremos a Newbury y Andover, que aunque cuentan con pequeños parques empresariales, la oferta no es demasiado alta. Para puntuar la distancia media en kilómetros de todos los centros reparadores, asignaremos el valor 1 al mayor (Swindon), el valor 5 al menor (Newbury) y se ponderará la nota de los otros dos (3,32≈3 para Reading y 2,42≈2 para Andover.  Precio del suelo industrial: El precio del suelo industrial varía en función de factores como la ubicación, la zonificación (es decir, si ya tienen permisos para uso industrial), la infraestructura, servicios y la demanda y oferta del mismo. Basándonos en estos factores, además de información cuantitativa obtenida de diferentes webs y agencias inmobiliarias, asignamos los valores de 4 a Swindon, Newbury y Andover, y 3 a Reading.  Accesibilidad y proximidad a la red principal de carreteras: Otro punto importante a tener en cuenta además de la ubicación es la accesibilidad y disponibilidad de infraestructuras de transporte, en este caso carreteras principales. Teniendo en cuenta que el centro de distribución se ubicaría en algún polígono industrial a las afueras de la ciudad, tanto Reading como Swindon estaría muy bien conectadas, ya que por ambas pasa la Autopista M4, una de las más transitadas. Por Swindon también pasa la A419 y la A420 a Oxford, lo que hace que se le asigne una puntuación de 5 frente a los 4 de Reading. Cerca de Newbury también pasa la autopista M4, por lo que se le asignan 3 puntos. 2 puntos tendría Andover, la peor ubicada en este sentido. Figura 4.5. Principales carreteras y autopistas de South West England 31 31 Optimización de transportes de reparables en el sector aeronáutico A continuación, se muestra la matriz de decisión con las puntuaciones asignadas para cada criterio: Reading Swindon Newbury Andover Disponibilidad de suelo industrial 5 4 2 2 Distancia media a los centros reparadores 3 1 5 2 Precio de suelo industrial 3 4 4 4 Proximidad a red de carreteras 4 5 3 2 15 14 14 10 Tabla 4.5. Matriz de Decisión Podemos observar que la ciudad que mayor puntuación ha obtenido es Reading, por lo que se toma la decisión de ubicar el centro de distribución en este lugar. Aunque las ciudades eran cercanas y las características similares para algunas de ellas, utilizar este tipo de herramientas para la toma de decisiones puede ser muy útil en problemas más complejos en los que el hecho de tomar una decisión u otra tenga un alto impacto en el resultado final. Figura 4.6. Ubicación gráfica del centro de distribución tras evaluar las opciones mediante el método de la matriz de decisión Ubicación del Centro de Distribución 32 33 33 Optimización de transportes de reparables en el sector aeronáutico 5 PROBLEMA DE RUTADO DE VEHÍCULOS En este capítulo se introducirá el problema de rutado de vehículos, describiendo matemáticamente el problema, sus elementos y principales características, así como su contexto histórico y estado del arte. Posteriormente, y una vez descrito el problema y objetivo a alcanzar, se presentarán algunos algoritmos que hagan posible su resolución y se diseñará un algoritmo para ello. 5.1 Introducción y Estado del Arte Los problemas de resolución de rutas son unos de los problemas de optimización combinatoria más estudiados. Estos problemas tratan de resolver el diseño óptimo de rutas que debe hacer un vehículo o una flota de vehículos para satisfacer la demanda de una serie de clientes ubicados en diferentes puntos del plano, sujeto a determinadas restricciones. Dentro de los problemas de rutado, podemos diferenciar según el lugar donde se produce la demanda (u oferta), ya sea en los nodos de la red o en los arcos. En los problemas en los que la demanda se produce en los arcos la tarea implica que los vehículos deben cubrir la totalidad o una parte de las conexiones entre los nodos de un grafo, es decir, todas o un número determinado de las aristas deben ser recorridas. Un ejemplo de este tipo de problemas es el Problema del Cartero Chino (CPP, del inglés Chinese Postman Problem), en el que un cartero debe recorrer un circuito que abarca todas las calles de un área determinada de la ciudad. El cartero debe repartir el correo de manera eficiente, minimizando la distancia total recorrida. Este problema es considerado técnicamente resuelto, lo que significa que existe un algoritmo capaz de encontrar una solución óptima en un tiempo razonable, lo que nos permite resolver problemas CPP de gran envergadura en pocos segundos utilizando una computadora moderna. Si extendemos esta idea a situaciones que involucran a múltiples vehículos, obtenemos lo que se conoce como Problema de Enrutamiento de Arcos Capacitados (CARP), en el que los vehículos deben recorrer circuitos que contienen conexiones que ya han sido atendidas por otro vehículo. Por otra parte, los Problemas de Vértices son aquellos en los que la demanda se produce en los nodos de la red, debiendo el vehículo o vehículos visitar a estos clientes recorriendo la menor distancia total posible. Un ejemplo de este problema es el TSP (Traveling Salesman Problem o Problema del Viajante). En él, la cantidad de combinaciones es tan alta que para resolver un problema con 100 nodos se necesitarían años usando una computadora actual, ya que el número de soluciones posibles es del orden de 10157. Este número de soluciones aumenta considerablemente si ahora tratamos de resolver la red de 50 nodos considerando un problema VRP (Vehicle Routing Problem), en el cual la demanda total requiere de más de un vehículo y por lo tanto es necesario dividir el conjunto de nodos cliente para que su demanda sea atendida por cada vehículo y posteriormente resolver un TSP con cada vehículo. Problema de Rutado de Vehículos 34 Figura 5.1. Representación gráfica de los problemas a) TSP y b) VRP Para hacer frente a este número tan alto de posibles combinaciones, se hace uso de diferentes algoritmos, ya sean mediante técnicas de programación matemática, algoritmos heurísticos y algoritmos metaheurísticos. Estos mecanismos se analizarán más en profundidad en la sección 5.3. 5.1.1 Contexto Histórico Desde que el problema de rutado de vehículos fuese inicialmente propuesto por Flood en 1956, multitud de autores han tratado de buscar soluciones óptimas o sub-óptimas a este problema o sus variantes mediante diferentes algoritmos que lo hiciesen computacionalmente viable. De la formulación del problema inicialmente propuesta por Flood nacen variantes como la Dantzig y Ramser en The Truck Dispatching Problem en 1959, en el que proponen un TSP generalizado en el que una serie de camiones-tanque de gasolina deben surtir a un número determinado de estaciones de servicio, pasando una sola vez por cada una de ellas. Considerando este problema como un TSP, es decir, contando solo con un vehículo para satisfacer la demanda, y asumiendo que cada par de nodos está conectado por un arco transitable, el número total de rutas diferentes para dicha red viene definido por: 𝑁 =1 2𝑛! (5.1) siendo n el número de nodos. Para evaluar la complejidad de este tipo de problemas, Lenstra y Rinnooy Kan (1981) llevaron a cabo un análisis de la dificultad del problema de enrutamiento de vehículos y llegaron a la conclusión de que prácticamente todos los problemas de enrutamiento de vehículos son NP-complejos, incluido el problema TSP, ya que no se resuelven en tiempo polinómico. 35 35 Optimización de transportes de reparables en el sector aeronáutico Figura 5.2. Número de soluciones posibles del problema TSP según el número de nodos de la red (escala logarítmica) La primera referencia al TSP múltiple o m-TSP en el cual se tiene un almacén central y m vehículos aparece en 1960 con Miller, Tucker y Zemlin. Este problema toma el nombre de VRP y a partir de él aparece el PTSP en 1969 a partir del trabajo de Tillman. El propósito de este problema consiste en determinar el costo mínimo esperado de desplazamiento a través de un grupo de nodos en los cuales hay probabilidades relacionadas con la presencia o ausencia de consumidores que necesitan atención. En cuanto a las variantes de los problemas TSP y VRP, de acuerdo con Solomon y Desrosiers (1988), el problema de enrutamiento de vehículos con ventanas de tiempo (VRPTW) también es NP-comlejo debido a que es una extensión del VRP. También lo es el problema de enrutamiento de vehículos con entregas estocásticas (VRPSD) aun representando una simplificación del VRP (Dror y Trudeau, 1990; Archetti et al., 2005). Por lo tanto, cualquier combinación de los anteriores, como el VRPTWSD, es también NP-complejo, lo que respalda la aplicación de heurísticas y metaheurísticas para resolver el problema. 5.1.2 Tipos de VRP En secciones anteriores se ha descrito el problema del Traveling Salesman (TSP) y su generalización al VRP, así como su evolución y contexto histórico. A continuación, se presentan las diferentes variantes del problema, según se modifiquen los diferentes requerimientos logísticos. Para entender mejor cómo estos requerimientos afectan al tipo de problema, se presentan los diferentes elementos que intervienen en un problema VRP:  Depósito (centro de distribución): La mercancía a repartir se suele ubicar inicialmente en un almacén central o depósito. De esta manera, los vehículos de cada ruta deben tener también inicio (y generalmente final) también en este mismo depósito u otro. Si se plantea un problema con múltiples depósitos, se debe definir si estos tienen una capacidad máxima (que puede ser diferente en cada uno), si cada uno tiene asignada una flota asignada o incluso definir unas ventanas temporales.  Clientes/proveedores (centros reparadores): Los clientes juegan el papel de generadores de la demanda en este tipo de problemas. La demanda puede ser entendida como un producto que debe transportarse y que, por tanto, ocupa un volumen determinado en un vehículo, o como un servicio que la empresa debe realizar y por lo tanto ocupa un cierto espacio de tiempo en el cual el vehículo se encuentra inmovilizado. Problema de Rutado de Vehículos 36 Como en el caso anterior, existen numerosas variantes del problema, en las cuales, por ejemplo, la demanda pueda ser satisfecha por más de un vehículo diferente o que ciertos materiales a ser entregados no estén inicialmente en el depósito y por lo tanto sea necesario visitar a un proveedor previamente (se establece una restricción en el orden de la ruta). Al igual que con los centros de distribución, los nodos cliente pueden tener definidas unas ventanas temporales, pueden tener una capacidad máxima de carga/descarga o deban ser visitados por un vehículo en particular.  Red de transporte: Se entiende la red de transporte como el grafo en el que los nodos son los clientes y depósitos y los arcos las vías de conexión entre ellos. Estos últimos pueden ser dirigidos o no (dependiendo de si se permite el transporte en un sentido o en ambos) y puede o no existir conexión entre todos los nodos. A cada arco se le asocia un coste que generalmente suele ser función de la distancia espacial entre nodos o el tiempo que el vehículo tarda en recorrerlo.  Flota de vehículos: Son el conjunto de agentes de transporte que forman parte de la red, es decir, definen el número máximo de rutas solución para el VRP. En general se asume que un vehículo, durante el período planificado, solo realizará una ruta, pero existen variantes del problema en las que el mismo vehículo puede participar en más de una ruta, por lo que el número máximo de rutas solución ya no sería igual al tamaño de la flota. Los vehículos suelen tener una capacidad volumétrica o de peso máxima, que puede ser común para todos los vehículos (flota homogénea) o diferentes para cada uno (flota heterogénea). En cuanto al coste, además del asociado a cada arco recogido, puede existir un fijo por vehículo que dependerá de si es utilizado o no.  Ruta o rutas solución: El objetivo de este tipo de problemas es determinar la ruta a llevar a cabo por cada uno de los vehículos de la flota, cumpliendo con las restricciones previamente descritas y asegurando que se satisface la demanda. Se denomina ruta o rutas solución a aquellas que cumplen con esto. Una vez definidos los elementos principales del problema, se describen algunas de las variantes más conocidas y sus principales características: 5.1.2.1 Problema VRP con restricciones de capacidad: CVRP Introducido por Ralphs, Hartman y Galati en 2001, el problema CVRP (Capacited VRP) es una variante en la cual los vehículos tienen una capacidad máxima determinada y constante. Conociéndose la demanda de los clientes, el objetivo es hallar las rutas óptimas (menor coste de transporte) asegurando que la demanda se cumple y que, a la vez, se usa el menor número de vehículos posible teniendo en cuenta su capacidad. 5.1.2.2 Problema VRP con restricciones de distancia: DVRP Toth y Vigo introdujeron en 2002 una variante del CVRP en un VRP con restricciones de distancia (DVRP). En este problema, a diferencia del CVRP previamente descrito, la restricción es de distancia (o tiempo) en vez de capacidad y la suma de la longitud de los arcos no puede exceder la máxima longitud de la ruta. 37 37 Optimización de transportes de reparables en el sector aeronáutico Si se combina la restricción tanto en la capacidad del vehículo como de distancia máxima o tiempo máximo, el problema se convierte en una combinación del CVRP y DVRP, llamada DCVRP. 5.1.2.3 Problema VRP con ventanas temporales: VRPTW El problema VPRTW (VRP with Time Windows), introducido por Cordone & Calvo en 2001, añade al VRP clásico la restricción de cumplir una ventana temporal en el que cada cliente debe ser atendido. De la misma manera, el depósito o centro de distribución también cuenta con una ventana temporal de la forma [ei,li]. El vehículo debe atender al cliente i en un instante de tiempo anterior a li y posterior a ei, ya que fuera de este intervalo sus instalaciones estarán cerradas. En realidad es posible llegar antes del instante ei,⁡pero⁡en⁡este⁡ caso⁡el vehículo deberá esperar hasta que se alcance dicho instante para comenzar el servicio (incurriendo en costes de paralización añadidos al hecho de no estar atendiendo a otro cliente en ese intervalo de tiempo). En general, este problema también incorpora la restricción de capacidad para la flota de vehículos, como en el CVRP. 5.1.2.4 Problema VRP con múltiples depósitos: MDVRP Este problema fue introducido por Hjorring en 1995 y debe su nombre a las siglas en inglés de Multiple Depot VRP. En este caso el número de depósitos es mayor que 1 y, al igual que en los casos anteriores, el objetivo es minimizar el número de vehículos a utilizar y la distancia recorrida por estos. Podría pensarse que este problema no es más que el conjunto de varios VRP a la vez, sin embargo, en este problema no se asigna inicialmente cada cliente a un depósito en concreto, sino que todos los depósitos pueden satisfacer la demanda de todos los clientes. Es por ello que el primer paso de la resolución del problema debe ser asignar cada cliente a un depósito para posteriormente definir la ruta de cada uno de los vehículos asociados al depósito en cuestión. 5.1.2.5 Problema VRP con entregas y devoluciones: VRPPD Introducido por Righini en 2000, en el problema VRPPD (VRP with Pickup and Delivery) existe la posibilidad de que un cliente que ya haya sido servido necesite que se le recoja mercancía. En este problema hay que tener en cuenta que la carga del vehículo no va a ser estrictamente decreciente (si cumple con la restricción de espacio a la salida del depósito la cumplirá siempre), sino que esta puede ir variando a medida que los clientes van introduciendo o sacando mercancía. Se supone que los clientes no pueden intercambiar mercancía, es decir, la mercancía empieza o acaba siempre en el depósito. 5.1.2.6 Problema VRP con viajes de regreso: VRPB El VRPB (VRP with Backhauls), introducido en 1992 por Jacobs-Blecha y Goetschalckx, es una variante del VRP en el que los nodos pueden ser servidos (clientes) o deben entregar mercancía (proveedores). Puede entenderse como una modificación del VRPPD en el que los clientes se dividen en dos grupos (los que tienen demanda y los que tienen oferta) y las devoluciones tienen lugar una vez se ha entregado toda la mercancía. Para que la solución sea factible se requiere que la capacidad de los vehículos no sea excedida en ningún punto Problema de Rutado de Vehículos 38 de la ruta y que cada cliente sea visitado por una sola ruta. 5.1.2.7 Problema VRP con entregas parciales: SDVRP El problema SDVRP (Split Delivery VRP), introducido por Dror, Laporte y Trudeau en 1994, es una variante del algoritmo VRP en que está permitido que un cliente sea servido por más de un vehículo. Este planteamiento resuelve el problema de que un cliente tenga una demanda tan alta que la capacidad de un vehículo no sea capaz de satisfacer. De esta manera, la solución óptima será aquella en la que el número de vehículos usados y la distancia recorrida o tiempo de transporte sea mínimo, independientemente del número de visitas a cada cliente. 5.1.2.8 Problema VRP con variables estocásticas: SVRP Introducido por Stewart y Golden, 1983, el SVRP (Stochastic VRP) es un problema VRP en el que una o varias variables del mismo (número de clientes, demanda, tiempo de servicios, etc.) son aleatorios. Para su resolución, se lleva a cabo una primera etapa en la cual se determina la solución antes de conocer el valor de las variables, para posteriormente llevar a cabo una corrección de la solución una vez conocidos los valores estocásticos. En función de la variable que sea aleatoria, existen las siguientes variantes:  Clientes estocásticos (SVRP-SN, Jaillet, 1985): cada cliente tiene una probabilidad p de estar presente y una probabilidad (1p) de encontrase ausente.  Demandas estocásticas (VRPUD, Laporte y Louveaux, 1987): la demanda de cada cliente es un una variable aleatoria.  Tiempos estocásticos (VRPSTT, Laporte, Louveaux y Mercure, 1992): los tiempos de transporte y los tiempos de servicio son variables aleatorias 5.1.2.9 Problema VRP periódico VRP: PVRP A diferencia del VRP clásico, el PVRP (Periodic VRP), introducido por Baptista, Oliveira y Zúquete en 2002, extiende su planificación a n días. Para que la ruta solución sea factible, además de cumplirse las restricciones del problema, se debe visitar a cada cliente al menos una vez y no es necesario que los vehículos vuelvan al depósito en el mismo día que salieron, sino que tienen opción de volver hasta el día n. 5.1.2.10 Problema VRP con instalaciones satélites: VRPSF El VRPSF (VRP with Satellite Facilities) es la variante del VRP en el que se permite el reabastecimiento de los vehículos sin necesidad de que vuelvan al depósito. Introducido por Bard en 1997, en este problema se asume que se dispone de instalaciones satélites donde los vehículos pueden reponer su carga y continuar con las entregas hasta el final de su turno sin necesidad de volver al depósito inicial. A diferencia del MDVRP, aquí cada vehículo no está asociado a un solo punto de carga, sino que puede ir abasteciéndose a lo largo del camino, lo que permite hallar soluciones con rutas más largas. 39 39 Optimización de transportes de reparables en el sector aeronáutico 5.2 Algoritmos de resolución Una vez conocidos y desarrollados los problemas TSP y VRP, así como sus tipos y variantes, en esa sección se expondrán los diferentes métodos de resolución del problema. Estos métodos se pueden dividir, según la clase de algoritmo que se emplee para su resolución, en tres grandes grupos: exactos, heurísticos y metaheurísticos. Figura 5.3. Taxonomía de los métodos de resolución de problemas VRP según la clase algoritmo 5.2.1 Métodos Exactos Se denomina método exacto a aquel que busca todas las soluciones posibles hasta encontrar la óptima, partiendo de un modelo de programación lineal, entera, cuadrática, etc., y haciendo uso de algoritmos de acotamiento (Lüer, Benavente, Bustos, & Venegas, 2009). Estos métodos ofrecen unos tiempos computacionales aceptables para problemas con menos de 50 depósitos, ya que por encima de este número, aunque se consiga hallar la solución óptima, el tiempo que tendríamos que emplear en dar con ella lo haría totalmente ineficiente. Cabe recordar la expresión (5.1) que establece el número de posibles combinaciones según el número de depósitos. Dentro de los métodos exactos, estos se pueden dividir en tres diferentes grupos:  Métodos de búsqueda directa de árbol: La búsqueda de la solución óptima se realiza sobre todos los nodos de un árbol de acuerdo a los criterios específicos de cada método. Algunos de los métodos más conocidos son: o Asignación de cota inferior (Laporte, Mercure y Nobert, 1986): este algoritmo asigna una cota inferior que permite disminuir el número de vehículos requeridos para visitar todos los vértices, proporcionando una cota superior para el número de vehículos y transformándolo en un problema TSP. o Algoritmo de ramificación y acotamiento o poda (Litle, Murty, Sweeney y Karel, 1968): en este caso, se recorre cada nodo del árbol desde el nivel superior hasta el inferior, obteniéndose un conjunto de soluciones de sub-problemas que luego se optimizan de manera independiente para determinar qué nodos pueden eliminarse. Un nodo (junto con sus Problema de Rutado de Vehículos 46 Problem with Pickup and Delivery). Como se explicó previamente, en este problema los nodos pueden ser a la vez demandantes de oferta y demanda, como es el caso observando los datos de la Tabla 4.1. Esta es la principal diferencia con el problema VRP con viajes de regreso (VRPB), y hace que sea más complejo ya que la capacidad del vehículo va fluctuando en función de la demanda de cada servicio. A continuación, se describe matemáticamente el problema VRPPD. 5.3.2 Modelado Matemático En el problema a modelar, se tienen en cuenta N nodos numerados de 0 a n, donde 0 es el centro de distribución y el resto de nodos son los nodos cliente. Así mismo, cada cliente i tiene asociada una demanda de entrega Ei y una demanda de recogida Ri que debe ser satisfecha por una flota de vehículos Q. Los principales parámetros que intervienen en el problema son, de esta forma:  Ni: Nodo i de la red de transporte  Ei: Demanda de entrega en el cliente i  Ri: Demanda de recogida en el cliente i  dij: Distancia recorrida entre los nodos i y j  Cq: Coste del kilómetro recorrido por el vehículo q  Qq: Capacidad del vehículo q Por otra parte, se presentan las siguientes variables de decisión del problema:  𝑋𝑖𝑗𝑘 ={1⁡si⁡el⁡vehículo⁡𝑞⁡recorre⁡el⁡arco⁡(𝑖,𝑗) 0⁡en⁡caso⁡contrario  𝑌𝑞={1⁡si⁡se⁡asigna⁡un⁡vehículo 0⁡en⁡caso⁡contrario  Lqi: volumen transportado por el vehículo q al viajar en un nodo i La función objetivo, aquella que debe ser minimizada para encontrar la solución óptima del problema, calcula el coste total asociado a la recogida y entrega teniendo en cuenta la distancia recorrida por cada uno de los vehículos de la flota y tiene esta forma: min𝐹𝑂 = ∑∑∑𝑋𝑖𝑗𝑞𝑑𝑖𝑗𝐶𝑞 𝑗∈𝑁𝑖∈𝑁𝑞∈𝑄 (5.1) A continuación, se presentan las diferentes restricciones a las que está sujeto el modelo:  Cada cliente i debe ser visitado por un y solo un vehículo q: 47 47 Optimización de transportes de reparables en el sector aeronáutico ∑∑𝑋𝑖𝑗𝑞 =1;⁡⁡∀𝑗 ∈𝑁 𝑖∈𝑁𝑞∈𝑄 (5.2)  Todos los vehículos deben comenzar y terminar su ruta siempre en el centro de distribución (nodo 0): ∑𝑋𝑖𝑗𝑞 =𝑌𝑞 𝑖∈𝑁 ;⁡⁡∀𝑗 ∈𝑁;⁡∀𝑞 ∈ 𝑄 (5.3) ∑𝑋𝑖𝑗𝑞 =𝑌𝑞 𝑗∈𝑁 ;⁡⁡∀𝑖 ∈ 𝑁;⁡∀𝑞 ∈𝑄 (5.4)  Restricción de capacidad del vehículo q: 𝐿𝑞𝑖 −𝐿𝑞𝑖 +𝑅𝑗−𝐸𝐽≤(1−𝑋𝑖𝑗)𝑄𝑞;⁡⁡∀𝑖 ∈ 𝑁;⁡∀𝑗 ∈𝑁;⁡∀𝑞 ∈𝑄 (5.5)  Restricción de capacidad de vehículo q cuando sale del centro de distribución: 𝐿𝑞0 ≤𝑄𝑞𝑌𝑞;⁡⁡∀𝑞 ∈ 𝑄 (5.6)  Restricción para establecer flujo en el modelo: ∑𝑋𝑖𝑗𝑞 −∑𝑋𝑗𝑖𝑞 =0 𝑖∈𝑁𝑖∈𝑁 ;⁡⁡∀𝑗 ∈𝑁;⁡∀𝑞 ∈ 𝑄 (5.7) 5.3.3 Resolución El algoritmo diseñado servirá al operador logístico para diseñar la ruta óptima cada vez que reciba mercancías en el centro de distribución. En este trabajo, y para evaluar la bondad de la solución propuesta, se utilizarán unos datos de demanda de recogida y entrega basados en el promedio semanal, redondeando al alza a enteros tanto el número de recogidas como de entregas. Este será uno de los peores casos de estudio, ya que lo habitual es que haya algunos centros reparadores que no tengan que ser visitados en alguna ruta en particular, lo que nos permitirá dimensionar la flota en exceso para tener siempre disponibilidad de la misma y evitar dejar algún TR sin entregar. Los datos de demanda por cliente del ejemplo a resolver se muestran en la Tabla 5.1. Problema de Rutado de Vehículos 48 Ciudad Número de TRs a entregar Nº de TRs a recoger Total ISLE OF WIGHT 2 2 4 WIMBORNE 2 2 4 SOUTHEND-ON-SEA 2 1 3 OXFORDSHIRE 1 0 1 GLOUCESTER 4 1 5 BRISTOL 2 2 4 COVENTRY 3 1 4 CRAWLEY 2 1 3 WOLVERHAMPTON 2 1 3 BRIDPORT 1 1 2 LONDON 1 1 2 POOLE 1 1 2 HEREFORD 2 1 3 MARLOW 2 1 3 LUTON 1 1 2 TITCHFIELD 1 1 2 PORTSMOUTH 2 1 3 ESSEX 1 1 2 WATERHEAD 2 1 3 YEOVIL 2 1 3 REDDITCH 1 1 2 LEIGHTON BUZZARD 1 1 2 WEST SUSSEX 1 1 2 VERWOOD, DORSET 3 3 6 CHELTENHAM 1 1 2 HANFORTH 1 2 3 MARSTON 1 1 2 BLACKPOOL 1 0 1 SUSSEX 2 0 2 BASILDON, ESSEX 2 0 2 CORNWALL 2 1 3 CHRISTCHURCH 1 1 2 FAREHAM-HAMPHIRE 2 1 3 SOUTHALL 2 1 3 TOTAL 57 36 93 Tabla 5.1. Valores de demanda de recogidas y entregas para el ejemplo a resolver Para resolver el problema, utilizaremos dos algoritmos que se basan en la metaheurística: el algoritmo de pétalos, que nos dará una buena aproximación inicial ya que previamente hemos diseñado el centro de distribución (o CEDI) en el punto central que minimiza la distancia total recorrida, y posteriormente un algoritmo de mejora basado en la metaheurística del vecino más cercano. Con este algoritmo, conseguiremos mejorar la solución obtenida previamente intercambiando nodos vecinos en busca de una distancia total recorrida menor. 49 49 Optimización de transportes de reparables en el sector aeronáutico 5.3.3.1 Algoritmo de Barrido El principio fundamental de este algoritmo está basado la observación de que en muchos problemas de rutado de vehículos, las rutas óptimas presentan una estructura lobulada o casi lobulada (Foster y Bryan, 1976). Basándose en el método de barrido introducido por Gillet y Miller en 1974, en este algoritmo se va recorriendo el plano mediante una semirrecta que va girando e incorporando nodos a la ruta, hasta que el vehículo se llena o se alcanza alguna restricción adicional. Para que este algoritmo sea eficiente, es necesario que los nodos cliente (centros reparadores) se sitúen en un sector geográfico centrado en el centro de distribución. Para ello, vamos a cambiar el sistema de referencia y vamos a ubicar el centro de distribución en el punto (0,0). Una vez centrado, vamos a calcular la ubicación relativa de cada nodo lo vamos a ubicar en el plano. De esta forma, obtenemos la siguiente distribución sobre el sistema de referencia: Figura 5.5. Ubicación gráfica de los nodos cliente en un sistema de referencia centrado en el CEDI Una vez colocados todos los nodos en el nuevo sistema de referencia, vamos a cambiar a coordenadas polares para facilitar el recorrido de la semirrecta. Para ello, utilizaremos las siguientes expresiones básicas: 𝑟=√𝑋2+𝑌2 (5.8) 𝜃 =𝑎𝑡𝑔(𝑌 𝑋) (5.9) Una vez convertidas todas las coordenadas de los nodos a polares, procedemos a ordenarlas en orden creciente según θ. De esta forma estaremos barriendo el espacio tal como se necesita en el algoritmo y estaríamos preparados para empezar a asignar nodos a cada ruta. Si se tratase de un problema TSP en el que no se tuviese límite superior en la distancia recorrida, el resultado de aplicar el algoritmo de barrido a nuestra red sería la que se muestra en la Figura 5.6. Problema de Rutado de Vehículos 50 Figura 5.6. Resultado de aplicar el algoritmo de barrido sobre la red completa En la Tabla 5.2 se muestra la numeración de los nodos (de menor a mayor ángulo, asumiendo que el centro de distribución es siempre el nodo 0) así como la conversión a coordenadas relativas y posteriormente a coordenadas polares. Una vez adaptados nuestros datos ya estamos preparados para diseñar el algoritmo de barrido teniendo en cuenta las demandas de entregas y recogidas. El proceso es simple y se basa en un procedimiento iterativo que va recorriendo cada uno de los nodos verificando que la capacidad del vehículo no se exceda ni que tampoco se vacíe por completo. En este punto, tenemos que tener en cuenta la Hipótesis 6, ya que la condición de que el vehículo se vacíe debe diferenciar entre materiales recogidos y materiales a entregar. De esta forma, las condiciones deben ser:  El vehículo debe volver al CEDI si, recogiendo todo el material reparado disponible en el siguiente nodo, la capacidad excedería el máximo permitido (en este caso 10).  El vehículo debe volver al CEDI una vez ha entregado todos los materiales reparables cargados en el CEDI, independientemente del espacio disponible. Solo habrá una excepción, que será cuando en el siguiente nodo a visitar solo exista demanda de recogida, y no de entrega.  Se supone que el vehículo siempre parte del centro de distribución cargado con la máxima carga posible (10 cajas). Sin embargo, se ha añadido una primera evaluación en la cual se comprueba si en el primer nodo la demanda de recogida supera a la demanda de entrega. Si esto es así, el vehículo sale con la cantidad máxima de cajas que le permita recoger todo el material reparado disponible en el primer nodo, para evitar que nunca se pueda iniciar una ruta. La lógica del algoritmo programado se representa en el diagrama de la Figura 5.7 51 51 Optimización de transportes de reparables en el sector aeronáutico Cartesianas Cartesianas relativas Polares n Ciudad x y X Y r (km) theta (deg) 0 READING 5712,06 -107,67 0 0 0 0 1 LEIGHTON BUZZARD 5763,12 -73,26 51,06 34,41 61,57 33,98 2 LUTON 5758,68 -46,62 46,62 61,05 76,81 52,63 3 MARLOW 5724,27 -86,58 12,21 21,09 24,37 59,93 4 ESSEX 5746,47 51,06 34,41 158,73 162,42 77,77 5 WIMBORNE 5720,94 -23,31 8,88 84,36 84,83 83,99 6 SOUTHALL 5717,61 -42,18 5,55 65,49 65,72 85,16 7 BASILDON, ESSEX 5724,27 49,95 12,21 157,62 158,09 85,57 8 LONDON 5717,61 -14,43 5,55 93,24 93,41 86,59 9 SOUTHEND-ON-SEA 5720,94 78,81 8,88 186,48 186,69 87,27 10 CRAWLEY 5673,21 -19,98 -38,85 87,69 95,91 113,90 11 SUSSEX 5654,34 -6,66 -57,72 101,01 116,34 119,74 12 WEST SUSSEX 5654,34 -58,83 -57,72 48,84 75,61 139,76 13 PORTSMOUTH 5638,8 -119,88 -73,26 -12,21 74,27 189,46 14 FAREHAM-HAMPHIRE 5644,35 -130,98 -67,71 -23,31 71,61 199,00 15 TITCHFIELD 5644,35 -137,64 -67,71 -29,97 74,05 203,88 16 ISLE OF WIGHT 5624,37 -147,63 -87,69 -39,96 96,37 204,50 17 CHRISTCHURCH 5632,14 -197,58 -79,92 -89,91 120,30 228,37 18 POOLE 5632,14 -216,45 -79,92 -108,78 134,98 233,70 19 VERWOOD, DORSET 5646,57 -207,57 -65,49 -99,9 119,45 236,75 20 BRIDPORT 5631,03 -306,36 -81,03 -198,69 214,58 247,81 21 YEOVIL 5654,34 -291,93 -57,72 -184,26 193,09 252,61 22 CORNWALL 5596,62 -527,25 -115,44 -419,58 435,17 254,62 23 BRISTOL 5712,06 -288,6 0,001 -180,93 180,93 270,00 24 GLOUCESTER 5757,57 -249,75 45,51 -142,08 149,19 287,76 25 HEREFORD 5778,66 -301,92 66,6 -194,25 205,35 288,92 26 CHELTENHAM 5760,9 -229,77 48,84 -122,1 131,51 291,80 27 REDDITCH 5806,41 -215,34 94,35 -107,67 143,16 311,23 28 WOLVERHAMPTON 5836,38 -236,43 124,32 -128,76 178,98 313,99 29 BLACKPOOL 5974,02 -339,66 261,96 -231,99 349,92 318,47 30 MARSTON 5912,97 -276,39 200,91 -168,72 262,36 319,98 31 OXFORDSHIRE 5753,13 -138,75 41,07 -31,08 51,50 322,88 32 HANFORTH 5921,85 -246,42 209,79 -138,75 251,52 326,52 33 COVENTRY 5817,51 -167,61 105,45 -59,94 121,30 330,39 34 WATERHEAD 5944,05 -229,77 231,99 -122,1 262,16 332,24 0 READING2 5712,06 -107,67 0 0 0 0 Tabla 5.2. Nodos ordenados según el ángulo y sus correspondientes coordenadas relativas Problema de Rutado de Vehículos 52 Figura 5.7. Diagrama de flujo del Algoritmo de Barrido Tras aplicar el algoritmo descrito sobre el problema-ejemplo, obtenemos que la red puede ser recorrida y la demanda satisfecha por seis vehículos, formando las rutas en forma de pétalos de la Figura 5.8. Figura 5.8. Solución del problema propuesto mediante el Algoritmo de Barrido 53 53 Optimización de transportes de reparables en el sector aeronáutico Mediante esta disposición, la flota de vehículos ha conseguido llevar a cabo las 57 entregas y 36 recogidas solicitadas. Podemos calcular la distancia recorrida por cada vehículo sumando la distancia entre cada uno de los nodos que es visitado en cada ruta. Para ello, primero debemos calcular una matriz de distancias entre todas las combinaciones de nodos, que se muestra en el Anexo I. Estas distancias están calculadas mediante la expresión (4.7) y con los datos de la Tabla 5.2. Los resultados obtenidos se muestran en la siguiente tabla: Ruta Nodos Entregas Recogidas km recorridos Ruta 1 0 1 2 3 4 5 6 0 9 7 444,25 Ruta 2 0 7 8 9 10 11 12 0 10 4 576,71 Ruta 3 0 13 14 15 16 17 18 0 9 7 320,08 Ruta 4 0 19 20 21 22 23 0 10 8 935,20 Ruta 5 0 24 25 26 27 28 0 10 5 543,14 Ruta 6 0 29 30 31 32 33 34 0 9 5 1382,82 Total 57 36 4202,21 Tabla 5.3. Resultados del problema propuesto mediante el Algoritmo de Barrido 5.3.3.2 Algoritmo de mejora mediante la heurística del vecino más cercano Como se puede observar a simple vista si miramos la Figura 5.8, la solución hallada mediante el algoritmo de barrido es una solución factible pero no óptima. El ejemplo más claro se puede ver en la Ruta 6, que cuenta con dos nodos cercanos al centro de distribución y el resto más alejado. Si se va recorriendo en el sentido horario de las agujas del reloj, se visitarán de manera alterna nodos cercanos y lejanos al centro de distribución, haciendo totalmente ineficiente el recorrido propuesto. Para ello, se propone un algoritmo de mejora que se basa en la heurística del vecino más cercano (Rosenkrantz, Stearns y Lewis, 1977). Mediante este algoritmo, se trata de construir un ciclo Hamiltoniano (ruta sin vértices repetidos que recorre todos los vértices del grafo) que se basa en desplazarse al nodo o vértice más cercano al actual, es decir, tomando la arista de menor coste. Aunque mejora los resultados del algoritmo de barrido ya que minimiza la distancia entre nodos, esta heurística es “miope”, ya que en cada iteración solo tiene en cuenta la siguiente elección disponible, de manera que tomar la mejor opción disponible para la iteración actual puede obligarle a tomar malas decisiones más adelante. De esta forma, recorrerá aristas de bajo coste al principio pero al final quedarán vértices cuya conexión sea de alto coste. En este problema, al ser relativamente sencillo debido al bajo número de nodos por ruta, esta heurística puede mejorar considerablemente el resultado obtenido anteriormente y además tiene un bajo coste computacional, por lo que se programa el algoritmo siguiendo la lógica representada en el diagrama de la Figura 5.9. Problema de Rutado de Vehículos 54 Figura 5.9. Diagrama de flujo de la heurística del vecino más cercano Aunque en el diagrama de flujo se simplifica el proceso, es necesario contar con una matriz de visita cuyos elementos valgan 1 cuando un nodo ha sido visitado y 0 cuando no. De esta manera, el vehículo no se dirigirá a un nodo ya visitado aunque sea el de menor distancia. Por otra parte, también será necesario imponer que el vehículo debe volver al nodo 0 una vez termine de recorrer el resto (el algoritmo debe ser general para n nodos ya que cada ruta puede tener un número diferente de paradas). Tomando como punto de partida las rutas que hemos obtenido de aplicar el algoritmo de barrido de la Tabla 5.3, y aplicando la heurística explicada, obtenemos los siguientes resultados: Ruta Nodos Entregas Recogidas km recorridos Ruta 1 0 3 1 2 6 5 4 0 9 7 393,96 Ruta 2 0 12 10 11 8 7 9 0 10 4 486,11 Ruta 3 0 14 15 13 16 17 18 0 9 7 332,56 Ruta 4 0 19 21 20 23 22 0 10 8 1014,81 Ruta 5 0 26 24 25 28 27 0 10 5 475,14 Ruta 6 0 31 33 32 34 30 29 0 9 5 774,44 Total 57 36 3477,02 Tabla 5.4. Resultados del problema propuesto mediante el Algoritmo de mejora basado en Heurística del Vecino más Cercano 55 55 Optimización de transportes de reparables en el sector aeronáutico Comparando los resultados con los anteriores, podemos observar que se ha mejorado el coste total del conjunto de rutas en 725,19. Sin embargo, tal como habíamos predicho, en algunas rutas el resultado de aplicar este algoritmo “ciego” puede haber empeorado ligeramente los resultados iniciales, como ha ocurrido con las rutas 3 y 4. Figura 5.10. Solución del problema propuesto mediante el Algoritmo de mejora basado en Heurística del Vecino más Cercano Para ilustrar este empeoramiento de los resultados, vamos a analizar un ejemplo. Si miramos la Ruta 4, podemos observar como, tras visitar el nodo 20 (el tercero de esta ruta), el algoritmo debe decidir si ir al nodo 23 (el más cercano) o al nodo 22 (más lejano). Según la heurística del vecino más cercano, el nodo a visitar debe ser el 23 ya que es el que se encuentra a menor distancia (83 km vs 223,6 km). Sin embargo, esto le obliga a que deba terminar la ruta recorriendo las aristas 23-22 (265,1 km) y 22-0 (435,1 km). En cambio, si hubiese elegido ir hacia el nodo 22, aunque en el momento hubiese recorrido 140,6 km más, las aristas que tendría que recorrer luego serían la 22-23 (265,1 km) y la 23-0 (180,9 km). Se muestra así que esta heurística realiza mejoras locales pero en ciertos casos puede empeorar la solución global. Figura 5.11. Ejemplo de decisión según la Heurística del Vecino más Cercano Problema de Rutado de Vehículos 62 En cualquier caso, para tomar el mejor resultado tomaremos, para cada ruta, la que menor distancia haya recorrido. De esta forma, aunque algún algoritmo empeore alguna de los rutas, siempre nos quedaremos con la mejor ya que puede haber configuraciones iniciales que se resuelvan mejor por un método o por otro. En la siguiente tabla se muestran los tiempos de ejecución de cada uno de los algoritmos: Algoritmo Tiempo de ejecución (seg) Algoritmo de barrido 0,016 Heurística de vecino más cercano 0,086 Búsqueda local (nodos adyacentes) 0,094 Búsqueda local (nodos no visitados) 0,102 Total 0,297 Tabla 5.10. Tiempos de ejecución del código VBA 63 63 Optimización de transportes de reparables en el sector aeronáutico 6 ANÁLISIS DE LA SOLUCIÓN PROPUESTA En el capítulo anterior se resolvió un problema cuyos datos estaban basados en valores promedios de las demandas de recogida y entrega, de cara a evaluar la bondad de los métodos de optimización escogidos. Una vez diseñado el algoritmo, en este capítulo simularemos los datos para un año completo y aplicaremos el algoritmo anterior a cada una de las 52 semanas, para evaluar el número de vehículos promedio que harán falta y los kilómetros estimados a recorrer. Con esos resultados, analizaremos el impacto tanto en costes como en Lead Time de la solución propuesta. Se simulan los datos para cada una de las semanas del año de manera aleatoria pero asegurando que el promedio de envíos y recogidas cumpla con los datos de la Tabla 4.1. Estos datos se muestran en el Anexo II. Aplicando los algoritmos de barrido, de vecino más cercano y de búsqueda local basado en permuta de nodos no visitados, obtenemos para cada semana los siguientes resultados: Semana Número de rutas (vehículos) Distancia recorrida (km) Semana Número de rutas (vehículos) Distancia recorrida (km) 1 7 3018,7 27 6 2512,0 2 11 4592,7 28 4 1577,3 3 7 2903,0 29 5 2493,7 4 6 2723,4 30 8 3206,0 5 8 3742,2 31 6 2829,4 6 5 1914,9 32 5 2514,4 7 6 2706,8 33 5 2698,5 8 6 3337,9 34 7 2874,6 9 7 3275,0 35 6 2618,3 10 7 2881,1 36 7 3186,7 11 5 2539,6 37 5 2083,2 12 4 2392,3 38 8 3358,6 13 8 3195,9 39 6 2387,4 14 6 2629,7 40 6 2615,1 15 6 2393,2 41 5 2380,4 16 7 3108,2 42 6 2703,6 17 4 2070,4 43 6 1750,6 18 7 2995,1 44 7 2890,3 19 6 2707,9 45 6 2714,9 20 5 2542,2 46 8 2914,8 21 6 1987,4 47 4 2109,1 22 6 2811,5 48 7 2864,0 23 7 2800,9 49 5 1962,5 24 9 3338,1 50 5 2734,4 25 8 3632,4 51 5 2437,7 26 6 2750,8 52 6 2482,8 Tabla 6.1. Resultados de aplicar los algoritmos de optimización semanalmente durante un año completo Análisis de la Solución Propuesta 64 Vamos a representar el número de vehículos necesarios para satisfacer la demanda semanal en un histograma, de cara a poder estimar el número necesario de vehículos que se deben contratar: Figura 6.1. Histograma del número de vehículos necesarios por semana Podemos observar que el número más repetido es el 6, que coincide con la mediana de la muestra. Si calculamos la desviación estándar, obtenemos que esta tiene un valor de 1,34. Podemos deducir que, si contratamos 6 vehículos, cubriremos el servicio el 63% de las ocasiones. Si contratásemos 7 vehículos, el servicio quedaría cubierto el 85% de las ocasiones y si fuesen 8 los vehículos contratados, se cubriría el 96%. Esta decisión se tomará más adelante cuando se analice el coste de reservar un vehículo así como posibles costes de cancelación. En cuanto a los kilómetros recorridos, el promedio es de 447 por ruta, lo que hace un total de 142.978 kilómetros. Si no hubiésemos aplicado algoritmos de optimización, el total de kilómetros recorridos hubiera sido 173.634, más de 30.000 km por encima del resultado final. En la Figura 6.2. se muestra el total de distancia recorrida en caso de haber utilizado cada método de optimización, donde se puede observar que aplicar la heurística del vecino más cercano ahorra un 14,2% de distancia, el algoritmo de búsqueda local con permuta de nodos adyacentes ahorra un 16,1% de distancia, y el basado en permuta de nodos no visitados permite ahorrar un 17,7% de distancia total. Figura 6.2. Comparación de distancia anual recorrida por algoritmo de optimización 65 65 Optimización de transportes de reparables en el sector aeronáutico La Figura 6.3 muestra estos mismos datos semanalmente, donde se puede notar que el algoritmo de búsqueda local con permuta de nodos no visitados es siempre el que mejores resultados obtiene, y el de barrido siempre el que peor. Figura 6.3. Distancia recorrida semanalmente por algoritmo de optimización 6.1 Análisis de Lead Times A continuación se va a estudiar la mejora en cuanto a tiempos de tránsito que se espera conseguir con la solución propuesta. Recordamos que los flujos son los siguientes:  Flujo de Almacén Central a Centro Reparador: Grupaje saliendo una vez en semana del almacén central. El LT será de 8 días de tránsito sumado a la espera al día de salida de la ruta, que podemos estimar como 3 días de media. El Lead Time de ida a centro reparador (sin contar trámites aduaneros) es de 11 días.  Flujo de Centro Reparador a Almacén Central: Grupaje saliendo cada vez que haya una expedición lista en un centro reparador. El LT es de 8 días de tránsito más 2 días aproximadamente para organizar la recogida. Vamos ahora a analizar los tiempos estimados para la solución propuesta, que consiste en hacer una ruta semanal con un tráiler al centro de distribución y posteriormente entregar y recoger todo de los centros reparadores mediante las rutas estudiadas en el capítulo anterior. El tiempo de tránsito desde el Almacén Central hasta el centro de distribución son dos días. A esto habrá que sumarle el tiempo de espera de la ruta, que inicialmente suponemos semanal, por lo que el promedio es de 3 días al igual que en la solución anterior. Es decir, el material llegaría al centro de distribución el quinto día y se llevaría a reparto el sexto, por lo que el promedio de LT de este flujo de ida se habrá reducido de 11 a 6 días, es decir, 5 días. Ahora, el tiempo máximo de tránsito será de 9 días y el mínimo de 3 días, sin contar trámites aduaneros, que se estima en 2 días. Para el flujo de vuelta, el tiempo de espera para que un material sea recogido es igual que en el caso contrario, ya que la misma ruta que entrega es la que recoge por lo que la frecuencia debe ser la misma. El tránsito es también de 2 días por lo que el LT desde centro reparador a Almacén Central sería también de 6 días de promedio, es decir, se consigue una reducción de 4 días. Todo lo expuesto previamente aplica únicamente a envíos con prioridad rutinaria (RTN). Los envíos en AOG Análisis de la Solución Propuesta 66 se continuarán enviando mediante vehículo dedicado a menos que el TR se genere el mismo día que sale la ruta, aprovechando que el tiempo de tránsito es similar. En el siguiente esquema se muestra la planificación semanal de la solución propuesta, que tiene un horizonte temporal de una semana: Figura 6.4. Planificación semanal de la solución propuesta Ahora debemos escoger el día de la semana que debe comenzar esta planificación:  Lunes: comenzando este día, la entrega sería el jueves y los materiales reparados llegarían al almacén central el domingo, por lo que habría que sumar un día más al LT del flujo de vuelta.  Martes: si el tráiler sale del almacén central el martes, el reparto se tendría que llevar a cabo el viernes. Teniendo en cuenta que muchos centros reparadores tienen horario reducido los viernes, es una opción arriesgada ya que si no da tiempo a hacer todas las entregas habría que sumar dos más más al LT hasta el lunes que vuelvan a abrir, además de tener que contratar más vehículos para hacer las entregas restantes.  Miércoles: saliendo este día, el reparto y recogida tendría que hacerse el lunes, añadiendo dos días de LT al flujo de reparables (ida). El tráiler llegaría el martes al almacén central (no se añade LT al flujo de vuelta).  Jueves: caso similar al anterior, pero solo se añadiría un día de LT al flujo de ida.  Viernes: con la salida un viernes, la llegada al centro de distribución sería el domingo. Esto implica que el tráiler debe quedarse inmovilizado durante un día, lo que además de sumar LT añade un sobrecoste que es preferible no asumir.  Sábado: el almacén central abre los sábados en horario de mañana, por lo que es viable la salida en este día. La llegada al almacén central sería el lunes a primera hora y el reparto el martes, saliendo el tráiler de vuelta el miércoles y llegando al Almacén Central el viernes.  Domingo: no es posible salir este día al estar el Almacén Central cerrado. Viendo las diferentes opciones, la mejor opción parece ser salir los sábados por la mañana, ya que es la única opción que no genera días de espera ni genera riesgos de no tener suficiente tiempo para completar los servicios. Podríamos conseguir tiempos aún más bajos si aumentamos la frecuencia de la ruta, teniendo siempre en cuenta que el mínimo tiempo de tránsito siempre será de 3 días. Si aumentamos la frecuencia de la ruta a dos por semana, tendríamos dos opciones viables: que la segunda salida se lleve a cabo el martes o el miércoles. Se 67 67 Optimización de transportes de reparables en el sector aeronáutico descartan el resto de días ya que estarían demasiado cerca de la otra salida. La opción del martes recordamos que tenía el problema de que se haría el reparto el viernes, pero si reducimos el número de TRs a la mitad (se reparten entre dos rutas) se podría conseguir entregar antes del cierre de los mismos. La opción del miércoles no reduciría tanto el LT de reparables ya que hay que contar con un tiempo de espera para el reparto, aunque sí reduciría a la mitad el de reparados. 6.2 Análisis Económico En esta sección se va a hacer una estimación de costes en función de los resultados del capítulo anterior. Para comenzar, se detallan los costes kilométricos de cada tipo de vehículo, obtenidos del informe de Julio de 2023 del “Observatorio de costes de transporte de mercancías por carretera” del Ministerio de Fomento: Tipo de vehículo Coste por km Coste por h Vehículo articulado de carga general 1,48 € 98,67 € Vehículo articulado de carga general en transporte internacional 1,59 € 119,46 € Tren de carretera 1,46 € 97,06 € Vehículo rígido de 3 ejes 1,36 € 71,92 € Vehículo rígido de 2 ejes 1,34 € 66,87 € Furgoneta 1,45 € 40,23 € Tabla 6.2. Costes kilométricos y horarios de transporte de mercancía por carretera Además de estos costes kilométricos y horarios, existen los siguientes costes fijos que debemos tener en cuenta a la hora de calcular el coste global de la solución propuesta:  Coste fijo por reserva de vehículo articulado: 80 €  Coste fijo por reserva de furgoneta: 40 €  Costes de cancelación de vehículo articulado: 120 €  Coste de cancelación de furgoneta: 60 €  Coste fijo para furgoneta adicional: 80 €  Coste horario de paralización de vehículo articulado: 5 €  Coste horario de paralización de furgoneta: 5 € Para calcular el coste anual de esta solución, debemos tener en cuenta que habrá ruta todas las semanas del año, y se han de tener en cuenta los siguientes conceptos:  Trayecto de Sevilla-Reading y viceversa: Este trayecto se hará en un vehículo articulado de carga general. La distancia (real, obtenida de la aplicación Google Maps) es de 2080 km, y se tardarían alrededor de 24 horas de conducción efectiva en este tipo de vehículo. El coste de cada trayecto sería: Análisis de la Solución Propuesta 68 𝐶𝑡𝑟𝑎𝑦,𝑆𝐸𝑉−𝑅𝐸𝐴 =𝐶ℎ∙𝑡+𝐶𝑑∙𝑑 =119,46∙24+1,59∙2080=⁡6.174,24⁡€ (6.1) Además, habría que sumar un día completo de paralización del vehículo en el que este está esperando a que las rutas de reparto y recogida terminen sus trayectos. Esto nos supone un coste de: 𝐶𝑝𝑎𝑟𝑎𝑙𝑖𝑧 =𝐶ℎ∙𝑡𝑝𝑎𝑟𝑎𝑙𝑖𝑧 =5∙24=⁡120⁡€ (6.3) Para calcular el coste total anual tendríamos que multiplicar por el número de semanas del año la suma del coste de dos trayectos entre Sevilla y Reading, los costes de paralización y el coste de reserva del vehículo que se calcula semanalmente: 𝐶𝑡,𝑇𝑅𝐴𝐼𝐿𝐸𝑅 =52(2𝐶𝑡𝑟𝑎𝑦,𝑆𝐸𝑉−𝑅𝐸𝐴 +⁡𝐶𝑝𝑎𝑟𝑎𝑙𝑖𝑧 +𝐶𝑟𝑒𝑠𝑒𝑟𝑣𝑎)=⁡⁡⁡652.520,96⁡€⁡ (6.3) Figura 6.5. Vehículo articulado de carga general  Rutas de reparto y recogida en centros reparadores: Para estas rutas elegiremos por su rapidez y facilidad para hacer tareas de reparto un vehículo de tipo furgoneta. Para calcular el coste de transporte tenemos que tener en cuenta tres factores: el coste por kilómetro, el coste por hora y el coste fijo por ruta. Para calcular el coste de trayecto puro (kilométrico y horario), usaremos los datos obtenidos en el capítulo anterior (Tabla 6.1 y Figura 6.2). Con estos datos obtendremos que la distancia total recorrida es de 142.978,41 kilómetros, que podemos multiplicar por el coste horario para obtener el anual. Para calcular el coste horario, asumimos que la velocidad media del recorrido es de 50 km/h (contando con las paradas para carga y descarga), por lo que emplearemos un total de 2.860 horas para llevar a cabo todas las rutas. 𝐶𝑡𝑟𝑎𝑦,𝑈𝐾 =𝐶ℎ∙𝑑 𝑣 +𝐶𝑑∙𝑑 =40,23∙2860+1,45∙142.978,41=⁡322.376,49⁡€⁡ (6.4) Ahora debemos calcular los costes fijos de reserva de los vehículos, así como las posibles 69 69 Optimización de transportes de reparables en el sector aeronáutico cancelaciones. Basándonos en los datos simulados para todo el año, vamos a calcular el coste anual que se tendría en los casos en que se reserven diferente número de furgonetas, sumándole los costes de furgoneta extra en caso de ser necesaria alguna más o restándole los costes de cancelación en caso de sobrar alguna. Los resultados se muestran en la siguiente figura: Figura 6.6. Costes fijos por cantidad de vehículos contratada a lo largo de un año Este cálculo confirma que la mejor opción es contratar 6 vehículos (la media) y pagar costes de cancelación cuando se necesiten menos y costes de vehículo extra cuando sea necesario. Se deduce por la forma de la gráfica que es preferible quedarse corto que largo, ya que aunque los costes de cancelación son menores que los de vehículo extra, cuando se cancela un vehículo además se pierde el fijo que se pagó inicialmente, por lo que sería un doble coste. Los costes fijos se calcularían de la siguiente manera: 𝐶𝑓𝑖𝑗𝑜,𝑈𝐾 =𝑁𝑣,𝑐𝑜𝑛𝑡𝑟𝑎𝑡𝑎𝑑𝑜 ∙𝐶𝑓𝑖𝑗𝑜 +𝑁𝑣,𝑐𝑎𝑛𝑐 ∙𝐶𝑐𝑎𝑛𝑐 +𝑁𝑣,𝑒𝑥𝑡𝑟𝑎 ∙𝐶𝑒𝑥𝑡𝑟𝑎 =⁡15.860,00⁡€⁡ (6.5) Los costes totales de las rutas en furgoneta en Inglaterra quedarían de la siguiente manera: 𝐶𝑡,𝐹𝑈𝑅𝐺𝑂𝑁𝐸𝑇𝐴 =𝐶𝑡𝑟𝑎𝑦,𝑈𝐾 +𝐶𝑓𝑖𝑗𝑜,𝑈𝐾 =⁡⁡338.236,49⁡€⁡ (6.6) Figura 6.7. Furgoneta Análisis de la Solución Propuesta 70  Costes logísticos del centro de distribución: El centro de distribución recibe una media de 40 TRs a la semana, si se dimensiona del lado de la seguridad con un 50% de espacio sobrante y se quiere apilar como máximo en dos alturas, se necesitarían alrededor de 45 m2, que incluyendo pasillos serían unos 50 m2. Según el portal en línea de estadísticas Statista, durante el primer trimestre de 2023 el precio medio anual de alquiler del m2 de suelo industrial (más concretamente, almacenes), fue de 300 €, por lo que podemos estimar un coste fijo de 15.000 € anuales en concepto de alquiler del centro de distribución. Además, es necesaria mano de obra para la carga y descarga de materiales, aunque esta es puntual (aproximadamente una hora) dos veces a la semana. El coste medio horario de la mano de obra en Inglaterra es de 25 €/h, por lo que semanalmente se gastarían 50 € y suponiendo que hay ruta las 52 semanas del año, el coste total de la mano de obra en el centro de distribución sería de 2600 €. Cabe destacar que el centro de distribución realmente solo estaría ocupado durante dos días a la semana, por lo que sería posible buscar alternativas más económicas que permitiesen compartir un almacén de manera coordinada, pero queda fuera del alcance de este trabajo académico. El coste anual del CEDI sería, por tanto: 𝐶𝐶𝐸𝐷𝐼 =𝐶𝑚𝑎𝑛𝑜⁡𝑑𝑒⁡𝑜𝑏𝑟𝑎 +𝐶𝑎𝑙𝑞𝑢𝑖𝑙𝑒𝑟 =⁡⁡⁡17.200⁡€⁡ (6.7) Calculamos ahora el coste total: 𝐶𝑎𝑛𝑢𝑎𝑙 =𝐶𝑡,𝑇𝑅𝐴𝐼𝐿𝐸𝑅 +𝐶𝑡,𝐹𝑈𝑅𝐺𝑂𝑁𝐸𝑇𝐴 +𝐶𝐶𝐸𝐷𝐼 =⁡𝟏.𝟎𝟎𝟕.𝟗𝟓𝟕,𝟒𝟓⁡€⁡ (6.8) Para poder comparar esta opción con el AS-IS que se tenía, se toman los datos del último año de grupaje y se calcula el coste medio por transporte. En este tipo de transportes, el coste varía poco entre unas localizaciones u otras, por lo que se puede considerar el coste homogéneo y de 325 € por TR. Considerando el número de entregas en 2116 y el número de recogidas en 1060 (al igual que en el caso anterior), el coste total resultará de multiplicar 3176 TRs por 350 €/TR: 𝐶𝑎𝑛𝑢𝑎𝑙,𝑔𝑟𝑢𝑝𝑎𝑗𝑒 =𝑛𝑇𝑅 ∙𝐶𝑇𝑅 =⁡⁡𝟏.𝟎𝟑𝟐.𝟐𝟎𝟎,𝟎𝟎⁡€⁡⁡ (6.9) De esta forma, habremos conseguido no solo reducir el Lead Time, sino además reducir sensiblemente el coste. El ahorro económico de esta solución se cifra en 24.242,55 €, que representa una reducción del 2,35%. 71 71 Optimización de transportes de reparables en el sector aeronáutico Figura 6.8. Comparativa de costes de AS-IS vs TO-BE En este punto, cabe destacar que si no se hubiesen utilizado algoritmos de optimización, simplemente con el algoritmo de barrido el coste de transporte puro de las rutas de reparto habría sido de 391.475,78 €, casi 70.000 € más, lo que habría hecho el business case negativo. En la siguiente tabla se muestran cómo habrían sido los costes totales en caso de utilizar cada algoritmo de optimización, así como el ahorro obtenido: Coste total Saving (€) Saving (%) Grupaje 1.032.200,00 € Algoritmo de barrido 1.077.056,74 € - 44.856,74 € -4,35% Heurística del vecino más cercano 1.021.299,58 € 10.900,42 € 1,06% Búsqueda local con permuta de nodos adyacentes 1.014.136,34 € 18.063,66 € 1,75% Búsqueda local con permuta de nodos no visitados 1.007.957,45 € 24.242,55 € 2,35% Tabla 6.3. Comparativa de costes de AS-IS con TO-BE para cada algoritmo de optimización Aunque el aumento de costes que se hubiese producido utilizando únicamente el algoritmo de barrido hubiese cumplido con los requerimientos del proyecto, que era aumentar costes menos de un 5% (véase el Capítulo 1.2), haber hecho uso de métodos heurísticos nos ha ahorrado más de 65 k€. Figura 6.9. Representación gráfica de la omparativa de costes para cada algoritmo de optimización Referencias 78 Zaragoza. [17] Toth, P. y Vigo, D. (2022). The Vehicle Routing Problem. Society of Industrial and Applied Mathematics (SIAM) monographs on discrete mathematics and applications. [18] Klapita, V. y Švecová, Z. (2010). Logistics centers location. Transport, 21(1), 48-52. [19] Lüer, A., Benavente, M., Bustos, J., y Venegas, B. (2009). El problema de rutas de vehículos: Extensiones y métodos de resolución, estado del arte. WORKSHOP INTERNATIONAL. Temuco. [20] González, D. y Gómez, D. (2019). Solución al problema de ruteo de vehículos con entregas y recogidas aplicando el algoritmo de pétalos y la heurística del vecino más cercano. Proyecto Curricular Ingeniería de Producción. Universidad Distrital Francisco José De Caldas. [21] Ryan, D. M., Hjorring, C., & Glover, F. (1993). Extensions of the petal method for vehicle routeing. Journal of the Operational Research Society, 44(3), 289-296. [22] Senthil Kumar, V. V. y Jayachitra R. (2016). Linear Sweep Algorithm for Vehicle Routing Problem with Simultaneous Pickup and Delivery between Two Depots with Several Nodes. Global Journal of Pure and Applied Mathematics.ISSN 0973-1768 Volume 12, Number 1 (2016), 897-908. [23] B. A. Foster y D. M. Ryan (1976). An integer programming approach to the vehicle scheduling problem. Opl Res. Q. 27, 367-284. [24] G. Laporte y Y. Nobert (1987). Exact algorithms for the vehicle routing problem. Ann Discrete Math, 31, 147-184. [25] Rosenkrantz, D. J., Stearns, R. E., y Lewis, P. (1977). An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing, 6(3), 563-581. [26] Statista. (2023). Industrial and Logistics Real estate rent per square meter in Europe 2023, by market. https://www.statista.com/statistics/858110/average-annual-industrial-rent-cost-per-square-meter-byeuropean-country [27] Ministerio de Fomento de España (2023) Observatorio de costes del transporte de mercancía por carretera. Julio 2023. Costes del Transporte de Mercancía por Carretera, 2, 6-50. 79 79 Optimización de transportes de reparables en el sector aeronáutico ANEXOS Anexo I: Matriz de distancias n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 00,0 61,6 76,8 24,4 162,4 84,8 65,7 158,1 93,4 186,7 95,9 116,3 75,6 74,3 71,6 74,0 96,4 120,3 135,0 119,5 214,6 193,1 435,2 180,9 149,2 205,4 131,5 143,2 179,0 349,9 262,4 51,5 251,5 121,3 262,2 161,6 0,0 27,0 41,1 125,4 65,4 55,1 129,2 74,4 157,8 104,5 127,5 109,7 132,8 132,1 135,1 157,4 180,6 194,1 177,8 267,9 244,2 483,6 221,3 176,6 229,2 156,5 148,5 178,9 339,8 252,4 66,2 234,9 108,9 239,2 276,8 27,0 0,0 52,7 98,4 44,4 41,3 102,5 52,2 131,0 89,5 111,7 105,1 140,5 142,1 146,1 168,1 197,0 211,8 196,1 289,4 266,6 507,2 246,4 203,1 256,1 183,2 175,3 205,1 363,7 276,8 92,3 258,0 134,5 260,6 324,4 41,1 52,7 0,0 139,4 63,4 44,9 136,5 72,5 165,4 83,9 106,2 75,2 91,7 91,4 94,8 117,1 144,3 159,2 143,8 238,7 216,9 458,8 202,4 166,5 222,1 147,8 152,7 187,1 355,6 267,6 59,6 254,1 123,5 262,3 4162,4 125,4 98,4 139,4 0,0 78,6 97,6 22,2 71,6 37,7 102,0 108,7 143,4 202,0 208,7 214,6 233,2 273,7 290,9 277,3 375,6 355,1 597,4 341,4 301,0 354,4 281,2 273,1 301,2 452,2 367,3 189,9 345,3 229,9 343,4 584,8 65,4 44,4 63,4 78,6 0,0 19,2 73,3 9,5 102,1 47,8 68,6 75,5 126,8 132,1 137,6 157,4 195,6 212,6 198,7 297,0 276,8 519,0 265,4 229,4 284,5 210,3 210,2 242,4 405,1 317,7 119,8 300,2 173,6 304,0 665,7 55,1 41,3 44,9 97,6 19,2 0,0 92,4 27,8 121,0 49,6 72,6 65,4 110,7 115,1 120,3 140,8 177,4 194,1 180,0 278,0 257,6 499,9 246,5 211,4 266,8 192,5 194,6 227,7 392,7 305,0 102,9 288,8 160,4 294,0 7158,1 129,2 102,5 136,5 22,2 73,3 92,4 0,0 64,7 29,1 86,6 90,0 129,3 190,1 197,8 203,9 221,4 264,1 281,9 269,0 368,3 349,0 591,1 338,8 301,5 356,0 282,1 277,7 307,5 462,8 377,0 190,9 356,2 236,7 355,7 893,4 74,4 52,2 72,5 71,6 9,5 27,8 64,7 0,0 93,3 44,7 63,7 77,3 131,6 137,7 143,3 162,6 202,1 219,4 205,8 304,5 284,6 526,9 274,2 238,7 293,9 219,6 219,7 251,8 414,2 326,8 129,3 309,1 182,9 312,5 9186,7 157,8 131,0 165,4 37,7 102,1 121,0 29,1 93,3 0,0 109,7 108,4 152,9 215,0 223,3 229,6 246,2 290,3 308,3 295,9 395,5 376,7 618,7 367,5 330,6 385,1 311,2 306,3 335,7 489,0 403,8 219,9 382,3 264,7 380,8 10 95,9 104,5 89,5 83,9 102,0 47,8 49,6 86,6 44,7 109,7 0,0 23,1 43,2 105,7 114,7 121,1 136,7 182,3 200,7 189,5 289,5 272,6 513,0 271,4 244,8 301,0 227,4 236,4 271,1 439,0 351,0 143,2 336,3 206,4 342,6 11 116,3 127,5 111,7 106,2 108,7 68,6 72,6 90,0 63,7 108,4 23,1 0,0 52,2 114,3 124,7 131,4 144,1 192,2 211,0 201,1 300,6 285,3 523,8 287,8 264,1 320,4 247,3 258,2 293,1 461,6 373,7 164,9 359,2 229,2 365,7 12 75,6 109,7 105,1 75,2 143,4 75,5 65,4 129,3 77,3 152,9 43,2 52,2 0,0 63,0 72,8 79,4 93,7 140,5 159,2 148,9 248,6 233,1 472,0 236,9 217,0 273,0 201,4 218,2 254,3 425,5 338,0 127,1 326,7 196,1 336,4 13 74,3 132,8 140,5 91,7 202,0 126,8 110,7 190,1 131,6 215,0 105,7 114,3 63,0 0,0 12,4 18,6 31,3 78,0 96,8 88,0 186,6 172,8 409,5 183,9 176,0 229,6 164,3 192,9 229,4 400,8 315,7 115,9 310,0 185,0 324,4 14 71,6 132,1 142,1 91,4 208,7 132,1 115,1 197,8 137,7 223,3 114,7 124,7 72,8 12,4 0,0 6,7 26,0 67,7 86,3 76,6 175,9 161,3 399,1 171,5 164,1 217,4 152,8 182,7 219,1 390,2 305,5 109,1 300,6 177,0 315,6 15 74,0 135,1 146,1 94,8 214,6 137,6 120,3 203,9 143,3 229,6 121,1 131,4 79,4 18,6 6,7 0,0 22,3 61,2 79,8 70,0 169,2 154,6 392,5 165,4 159,3 212,2 148,6 179,7 216,0 386,6 302,3 108,8 298,1 175,7 313,5 16 96,4 157,4 168,1 117,1 233,2 157,4 140,8 221,4 162,6 246,2 136,7 144,1 93,7 31,3 26,0 22,3 0,0 50,6 69,3 63,9 158,9 147,4 380,6 166,0 167,8 218,2 159,3 194,2 229,9 398,9 316,0 129,1 313,5 194,2 330,1 17 120,3 180,6 197,0 144,3 273,7 195,6 177,4 264,1 202,1 290,3 182,3 192,2 140,5 78,0 67,7 61,2 50,6 0,0 18,9 17,6 108,8 96,9 331,6 121,1 135,8 179,9 132,7 175,2 207,9 370,2 291,7 134,5 293,8 187,8 313,6 18 135,0 194,1 211,8 159,2 290,9 212,6 194,1 281,9 219,4 308,3 200,7 211,0 159,2 96,8 86,3 79,8 69,3 18,9 0,0 16,9 89,9 78,7 312,8 107,7 129,8 169,6 129,4 174,3 205,2 363,4 287,2 143,8 291,3 191,7 312,2 19 119,5 177,8 196,1 143,8 277,3 198,7 180,0 269,0 205,8 295,9 189,5 201,1 148,9 88,0 76,6 70,0 63,9 17,6 16,9 0,0 100,0 84,7 323,6 104,2 118,7 162,3 116,5 160,0 192,0 353,1 275,1 126,9 278,0 175,5 298,3 20 214,6 267,9 289,4 238,7 375,6 297,0 278,0 368,3 304,5 395,5 289,5 300,6 248,6 186,6 175,9 169,2 158,9 108,8 89,9 100,0 0,0 27,4 223,6 83,0 138,6 147,7 150,8 197,6 216,9 344,6 283,5 207,4 296,9 232,4 322,3 21 193,1 244,2 266,6 216,9 355,1 276,8 257,6 349,0 284,6 376,7 272,6 285,3 233,1 172,8 161,3 154,6 147,4 96,9 78,7 84,7 27,4 0,0 242,3 57,8 111,5 124,7 123,4 170,3 190,3 323,2 259,1 182,3 271,4 205,1 296,3 22 435,2 483,6 507,2 458,8 597,4 519,0 499,9 591,1 526,9 618,7 513,0 523,8 472,0 409,5 399,1 392,5 380,6 331,6 312,8 323,6 223,6 242,3 0,0 265,1 320,8 289,7 339,8 375,9 376,9 421,5 403,7 418,8 429,7 422,1 457,4 23 180,9 221,3 246,4 202,4 341,4 265,4 246,5 338,8 274,2 367,5 271,4 287,8 236,9 183,9 171,5 165,4 166,0 121,1 107,7 104,2 83,0 57,8 265,1 0,0 59,8 67,9 76,5 119,5 134,8 266,9 201,3 155,4 214,0 160,5 239,3 24 149,2 176,6 203,1 166,5 301,0 229,4 211,4 301,5 238,7 330,6 244,8 264,1 217,0 176,0 164,1 159,3 167,8 135,8 129,8 118,7 138,6 111,5 320,8 59,8 0,0 56,3 20,3 59,7 79,9 234,4 157,7 111,1 164,3 101,7 187,5 25 205,4 229,2 256,1 222,1 354,4 284,5 266,8 356,0 293,9 385,1 301,0 320,4 273,0 229,6 217,4 212,2 218,2 179,9 169,6 162,3 147,7 124,7 289,7 67,9 56,3 0,0 74,3 90,9 87,3 199,0 136,7 165,2 153,6 139,8 180,4 26 131,5 156,5 183,2 147,8 281,2 210,3 192,5 282,1 219,6 311,2 227,4 247,3 201,4 164,3 152,8 148,6 159,3 132,7 129,4 116,5 150,8 123,4 339,8 76,5 20,3 74,3 0,0 47,7 75,8 239,8 159,1 91,4 161,8 84,1 183,2 27 143,2 148,5 175,3 152,7 273,1 210,2 194,6 277,7 219,7 306,3 236,4 258,2 218,2 192,9 182,7 179,7 194,2 175,2 174,3 160,0 197,6 170,3 375,9 119,5 59,7 90,9 47,7 0,0 36,6 208,7 122,8 93,3 119,6 49,0 138,4 28 179,0 178,9 205,1 187,1 301,2 242,4 227,7 307,5 251,8 335,7 271,1 293,1 254,3 229,4 219,1 216,0 229,9 207,9 205,2 192,0 216,9 190,3 376,9 134,8 79,9 87,3 75,8 36,6 0,0 172,1 86,4 128,3 86,1 71,4 107,9 29 349,9 339,8 363,7 355,6 452,2 405,1 392,7 462,8 414,2 489,0 439,0 461,6 425,5 400,8 390,2 386,6 398,9 370,2 363,4 353,1 344,6 323,2 421,5 266,9 234,4 199,0 239,8 208,7 172,1 0,0 87,9 298,6 106,8 232,6 113,9 30 262,4 252,4 276,8 267,6 367,3 317,7 305,0 377,0 326,8 403,8 351,0 373,7 338,0 315,7 305,5 302,3 316,0 291,7 287,2 275,1 283,5 259,1 403,7 201,3 157,7 136,7 159,1 122,8 86,4 87,9 0,0 210,9 31,3 144,7 56,0 31 51,5 66,2 92,3 59,6 189,9 119,8 102,9 190,9 129,3 219,9 143,2 164,9 127,1 115,9 109,1 108,8 129,1 134,5 143,8 126,9 207,4 182,3 418,8 155,4 111,1 165,2 91,4 93,3 128,3 298,6 210,9 0,0 200,1 70,6 211,5 32 251,5 234,9 258,0 254,1 345,3 300,2 288,8 356,2 309,1 382,3 336,3 359,2 326,7 310,0 300,6 298,1 313,5 293,8 291,3 278,0 296,9 271,4 429,7 214,0 164,3 153,6 161,8 119,6 86,1 106,8 31,3 200,1 0,0 130,8 27,7 33 121,3 108,9 134,5 123,5 229,9 173,6 160,4 236,7 182,9 264,7 206,4 229,2 196,1 185,0 177,0 175,7 194,2 187,8 191,7 175,5 232,4 205,1 422,1 160,5 101,7 139,8 84,1 49,0 71,4 232,6 144,7 70,6 130,8 0,0 141,0 34 262,2 239,2 260,6 262,3 343,4 304,0 294,0 355,7 312,5 380,8 342,6 365,7 336,4 324,4 315,6 313,5 330,1 313,6 312,2 298,3 322,3 296,3 457,4 239,3 187,5 180,4 183,2 138,4 107,9 113,9 56,0 211,5 27,7 141,0 0,0 Anexos 80 Anexo II: Demandas de recogidas y entregas simuladas para un año completo Ciudad Número de TRs a entregar total CW01 CW02 CW03 CW04 CW05 CW06 CW07 CW08 CW09 CW10 CW11 CW12 CW13 CW14 CW15 CW16 CW17 CW18 CW19 CW20 CW21 CW22 CW23 CW24 CW25 CW26 CW27 CW28 CW29 CW30 CW31 CW32 CW33 CW34 CW35 CW36 CW37 CW38 CW39 CW40 CW41 CW42 CW43 CW44 CW45 CW46 CW47 CW48 CW49 CW50 CW51 CW52 ISLE OF WIGHT 63 3013310203112022113103021000000030300300003033300303 WIMBORNE 91 3243114310242032000304431201104430012400330214220020 SOUTHEND-ON-SEA 56 5 5 1 1 2 0 1 2 2 2 2 2 2 1 0 2 0 0 0 0 0 1 1 0 1 1 2 0 1 5 1 1 0 0 0 0 0 1 1 1 0 2 2 1 0 0 0 0 0 2 2 0 OXFORDSHIRE 35 0121010112111021100200001111011101020010000111200100 GLOUCESTER 193 6754407457040716064360658603344620482530500756680001 BRISTOL 66 3100111211022202222000000102223020030332012221021232 COVENTRY 112 2267002450307004313000016310050010016340600575302004 CRAWLEY 72 1801001202100011032312202221323310322133002010201020 WOLVERHAMPTON 66 2002333002010020121020200023232033033203201011101310 BRIDPORT 53 0410221121211111112111001121120112111020100120101011 LONDON 49 0021102012010020121212232101100011010102010110021312 POOLE 31 1012000100011001010010110100110110111211110111001010 HEREFORD 80 0022300130100134440002400030033400512000202002443134 MARLOW 67 1022122130113342103204040230110000000232223002000002 LUTON 30 1201010012100001022220000011200000010021200000100100 TITCHFIELD 27 0111000110110100001010001111011001100101111000101110 PORTSMOUTH 80 2520423103202040130013333000140230002304103000210322 ESSEX 36 1101110000012000010221100221100000112121011110100110 WATERHEAD 52 0000102301320000022100002200020321222120220220120111 YEOVIL 59 1010202310323011213200031321121001211230010002031000 REDDITCH 29 1210001111010110010001121000000011000101111110011001 LEIGHTON BUZZARD 39 1 0 1 0 0 0 1 1 2 2 2 0 2 2 1 0 0 2 0 0 1 1 0 1 0 1 2 2 0 0 1 1 2 0 0 2 0 1 1 0 1 0 0 1 0 1 0 0 0 1 2 0 WEST SUSSEX 43 1212101120100001100010111100110112221002110021020211 VERWOOD, DORSET 130 2 3 6 3 3 1 5 4 4 0 0 0 0 0 6 7 0 0 0 2 0 5 5 2 0 1 2 4 4 5 3 5 0 1 1 4 5 0 6 5 3 1 1 0 4 5 0 5 4 0 1 2 CHELTENHAM 48 2210100300000022112220101110222100120011010102220021 HANFORTH 43 2100101012100001102202111200122201112000001022002002 MARSTON 53 1022101102200102202002022212122110012000220202100211 BLACKPOOL 28 0500000000550000000000000000003001220000000500000000 SUSSEX 76 2600211140103432010300020030302120300014032033032320 BASILDON, ESSEX 63 1 3 0 2 0 2 1 0 0 0 3 0 3 1 1 0 3 0 3 2 0 2 1 3 2 0 0 0 3 0 2 0 0 1 2 3 3 1 0 2 2 0 2 0 2 0 1 2 0 1 1 2 CORNWALL 73 3002330122213122123201201200232122302303001212101010 CHRISTCHURCH 34 2100010220011011010000001111102011210201200000101011 FAREHAM-HAMPHIRE 67 2 7 2 2 2 1 0 3 3 1 0 2 0 2 1 2 0 3 0 2 0 0 3 1 2 2 0 3 0 0 1 0 2 2 3 2 0 0 3 1 0 0 0 1 0 1 0 0 2 2 0 1 SOUTHALL 72 1140132002212123133001220000000340303021042233010220 81 81 Optimización de transportes de reparables en el sector aeronáutico Ciudad Nº de TRs a recoger total CW01 CW02 CW03 CW04 CW05 CW06 CW07 CW08 CW09 CW10 CW11 CW12 CW13 CW14 CW15 CW16 CW17 CW18 CW19 CW20 CW21 CW22 CW23 CW24 CW25 CW26 CW27 CW28 CW29 CW30 CW31 CW32 CW33 CW34 CW35 CW36 CW37 CW38 CW39 CW40 CW41 CW42 CW43 CW44 CW45 CW46 CW47 CW48 CW49 CW50 CW51 CW52 ISLE OF WIGHT 62 2 2 0 2 0 0 1 3 0 2 0 1 0 0 1 1 1 0 0 1 2 0 0 1 2 2 1 0 0 1 1 3 2 2 3 3 0 2 2 2 1 0 2 2 2 2 0 2 2 2 0 1 WIMBORNE 76 0113000203322031013213012310122323112021020232202002 SOUTHEND-ON-SEA 33 0 3 1 1 0 0 0 1 0 2 0 1 1 1 2 1 1 1 1 1 0 1 0 0 1 0 1 0 0 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 0 0 1 0 0 0 0 1 OXFORDSHIRE 2 0000000000000000000000000000000000000000000000000000 GLOUCESTER 26 1111001101010011010011101110110000110000101110001100 BRISTOL 65 0572121110000602001110502123002011200201021013120001 COVENTRY 38 1020111001102100001001221101101201010000110110110211 CRAWLEY 29 1110011000101001000101110011110010010011101010110101 WOLVERHAMPTON 29 0 5 1 1 1 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 1 1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 1 BRIDPORT 29 1101200100100010000011010110010112100010010001111100 LONDON 29 0101101111100001100010010100010110100001110100110110 POOLE 4 0100000000000000000000000000000000000000000000000000 HEREFORD 4 0000000000000000000000000000000000000000000000000000 MARLOW 31 0201000110001100011021001001011011010101010111002110 LUTON 32 1110110000110100011011011000100011111100010111010111 TITCHFIELD 29 0011100111101111000111101110100111010011011010101000 PORTSMOUTH 36 0500001111003200100111010111111001000101111001100010 ESSEX 28 0011011010011001101101000110101000111101110000000111 WATERHEAD 28 0500001101100000100100111107000001000010000101010011 YEOVIL 26 0000101000000010011011110000001010010101101100111111 REDDITCH 27 0011101111001010110101010000110101011001111000001101 LEIGHTON BUZZARD 27 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 1 1 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 1 1 1 1 0 1 0 1 1 0 WEST SUSSEX 3 0200000000000000000000000000000000000000000000000000 VERWOOD, DORSET 131 4 5 5 3 3 5 0 0 3 4 0 2 4 6 5 3 0 4 0 5 3 3 5 4 6 5 0 0 3 0 5 2 0 0 0 1 2 5 5 0 2 4 1 6 0 0 0 1 0 6 0 0 CHELTENHAM 31 0400201110001110110010001000022001100211001010010001 HANFORTH 74 3130113112310301020200302010002201332303042322313002 MARSTON 4 0000000000000000000000000000000000000000000000000000 BLACKPOOL 1 0000000000000000000000000000000000000000000000000000 SUSSEX 0 0000000000000000000000000000000000000000000000000000 BASILDON, ESSEX 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 CORNWALL 28 1000010001000110000102120100111002001002111102110001 CHRISTCHURCH 15 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 0 1 1 1 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 FAREHAM-HAMPHIRE 52 0 0 0 1 0 0 0 2 3 2 0 0 2 0 0 3 2 1 1 1 3 1 0 3 2 2 0 0 0 3 3 0 1 0 1 2 1 1 3 0 1 1 0 0 0 1 1 3 1 2 0 0 SOUTHALL 29 1001101111110110000100111000010101100000101101101011 Anexos 82 Anexo III: Código de programación en Visual Basic - Declaración de variables globales y macro principal: Public n_nodes Public id Public city Public x Public y Public r Public theta Public deliveries Public collections 'Parámetros del problema Public Const max_TR As Integer = 10 ' Capacidad máxima del vehículo Public Const max_vehicles As Integer = 15 ' Número máximo de vehículos de la flota Sub main() Application.ScreenUpdating = False Call import_data ' Macro que importa los datos en variables globales Call erase_results ' Macro que borra los resultados del problema anterior Call petals ' Macro que define los pétalos de las rutas Call neighbor_heuristic ' Macro que optimiza cada pétalo mediante haurística del vecino más cercano Call local_search ' Macro que optimiza cada pétalo mediante búsqueda local Call local_search__bis ' Macro que optimiza cada pétalo mediante búsqueda local con el resto de nodos de la ruta End Sub - Macro que importa los datos del problema: Sub import_data() Sheets("Data").Select n_nodes = Range("A2").End(xlDown).Row - 3 ' Número de nodos (sin contar el CEDI) ReDim id(n_nodes) ' ID del nodo (el CEDI es el nodo 0) ReDim city(n_nodes) ' Nombre de la ciudad del nodo ReDim x(n_nodes) ' Coordenada x del nodo ReDim y(n_nodes) ' Coordenada y del nodo ReDim r(n_nodes) ' Coordenada polar r del nodo ReDim theta(n_nodes) ' Coordenada polar theta del nodo ReDim deliveries(n_nodes) ' Número de TRs a entregar en el nodo ReDim collections(n_nodes) ' Número de TRs a recoger en el nodo For i = 0 To n_nodes id(i) = Range("A2").Offset(i + 1, 0).Value city(i) = Range("B2").Offset(i + 1, 0).Value deliveries(i) = Range("C2").Offset(i + 1, 0).Value collections(i) = Range("D2").Offset(i + 1, 0).Value x(i) = Range("H2").Offset(i + 1, 0).Value y(i) = Range("I2").Offset(i + 1, 0).Value r(i) = Range("J2").Offset(i + 1, 0).Value theta(i) = Range("K2").Offset(i + 1, 0).Value Next End Sub - Macro que borra los datos del problema anterior: Sub erase_results() Sheets("Resultado").Select Range("C2:L16").ClearContents Sheets("Resultado_2").Select Range("C2:L16").ClearContents Sheets("Resultado_3").Select Range("C2:L16").ClearContents Sheets("Resultado_4").Select Range("C2:L16").ClearContents 83 83 Optimización de transportes de reparables en el sector aeronáutico End Sub - Macro que forma los pétalos con el Algoritmo de Barrido: Sub petals() Dim vehicle(max_vehicles) As Integer ' Número de vehículo (ruta) Dim customer As Integer ' Número de nodo recorrido Dim n_collected As Integer ' Número de TRs recorridos durante la ruta Dim n_to_deliver As Integer ' Número de TRs pendientes de entregar durante la ruta Dim n_result(max_vehicles) As Integer ' Nodos que alcanza cada ruta Dim j As Integer ' Variable auxiliar para imprimir los nodos-ruta en la hoja de resultados Sheets("Resultado").Select Range("C2:L16").ClearContents ' Borramos el resultado de la ruta anterior customer = 1 ' Comienzo con el primer cliente, saltándome el CEDI For n_route = 1 To max_vehicles ' Itero para cada ruta j = 0 vehicle(n_route) = max_TR ' Defino la carga del vehículo como la máxima posible While max_TR - vehicle(n_route) < collections(customer) - deliveries(customer) vehicle(n_route) = vehicle(n_route) - 1 ' Si en el primer nodo la demanda de recogida es la mayor que la demanda de entrega, cargo un TR menos para hacer hueco a la recogida y poder comenzar la ruta Wend n_to_deliver = vehicle(n_route) ' Defino la cantidad de TRs en entregar n_collected = 0 ' Al inicio de la ruta, no habré recogido ningún TR While (vehicle(n_route) + collections(customer) - deliveries(customer)) <= max_TR And n_to_deliver >= deliveries(customer) ' Ahora itero hasta que se llene el camión o se acaben las entregas pendientes vehicle(n_route) = vehicle(n_route) + collections(customer) - deliveries(customer) n_collected = n_collected + collections(customer) ' Su suman los TRs recogidos a la cuenta de recogidas n_to_deliver = n_to_deliver - deliveries(customer) ' Su restan los TRs entregados a la cuenta de entregas pendientes j = j + 1 Sheets("Resultado").Range("A1").Offset(n_route, j + 1).Value = customer customer = customer + 1 ' Voy al siguiente nodo If customer = n_nodes + 1 Then ' Cuando llego al último cliente, salgo del bucle GoTo finished End If Wend n_result(n_route) = customer - 1 ' La variable n_result toma el ID del último nodo visitado por cada vehículo Next finished: n_result(n_route) = customer - 1 End Sub - Macro que aplica la heurística del vecino más cercano: Sub neighbor_heuristic() Dim m_dist(34, 34) ' Matriz de distancias Dim m_res(15, 11) ' Matriz resultado del algoritmo de pétalos Dim m_routes(15, 11) ' Matriz de rutas Dim visit(15, 11) As Boolean ' Vector de visita Dim act_node ' Nodo actual Dim min_dist As Double ' Variable auxiliar para distancia mínima Dim neighbor As Integer ' Vecino más cercano Dim next_node As Integer ' Variabla auxiliar para conocer la ID del siguiente nodo ' Carga de la matriz de distancias Sheets("matriz_distancias").Select For a = 0 To 34 For b = 0 To 34 m_dist(a, b) = Range("B2").Offset(a, b).Value Next Next ' Carga del resultado del algoritmo de pétalos Sheets("Resultado").Select Anexos 84 For m = 1 To max_vehicles For n = 0 To max_TR m_res(m, n) = Range("B2").Offset(m - 1, n).Value Next Next 'Algoritmo de mejora For i = 1 To max_vehicles ' Entro en cada ruta ' Comienzo en el nodo 0 act_node = 0 m_routes(i, 0) = 0 visit(i, 0) = True For j = 1 To max_TR min_dist = -1 neighbor = -1 For k = 1 To max_TR If Not visit(i, k) And m_res(i, k) <> "" Then If min_dist = -1 Or m_dist(act_node, m_res(i, k)) < min_dist Then min_dist = m_dist(act_node, m_res(i, k)) neighbor = k End If End If Next If neighbor <> -1 Then visit(i, neighbor) = True m_routes(i, j) = m_res(i, neighbor) act_node = m_res(i, neighbor) Else m_routes(i, j) = "" End If Next Next Sheets("Resultado_2").Select For i_aux = 1 To max_vehicles For j_aux = 1 To max_TR Sheets("Resultado_2").Range("A1").Offset(i_aux, j_aux + 1).Value = m_routes(i_aux, j_aux) Next Next End Sub - Macro que aplica el algoritmo de búsqueda local con permuta de nodos adyacentes: Sub local_search() Dim m_dist(34, 34) ' Matriz de distancias Dim m_res(15, 11) ' Matriz resultado del algoritmo de pétalos con heurística de vecindad Dim m_routes(15, 11) ' Matriz de rutas Dim best_d As Double Dim aux As Integer ' Variable auxiliar para hacer el intercambio de nodos ' Carga de la matriz de distancias Sheets("matriz_distancias").Select For a = 0 To 34 For b = 0 To 34 m_dist(a, b) = Range("B2").Offset(a, b).Value Next Next ' Carga del resultado del algoritmo de pétalos con heurística de vecindad Sheets("Resultado_2").Select For m = 1 To max_vehicles For n = 0 To max_TR m_res(m, n) = Range("B2").Offset(m - 1, n).Value Next Next 85 85 Optimización de transportes de reparables en el sector aeronáutico For i = 1 To max_vehicles permuta = 1 While permuta = 1 permuta = 0 ' Calculo distancia total inicial d = 0 For k = 0 To max_TR ' Calculo la distancia total recorrida If m_res(i, k + 1) <> "" Then d = d + m_dist(m_res(i, k), m_res(i, k + 1)) ElseIf m_res(i, k) <> "" Then d = d + m_dist(m_res(i, k), 0) End If Next best_d = d For j = 1 To max_TR If m_res(i, j + 1) <> "" Then ' Intercambio el nodo aux = m_res(i, j) m_res(i, j) = m_res(i, j + 1) m_res(i, j + 1) = aux ' Calculo distancia total d = 0 For k = 0 To max_TR ' Calculo la distancia total recorrida If m_res(i, k + 1) <> "" Then d = d + m_dist(m_res(i, k), m_res(i, k + 1)) ElseIf m_res(i, k) <> "" Then d = d + m_dist(m_res(i, k), 0) End If Next If d < best_d Then ' Si mejora, me quedo con la distancia mínima best_d = d permuta = 1 Else aux = m_res(i, j) ' Si no mejora, deshago el cambio m_res(i, j) = m_res(i, j + 1) m_res(i, j + 1) = aux End If End If Next Wend Next Sheets("Resultado").Select For i_aux = 1 To max_vehicles For j_aux = 1 To max_TR Sheets("Resultado_3").Range("A1").Offset(i_aux, j_aux + 1).Value = m_res(i_aux, j_aux) Next Next End Sub - Macro que aplica el algoritmo de búsqueda local con permuta de nodos no visitados: Sub local_search_bis() Dim m_dist(34, 34) ' Matriz de distancias Dim m_res(15, 11) ' Matriz resultado del algoritmo de pétalos con heurística de vecindad Dim m_routes(15, 11) ' Matriz de rutas Dim best_d As Double Dim aux As Integer ' Variable auxiliar para hacer el intercambio de nodos ' Carga de la matriz de distancias Sheets("matriz_distancias").Select For a = 0 To 34 Anexos 86 For b = 0 To 34 m_dist(a, b) = Range("B2").Offset(a, b).Value Next Next ' Carga del resultado del algoritmo de pétalos con heurística de vecindad Sheets("Resultado_3").Select For m = 1 To max_vehicles For n = 0 To max_TR m_res(m, n) = Range("B2").Offset(m - 1, n).Value Next Next For i = 1 To max_vehicles permuta = 1 While permuta = 1 permuta = 0 ' Calculo distancia total inicial d = 0 For k = 0 To max_TR ' Calculo la distancia total recorrida If m_res(i, k + 1) <> "" Then d = d + m_dist(m_res(i, k), m_res(i, k + 1)) ElseIf m_res(i, k) <> "" Then d = d + m_dist(m_res(i, k), 0) End If Next best_d = d For j = 1 To max_TR For p = j + 1 To max_TR If m_res(i, p) <> "" Then ' Intercambio el nodo aux = m_res(i, j) m_res(i, j) = m_res(i, p) m_res(i, p) = aux ' Calculo distancia total d = 0 For k = 0 To max_TR ' Calculo la distancia total recorrida If m_res(i, k + 1) <> "" Then d = d + m_dist(m_res(i, k), m_res(i, k + 1)) ElseIf m_res(i, k) <> "" Then d = d + m_dist(m_res(i, k), 0) End If Next If d < best_d Then ' Si mejora, me quedo con la distancia mínima best_d = d permuta = 1 Else aux = m_res(i, j) ' Si no mejora, deshago el cambio m_res(i, j) = m_res(i, p) m_res(i, p) = aux End If End If Next Next Wend Next Sheets("Resultado_4").Select For i_aux = 1 To max_vehicles For j_aux = 1 To max_TR Sheets("Resultado_4").Range("A1").Offset(i_aux, j_aux + 1).Value = m_res(i_aux, j_aux) Next Next End Sub