Una búsqueda tabú reactiva para la optimización del acarreo terrestre con vehículos heterogéneos

Equation Chapter 1 Section 1 Trabajo Fin de Grado Grado en Ingeniería de las Tecnologías Industriales Una búsqueda tabú reactiva para la optimización del acarreo terrestre con vehículos heterogéneos Autor: Jose Mariano Casallo Clapés Tutor: Alejandro Escudero Santana Dpto. Organización Industrial y Gestión de Empresas II Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2020 iii Trabajo Fin de Grado Grado en Ingenieria de las Tecnologías Industriales Una búsqueda tabú reactiva para la optimización del acarreo terrestre con vehículos heterogéneos Autor: Jose Mariano Casallo Clapés Tutor: Alejandro Escudero Santana Profesor Titular de Universidad Dpto. de Organización Industrial y Gestión de Empresas II Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2020 v Trabajo Fin de Grado: Una búsqueda tabú reactiva para la optimización del acarreo terrestre con vehículos heterogéneos Autor: Jose Mariano Casallo Clapés Tutor: Alejandro Escudero Santana El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2020 El Secretario del Tribunal vii A Antonio ix Agradecimientos A la paciencia de mi familia, Al optimismo de mis amigos. José Mariano Casallo Clapés Sevilla, 2020 ÍNDICE DE TABLAS Tabla 1. Conjunto de operaciones y estados en el acarreo terrestre. Fuente: Escudero Santana (2013) 9 Tabla 3. Tipos de contenedor según sus diferentes funciones 11 Tabla 4. Variables del problema MSDDP 15 Tabla 5. Resultados para el caso 1 45 Tabla 6. Resultados para el caso 2 46 Tabla 7. Resultados para el caso 3. 47 Tabla 8. Resultados para el caso 4. 47 Tabla 9. Resultados para el caso 5. 48 Tabla 10. Resultados para el caso 6. 49 Tabla 11. Resultados para el caso 7. 50 xvii ÍNDICE DE FIGURAS Ilustración 1. Proporción de los diferentes modos de transporte empleados en UE y España respectivamente (Fuente: https://contenidos.ceoe.es) 3 Ilustración 2.Esquema transporte intermodal: Ferrocarril - Carretera 4 Ilustración 3. Estados diferentes del camión (Escudero 2013) 7 Ilustración 4. Diferentes movimientos de las operaciones de acarreo terrestre (Escudero 2013) 8 Ilustración 5. Ventanas temporales de las tareas. Fuente: Escudero-Santana (2013) 15 Ilustración 6. Esquema de resolución de un problema mediante algoritmo Branch & Bound (Briheche et al, 2020) 20 Ilustración 7. Solución inicial de Clark & Wright 21 Ilustración 8. Solución óptima, Clark & Wright 22 Ilustración 9. Ejemplo de resolución mediante método del barrido (Arango Serna et al. 2009) 22 Ilustración 10. Pseudo-código GRASP (Resende et al. 2003) 24 Ilustración 11. Pseudo-código Algoritmo Genético Simple (UPV) 25 Ilustración 12. Pseudo-código Recocido Simulado (Tricas, 2015) 26 Ilustración 13. Solucion inicial 28 Ilustración 14. Lista Tabú de 5 elementos 28 Ilustración 15. Solución resultado de aplicar vecindad 1-5 28 Ilustración 16. Lista Tabú actualizada 28 Ilustración 17. Vector solucion actualizado 29 Ilustración 18. Lista Tabú actualizada. Segundo ciclo 29 Ilustración 19. Adjacent Swap 29 Ilustración 20. General Swap 30 Ilustración 21. Insertion 30 Ilustración 22. Función escape del algoritmo RTS en Pascal. (Battiti et al, 1994) 33 Ilustración 23. Esquema general resolución del problema (Elaboración propia) 37 Ilustración 24. Funcion Read_problem codificada en Python 37 Ilustración 25. Vecindad aplicada a una solucion aleatoria del problema 39 Ilustración 26. Actualizacion en Python de km_list, t_f y posicion_actual 41 Ilustración 27. Diagrama RTS aplicado al problema de acarreo 42 Ilustración 28. Pseudo-código del mecanismo RTS 44 Ilustración 29. Izqda: Evolución de la f.o. para el caso 1. Dcha: Gráfica ampliada 46 Ilustración 30. Izqda: Evolución de la f.o. para el caso 1. Dcha: Gráfica ampliada 46 Ilustración 31. Izqda. Evolución f.o. para el caso 4. Dcha: Evolución del bypass 47 Ilustración 32. Izqda: Evolucion f.o. para el caso 4. Dcha: Gráfica ampliada 48 Ilustración 33. Izqda: Evolución f.o. en el caso 5. Dcha. Evolución Bypass 48 xix 1 1 INTRODUCCIÓN Actualmente, la distribución de mercancías se considera uno de los campos de la logística más interesantes en cuanto a optimización se refiere. Una parte importante de los costes de una empresa se debe a estos costes logísticos, y en un entorno cada vez más competitivo, la búsqueda de la mejora del servicio al cliente genera un claro aumento de dichos costes de transporte. Además, debido al desequilibrio actual en el sistema de transporte de la UE, aparecen ciertos efectos externos de carácter negativo, a saber: costes de congestión, contaminación tanto atmosférica como acústica o accidentes. Por todo ello surge este deseo de mejorar la eficiencia en el transporte, persiguiendo que sea más adecuado en costes, más seguro, y logrando una disminución de su impacto ambiental, así como una mayor aceptación social. Esta búsqueda del transporte sostenible ha llevado a un nuevo concepto de política de distribución de mercancías: el transporte intermodal. Este concepto se trata de una integración del sistema de transporte, y se basa en recurrir en cada tramo de la cadena al medio de transporte más adecuado. Decide, para cada etapa, entre el medio marítimo, aéreo, el ferrocarril y el transporte por carretera, optimizando así tanto los diferentes tramos como la cadena global. Ante el objetivo de mejorar la flexibilidad, y conseguir un servicio de entrega puerta a puerta, destaca sobre los demás un medio: el transporte por carretera. Teniendo en cuenta que la unidad de carga es el contenedor, tanto el tramo inicial de una tarea como el final, va a ser llevado a cabo por camiones, y a este movimiento se le denomina acarreo terrestre o drayage. El acarreo terrestre supone una parte imprescindible en la cadena intermodal, ya que aporta la flexibilidad necesaria para cumplir con las exigencias relacionadas con el servicio al cliente que aparecen en la actualidad. Esta parte de la cadena sigue suponiendo un porcentaje importante de los costes logísticos, y es en este proyecto donde se propondrá una optimización para reducir dichos costes, y por tanto conseguir una mejora en el rendimiento de la actividad. El acarreo terrestre se define como un problema de optimización NP-Hard en cuanto a su complejidad. Todavía son muchas las empresas que resuelven dicho problema manualmente, y es por tanto muy interesante la búsqueda de su resolución mediante herramientas informáticas. Técnicas heurísticas y meta-heurísticas pueden proporcionar una solución eficiente para el problema del drayage, y este documento mostrará algunas de las más interesantes. Este proyecto ha optado por la Búsqueda Tabú o Tabu Search, la cual será analizada en profundidad. Mediante dicho método se buscará por tanto conseguir una solución que suponga una mejora en cuanto a eficiencia y ahorro de costes, además de conseguir una reducción en los problemas presentes del impacto ambiental y en el tiempo requerido para dicha actividad. 1.1. Objetivos Este proyecto va a tratar de ofrecer la solución óptima al problema del acarreo terrestre, buscando minimizar los tiempos de transporte mediante la elección correcta de las rutas formadas por las diferentes localizaciones, y minimizar por tanto los costes logísticos que van ligados con dichas rutas. Este ahorro en costes será debido, entre otros, a la reducción de combustible necesario para llevar a cabo la tarea, por lo que también se perseguirá una minimización de la contaminación que el petróleo y la emisión de gases de combustión puede ocasionar durante el transcurso de la actividad. Para la resolución de dicho problema, se presentará una descripción detallada del drayage, así como del método que va a ser empleado para afrontar dicho problema. Además, se incluirá el caso práctico en cuestión y las simplificaciones pertinentes para poder llevar a cabo el proyecto. El objetivo es, por tanto, mostrar cómo, mediante herramientas informáticas, se implementa una heurística Introducción 2 para resolver de manera óptima el problema del acarreo terrestre, consiguiendo aumentar la eficiencia y flexibilidad del transporte por carretera reduciendo además los costes de la tarea. 1.2. Estructura del trabajo Este documento se estructura en 8 capítulos: - En el capítulo 1 se muestra una introducción, donde se expone la motivación del problema y los objetivos. - En el capítulo 2 se analiza el transporte intermodal y sus características. - En el capítulo 3 se pasa a profundizar en el acarreo terrestre: características, revisión bibliográfica, variantes del problema y su modelado. - El capítulo 4 recoge los diferentes tipos de métodos de resolución, diferenciando entre exactos, heurísticas y metaheurísticas, así como describiendo algunos de los algoritmos más empleados de cada tipo. - El capítulo 5 se centra en la búsqueda tabú, su definición, características, y una introducción a la búsqueda tabú reactiva, la cual se emplea en este proyecto. - En el capítulo 6, se aplica el método de la Búsqueda Tabú al problema del Acarreo Terrestre. Se detallan las variables, parámetros necesarios, así como la estructura de resolución y las diferentes funciones empleadas en Python. - El capítulo 7 se exponen los resultados obtenidos en las simulaciones. - En el capítulo 8 se recogen las conclusiones que surgen del desarrollo del proyecto. 3 2 EL TRANSPORTE INTERMODAL 2.1. Concepto de logística y modos de transporte Antes de exponer el significado de transporte intermodal, y de desarrollar dicho concepto, resulta de interés llevar a cabo una introducción sobre la logística para comprender mejor el entorno que va a ser analizado. Según la CLM (Council of Logistic Management), la logística es la parte de la cadena de suministros que planifica, implementa y controla el almacenamiento y flujo eficiente y efectivo de bienes, servicios e información relacionada desde el punto de origen al punto de consumo con el objetivo de cubrir las necesidades de los clientes. (Wu, 2007) Es en el flujo de bienes entre diferentes localizaciones, en el que este documento se centra. Según su modo, el transporte se divide en dos grandes conceptos: transporte unimodal y transporte intermodal. Atendiendo a la definición de modo de transporte como el conjunto de técnicas que utilizan vías de transporte de la misma naturaleza, se entiende como unimodal, aquel que solamente emplea un modo e intermodal por tanto aquel en el que se recurre a varios. Los diferentes modos de transporte a tener en cuenta son: - Marítimo: Emplea como medio de transporte el mar, y es considerado el óptimo para la distribución de mercancías en grandes volúmenes, entre dos localizaciones alejadas geográficamente. - Ferrocarril: Emplea la red ferroviaria del territorio en cuestión, para el traslado de la mercancía. Está por tanto muy condicionado por la infraestructura, lo cual conduce a una falta de flexibilidad que desemboca en una preferencia por el transporte marítimo para el trayecto principal. - Aéreo: Es el más moderno y como ventajas aporta la rapidez, muy útil en envíos urgentes. Supone, por otra parte, muy restrictivo a la hora de contemplar características como el volumen o el peso. - Carretera: La unidad de carga es transportada por camiones, desde el punto de recogida al punto de destino. Es el modo más flexible debido a la amplia red de infraestructura, y es por eso que se recurre a este modo tanto para el trayecto inicial de la cadena como para el final. Los siguientes gráficos muestran el porcentaje de empleo de cada uno de los modos de transporte, tanto en la Unión Europea (izqda.) como en España (dcha.). Se observa claramente cómo el transporte por carretera es con diferencia el más empleado. Ilustración 1. Proporción de los diferentes modos de transporte empleados en UE y España respectivamente (Fuente: https://contenidos.ceoe.es) El transporte intermodal 4 2.2. Definición Una vez conocidos los diferentes modos, es posible comprender mejor la definición de transporte intermodal: - “Movimiento de bienes en una misma unidad de carga o vehículo, que usa sucesivamente varios modos de transporte sin manejo de los bienes en los cambios de modos”. (Van Duin & Van Ham, 1998) - “Movimiento de camiones o contenedores sobre vagones de tren, con transporte por carretera en los tramos finales” (Nozick & Morlok, 1997) Ilustración 2.Esquema transporte intermodal: Ferrocarril - Carretera Estas dos definiciones suponen la introducción perfecta para poder comenzar a profundizar en el transporte intermodal, así como para hablar de ciertos conceptos esenciales para la resolución del problema planteado. Uno de estos conceptos fundamentales es la unidad de carga. En lo que atañe a este proyecto, se toma como dicha unidad el contenedor, el cual se analizará más adelante. Otro concepto básico para comprender el problema será la terminal. La terminal será el punto donde se lleven a cabo los trasbordos de una unidad de carga de un modo de transporte al siguiente. También es interesante introducir el concepto de depósito, o localización donde se encontrarán los contenedores, a la espera de ser recogidos por el modo de transporte pertinente. Los depósitos se suelen localizar en emplazamientos cercanos a las terminales intermodales, para facilitar el transporte entre ambos y minimizar las distancias recorridas por las empresas transportistas. 2.3. Ventajas e inconvenientes El transporte intermodal presenta ventajas en varios aspectos. Algunos de los más importantes son: - Reducción de costes: En cada una de las etapas, se decide entre el modo de transporte más económico, atendiendo a las características de cada operación. - Aumento de la seguridad: Como se ha comentado anteriormente, la unidad de carga es el contenedor. Éste se cierra herméticamente, lo cual influye de manera positiva en la reducción de robos de mercancía. Al disminuir el riesgo de hurto, se reduce sustancialmente la necesidad de inspecciones y revisiones, lo cual resulta de gran interés. Este cierre hermético de la unidad de carga favorece además la conservación de la mercancía frente a situaciones climáticas desfavorables. - Optimización del tiempo: Se realiza un análisis para decidir qué modo es más favorable teniendo en cuenta el tráfico y las condiciones que influyan en el tiempo del trayecto. - Reducción de documentación: La documentación necesaria para llevar a cabo el transporte abarca toda la combinación de modos. Es decir, se reducen los trámites al no tener que documentar los diferentes trayectos por separado. - Reducción de tiempos en cuanto a carga y descarga: La estandarización de la unidad de carga permite un ahorro de tiempo en el manejo del contenedor, al ser siempre las mismas dimensiones. Se reducen los tiempos de manipulación. 5 5 Una búsqueda tabú reactiva para la optimización del acarreo terrestre con vehículos heterogéneos - Medio ambiente: El transporte por carretera es el más contaminante. Al combinarse con otros modos de transporte, se consigue una disminución de emisiones de CO2, lo cual supone también una ventaja para la opinión social. - Reducción de plazos: Los tiempos de transporte también se analizan al decidir el medio, buscando aquel que suponga un ahorro de tiempo en cuanto a plazo de entrega. Sin embargo, el transporte intermodal también cuenta con características desfavorables para la distribución de mercancías. Alguna de las más destacables son: - Costes de manejo: Aunque el contenedor supone una ventaja debido a su estandarización, es cierto que requiere un equipo para su manipulación que supone un coste para la empresa. - Aumento de riesgo: A mayor número de modos de transporte usado, mayor probabilidad de fallo en las transiciones de uno a otro. Estos fallos pueden consistir en daños durante la manipulación, imprevistos como colas, o ventanas temporales. - Velocidad: Hay una gran diferencia en cuanto a velocidad si se analizan los diferentes medios de transporte. El aéreo o el ferrocarril son más rápidos que el marítimo y el transporte por carretera. Al combinarlos, a pesar de conseguir las ventajas antes nombradas, se percibe una reducción en la velocidad. Esta selección de ventajas e inconvenientes permiten concluir que la rentabilidad del transporte intermodal se persigue mediante el análisis de cada caso particular. Este análisis consiste en observar los modos de transporte disponibles, atendiendo a la infraestructura necesaria y al tiempo de entrega previsto. Una vez obtenidos los datos, se pasa a tomar una decisión con la combinación de modos de transporte que mejor se adapte a las necesidades de la empresa. El acarreo terrestre 12 El drayage, como ya se ha mencionado anteriormente, supone una pieza fundamental en el transporte intermodal, y se detalla a continuación una selección de algunos de los autores más relevantes. Como introducción, resulta de gran interés el trabajo de investigación de Macharis y Bontekoning (2004), en el cuál se lleva a cabo un análisis de los estudios que se han realizado en los años anteriores, atendiendo a su horizonte de planificación, destacando dos enfoques: Estratégico-táctico y operativo. Se muestra a continuación un análisis bibliográfico relacionado, en primer lugar, con el enfoque estratégicotáctico, y en segundo lugar con el enfoque operacional. - Enfoque estratégico-táctico. El enfoque estratégico-táctico se centra en el análisis de costes y calidad de servicio de las diferentes medidas que pueden adoptarse en el transporte intermodal, y en concreto, indagan en el beneficio de dichas medidas que se genera en todo el conjunto. Desde el punto de vista cronológico, destaca en primer lugar Fowkes & Nash. (1991). En dicho estudio se enfoca el análisis de costes en la relación de los diferentes puntos logísticos con la terminal, considerando la localización entra ambos como punto estratégico clave para la optimización del problema. Más adelante, Spasovic y Morlok (1993) se centran, en cambio, en los diversos precios que pueden atribuirse a las distintas tareas de acarreo, así como un análisis previo relacionado con la planificación de recursos para optimizar el problema del drayage en cuanto a costes y calidad de servicio. Para ello desarrollan un modelo lineal entero que permite llevar a porcentajes el ahorro de costes de las diversas tareas (Morlok & Spasovic, 1994). Nierat (1997) analiza la relación entre la planificación de los recursos antes comentada y el aumento de la zona de influencia terrestre del puerto marítimo, hinterland, teniendo en cuenta el factor de ocupación de los vehículos o el número de operaciones de acarreo realizadas por el camión. Taylor (2002), propone dos alternativas diferentes en cuanto a la elección de la terminal de trasbordo, y expone las conclusiones en cuanto a la optimización de costes relacionados con las distancias recorridas. Cheung (2008) analizan las diferentes políticas relacionadas con el acarreo empleadas por el gobierno, diferenciando entre dos: o 4up-4down: conductor, cabeza tractora, chasis y contenedor forman una unidad, indivisible, encargada de llevar a cabo tanto el viaje de ida como el de vuelta. o 2up-2down: También llamada política de total libertad, en la que solamente el conductor y cabeza tractora forman parte de dicho conjunto. - Enfoque operativo Este segundo enfoque se basa en buscar la resolución al problema del acarreo terrestre diario, daily drayage problem (DDP). Según Escudero-Santana (2013), su objetivo se define como minimizar los costes de todas las operaciones de acarreo que son llevadas a cabo por una empresa, o consorcio de empresas, en una región determinada a lo largo de una jornada laboral, teniendo en cuenta unos recursos limitados y una serie de restricciones a cumplir. Cuando una de las restricciones es la referida a las ventanas temporales, en la que el problema debe resolverse teniendo en cuenta los intervalos de tiempo en los que es posible realizar tanto la entrega como la recogida, se hablará de daily drayage problem with time windows (DDPTW). Otra restricción a estudiar será el tamaño del contenedor o unidad de carga. Es interesante afrontar el problema teniendo en cuenta este factor, pues tanto las empresas como los cargadores pueden recibir, o realizar encargos tanto de contenedores de 20 pies como de contenedores de 40. Este tipo de problema recibiría el nombre de Multi-size daily drayage problem (MSDDP), y es el estudiado en este trabajo. Los diferentes problemas son variantes específicas del problema de enrutamiento de vehículos VRP, 13 13 Una búsqueda tabú reactiva para la optimización del acarreo terrestre con vehículos heterogéneos denominado en inglés vehicle routing problem, y en concreto del VRPTW (vehicle routing problem with time windows), un problema considerado binario al basarse en dos situaciones: O lleva contenedor, o no lo lleva. Muchos autores han llevado a cabo proyectos de mejora para la optimización de diferentes variantes del problema de enrutamiento comentado VRPTW. Algunos de los más importantes son: o TSP: Traveling Salesman Problem With Time Windows o PDPTW: Pickup and Delivery Problem with Time Windows Para la resolución de estos problemas y de sus diferentes variantes, se recurre a tres métodos:  Métodos exactos  Heurísticas  Metaheurísticas En el siguiente capítulo se describirán en detalle los tres tipos de métodos de resolución. Por tanto, el daily drayage problema with time windows puede afrontarse como una variante de los dos problemas de enrutamiento expuestos (TSP, PDPTW). Jula et al. (2005) consideran dicho problema como un asymetric multi-traveling salesman problem with time windows (am-TSPTW), suponiendo que en vez de un sujeto realizando las diversas rutas, aparecen varios en el problema. Gronalt et al. (2003) plantean en cambio el problema como un full-load pickup and delivery problem with time windows (FLPDPTW), desarrollando una heurística híbrida para su resolución. Por otra parte, cabe destacar también la investigación relacionada con el problema de los contenedores vacíos. Smilowitz (2006), introduce la aplicación del Multi-Resource Routing Problem (MRRP) with flexible tasks, es decir, modela el problema de acarreo como un problema de enrutamiento que considera tanto contenedores llenos como vacíos, empleando tareas flexibles (no es obligatorio conocerse la localización de origen o de destino, empleadas para los contenedores vacíos, ya que puede ser irrelevante la procedencia de un contenedor vacío para aquel que lo requiere, y puede ser irrelevante su destino para aquel que quiera liberarlo tras finalizar su tarea concreta. 3.2. Problema del acarreo diario con varios tamaños de contenedores. El acarreo terrestre se realiza fundamentalmente en un área local determinada. Como ya se ha comentado anteriormente, resulta de gran utilidad para llegar a localizaciones que con otros modos de transporte sería totalmente inviable. Aporta la flexibilidad necesaria para poder tener ese alcance que permite la entrega y recogida de mercancías en clientes locales. Ya se ha introducido el concepto de acarreo diario o Daily Drayage Problem. En este apartado se profundizará en un caso particular de dicho problema, que tiene en cuenta como restricción el tamaño de la unidad de carga, sabiendo que éste podrá ser o bien de 20 pies o bien de 40. Se analiza por tanto a continuación el problema de acarreo diario con varios tamaños de contenedores, denominado en inglés como Multi-Size Daily Drayage Problem (MSDDP). La resolución de dicho problema consistirá en la búsqueda de la combinación de rutas óptima en cuanto a ahorro de costes se refiere. Los costes a tener en cuenta a la hora de buscar la solución son: - Costes de penalización: Aquellos que se aplican al inclumplir alguna de las restricciones propuestas en el modelo generado. Serán costes de penalización aquellos por incumplir las ventanas temporales, por ejemplo. - Costes fijos. Relacionados con la flota de vehículos. Dependerán del número de camiones empleados para llevar a cabo las tareas, e implican costes como el sueldo del empleado, el propio coste del camión, etc. El acarreo terrestre 14 - Costes variables: Relacionados con la distancia en kilómetros recorrida, implicando este número el gasto de combustible, desgaste de neumático y mantenimiento de los vehículos. 3.2.1. Simplificación del problema Se llevan las siguientes simplificaciones para la resolución del problema propuesto: - Entorno determinista. Las diferentes variables que aparecen en el problema son conocidas, lo que permite afrontar el problema desde un punto de vista estático. - Se consideran tareas de importación y tareas de exportación, y se añaden a dicho problema las tareas flexibles, en las que se lleva a cabo el bypass, o movimiento de contenedores vacíos entre clientes, en vez de recurrir al transporte de la terminal a las diferentes localizaciones. - Se considerará la misma velocidad (constante) durante todo el trayecto, en todos los vehículos. Todos los vehículos son de las mismas características, y misma capacidad. - Un vehículo será capaz de transportar, o bien, dos contenedores de 20’, o bien, un contenedor de 40’. - No se tendrá en cuenta el peso de los contenedores, distinguiéndose solamente entre lleno (load) y vacío (empty). - Debido a la proximidad con la que se encuentran en la realidad el depósito y la terminal, se considera en la formulación del problema una misma ubicación para ambos. Dicha localización se conoce de antemano, y es fija. - No se tendrán en cuenta tiempos de descanso de los conductores 3.2.2. Tareas reales y ficticias Es importante tener en cuenta que tanto el punto de partida de los vehículos como el punto en el que deben acabar al fin de la jornada laboral, es el depósito. Se conoce, para cada tarea, el punto de inicio y el de destino, y por tanto, cada camión tendrá asociada dos tareas ficticias: Una de inicio de jornada, y otra de finalización. Esto se lleva a cabo para asegurar, en el caso de tareas de exportación, que el vehículo se desplaza desde un punto determinado hasta el cliente, y en el caso de las tareas de importación, para modelar el regreso del camión al depósito una vez realizadas las operaciones pertinentes. Así pues, quedan determinados dos tipos diferentes de tareas, que serán de gran utilidad a la hora de modelar el problema: - Tareas reales (𝑇𝑟). Conjunto de ordenes que engloba el acarreo para llevar a cabo a lo largo de la jornada laboral. Inluyen tanto los trayectos entre clientes, como aquellos movimientos del depósito a éstos. - Tareas ficticias(𝑇𝑓). Tienen características diferentes a las reales. Sirven para modelar las limitaciones temporales en el depósito, así como los movimientos de retorno de los camiones al depósito. Por tanto, las tareas ficticias hacen posible el poder comenzar el problema con los vehículos en la terminal (o depósito). El punto de origen de éstas seran las coordenadas de tal ubicación, y las variables de distancia euclídea y tiempos de trayecto serán nulos para no influir en el análisis del problema a resolver. Así pues, si se agrupan los diferentes tipos de tareas vistos hasta ahora, se obtienen las siguientes conclusiones: - 𝑇𝑟= 𝑇𝐼 ∪ 𝑇𝐸∪ 𝑇𝐹 - 𝑇𝑓= 𝑇𝑓 𝑖𝑛𝑖 ∪ 𝑇𝑓 𝑒𝑛𝑑 - 𝑇 = 𝑇𝑓∪ 𝑇𝑟 - 𝑇𝑓∩ 𝑇𝑟= ∅ 15 15 Una búsqueda tabú reactiva para la optimización del acarreo terrestre con vehículos heterogéneos 3.2.3. Formulación Se procede a continuación a representar el modelo matemático que refleja el problema propuesto, indicándose los diferentes parámetros empleados, las variables y la función objetivo. Parámetros En caso de no cumplirse estos intervalos de tiempo, se aplicarían penalizaciones. Estas penalizaciones van a modelarse como parámetros, y se van a traducir en los diferentes costes a tener en cuenta en el desarrollo del problema. Dependiendo del retraso, la penalización será diferente, diferenciando entre: - Retraso en la recogida del contenedor [𝑐𝑤𝑎𝑖𝑡 ]: Implica una penalización que simboliza el tiempo extra que dicho contenedor debe permanecer esperando en la terminal. Supondrá una función en la que el coste incrementará linealmente con el tiempo de retraso. - Retraso en la entrega [𝑐𝑚𝑖𝑠𝑠]: Implica una penalización mayor, ya que puede significar que el siguiente medio de transporte de la cadena intermodal haya efectuado su salida, perdiéndose en ese caso el envío. Se representa como una función escalón, con coste 𝑐𝑚𝑖𝑠𝑠 si la entrega es posterior al momento 𝐿𝑖 𝐷. Ilustración 5. Ventanas temporales de las tareas. Fuente: Escudero-Santana (2013) Otros costes que se tendrán en cuenta también serán modelados como parámetros: - 𝑐𝑣: Coste fijo por vehículo usado. Penaliza el exceso de camiones empleados para la resolución del problema. - 𝑐𝑘𝑚: Coste asociado a la distancia recorrida en km. - 𝑐𝑑𝑒𝑝𝑜𝑡: Coste debido a retrasos en el retorno al depósito tras finalizar la jornada laboral Además, la jornada laboral también se modela mediante las ventanas temporales, siendo necesario que todos los vehículos acaben en el depósito dentro del intervalo de tiempo que se haya estipulado en el enunciado del problema. Variables Las variables del problema se representan en la siguiente tabla: Tabla 3. Variables del problema MSDDP 𝒅𝒊 Distancia euclídea entre origen y destino de la tarea 𝒕𝒊 Tiempo de realización de la tarea i El acarreo terrestre 16 𝒔𝒊 𝑶 𝒚 𝒔𝒊 𝑫 Tiempos de servicio de origen y destino (Carga y descarga del contenedor 𝑻𝑰 𝒚 𝑻𝑬 Tareas de importación y exportación 𝑻𝑭 Tarea flexible. Tanto origen como destino será la ubicación de un cliente determinado. [𝑬𝒊 𝑶; 𝑳𝒊 𝑶] Ventana temporal en la que se permite la carga del contenedor en origen. [𝑬𝒊 𝑫; 𝑳𝒊 𝑫] Ventana temporal en la que se permite la descarga del contenedor en destino. Las dos últimas filas de la tabla anterior muestran las ventanas temporales, las cuales caracterizan las diferentes tareas. - Variables de decisión Se emplean las siguientes variables binarias: o 𝑛𝑣𝑖= o 𝑥𝑖𝑗 = o 𝑙𝑖 𝑂= o 𝑙𝑗 𝐷= o 𝑙𝑗 𝑑𝑒𝑝𝑜𝑡 = - Función objetivo Se expone a continuación la función objetivo, que minimiza el coste total teniendo en cuenta la realización de todas las tareas, así como las diferentes penalizaciones expuestas: 1 la tarea i y la tarea j son servidas consecutivamente la tarea i y la tarea j son servidas consecutivamente 0 en otro caso en otro caso 1 existe retraso al servir en el origen la tarea i existe retraso al servir en el origen la tarea i 0 en otro caso en otro caso 1 existe retraso al servir en el destino la tarea j existe retraso al servir en el destino la tarea j 0 en otro caso en otro caso 1 el vehículo que realiza la tarea j llega al depósito con retraso 0 en otro caso 1 Si el vehículo i es usado por primera vez si el vehículo i es usado por primera vez 0 en otro caso en otro caso 17 17 Una búsqueda tabú reactiva para la optimización del acarreo terrestre con vehículos heterogéneos 19 4 MÉTODOS DE RESOLUCIÓN Son muchas las variantes que a lo largo de los años han surgido del famoso problema de ruteo VRP. Se han enumerado ya algunas de las más importantes, en las cuales, restricciones como las ventanas temporales o el tamaño de los contenedores juegan un papel fundamental. Conforme pasan los años, aumenta por tanto la investigación en lo que respecta a la búsqueda de una solución óptima para dicho problema, y se recurre para ello a diferentes caminos, diferentes métodos de resolución dependiendo del autor. En este capítulo se llevará a cabo un análisis de los diferentes métodos que existen para la búsqueda de la optimización de un problema, exponiendo sus principales características y estudiando los diferentes tipos de cada uno de ellos. 4.1. Métodos exactos Son aquellos que ofrecen una solución óptima global al problema propuesto. Computacionalmente resultan ser más lentos que cualquier heurística, y por ello solo se emplean para aquellos problemas de dimensiones pequeñas, en los que no se manejen grandes cantidades de datos. En el caso de un VRP, podrían emplearse siempre y cuando el problema supusiera una única localización para el depósito o terminal, resultando poco recomendable recurrir a un método exacto para la resolución de un problema de enrutamiento con varios emplazamientos de depósitos y terminales. Se muestran a continuación algunos de los métodos más relevantes: 4.1.1. Branch and Bound (B&B) Según Mullin & Belotti (2016)el algoritmo Branch and Bound (Ramificación y Acotación) emplea la partición recursiva para resolver problemas de optimización no-convexos, y sirve para resolver problemas que van desde la optimización lineal de enteros mixtos (Mixed-Integer Linear Optimization), donde una función objetivo lineal se minimiza sujeta a restricciones lineales e íntegramente de un subconjunto de variables (Nemhauser & Wosley, 1988), a una optimización global, donde ambas funciones objetivo son forzadas a ser enteros (Horst & Tuy, 1996) Se entiende por branch, la ramificación de uno de los nodos en dos nuevos a analizar, y dicha ramificación se lleva a cabo cuando alguna de las cotas (bound) de dichos nodos se ve modificada. El algoritmo se resume en los siguientes pasos: Paso 0. Inicialización Se inicializa la lista de nodos para explorar con el nodo raíz. Paso 1. Exploración Se pasa al siguiente nodo y se calcula su relajación lineal. Paso 2. Límite Se compara el valor obtenido en el nodo actual con el anterior. Si es menor, se procede al siguiente paso. Si es mayor que el anterior, se deshecha dicha opción y se vuelve al paso 1. Paso 3. Actualización Si la relajación del nodo actual es una solución entera, entonces se ha mejorado dicha solución. Debe tenerse en cuenta que la solución empleando este método es siempre entera. Ésta pasa a ser la nueva solución actualizada, y se vuelve a proceder desde el paso 1. Métodos de resolución 20 Paso 4. Ramificación Se ramifica el nodo actual en dos. Se comprueba la solución de ambos. Si es válida, se continúa explorando dicho nodo y se procede al paso 1 de nuevo. A continuación se expone un ejemplo gráfico de un problema resuelto mediante el método B&B Ilustración 6. Esquema de resolución de un problema mediante algoritmo Branch & Bound (Briheche, Barbaresco, Bennis, & Chablat, 2020) 4.1.2. Branch and cut El procedimiento Branch and cut resulta similar en cuanto a la búsqueda de la solución óptima mediante el desarrollo de nodos. Cada nodo representa un subproblema del tipo lineal (Linear Programming) o cuadrático (Quadratic Programming) que debe ser procesado; es decir, debe ser resuelto, comprobarse que es entero y posteriormente ser analizado. Se denominará a los nodos activos si todavía no han sido procesados. Se denominará cut (corte) a toda aquella restricción que se añada al modelo. El propósito de añadir cortes al problema no es otro que el de reducir el tamaño de dicho problema representado en los nodos. Dicho de otra forma, añadiendo cortes se persigue prescindir de nuevas ramificaciones innecesarias. Una vez aplicada la técnica de adición del plano de corte o restricción comentada, se procede a aplicar el algoritmo Branch and Bound expuesto anteriormente. 4.2. Heurísticas Se califica de heurístico al procedimiento en el que se tiene un alto grado de confianza en que encuentre soluciones de alta calidad con un coste computacional razonable, aunque no se garantice su optimalidad o su factibilidad, e incluso, en algunos casos, no se llegue a establecer lo cerca que se está de dicha situación Por tanto, una heurística es una técnica que busca soluciones siguiendo una serie de pasos previamente fijados y que se aproximan al óptimo, a un costo computacional razonable. Mediante esta breve definición se obtiene un buen resumen del concepto de método heurístico, el cual, es empleado para la resolución de problemas de optimización de un tamaño considerable. Como se expone en la definición, no garantizan la optimalidad del problema; sin embargo, ofrecen una aproximación muy buena, teniendo en cuenta el notable incremento de velocidad computacional respecto a los métodos exactos. Orientando de nuevo este tipo de método aproximado al problema de ruteo de vehículos, destacan tres 21 21 Una búsqueda tabú reactiva para la optimización del acarreo terrestre con vehículos heterogéneos variantes atendiendo a la forma en que se desarrollan: Constructivas, de mejora, y aquellas que emplean técnicas de relajación. - Constructivas: Siguiendo un criterio determinado, se va construyendo una solución admisible, progresivamente conforme avanza el algoritmo. Una de las más famosas es la heurística de ahorros. Empleada para problemas de ruteo, busca reducir la distancia global recorrida modificando el orden de los grafos, entendiéndose cada grafo como una localización. Otra heurística de este tipo sería el método del barrido, el cual fija alguna de las restricciones como por ejemplo la distancia límite a recorrer, y se “recorre” todas las opciones siguiendo un parámetro fijado de antemano al que se le denomina “ángulo”. - Heurísticas de mejora: A partir de una solución admisible, el algoritmo se dedica a proponer variaciones, ya sea en una de las rutas propuestas, modificándose el orden de las localizaciones visitadas, o bien, variando las rutas entre ellas en búsqueda de la mejora de la solución actual. - Heurísticas de relajación: Como su propio nombre indica, tratan de relajar las restricciones, es decir, discernir entre aquellas restricciones de difícil cumplimiento y aquellas que no lo suponen, pasando a formar parte las primeras de la función objetivo, multiplicadas por una penalización. Destaca la Relajación Lagrangiana, la cual lleva a cabo el procedimiento comentado para conseguir un problema acotado y acelerar la resolución. Una vez expuestos los tres tipos de heurísticas atendiendo al problema de ruteo de vehículos, resulta interesante indagar en alguno de los métodos heurísticos que existen en el campo de la optimización. Se exponen a continuación los más relevantes: 4.2.1. Método de Clark y Wright También conocido como método de ahorros, es uno de los algoritmos más recurrentes a la hora de afrontar el problema de ruteo de vehículos. Su tiempo de computación resulta ser reducido, lo cual permite ofrecer una solución rápida, y próxima al óptimo. En el caso del VRP, consiste en asignar la posición 0 al depósito (Se debe tener en cuenta que trabaja con un único depósito) y corresponderán a los diferentes clientes las posiciones desde 1 a n. Cada cliente se representa mediante una variable 𝑥𝑖𝑗, y se registra en una base de datos cada uno de los costes que hay entre el depósito y los clientes, así como todos los costes entre cada uno de los diferentes clientes. Se designan mediante 𝑐𝑖𝑗. El algoritmo partirá de la solución admisible que une cada uno de los clientes con el depósito, es decir, la solución inicial no es otra que tantas rutas como clientes, siendo dicha ruta: 𝑑𝑒𝑝𝑜𝑡 − 𝑐𝑖 ; 𝑐𝑖 –𝑑𝑒𝑝𝑜𝑡 ꓯ i = 1,…,n Ilustración 7. Solución inicial de Clark & Wright Coste inicial: Búsqueda Tabú 28 apartado 5.2.3. Ejemplo. Sea la solución con la que se trabaja un vector de 5 posiciones: 𝑥𝑖 =1,..,5 ꓯi 1 4 3 5 2 Ilustración 13. Solucion inicial Se genera una lista tabú, inicialmente vacía, con los posibles movimientos: 1 2 3 4 5 1 2 3 4 5 Ilustración 14. Lista Tabú de 5 elementos Si se llevara a cabo en la siguiente iteración en la figura 10, la vecindad 1-5 (intercambio de dichos elementos), y asumiendo que la prohibición de dicho movimiento es durante 3 ciclos en este ejemplo, la lista quedaría actualizada como en la ilustración 11: 5 4 3 1 2 Ilustración 15. Solución resultado de aplicar vecindad 1-5 1 2 3 4 5 1 3 2 3 4 5 Ilustración 16. Lista Tabú actualizada En el siguiente ciclo, si ahora se aplica un intercambio de los elementos 5 y 3, el vector solución actualizado y la nueva lista actualizada quedarán de la siguiente manera: 3 4 5 1 2 29 29 Una búsqueda tabú reactiva para la optimización del acarreo terrestre con vehículos heterogéneos Ilustración 17. Vector solucion actualizado 1 2 3 4 5 1 3 2 2 3 4 5 Ilustración 18. Lista Tabú actualizada. Segundo ciclo Con esto, se consigue ahorrar tiempo computacional, ya que al estar prohibidos temporalmente los movimientos registrados en la lista, se reduce el número de acciones que deben ejecutarse en cada uno de los ciclos. 5.2.2. Vecindad En el apartado anterior ya se introduce el concepto de vecindad mediante el ejemplo propuesto. El algoritmo tabú emplea para la búsqueda del óptimo un método iterativo por el cual va aplicando en cada ciclo intercambios entre los diferentes elementos que componen la solución. Cada intercambio o vecindad supone una variación de la función objetivo, y será entonces necesario valorar si dicha modificación resulta una función mejor o peor que la anterior. Así pues, se entiende por vecindad ese intercambio entre dos elementos de la solución, siendo tres los conceptos de vecindad más populares: - Adjacent Swap: Una solución S de n elementos tiene n-1 vecinos. Se realizan intercambios exclusivamente entre aquellos elementos adyacentes. Ilustración 19. Adjacent Swap - General Swap: Una solución S de n elementos tiene 𝑛(𝑛−1) 2 vecinos. Un elemento puede intercambiarse por cualquiera de los demás. Búsqueda Tabú 30 Ilustración 20. General Swap - Insertion: Una solución S de n elementos tiene (𝑛 − 1)2 vecinos. Se extrae un elemento y se “inserta” en una determinada posición. Ilustración 21. Insertion 5.2.3. Niveles de aspiración Hay ocasiones en las que interesa otorgar al algoritmo cierta flexibilidad. El criterio de aspiración permite determinar ciertas condiciones en las cuales está permitido incluir alguno de los movimientos restringidos que se encuentran en la lista tabú. Los niveles de aspiración se clasifican en dos: - Aspiraciones de movimiento: Se invalida la restricción en la lista tabú de un cierto movimiento, en caso de que se cumpla el criterio. - Aspiraciones de atributo: Se invalida la restricción en la lista de un determinado atributo. Según Guerrero & Escudero Santana (2014) , los criterios de aspiración surgen por tres motivos: - Si todos los posibles movimientos se consideran tabú, entonces se deberá escoger el movimiento “menos tabú” de todos ellos. Esto es que si se tienen varios movimientos restringidos, se escogerá el movimiento que le resten menos iteraciones para volver a ser permitido. - En el caso de que el valor de la función objetivo de una solución, sea mejor que el mejor valor obtenido hasta el momento. Por ejemplo, un movimiento m es aceptado sí, en un problema de minimización, el valor de la solución x resultante es menor que el menor coste obtenido hasta entonces. - Para los casos en los que un atributo de aspiración para alcanzar una solución x se satisface si la dirección para en x otorga una mejora y el actual movimiento también es de mejora. En ese caso, se toma a x como posible candidato. 5.2.4. Estrategias de búsqueda El algoritmo de la búsqueda tabú lleva asociada la interacción entre la memoria a corto plazo y a largo plazo. En cuanto a la memoria a corto plazo, ha sido analizado el método por el cual, mediante la lista tabú, se 31 31 Una búsqueda tabú reactiva para la optimización del acarreo terrestre con vehículos heterogéneos almacenan aquellos movimientos recientes para no recaer en óptimos locales. Esta es la estrategia fundamental que dicha memoria sigue. Mientras que la memoria a corto plazo se orienta a la búsqueda de un óptimo local, la memoria a largo plazo tendrá como fin encontrar un óptimo global. Así, en este apartado se analizan las dos estrategias más importantes en cuanto al uso de memoria a largo plazo. En búsqueda tabú, se entiende por memoria a largo plazo el registro y almacenaje de la frecuencia con que un determinado atributo aparece en una región de soluciones determinada. La identificación de diferentes regiones es la que rige este tipo de uso de memoria. Martí (2003) define estas dos estrategias de la siguiente manera: - Diversificación: consiste en visitar nuevas áreas no exploradas del espacio de soluciones. Para ello se modifican las reglas de elección para incorporar a las soluciones atributos que no han sido usados frecuentemente. - Intensificación: consiste en regresar a regiones ya exploradas para estudiarlas más a fondo. Para ello se favorece la aparición de aquellos atributos asociados a buenas soluciones encontradas 5.3. Búsqueda tabú reactiva 5.3.1. Definición Según Battiti y Tecchiolli (1994), la búsqueda tabú reactiva (RTS) aumenta la robustez del algoritmo, y se basa en un simple mecanismo de adaptación del tamaño de la lista tabú acorde con las propiedades del problema de optimización. Así, las configuraciones visitadas durante la búsqueda y el correspondiente número de iteraciones se guardan en la memoria para que, tras la elección del último movimiento, se pueda verificar la repetición de las configuraciones y calcular el intervalo entre dos visitas. El mecanismo básico de “reacción” rápida aumenta el tamaño de la lista cuando ciertas configuraciones se repiten. Esto va acompañado de un mecanismo de reducción más lento para disminuir aquellas regiones del espacio de búsqueda que no necesiten tamaños tan grandes. En resumen, se trata de una variación del algoritmo en la que los tamaños de la lista tabú pasan a variar dependiendo de las necesidades en cada momento durante la ejecución del mismo. 5.3.2. Características La búsqueda tabú reactiva constituye una variante de gran interés en lo que respecta a la búsqueda del óptimo, siendo de gran utilidad a la hora de mantener el control sobre posibles movimientos cíclicos. Como se ha comentado anteriormente, tras cada iteración se almacena en memoria la configuración de las soluciones obtenidas. Tras esto, se valora si el procedimiento ha quedado “estancado” en un ciclo, situación que ocurre al dar con un óptimo local (atractor). Cuando se sospecha de la presencia de un atractor fuerte, el método RTS añade un mecanismo de diversificación, descrito en el apartado anterior, que permite abandonar la solución actual, y seguir profundizando en el análisis de zonas que no han sido tocadas por el método hasta ese momento. Pueden analizarse tres procedimientos distintos a la hora de ejecutar el método RTS: 1. Mecanismo de reacción básico. Consiste en aumentar la lista tabú cuando las configuraciones de la solución actual llevan repitiéndose durante un número determinado de iteraciones. Este mecanismo también puede encargarse de reducir dicha lista en caso de que no aparezca una necesidad de aumento de la misma. 2. Mecanismo de diversificación. A lo largo de la búsqueda del óptimo, es frecuente que el método de búsqueda caiga en un óptimo local o atractor (Battiti, 1994). El atractor puede desencadenar en una Búsqueda Tabú 32 búsqueda cíclica, en la cual, al cabo de un número de iteraciones N, la solución analizada siga siendo la misma. Para evitar este comportamiento cíclico, se aplica un mecanismo de diversificación por el cual, como se ha descrito en el apartado anterior, se pasan a analizar nuevos conjuntos de soluciones abandonando así el óptimo local. 3. Restricción del área de búsqueda. Un procedimiento interesante para huir de los óptimos locales es el de restringir la trayectoria a una determinada área del espacio de búsqueda, e ir variando dicha área de manera aleatoria. Battiti et al. (1994) introducen el concepto de caos para describir dicho procedimiento, en el cual, hablan de atractores caóticos, caracterizados por la “contracción de áreas”, por la cual, «diferentes trayectorias comienzan con condiciones iniciales diferentes, siendo comprimidas en un área limitada del espacio de configuraciones fijado, con dependencia de las condiciones iniciales, por lo que las diferentes trayectorias acaban divergiendo». 5.3.3. Caos y exponente de Lyapunov Como se expone en el apartado anterior, RTS recurre a dos conceptos relacionados con la rama de los sistemas dinámicos: Caos y el exponente de Lyapunov. El concepto de Caos es empleado para muchas aplicaciones en ingeniería informática, en lo que respecta a sistemas dinámicos. Se muestra a continuación una definición matemática del concepto expuesta en la Universidad Politécnica de Madrid (Escribano Iglesias & Giraldo Carbajo): Se dice que un sistema dinámico (X, f) es caótico si - es sensible respecto a las condiciones iniciales - es topológicamente transitivo, - sus puntos periódicos son densos en X. Si (X, f) es sensible respecto a las condiciones iniciales, pequeños errores en la estimación de valores de la función se pueden ampliar considerablemente al iterarla. Si (X, f) es topológicamente transitivo no puede descomponerse en dos subconjuntos disjuntos invariantes con interior no vacío. (Si f posee una órbita densa entonces (X,f) es topológicamente transitivo). Por tanto, si un sistema dinámico es caótico, tiene una componente de impredicibilidad, una componente de irreducibilidad pero aun así tiene una tercera componente de regularidad. Según Battiti (1994), sea una función g que mapea un punto en el paso n a un punto en el paso n + 1, 𝑔𝑘(x) se define como el mapeo obtenido al interactuar g, k veces. Si se empieza con configuraciones cercanas 𝑥0 y 𝑥0+ 𝜀, el exponente de Lyapunov λ se define por la relación: Si λ > 0, los puntos iniciales divergen exponencialmente, y si las trayectorias se mantienen dentro de una región en el espacio, uno obtiene lo que se llama caos determinístico. Estos dos conceptos permiten al método de búsqueda una acción aleatoria, a pesar de ser en realidad determinística, y sirve de gran utilidad para escapar de aquellas iteraciones en las que se 33 33 Una búsqueda tabú reactiva para la optimización del acarreo terrestre con vehículos heterogéneos ha entrado en un ciclo, es decir, en un análisis del mismo óptimo local durante un número límite de iteraciones. 5.3.4. Procedimiento y método de escape Así pues, el algoritmo propuesto que emplea estos conceptos se expone de la siguiente manera: 1. Evaluación de los posibles movimientos elementales a partir de la configuración actual 2. Búsqueda de la última configuración analizada y decisión sobre la ejecución del mecanismo de escape 3. En caso de no ejecutarse el escape, búsqueda del mejor movimiento 4. En caso afirmativo, ejecución de una serie de movimientos aleatorios Cuando se lleva a cabo una repetición en el movimiento, la lista tabú aumenta, consiguiéndose así a largo plazo evitar en próximas iteraciones la recaída en un movimiento cíclico. La estrategia de escape propuesta por Battiti (1994) consiste en realizar un determinado número de movimientos aleatorios, proporcionales al número promedio de movimientos entre ciclos. Ilustración 22. Función escape del algoritmo RTS en Pascal. (Battiti et al, 1994) El pseudo-código de la función escape expuesto en la Figura (22), se resume en lo siguiente: o Reinicio del desglose en la estructura de memoria o Generar un número aleatorio en el rango (0,1) o Durante un número determinado (steps), generar vecindades nuevas en la solución o Actualizar la lista tabú. En resumen, la búsqueda tabú reactiva supone una aplicación de los sistemas dinámicos al método clásico de la búsqueda tabú, aportando a ésta la independencia para generar cambios en la lista de movimientos tabú en función de la situación. Esto, permite una mayor versatilidad en cuanto a la búsqueda del óptimo, así como un incremento de la eficiencia. 35 6 BÚSQUEDA TABÚ REACTIVA APLICADA AL ACARREO TERRESTRE 6.1. Planteamiento del problema El fin de este proyecto consiste en aplicar la búsqueda tabú reactiva, comentada y analizada en el capítulo anterior, al problema del acarreo diario con vehículos heterogéneos. Ya se ha hablado de la dificultad de dicho problema, ya que es necesario trabajar con números elevados de clientes, surgiendo de cada uno de ellos un cierto número de tareas y operaciones de acarreo que deben ser ejecutadas cumpliendo ciertas restricciones, entre las cuales las más importantes son las ventanas temporales y el tamaño de la unidad de carga. Es por ello que un método dinámico como el RTS ofrece, en un tiempo razonable como se apreciará más adelante, esa solución buscada, la cual sería complicada de obtener siguiendo otras técnicas de optimización. Para comenzar con el planteamiento del problema, se muestran los parámetros que acotan el tamaño del mismo: - Número de vehículos: El parámetro num_veh indica el tamaño de la flota de vehículos con la que cuenta el depósito. Dicha dimensión de la flota influirá en la capacidad de variación de la solución. El problema contará con más flexibilidad cuanto mayor sea en número de vehículos, pues habrá más opciones en cuanto a combinación de tareas. A modo de ejemplo, si la flota cuenta con tan solo un camión, el problema se reduciría a un problema similar al TSP, en el que el mismo vehículo debe pasar por todos los puntos. Por otro lado, una flota amplia permitirá una combinación de muchas rutas más pequeñas. - Número de tareas: El parámetro num_tasks dimensiona el problema en cuanto al tamaño y dificultad. La solución variará dependiendo del número de tareas u operaciones a realizar, y de ello dependerá a su vez la elección de una flota de un tamaño diferente. Este proyecto cuenta con dos tipos de tareas: exportación e importación, cada una de ellas, dividida a su vez en dos tipos de operaciones: Recogida (Pick-up) y Entrega (Delivery), de las cuales en algunos casos, serán ficticias, como ya se ha comentado en el capítulo del acarreo terrestre. Además de los parámetros que se enfocan en la dimensión del problema, y que conciernen a la teoría del acarreo, existen en este proyecto un segundo conjunto de parámetros, los cuales resultan de interés tanto a nivel computacional, como a la hora de permitir al usuario una mayor flexibilidad. Dichos parámetros son las penalizaciones. En muchos métodos de optimización se recurre a penalizaciones, las cuales posteriormente se emplean en la función de evaluación para aportar más importancia a ciertos aspectos de la solución que en determinados casos pueden cobrar más o menos relevancia. Es posible que en futuras aplicaciones, el programa en cuestión sea empleado para realizar la gestión de la flota, y sea interesante dar más importancia al cumplimiento de los horarios (ventanas temporales) que al precio del conjunto resultante de las rutas. Las penalizaciones permiten asignar costes en función de los intereses del usuario, y además permiten al método descartar soluciones de una manera más rápida, para encontrar el óptimo de una manera más eficiente. Así pues, se exponen las penalizaciones empleadas como parámetros: Búsqueda Tabú Reactiva aplicada al acarreo Terrestre 36 - Penalización por número de camiones (penal_trucks): Se asigna un determinado coste por cada vehículo que se añade a la solución. Dicho coste se acumula con el número de vehículos empleados, y más adelante se añade a la evaluación de la solución. Con ello, el programa puede discernir entre la opción de utilizar más o menos vehículos para el acarreo. - Penalización ventanas temporales (penal_retraso): Durante la búsqueda del óptimo, muchas de las soluciones incumplirán las restricciones relacionadas con las ventanas temporales, ya sea en cuanto a retrasos, o bien debido a llegadas más tarde de lo que el intervalo indicado expone. Es importante penalizar dicho incumplimiento, y aplicar un coste a la solución si esto ocurre. Dependiendo de la decisión del usuario, podrá asignarse una penalización más o menos alta para que el programa decida sobre la importancia del retraso en la búsqueda del óptimo. - Penalización del orden: El parámetro penal_orden se emplea exclusivamente para dirigir la solución a la región de admisibilidad. Como se expuso anteriormente, es necesario realizar en primer lugar una recogida antes del reparto. Cualquier cliente debe tener antes la orden pick-up que la orden delivery. El inverso es inadmisible, y una manera de evitar dicha situación es penalizándola con un número de orden superior al rango de soluciones, para conseguir que el algoritmo huya de esas soluciones. Como ya se ha comentado, las diferentes penalizaciones expuestas anteriormente se emplean a modo de coste que se incluye posteriormente en la función de evaluación. En segundo lugar, cabe destacar el papel de los costes en el problema. Como ya se ha comentado, el objetivo es reducir los costes en el acarreo de los vehículos mediante la reducción de los kilómetros recorridos, así como de los vehículos empleados para las tareas. Por ellos, los diferentes costes implicados son: - Coste por kilómetro recorrido. - Coste por vehículo - Costes asociados a las penalizaciones (Ventanas temporales, tareas sin realizar) Los costes se emplean en la función evaluación, la cual se explica en el siguiente apartado, y juegan el papel principal en el resultado (función objetivo). 6.2. Codificación general del algoritmo en Python Se expone a continuación el esquema empleado para la resolución del problema: 37 37 Una búsqueda tabú reactiva para la optimización del acarreo terrestre con vehículos heterogéneos Ilustración 23. Esquema general resolución del problema (Elaboración propia) En primer lugar, se designa valor a los diferentes parámetros indicados en el apartado anterior. Una vez indicados los diferentes pesos de las penalizaciones, y el número de vehículos y tareas, el programa pasa a leer los diferentes datos, obteniendo la información en este caso de una hoja Excel. En ella se halla toda la información pertinente. Mediante la librería Pandas, Python permite leer de forma sencilla datos de una hoja Excel: Se expone a continuación la función Python encargada de leer el problema: Ilustración 24. Funcion Read_problem codificada en Python Una vez realizada la tarea de lectura de datos, el siguiente paso será adaptar dichos datos al problema que atañe a este proyecto. Para ello, el programa Python cuenta, en primer lugar, con dos funciones llamadas read_tasks y read_operations, encargadas de registrar en una estructura de datos la información obtenida de la hoja de Búsqueda Tabú Reactiva aplicada al acarreo Terrestre 44 Ilustración 31. Pseudo-código del mecanismo RTS 45 7 RESULTADOS Una vez se han desarrollado los aspectos relacionados tanto con el problema como con el método de resolución empleado, se procede a exponer los diferentes resultados obtenidos mediante el programa implementado en Python. El programa en cuestión obtiene los datos relevantes para la resolución de una hoja Excel llamada 'B2_R1_010_F.xlsx'. Dicho documento consta de 7 enunciados, en los cuales aparecen variaciones relacionadas con las ventanas temporales de los diversos clientes, así como diferentes intervalos de las mismas. Otra de las variaciones de los enunciados es el número de tareas que requieren operaciones con contenedores vacíos. Resulta interesante especificar las características del ordenador con el que se pone a prueba el algoritmo, ya que influye en el tiempo de computación. Dichas características se exponen a continuación: Ordenador: Packard Bell EasyNote TS44HR Procesador: Intel® Core™ i5-2450M CPU @2.50GHz Memoria RAM: 4,00GB Sistema Operativo: Windows 10 Home 64bits. A continuacion se mostrarán siete casos diferentes, los cuales han sido resueltos en primer lugar mediante la búsqueda tabú (TS) y posteriormente se ha aplicado la búsqueda tabú reactiva (RTS). Se considera una flota máxima de ocho vehículos El uso de cada camión adicional se penaliza con un coste de 10 u.m. El km recorrido supone un coste de 1 u.m. Las tablas mostrarán, para cada hoja Excel: - Función objetivo - Número de bypass realizados - Número de camiones - Tamaño final de la lista tabú - Intervalo de las ventanas temporales Se adjuntará además, para cada caso, una gráfica obtenida en Python con la evolución de la función objetivo y el número de Bypass considerados en cada iteración. 7.1. Resultados para 500 iteraciones y flota máxima de 8 camiones - Caso 1. F.O BYPASS FLOTA LISTA TABU TW RTS 530.94 0 6 187 30/60 TS 636.28 1 6 10 30/60 Tabla 4. Resultados para el caso 1 Resultados 46 Ilustración 32. Izqda: Evolución de la f.o. mediante TS. Dcha: Mediante RTS El algoritmo RTS (derecha) no haya una mejora en la solución hasta pasadas las 300 iteraciones, como se aprecia en la imagen ampliada. No se contemplan acciones de bypass, por lo que no se muestra la gráfica más ampliada. Las ventanas temporales (30 ud. temporales en el caso de tareas con contenedores llenos, 60 para los contenedores vacíos), no permiten flexibilidad en la solución, ya que son intervalos de tiempo muy estrechos. Diferencia de 100 uds. Monetarias entre el coste obtenido mediante la búsqueda tabú y el obtenido mediante la búsqueda tabú reactiiva - Caso 2. F.O BYPASS FLOTA LISTA TABU TW RTS 517.86 0 7 128 60 TS 543.809 0 7 10 60 Tabla 5. Resultados para el caso 2 Ilustración 33. Izqda: Evolución de la f.o. con TS. Dcha: Gráfica RTS - Caso 3. 47 47 Una búsqueda tabú reactiva para la optimización del acarreo terrestre con vehículos heterogéneos F.O BYPASS FLOTA LISTA TABU TW RTS 489.45 1 6 199 90 TS 492.38 1 6 10 90 Tabla 6. Resultados para el caso 3. Ilustración 34. Izqda. Evolución (RTS) de f.o. para el caso 3. Dcha: Evolución del bypass Ilustración 35. Comparativa de evolución de la f.o entre RTS (izqda.) y TS (dcha.) - Caso 4. F.O BYPASS FLOTA LISTA TABU TW RTS 500.39 0 6 202 120 TS 534.37 0 7 10 120 Tabla 7. Resultados para el caso 4. Resultados 48 Ilustración 36. Izqda: Evolucion f.o. para el caso 4. Dcha: Gráfica ampliada - Caso 5. F.O BYPASS FLOTA LISTA TABU TW RTS 363.71 4 5 168 240 TS 468.15 4 4 10 240 Tabla 8. Resultados para el caso 5. Ilustración 37. Izqda: Evolución f.o. en el caso 5. Dcha. Evolución Bypass (RTS) 49 49 Una búsqueda tabú reactiva para la optimización del acarreo terrestre con vehículos heterogéneos Ilustración 38. Evolución de f.o. en para el caso 5 (TS) En este caso 5, se muestran las gráficas resultado por separado, y tras ser ampliadas. Así, se consigue apreciar el resultado, el cual indica una clara disminución de los costes, y una clara diferencia con respecto al resto. En este supuesto práctico, el método tabú reactivo ha recurrido al abandono del óptimo local en sucesivas ocasiones. Por otra parte, el bypass cobra protagonismo, llegándose a realizar 5 acciones alrededor de la iteración 200. De este quinto caso obtenemos el mejor resultado, y el que mejor refleja el comportamiento del algoritmo. En la ilustración 35 se aprecia el desarrollo de la búsqueda tabú básica. Mediante este método se consigue una función objetivo de 468 u.m - Caso 6. F.O BYPASS FLOTA LISTA TABU TW RTS 507.54 0 6 226 120 TS 654.34 0 7 10 120 Tabla 9. Resultados para el caso 6. Ilustración 39. Izqda: Evolucion f.o. para el caso 6. Dcha: Gráfica ampliada (RTS) Resultados 50 Ilustración 40. Evolución de la f.o. mediante TS - Caso 7. F.O BYPASS FLOTA LISTA TABU TW 425.71 2 5 194 240 Tabla 10. Resultados para el caso 7. Ilustración 41 Izqda: Evolución f.o. en el caso 5. Dcha. Evolución Bypass En este caso 7 se aprecia de nuevo cómo el aumento de las ventanas temporales influye en la función objetivo. Además, se aprecia de nuevo cómo el algoritmo escapa de los óptimos locales, y propone nuevas áreas para encontrar el nuevo óptimo. El programa discierne entre el número de tareas ficticias solucionadas mediante bypass, concluyéndose en 2 al final de la ejecución. 51 8 CONCLUSIONES Por último, queda comentar las conclusions obtenidas durante el desarrollo de este proyecto. Para ello, se resume en primer lugar cada uno de los puntos en los que se ha profundizado. En primer lugar, se ha indagado en el transporte intermodal, y en concreto en el acarreo terrestre, para conocer el ámbito en el que este trabajo puede aportar mejoras en la logística, y se ha comentado la importancia del transporte por carretera a la hora de conseguir flexibilidad y un mayor alcance en las tareas de distribución. Seguidamente se ha expuesto un capítulo sobre el acarreo terrestre, analizando sus principales características, a saber: Conceptos de exportación e importación, el camión como vehículo empleado, consideración de los contenedores de 20’ y 40’ como unidad de carga, ventanas temporales, tareas ficticias y concepto de bypass. Se ha realizado más adelante un análisis de los diversos métodos de optimización, distinguiendo entre métodos exactos, heurísticas y metaheurísticas, y en concreto se ha analizado el método de la búsqueda tabú. Por último, se ha estudiado la búsqueda tabú reactiva, la cual ha sido la herramienta para la resolución de este problema. Tras ver los resultados obtenidos mediante un código Python, en el capítulo anterior, se obtienen las siguientes conclusiones: - Al variar la lista tabú mediante el mecanismo RTS, el programa escapa de óptimos locales, analizando nuevas áreas de soluciones. Se obtiene así una mejora en la función objetivo, lo cual se traduce en una disminución de los costes. - La técnica del bypass cobra importancia a medida que aumentan las tareas con contenedores vacíos, ya que los vehículos tienen la opción de trasladar dicha unidad de carga de un cliente a otro sin necesidad de pasar por el depósito. - A pesar de contar con una flota ficticia de 8 vehículos, se aprecia que en el caso más costoso, el programa requiere solamente 7, llegando a necesitar 5 vehículos en los últimos ejemplos. - Cuanto mayor es el intervalo de las ventanas temporales, menor es el coste de la actividad. Una mayor franja horaria de los clientes permite una mayor versatilidad a la hora de mejorar las rutas de los vehículos. 8.1. Lineas de futuro Este método de optimización supone una introducción a una técnica que cada vez se desarrolla con mayor velocidad: la inteligencia artificial. La búsqueda tabú reactiva se basa en el uso de memoria del algoritmo tabú, para discernir en la toma de decisión de, en este caso, el tamaño de la lista en la que almacena los movimientos prohibidos. Este proyecto supone una pequeña introducción al campo de la inteligencia artificial, y el desarrollo teórico del mismo resulta un campo de gran interés para aplicar dicha técnica, y conseguir mejores resultados requiriendo a su vez tiempos de computación mucho menores. 53 REFERENCIAS Arango Serna, M. D., Gil Gómez, H., & Zapata Cortes, J. A. (2009). Lean logistics applied to transport in the miner sector. Boletín de Ciencias de la Tierra(25), 121-136. Autor. (2012). Este es el ejemplo de una cita. Tesis Doctoral, 2(13). Autor, O. (2001). Otra cita distinta. revista, pág. 12. Battiti, R., & Tecchiolli, G. (1994). The Reactive Tabu Search. ORSA Journal on computing(6(2)), 126-140. Briheche, Y., Barbaresco, F., Bennis, F., & Chablat, D. (2020). Branch-and-Bound Method for Just-in-Time Optimization of Radar Search Patterns. Cheung. (2008). An attributedecision model for cross-border drayage problem. Transportation Research Part E- Logistics and Transportation Review(44 (2)), 217-234. Escribano Iglesias, M., & Giraldo Carbajo, A. (s.f.). Departamento de Matemática Aplicada para las Tecnologías de la Información y las Comunicaciones. Obtenido de http://www.dma.fi.upm.es/docencia/plan96/sistemas_dinamicos/ Escudero Santana, A. (2013). Mejoras en el transporte intermodal: Optimización en tiempo real del acarreo terrestre, Capítulo 5. El problema del Acarreo Terrestre. Tesis Doctoral, ETS de Ingeniería, Sevilla. Fowkes, A. S., & Nash, C. (1991). Analysing demand for rail travel. Avebury: Aldershot, Hants; Brookfield, Vt. Glover, F. (1986). Future Paths for Integer Programming and Links to Artificial Intelligence. Computers & Operations Research(13), 533-549. Gronalt, M., Hartl, R. F., & Reinmann, M. (2003). New savings based algorithms for time constrained pickup and delivery of full truckloads. European Journal of Operational Research, 151(3), 520-535. Guerrero Herruzo, J., & Escudero Santana, A. (2014). Resolución del problema del Acarreo Terrestre mediante la implementación de un algoritmo basado en la metaheurística de Búsqueda Tabú. Trabajo Fin de Grado, ETSI. Universidad de Sevilla, Departamento de Organización y Gestión de Empresas II, Sevilla. Horst, R., & Tuy, H. (1996). Global optimization: deterministic approaches. Springer. Jula, H., Dessouky, M., Ioannou, P., & Chassiakos, A. (2005). Container movement by trucks in metropolitan networks: modeling and optimization. Transportation Research Part E- Logistics and Transportation Review(41(3)), 235-259. Macharis, C., & Bontekoning, Y. M. (2004). Opportunities for OR in intermodal freight transport research: A review. European Journal of operational research, 153(2), 400-416. Martí, R. (2003). Procedimientos metaheurísticos en optimización combinatoria. En Matemátiques (Vol. 1, págs. 3-62). Valencia: Universidad de Valencia. Melián, B., Pérez, J. A., & Moreno Vega, J. M. (2003). Metaheurísticas: Una visión global. Inteligencia Artificial. Revista Iberoamericana de Inteligencia Artificial, 7(19), 0. Morlok, E. K., & Spasovic, L. N. (1994). Redesigning rail-truck intermodal drayage operations for enhanced service and cost performance. Journal of the Transportation Research Forum. Mullin, T., & Belotti, P. (2016). Using branch-and-bound algorithms to optimize selection of a fixed-size breeding population under a relatedness constraint. Tree Genetics & Genomes(12(4)). Nemhauser, G. L., & Wosley, L. A. (1988). Integer and combinatorial optimization. New York: Wiley- Interscience. Nierat, P. (1997). Market area of rail-truck terminals: Pertinence of the spatial theory. Transportation Anexos 60 'id_n': index + self.num_tasks + 1, 'task_id': index + 1, 'type': 'oef', 'position': 'depot', 'xy': [task_i['Dx'], task_i['Dy']], 'x': task_i['Dx'], 'y': task_i['Dy'], 'TWe': task_i['TWD1'], 'TWl': task_i['TWD2'], 'st': task_i['Unload'], 'container_size': -task_i['CS'], 'charge': 0, 'paired_id': 'oe%d' % (index + 1), 'paired_empty': None} # id += 1 # self.O_OE.append(operation_pickup) # self.O_OE_F.append(operation_delivery) self.O_P_V.append(operation_pickup) self.O_D_F.append(operation_delivery) for index, task_i in self.T_IE.iterrows(): task_i = task_i.to_dict() operation_pickup = {'id': 'ief%d' % (index + 1), 'id_n': (index + 1), 'task_id': (index + 1), 'type': 'ief', 'position': 'depot', 'xy': [task_i['Ox'], task_i['Oy']], 'x': task_i['Ox'], 'y': task_i['Oy'], 'TWe': task_i['TWO1'], 'TWl': task_i['TWO2'], 'st': task_i['Load'], 'container_size': task_i['CS'], 'charge': 0, 'paired_id': 'ie%d' % (index + 1), 'paired_empty': None} # id += 1 operation_delivery = {'id': 'ie%d' % (index + 1), 'id_n': index + self.num_tasks + 1, 'task_id': index + 1, 'type': 'ie', 'position': 'customer', 'xy': [task_i['Dx'], task_i['Dy']], 'x': task_i['Dx'], 'y': task_i['Dy'], 'TWe': task_i['TWD1'], 'TWl': task_i['TWD2'], 'st': task_i['Unload'], 'container_size': -task_i['CS'], 'charge': 0, 'paired_id': 'ief%d' % (index + 1), 'paired_empty': None} # id += 1 self.O_P_F.append(operation_pickup) self.O_D_V.append(operation_delivery) 61 61 Una búsqueda tabú reactiva para la optimización del acarreo terrestre con vehículos heterogéneos depot = {'id': 'depot', 'id_n': 0, 'task_id': 0, 'type': 'depot', 'position': 'depot', 'xy': self.depot_xy, 'x': self.depot_xy[0], 'y': self.depot_xy[1], 'TWe': self.depot_TW[0], 'TWl': self.depot_TW[1], 'st': 0, # <-------------------------------------- 'container_size': 0, 'charge': 0, 'paired_id': None, 'paired_empty': None} self.O = self.O_P + self.O_D + self.O_P_V + self.O_D_V + self.O_P_F + self.O_D_F + [depot] self.df_O = pd.DataFrame(self.O) def create_initial_solution(self): current_solution = [] for order in self.O: current_solution.append(order['id']) return current_solution # Escribo self donde habria puesto tabusearch # Para tener en cuenta las ventanas temporales vamos a fijar una velocidad de 50 km/h simulando los limites de velocidad en una ciudad def eval_function(self, current_solution): penal=0 pickup_done = [] delivery_done = [] for h in range(len(self.O)): pickup_done.append(0) delivery_done.append(0) for i in range(0, len(current_solution)): for j in range(0, len(self.O)): if current_solution[i] == self.O[j]['id']: if self.O[j]['id'][0] == 'p': if pickup_done[int(self.O[j]['id'][1:3])] == 0: pickup_done[int(self.O[j]['id'][1:3])] = 1 elif self.O[j]['id'][0] == 'd' and self.O[j]['id'][1] != 'e': if pickup_done[int(self.O[j]['id'][1:3])] == 0: penal += self.penal_orden #solution[i] = 'p%d' % int(self.O[j]['id'][1:3]) # Realizo el cambio en current solution #pickup_done[int(self.O[j]['id'][1:3])] = 1 else: delivery_done[int(self.O[j]['id'][1:3])] = 1 # Hacemos lo mismo con las operaciones de contenedor vacio TIPO 3 if self.O[j]['id'][0:2] == 'oe' and self.O[j]['id'][2] != Anexos 62 'f': #if delivery_done[int(self.O[j]['id'][2:4])-10] == 1: if pickup_done[int(self.O[j]['id'][2:4])] == 0: pickup_done[int(self.O[j]['id'][2:4])] = 1 elif self.O[j]['id'][0:3] == 'oef': if pickup_done[int(self.O[j]['id'][3:5])] == 0: penal += self.penal_orden # Hacemos lo mismo con las operaciones de contenedor vacio TIPO 4 if self.O[j]['id'][0:3] == 'ief': if pickup_done[int(self.O[j]['id'][3:5])] == 0: pickup_done[int(self.O[j]['id'][3:5])] = 1 elif self.O[j]['id'][0:2] == 'ie' and self.O[j]['id'][2] != 'f': if pickup_done[int(self.O[j]['id'][2:4])] == 0: penal += self.penal_orden # Vamos a definir una lista llamada truck_list en la que se ve el estado ACTUAL de los camiones bypass = 0 truck_list = [] trucks = [] km_list = [] t_f = [] posicion_actual = [] for i in range(0, self.nv): truck_list.append([0, 0]) trucks.append([]) km_list.append(0) t_f.append(0) posicion_actual.append([35, 35]) velocidad_truck = 50 penaliza_retraso = 0 for i in range(0, len(current_solution)): for j in range(0, len(self.O)): asignado = False # Cada 'p' se descarta una vez ha sido asignada en un camion enviado = False # Cada 'd' se descarta una vez enviado en un camion if current_solution[i] == self.O[j]['id']: if self.O[j]['id'][0] == 'p': for n in range(0, len(truck_list)): if self.O[j]['container_size'] == 1: for l in range(0, 2): if truck_list[n][l] == 0 and not asignado: # LA SIGUIENTE CONDICION COMPRUEBA SI EL CAMION LLEGA AL CLIENTE DENTRO DE LA VENTANA TEMPORAL if (((t_f[n] + 60 * self.NORMA(posicion_actual[n], self.O[j]['xy'])/ velocidad_truck)) <= self.O[j]['TWl']) and (((t_f[n] + 60 * self.NORMA(posicion_actual[n], self.O[j]['xy'])/ velocidad_truck) >= self.O[j]['TWe'])): 63 63 Una búsqueda tabú reactiva para la optimización del acarreo terrestre con vehículos heterogéneos truck_list[n][l] = int(current_solution[i][1:3]) trucks[n].append(current_solution[i]) km_list[n] = km_list[n] + self.NORMA(posicion_actual[n], self.O[j]['xy']) t_f[n] = t_f[n] + self.O[j]['st'] + 60*(self.NORMA(posicion_actual[n], self.O[j]['xy'])/velocidad_truck) posicion_actual[n] = self.O[j]['xy'] # Ese punto tendrá que estar dentro del intervalo de la ventana temporal asignado = True elif (((t_f[n] + 60 * self.NORMA(posicion_actual[n], self.O[j]['xy'])/ velocidad_truck) < self.O[j]['TWe'])): truck_list[n][l] = int(current_solution[i][1:3]) trucks[n].append(current_solution[i]) km_list[n] = km_list[n] + self.NORMA(posicion_actual[n], self.O[j]['xy']) t_f[n] = self.O[j]['TWe'] + self.O[j]['st'] posicion_actual[n] = self.O[j]['xy'] # Ese punto tendrá que estar dentro del intervalo de la ventana temporal asignado = True else: # SI EL CAMION LLEGA FUERA DEL INTERVALO DE TIEMPO, APLICAMOS UNA PENALIZACION penaliza_retraso += self.penal_retraso km_list[n] = km_list[n] + self.NORMA(posicion_actual[n], self.O[j]['xy']) t_f[n] = t_f[n]+ self.O[j]['st'] + 60 * (self.NORMA(posicion_actual[n], self.O[j]['xy']) / velocidad_truck) posicion_actual[n] = self.O[j]['xy'] truck_list[n][l] = int(current_solution[i][1:3]) asignado = True trucks[n].append(current_solution[i]) if self.O[j]['container_size'] == 2: if truck_list[n][0] == 0 and truck_list[n][1] == 0 and not asignado: if (((t_f[n] + 60*self.NORMA(posicion_actual[n], self.O[j]['xy'])/velocidad_truck)) <= self.O[j]['TWl']) and (((t_f[n] + 60*self.NORMA(posicion_actual[n], self.O[j]['xy'])/ velocidad_truck) >= self.O[j]['TWe'])): Anexos 64 truck_list[n][0] = int(current_solution[i][1:3]) truck_list[n][1] = int(current_solution[i][1:3]) trucks[n].append(current_solution[i]) km_list[n] = km_list[n] + self.NORMA(posicion_actual[n], self.O[j]['xy']) t_f[n] = t_f[n]+ self.O[j]['st'] + 60 * (self.NORMA(posicion_actual[n], self.O[j]['xy']) / velocidad_truck) posicion_actual[n] = self.O[j]['xy'] asignado = True print('Contenedor de 40 recogido') elif (((t_f[n] + 60 * self.NORMA(posicion_actual[n], self.O[j]['xy'])/ velocidad_truck) < self.O[j]['TWe'])): truck_list[n][0] = int(current_solution[i][1:3]) truck_list[n][1] = int(current_solution[i][1:3]) trucks[n].append(current_solution[i]) km_list[n] = km_list[n] + self.NORMA(posicion_actual[n], self.O[j]['xy']) t_f[n] = self.O[j]['TWe']+ self.O[j]['st'] posicion_actual[n] = self.O[j]['xy'] asignado = True else: penaliza_retraso += self.penal_retraso km_list[n] = km_list[n] + self.NORMA(posicion_actual[n], self.O[j]['xy']) t_f[n] = t_f[n]+ self.O[j]['st'] + 60 * (self.NORMA(posicion_actual[n], self.O[j]['xy']) / velocidad_truck) posicion_actual[n] = self.O[j]['xy'] truck_list[n][0] = int(current_solution[i][1:3]) truck_list[n][1] = int(current_solution[i][1:3]) asignado = True trucks[n].append(current_solution[i]) if self.O[j]['id'][0] == 'd' and self.O[j]['id'][1] != 'e': for n in range(0, len(truck_list)): for l in range(0, 2): if truck_list[n][l] == int(current_solution[i][1:3]) and not enviado: if (((t_f[n] + 60*(self.NORMA(posicion_actual[n], self.O[j]['xy']))/velocidad_truck)) <= self.O[j]['TWl']) and (((t_f[n] + 60*(self.NORMA(posicion_actual[n], self.O[j]['xy'])) / velocidad_truck) >= self.O[j]['TWe'])): km_list[n] = km_list[n] + self.NORMA(posicion_actual[n], self.O[j]['xy']) t_f[n] = t_f[n]+ self.O[j]['st'] + 60*(self.NORMA(posicion_actual[n], self.O[j]['xy'])/velocidad_truck) 65 65 Una búsqueda tabú reactiva para la optimización del acarreo terrestre con vehículos heterogéneos posicion_actual[n] = self.O[j]['xy'] truck_list[n][l] = 0 enviado = True trucks[n].append(current_solution[i]) elif (((t_f[n] + 60*(self.NORMA(posicion_actual[n], self.O[j]['xy'])) / velocidad_truck) < self.O[j]['TWe'])): km_list[n] = km_list[n] + self.NORMA(posicion_actual[n], self.O[j]['xy']) t_f[n] = self.O[j]['TWe']+ self.O[j]['st'] posicion_actual[n] = self.O[j]['xy'] truck_list[n][l] = 0 enviado = True trucks[n].append(current_solution[i]) else: km_list[n] = km_list[n] + self.NORMA(posicion_actual[n], self.O[j]['xy']) t_f[n] = t_f[n]+ self.O[j]['st'] + 60 * (self.NORMA(posicion_actual[n], self.O[j]['xy']) / velocidad_truck) penaliza_retraso += self.penal_retraso posicion_actual[n] = self.O[j]['xy'] truck_list[n][l] = 0 enviado = True trucks[n].append(current_solution[i]) if self.O[j]['id'][0:2] == 'oe' and self.O[j]['id'][2] != 'f': for n in range(0, len(truck_list)): if self.O[j]['container_size'] == 1: for l in range(0, 2): if truck_list[n][l] == 0 and not asignado: if (((t_f[n] + 60 * (self.NORMA(posicion_actual[n], self.O[j]['xy'])) / velocidad_truck)) <=self.O[j]['TWl']) and (((t_f[n] + 60 * (self.NORMA(posicion_actual[n], self.O[j]['xy'])) / velocidad_truck) >=self.O[j]['TWe'])): truck_list[n][l] = int(current_solution[i][2:4]) trucks[n].append(current_solution[i]) km_list[n] = km_list[n] + self.NORMA(posicion_actual[n], self.O[j]['xy']) t_f[n] = t_f[n]+ self.O[j]['st'] + 60 * (self.NORMA(posicion_actual[n], self.O[j]['xy']) / velocidad_truck) posicion_actual[n] = self.O[j]['xy'] asignado = True elif (((t_f[n] + 60 * Anexos 66 self.NORMA(posicion_actual[n], self.O[j]['xy'])/ velocidad_truck) < self.O[j]['TWe'])): truck_list[n][l] = int(current_solution[i][2:4]) trucks[n].append(current_solution[i]) km_list[n] = km_list[n] + self.NORMA(posicion_actual[n], self.O[j]['xy']) t_f[n] = self.O[j]['TWe']+ self.O[j]['st'] posicion_actual[n] = self.O[j]['xy'] # Ese punto tendrá que estar dentro del intervalo de la ventana temporal asignado = True else: # SI EL CAMION LLEGA FUERA DEL INTERVALO DE TIEMPO, APLICAMOS UNA PENALIZACION penaliza_retraso += self.penal_retraso km_list[n] = km_list[n] + self.NORMA(posicion_actual[n], self.O[j]['xy']) t_f[n] = t_f[n]+ self.O[j]['st'] + 60 * (self.NORMA(posicion_actual[n], self.O[j]['xy']) / velocidad_truck) posicion_actual[n] = self.O[j]['xy'] truck_list[n][l] = int(current_solution[i][2:4]) asignado = True trucks[n].append(current_solution[i]) elif self.O[j]['container_size'] == 2: if truck_list[n][0] == 0 and truck_list[n][1] == 0 and not asignado: if (((t_f[n] + 60 * (self.NORMA(posicion_actual[n], self.O[j]['xy'])) / velocidad_truck)) <= self.O[j]['TWl']) and (((t_f[n] + 60 * (self.NORMA(posicion_actual[n], self.O[j]['xy'])) / velocidad_truck) >= self.O[j]['TWe'])): truck_list[n][0] = int(current_solution[i][2:4]) truck_list[n][1] = int(current_solution[i][2:4]) trucks[n].append(current_solution[i]) km_list[n] = km_list[n] + self.NORMA(posicion_actual[n], self.O[j]['xy']) t_f[n] = t_f[n]+ self.O[j]['st'] + 60 * (self.NORMA(posicion_actual[n], self.O[j]['xy']) / velocidad_truck) posicion_actual[n] = self.O[j]['xy'] asignado = True print('Contenedor de 40 recogido') elif (((t_f[n] + 60 * self.NORMA(posicion_actual[n],self.O[j]['xy']) / velocidad_truck) <self.O[j]['TWe'])): 67 67 Una búsqueda tabú reactiva para la optimización del acarreo terrestre con vehículos heterogéneos truck_list[n][0] = int(current_solution[i][2:4]) truck_list[n][1] = int(current_solution[i][2:4]) trucks[n].append(current_solution[i]) km_list[n] = km_list[n] + self.NORMA(posicion_actual[n], self.O[j]['xy']) t_f[n] = self.O[j]['TWe']+ self.O[j]['st'] posicion_actual[n] = self.O[j]['xy'] asignado = True else: penaliza_retraso += self.penal_retraso km_list[n] = km_list[n] + self.NORMA(posicion_actual[n], self.O[j]['xy']) t_f[n] = t_f[n]+ self.O[j]['st'] + 60 * (self.NORMA(posicion_actual[n], self.O[j]['xy']) / velocidad_truck) posicion_actual[n] = self.O[j]['xy'] truck_list[n][0] = int(current_solution[i][1:3]) truck_list[n][1] = int(current_solution[i][1:3]) asignado = True trucks[n].append(current_solution[i]) if self.O[j]['id'][0:3] == 'oef': if i < len(current_solution)-1: if current_solution[i+1][0:3] == 'ief': for n in range(0, len(truck_list)): for l in range(0,2): if truck_list[n][l] == int(current_solution[i][3:5]): truck_list[n][l] = int(current_solution[i+1][3:5]) bypass += 1 else: for n in range(0, len(truck_list)): for l in range(0, 2): if truck_list[n][l] == int(current_solution[i][3:5]) and not enviado: if (((t_f[n] + 60 * (self.NORMA(posicion_actual[n], self.O[j]['xy'])) / velocidad_truck)) <=self.O[j]['TWl']) and (((t_f[n] + 60 * (self.NORMA(posicion_actual[n], self.O[j]['xy'])) / velocidad_truck) >= self.O[j]['TWe'])): km_list[n] = km_list[n] + self.NORMA(posicion_actual[n],self.O[j]['xy']) t_f[n] = t_f[n]+ self.O[j]['st'] + 60 * (self.NORMA(posicion_actual[n],self.O[j]['xy']) / velocidad_truck) posicion_actual[n] = self.O[j]['xy'] truck_list[n][l] = 0 enviado = True Anexos 68 trucks[n].append(current_solution[i]) elif (((t_f[n] + 60 * (self.NORMA(posicion_actual[n], self.O[j]['xy'])) / velocidad_truck) <self.O[j]['TWe'])): km_list[n] = km_list[n] + self.NORMA(posicion_actual[n], self.O[j]['xy']) t_f[n] = self.O[j]['TWe']+ self.O[j]['st'] posicion_actual[n] = self.O[j]['xy'] truck_list[n][l] = 0 enviado = True trucks[n].append(current_solution[i]) else: km_list[n] = km_list[n] + self.NORMA(posicion_actual[n], self.O[j]['xy']) t_f[n] = t_f[n]+ self.O[j]['st'] + 60 * (self.NORMA(posicion_actual[n], self.O[j]['xy']) / velocidad_truck) penaliza_retraso += self.penal_retraso posicion_actual[n] = self.O[j]['xy'] truck_list[n][l] = 0 enviado = True trucks[n].append(current_solution[i]) else: for n in range(0, len(truck_list)): for l in range(0, 2): if truck_list[n][l] == int(current_solution[i][3:5]) and not enviado: if (((t_f[n] + 60 * (self.NORMA(posicion_actual[n], self.O[j]['xy'])) / velocidad_truck)) <= self.O[j]['TWl']) and (((t_f[n] + 60 * (self.NORMA(posicion_actual[n], self.O[j]['xy'])) / velocidad_truck) >= self.O[j]['TWe'])): km_list[n] = km_list[n] + self.NORMA(posicion_actual[n], self.O[j]['xy']) t_f[n] = t_f[n]+ self.O[j]['st'] + 60 * (self.NORMA(posicion_actual[n], self.O[j]['xy']) / velocidad_truck) posicion_actual[n] = self.O[j]['xy'] truck_list[n][l] = 0 enviado = True trucks[n].append(current_solution[i]) elif (((t_f[n] + 60 * (self.NORMA(posicion_actual[n], self.O[j]['xy'])) / velocidad_truck) < self.O[j]['TWe'])): 69 69 Una búsqueda tabú reactiva para la optimización del acarreo terrestre con vehículos heterogéneos km_list[n] = km_list[n] + self.NORMA(posicion_actual[n], self.O[j]['xy']) t_f[n] = self.O[j]['TWe']+ self.O[j]['st'] posicion_actual[n] = self.O[j]['xy'] truck_list[n][l] = 0 enviado = True trucks[n].append(current_solution[i]) else: km_list[n] = km_list[n] + self.NORMA(posicion_actual[n], self.O[j]['xy']) t_f[n] = t_f[n]+ self.O[j]['st'] + 60 * (self.NORMA(posicion_actual[n],self.O[j]['xy']) / velocidad_truck) penaliza_retraso += self.penal_retraso posicion_actual[n] = self.O[j]['xy'] truck_list[n][l] = 0 enviado = True trucks[n].append(current_solution[i]) if self.O[j]['id'][0:3] == 'ief': if current_solution[i-1][0:3] == 'oef': pass else: for n in range(0, len(truck_list)): if self.O[j]['container_size'] == 1: for l in range(0, 2): if truck_list[n][l] == 0 and not asignado: if (((t_f[n] + 60 * self.NORMA(posicion_actual[n],self.O[j]['xy']) / velocidad_truck)) <=self.O[j]['TWl']) and (((t_f[n] + 60 * self.NORMA(posicion_actual[n],self.O[j]['xy']) / velocidad_truck) >=self.O[j]['TWe'])): truck_list[n][l] = int(current_solution[i][3:5]) trucks[n].append(current_solution[i]) km_list[n] = km_list[n] + self.NORMA(posicion_actual[n], self.O[j]['xy']) t_f[n] = t_f[n]+ self.O[j]['st'] + 60 * (self.NORMA(posicion_actual[n], self.O[j]['xy']) / velocidad_truck) posicion_actual[n] = self.O[j]['xy'] asignado = True elif (((t_f[n] + 60*(self.NORMA(posicion_actual[n], self.O[j]['xy'])) / velocidad_truck) < self.O[j]['TWe'])): truck_list[n][l] = int(current_solution[i][3:5])