Cuestiones algorítmicas para determinar completamente las soluciones SBTP factibles

Una solución SBTP factible está completamente determinada por ( $i$ ) el conjunto de barcos atendidos, ( $ii$ ) el tiempo de servicio de cada barco y ( $iii$ ) la asignación de los barcos atendidos a los atraques. Todas las formulaciones que hemos introducido incluyen información explícita sobre los ítems ( $i$ ) y ( $ii$ ), a través de las variables de decisión $z_k$ , $k\in K$ y $s_i$ , $i\in V$ , respectivamente, que son los dos conjuntos de variables de decisión comunes a las cuatro formulaciones. Aún así, excepto para la formulación F3, en la que la expresión $\sum_{t\in T}\hat h_{irt}$ da información explícita sobre si el barco $i\in V$ está asignado o no al atraque $r\in R$ , todas las demás formulaciones omiten dicha información. Además, incluso si los horarios de salida junto con la asignación explícita de los buques a los atraques determinan la secuencia de servicio de cada atraque, esta información no es explícita en ninguna de las formulaciones presentadas: en F0 y F1 porque la asignación de atraques no es explícita (a pesar de tener el vector de predecesores $p$ ) y en las formulaciones F2 y F3 porque no incluyen información de secuenciación explícita.

Por otro lado, en la sección x1-60003.2 hemos visto que F2 es una relajación que no necesariamente produce soluciones SBTP factibles, aunque en algunos casos los subproblemas auxiliares $AP(\bar z, \bar h)$ , $r\in R$ dan asignaciones de barcos a atraques que pueden dar soluciones factibles. Obtener soluciones factibles a partir de la información proporcionada por estos subproblemas auxiliares puede ser útil, no sólo dentro de un marco algorítmico basado en F2, sino también para apoyar cualquier formulación válida con alguna solución factible inicial, que podría usarse como base y posiblemente podría reducir la carga computacional necesaria para resolver de manera óptima las formulaciones.

En el resto de esta sección, primero presentamos procedimientos simples para obtener asignaciones explícitas de atraques y secuencias explícitas de barcos consecutivos atendidos en cada atraque. Luego damos una plantilla simple para encontrar soluciones SBTP factibles, basadas en la solución de los subproblemas $AP(\bar z, \bar h)$ .

Subsecciones