Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal

i S Equation Chapter 1 Section 1 Trabajo Fin de Máster Máster en Organización Industrial y Gestión de Empresas Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Autor: Manuel Cuberos Gallardo Tutor: Dr. Alejandro Escudero Santana Dep. Organización Industrial y Gestión de Empresas II Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2015 ii iii Trabajo Fin de Máster Máster en Organización Industrial y Gestión de Empresas Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Autor: Manuel Cuberos Gallardo Tutor: Alejandro Escudero Santana Profesor ayudante doctor Dep. de Organización Industrial y Gestión de Empresas II Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2015 iv v Trabajo Fin de Máster: Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Autor: Manuel Cuberos Gallardo Tutor: Alejandro Escudero Santana El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2015 El Secretario del Tribunal vi Resumen El transporte intermodal es un método de organizar el transporte de mercancías consistente en realizar los envíos empleando varios modos de transporte pero cargando una única unidad de carga. Esto permite reducir el tiempo que debe pasar la mercancía en las terminales, agilizando toda la cadena de transporte. Sin embargo, para conseguir que el transporte intermodal sea eficiente, es necesaria la planificación de las diversas etapas que la componen: el trayecto principal, en buque o tren, que se encarga de cubrir grandes distancias; el acarreo terrestre, que permite conectar la terminal intermodal con su hinterland, y el intercambio intermodal. Esta etapa consiste en cambiar el modo de transporte de la mercancía en la terminal. El intercambio intermodal es un proceso compuesto por muchas operaciones diferentes. Sin embargo, muchas de las ellas comparten recursos como maquinaria, personal, espacio, etc. por lo que el mejor enfoque para gestionar el intercambio intermodal es integrando varias de esas operaciones. El presente trabajo pretende ofrecer un método para mejorar la eficiencia de una terminal intermodal a partir de la sincronización de los procesos de descarga y carga de buques y trenes, lo que se consigue programando las grúas encargadas de dichos procesos. Con ello se consigue reducir el tiempo que pasan los contenedores en la terminal, así como el tiempo que pasan los buques y los trenes esperando a ser cargados en la terminal. Para resolver la problemática presentada se ha desarrollado un algoritmo basado en la heurística de recocido simulado. Dicha heurística, inspirada en el proceso de recocido del acero para conseguir material recristalizado con baja energía interna, ha servido como base para el desarrollo de algoritmos para la resolución de diversos problemas de optimización. La principal particularidad del algoritmo de recocido simulado es su comportamiento convergente al óptimo del problema si está correctamente parametrizado, lo que se consigue gracias a la capacidad de escapar de óptimos locales propia de la heurística. Con el fin de demostrar la validez del algoritmo se ha desarrollado una batería de problemas de aplicación. Los resultados obtenidos han corroborado el buen comportamiento del algoritmo de recocido simulado ante el problema de sincronización y programación de grúas. vii viii Índice Resumen vi Índice viii Índice de Tablas x Índice de Figuras xv Glosario xvi 1 Introducción y Objetivos 17 1.1 Antecedentes y contexto 17 1.2 Objetivo del trabajo 19 1.3 Contenido del trabajo 19 2 Las terminales de contenedores 20 2.1. Tipos de terminales intermodales 21 2.1.1 Puertos secos 21 2.1.2 Terminales portuarias de contenedores 22 2.2 Elementos de las terminales portuarias de contenedores 23 2.2.1 Los contenedores de mercancía 24 2.2.2 Zonas de una terminal portuaria de contenedores 25 2.2.3 Equipos de una terminal portuaria de contenedores 26 2.3 Servicios ofrecidos por una terminal portuaria de contenedores 31 2.3.1 Carga y descarga de buques 31 2.3.2 Almacenamiento de mercancía 31 2.3.3 Cambio del modo de transporte 31 3 Operativas en una terminal de contenedores portuaria 32 3.1 Operativa del buque 33 3.1.1 El problema de asignación de muelles 33 3.1.2 La planificación de la estiba dentro del buque 35 3.1.3 Problema de programación de grúas pórtico 37 3.2 Operativa de almacenamiento y apilado 38 3.2.1 La localización de los contenedores en la zona de almacenaje 38 3.2.2 La relocalización de contenedores en la zona de almacenaje 40 3.3 Operativa de transferencia 42 3.3.1 El transporte en muelles 42 3.3.2 El transporte terrestre 44 3.3.3 La programación de las grúas 45 4 El problema de secuenciación y programación de grúas 48 4.1 Definición del problema 49 4.2 Formulación conceptual del problema 50 4.2.1 Consideraciones y simplificaciones del problema 50 4.2.2 Variables de la planificación 51 4.2.3 Función objetivo 52 4.2.4 Restricciones del problema 52 4.3 Ejemplo conceptual 53 ix 5 Metodología: El recocido simulado 56 5.1 Introducción a la heurística de Recocido Simulado 57 5.2 El recocido simulado en problemas de optimización 59 5.3 Adaptación del recocido simulado al problema de secuenciación y programación de grúas 60 5.3.1 Parámetros del algoritmo 61 5.3.2 Funcionamiento del algoritmo 62 5.3.3 Codificación de la solución 64 6 Resultados 66 6.1 Batería de problemas 66 6.2 Resultados 69 7 Conclusiones 73 8 Referencias bibliográficas 75 Anexo I. Batería de problemas 82 Anexo II. Resultados de la batería de problemas 90 Anexo III. Parametrización 143 Función de enfriamiento 143 Temperatura inicial y temperatura final 144 Longitud de la cadena 145 Tamaño del vecindario 146 xvi Glosario BAP Berth Allocation Problem CPMP Container Pre-Marshalling Problem DDP Daily Drayage Problem GRASP Greedy Randomized Adaptative Search Procedure ISO International Organization for Standardization LTP Landside Transport Problem MBPP Master Bay Planning Problem NP No polinomial QCSP Quay Crane Scheduling Problem QTP Quasyde Transport Problem SA Simulated Annealing SPP Stowage Planning Problem TEU Twenty-foot Equivalent Unit TPC Terminal Portuaria de Contenedores TTRP Truck and Trailer Routing Problem UNCTAD United Nations Conference on Trade and Development UNE Una Norma Española VRP Vehicle Routing Problem VRPTW Vehicle Routing Problem with Time Windows YAP Yard Allocation Problem YCSP Yard Crane Scheduling Problem ZA Zona de Almacenamiento 17 17 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal 1 INTRODUCCIÓN Y OBJETIVOS l transporte de mercancías es una actividad más que demuestra el creciente proceso de globalización en que se encuentra la sociedad en la actualidad. Hoy en día, largas cadenas de transporte se encargan de conectar todo el mundo con el fin de eliminar barreras geográficas entre la producción y el consumo. A la hora de determinar el modo de transporte, el marítimo es la opción más común para trayectos de larga distancia. Sin embargo, la escasa flexibilidad hace que sea necesario sincronizar los envíos marítimos puerto a puerto con otros modos de transporte como el ferrocarril y el transporte por carretera. Este concepto se conoce como transporte multimodal. Entre las diferentes formas de llevar a cabo el transporte de mercancías, la de mayor crecimiento es el transporte intermodal, el cual es un modo particular de multimodalidad. Consiste en utilizar diferentes modos de transporte para transportar una misma unidad de carga. Esta particularidad permite reducir el tiempo que debe pasar la mercancía en las terminales intermodales, al sustituir las operaciones de carga y descarga de mercancía de un contenedor a otro, por operaciones de carga y descarga de los propios contenedores entre los diferentes medios de transporte. Las terminales portuarias de contenedores son esenciales para entender el concepto de transporte de larga distancia de mercancías. En ellas los contenedores deben ser descargados de los buques para posteriormente ser cargados en trenes o camiones para continuar la cadena logística. Esto hace que en las terminales portuarias se desarrollen diferentes operaciones que son esenciales para tratar de agilizar los envíos. 1.1 Antecedentes y contexto El transporte de mercancías ha ido evolucionando en pos de conseguir hacer llegar cualquier tipo de producto a cualquier lugar del mundo. La especialización de la producción y el abaratamiento del transporte han favorecido dicha evolución. De entre todos los cambios que ha experimentado el transporte de mercancías, el más trascendente fue la aparición de los contenedores El crecimiento del transporte de contenedores se ha acentuado a medida que el desarrollo económico y tecnológico ha ido permitiendo aumentar la productividad de los puertos. Como se aprecia en la siguiente gráfica, el envío de contenedores lleva décadas creciendo año a año, con la salvedad del año 2009, donde la E Introducción y Objetivos 18 18 crisis mundial trajo consigo una inaudita reducción del comercio de contenedores. Figura 1. Evolución comercio contenedorizado mundial, 1996-2014 Fuente: UNCTAD 2014 Resulta especialmente llamativa la distribución de las rutas que más han crecido en los últimos años. Entra las tres grandes rutas este-oeste, las que unen Asia con Europa y América, la que más han crecido con mucha diferencia han sido las que conectan Asia (centro manufacturero) con Asia y América (consumidores), siendo mucho menor el crecimiento del transporte de contenedores entre Europa y América. . Figura 2. Tráfico de carga en las principales rutas del comercio contenedorizado, 1995-2013 Fuente: UNCTAD 2014 19 19 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal 1.2 Objetivo del trabajo El crecimiento de la intermodalidad como forma de transporte de mercancías hace que la gestión eficiente de las terminales intermodales sea imprescindible. El intercambio del modo de transporte de la mercancía es un proceso complejo que depende de muchos factores diferentes, lo que dificulta la planificación de las operaciones necesarias para dichos intercambios. Estas operaciones guardan fuerte relación las unas con las otras. Este aspecto, unido a la necesidad de gestionar todas ellas para conseguir optimizar la etapa de cambio de modo de transporte, sugiere enfocar el problema integrando diferentes operativas. En concreto, se pretende agilizar el proceso de descarga de buques y posterior carga de trenes, y viceversa. Este problema incluye por un lado la asignación de recursos a los distintos buques y trenes, y por otro la programación de las grúas disponibles en la terminal de contenedores. Para resolver el problema se ha llevado a cabo una adaptación al problema de la heurística del recocido simulado, empleada en una gran variedad de problemas de optimización. 1.3 Contenido del trabajo Para contextualizar el trabajo se presenta el concepto de transporte intermodal en el apartado 2. Además, se describen diversos conceptos relacionados con las terminales de contenedores esenciales para contextualizar el trabajo realizado. En el apartado 3, se lleva a cabo una revisión sobre el estado del arte de las operativas que se dan en las terminales y que hacen posible los intercambios intermodales. En el apartado 4 se profundiza en el problema a resolver para mejorar la eficiencia en una terminal portuaria de contenedores. En esta sección se detallan las variables del problema, así como las restricciones y la función objetivo. En el apartado 5 se presenta la heurística del recocido simulado. Se presenta una revisión bibliográfica de diferentes problemas de la literatura que han sido resueltos empleando dicha heurística, y se muestra la adaptación de la misma al problema a resolver. En el apartado 6 se analizan los resultados obtenidos a partir de una batería de problemas. Dichos resultados son comparados con los ofrecidos por otras heurísticas a la misma batería de problemas, con el fin de determinar la adecuación del algoritmo de recocido simulado al problema de optimización resuelto. Por último, en el apartado 7 se exponen las conclusiones obtenidas del desarrollo del presente trabajo. Las terminales de contenedores 20 20 2 LAS TERMINALES DE CONTENEDORES l transporte intermodal consiste en la articulación entre diferentes modos de transportando empleando una única medida de carga, generalmente contenedores, a fin de realizar de manera más eficiente las operaciones de transbordo de mercancías y materiales. Como definieron (Van Duin y Van Ham 1998) “el transporte intermodal es el 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”. En la misma línea, en la literatura también se define el transporte intermodal como “Transporte en el que dos o más modos son unidos de principio a fin con el objetivo de transportar mercancías o personas de un punto de origen a un punto de destino” (Southworth y Peterson 2000) y “envío de mercancías y el movimiento de personas envueltas en más de un modo de transporte durante un viaje simple y sin fisuras” (Jones, Cassady, y Bowden Jr 2000). El transporte intermodal suele dividirse en 3 etapas diferenciadas:  Acarreo terrestre: Se refiere al transporte por carretera de la mercancía hasta la terminal intermodal, ya sea de ferrocarril o portuaria. Esta etapa es la más flexible de toda la cadena de transporte.  Transbordo en terminal: En las terminales intermodales de origen y de destino, la mercancía debe ser descargada de los camiones, apilada de forma ordenada y posteriormente cargada en el buque o tren encargado del trayecto principal. La aparición de los contenedores fue revolucionaria ya que se consiguieron reducir enormemente los tiempos que debía pasar la mercancía en las terminales.  Trayecto principal: En ferrocarril o en buque por vía marítima, el trayecto principal cubre grandes distancias entre la terminal de origen y la de destino. E 21 21 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Figura 3. Etapas del transporte intermodal El transbordo en terminal es la etapa que requiere una mayor sincronización y precisión si se quiere optimizar el envío a lo largo de toda la cadena. Tal y como se concluye en (Ambrosino, Sciomachen, y Tanfani 2004), todas las operaciones a realizar en la terminal deben ser optimizadas con el fin de obtener la máxima eficiencia a lo largo de todo el proceso. Por tanto, es importante optimizar los recursos de los que se dispone en la terminal para agilizar lo máximo posible las operaciones en la misma. 2.1. Tipos de terminales intermodales Las terminales intermodales se clasifican en dos tipos según la geografía en que se encuentran ubicadas: terminales portuarias, donde se producen las llegadas de buques con contenedores, y terminales de interior, con conexión a transporte ferroviario. 2.1.1 Puertos secos Un puerto seco es una terminal intermodal situada en el interior de un país o región, que se conecta con uno o varios puertos marítimos a través de la red ferroviaria y por carretera. Suelen ubicarse cerca de grandes ciudades o núcleos de producción. En ellas se produce el intercambio de contenedores entre camiones y trenes. Para ello, los puertos secos necesitan grúas capaces de cargar y descargar trenes, así como de desplazar los contenedores de una zona de la terminal a otra. En España el más importante es el Puerto Seco de Madrid, llegando a manipular más de 120.000 TEU en 2014 tras haber experimentado un crecimiento exponencial en el presente siglo. Las terminales de contenedores 22 22 Figura 4. Puerto Seco de Madrid Fuente: www.puertoseco.com 2.1.2 Terminales portuarias de contenedores Las terminales portuarias de contenedores se ubican en la costa, o en ríos accesibles a buques cargueros. Se puede definir terminal portuaria como instalación o conjunto de instalaciones destinadas a conectar el modo de transporte marítimo con los diferentes modos terrestres. En la literatura, algunos autores determinan que los puertos no son más que un eslabón más en la cadena del transporte y el comercio, por lo que un uso eficiente de los mismos contribuye al bienestar social al generar excedentes para productores y consumidores (Goss 1990). Aproximadamente el 46% del tráfico portuario de contenedores de todo el mundo en 2013 estaba representado en los 20 puertos principales. Además, los 10 principales puertos se encuentran en Asia, lo que es un reflejo del papel como importador que tiene el continente en todo el planeta. En Europa, el puerto con mayor tráfico de contenedores se encuentra en Rotterdam (Países Bajos), siendo también grandes puertos internacionales el de Amberes (Bélgica) y Hamburgo (Alemania). 23 23 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Figura 5. Tráfico de contenedores en los principales puertos del mundo En la Figura 5 se aprecia fácilmente la enorme diferencia de volumen entre el tráfico que manejan los puertos asiáticos con los europeos, y especialmente con los españoles.. Figura 6. Puerto de Rotterdam 2.2 Elementos de las terminales portuarias de contenedores La complejidad en la gestión y funcionamiento de una terminal portuaria de contenedores se fundamenta en su papel como centro de intercambio nodal de mercancía. Para que este intercambio se produzca de manera 36,6 32,6 23,3 22,3 17,7 17,3 15,5 15,3 13,6 13 11,6 9,2 8,6 4,4 4,3 0,14 0 5 10 15 20 25 30 35 40 Millones de TEU Las terminales de contenedores 24 24 eficiente es necesario que se desarrollen diferentes procesos, a priori independientes entre sí. Las operaciones a realizar en una terminal requieren el empleo de distintos recursos, como los contenedores, las grúas y demás maquinaria, así como de las diferentes zonas de la terminal. 2.2.1 Los contenedores de mercancía La aparición del contenedor fue fundamental para el crecimiento del transporte de mercancías en todo el mundo. Antes de ellos, el transporte se hacía en paquetes con diferentes formas, tamaños y pesos, y los procesos de carga y descarga eran muy lentos. Fue el transportista estadounidense Malcolm McLean quien ideó el uso de cajas metálicas para el transporte de sus mercancías con el fin de facilitar los procesos de carga y descarga y evitar rupturas y robos de la mercancía. En 1956 se produjo el primer traslado en buque de 58 contenedores desde New Jersey a Houston. En 1966 se produjo el primer viaje transoceánico, cuando el petrolero Fairland cubrió la ruta Nueva York – Rotterdam cargado con 228 contenedores. Estos primeros contenedores tenían unas dimensiones de 35 pies de longitud, 8 de altura y 8 de anchura. Actualmente estas dimensiones están estandarizadas según la norma ISO 668 y su homóloga UNE 117101:2003. Por ello, los buques portacontenedores y demás medios de transporte de mercancías están estandarizados para optimizar los envíos de contenedores de 20 y de 40 pies. Estas dimensiones dieron paso a una nueva unidad de medida, el TEU, del término inglés Twenty-foot Equivalent Unit. Así, los contenedores estandarizados tienen dimensiones de 1 o 2 TEU. Existen además diferentes tipos de contenedores, como se pueden ver resumidos en la Tabla 1. Dry Van o Contenedor Estándar Son los más utilizados para el transporte, y dada su versatilidad pueden ser empleados para casi cualquier tipo de carga. Además de existir de 20 o 40 pies, existe el High Cube, de 40 pies y más alto y con más capacidad que el estándar. Reefer o Frigoríficos Son contenedores refrigerados. Empleados sobre todo para el transporte de alimentos, necesitan ir conectados a red eléctrica para mantener baja la temperatura de su interior. Tank o Cisterna Para transportar líquidos y gases. Es una cisterna con una estructura para que pueda ser manipulada como los dry van. Flexitank o Tanque Flexible Es una bolsa o tanque flexible de gran tamaño que transforma un contenedor 20 pies convencional en un seguro y eficiente sistema de transporte de líquidos a granel. 25 25 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Open Side o Lateral Abierto Son usados cuando se requiere acceder a la mercancía a través del lateral del contenedor, generalmente cuando la carga es indivisible a menor tamaño. Open Top o Techo Abierto Contenedor usado como carga de mercancía voluminosa o que tiene que cargarse por la parte superior. Flat Rack o Plataforma Se emplean habitualmente cuando la carga es sobredimensionada al tamaño de un contenedor estándar. Tabla 1. Tipos de contenedores Las dimensiones estandarizadas de los principales tipos de contenedores se reflejan en la Tabla 2. Nombre Longitud (m) Anchura (m) Altura (m) Contenedor de 20’ 6,058 2,438 2,438 Contenedor de 40‘ 12,192 2,438 2,438 Contenedor High Cube 12,192 2,438 2,591 Tabla 2. Dimensiones de los principales tipos de contenedores 2.2.2 Zonas de una terminal portuaria de contenedores Las terminales de contenedores suelen ser grandes superficies, con espacio suficiente para que se puedan llevar a cabo las diferentes operaciones que se dan en los puertos. Las principales zonas en las que se divide una terminal portuaria de contenedores son:  Zona de operaciones de buques: Junto a los muelles donde atracan los barcos, en esta zona se ubican las grúas pórtico que se encargan de la carga y descarga de contenedores en los buques.  Zona de almacenaje: Son grandes extensiones donde se almacenan los contenedores. Según la distribución de los mismos se distinguen dos tipos*:  Estructura europea o automatizada: Los bloques de contenedores están perpendiculares a la línea de atraque. Están automatizadas, ya que están pensadas para minimizar el espacio necesario entre los bloques de contenedores, de forma que no hay espacio para carretillas, por lo que solo se puede Operativas en una terminal de contenedores portuaria 32 32 3 OPERATIVAS EN UNA TERMINAL DE CONTENEDORES PORTUARIA as terminales portuarias de contenedores son grandes superficies donde coexisten elementos muy diferenciados con fines particulares distintos, si bien todas las acciones que se producen en una terminal intermodal tienen un mismo objetivo: cambiar el modo de transporte en que se envía la mercancía. Los contenedores llegan a la terminal por carretera, en ferrocarril, o en buques. Una vez en la terminal, se inicia el proceso de intercambio de modo, que consta de diferentes operaciones: 1) Descarga de la mercancía del buque. 2) Traslado del contenedor desde la zona de operaciones de buques hasta el patio de almacenamiento de contenedores. 3) Envío de la mercancía hasta la zona de operaciones terrestres. 4) Carga del contenedor en el ferrocarril o camión correspondiente. Cuando el proceso sigue este orden se denomina envío de importación. Cuando la mercancía llega a la terminal por carretera o ferrocarril y sale de ésta por la vía marítima se denomina de exportación. Debido a la variedad de operaciones a las que se somete un contenedor en la terminal, la prioridad por minimizar recursos, y la necesidad de que el cambio de modo se haga en el menor tiempo posible, surgen diferentes problemas que deben tratarse para conseguir la mayor eficiencia. La variedad de las operaciones que se producenenuna terminal portuariahace que en la literatura se diferenciendistintas operativas que se desarrollan de manerasimultanea.En trabajos como (Voß et al. 2004), (Stahlbock y Voß 2008) o (I. F. a Vis y De Koster 2003) se hacen revisiones bibliográficas donde se recogen las principales operaciones que se dan en las terminales de contenedores, y los problemas derivados de las mismas. Las distintas operaciones de una terminal se dividen generalmente en función del entorno en que se desarrollan, correspondientes a las diferentes zonas de las terminales descritas en el apartado anterior. Considerando que las tareas que se desarrollan en la zona de servicio tiene una naturaleza diferente, se van a L 33 33 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal analizar las operativas que se producen en las otras tres zonas. Dichas operativas, y sus principales operaciones, se reflejan enla Figura 17. Figura 17. Operaciones en una terminal portuaria de contenedores Fuente: (Arango, Cortes, y Sanz 2010) 3.1 Operativa del buque En la zona de operaciones de buques se dan diferentes tareas que deben desenvocar en la carga o descarga de los contenedores de los barcos. Para ello deben resolverse tres problemas principales, los que responden a las preguntas: 1. ¿Qué muelle se asigna a cada buque? 2. ¿Cómo deben colocarse los contenedores en el buque? 3. ¿Cómo deben gestionarse las grúas pórtico para que la carga/descarga sea eficiente y segura? Estas tres cuestiones dan lugar a sendos problemas, los cuales han sido muy estudiados durante años, y siguen siendo hoy día objeto de investigaciones. 3.1.1 El problema de asignación de muelles Como se aprecia en la literatura, el problema de asignación de muelles es uno de los más estudiados. Llamado en inglés berth allocation problem (BAP), la resolución de este problema debe considerar varios aspectos: Operativas en una terminal de contenedores portuaria 34 34  La ubicación de los contenedores que deben cargarse en el buque, con el fin de que estos se coloquen anteriormente en la zona de almacenamiento cerca del muelle donde atracará el buque.  Los tiempos que pasan los buques en los muelles, así como las horas previstas de llegadas de los barcos. En (Lai y Shih 1992) y en (Bierwirth y Meisel 2010) se llevan a cabo sendas revisiones de la literatura con el fin de facilitar el modelado de las características y sugerir algoritmos aplicables al BAP. Este segundo trabajo presta especial atención a los enfoques de soluciones integradas, los cuales son cada vez más relevantes en las terminales. Se diferencian dos variantes del problema de asignación de muelles: problema estático y problema dinámico. El problema estático (SBAP) trata de cubrir una planificación siendo conocidas las entradas y salidas durante el proceso. La novedad del escenario dinámico (DBAP) es que se replanifica cada vez que se produce un nuevo evento en el sistema, como puede ser la llegada o salida de un tren o buque. Una resolución del SBAP se encuentra en (Dai et al. 2008), donde se trata de optimizar el proceso empleando un algoritmo genético. Otros estudios como el presentado en (Imai, Nishimura, y Papadimitriou 2001) tratan de resolver el problema de asignación de muelle considerándolo dinámico. Para resolver el problema no polinomial, desarrollan una heurística basada en una simplificación lagrangiana del problema original. Para resolver el problema se han aplicado diferentes heurísticas. En (Nishimura, Imai, y Papadimitriou 2001) presentan una heuristica basada en un algoritmo genético para resolver el problema. Este estudio se complementa con (Imai, Nishimura, y Papadimitriou 2003), donde se distinguen prioridades entre los distintos buques. Uno de los factores que influyen en la tipología del problema es cómo se consideran los muelles, discreto o continuo, considerando discreto el muelle que tiene un número determinado de posiciones de atraque de buques, mientras que en un muelle continuo el número de buques que pueden atracar simultáneamente depende principalmente del tamaño de los propios buques. Esta característica se representa de manera visual en la Figura 18. Figura 18. Muelle discreto vs muelles continuo En (Imai et al. 2005) se desarrolla una heurística para resolver el BAP considerando un muelle continuo. En la misma línea, (S.-W. Lin y Ting 2013) propone una heurística basada en el algoritmo de recocido simulado, 35 35 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal concluyendo que dicha heurística alcanza el óptimo el problemas de pequeño tamaño, y encuentra buenas soluciones en problemas de gran tamaño debido a la propiedad convergente de dicho algoritmo. Otra investigación basada en el algoritmo de recocido simulado se encuentra en (Moorthy y Teo 2007). Además, en la literatura se encuentran varias investigaciones que combinan la optimización y la simulación, como (Arango et al. 2013) que desarrolla un algoritmo genético para resolver el problema de asignación de muelles dinámico y se complementa con un modelo de simulación para dar consistencia a los resultados. 3.1.2 La planificación de la estiba dentro del buque El plan maestro de muelle, conocido en la literatura científica como stowage planning problem o master bay planning problem (SPP, MBPP), consiste en la colocación de los contenedores dentro del buque. Debido a que los contenedores se colocan en pilas en los buques, es común que para que un contenedor determinado pueda ser descargado en un puerto se requiera la descarga de otro contenedor para tener acceso al contenedor a descargar, teniendo que volver a cargar posteriormente el contenedor cuyo destino es otro puerto. Estos movimientos deben evitarse para conseguir una mayor eficiencia, para lo que se lleva a cabo una planificación de la estiba. Un ejemplo de la colocación de los contenedores en un buque se observa en la Figura 19. Los principales objetivos de una correcta estiba son:  Garantizar la seguridad de la tripulación y el personal del puerto.  Aprovechar al máximo la capacidad de carga de los buques.  Proteger la mercancía de posibles daños.  Colocar los contenedores de forma que se agilicen las operaciones de carga y descarga en los puertos. Operativas en una terminal de contenedores portuaria 36 36 Figura 19. Visualización de estiba de un buque Esta tarea ha correspondido históricamente a la naviera encargada del transporte. Esta información se envía a la terminal portuaria, la cual debe preparar los contenedores en la zona de almacenamiento para agilizar la posterior carga del buque. Sin embargo, la terminal elaboraba otra planificación de la estiba de manera independiente, lo que da lugar a problemas de recolocación de contenedores. Esta tesitura inspiró una investigación multiobjetivo que busca maximizar la estabilidad del buque y minimizar los movimientos de recolocación de contenedores (Imai et al. 2006). El objetivo de la planificación de la estiba es maximizar la capacidad de los buques de carga, además de minimizar el tiempo necesario de atraque de los mismos en las terminales portuarias. Tal y como se analiza en (Tierney, Pacino, y Jensen 2014) se trata de un problema NP-complejo, aunque dicha investigación propone una estrategia para que el problema pase a dificultad polinómica. En (Bortfeldt y Gehring 2001) se presenta un algoritmo genético para resolver el SPP, considerando diferentes tipos de contenedores que deben ser apilados en un mismo buque. Este trabajo avala el buen comportamiento del algoritmo genético en este problema frente a otros métodos de resolución. En (Ambrosino et al. 2009)se resuelve el problema de la estiba partiendo de la solución óptima de subconjuntos independientes. Para resolver el problema general se utiliza una heurística basada en una búsqueda tabú. El algoritmo permite, además de garantizar la estabilidad del buque, reducir el tiempo de manipulación de los contenedores al ser cargados. Posteriormente, en (Ambrosino y Anghinolfi 2010) se presentan dos nuevas heurísticas para resolver el MBPP. Por un lado, se muestra una heurística simple constructiva, además de un algoritmo de optimización basado en colonia de hormigas. El comportamiento de estos procedimientos se compara con el que aporta la búsqueda tabú, presentada anteriormente. En (Wilson, Roach, y Ware 2001) los autores introducen la idea de dividir el problema complejo de la estiba en subproblemas: una proceso de planificación estratégico general, y un procedimiento de planificación 37 37 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal táctica especializada, donde los contenedores concretos quedan asignados a posiciones determinadas. En (Avriel y Penn 1993) se trata la planificación de la estiba con el fin de minimizar el número de movimientos de contenedores sin tener en cuenta las limitaciones de estabilidad. Primeramente se realiza un modelo de programación lineal binaria para el problema simplificado. Sin embargo, este tipo de modelo está muy limitado cuando el tamaño del problema aumenta debido al elevado número de variables necesarias para la resolución. Por esta razón, se presenta un algoritmo heurístico basado en una matriz de transporte "reducido", es decir, contenedores con los mismos puertos de origen y de destino se guardan en pilas completos siempre que sea posible, y sólo los contenedores restantes se asignan por el modelo de programación lineal binaria. Este enfoque a menudo permite la planificación de estiba de un número mucho mayor de recipientes que el uso de la formulación exacta. En la misma línea,(Avriel et al. 1998) y(Ambrosino, Sciomachen, y Tanfani 2004) parten del modelo lineal binario y lo complementan con una heurística que permite relajar algunas restricciones, y abarcar así problemas de mayor tamaño. 3.1.3 Problema de programación de grúas pórtico Conocido en la literatura como quay crane scheduling problem (QCSP), el problema de programación de grúas de buques consiste en determinar la secuencia de movimientos de carga y descarga de las grúas asignadas a un buque con el fin de minimizar el tiempo que debe permanecer el buque en el puerto. (Daganzo 1989) presenta el problema como complejo NP, y limita la resolución por métodos numéricos exactos a casos con pocos buques. Para resolverlo, muchos autores han propuesto diferentes métodos, como se recoge en (Meisel y Bierwirth 2011) donde se muestra un enfoque unificado para evaluar el desempeño de diferentes modelos y algoritmos propuestos en la literatura para la resolución del QCSP. En (Moccia et al. 2006) se presenta el problema de programación de muelles como un problema de rutado (vehicle routing problem, en adelante VRP) con restricciones de precedencia. El trabajo incluye el desarrollo de un algoritmo de ramificación y corte (branch and cut) para problemas grandes, mientras que los de menor tamaño se resuelven empleando el software comercial de optimización CPLEX. En la misma línea en (Peterkofsky y Daganzo 1990) desarrollan un método de ramificación y poda (branch and bound) para obtener la solución óptima del QCSP. Un algoritmo similar se emplea en (Kim y Park 2004) donde además, se propone una heurística basada en un algoritmo GRASP (greedy randomized adaptative search procedure) de menor carga computacional, y se comparan los resultados alcanzados por ambos procedimientos. Una comparación con este trabajo se presenta en (Sammarra et al. 2007), donde se propone una heurística de búsqueda tabú para el problema de programación de grúas. El QCSP se descompone en un problema de enrutamiento y otro de programación, siendo el primero resuelta con el algoritmo tabú y resolviendo el el problema de programación con una técnica de búsqueda local. Por su parte, en (Bierwirth y Meisel 2009) los autores presentan un modelo de optimización para el problema de programación de grúas de muelle y se propone una heurística para resolverlo. Básicamente, se aplica un Operativas en una terminal de contenedores portuaria 38 38 algoritmo branch and bound para alcanzar un subconjunto de buenas soluciones, utilizando un criterio de ramificación y poda centrado en las restricciones de interferencia de grúas. En (Bish 2003) se resuelve un problema de programación de varias grúas con restricciones, dividiendo el mismo en tres subproblemas: determinar la ubicación del contenedor una vez descargado, definir la asignación de vehículos a los contenedores que deben ser transportados en la terminal, y programar las operaciones de carga y descarga de las grúas. Se desarrolla para ello un algoritmo heurístico basado en la formulación del problema como un problema de transbordo. Una variante del problema consiste en considerar conjuntos el problema de asignación de muelle BAP y el de programación de grúas pórtico QCSP. En (Liang, Huang, y Yang 2009) se presenta el problema QCSP conjunto con el de asignación de muelle (BAP), por lo que se introduce una formulación simultanea de ambos problemas. Dicho problema se resuelve empleando un método que combina un algoritmo genético con una .heurística rápida que permite obtener soluciones aproximadas del problema. En la misma línea, (TavakkoliMoghaddam et al. 2009), (D.-H. Lee, Wang, y Miao 2008) y (Imai et al. 2008) proponen un modelo de programación entera mixta para el problema de programación y asignación de grúas de muelle.Estas investigaciones resuelvenel problema con una heurística basada en un algoritmo genético, y se demuestra su idoneidad comparando los resultados en términos de carga computacional con los ofrecidos por el software comercial LINGO. 3.2 Operativa de almacenamiento y apilado La gestión de las zonas de almacenamiento de las terminales ha adquirido mucha importancia a medida que ha aumentado el tráfico de contenedores, debido a la necesidad de almacenar un número mayor de contenedores en un determinado espacio, a menudo limitado y sin posibilidad de crecer. Por ello, el uso eficiente de los recursos requeridos para el almacenaje es fundamental para conseguir eficiencia en toda la cadena logística. Entre estos recursos se encuentran las grúas, los vehículos encargados de transportar los contenedores en la terminal y el espacio disponible para el almacenamiento. La operativa de almacenamiento y apilado engloba dos subsistemas, los cuales se detallan a continuación. 3.2.1 La localización de los contenedores en la zona de almacenaje Conocido en la literatura como yard allocation problem (YAP), este problema consiste en asignar una posición a cada contenedor que llega a la zona de almacenaje. En este problema hay que tener en cuenta factores como el tamaño del contenedor a almacenar, la fecha y hora a la que debe ser cargado el contenedor en el tren o barco, las características del contenedor, etc. El objetivo principal de una buena planificación de la ubicación de los contenedores es minimizar el tiempo que deben pasar los contenedores en la zona de almacenamiento, así como agilizar el proceso de almacenar los contenedores. 39 39 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal En (Gambardella, Rizzoli, y Zaffalon 1998) se presenta un sistema de ayuda a la toma de decisiones para la gestión de una terminal. Entre los problemas a resolver considera el YAP, así como la asignación de recursos y la programación de operaciones, con el fin de maximizar la eficiencia de la terminal. Este sistema se basa en la programación lineal entera, y en la simulación de eventos discretos que se emplea para validar los resultados. En (Zhang et al. 2003) se estudia el problema de asignación de espacio de almacenamiento en los patios de contenedores. Los autores plantean una división del problema en dos subproblemas de diferente nivel, formulando cada uno de ellos como modelos de programación matemática:  En el primer nivel, se determina el número total de contenedores que se ubica en cada bloque de almacenamiento en cada período de tiempo del horizonte de planificación  El segundo nivel determina el número de contenedores asociados con cada buque con el fin de minimizar la distancia total del transporte de los contenedores entre sus bloques de almacenamiento y los lugares de atraque de los buques. En (Bazzazi, Safaei, y Javadian 2009) se presenta un algoritmo genético para resolver el problema de localización de contenedores en una terminal. La validez del algoritmo se refleja con los resultados ofrecidos por el mismo al resolver diferentes modelos. En la misma línea, (Kim y Park 2003) formulan un modelo de programación lineal entera mixta para resolver el problema de exportación. Se proponen para resolver el problema dos algorítmicos heurísticos basados en el tiempo de permanencia de los contenedores y en un métodosubgradiente de optimización respectivamente. En (Canonaco et al. 2008) se plantea un modelo de red de colas. Se emplea además un software de simulación de eventos disctretos implementado en Delphi para comprobar la validez de los resultados obtenidos. En (L. H. Lee et al. 2006) se propone una metodología de pre-localización de los espacios en la zona de almacenamiento para los contenedores con el fin de maximizar la eficiencia en las operaciones de carga de contenedores. Se formula un modelo de programación entera mixta para determinar el número mínimo de grúas de patio necesarias y la ubicación donde se deben almacenar contenedores sin carga. El modelo se resuelve usando CPLEX. Los autores consideran la posición de los contenedores en los diferentes bloques dentro de la zona de almacenamiento, no teniendo en cuenta las diferentes ubicaciones posibles del contenedor dentro de un mismo bloque. Otras investigaciones consideran conjunto el problema con el de la gestión de grúas del muelle, al ser dependientes el uno del otro. Así, (Chen et al. 2007) presentan un modelo integrado para programar los equipos necesarios para los procesos de carga de contenedores en una terminal, incluyendo la gestión de grúas pórtico de muelles, grúas de la zona de almacenamiento, y vehículos de la zona de almacenamiento. Se propone un algoritmo de búsqueda tabú para resolver el problema. En (Zhen, Chew, y Lee 2011) se contempla el problema integrado de la gestión de muelles y la gestión de la zona de almacenamiento, asignando ubicaciones del patio de contenedores a los buques, ya que son dos Operativas en una terminal de contenedores portuaria 40 40 problemas que dependen el uno del otro. Se propone un modelo un modelo de programación entera mixta para integrar ambos problemas con el fin de minimizar los costes asociados a los procesos, teniendo en cuenta la distancia entre el muelle y la zona de almacenamiento designadas a cada buque. Para resolver el problema a gran escala se desarrolla un algoritmo heurístico, el cual es validado a partir de ejemplos numéricos. Por su parte, (Gambardella et al. 2001) muestran una metodología para la resolución del problema integrado, y demuestran la validez de la misma con un software de simulación. 3.2.2 La relocalización de contenedores en la zona de almacenaje Conocido en la literatura como container pre-marshalling problem (CPMP), el problema de relocalización surge debido a la necesidad de reordenar los contenedores en la zona de almacenamiento con el fin de conseguir la máxima eficiencia en los procesos de carga. Estos movimientos son necesarios para situar los contenedores en una ubicación cercana a la zona en la que van a ser cargados, ya sea en buques u otros modos de transporte, y minimizar los tiempos que deben de pasar los buques, trenes y camiones en la terminal. Este proceso se realiza una vez finalizado el plan de estiba del buque y antes de comenzar el proceso de carga (Caserta y Voß 2009). En la Figura 20 se pueden observar una representación del problema de recolocación de contenedores. En (Caserta, Schwarze, y Voß 2012) se presenta el problema como no polinomial complejo. Para resolverlo, se presenta un modelo matemático que proporciona soluciones óptimas. Sin embargo, debido al comportamiento no polinomial del problema, este método solo es válido para problemas de un tamaño limitado. Pasa resolver problemas de mayor tamaño, se propone un modelo de programación lineal binaria considerando algunas simplificaciones comunes en la literatura. Por otro lado, se propone una heurística simple basada en reglas de reubicación para generar soluciones de calidad en tiempos computacionales muy cortos, con el fin de resolver el problema en tiempo real. La validez de la heurística se comprueba comparando los resultados con los ofrecidos por un optimizador comercial. En (Jovanovic, Tuba, y Voß 2015) se desarrolla un algoritmo basado en la combinación de varias heurísticas y se demuestra la validez del mismo. En lugar de aleatorizar para mejorar el rendimiento del algoritmo que requiere la generación de nuevas soluciones, las diferentes heurísticas se emplean generando pocas soluciones nuevas de calidad y descartando la generación aleatoria. Esto produce una mejora tanto en la calidad de las soluciones encontradas, como en la carga computacional requerida. Por su parte, (Forster y Bortfeldt 2012) presentan una heurística basada en un procedimiento de búsqueda de árbol para resolver el CPMP, y demuestran la validez y la adecuación de la misma para este problema. 41 41 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Figura 20 Representación del CPMP Fuente: (Forster y Bortfeldt 2012) (Y. Lee y Chao 2009) se centran en que los únicos contenedores accesibles en un patio de contenedores son los que se encuentran en la parte superior de cada bloque, lo que genera la necesidad de manipular contenedores que no van a ser cargados. En este trabajo se propone una heurística que consiste en dos subrutinas principales y tres subrutinas menores. Cada uno de los componentes juega un papel diferente en la heurística. En la primera, se establece la trayectoria que deben seguir los contenedores que deben ser cargados proximamente para estar situados sobre aquellos con fecha de carga más tardía. En la segunda, mediante programación lineal entera, se elige la trayectoria que requiere menos movimientos. En (Y. Lee y Hsu 2007) se plantea un modelo matemático para el CPMP. Partiendo de un layout de la zona de almacenamiento y de una determinada secuencia de carga de contenedores, el modelo genera un plan para recolocar los contenedores en el patio. Consiste en un modelo de programación entera compuesta por un problema de flujo de múltiples productos y un conjunto de consideraciones:  La pre-agrupación se realiza en el mismo bloque de contenedores.  En cada bloque solo se agrupan contenedores de un tamaño concreto.  Solo es atendido un barco por grúa y por bloque de contenedores.  La programación de la carga de contenedores es conocida. En (Expósito-Izquierdo, Melián-Batista, y Moreno-Vega 2012) el objetivo del problema es reducir al mínimo el número de movimientos necesarios para organizar todos los contenedores de modo que las reubicaciones adicionales no sean necesarios. Se presenta un método heurístico para resolver el CPMP y se compara con otros métodos propuestos en la literatura. Se elabora un generador de casos capaz de crear problemas de diferentes niveles de dificultad, desde dificultad baja hasta complejos. Para determinar la complejidad se toman en cuentatanto la tasa de ocupación del patio de contenedores como el porcentaje de contenedores con alta prioridad –que deben ser accesibles– que se encuentran situados bajo contenedores de menor prioridad. Los experimentos computacionales corroboran el buen desempeño tanto de la heurística como del generador de escenarios. El problema de secuenciación y programación de grúas 48 48 4 EL PROBLEMA DE SECUENCIACIÓN Y PROGRAMACIÓN DE GRÚAS na vez analizado el estado del arte sobre los diferentes problemas que aparecen en las terminales portuarias de contenedores, se puede considerar una terminal intermodal de contenedores como un sistema complejo compuesto a su vez por múltiples operativas diferentes, las cuales deben ser optimizadas si se pretende conseguir un funcionamiento eficiente de toda la cadena de transporte. Dichas operativas, lejos de ser independientes, mantienen una fuerte relación las unas con las otras, lo que sugiere que el enfoque más apropiado para afrontar el problema es considerar diferentes procesos de manera conjunta. El creciente tráfico de mercancías en las terminales intermodales hace imprescindible planificar las operaciones con el fin de evitar cuellos de botella en los diferentes procesos, los cuales generan costes adicionales a la cadena logística. Estos costes se suelen asociar al uso ineficiente que se haga de los recursos requeridos en una terminal intermodal. Entre los recursos, los muelles de atraque son considerados los más costosos debido al alto coste asociado a la construcción de nuevos muelles, a veces incluso inviable debido a las limitaciones geográficas de la zona. Resulta por tanto fundamental gestionar de manera competente la ocupación de los muelles de atraque en las terminales. Otro aspecto relevante en las terminales de contenedores es el tiempo que pasa la mercancía en la propia terminal. Considerando que la mercancía se transporta siguiendo un modelo intermodal, el proceso que siguen los contenedores en la terminal es: 1. Entrada en la terminal en buques. 2. Descarga del contenedor. 3. Permanece en la zona de almacenamiento. 4. Carga del contenedor en el tren o camión. 5. Salida de la terminal. Este proceso, representado en la Figura 24, es conocido como importanción. También se considera el proceso de exportación que se produce en sentido inverso, llevándose a cabo las entradas de contenedores por carretera o ferrocarril, los cuales son posteriormente cargados y salen de la terminal en buques. U 49 49 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Figura 24. Representación de un proceso de importanción de mercancías El espacio con el que se cuenta en la zona de almacenamiento es también un recurso limitante en una terminal intermodal. Minimizar el tiempo que deben pasar los contenedores en la terminal supone que la necesidad de espacio en la zona de almacenamiento sea menor, lo que se traduce en un uso eficiente del recurso espacio. Esto puede conseguirse sincronizando la carga y descarga de los contenedores de los diferentes transportes, considerando para cada contenedor tanto el vehículo en el que entran a la terminal como en el que salen. 4.1 Definición del problema El problema a resolver consiste en minimizar todo el tiempo de servicio de la terminal intermodal. Este tiempo de servicio incluye desde el instante en que llegan los buques y los trenes, hasta su salida de la terminal una vez concluidos los procesos de descarga y carga de contenedores. Para lograrlo se tendrán en cuenta cuatro operativas que deben ser resueltas: 1. Asignación de muelles. Se le deberá asignar a cada buque una hora de llegada al muelle, siempre y cuando haya disponibilidad. 2. Programación de las grúas de muelle. Se tomará la decisión de cuantas grúas operan sobre cada buque, y que acción realizan en cada instante. 3. Asignación de los instantes de llegada a los trenes. El problema de secuenciación y programación de grúas 50 50 4. Programación de las grúas de trenes. Dicha operativa es análoga a la programación de grúas de muelle. 4.2 Formulación conceptual del problema La complejidad del problema en escenarios de tamaño considerable hace que no se lleve a cabo su resolución por métodos exactos, debido al alto coste computacional que supone. Se buscará encontrar una buena solución del problema a partir de un método heurístico basado en un algoritmo de recocido simulado, como se detalla en el apartado siguiente. No es necesaria por tanto la formulación del modelo matemático del problema, que se presenta a continuación desde un punto de vista conceptual. 4.2.1 Consideraciones y simplificaciones del problema Existen una serie de consideraciones previas a tener en cuenta a la hora de afrontar este problema.  Se considera el problema en una terminal intermodal, por lo que los contenedores que lleguen por vía marítima, serán descargados del buque y cargados en trenes, y viceversa; existiendo también la posibilidad de que un contenedor sea descargado de un buque y cargado en otro barco.  Los contenedores asignados a cada tren y a cada buque son conocidos de antemano, tanto los que deben ser descargados como los que se cargan posteriormente.  La secuencia de carga y descarga de los contenedores de los buques se considera predefinida ya que esta información se determina en el plan de estiba. Por su parte, la secuencia de carga y descarga de los trenes sí es variable y debe determinarse la secuencia óptima.  Sólo podrán cargarse contenedores que previamente hayan sido descargados, ya que el planificador se encarga de organizar todo el intercambio intermodal, desde la llegada del contenedor hasta su salida de la terminal.  El muelle se considera continuo, por lo que la disponibilidad de atraque será determinada por la disponibilidad de grúas pórtico.  Varias grúas pueden actuar simultáneamente sobre un mismo buque o tren.  El tiempo se considera en cuantos, siendo el instante 0 el momento de inicio de la planificación. Debido a la complejidad del problema, se tienen en cuenta varias simplificaciones, todas ellas justificadas y que no modifican la validez de las soluciones alcanzadas.  No se considera existencia de zona de apilamiento interno. Esta decisión se debe a que el planificador cubre todo el intercambio intermodal. 51 51 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal  El transporte terrestre se limita a transporte ferroviario. Los camiones pueden ser considerados trenes con capacidad de carga unitaria.  No se consideran los tiempos de transporte de contenedores entre la zona de operaciones de buques y las zonas de operaciones terrestres, ya que se supone que dichos tiempos son constantes y no representativos.  Los contenedores no se representan individualmente sino como conjuntos de contenedores. Esta simplificación se debe a que es habitual encontrar que un mismo bloque de contenedores compartan origen y destino, y por tanto sean transportados en los mismos buques y trenes. Cada conjunto de contenedores puede ser manipulado únicamente por una grúa en los procesos de carga y de descarga.  Los tiempos de operación de descarga y de carga se consideran dependientes de la capacidad de trabajo de las grúas. 4.2.2 Variables de la planificación Para conseguir minimizar los tiempos de servicio de la terminal, la planificación debe determinar los horarios de llegada de los buques y los trenes dentro de unas ventanas temporales, con el fin de que salgan de la terminal en el menor tiempo posible. El resultado será la asignación de instantes de llegada de los buques y trenes, la asignación de las grúas a dichos buques y la programación de las mismas. Entre las variables del problema se encuentran: T: Conjunto de trenes que forman parte de la planificación. V: Conjunto de buques que forman parte de la planificación. TC: Conjunto de grúas que cargan y descargan contenedores en los trenes. VC: Conjunto de grúas que cargan y descargan contenedores en los barcos. CUTij: Variable binaria. Toma el valor 1 si el contenedor i se descarga desde el tren j, y 0 en caso contrario. CLTij: Variable binaria. Toma el valor 1 si el contenedor i se carga en el tren j, y 0 en caso contrario. CUVij: Variable binaria. Toma el valor 1 si el contenedor i se descarga desde el buque j, y 0 en caso contrario. CLVij: Variable binaria. Toma el valor 1 si el contenedor i se carga desde el buque j, y 0 en caso contrario. TuC: Instante de descarga de un contenedor. TlC: Instante de carga de un contenedor. TinT: Instante de llegada de tren. ToutT: Instante de salida de tren. TinV: Instante de llegada de buque. ToutV: Instante de salida de buque. El problema de secuenciación y programación de grúas 52 52 Este resultado da lugar a una importante reducción de costes debido al mejor aprovechamiento de los recursos disponibles en la terminal. 4.2.3 Función objetivo El objetivo del problema es minimizar la suma total de los tiempos de servicio en la terminal, es decir, el tiempo que pasan los buques y trenes en la terminal intermodal. Para ello se asignan los tiempos te entrada de los diferentes transportes, TinT y TinV. Los barcos y trenes abandonan la terminal cuando se han terminado las operaciones de carga sobre los mismos, por lo que los instantes de salida, ToutT e ToutV se asignan en función del instante de llegada, siendo anterior la salida si existe disponibilidad de grúas en el momento en el que el buque o tren llega a la terminal. Por tanto, la mejor solución no estará siempre asociada a que los trenes y los barcos hagan su entrada en la terminal tan pronto como lo permita su ventana temporal, ya que la disponibilidad de las grúas es determinante para terminar en el menor tiempo posible el intercambio intermodal. Así, en un problema genérico con N buques y M trenes, se puede representar la función objetivo como 𝑀𝑖𝑛 ∑𝑇𝑜𝑢𝑡𝑉𝑖+∑𝑇𝑜𝑢𝑡𝑇𝑗 𝑗, 𝑖 𝑖∈𝑁; 𝑗∈𝑀 4.2.4 Restricciones del problema La complejidad del problema presentado tiene su impacto en el número de restricciones que aparecen a la hora de plantear una solución válida a la planificación. Se Supone un problema en el que hay que gestionar el intercambio intermodal entre N buques y M trenes en una terminal, donde se cuentan con Q grúas que pueden operar en muelles y R grúas para operar sobre los trenes. El conjunto total de contenedores se representa por C -CUV para los contenedores que llegan a la terminal en buque y CUT para los contenedores que llegan a la terminal en tren; CLV y CLT para los contenedores que son cargados en buques y trenes respectivamente-, los cuales se descargan en el instante UC y se cargan en el instante LC. Las restricciones a tener en cuenta en el problema son:  Un contenedor no puede ser cargado antes de ser descargado. 𝑈𝐶𝑖<𝐿𝐶𝑖 ∀ 𝑖∈𝐶  Tanto los trenes como los buques deben entrar en la terminal en un instante dentro de su ventana temporal. 𝐸𝑎𝑇𝑖≤𝑇𝑖𝑛𝑉𝑖≤𝐿𝑎𝑇𝑖 ∀ 𝑖∈𝑁 𝐸𝑎𝑇𝑖≤𝑇𝑖𝑛𝑇𝑖≤𝐿𝑎𝑇𝑖 ∀ 𝑖∈𝑀  Los contenedores no pueden comenzar a ser descargados antes de que el tren o buque que lo transporta haya llegado a la terminal. 53 53 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal 𝑇𝑖𝑛𝑉𝑖<𝑇𝑢𝐶𝑗·𝐶𝐿𝑉𝑗𝑖 ∀ 𝑖 ∈𝑁,∀ 𝑗∈𝐶 𝑇𝑖𝑛𝑇𝑖<𝑇𝑢𝐶𝑗·𝐶𝐿𝑇𝑗𝑖 ∀ 𝑖 ∈𝑀,∀ 𝑗∈𝐶  Los barcos y los trenes no pueden salir de la terminal hasta que no han sido completamente cargados. 𝑇𝑜𝑢𝑡𝑉𝑖>𝑇𝑙𝐶𝑗·𝐶𝐿𝑉𝑗𝑖 ∀ 𝑖 ∈𝑁,∀ 𝑗∈𝐶 𝑇𝑜𝑢𝑡𝑇𝑖>𝑇𝑙𝐶𝑗·𝐶𝐿𝑇𝑗𝑖 ∀ 𝑖 ∈𝑀,∀ 𝑗∈𝐶 Nota: Debido a que la resolución del problema se lleva a cabo empleado un método heurístico, no es necesaria la representación matemática de todas las restricciones del sistema. 4.3 Ejemplo conceptual Sea una terminal intermodal a la que deben llegar 3 trenes cargados cada uno con 2 conjuntos de contenedores y 2 buques cargados con 3 conjuntos de contenedores cada uno. Cada tren y cada buque tiene una ventana temporal dentro de la cual pueden hacer su entrada a la terminal, definida por un early arrival time (EaT) y un last arrival time (LaT). Se consideran los datos reflejados en la Tabla 3: Identificador EaT LaT Contenedores a descargar Contenedores a cargar Buque 1 5 20 A, B, C G, I, L Buque 2 15 45 D, E, F H, J, K Tren 1 25 45 G, H A, D Tren 2 10 25 I, J C, E Tren 3 20 50 K, L F, B Tabla 3. Datos de entrada del problema El tiempo de carga y descarga de cada conjunto de contenedores se estima constante, de duración 5. Se suponen que existen dos grúas pórticos capaces de descargar y cargar contenedores en los buques, y otras dos grúas que pueden operar sobre los trenes. El problema consiste en determinar un instante de llegada a cada buque y a cada tren, así como asignar las tareas de carga y descarga a las diferentes grúas. El objetivo es que el intercamio intermodal se realice lo antes posible, por lo que se busca minimizar la suma total de los instantes de salida. Una solución lógica sería decidir que cada buque y cada tren entre en la terminal tan pronto como su ventana temporal lo permita. Para la gestión de grúas, una opción es decidir realizar todas las descargas antes de ejecutar las cargas de contenedores. En la Tabla 4 se refleja la programación de dicha gestión. El problema de secuenciación y programación de grúas 54 54 Instante 5 10 15 20 25 30 35 40 Grúa B1 Unload A Unload C Unload D Unload F Load H Load I Load J Grúa B2 Unload B Unload E Load G Load L Load K Grúa T1 Unload I Unload K Unload H Load A Load C Load F Grúa T2 Unload J Unload L Unload G Load D Load E Load B Tabla 4. Programación de grúas priorizando descargas Esta programación daría como resultado los siguientes instantes de salida, considerando que cada buque y cada tren abandona de la terminal cuando ha terminado de ser cargado son los recogidos en la Tabla 5: Identificador Instante de Salida Buque 1 40 Buque 2 45 Tren 1 35 Tren 2 40 Tren 3 45 TOTAL 205 Tabla 5. Instantes de salida priorizando descargas Un nuevo criterio, donde se priorice las cargas de contenedores ante las descargas, daría lugar a la programación reflejada en la Tabla 6. Instante 5 10 15 20 25 30 35 40 Grúa B1 Unload A Unload C Unload D Unload F Load H Load I Load J Grúa B2 Unload B Unload E Load G Load L Load K Grúa T1 Unload I Load C Load E Unload H Load A Unload K Load F 55 55 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Grúa T2 Unload J Unload L Unload G Load D Load B Tabla 6. Programación de grúas priorizando cargas Esta programación daría como resultado los siguientes instantes de salida, considerando que cada buque y cada tren abandona de la terminal cuando ha terminado de ser cargado son los recogidos en la Tabla 7. Identificador Instante de Salida Buque 1 40 Buque 2 45 Tren 1 35 Tren 2 25 Tren 3 45 TOTAL 190 Tabla 7. Instantes de salida priorizando cargas Se observa cómo se ha conseguido reducir sustancialmente la suma total de los instantes de salida con respecto al criterio de priorizar las descargas de los buques y trenes. Sin embargo, el criterio de dar prioridad a las cargas de los buques y los trenes no tiene por qué se la mejor opción para resolver el problema, por lo que es imprescindible el desarrollo de un algoritmo capaz de ofrecer buenas soluciones en escenarios complejos. Metodología: El recocido simulado 56 56 5 METODOLOGÍA: EL RECOCIDO SIMULADO l problema presentado se corresponde con un problema de optimización de tipo no polinomial complejo (NP). La alta complejidad del problema hace que la resolución del mismo a través de métodos exactos se limite a problemas de un tamaño reducido. Para este tipo de problemas, el número de soluciones posibles crece exponencialmente a medida que el número de variables y restricciones aumentan, por lo que se puede concluir que la búsqueda exhaustiva de todas las soluciones con el fin de encontrar el óptimo no es factible para problemas de un tamaño considerable. Por tanto, ante la dificultad de emplear métodos exactos para la búsqueda del óptimo en problemas complejos, en la literatura se pueden encontrar heurísticas y metaheurísticas destinadas a la resolución de este tipo de problemas. La RAE define una heurísta como “manera de buscar la solución de un problema mediante métodos no rigurosos, como por tanteo, reglas empíricas, etc.” En la misma línea, (Arbelaitz 2002) define:  Técnica que explora buenas soluciones, cercanas al óptimo, en un tiempo computacional razonable, sin poder garantizar ni factibilidad ni optimalidad y en muchos casos incapaz de indicar la distancia a la que queda el óptimo.  Conjunto de procedimientos simples, a menudo basados en el sentido común, que se supone ofrecerá una buena solución, aunque no necesariamente óptima, a problemas difícilies de un modo fácil y rápido. Se deduce que la utilización de heurísticas no garantiza encontrar un óptimo global ni local. Por el contrario, los métodos heurísticos no requieren especificación matemática completa del sistema, por lo que se consiguen modelos más “realistas” que los empleados en los métodos exactos. Esto lleva a la cuestión de si es mejor conseguir una solución exacta de un modelo aproximado o una solución aproximada de un modelo “exacto”. El principal motivo para utilizar heurísticas ante modelos exactos es el tiempo de ejecución, mucho menor en las heurísticas. Además, las heurísticas cuentan con otra ventaja ante los métodos exactos, y es la mayor flexibilidad en el manejo de las características del modelo, lo que hace que sean más explicativos. Por otro lado, el mayor inconveniente de las heurísticas no es sólo que no garantizan el óptimo, sino que tampoco ofrecen información de la bondad de la solución obtenida. Por tanto, si se necesita una solución E 57 57 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal precisa, debería emplearse un método exacto. Las metaheurísticas se basan en dotar a una heurística de una guía de acuerdo a algún concepto de la naturaleza, la biología, la inteligencia artificial, las matemáticas o la física. El objetivo es orientar a la heurística modificando las soluciones que ofrecen las heurísticas para encontrar otra mejor hasta que no se pueda encontrar ninguna solución que presente mejora en el vecindario de la solución actual. El vecindario de una solución se define como el conjunto de soluciones obtenidas a partir de la misma por medio de una operación básica llamada movimiento. Los movimientos más comunes para pasar de una solución a otra son:  Descenso aleatorio: Cada movimiento se hace eligiendo una solución aleatoria del vecindario. El proceso termina cuando todas las soluciones del vecindario sean peores que la solución actual.  Método descendente de la mayor pendiente: Se exploran todas las soluciones del vecindario. El movimiento se hace a la mejor solución del mismo. El gran inconveniente de estos procesos a simple vista es la posibilidad de caer en un óptimo local. Para contrarrestar esto, las metaheurísticas deben ser capaces de escapar de los óptimos locales para intentar encontrar el óptimo global. 5.1 Introducción a la heurística de Recocido Simulado El recocido simulado, también denominado Simulated Annealing (en adelante, SA), enfriamiento simulado, método descendente probabilistico, o relajación estocástica, es un algoritmo de búsqueda metaheurística de optimización global, basado en el proceso de recocido del acero y las cerámicas para obtener material cristalizado. Esta técnica consiste en calentar el material para dotar a los átomos de energía y que así puedan desplazarse. Posteriormente, se deja enfriar el material lentamente para hacer que recristalice en configuraciones con menor energía que la inicial. Cuanto más lento sea el procedimiento de enfriamiento del material, mayor probabilidad se tiene de conseguir un cristal perfectamente estructurado con baja energía interna. Las ideas en las que se basa el algoritmo fueron introducidas en (Metropolis et al. 1953), en un algoritmo para simular el proceso de enfriamiento antes descrito. Posteriormente, fue desarrollado independientemente en (Kirkpatrick, Gelatt, y Vecchi 1983) y (Černý 1985) donde se propuso que este algoritmo podía ser empleado para resolver problemas de optimización. El algoritmo parte de una solución aleatoria. A partir de ella, genera un vecindario de la misma y aleatoriamente se elige una solución perteneciente al vecindario, la cual se evalúa y se compara con la solución inicial. Si la solución nueva es mejor que la anterior, se adopta esta nueva solución y se examina su vecindario. Este procedimiento se repite hasta que se alcanza una condición de parada. Para evitar caer en óptimos locales, el recocido simulado permite el movimiento hacia soluciones peores según una determinada probabilidad, la cual disminuye a medida que aumentan las iteraciones mediante un parámetro que se llama Temperatura (T), por analogía con el método de cristalización de materiales. La temperatura parte de valores muy altos y tiende a cero asintóticamente. Para valores muy bajos de T, la probabilidad de transición a una solución peor es prácticamente nula. Otros parámetros del algoritmo son la función de enfriamiento que Metodología: El recocido simulado 64 64 Figura 26. Visualización del comportamiento convergente del algoritmo 5.3.3 Codificación de la solución La resolución del problema consiste en asignar a los buques y a los trenes un instante de llegada dentro de su ventana temporal a partir del cual se inicia el proceso del intercambio intermodal. La planificación determina que dicho intercambio concluye cuando todos los buques y los trenes abandonan la terminal. Al considerarse que los buques y los trenes salen de la terminal cuando se les han cargado los contenedores pertinentes, se debe incluir en la solución el instante de salida de cada tren y cada buque. Por tanto la codificación de la solución se expresa como aparece en la BUQUES Identificador Inicio Ventana Temporal Fin Ventana Temporal Instante de llegada Instante de salida B001 5 20 5 40 B002 15 45 15 45 Tabla 10. Codificación de la solución de los buques 65 65 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal TRENES Identificador Inicio Ventana Temporal Fin Ventana Temporal Instante de llegada Instante de salida T001 25 45 25 35 T002 10 25 10 25 T003 20 50 20 45 Tabla 11. Codificación de la solución de los trenes Las asignaciones de los instantes de llegada se toman en función de la disponibilidad de las grúas encargadas de las operaciones de descargar y cargar los contenedores. Por tanto, la codificación de la solución incluye la programación de las grúas especificando qué tareas ejecutan en cada instante de tiempo. Las operaciones de carga se representan con ‘1’, mientras las operaciones de descarga son identificadas con ‘-1’. En la Tabla 12 se muestra un ejemplo de la codificación de la programación de una grúa de buque. Grúa de buque 1 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tipo de operación -1 -1 -1 -1 1 1 1 Contenedor A C D F H I J Instante 5 10 15 20 30 35 40 Tabla 12. Programación de una grúa de buque Resultados 66 66 6 RESULTADOS on el fin de verificar la validez del algoritmo, se ha elaborado una batería de problemas cuya resolución ofrece una visión global sobre el comportamiento del algoritmo ante el problema de optimización presentado. Dicha batería, ha sido también resuelta empleando otras heurístias muy comunes en problemas de optimización, como son un algoritmo genético y una búsqueda tabú, con el fin de comparar y evaluar el comportamiento de la heurítica de recocido simulado. 6.1 Batería de problemas La batería de problemas propuesta consta de 16 escenarios. En cada uno de ellos se lleva a cabo la asignación de instantes de llegada a un determinado número de buques y trenes, así como la programación de las grúas para cubrir todas las tareas de carga y descarga de contenedores, con el objetivo de minimizar la suma total de todos los instantes de salida. Los archivos de entrada deben contener toda la información necesaria para resolver el problema:  Número de buques que llegan a la terminal.  Número de trenes que llegan a la terminal.  Número de grúas para descargar y cargar los buques.  Número de grúas para descargar y cargar los trenes.  Contenedores a descargar de cada buque y de cada tren.  Contenedores a cargar en cada buque y en cada tren.  Ventana temporal de entrada a la terminal de cada buque y cada tren.  Capacidad de operación de cada grúa, expresada en tiempo que necesita para descargar y cargar un conjunto de contenedores. Los 16 casos posibles se corresponden con cuatro casos de entradas de trenes y buques cargados con contenedores. Cada uno de los cuatro casos se ha resuelto a su vez con cuatro escenarios diferentes de disponibilidad de grúas. En la Tabla 13 se muestran resumidos los 16 escenarios de la batería. C 67 67 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Escenario Nº Buques Nº Trenes Nº Grúas Buque Nº Grúas Tren Escenario 1 2 3 1 1 Escenario 2 2 3 2 2 Escenario 3 2 3 3 3 Escenario 4 2 3 4 4 Escenario 5 2 4 1 1 Escenario 6 2 4 2 2 Escenario7 2 4 3 3 Escenario 8 2 4 4 4 Escenario 9 5 10 1 1 Escenario 10 5 10 2 2 Escenario 11 5 10 3 3 Escenario 12 5 10 4 4 Escenario 13 10 20 1 1 Escenario 14 10 20 2 2 Escenario 15 10 20 3 3 Escenario 16 10 20 4 4 Tabla 13. Escenarios de la batería de problemas El algoritmo programado resuelve el problema presentado de manera eficiente. Para hacer comprensible la solución propuesta, se genera un archivo en el que se reflejan las asignaciones dadas. Esta información se representa en forma de tablas. Resultados 68 68 A modo de ejemplo, se plasma la representación de la solución del escenario 3, en el que hay que programar la carga y descarga de contenedores de dos buques y tres trenes, contando con tres grúas para operar sobre buques y tres grúas de trenes. En la Tabla 14 se observa la representación de la solución para las entidades buque, y de forma análoga en la Tabla 15 se muestra la solución para los trenes. BUQUES Identificador Inicio ventana temporal Fin ventana temporal Instante de llegada Instante de salida B001 10 40 10 35 B002 20 50 20 30 Tabla 14. Representación de solución de los buques TRENES Identificador Inicio ventana temporal Fin ventana temporal Instante de llegada Instante de salida T001 5 35 15 35 T002 15 45 15 25 T003 25 55 25 35 Tabla 15. Representación de solución de los trenes En las tablas se refleja el instante de salida de cada entidad, que es lo que se pretende minimizar en este problema. En esta situación, el valor de la función objetivo -suma de los instants de salida-, es de 160. Además de este valor, el tiempo computacional empleado por el algoritmo también se exporta en la solución. Por otro lado, la resolución del problema también se ocupa de asignar a cada grúa una tarea en cada instante de tiempo. En la nomenclatura usada se les ha denominado a las tareas de carga como operaciones de tipo 1, y a las de descarga tipo -1. Estas asignaciones también se exportan en forma de tabla, como se muestra a modo de ejemplo. (Ver Tabla 16, Tabla 17, Tabla 18, Tabla 19, Tabla 20 y Tabla 21). Grúa de buque 1 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tipo de operación -1 -1 1 1 1 1 Contenedor Ab Db Jb Ib Lb Gb Instante 10 20 25 30 35 45 Tabla 16. Asignación de tareas a la grúa de buque 1 Grúa de buque 2 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tipo de operación -1 -1 1 1 1 Contenedor Bb Eb Gb Kb Hb Instante 10 20 25 30 35 Tabla 17. Asignación de tareas a la grúa de buque 2 69 69 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Grúa de buque 3 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tipo de operación -1 -1 1 1 - Contenedor Cb Fb Hb Lb - Instante 10 20 25 30 - Tabla 18. Asignación de tareas a la grúa de buque 3 Grúa de tren 1 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tipo de operación -1 -1 -1 1 -1 Contenedor Hb Ib Kb Cb Kb Instante 15 20 25 30 30 Tabla 19. Asignación de tareas a la grúa de tren 1 Grúa de tren 2 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tipo de operación -1 1 -1 1 1 Contenedor Gb Bb Lb Eb Bb Instante 15 20 25 30 35 Tabla 20. Asignación de tareas a la grúa de tren 2 Grúa de tren 3 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tipo de operación -1 1 1 1 - Contenedor Jb Ab Fb Db - Instante 15 20 25 30 - Tabla 21. Asignación de tareas a la grúa de tren 3 6.2 Resultados Para calificar la adecuación de la heurística al problema resuelto, se han comparado los resultados alcanzados con el algoritmo de recocido simulado con los ofrecidos por otros dos algoritmos, uno basado en una búsqueda tabú y un algoritmo genético. Con el fin de encontrar una buena relación entre la bondad de la solución y el tiempo computacional requerido, se ha llevado a cabo un proceso de parametrización. A partir del mismo se han definido los parámetros que se reflejan en la Tabla 22. Parámetro Valor T0 50 Resultados 70 70 Parámetro Valor Tmin 0,3 L {2 𝑠𝑖 10<𝑡<50 4 𝑠𝑖 2<𝑡<10 6 𝑠𝑖 0,3<𝑡<2 TamVec Nº buques + Nº trenes β {0,01 𝑒𝑠𝑐𝑒𝑛𝑎𝑟𝑖𝑜𝑠 1 − 4 0,02 𝑒𝑠𝑐𝑒𝑛𝑎𝑟𝑖𝑜𝑠 5 − 8 0,03 𝑒𝑠𝑐𝑒𝑛𝑎𝑟𝑖𝑜𝑠 9 − 12 0,06 𝑒𝑠𝑐𝑒𝑛𝑎𝑟𝑖𝑜𝑠 13−16 Tabla 22. Parámetros del algoritmo Los resultados alcanzados por una y otra heurística se muestran en la Tabla 23. Recocido Simulado Búsqueda Tabú Algoritmo Genético Tiempo de ejecución Solución Tiempo de ejecución Solución Tiempo de ejecución Solución Escenario 1 49,47 265 268,72 265 11,66 265 Escenario 2 65,93 180 289,04 185 25,33 180 Escenario 3 92,52 160 319,64 160 37,00 160 Escenario 4 124,79 150 351,38 150 52,71 150 Escenario 5 39,50 390 286,69 390 50,88 385 Escenario 6 48,67 245 307,35 245 54,87 245 Escenario 7 69,84 220 345,99 220 50,80 220 Escenario 8 87,47 200 386,10 200 66,45 200 Escenario 9 319,24 2200 562,70 2180 354,39 2125 Escenario 10 274,53 1065 509,52 1075 325,41 1035 Escenario 11 289,21 755 563,11 785 391,71 755 Escenario 12 373,57 620 653,82 655 478,53 620 Escenario 13 1793,86 8700 2175,10 8665 2762,93 8640 Escenario 14 1466,61 4400 1873,02 4285 2545,62 4215 Escenario 15 1273,90 2810 1749,12 2860 2283,95 2765 Escenario 16 1133,67 2230 1567,35 2230 2340,65 2165 Tabla 23. Comparativa de resultados Se observa que los resultados alcanzados por el algoritmo de recocido simulado son equiparable a los que alcanzan otras heurísticas tanto en la bondad de las soluciones como en tiempos computacionales, si bien es cierto que el algoritmo genético encuentra mejores soluciones en problemas de tamaño grande. En la Figura 27 se muestran los resultados alcanzados en forma de gráfica. 71 71 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Figura 27. Comparativa de resultados Se aprecia también como los tiempos computacionales para resolver el problema aumentan a mayor velocidad que el tamaño del mismo debido al carácter NP del problema. Este crecimiento de los tiempos computacionales en todas las heurísticas se plasma en la Figura 28. Especialmente en el escenario 13, donde el tamaño del problema duplica al del escenario anterior (10 buques y 20 trenes ante los 5 buques y 10 trenes del escenario 12). 265 180 160 150 265 185 160 150 265 180 160 150 140 160 180 200 220 240 260 280 Escenario 1 Escenario 2 Escenario 3 Escenario 4 Comparativa de Resultados (1) Algoritmo Genético Búsqueda Tabú Recocido Simulado 385 245 220 200 390 245 220 200 390 245 220 200 190 240 290 340 390 Escenario 5 Escenario 6 Escenario 7 Escenario 8 Comparativa de Resultados (2) Algoritmo Genético Búsqueda Tabú Recocido Simulado 2125 1035 755 620 2180 1075 785 655 2200 1055 755 620 600 800 1000 1200 1400 1600 1800 2000 2200 Escenario 9 Escenario 10 Escenario 11 Escenario 12 Comparativa de Resultados (3) Algoritmo Genético Búsqueda Tabú Recocido Simulado 8640 4215 2765 2165 8665 4285 2860 2230 8700 4400 2810 2230 2100 3100 4100 5100 6100 7100 8100 Escenario 13 Escenario 14 Escenario 15 Escenario 16 Comparativa de Resultados (4) Algoritmo Genético Búsqueda Tabú Recocido Simulado Resultados 72 72 Figura 28. Tiempos de computación Otro aspecto a considerar es la gran diferencia que se observa entre contar con una grúa de cada tipo o con más grúa, ya que esto permite las cargas y descargas en paralelo y ofrece mucha más flexibilidad en la gestión de las operaciones. 0,00 500,00 1000,00 1500,00 2000,00 2500,00 3000,00 Tiempos de Computación (s) Recocido Simulado Búsqueda Tabú Algoritmo Genético 73 73 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal 7 CONCLUSIONES a evolución hacia un mercado mundial globalizado hace del transporte de mercancías una pieza fundamental en el buen funcionamiento del mismo. La cadena logística debe ser clave para conseguir llevar a cabo el transporte de mercancías de manera eficiente. Debido a la necesidad de cubrir distancias cada vez mayores propiciadas por la lejanía entre los focos productores y los consumidores, la tendencia es el transporte intermodal. El transporte intermodal consta de 3 etapas diferenciadas: el trayecto principal, que cubre grandes distancias; el transprte terrestre, que une la terminal intermodal con los clientes y proveedores; y el transbordo en la terminal, donde se lleva a cabo el cambio de modo de la mercancía. Esta última etapa es de gran complejidad, al reunir muchas operaciones diferentes las cuales deben ser sincronizadas y optimizadas para conseguir una cadena de transporte eficiente. En esta línea, se ha llevado a cabo un análisis del estado del arte de las diferentes operativas que se deben resolver para gestionar una terminal de manera eficiente, diferenciando las operaciones que se dan en la zona de muelle, la zona de almacenamiento y la zona de transporte terrestre de la terminal. A partir de este análisis se ha remarcado la necesidad de considerar varias operativas integradas en la resolución del problema del intercabio intermodal. A continuación se ha explicado el problema a resolver, el cual ocupa el problema de asignación de muelles a los buques y la programación de las grúas para agilizar los procesos de carga y descarga, consiguiendo reducir el tiempo que deben pasar los buques y los trenes en la terminal. Para su resolución se ha desarrollado un algoritmo basado en la heurística de recocido simulado para resolver un problema de secuenciación de tareas y programación de grúas con el fin de optimizar el intercambio de mercancías en una terminal intermodal. El algoritmo se ha aplicado a una batería de 16 problemas y se ha analizado el comportamiento del mismo. Los resultados obtenidos se han comparado a los que se han alcanzado empleando un algoritmo genético y un algoritmo basada en una búsqueda tabú. De esta comparativa se concluye la adecuación de la heurística de recocido simulado al problema resuelto, alcanzando soluciones tan buenas como las ofrecidas por las otras L Referencias bibliográficas 80 80 Nguyen, Thanh Trung, Ngoc Tuan Tran, y Tuan Anh Duong. 2009. «Informed simulated annealing for optimizing dorm room assignments.» Proceedings - 2009 1st Asian Conference on Intelligent Information and Database Systems, ACIIDS 2009: 265-70. Nishimura, Etsuko, Akio Imai, y Stratos Papadimitriou. 2001. «Berth allocation planning in the public berth system by genetic algorithms.» European Journal of Operational Research 131(2): 282-92. ———. 2005. «Yard trailer routing at a maritime container terminal.» Transportation Research Part E: Logistics and Transportation Review 41(1): 53-76. Osman, Ibrahim Hassan. 1993. «Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem.» Annals of Operations Research 41(4): 421-51. Peterkofsky, Roy I., y Carlos F. Daganzo. 1990. «A branch and bound solution method for the crane scheduling problem.» Transportation Research Part B: Methodological 24(3): 159-72. Sammarra, Marcello, Jean François Cordeau, Gilbert Laporte, y M. Flavia Monaco. 2007. «A tabu search heuristic for the quay crane scheduling problem.» Journal of Scheduling 10: 327-36. Scheuerer, Stephan. 2006. «A tabu search heuristic for the truck and trailer routing problem.» Computers and Operations Research 33: 894-909. Southworth, Frank, y Bruce E Peterson. 2000. «Intermodal and international freight network modeling.» Transportation Research Part C: Emerging Technologies 8(1-6): 147-66. Stahlbock, Robert, y Stefan Voß. 2008. «Operations research at container terminals: A literature update.» OR Spectrum 30(1): 1-52. Tavakkoli-Moghaddam, R. et al. 2009. «An efficient algorithm for solving a new mathematical model for a quay crane scheduling problem in container ports.» Computers and Industrial Engineering 56(1): 241-48. Thangiah, S R, I H Osman, y T Sun. 1994. «Hybrid genetic algorithm, simulated annealing and tabu search methods for vehicle routing problems with time windows.» Computer Science Department Slippery Rock University Technical Report SRU CpScTR9427: 1-37. Tierney, Kevin, Dario Pacino, y Rune Møller Jensen. 2014. «On the complexity of container stowage planning problems.» Discrete Applied Mathematics 169(December): 225-30. Villegas, Juan G. et al. 2013. «A matheuristic for the truck and trailer routing problem.» European Journal of Operational Research 230(2): 231-44. Vis, I. F A, R. De Koster, K. J. Roodbergen, y L. W P Peeters. 2001. «Determination of the number of automated guided vehicles required at a semi-automated container terminal.» Journal of the Operational Research Society 52(4): 409-17. Vis, Iris F a, y René De Koster. 2003. «Transshipment of containers at a container terminal: An overview.» European Journal of Operational Research 147(1): 1-16. Vis, Iris F. a., René (M.) B. M. de Koster, y Martin W. P. Savelsbergh. 2005. «Minimum Vehicle Fleet Size Under Time-Window Constraints at a Container Terminal.» Transportation Science 39(2): 249-60. Vis, Iris F.a. 2006. «Survey of research in the design and control of automated guided vehicle 81 81 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal systems.» European Journal of Operational Research 170(3): 677-709. Voß, Stefan, Robert Stahlbock, y Dirk Steenken. 2004. «Container terminal operation and operations research - a classification and literature review.» OR Spectrum 26(1): 3-49. Wang, Jiunn-Chin. 2012. «A Multistart Simulated Annealing Algorithm for the Quadratic Assignment Problem.» 2012 Third International Conference on Innovations in Bio-Inspired Computing and Applications: 19-23. Wilson, Id, Pa Roach, y Ja Ware. 2001. «Container stowage pre-planning: using search to generate solutions, a case study.» Knowledge-Based Systems 14(3-4): 137-45. Yan, Wei, Youfang Huang, Daofang Chang, y Junliang He. 2011. «An investigation into knowledgebased yard crane scheduling for container terminals.» Advanced Engineering Informatics 25(3): 462-71. Zhang, Chuqian et al. 2003. «Storage space allocation in container terminals.» Transportation Research Part B: Methodological 37(10): 883-903. Zhen, Lu, Ek Peng Chew, y Loo Hay Lee. 2011. «An Integrated Model for Berth Template and Yard Template Planning in Transshipment Hubs.» Transportation Science 43(45(5)): 483-504. Zhu, Minghua, Xiumin Fan, Huanchong Cheng, y Qichang He. 2010. «Modeling and simulation of automated container terminal operation.» Journal of Computers 5(6): 951-57. Anexo I. Batería de problemas 82 82 ANEXO I. BATERÍA DE PROBLEMAS A continuación se presenta la batería de problemas resuelta para demostrar la validez del algoritmo. Los datos de entrada de todos los escenarios son:  Las ventanas temporales de los buques y los trenes.  Los tiempos de descarga y de carga de cada grúa. La configuración de los 16 escenarios se basa en 4 modelos de entrada de buques y trenes resueltos cada uno en 4 escenarios posibles, dependiendo de la disponibilidad de grúas. Escenarios 1 a 4 Identificador transporte Contenedores a descargar Contenedores a cargar Inicio ventana temporal Fin ventana temporal V001 Ab,Bb,Cb Ib,Kb,Lb 10 40 V002 Db,Eb,Fb Jb,Gb,Hb 20 50 T001 Gb,Hb Eb,Fb 5 35 T002 Ib,Jb Ab,Bb 15 45 T003 Kb,Lb Cb,Db 25 55 Tabla 24. Entradas de buques y trenes para los escenarios 1 a 4 Escenario 1 Identificador grúa Tipo de grúa Tiempo de descarga Tiempo de carga C001 Barco 5 5 C001 Tren 5 5 Tabla 25. Grúas disponibles en el escenario 1 Escenario 2 Identificador grúa Tipo de grúa Tiempo de descarga Tiempo de carga C001 Barco 5 5 C002 Barco 5 5 C001 Tren 5 5 C002 Tren 5 5 Tabla 26. Grúas disponibles en el escenario 2 83 83 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Escenario 3 Identificador grúa Tipo de grúa Tiempo de descarga Tiempo de carga C001 Barco 5 5 C002 Barco 5 5 C003 Barco 5 5 C001 Tren 5 5 C002 Tren 5 5 C003 Tren 5 5 Tabla 27. Grúas disponibles en el escenario 3 Escenario 4 Identificador grúa Tipo de grúa Tiempo de descarga Tiempo de carga C001 Barco 5 5 C002 Barco 5 5 C003 Barco 5 5 C004 Barco 5 5 C001 Tren 5 5 C002 Tren 5 5 C003 Tren 5 5 C004 Tren 5 5 Tabla 28. Grúas disponibles en el escenario 4 Anexo I. Batería de problemas 84 84 Escenarios 5 a 8 Identificador transporte Contenedores a descargar Contenedores a cargar Inicio ventana temporal Fin ventana temporal V001 Ab,Bb,Cb,Db Ib,Kb,Lb,Ob 10 40 V002 Eb,Fb,Gb,Hb Jb,Mb,Nb,Pb 20 50 T001 Ob,Pb Eb,Fb 5 35 T002 Ib,Jb Ab,Bb 15 45 T003 Kb,Lb Cb,Db 25 55 T004 Mb,Nb Gb,Hb 30 65 Tabla 29. Entradas de buques y trenes en los escenarios 5 a 8 Escenario 5 Identificador grúa Tipo de grúa Tiempo de descarga Tiempo de carga C001 Barco 5 5 C001 Tren 5 5 Tabla 30. Grúas disponibles en el escenario 5 Escenario 6 Identificador grúa Tipo de grúa Tiempo de descarga Tiempo de carga C001 Barco 5 5 C002 Barco 5 5 C001 Tren 5 5 C002 Tren 5 5 Tabla 31. Grúas disponibles en el escenario 6 Escenario 7 Identificador grúa Tipo de grúa Tiempo de descarga Tiempo de carga C001 Barco 5 5 C002 Barco 5 5 C003 Barco 5 5 C001 Tren 5 5 C002 Tren 5 5 C003 Tren 5 5 Tabla 32. Grúas disponibles en el escenario 7 85 85 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Escenario 8 Identificador grúa Tipo de grúa Tiempo de descarga Tiempo de carga C001 Barco 5 5 C002 Barco 5 5 C003 Barco 5 5 C004 Barco 5 5 C001 Tren 5 5 C002 Tren 5 5 C003 Tren 5 5 C004 Tren 5 5 Tabla 33. Grúas disponibles en el escenario 8 Anexo I. Batería de problemas 86 86 Escenarios 9 a 12 Identificador transporte Contenedores a descargar Contenedores a cargar Inicio ventana temporal Fin ventana temporal V001 Ab,Bb,Cb,Db ab,bb,cb,db 10 40 V002 Eb,Fb,Gb,Hb eb,fb,gb,hb 20 50 V003 Ib,Jb,Kb,Lb ib,jb,kb,lb 15 35 V004 Mb,Nb,Ob,Pb mb,nb,ob,pb 30 70 V005 Qb,Rb,Sb,Tb qb,rb,sb,tb 50 90 T001 ab,bb Ab,Bb 5 35 T002 cb,db Cb,Db 15 45 T003 eb,fb Eb,Fb 25 55 T004 gb,hb Gb,Hb 30 65 T005 ib,jb Ib,Jb 10 35 T006 kb,lb Kb,Lb 15 60 T007 mb,nb Mb,Nb 5 20 T000 ob,pb Ob,Pb 15 45 T009 qb,rb Qb,Rb 25 55 T0010 sb,tb Sb,Tb 30 65 Tabla 34. Entradas de buques y trenes en los escenarios 9 a 12 Escenario 9 Identificador grúa Tipo de grúa Tiempo de descarga Tiempo de carga C001 V 5 5 C001 T 5 5 Tabla 35. Grúas disponibles en el escenario 9 Escenario 10 Identificador grúa Tipo de grúa Tiempo de descarga Tiempo de carga C001 V 5 5 C002 V 5 5 C001 T 5 5 C002 T 5 5 Tabla 36. Grúas disponibles en el escenario 10 Escenario 11 Identificador grúa Tipo de grúa Tiempo de descarga Tiempo de carga C001 Barco 5 5 C002 Barco 5 5 C003 Barco 5 5 C001 Tren 5 5 C002 Tren 5 5 C003 Tren 5 5 Tabla 37. Grúas disponibles en el escenario 11 87 87 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Escenario 12 Identificador grúa Tipo de grúa Tiempo de descarga Tiempo de carga C001 Barco 5 5 C002 Barco 5 5 C003 Barco 5 5 C004 Barco 5 5 C001 Tren 5 5 C002 Tren 5 5 C003 Tren 5 5 C004 Tren 5 5 Tabla 38. Grúas disponibles en el escenario 12 Anexo I. Batería de problemas 88 88 Escenarios 13 a 16 Identificador transporte Contenedores a descargar Contenedores a cargar Inicio ventana temporal Fin ventana temporal V001 Aa,Ba,Ca,Da aa,ba,ca,da 10 40 V002 Ea,Fa,Ga,Ha ea,fa,ga,ha 20 75 V003 Ia,Ja,Ka,La ia,ja,ka,la 25 45 V004 Ma,Na,Oa,Pa ma,na,oa,pa 20 50 V005 Qa,Ra,Sa,Ta qa,ra,sa,ta 50 85 V006 Ua,Va,Wa,Xa ua,va,wa,xa 40 90 V007 Ya,Za,Ab,Bb ya,za,ab,bb 45 100 V008 Cb,Db,Eb,Fb cb,db,eb,fb 35 95 V009 Gb,Hb,Ib,Jb gb,hb,ib,jb 30 60 V010 Kb,Lb,Mb,Nb kb,lb,mb,nb 30 55 T001 aa,ba Aa,Ba 5 35 T002 ca,da Ca,Da 15 45 T003 ea,fa Ea,Fa 25 55 T004 ga,ha Ga,Ha 35 65 T005 ia,ja Ia,Ja 30 80 T006 ka,la Ka,La 25 45 T007 ma,na Ma,Na 20 55 T008 oa,pa Oa,Pa 35 70 T009 qa,ra Qa,Ra 60 110 T010 sa,ta Sa,Ta 55 90 T011 ua,va Ua,Va 45 75 T012 wa,xa Wa,Xa 20 55 T013 ya,za Ya,Za 35 60 T014 ab,bb Ab,Bb 10 45 T015 cb,db Cb,Db 55 80 T016 eb,fb Eb,Fb 45 95 T017 gb,hb Gb,Hb 65 105 T018 ib,jb Ib,Jb 70 115 T019 kb,lb Kb,Lb 25 80 T020 mb,nb Mb,Nb 50 100 Tabla 39. Entrada de buques y trenes en los escenarios 13 a 16 Escenario 13 Identificador grúa Tipo de grúa Tiempo de descarga Tiempo de carga C001 Barco 5 5 C001 Tren 5 5 Tabla 40. Grúas disponibles en el escenario 13 89 89 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Escenario 14 Identificador grúa Tipo de grúa Tiempo de descarga Tiempo de carga C001 Barco 5 5 C002 Barco 5 5 C001 Tren 5 5 C002 Tren 5 5 Tabla 41. Grúas disponibles en el escenario 14 Escenario 15 Identificador grúa Tipo de grúa Tiempo de descarga Tiempo de carga C001 Barco 5 5 C002 Barco 5 5 C003 Barco 5 5 C001 Tren 5 5 C002 Tren 5 5 C003 Tren 5 5 Tabla 42. Grúas disponibles en el escenario 15 Escenario 16 Identificador grúa Tipo de grúa Tiempo de descarga Tiempo de carga C001 Barco 5 5 C002 Barco 5 5 C003 Barco 5 5 C004 Barco 5 5 C001 Tren 5 5 C002 Tren 5 5 C003 Tren 5 5 C004 Tren 5 5 Tabla 43. Grúas disponibles en el escenario 16 Anexo II. Resultados de la batería de problemas 96 96 Valor de la solución Tiempo de computación (s) 160 92,52 Tabla 64. Solución del problema 3 97 97 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Problema 4 BUQUES Identificador Inicio Ventana Temporal Fin Ventana Temporal Instante de llegada Instante de salida B001 10 40 10 35 B002 20 50 20 30 Tabla 65. Solución buques. Escenario 4 TRENES Identificador Inicio Ventana Temporal Fin Ventana Temporal Instante de llegada Instante de salida T001 5 35 5 30 T002 15 45 15 20 T003 25 55 25 35 Tabla 66. Solución trenes. Escenario 4 Grúa de buque 1 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tipo de operación -1 1 1 1 Contenedor Ab Ib Jb Kb Instante 10 20 25 30 Tabla 67. Configuración grúa de buque 1. Escenario 4 Grúa de buque 2 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tipo de operación -1 -1 1 1 Contenedor Bb Db Gb Lb Instante 10 20 25 30 Tabla 68. Configuración grúa de buque 2. Escenario 4 Anexo II. Resultados de la batería de problemas 98 98 Grúa de buque 3 Tarea 1 Tarea 2 Tarea 3 Tipo de operación -1 -1 1 Contenedor Cb Eb Hb Instante 10 20 25 Tabla 69. Configuración grúa de buque 3. Escenario 4 Grúa de buque 4 Tarea 1 Tipo de operación -1 Contenedor Fb Instante 20 Tabla 70. Configuración grúa de buque 4. Escenario 4 Grúa de tren 1 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tipo de operación -1 -1 -1 1 Contenedor Gb Jb Lb Db Instante 5 15 25 30 Tabla 71. Configuración grúa de tren 1. Escenario 4 Grúa de tren 2 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tipo de operación -1 -1 1 1 Contenedor Hb Ib Eb Cb Instante 5 15 25 30 Tabla 72. Configuración grúa de tren 2. Escenario 4 99 99 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Grúa de tren 3 Tarea 1 Tarea 2 Tipo de operación 1 -1 Contenedor Bb Kb Instante 15 25 Tabla 73. Configuración grúa de tren 3. Escenario 4 Grúa de tren 4 Tarea 1 Tarea 2 Tipo de operación 1 1 Contenedor Ab Fb Instante 15 25 Tabla 74. Configuración grúa de tren 4. Escenario 4 Valor de la solución Tiempo de computación (s) 150 124,79 Tabla 75. Solución del problema 4 Anexo II. Resultados de la batería de problemas 100 100 Problema 5 BUQUES Identificador Inicio Ventana Temporal Fin Ventana Temporal Instante de llegada Instante de salida B001 10 40 10 60 B002 20 50 20 90 Tabla 76. Solución buques. Escenario 5 TRENES Identificador Inicio Ventana Temporal Fin Ventana Temporal Instante de llegada Instante de salida T001 5 35 5 65 T002 15 45 15 35 T003 25 55 30 55 T004 30 65 60 85 Tabla 77. Solución trenes. Escenario 5 Grúa de buque 1 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tarea 8 Tipo de operación -1 -1 -1 -1 -1 1 1 1 Contenedor Ab Bb Cb Db Eb Ib Kb Lb Instante 10 15 20 25 30 35 40 45 Grúa de buque 1 Tarea 9 Tarea 10 Tarea 11 Tarea 12 Tarea 13 Tarea 14 Tarea 15 Tarea 16 Tipo de operación -1 1 -1 -1 1 1 1 1 Contenedor Fb Ob Gb Hb Jb Mb Nb Pb Instante 50 55 60 65 70 75 80 85 Tabla 78. Configuración grúa de buque 1. Escenario 5 Grúa de tren 1 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tarea 8 Tipo de operación -1 -1 -1 -1 1 1 -1 -1 101 101 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Contenedor Pb Ob Jb Ib Ab Bb Kb Lb Instante 5 10 15 20 25 30 35 40 Grúa de tren 1 Tarea 9 Tarea 10 Tarea 11 Tarea 12 Tarea 13 Tarea 14 Tarea 15 Tarea 16 Tipo de operación 1 1 1 1 -1 -1 1 1 Contenedor Cb Db Fb Eb Mb Nb Gb Hb Instante 45 50 55 60 65 70 75 80 Tabla 79. Configuración grúa de tren 1. Escenario 5 Valor de la solución Tiempo de computación (s) 390 39,50 Tabla 80. Solución del problema 5 Anexo II. Resultados de la batería de problemas 102 102 Problema 6 BUQUES Identificador Inicio Ventana Temporal Fin Ventana Temporal Instante de llegada Instante de salida B001 10 40 10 45 B002 20 50 20 50 Tabla 81. Solución buques. Escenario 6 TRENES Identificador Inicio Ventana Temporal Fin Ventana Temporal Instante de llegada Instante de salida T001 5 35 10 30 T002 15 45 15 25 T003 25 55 25 45 T004 30 65 35 50 Tabla 82. Solución trenes. Escenario 6 Grúa de buque 1 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tarea 8 Tarea 9 Tipo de operación -1 -1 -1 1 -1 1 1 1 1 Contenedor Ab Cb Eb Ib Hb Kb Ob Nb Pb Instante 10 15 20 25 30 35 40 45 50 Tabla 83. Configuración grúa de buque 1. Escenario 6 Grúa de buque 2 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tarea 8 Tipo de operación -1 -1 -1 -1 1 1 1 1 Contenedor Bb Db Fb Gb Jb Lb Mb Pb Instante 10 15 20 25 30 35 40 45 Tabla 84. Configuración grúa de buque 2. Escenario 6 103 103 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Grúa de tren 1 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tarea 8 Tipo de operación -1 -1 1 1 -1 -1 1 1 Contenedor Pb Ib Bb Fb Lb Mb Db Gb Instante 10 15 20 25 30 35 40 45 Tabla 85. Configuración grúa de tren 1. Escenario 6 Grúa de tren 2 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tarea 8 Tipo de operación -1 -1 1 1 -1 -1 1 1 Contenedor Ob Jb Ab Eb Kb Nb Cb Hb Instante 10 15 20 25 30 35 40 45 Tabla 86. Configuración grúa de tren 2. Escenario 6 Valor de la solución Tiempo de computación (s) 245 48,67 Tabla 87. Solución del problema 5 Anexo II. Resultados de la batería de problemas 104 104 Problema 7 BUQUES Identificador Inicio Ventana Temporal Fin Ventana Temporal Instante de llegada Instante de salida B001 10 40 10 35 B002 20 50 20 45 Tabla 88. Solución buques. Escenario 7 TRENES Identificador Inicio Ventana Temporal Fin Ventana Temporal Instante de llegada Instante de salida T001 5 35 10 35 T002 15 45 15 25 T003 25 55 25 35 T004 30 65 30 45 Tabla 89. Solución trenes. Escenario 7 Grúa de buque 1 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tipo de operación -1 -1 1 -1 1 1 Contenedor Ab Db Ib Gb Kb Mb Instante 10 15 20 25 30 40 Tabla 90. Configuración grúa de buque 1. Escenario 7 Grúa de buque 2 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tipo de operación -1 -1 -1 1 1 Contenedor Bb Eb Hb Lb Nb Instante 10 20 25 30 40 Tabla 91. Configuración grúa de buque 2. Escenario 7 105 105 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Grúa de buque 3 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tipo de operación -1 -1 1 1 1 Contenedor Cb Fb Jb Ob Pb Instante 10 20 25 30 40 Tabla 92. Configuración grúa de buque 3. Escenario 7 Grúa de tren 1 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tipo de operación -1 -1 1 -1 1 Contenedor Ob Ib Ab Kb Db Instante 5 15 20 25 30 Tabla 93. Configuración grúa de tren 1. Escenario 7 Grúa de tren 2 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tipo de operación -1 -1 -1 1 -1 Contenedor Pb Jb Lb Cb Nb Instante 5 15 25 30 35 Tabla 94. Configuración grúa de tren 2. Escenario 7 Grúa de tren 3 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tipo de operación 1 1 1 1 1 Contenedor Bb Eb Fb Gb Hb Instante 15 25 30 35 35 Tabla 95. Configuración grúa de tren 3. Escenario 7 Valor de la solución Tiempo de computación (s) Anexo II. Resultados de la batería de problemas 112 112 Tipo de operación -1 1 -1 -1 -1 1 -1 -1 -1 -1 Contenedor sb Cb gb hb rb Hb qb tb kb lb Instante 105 110 115 120 125 130 135 140 145 150 Grúa de tren 1 Tarea 31 Tarea 32 Tarea 33 Tarea 34 Tarea 35 Tarea 36 Tarea 37 Tarea 38 Tarea 39 Tarea 40 Tipo de operación 1 1 1 -1 1 1 1 1 1 1 Contenedor Lb Gb Kb pb Rb Qb Pb Tb Ob Sb Instante 155 160 165 170 175 180 185 190 195 200 Tabla 111. Configuración grúa de tren 1. Escenario 9 Valor de la solución Tiempo de computación (s) 2195 319,25 Tabla 112. Solución del problema 9 113 113 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Problema 10 BUQUES Identificador Inicio Ventana Temporal Fin Ventana Temporal Instante de llegada Instante de salida B001 10 40 10 40 B002 20 50 50 90 B003 15 35 25 55 B004 30 70 35 90 B005 50 90 90 110 Tabla 113. Solución buques. Escenario 10 TRENES Identificador Inicio Ventana Temporal Fin Ventana Temporal Instante de llegada Instante de salida T001 5 35 5 25 T002 15 45 25 40 T003 25 55 50 70 T004 30 65 50 95 T005 10 35 10 40 T006 15 60 30 50 T007 5 20 10 60 T008 15 45 45 85 T009 25 55 50 100 T0010 30 65 65 105 Tabla 114. Solución trenes. Escenario 10 Grúa de buque 1 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tarea 8 Tarea 9 Tarea 10 Tipo de operación -1 -1 1 -1 1 -1 1 -1 1 -1 Contenedor Ab Cb ab Ib cb Lb ib Nb kb Eb Instante 10 15 20 25 30 35 40 45 50 55 Anexo II. Resultados de la batería de problemas 114 114 Grúa de buque 1 Tarea 11 Tarea 12 Tarea 13 Tarea 14 Tarea 15 Tarea 16 Tarea 17 Tarea 18 Tarea 19 Tarea 20 Tipo de operación -1 1 1 1 1 1 -1 -1 1 1 Contenedor Gb eb fb mb gb hb Qb Sb qb sb Instante 60 65 70 75 80 85 90 95 100 105 Tabla 115. Configuración grúa de buque 1. Escenario 10 Grúa de buque 2 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tarea 8 Tarea 9 Tarea 10 Tipo de operación -1 -1 1 -1 -1 1 -1 1 1 -1 Contenedor Bb Db bb Jb Kb db Mb jb lb Fb Instante 10 15 20 25 30 35 40 45 50 55 Grúa de tren 2 Tarea 11 Tarea 12 Tarea 13 Tarea 14 Tarea 15 Tarea 16 Tarea 17 Tarea 18 Tarea 19 Tarea 20 Tipo de operación -1 -1 -1 1 1 1 -1 -1 1 1 Contenedor Hb Ob Pb nb ob pb Rb Tb rb tb Instante 60 65 70 75 80 85 90 95 100 105 Tabla 116. Configuración grúa de buque 2. Escenario 10 Grúa de tren 1 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tarea 8 Tarea 9 Tarea 10 Tipo de operación -1 -1 1 -1 -1 1 1 -1 1 1 Contenedor bb nb Bb ib db Ib Cb kb Lb Nb Instante 5 10 15 20 25 30 35 40 45 50 Grúa de tren 1 Tarea 11 Tarea 12 Tarea 13 Tarea 14 Tarea 15 Tarea 16 Tarea 17 Tarea 18 Tarea 19 Tarea 20 Tipo de operación 1 -1 1 -1 -1 1 -1 1 1 1 Contenedor Mb fb Eb hb tb Pb qb Gb Qb Tb 115 115 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Instante 55 60 65 70 75 80 85 90 95 100 Tabla 117. Configuración grúa de tren 1. Escenario 10 Grúa de tren 2 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tarea 8 Tarea 9 Tarea 10 Tipo de operación -1 -1 -1 1 -1 1 1 -1 1 -1 Contenedor ab mb jb Ab cb Db Jb lb Kb ob Instante 5 10 15 20 25 30 35 40 45 50 Grúa de tren 2 Tarea 11 Tarea 12 Tarea 13 Tarea 14 Tarea 15 Tarea 16 Tarea 17 Tarea 18 Tarea 19 Tarea 20 Tipo de operación -1 -1 1 -1 -1 1 -1 1 1 1 Contenedor gb eb Fb sb pb Ob rb Hb Rb Sb Instante 55 60 65 70 75 80 85 90 95 100 Tabla 118. Configuración gría de tren 2. Escenario 10 Valor de la solución Tiempo de computación (s) 1055 274,53 Tabla 119. Solución del problema 10 Anexo II. Resultados de la batería de problemas 116 116 Problema 11 BUQUES Identificador Inicio Ventana Temporal Fin Ventana Temporal Instante de llegada Instante de salida B001 10 40 10 30 B002 20 50 30 55 B003 15 35 15 40 B004 30 70 45 70 B005 50 90 55 80 Tabla 120. Solución buques. Escenario 11 TRENES Identificador Inicio Ventana Temporal Fin Ventana Temporal Instante de llegada Instante de salida T001 5 35 5 20 T002 15 45 20 30 T003 25 55 30 45 T004 30 65 40 55 T005 10 35 10 35 T006 15 60 15 35 T007 5 20 5 55 T008 15 45 40 65 T009 25 55 55 70 T0010 30 65 65 80 Tabla 121. Solución trenes. Escenario 11 Grúa de buque 1 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tarea 8 Tarea 9 Tarea 10 Tipo de operación -1 -1 -1 1 1 1 -1 -1 1 -1 Contenedor Ab Db Ib cb ib kb Gb Mb gb Pb 117 117 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Instante 10 15 20 25 30 35 40 45 50 55 Grúa de buque 1 Tarea 11 Tarea 12 Tarea 13 Tarea 14 Tarea 15 Tarea 16 Tarea 17 Tarea 18 Tarea 19 Tarea 20 Tipo de operación -1 -1 1 1 1 -1 1 1 1 1 Contenedor Rb Tb qb sb gb Sb mb ob qb sb Instante 60 65 70 75 80 85 90 95 100 105 Tabla 122. Configuración grúa de buque 1. Escenario 11 Grúa de buque 2 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tarea 8 Tarea 9 Tarea 10 Tipo de operación -1 1 -1 1 -1 -1 -1 1 1 1 Contenedor Bb ab Jb db Eb Fb Hb fb hb mb Instante 10 15 20 25 30 35 40 45 50 55 Grúa de buque 2 Tarea 11 Tarea 12 Tarea 13 Tarea 14 Tarea 15 Tarea 16 Tarea 17 Tarea 18 Tarea 19 Tarea 20 Tipo de operación -1 1 1 1 1 -1 1 1 1 1 Contenedor Sb ob rb tb hb Tb nb pb rb tb Instante 60 65 70 75 80 85 90 95 100 105 Tabla 123. Configuración grúa de buque 2. Escenario 11 Grúa de buque 3 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tipo de operación -1 1 -1 -1 1 1 1 Contenedor Cb bb Kb Lb jb lb eb Instante 10 15 20 25 30 35 40 Grúa de buque 3 Tarea 8 Tarea 9 Tarea 10 Tarea 11 Tarea 12 Tarea 13 Tarea 14 Tipo de operación -1 -1 -1 1 1 1 1 Contenedor Nb Ob Qb nb pb Rb Tb Anexo II. Resultados de la batería de problemas 118 118 Instante 45 50 55 60 65 80 90 Tabla 124. Configuración grúa de buque 3. Escenario 11 Grúa de tren 1 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tipo de operación -1 -1 -1 -1 1 1 -1 Contenedor ab jb kb lb Db Ib fb Instante 5 10 15 20 25 30 35 Grúa de tren 1 Tarea 8 Tarea 9 Tarea 10 Tarea 11 Tarea 12 Tarea 13 Tarea 14 Tipo de operación -1 -1 1 1 -1 -1 1 Contenedor pb gb Mb Pb qb sb Sb Instante 40 45 50 60 65 70 75 Tabla 125. Configuración grúa de tren 1. Escenario 11 Grúa de tren 2 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tipo de operación -1 -1 1 -1 1 1 -1 Contenedor bb ib Bb cb Cb Lb eb Instante 5 10 15 20 25 30 35 Grúa de tren 2 Tarea 8 Tarea 9 Tarea 10 Tarea 11 Tarea 12 Tarea 13 Tarea 14 Tipo de operación -1 -1 1 1 1 -1 Contenedor ob hb Hb Ob Qb tb Instante 40 45 50 60 65 70 Tabla 126. Configuración grúa de tren 2. Escenario 11 Grúa de tren 3 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 119 119 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Tipo de operación -1 -1 1 -1 1 1 1 Contenedor mb nb Ab db Jb Kb Eb Instante 5 10 15 20 25 30 35 Grúa de tren 3 Tarea 8 Tarea 9 Tarea 10 Tarea 11 Tarea 12 Tarea 13 Tarea 14 Tipo de operación 1 1 1 -1 1 1 1 Contenedor Fb Gb Nb rb Rb Tb Fb Instante 40 45 50 60 65 70 40 Tabla 127. Configuración grúa de tren 3. Escenario 11 Valor de la solución Tiempo de computación (s) 220 289,21 Tabla 128. Solución del problema 11 Anexo II. Resultados de la batería de problemas 120 120 Problema 12 BUQUES Identificador Inicio Ventana Temporal Fin Ventana Temporal Instante de llegada Instante de salida B001 10 40 10 25 B002 20 50 25 45 B003 15 35 15 35 B004 30 70 35 55 B005 50 90 50 65 Tabla 129. Solución buques. Escenario 12 TRENES Identificador Inicio Ventana Temporal Fin Ventana Temporal Instante de llegada Instante de salida T001 5 35 5 20 T002 15 45 15 25 T003 25 55 25 35 T004 30 65 35 40 T005 10 35 10 25 T006 15 60 25 30 T007 5 20 10 45 T008 15 45 40 50 T009 25 55 50 60 T0010 30 65 45 65 Tabla 130. Solución trenes. Escenario 12 Grúa de buque 1 Tare a 1 Tare a 2 Tare a 3 Tare a 4 Tare a 5 Tare a 6 Tare a 7 Tare a 8 Tare a 9 Tare a 10 Tare a 11 Tipo de operación -1 1 1 1 1 1 1 1 -1 -1 1 Contenedor Ab ab cb ib kb eb gb mb Qb Sb qb 121 121 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Instante 10 15 20 25 30 35 40 45 50 55 60 Tabla 131. Configuración grúa de buque 1. Escenario 12 Grúa de buque 2 Tare a 1 Tare a 2 Tare a 3 Tare a 4 Tare a 5 Tare a 6 Tare a 7 Tare a 8 Tare a 9 Tare a 10 Tare a 11 Tipo de operación -1 1 1 -1 -1 1 -1 1 1 -1 1 Contenedor Bb bb db Eb Gb fb Ob nb ob Tb rb Instante 10 15 20 25 30 35 40 45 50 55 60 Tabla 132. Configuración grúa de buque 2. Escenario 12 Grúa de buque 3 Tare a 1 Tare a 2 Tare a 3 Tare a 4 Tare a 5 Tare a 6 Tare a 7 Tare a 8 Tare a 9 Tare a 10 Tare a 11 Tipo de operación -1 -1 -1 -1 1 -1 1 1 1 -1 -1 Contenedor Cb Ib Kb Fb lb Mb hb pb sb Cb Ib Instante 10 15 20 25 30 35 40 50 60 10 15 Tabla 133. Configuración grúa de buque 3. Escenario 12 Grúa de buque 4 Tare a 1 Tare a 2 Tare a 3 Tare a 4 Tare a 5 Tare a 6 Tare a 7 Tare a 8 Tare a 9 Tare a 10 Tare a 11 Tipo de operación -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 Contenedor Db Jb Lb jb Hb Nb Pb Rb tb Db Jb Instante 10 15 20 25 30 35 40 50 60 10 15 Tabla 134. Configuración grúa de buque 4. Escenario 12 Grúa de tren 1 Tare a 1 Tare a 2 Tare a 3 Tare a 4 Tare a 5 Tare a 6 Tare a 7 Tare a 8 Tare a 9 Tare a 10 Tare a 11 Tipo de operación -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 Contenedor ab nb Ab Jb kb fb hb Mb pb tb rb Instante 5 10 15 20 25 30 35 40 45 50 55 Anexo II. Resultados de la batería de problemas 128 128 Problema 14 BUQUES Identificador Inicio Ventana Temporal Fin Ventana Temporal Instante de llegada Instante de salida B001 10 40 10 50 B002 20 75 25 110 B003 25 45 35 210 B004 20 50 20 165 B005 50 85 70 175 B006 40 90 55 195 B007 45 100 70 135 B008 35 95 95 195 B009 30 60 40 200 B0010 30 55 50 155 Tabla 145. Solución buques. Escenario 14 TRENES Identificador Inicio Ventana Temporal Fin Ventana Temporal Instante de llegada Instante de salida T001 5 35 5 30 T002 15 45 20 55 T003 25 55 50 105 T004 35 65 35 60 T005 30 80 65 210 T006 25 45 25 160 T007 20 55 55 100 T008 35 70 40 120 T009 60 110 75 140 T0010 55 90 60 150 T0011 45 75 70 190 T0012 20 55 25 105 T0013 35 60 35 115 129 129 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal T0014 10 45 15 135 T0015 55 80 70 180 T0016 45 95 85 195 T0017 65 105 80 210 T0018 70 115 105 190 T0019 25 80 75 155 T0020 50 100 70 205 Tabla 146. Solución trenes. Escenario 14 Grúa de buque 1 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tarea 8 Tarea 9 Tarea 10 Tipo de operación -1 -1 -1 1 -1 -1 -1 1 -1 -1 Contenedor Aa Ca Ma ba Fa Ha Na da Oa Ua Instante 10 15 20 25 30 35 40 45 50 55 Grúa de buque 1 Tarea 11 Tarea 12 Tarea 13 Tarea 14 Tarea 15 Tarea 16 Tarea 17 Tarea 18 Tarea 19 Tarea 20 Tipo de operación -1 1 -1 -1 1 -1 -1 -1 -1 1 Contenedor Va ea Ya Ja fa Mb Pa Qa Cb ha Instante 60 65 70 75 80 85 90 95 100 105 Grúa de buque 1 Tarea 21 Tarea 22 Tarea 23 Tarea 24 Tarea 25 Tarea 26 Tarea 27 Tarea 28 Tarea 29 Tarea 30 Tipo de operación -1 -1 1 1 -1 -1 -1 1 1 -1 Contenedor Db Bb ya ab La Sa Ta lb nb Eb Instante 110 115 120 125 130 135 140 145 150 155 Grúa de buque 1 Tarea 31 Tarea 32 Tarea 33 Tarea 34 Tarea 35 Tarea 36 Tarea 37 Tarea 38 Tarea 39 Tarea 40 Tipo de operación 1 1 1 1 1 1 1 1 1 1 Contenedor pa cb ta ua eb gb fb ib ia ka Instante 160 165 170 175 180 185 190 195 200 205 Tabla 147. Configuración grúa de buque 1. Escenario 14 Anexo II. Resultados de la batería de problemas 130 130 Grúa de buque 2 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tarea 8 Tarea 9 Tarea 10 Tipo de operación -1 -1 1 -1 -1 1 -1 -1 -1 -1 Contenedor Ba Da aa Ea Ga ca Gb Hb Ib Jb Instante 10 15 20 25 30 35 40 45 50 55 Grúa de buque 2 Tarea 11 Tarea 12 Tarea 13 Tarea 14 Tarea 15 Tarea 16 Tarea 17 Tarea 18 Tarea 19 Tarea 20 Tipo de operación -1 -1 -1 -1 -1 1 -1 -1 -1 1 Contenedor Wa Kb Ia Lb Xa ga Za Ab Nb ma Instante 60 65 70 75 80 85 90 95 100 105 Grúa de buque 2 Tarea 21 Tarea 22 Tarea 23 Tarea 24 Tarea 25 Tarea 26 Tarea 27 Tarea 28 Tarea 29 Tarea 30 Tipo de operación -1 -1 1 1 1 1 1 1 1 1 Contenedor Ra Ka za na bb kb qa mb oa ra Instante 110 115 120 125 130 135 140 145 150 155 Grúa de buque 2 Tarea 31 Tarea 32 Tarea 33 Tarea 34 Tarea 35 Tarea 36 Tarea 37 Tarea 38 Tarea 39 Tarea 40 Tipo de operación -1 1 1 1 1 1 1 1 1 1 Contenedor Fb sa db va wa hb xa jb ja la Instante 160 165 170 175 180 185 190 195 200 205 Tabla 148. Configuración grúa de buque 2. Escenario 14 Grúa de tren 1 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tarea 8 Tarea 9 Tarea 10 Tipo de operación -1 -1 -1 -1 -1 -1 1 -1 -1 1 Contenedor aa ab bb ka ca za Ca ga fa Ga Instante 5 15 20 25 30 35 40 45 50 55 131 131 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Grúa de tren 1 Tarea 11 Tarea 12 Tarea 13 Tarea 14 Tarea 15 Tarea 16 Tarea 17 Tarea 18 Tarea 19 Tarea 20 Tipo de operación -1 -1 -1 -1 1 -1 1 -1 1 -1 Contenedor pa oa na ra Ma ta Ya mb Wa ib Instante 60 65 70 75 80 85 90 95 100 105 Grúa de tren 1 Tarea 21 Tarea 22 Tarea 23 Tarea 24 Tarea 25 Tarea 26 Tarea 27 Tarea 28 Tarea 29 Tarea 30 Tipo de operación -1 1 1 -1 1 1 -1 -1 1 -1 Contenedor sa Oa Ka jb Qa Ra fb nb Lb db Instante 110 115 120 125 130 135 140 145 150 155 Grúa de tren 1 Tarea 31 Tarea 32 Tarea 33 Tarea 34 Tarea 35 Tarea 36 Tarea 37 Tarea 38 Tarea 39 Tarea 40 Tipo de operación 1 -1 -1 -1 -1 1 1 -1 1 1 Contenedor Jb va ua gb hb Ua Nb ia Mb Hb Instante 160 165 170 175 180 185 190 195 200 205 Tabla 149. Configuración grúa de tren 1. Escenario 14 Grúa de tren 2 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tarea 8 Tarea 9 Tarea 10 Tipo de operación -1 1 -1 1 -1 -1 -1 1 1 -1 Contenedor ba Ba da Aa wa ya ha Ha Da ea Instante 5 15 20 25 30 35 40 45 50 55 Grúa de tren 2 Tarea 11 Tarea 12 Tarea 13 Tarea 14 Tarea 15 Tarea 16 Tarea 17 Tarea 18 Tarea 19 Tarea 20 Tipo de operación -1 -1 1 -1 -1 1 -1 1 1 1 Contenedor xa ma Ea la qa Xa lb Na Fa Pa Instante 60 65 70 75 80 85 90 95 100 105 Grúa de tren 2 Tarea 21 Tarea 22 Tarea 23 Tarea 24 Tarea 25 Tarea 26 Tarea 27 Tarea 28 Tarea 29 Tarea 30 Anexo II. Resultados de la batería de problemas 132 132 Tipo de operación 1 -1 -1 1 1 -1 1 1 1 1 Contenedor Za ja kb Bb Ab cb Sa Ta Kb La Instante 110 115 120 125 130 135 140 145 150 155 Grúa de tren 2 Tarea 31 Tarea 32 Tarea 33 Tarea 34 Tarea 35 Tarea 36 Tarea 37 Tarea 38 Tarea 39 Tarea 40 Tipo de operación 1 -1 1 1 1 1 1 1 1 1 Contenedor Db eb Va Cb Fb Ib Eb Gb Ja Ia Instante 160 165 170 175 180 185 190 195 200 205 Tabla 150. Configuración grúa de tren 2. Escenario 14 Valor de la solución Tiempo de computación (s) 4400 1466,61 133 133 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Problema 15 BUQUES Identificador Inicio Ventana Temporal Fin Ventana Temporal Instante de llegada Instante de salida B001 10 40 10 30 B002 20 75 20 65 B003 25 45 35 65 B004 20 50 30 110 B005 50 85 55 140 B006 40 90 55 100 B007 45 100 85 125 B008 35 95 50 130 B009 30 60 60 145 B0010 30 55 55 120 Tabla 151. Solución buques. Escenario 15 TRENES Identificador Inicio Ventana Temporal Fin Ventana Temporal Instante de llegada Instante de salida T001 5 35 5 25 T002 15 45 15 25 T003 25 55 25 35 T004 35 65 45 60 T005 30 80 35 55 T006 25 45 35 75 T007 20 55 25 40 T008 35 70 60 75 T009 60 110 95 140 T0010 55 90 75 125 T0011 45 75 55 90 T0012 20 55 55 95 T0013 35 60 45 105 Anexo II. Resultados de la batería de problemas 134 134 T0014 10 45 10 125 T0015 55 80 75 95 T0016 45 95 75 115 T0017 65 105 100 145 T0018 70 115 110 140 T0019 25 80 80 100 T0020 50 100 90 115 Tabla 152. Solución trenes. Escenario 15 Grúa de buque 1 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tarea 8 Tarea 9 Tarea 10 Tipo de operación -1 -1 1 -1 -1 -1 -1 1 1 -1 Contenedor Aa Da ca Ga Ma Pa Ja fa ia Ua Instante 10 15 20 25 30 35 40 45 50 55 Grúa de buque 1 Tarea 11 Tarea 12 Tarea 13 Tarea 14 Tarea 15 Tarea 16 Tarea 17 Tarea 18 Tarea 19 Tarea 20 Tipo de operación 1 -1 -1 -1 -1 1 1 1 -1 -1 Contenedor la Va Wa Sa Ta va kb xa Ab Bb Instante 60 65 70 75 80 85 90 95 100 105 Grúa de buque 1 Tarea 21 Tarea 22 Tarea 23 Tarea 24 Tarea 25 Tarea 26 Tarea 27 Tarea 28 Tarea 29 Tarea 30 Tipo de operación 1 1 1 -1 1 1 1 Contenedor mb nb db Jb qa ta ib Instante 110 115 120 125 130 135 140 Tabla 153. Configuración grúa de buque 1. Escenario 15 Grúa de buque 2 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tarea 8 Tarea 9 Tarea 10 Tipo de operación -1 1 -1 -1 -1 -1 1 -1 1 1 Contenedor Ba aa Ea Ha Na Ia ea Ka ga ja 135 135 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Instante 10 15 20 25 30 35 40 45 50 55 Grúa de buque 2 Tarea 11 Tarea 12 Tarea 13 Tarea 14 Tarea 15 Tarea 16 Tarea 17 Tarea 18 Tarea 19 Tarea 20 Tipo de operación 1 -1 -1 -1 -1 1 -1 -1 -1 1 Contenedor ha Lb Xa Mb Gb wa Eb Za Fb cb Instante 60 65 70 75 80 85 90 95 100 105 Grúa de buque 2 Tarea 21 Tarea 22 Tarea 23 Tarea 24 Tarea 25 Tarea 26 Tarea 27 Tarea 28 Tarea 29 Tarea 30 Tipo de operación 1 1 1 1 1 1 1 Contenedor ya za bb eb ra gb jb Instante 110 115 120 125 130 135 140 Tabla 154. Configuración grúa de buque 2. Escenario 15 Grúa de buque 3 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tarea 8 Tarea 9 Tarea 10 Tipo de operación -1 1 -1 1 -1 1 1 -1 -1 1 Contenedor Ca ba Fa da Oa ma na La Cb ka Instante 10 15 20 25 30 35 40 45 50 55 Grúa de buque 3 Tarea 11 Tarea 12 Tarea 13 Tarea 14 Tarea 15 Tarea 16 Tarea 17 Tarea 18 Tarea 19 Tarea 20 Tipo de operación -1 -1 -1 1 -1 -1 -1 1 1 1 Contenedor Kb Qa Ra ua Nb Db Ya lb oa pa Instante 60 65 70 75 80 85 90 95 100 105 Grúa de buque 3 Tarea 21 Tarea 22 Tarea 23 Tarea 24 Tarea 25 Tarea 26 Tarea 27 Tarea 28 Tarea 29 Tarea 30 Tipo de operación -1 1 -1 1 1 1 Contenedor Hb ab Ib fb sa hb Instante 110 115 120 125 130 135 Tabla 155. Configuración grúa de buque 3. Escenario 15 Anexo II. Resultados de la batería de problemas 136 136 Grúa de tren 1 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tarea 8 Tarea 9 Tarea 10 Tipo de operación -1 -1 1 1 -1 -1 1 -1 -1 1 Contenedor aa bb Aa Ca fa ea Ma la ga Ja Instante 5 10 15 20 25 30 35 40 45 50 Grúa de tren 1 Tarea 11 Tarea 12 Tarea 13 Tarea 14 Tarea 15 Tarea 16 Tarea 17 Tarea 18 Tarea 19 Tarea 20 Tipo de operación -1 -1 -1 1 -1 -1 -1 1 1 -1 Contenedor wa ua va Pa cb kb eb Xa Kb mb Instante 55 60 65 70 75 80 85 90 95 100 Grúa de tren 1 Tarea 21 Tarea 22 Tarea 23 Tarea 24 Tarea 25 Tarea 26 Tarea 27 Tarea 28 Tarea 29 Tarea 30 Tipo de operación 1 1 -1 1 -1 1 1 1 Contenedor Eb Mb jb Sa ra Ib Ra Hb Instante 105 110 115 120 125 130 135 140 Tabla 156. Configuración grúa de tren 1. Escenario 15 Grúa de tren 2 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tarea 8 Tarea 9 Tarea 10 Tipo de operación -1 -1 -1 1 -1 1 1 -1 1 -1 Contenedor ba ab da Da ma Ea Na ja Ia ya Instante 5 10 15 20 25 30 35 40 45 50 Grúa de tren 2 Tarea 11 Tarea 12 Tarea 13 Tarea 14 Tarea 15 Tarea 16 Tarea 17 Tarea 18 Tarea 19 Tarea 20 Tipo de operación 1 -1 -1 1 -1 -1 1 1 1 1 Contenedor Ga xa oa Oa db lb Va Lb Ya Za Instante 55 60 65 70 75 80 85 90 95 100 Grúa de tren 2 Tarea 21 Tarea 22 Tarea 23 Tarea 24 Tarea 25 Tarea 26 Tarea 27 Tarea 28 Tarea 29 Tarea 30 137 137 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Tipo de operación -1 1 -1 1 1 -1 1 Contenedor nb Fb qa Bb Qa gb Jb Instante 105 110 115 120 125 130 135 Tabla 157. Configuración grúa de tren 2. Escenario 15 Grúa de tren 3 Tarea 1 Tarea 2 Tarea 3 Tarea 4 Tarea 5 Tarea 6 Tarea 7 Tarea 8 Tarea 9 Tarea 10 Tipo de operación -1 1 -1 1 -1 -1 -1 -1 1 1 Contenedor ca Ba na Fa ka ia za ha Ha La Instante 15 20 25 30 35 40 45 50 55 60 Grúa de tren 3 Tarea 11 Tarea 12 Tarea 13 Tarea 14 Tarea 15 Tarea 16 Tarea 17 Tarea 18 Tarea 19 Tarea 20 Tipo de operación -1 1 1 1 1 1 -1 -1 -1 1 Contenedor pa Ka Cb Ua Wa Db fb ta sa Nb Instante 65 70 75 80 85 90 95 100 105 110 Grúa de tren 3 Tarea 21 Tarea 22 Tarea 23 Tarea 24 Tarea 25 Tarea 26 Tarea 27 Tarea 28 Tarea 29 Tarea 30 Tipo de operación 1 1 -1 -1 1 Contenedor Ab Ta ib hb Gb Instante 115 120 125 130 135 Tabla 158. Configuración grúa de tren 3. Escenario 15 Valor de la solución Tiempo de computación (s) 2810 1273,90 Tabla 159. Solución del problema 15 Anexo III. Parametrización 144 144 Escenario 16 2225 6628,78 2185 1337,16 2410 744,09 Tabla 171. Resultados para la parametrización β En vistas de los resultados obtenidos en las pruebas, se aprecia que el algoritmo suele encontrar mejores soluciones cuando la velocidad de enfriamiento es menor. Por contra, esto requiere un mayor coste computacional. Sin embargo, el algoritmo con un valor de β = 0.05 ha encontrado soluciones tan buenas o mejores que con β = 0.01 en 9 casos de 16, empleando menos tiempo de ejecución. Se ha decidido por tanto tomar un valor de β que dependa del tamaño del problema. En problemas pequeños, el tiempo computacional es corto y la diferencia en tiempo computacional entre las diferentes velocidades de enfriamiento no es determinante. Por contra, imponer una velocidad de enfriamiento lenta en problemas de gran tamaño implica un alto coste de ejecución, lo cual no resulta interesante desde el punto de vista de la investigación en el que se enmarca el presente trabajo. Los valores del parámetro β serán por tanto los reflejados en la Tabla 172. β Escenario 0.01 Escenario 1 a 4 0.02 Escenario 5 a 8 0.03 Escenario 9 a 12 0.04 Escenario 13 a 16 Tabla 172. Parametrización β Temperatura inicial y temperatura final Cuando la temperatura es alta, decrece a gran velocidad debido al carácter exponencial de la función de enfriamiento. Esto hace que aumentar la temperatura inicial solo suponga el incremento de unas pocas iteraciones más, las cuales no son representativas en el comportamiento del algoritmo. Por otra parte, a temperaturas muy bajas la probabilidad de adoptar una solución peor es casi nula, por lo que una variación de temperatura minima el único impacto que tiene es el de realizar una búsqueda más intensas cuando la probabilidad de aceptar peores es casi nula. Este concepto ya puede ser regulado con el parámetro L, por lo que se ha tomado un valor de tmin estimado conforme a la literatura. t0 50 tmin 0.3 Tabla 173. Parametrización t0 y tmin 145 145 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal Longitud de la cadena El parámetro L permite hacer un número determinado de iteraciones en cada valor de la temperatura (t). Esta idea permite hacer búsquedas más exhaustivas cuando el valor de t es bajo y por tanto la probabilidad de aceptar una solución peor es menor. Se ha decidido que L tome por tanto valores diferentes en función de la temperatura. Las posibles configuraciones de L y los resultados del algoritmo ante las mismas se reflejan en la Tabla 174: 𝐋={𝟏 𝒔𝒊 𝟏𝟎<𝒕<𝟓𝟎 𝟐 𝒔𝒊 𝟐<𝒕<𝟏𝟎 𝟑 𝒔𝒊 𝟎,𝟑<𝒕<𝟐 𝐋={𝟓 𝒔𝒊 𝟏𝟎<𝒕<𝟓𝟎 𝟏𝟎 𝒔𝒊 𝟐<𝒕<𝟏𝟎 𝟐𝟎 𝒔𝒊 𝟎,𝟑<𝒕<𝟐 𝐋={𝟐 𝒔𝒊 𝟏𝟎<𝒕<𝟓𝟎 𝟒 𝒔𝒊 𝟐<𝒕<𝟏𝟎 𝟔 𝒔𝒊 𝟎,𝟑<𝒕<𝟐 Solución Tiempo de ejecución Solución Tiempo de ejecución Solución Tiempo de ejecución Escen. 1 290 10,41 275 51,39 275 20,26 Escen. 2 180 13,42 180 67,71 180 25,80 Escen. 3 160 18,96 160 92,45 160 37,06 Escen. 4 150 24,59 150 126,27 150 48,99 Escen. 5 410 13,23 390 68,81 390 25,69 Escen. 6 245 16,16 245 83,96 245 33,32 Escen. 7 220 23,60 220 120,55 220 46,22 Escen. 8 205 29,30 200 156,13 200 57,51 Escen. 9 2340 64,35 2170 326,84 2235 127,76 Escen. 10 1115 54,11 1055 262,16 1085 109,88 Escen. 11 850 58,40 785 306,89 770 115,80 Escen. 12 670 74,03 620 378,85 645 140,78 Escen. 13 8960 354,47 8810 1922,74 8885 688,00 Escen. 14 4325 286,56 4400 1582,78 4405 560,96 Escen. 15 2870 256,76 2810 1308,89 3105 523,93 Escen. 16 2320 259,14 2230 1235,39 2245 462,78 Tabla 174. Resultados para la parametrización L Se aprecia que cuanto mayor sea L mejores soluciones se alcanzan en escenarios grandes. Sin embargo, debido al alto coste computacional requerido para resolver problemas grandes con demasiadas iteraciones, y a la vista de que los resultados ofrecidos con una L menor no distan mucho de las encuentran con valores altos de L, se eligen los valores de L recogidos en la Tabla 175. L t 2 10<t<50 4 2<t<10 6 0.3<t<2 Tabla 175. Parametrización L Anexo III. Parametrización 146 146 Tamaño del vecindario El número de vecinos que se calculan en cada iteración (Tvec) no es un parámetro propio del SA, pero tiene mucha influencia en la calidad de las soluciones y en el coste computacional del algoritmo. Tvec = 1 Tvec = 10 Tvec = 30 Solución Tiempo de ejecución Solución Tiempo de ejecución Solución Tiempo de ejecución Escenario 1 345 2,76 265 20,18 265 61,32 Escenario 2 290 3,82 180 26,93 180 79,60 Escenario 3 260 5,34 160 37,29 160 111,83 Escenario 4 245 7,31 150 49,31 150 147,91 Escenario 5 475 3,84 390 26,60 400 78,24 Escenario 6 340 4,67 245 33,08 245 98,23 Escenario 7 345 7,74 220 46,15 220 138,69 Escenario 8 330 6,97 200 56,72 200 179,92 Escenario 9 2450 17,71 2150 119,16 2175 356,43 Escenario 10 1360 15,89 1100 105,98 1070 285,80 Escenario 11 1080 16,56 845 123,81 755 335,72 Escenario 12 880 23,92 660 136,78 615 427,96 Escenario 13 9530 96,79 9010 690,50 8635 1986,40 Escenario 14 5240 84,94 4405 560,96 4435 1702,01 Escenario 15 3365 73,95 3105 523,93 3020 1476,04 Escenario 16 2895 84,41 2245 462,78 2205 1340,58 Tabla 176. Resultados para la paremetrización de Tvec A la vista de los resultados queda latente la necesidad de crear un vecindario de varios vecinos, ya que los resultados obtenidas cuando se crea un único vecino no son buenos. Por contra, un vecindario demasiado grande no consigue mejorar los resultados en problemas de tamaño reducido por lo que se decide que el tamaño de la vecindad sea tan grande como número de trenes y buques compongan el problema. Así, el valor del parámetro Tvec en cada escenario se resume en la Tabla 177. Tvec Escenario 5 Escenario 1 a 4 6 Escenario 5 a 8 15 Escenario 9 a 12 30 Escenario 13 a 16 Tabla 177. Parametrización Tvec 147 147 Algoritmo de recocido simulado para la mejora de la eficiencia de una terminal intermodal