El problema de la plantilla de atraque estratégico

Como se mencionó, el objetivo del SBTP es desarrollar una plantilla para un horizonte temporal cíclico, en el que las solicitudes de servicio de algunos barcos pueden ser rechazadas. Dicha plantilla debe diferenciar entre barcos aceptados (servidos) y rechazados (no atendidos). Además, debe tener en cuenta que el servicio a un buque aceptado puede iniciarse en el ciclo siguiente al de su llegada al puerto, o que, incluso si el servicio comienza en el mismo ciclo de llegada del buque, su servicio puede terminar en el siguiente ciclo. Para diferenciar entre los ciclos potencialmente diferentes cuando se llevan a cabo las operaciones, usaremos los términos ciclo de llegada, ciclo de servicio y ciclo de terminación para referirnos al ciclo cuando llega un barco determinado a puerto, cuando su servicio inicia y cuando termina, respectivamente. Cuando el ciclo de servicio de un buque servido no coincida con su ciclo de llegada, será el ciclo siguiente al ciclo de llegada del buque. Del mismo modo, cuando el ciclo de terminación de un buque servido no coincida con su ciclo de servicio, será el ciclo siguiente al ciclo de servicio (y llegada) del buque.

Sea $H$ la duración de un ciclo y $V=\{1, \dots , n\}$ el conjunto de índices para los barcos. Asociado con cada barco $i\in V$ , sean $a_i$ y $c_i$ los tiempos de llegada y de procesamiento (servicio), respectivamente. Suponemos que dentro de cada ciclo todas las actividades tienen lugar en un horizonte temporal discretizado $T=\{1, \dots , H\}$ . Así, suponemos que $a_i$ , $c_i$ , así como los tiempos de todas las operaciones relacionadas con los barcos aceptados toman valores en $T$ . Sea $K=\{1, \dots, m\}$ el conjunto de índices para los subgrupos vinculados de barcos, $V_k\subset V$ el $k$ -ésimo subconjunto de barcos, y $C_k=\sum_{i \in V_k}c_i$ el tiempo total de procesamiento de todos los barcos de la clase $k$ . Al definir un subconjunto unitario $V_k=\{i\}$ (con el coeficiente asociado $C_k=c_i$ ) para cada barco $i$ originalmente no adjunto a ninguna nave nodriza, asumimos sin pérdida de generalidad que $\{V_k \}_{k\in K}$ define una partición de $V$ . A continuación, para cada $i\in V$ , $k(i)\in K$ denota el índice del subconjunto $V_k$ tal que $i\in V_{k(i)}$ .

El objetivo del SBTP es doble. Desde el punto de vista estratégico, su objetivo es reducir los rechazos de las peticiones de servicio. En el aspecto operativo, apunta a reducir los tiempos de espera de los barcos (atendidos) desde su llegada hasta el inicio de su servicio. Específicamente, sea $g \geq 0$ una penalización dada por unidad de tiempo de servicio rechazada; es decir, si se rechaza la petición de la clase $k\in K$ , entonces se incurre en un costo $g\times C_k$ . Además, cada barco atendido incurre en un coste de una unidad por unidad de tiempo de espera. Por lo tanto, el objetivo consta de la suma de dos términos: ( $i$ ) la penalización total por llamadas rechazadas ( $g\sum_{k\in \overline K} C_k$ ), y ( $ii$ ) el tiempo total de espera de los barcos atendidos ( $\sum_{i\in\overline V} w_i$ ), donde $\overline K\subseteq K$ denota el conjunto de índices de las clases de buques rechazados, $\overline V\subseteq V$ el conjunto de índices de barcos atendidos y $w_i$ el tiempo que espera el barco $i$ desde su llegada hasta que inicia su servicio.

El SBTP debe determinar una partición de las clases de buques que serán atendidas/rechazadas, así como una asignación de atraques junto con una secuencia cíclica para el servicio de las escalas aceptadas asignadas al mismo atraque, de manera que el tiempo total de servicio de las peticiones atendidas en el mismo atraque no exceda la duración del ciclo, $H$ .

Observe que el SBTP integra tres problemas combinatorios difíciles. Por un lado, la selección de los barcos que serán atendidos, respetando las relaciones entre los barcos de cada grupo. Por otro lado, la asignación de los buques aceptados a los atraques, respetando la duración del ciclo dentro de cada atraque, lo que puede verse como un problema de embalaje de contenedores Korte and Vygen (2006). Finalmente, la secuenciación óptima del servicio para todos los barcos asignados a cada atraque, que puede reducirse al problema de encontrar el horario de servicio que minimice la tardanza total Du and Leung (1990). Tanto empacar en el contenedor como minimizar las tardanzas ya son problemas NP-difíciles.