Marco algorítmico para encontrar soluciones SBTP factibles

A continuación presentamos un marco algorítmico para construir soluciones SBTP factibles:

S1 Defina un subconjunto tentativo de barcos servidos, $\overline V$ , y tiempos de servicio tentativos para los barcos seleccionados, $\bar h_i$ , $i\in \overline V$ , respetando las restricciones del barco nodriza ().

S2 Obtener una asignación de barcos seleccionados a los atraques, $\{B^r\}_{r\in R}$ , que satisfaga la duración del ciclo, es decir, $\sum_{i\in B^r}c_i \le H$ , $r\in R$ , desviándose lo menos posible de los tiempos de servicio tentativos $\bar h_i$ , $i\in \overline V$ .

S3 Para cada atraque $r\in R$ , cree una secuencia de servicio para los barcos asignados a él, $\{B^r\}$ .

Hay varias formas de implementar el esquema algorítmico anterior. Por ejemplo, la formulación F2 se puede utilizar para S1 y el problema auxiliar $AP(\bar z, \bar h)$ para S2. Esto naturalmente conduce a un algoritmo de solución de 2 fases en el que la primera fase produce un límite inferior válido, aunque no necesariamente una solución SBTP factible y la segunda fase produce un límite superior válido asociado con la solución SBTP factible obtenida después de aplicar S2+S3.

Otra posibilidad que permite obtener soluciones SBTP factibles desde cero, es fusionar S1 y S2 en un solo paso en el que se resuelve una variación de $AP(\bar z, \bar h)$ con $\overline V=V$ , donde los tiempos de llegada se utilizan como tiempos de servicio tentativos, es decir, $\bar h_{it}=1$ si y solo si se establecen $t=a_i$ , $i\in V$ y restricciones () como desigualdades “ $\leq$ ”. Ahora bien, para garantizar que se cumplan las restricciones de la nave nodriza, se deben imponer las siguientes restricciones adicionales:

$\displaystyle \sum_{r\in R}\lambda_{ir}=z_{k(i)}, \qquad \qquad i\in V.$

Para lograr un equilibrio entre los barcos atendidos (que ahora no se conocen de antemano) y la superposición de servicios (que puede ser bastante alta, dado que los tiempos de servicio se ajustan a los tiempos de llegada), un objetivo adecuado que incorpore una combinación ponderada de ambos criterios es la maximización de:

$\displaystyle \mu \sum_{i\in V}c_i\sum_{r\in R}\lambda_{ir}-\sum_{r\in R}\sum_{t\in T}\sigma_{rt}.$

En S3, para encontrar una secuencia de servicio óptima del conjunto de barcos $B^r$ asignados a cada atraque $r\in R$ ignoramos los tiempos de inicio tentativos $\bar h_i$ y buscamos una secuencia de los barcos de $B^r$ que minimiza los tiempos totales de espera. Para esto utilizamos una formulación que particulariza F2 para un solo atraque, suponiendo que el conjunto de barcos que deben ser atendidos es precisamente $B^r$ . Las variables $z$ ya no son necesarias, ya que es posible atender a todos los barcos indexados en $B^r$ dentro de un ciclo, dado que el resultado de S2 satisface que $\sum_{i\in B^r} {c_i }\leq H$ . Tenga en cuenta que la formulación resultante ahora es exacta, ya que estamos restringiendo a un solo lugar de atraque (el lado derecho de la restricción actualizada () será 1), por lo que no pueden aparecer superposiciones de servicios entre los lugares de atraque. La formulación correspondiente al atraque $r$ es:

$\begin{subequations}\begin{align} \text{SEQ}_r\qquad \qquad & \min\sum\limits_{i... ...e{-0.6cm}\hspace{1.23cm}s_i, w_i\ge 0 && i\in B^r. \end{align}\end{subequations}$

Observe que los tiempos de espera resultantes de los tiempos de llegada $a_i$ , pueden verse como la tardanzas relativas a las fechas de vencimiento $a_i+c_i-1$ . Por lo tanto SEQ $_r$ es una formulación exacta para la minimización de la tardanza total como se define anteriormente. Como se muestra en Du and Leung (1990), este problema ya es NP-difícil.

S1	Defina un subconjunto tentativo de barcos servidos, $\overline V$ , y tiempos de servicio tentativos para los barcos seleccionados, $\bar h_i$ , $i\in \overline V$ , respetando las restricciones del barco nodriza ().
S2	Obtener una asignación de barcos seleccionados a los atraques, $\{B^r\}_{r\in R}$ , que satisfaga la duración del ciclo, es decir, $\sum_{i\in B^r}c_i \le H$ , $r\in R$ , desviándose lo menos posible de los tiempos de servicio tentativos $\bar h_i$ , $i\in \overline V$ .
S3	Para cada atraque $r\in R$ , cree una secuencia de servicio para los barcos asignados a él, $\{B^r\}$ .