Introducción

En este artículo estudiamos el problema de la plantilla de atraque estratégico (SBTP⁴). El SBTP combina decisiones estratégicas y operativas para la planificación de atraques a medio plazo de un conjunto determinado de buques que hacen escala cíclica. Mientras que las decisiones estratégicas dictan que buques serán atendidos y aquellos cuyas escalas será rechazadas, las decisiones operativas determinan la plantilla de atraque que se aplicará de forma cíclica en el horizonte de planificación considerado. Además, pueden existir vínculos que relacionen las decisiones estratégicas de servicio a buques pertenecientes a determinados grupos. Estos vínculos se derivan de fuertes relaciones de transbordo entre algunos buques nodriza de gran tamaño y algunos buques alimentadores más pequeños, que están vinculados contractualmente entre sí. Todos los barcos dentro de cada grupo deben ser tratados de manera similar, en el sentido de que todos ellos son atendidos o rechazados.

En particular, el SBTP tiene como objetivo decidir qué barcos que hacen escala deben ser aceptados para atracar y determina la asignación de tiempo y atraque más adecuada para el tráfico entrante aceptado. En concreto, su objetivo es desarrollar una plantilla para los buques aceptados para un horizonte temporal cíclico, consistente en una asignación de atraques junto con una ventana horaria de servicio (atraque) para cada uno de los buques aceptados. Se deben tener en cuenta las siguientes cuestiones: () hay un número limitado de atraques disponibles; () debido a la naturaleza cíclica de la plantilla, los períodos de servicio de los buques asignados al mismo atraque no deben superponerse; y () el servicio a un barco puede comenzar en el ciclo siguiente al que llega al puerto, o, incluso si el servicio comienza en el mismo ciclo cuando llega el barco, su servicio puede terminar en el siguiente ciclo. El objetivo es minimizar la suma de los tiempos de espera de los barcos aceptados más una penalización por cada escala rechazada proporcional a su carga de trabajo.

En términos generales, los problemas de asignación de atraques (BAP)⁵ tienen como objetivo asignar posiciones de atraque y tiempos de servicio a los buques que hacen escala en una terminal de contenedores. En la literatura se han estudiado diferentes variantes de tales problemas. El lector puede dirigirse a Bierwirth and Meisel (2010,2015) para obtener información sobre el tema, o a la introducción y revisión de la literatura de Iris et al. (2018) donde se destacan la relevancia y las implicaciones económicas reales de estos problemas, y se motivan y revisan las diferentes perspectivas y variantes que BAP puede integrar.

La mayoría de los BAP estudiados en la literatura abordan decisiones tácticas u operativas relacionadas con la asignación y el servicio de los buques, pero ignoran las decisiones estratégicas sobre las escalas de los buques que deben aceptarse o rechazarse. Algunos ejemplos son Cordeau et al. (2005); Lalla-Ruiz and Voss (2016); Monaco and Sammarra (2007); Xu et al. (2012); Buhrkal et al. (2011); Imai et al. (2003), por mencionar sólo algunos. Aún así, en BAP surgen decisiones estratégicas, debido a la limitada capacidad de atraque semanal de los puertos combinada con la llegada cíclica a los puertos de los barcos que hacen escala. Por tanto, es necesario abordar el BAP desde una perspectiva de largo plazo, abordando modelos que integren decisiones estratégicas sobre las peticiones a rechazar. La asignación de barcos que hacen escala cíclica en múltiples terminales dentro del mismo puerto fue estudiada en Hendriks et al. (2012), donde el objetivo es minimizar el desequilibrio relativo a la carga de trabajo de las grúas de muelle junto con la cantidad de contenedores a transportar entre terminales. Jin et al. (2015) también consideró el equilibrio de la distribución de la carga de trabajo a lo largo del tiempo y abordó la congestión de los atraques en los muelles desde un punto de vista de planificación táctica. Para ello, los autores abordaron conjuntamente el problema de diseño de la plantilla de atraque y el problema de diseño de la plantilla de patio con el objetivo de combinar los costes debidos a los flujos de contenedores con los relacionados con el desequilibrio de la carga de trabajo en el muelle. El problema de la plantilla de atraque también se ha estudiado para un muelle continuo como un problema de decisión táctica a medio plazo en Huang et al. (2016). El SBTP que estudiamos en este artículo fue propuesto en Imai et al. (2014). Como se mencionó, el SBTP se define a nivel de planificación estratégica e incluye decisiones sobre la selección de los barcos a atender y la asignación de ventanas de tiempo de atraque para los barcos seleccionados dentro de un horizonte cíclico. Además, considera condiciones adicionales que vinculan las decisiones de aceptación/rechazo de los buques nodriza y alimentadores bajo consideración. En Imai et al. (2014) los autores propusieron una formulación que extiende la de Imai et al. (2001) y varias heurísticas basadas en la solución de un dual de Lagrange con enfoques alternativos de optimización subgradiente. Los resultados computacionales mostraron la dificultad de resolver el problema con las heurísticas propuestas. El SBTP también ha sido estudiado en Iris et al. (2018), donde los autores analizan la formulación inicial propuesta en Imai et al. (2014), que permaneció computacionalmente inexplorada y proponen una formulación diferente basada en la solución de un problema generalizado de empaquetado de conjuntos (GSP). Ambas formulaciones se refuerzan al incluir límites inferiores adicionales. Se creó y utilizó un conjunto de instancias de referencia en los extensos experimentos computacionales llevados a cabo. Los resultados obtenidos mostraron que ambas formulaciones mejoraron notablemente con la adición de los límites inferiores y resaltaron la superioridad de la formulación GSP reforzada.

En este artículo desarrollamos nuevas formulaciones de programación lineal entera mixta y alternativas algorítmicas para resolver el SBTP. Además de las variables binarias estratégicas naturales asociadas con la aceptación/rechazo de escalas de barcos, todas las formulaciones propuestas utilizan variables binarias que clasifican a los barcos atendidos dependiendo de si su servicio comienza o no durante su ciclo de llegada o en el siguiente. Esto ayuda a modelar el STBP, ya que se puede obtener una expresión lineal cerrada para los tiempos de espera. Las formulaciones más básicas utilizan variables adicionales que relacionan los buques atendidos con sus predecesores inmediatos en los atraques correspondientes. Aún así, tales variables pueden evitarse expresando las horas de inicio del servicio a los buques en términos de nuevas variables de decisión binarias que indiquen si su servicio comienza o no en los diferentes períodos de tiempo del horizonte de planificación. A su vez, estas nuevas variables binarias nos permiten contabilizar el número de barcos atendidos simultáneamente en cada periodo horario, brindándonos la posibilidad de garantizar que se respeta la disponibilidad de atraques en cada periodo horario. La agregación de las nuevas variables de decisión sobre todos los amarres conduce a una formulación para una relajación de SBTP, que puede resolverse en tiempos de computación notablemente pequeños. Además, al resolver un subproblema auxiliar, la solución agregada relajada se puede desagregar en una solución SBTP factible. Esto conduce a una simple verificación de factibilidad que indica si la solución disponible es óptima o no para el SBTP. Por lo tanto, la formulación agregada se puede combinar con la verificación de factibilidad dentro de un algoritmo de solución de 2 fases para SBTP. Alternativamente, considerar variables desagregadas para los períodos iniciales de servicio a los buques aceptados en los diferentes atraques produce una formulación válida para el SBTP, a expensas de aumentar el número total de variables binarias y restricciones. Aún así, la formulación se puede resolver de manera muy eficiente con cualquier software de optimización disponible en el mercado y produce excelentes resultados.

Se han llevado a cabo extensas pruebas computacionales con el conjunto de 96 instancias de referencia generadas en Iris et al. (2018) con un número de barcos que hacen escala entre y un número de amarres entre . Los resultados obtenidos resaltan la efectividad de las dos formulaciones con base en las variables indicadoras para los períodos de inicio del servicio de los buques aceptados. Tanto el algoritmo de solución de 2 fases basado en la formulación relajada con las variables agregadas, como la formulación exacta usando las variables de decisión desagregadas superan la formulación más eficiente propuesta en Iris et al. (2018). El algoritmo de 2 fases ha resuelto con optimalidad probada 78 de los 96 casos de referencia con tiempos de cálculo que siempre están por debajo de 500 segundos. La formulación desagregada fue capaz de resolver 94 instancias de referencia en un tiempo máximo de tres horas y produjo saltos de optimalidad porcentuales muy pequeños para las dos instancias restantes.

El resto de este trabajo se estructura de la siguiente manera. En la sección x1-30002 damos una definición formal del SBTP y discutimos su relación con algunos problemas combinatorios bien conocidos. La sección x1-40003 presenta las formulaciones básicas donde los tiempos de espera se expresan en términos de variables de decisión que indican si el servicio a una llamada aceptada comienza en su ciclo de llegada o en el siguiente. En la sección x1-50003.1 introducimos la formulación con las variables agregadas del período de inicio del servicio, mientras que en la sección x1-60003.2 mostramos que es una relajación del SBTP y estudiamos algunas de sus propiedades que serán explotadas en el diseño del algoritmo de 2 fases. Las secciones x1-70004 y x1-80004.1 presentan la formulación SBTP válida basada en las variables desagregadas del período de inicio del servicio y brindan una comparación de todas las formulaciones desarrolladas en términos de su número de variables de decisión y restricciones. En la sección x1-90005 abordamos varias cuestiones algorítmicas que se explotarán para determinar soluciones factibles, ya sea desde cero o a partir de una formulación agregada relajada. Las pruebas computacionales que se han realizado se describen en la sección x1-130006 donde resumimos y analizamos los resultados numéricos que hemos obtenido y los comparamos con los de Iris et al. (2018). El artículo acaba con la sección x1-170007 con algunas conclusiones y comentarios finales.