Análisis de la formulación F1

El objetivo final del SBTP es determinar los buques que serán atendidos y obtener las secuencias de servicio a aplicar cíclicamente en cada amarre. Sin embargo, teniendo en cuenta que el objetivo consiste en una penalización por cada escala no atendida más la suma de los tiempos de espera de los barcos atendidos, que vienen dictados por sus horarios de salida, el SBTP se reduce esencialmente a identificar los barcos atendidos y encontrar horarios factibles de inicio para ellos. De hecho, los tiempos de inicio factibles pueden derivarse de secuencias de servicio factibles. Esta es, de hecho, la idea principal en la formulación que hemos presentado, donde los tiempos de salida de los barcos atendidos se determinan a partir de las secuencias de las variables predecesoras $p$

y su relación con las variables $s$

, que es establecida por las restricciones (

)-(

). La pregunta que planteamos aquí es si se pueden obtener tiempos de salida factibles sin tener una representación explícita de las secuencias de barcos atendidos en los amarres. En particular, si algún conjunto de variables $z$

están vinculados mediante las restricciones (

) y (

), junto con un conjunto de variables $h$

que satisfacen las restricciones (

) -(

) induce una solución factible para el SBTP.

Lamentablemente, como muestra el ejemplo ilustrado en la figura x1-6001r2, la respuesta a la pregunta anterior es negativa, lo que indica que las restricciones (

)-(

) no son suficientes para garantizar que se pueda obtener una solución SBTP factible. El ejemplo considera una duración de ciclo $H=8$

y $V=\{1, 2, 3\}$ , donde el tiempo de procesamiento de los tres barcos es de cinco unidades ( $c_i=5$

para todos los $i\in V$ ). Es fácil comprobar que si el número de amarres disponibles es $b=2$

, no existe una solución factible en la que se atienda a los tres barcos (independientemente de cuáles sean los horarios de llegada de los barcos). Sin embargo, como muestra la figura x1-6001r2, es posible encontrar horas de inicio para los barcos que satisfacen las restricciones (

), es decir, horas de inicio tales que en cada período de tiempo se procesen como máximo dos barcos. En la solución representada en la figura $s_1=1$

. E s decir, $h_{1t}=1$ para todo $t\in [1, 5]$ ; $h_{2t}=1$ para todos $t\in[3, 7]$ ; y, $h_{3t}=1$ para todos $t\in [1, 2]\cup[6, 8]$ . Como puede verse, estos valores satisfacen las restricciones (

**Figura:** Ejemplo con , $V=\{1, 2, 3\}$ , , $i\in V$ y donde no existe una solución factible que sirva a todos los barcos, pero se pueden encontrar valores $h_{it}$ que satisfacen las restricciones ()
$\includegraphics[width=0.5\textwidth]{dibujo2.pdf}$

Por lo tanto, concluimos que la siguiente formulación F2 es una relajación del SBTP:

La relación entre los valores óptimos de $F2$

se resume a continuación, donde $v(\cdot)$ denota el valor óptimo de un problema de optimización dado.

Dado que una solución factible a la formulación $F2$

no necesariamente induce una solución factible para el SBTP, ahora abordamos la cuestión de si podemos saber si existe una solución factible para el SBTP apoyada por un vector dado $(\bar z, \bar h)$ en el dominio factible de $F2$

. Como explicamos a continuación, la respuesta a esta pregunta se puede obtener resolviendo un problema auxiliar, que en lo sucesivo denominaremos $AP(\bar z, \bar h)$ , que puede usarse como oráculo. El problema $AP(\bar z, \bar h)$ supone que todos los barcos indexados en $\overline V=\{i\in V:\overline z_{k(i)}=1\}$ deben ser atendidos y sus horarios de inicio de servicio son los dictados por $\bar h$ . Esencialmente, $AP(\bar z, \bar h)$ reformula la pregunta anterior en términos de encontrar una asignación a los atraques de los barcos indexados en $\overline V$ , de modo que el tiempo de servicio general de todos los barcos asignados al mismo atraque no excede la duración de un ciclo y minimize la superposición total de los servicios. Dado que idealmente cada atraque tiene una capacidad de servicio de uno en cada período de tiempo, definimos la superposición de servicios en un atraque en un período de tiempo dado $t$

como el exceso de barcos asignados al atraque en el período de tiempo $t$

. Este exceso está dado por el número de buques asignados al atraque al que se presta servicio en el período $t$

menos uno, o cero cuando esta cantidad es negativa.

A continuación, sea $R=\{1, \dots, b\}$ el índice establecido para los atraques y ${\overline{ V}^t}=\{i\in \overline V: \bar h_{i}\leq t$ y $\bar h_{i}+c_i-1\geq t\} \cup \{i\in \overline V: \bar h_{i}>t$ y $(\bar h_{i}+c_i-1) \geq t + H\}$ el conjunto de barcos indexados en $\overline V$ que reciben servicio en el período de tiempo $t$

suponiendo que sus tiempos de servicio de inicio están dictados por $\bar h$ .

Para cada $i\in \overline V$ , $r\in R$ , sea $\lambda_{ir}\in \{0, 1\}$ , una variable binaria, que toma el valor 1 si y solo si el barco $i$

está asignado al atraque $r$

. Asociada con cada atraque $r\in R$ y período de tiempo $t\in T$ consideremos otra variable de decisión $\sigma_{rt}$ que indica la superposición de servicios en el atraque $r$

en el período de tiempo $t$

. Es decir, $\sigma_{rt}=\max\{\sum_{i\in \overline Z^t}\lambda_{ir}-1,\, 0\}$ es el exceso relativo a la capacidad de servicio del atraque $r$

en el periodo de tiempo $t$

Las restricciones (

) garantizan que todos los barcos de $\overline V$ estén asignados a algún atraque y (

) que el tiempo total de servicio de todos los barcos asignados al mismo atraque no exceda la duración del ciclo. Finalmente, las restricciones (

) determinan los solapamientos, cuya cantidad total se minimiza.

Obsérvese que $AP(\bar z, \bar h)$ es una variación de un problema de mochila (ver, p.e. capítulo 18 en Korte and Vygen, 2006), donde la capacidad de las mochilas es $H$

y la demanda del barco $i\in \overline V$ es $c_i$

, y recuérdese que se sabe que el problema de la mochila es NP-duro Garey and Johnson (1979). Además, dado que imponemos que todos los barcos indexados en $\overline V$ estén asignados, puede suceder que su dominio factible esté vacío. Sea $\Omega_{AP(\bar z, \bar h)}=\{ (\lambda, \sigma)\in\{0,\, 1\}^{\vert\overline V\vert}\times \mathbf{ R}^+:$ satisfaciendo $\eqref{alloc:assign}- \eqref{alloc:domain2}\}$ que denota el dominio factible de $AP(\bar z, \bar h)$ .

Proposición 2

Si $\Omega_{AP(\bar z, \bar h)}=\emptyset$ , entonces no hay una solución factible para que $SBTP$

que atiende a todos los barcos indexados en $\overline V$ . Supongamos que $\Omega_{AP(\bar z, \bar h)}\neq \emptyset$ . Entonces,

Existe una solución factible al SBTP que atiende a todos los barcos indexados en $\overline V=\{i\in V:\overline z_{k(i)}=1\}$ con tiempos de inicio dados por $\{\bar h_{it}\}_{i\in \overline V, t \in T}$ si y solo si $v(AP(\bar z, \bar h))$ es cero.
Supongamos $v(AP(\bar z, \bar h))=0$ , y sea $\bar \lambda$ el vector de asignación asociado con una solución óptima de $AP(\bar z, \bar h)$ . Entonces la solución $(\bar z, \bar h)$ donde cada barco $i\in \overline V$ inicia su servicio en el periodo de tiempo con $\bar h_{it}=1$ en el atraque $r\in R$ tal que $\bar\lambda_{ir}=1$ es una solución SBTP óptima.

Cuando $\Omega_{AP(\bar z, \bar h)}\neq \emptyset$ , pero $v(AP(\bar z, \bar h))>0$ , entonces no existe una solución factible para que SBTP sirva a todos los barcos de $\overline V$ con tiempos de inicio $\{\bar h_{it}\}_{i\in \overline V, t \in T}$ . Aún así, a partir de una asignación óptima a $AP(\bar z, \bar h)$ se puede obtener heurísticamente una solución SBTP factible. Dado que el tiempo total de servicio de todos los barcos asignados al mismo atraque no excede la duración del ciclo, es posible secuenciar todos estos barcos de tal manera que no haya superposiciones de servicios, aunque esto conllevará cambios en los tiempos de inicio del servicio de algunos buques y, a su vez, en sus tiempos de espera, como se comentará en el apartado x1-90005.