Resultados numéricos para instancias con cuatro atraques
Siguiente: Resultados numéricos para instancias Subir: Experimentos computacionales Anterior: Experimentos computacionales


Resultados numéricos para instancias con cuatro atraques

Comenzamos nuestro análisis comparando varias formulaciones y esquemas algorítmicos simples entre ellos en las instancias con cuatro atraques, todas las cuales tienen un número de barcos que hacen escala $n\in\{50, 70\}$. Es decir, consideramos las clases $\mathcal{C}_{n\_4\_c\_s}$, para variar los valores de los parámetros restantes.

Las pruebas preliminares indicaron que la formulación F0 produjo límites LP muy débiles y solo fue capaz de resolver instancias de tamaño pequeño con optimalidad probada. Por lo tanto, lo excluimos de una mayor consideración y nos centramos en las formulaciones restantes. Por otro lado, hemos utilizado la formulación F2 dentro del marco algorítmico de dos fases descrito en la sección x1-120005.3 en la que la primera fase consiste en resolver F2, por lo que produce un límite inferior válido y la segunda fase, que produce un límite superior válido, consta de la solución del problema auxiliar $AP(\bar z, \bar h)$, seguido de la solución de los subproblemas SEQ$_r$, asociados con los conjuntos de barcos resultantes $B^r$, $r\in R$. Recuerde que la proposición x1-60032 nos da una verificación simple de la optimalidad de las soluciones producidas por F2. En particular, cuando $v(AP(\bar z, \bar h))=0$, la solución producida por F2 es factible para SBTP y, por lo tanto, óptima.

En el resto de esta sección compararemos los siguientes límites:

F3 produjo soluciones óptimas para todas las instancias consideradas dentro de un tiempo de cálculo máximo de 3600, con la excepción de la instancia 21_70_4B_E_S, para la cual F3 consumió más de 9000 segundos. Esto nos permite informar las desviaciones porcentuales de los límites superior e inferior anteriores en relación con los valores óptimos, así como los saltos porcentuales de optimización de los intervalos $[L_i, U_i]$, $i=0, 1, 2, 3$. En todos los casos, los límites que analizamos corresponden a tiempos de espera. Es decir, si el valor de una solución es $W+P^*$, donde $W=\sum_{i\in \overline V}w_i$ es el tiempo total de espera de los barcos atendidos, excluimos el término de penalización constante $P^*$ y solo considera el valor $W$. De lo contrario, diferencias relativamente grandes en el valor de $W$ pueden ocultarse de alguna manera detrás del gran valor del término de penalización $P^*$. Por lo tanto, los límites reales que consideramos para $i=0, \dots, 3$ son $L^w_i$ y $U^w_i$, tales que $L_i=L^w_i+P^*$ y $U_i=U ^w_i + P^*$. Entonces, si $W^*$ es el tiempo de espera total en una solución óptima, las desviaciones porcentuales y las brechas de optimización que informamos se definen de la siguiente manera:

La tabla x1-14001r3 proporciona valores promedio, sobre todas las instancias en cada una de las clases $\mathcal{C}_{n\_4\_c\_s}$, de las desviaciones y brechas porcentuales anteriores, así como como los tiempos de cálculo (en segundos) necesarios para obtener cada uno de los límites correspondientes. Se estableció un tiempo máximo de cálculo de 3600 segundos en todas las pruebas, a excepción de la instancia 21_70_4B_E_S con formulación F3 para la cual, como se mencionó, permitimos exceder ese límite de tiempo para garantizar la optimalidad de la solución obtenida. La tabla también proporciona el número total de instancias de la clase correspondiente resueltas con optimalidad probada en cada caso. El encabezado de la tabla consta de tres filas que indican el número de barcos que hacen escala ($n$), la combinación de parámetros (S/L-A/E) y las etiquetas de las instancias en la clase correspondiente (Etiquetas), respectivamente. Como puede verse, cada clase de instancia $\mathcal{C}_{n\_4\_c\_s}$ está asociada con una columna. Los resultados numéricos se resumen en cuatro bloques de filas, el primero, denominado HEUR, para la solución heurística combinada con el límite LP de F1, es seguido por un bloque para cada una de las formulaciones F1, F2 y F3, cada uno de ellos etiquetado como $F_i$, $i=1, \dots, 3$, respectivamente. Los bloques HEUR, $F_1$ y $F_3$ tienen la misma estructura que consta de cinco filas; las primeras tres filas se refieren a $\%DL_i^w$, $\%DU_i^w$ y $\%G_i^w$, respectivamente, la fila CPU$_i$ a los tiempos de cálculo y la fila $\char93 Opt_i$ proporciona el número de instancias en cada clase resueltas de manera óptima dentro del tiempo máximo de computación. El bloque $F_2$ consta de siete filas, las dos primeras relacionadas con el resultado de la formulación F2: desviaciones porcentuales promedio $\%DL_2^w$ y tiempos de cálculo promedio para resolver óptimamente F2 ($TL_2$). Las siguientes dos filas están relacionadas con el resultado de la segunda fase del procedimiento algorítmico que hemos explicado: desviaciones porcentuales promedio de los límites superiores obtenidos ($\%DU_2^w$) y tiempos de cálculo promedio ($TU_2$). Las últimas tres filas proporcionan las brechas porcentuales promedio en la terminación ($\%G_2^w$), los tiempos totales de computación ( $CPU_2=TL_2+TU_2$) y el número de instancias resueltas con optimalidad comprobada ($\char93 Opt_2$), que es dado por el número de instancias en cada clase para las cuales la proposición x1-60032 basada en la verificación de optimalidad indicó que la solución producida por F2 era factible para SBTP.

A primera vista, los resultados de HEUR pueden parecer bastante modestos, aunque una mirada más cercana resalta los siguientes aspectos positivos: la simplicidad de los procedimientos utilizados para obtener los límites inferior y superior, la calidad de los límites LP producidos por formulación F1 y los pequeños tiempos de cálculo necesarios para obtener estos límites superiores e inferiores (iniciales). De hecho, estos resultados son superados por los de F1, aunque de alguna manera es decepcionante que la buena calidad de los límites iniciales de LP no resulte en una exploración más efectiva del árbol de enumeración. Como puede verse, sólo 10 de estos 32 casos de referencia se resolvieron de forma óptima en el plazo máximo de una hora. Tenga en cuenta que todas las instancias resueltas óptimamente pertenecen a clases donde el parámetro tipo de servicio es $s=S$, es decir, tienen tiempos de servicio pequeños. Entre los casos con tiempos de servicio grandes, aquellos correspondientes a la composición A (donde la proporción de los diferentes tipos de barcos no es la misma) produjeron límites inferiores algo más estrictos en la terminación; en particular, esos límites inferiores coincidieron con el valor óptimo para dos instancias adicionales en la clase $\mathcal{C}_{50\_4\_A\_L}$ y una instancia adicional en $\mathcal{C}_{70\_4\ _A\_L}$. Sin embargo, los resultados generales indican que, si bien la F1 produce límites inferiores muy ajustados en tiempos de computación pequeños, tiene dificultades para producir soluciones factibles de buena calidad. De hecho, en varios casos sin resolver, el límite superior en la terminación se asoció con una solución encontrada por la heurística predeterminada en el nodo raíz.

Por el contrario, los resultados mostrados en el bloque F2 indican la efectividad del procedimiento de solución de 2 fases basado en la formulación F2. Por un lado, F2 produce límites inferiores extremadamente ajustados, que ya corresponden a valores óptimos de SBTP para 15 y 10 de los 16 casos con $n=50$ y $n=70$, analizados respectivamente en la tabla x1-14001r3. Como se puede observar, el valor de $\%DL_2^w$ para la clase $\mathcal{C}_{50\_4\_L\_E}$ es 0, lo que significa que por ejemplo 11, que es el único caso de $\mathcal{C}_{50\_4\_L\_E}$ donde el resultado de F2 no fue factible para SBTP, el límite inferior obtenido coincidió con el valor óptimo de SBTP. Los valores de $\%DL_2^w$ para las clases $\mathcal{C}_{70\_4\_L\_A}$ y $\mathcal{C}_{70\_4\_L\_E}$ son un poco más altos: 0,39 y 2,82, respectivamente. Para $\mathcal{C}_{70\_4\_L\_A}$ nuevamente hay una sola instancia (la etiquetada como 31) para lo cual el límite inferior producido por F2 no coincidió con el valor óptimo de SBTP. En cambio, ninguno de los límites inferiores obtenidos para las instancias de $\mathcal{C}_{70\_4\_L\_E}$ coincidió con sus valores óptimos y sus desviaciones porcentuales oscilan entre 2,04 y 4,63. Nos gustaría llamar la atención sobre los tiempos de cálculo necesarios para resolver óptimamente F2, que para todos los casos con $n=50$ y $n=70$ fueron menores que 12 y 26 segundos, respectivamente.

Sin embargo, los mejores resultados se obtuvieron claramente con la formulación F3, que produjo soluciones óptimas para todos los casos considerados. Los tiempos de computación son notables. Todas las instancias de las clases $\mathcal{C}_{50\_4\_S\_A}$ y $\mathcal{C}_{50\_4\_S\_E}$ se resolvieron en menos de 2,5 segundos; los tiempos de cálculo de las instancias en $\mathcal{C}_{50\_4\_L\_A}$ oscilan entre 2,9 y 73,1 segundos, excepto la instancia 15, que requirió 128,4 segundos. Las instancias en $\mathcal{C}_{50\_4\_L\_E}$ se resolvieron en menos de 275 segundos, con la excepción de la instancia 9, que requirió 128,4 segundos. Como era de esperar, los tiempos de cálculo aumentan con el número de barcos que hacen escala, aunque los tiempos de cálculo siguen siendo muy pequeños. Sólo dos de las 16 instancias con $n=70$ requirieron más de 1000 segundos: instancia 21, que, como se mencionó, consumió 9368.14 segundos, y la instancia 31, que consumió 1091,5 segundos.


Tabla: Resumen de resultados numéricos para instancias pequeñas con $b=4$ y $n\in\{50, 70\}$.
$n$: 50 70
L/S-A/E: S-A S-E L-A L-E S-A S-E L-A L-E
Inst. labels: 1-4 5-8 13-16 9-12 17-20 21-24 29-32 25-28
HEUR $DL_0^w$ 0.00 0.10 1.42 4.66 1.13 0.91 8.04 7.85
$DU_0^w$ 31.40 38.28 46.46 92.77 59.04 43.40 246.14 179.85
$\%G_0^w$ 31.40 38.42 48.52 103.92 61.00 44.79 281.38 203.05
$CPU_0$ 0.74 0.69 3.59 12.18 26.80 4.29 7.30 6.03
$\char93 Opt_0$ 0 0 0 0 0 0 0 0
F1 $DL_1^w$ 0.00 0.00 1.49 0.11 0.00 0.17 4.86 4.44
$DU_1^w$ 0.00 0.00 76.55 43.60 11.86 33.79 126.25 125.64
$\%G_1^w$ 0.00 0.00 80.01 43.25 11.86 30.00 137.52 136.52
$CPU_1$ 2.54 6.71 3599.81 3600.29 1846.31 3599.87 3599.86 3600.51
$\char93 Opt_1$ 4 4 0 0 2 0 0 0
F2 $DL_2^w$ 0.00 0.00 0.00 0.00 0.00 0.00 0.39 2.82
$TL_2^w$ 0.21 0.26 2.56 7.83 0.79 6.76 19.35 15.74
$DU_2^w$ 0.00 0.00 0.00 4.77 0.00 0.00 9.33 46.23
$TU_2^w$ 0.04 0.05 0.06 5.23 0.20 0.06 6.96 75.53
$\%G_2^w$ 0.00 0.00 0.00 4.77 0.00 0.00 9.76 50.47
$CPU_2$ 0.25 0.31 2.62 13.06 1.00 6.83 26.31 91.26
$\char93 Opt_2$ 4 4 4 3 4 4 2 0
F3 $DL_3^w$ 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
$DU_3^w$ 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
$\%G_3^w$ 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
$CPU_3$ 1.52 1.73 53.83 407.46 7.03 2357.58 650.40 576.25
$\char93 Opt_3$ 4 4 4 4 4 4 4 4

Siguiente: Resultados numéricos para instancias Subir: Experimentos computacionales Anterior: Experimentos computacionales