Resultados numéricos para instancias más grandes
Siguiente: Comparación de F2 y Subir: Experimentos computacionales Anterior: Resultados numéricos para instancias


Resultados numéricos para instancias más grandes

A continuación presentamos los resultados que hemos obtenido con las instancias con $b\in\{8, 12\}$, todas las cuales tienen un número de barcos $n\in\{70, 100, 150\}$. Teniendo en cuenta los resultados obtenidos con las instancias más pequeñas, ahora hemos probado el algoritmo de 2 fases basado en $F2$ y la formulación $F3$. Si bien no establecimos un límite de tiempo máximo para el algoritmo de 2 fases, ya que en todos los casos el procedimiento terminó en tiempos de cálculo pequeños, sí establecimos un límite de tiempo máximo de 10.800 segundos (tres horas) para la solución de la formulación F3. Para facilitar la legibilidad de los resultados numéricos se resumen en dos tablas diferentes: tabla x1-15001r4 para el procedimiento de 2 fases basado en F2 y tabla x1-15002r5 para los resultados obtenidos con formulación $F3$. La estructura de ambas tablas es similar: cada fila corresponde a una clase de instancias y, excepto las columnas que muestran las características de las instancias, hay una columna para cada uno de los ítems analizados. Por lo tanto, la tabla x1-15001r4 tiene siete columnas de este tipo, etiquetadas respectivamente con $\%DL_2^w$, $TL_2$, $\%DU_2^w$, $TU_2$, $\%G_2^w. $, $CPU_2$ y $\char93 Opt_2$, mientras que la tabla x1-15002r5 tiene cinco de estas columnas, etiquetadas respectivamente con $\%DL_3^w$, $\%DU_3^w$, $\%G_3^w$, $CPU_3$ y $\char93 Optar_3$. El significado de los títulos es el mismo que en la tabla x1-14001r3.


Tabla: Resumen de resultados numéricos con F2 para instancias con $b=4$ y $n\in\{50, 70\}$
$b$ $n$ S/L A/E Inst. $\%DL_2^{w}$ $TL_2$ $\%DU_2^w$ $TU_2$ . $\%G_2^w$ $CPU_2$ . $\char93 Opt_2$
4 100 S A 33-36 0.00 12 .14 3.75 2 .01 3.75 14 .15 3
E 37-40 0.00 16 .97 0.00 0 .08 0.00 17 .05 4
L A 45-48 0.29 25 .48 31.46 8 .77 31.91 34 .24 1
E 41-44 2.03 20 .72 34.01 1 .94 36.91 22 .66 0
8 70 S A 61-64 0.00 0 .30 0.00 0 .12 0.00 0 .41 4
E 57-60 0.00 0 .32 0.00 0 .12 0.00 0 .45 4
L A 49-52 0.00 0 .43 0.00 0 .15 0.00 0 .57 4
E 53-56 0.00 0 .46 0.00 0 .19 0.00 0 .65 4
100 S A 65-68 0.00 0 .42 0.00 0 .16 0.00 0 .58 4
E 77-80 0.00 0 .52 0.00 0 .12 0.00 0 .64 4
L A 69-72 0.00 1 .43 0.00 0 .26 0.00 1 .70 4
E 73-76 0.07 10 .67 2.84 225 .56 2.92 236 .22 1
12 150 S A 93-96 0.00 0 .77 0.00 0 .21 0.00 0 .98 4
E 81-84 0.00 0 .83 0.00 0 .33 0.00 1 .16 4
L A 89-92 0.00 1 .65 0.00 4 .18 0.00 5 .83 4
E 85-88 0.00 6 .69 0.00 14 .55 0.00 21 .23 4

Nuevamente podemos apreciar el excelente desempeño tanto del procedimiento de solución de 2 fases como de la formulación F3. El esquema algorítmico basado en F2 produjo una solución óptima demostrable para 53 de los 64 casos más grandes y para los casos en los que no se encontró una solución óptima, las desviaciones porcentuales $\%DL_2^{w}$ son extremadamente pequeñas. Las desviaciones más grandes aparecen en $\mathcal{C}_{100\_4\_L\_E}$, en particular, por ejemplo, 44_50_4B_E_L, donde la desviación porcentual del límite inferior producida por F2 y el valor óptimo es 3,85. Otras clases de instancias donde no siempre se encontraron soluciones SBTP óptimas son $\mathcal{C}_{100\_4\_S\_A}$, $\mathcal{C}_{100\_4\_L\_A}$ y $\mathcal{C}_{100\_8\_L\_E}$. Aun así, en la mayoría de los casos en los que F2 no produjo una solución óptima, el límite inferior obtenido coincide con el valor óptimo de SBTP, las únicas excepciones son la instancia 44_50_4B_E_L con una desviación porcentual de 1,18 y la instancia 76 con una desviación porcentual de 2,29.

Si bien los límites inferiores producidos por F2 son óptimos o casi óptimos, la calidad de los límites superiores no es tan alta en los casos en los que la verificación de optimalidad no certificó la optimalidad de la solución obtenida. Esto no es sorprendente, dada la simplicidad de la segunda fase, que produce una solución factible en la que la asignación de los barcos servidos a los atraques está dictada por el resultado de $AP(\bar z, \bar h)$, a pesar de que la comprobación de la optimalidad ha resultado negativa, lo que es una indicación bastante clara de que dicha asignación probablemente no sea óptima. Aún así, los límites superiores que obtenemos en tales casos son, en general, bastante ajustados, con la excepción de aquellos para instancias en las clases $\mathcal{C}_{100\_4\_L\_A}$ y $\mathcal{C}_{100\_4\_L\_E}$.

Nótese que todas las instancias que no fueron resueltas óptimamente con el procedimiento basado en F2 corresponden a clases con valores altos de la relación de demanda $R=D/B$. En particular, para $\mathcal{C}_{100\_4\_L\_E}$, que produjo las mayores brechas de desviación porcentual, $R=1.97$ (la demanda general es casi el doble de la capacidad de servicio), que es la mayor valor entre todas las clases. Clases $\mathcal{C}_{100\_4\_S\_A}$, $\mathcal{C}_{100\_4\_L\_A}$ y $\mathcal{C}_{100\_8\_L\_E}$ también tiene valores de $R>1$.

Finalmente observamos que los tiempos totales de cálculo requeridos por el procedimiento de 2 fases son notablemente pequeños. Los tiempos medios totales de cálculo siempre están por debajo de los 250 segundos, incluso para la clase más exigente en ese sentido, $\mathcal{C}_{100\_8\_L\_E}$. Observe que los tiempos de cálculo promedio de la primera fase en la que la formulación F2 se resuelve de forma óptima, $TL_2$, están por debajo de 26 segundos para todas las clases de instancias. La instancia individual más exigente para la primera fase fue la instancia 45, que requirió menos de 35 segundos. La primera fase consumió menos de cinco segundos para todas las instancias con $n=150$, con la excepción de la instancia 85, lo que requirió casi 16 segundos. De hecho, la carga computacional del procedimiento de 2 fases depende esencialmente de la segunda fase y, en particular, de la solución del problema de asignación de atraques $AP(\bar z, \bar h)$, que se vuelve más exigente, no sólo a medida que aumentan los tamaños de las instancias, pero principalmente a medida que aumenta la tasa de demanda $R$. Podemos observar que el mayor tiempo promedio de cálculo para la segunda fase de 236.22 segundos corresponde nuevamente a la clase $\mathcal{C}_{100\_8\_L\_E}$, que como se mencionó, tiene el mayor valor de $R$.


Tabla: Resumen de resultados numéricos con F3 para instancias con $b=4$ y $n\in\{50, 70\}$
F3
$b$ $n$ S/L A/E Inst. $\%DL_3^w$ $\%DU_3^w$ $\%G^w_3$ $CPU_3$ $\char93 Opt_3$
4 100 S A 33-36 0.00 0.00 0.00 848.24 4
E 37-40 0.00 0.00 0.00 1112.21 4
L A 45-48 0.00 0.00 0.00 401.28 4
E 41-44 0.00 0.00 0.00 522.88 4
8 70 S A 61-64 0.00 0.00 0.00 3.19 4
E 57-60 0.00 0.00 0.00 3.51 4
L A 49-52 0.00 0.00 0.00 5.99 4
E 53-56 0.00 0.00 0.00 6.90 4
100 S A 65-68 0.00 0.00 0.00 5.75 4
E 77-80 0.00 0.00 0.00 6.64 4
L A 69-72 0.00 0.00 0.00 1030.30 4
E 73-76 0.00 0.00 0.00 3258.72 4
12 150 S A 93-96 0.00 0.00 0.00 9.45 4
E 81-84 0.00 0.00 0.00 12.76 4
L A 89-92 0.00 0.00 0.00 22.46 4
E 85-88 0.10 1.60 1.70 7173.10 2

Ahora centramos nuestra atención en los resultados de la formulación F3, que se resumen en la tabla x1-15002r5. Como se puede observar, 62 de los 64 casos de las clases consideradas se resolvieron con optimalidad probada dentro del límite de tiempo máximo de 10.800 segundos. Las únicas dos instancias que no se resolvieron óptimamente pertenecen a la clase $\mathcal{C}_{150\_12\_L\_E}$, es decir, las instancias 85 y 86. Dado que ambos casos se resolvieron de manera óptima con el procedimiento de 2 fases, conocemos sus valores óptimos, por lo que los resultados obtenidos se pueden evaluar mejor. En particular, sus tiempos de espera totales óptimos son 440 y 362, respectivamente. Al finalizar, los límites inferior y superior del tiempo total de espera que obtuvimos, por ejemplo, 85 son $L_3^w=439.30$ y $U_3^w=467$, respectivamente, con las desviaciones porcentuales correspondientes de $DL_3^w=0.16\%$ y $DU_3^w=6.14\%$. Por ejemplo 86 los límites obtenidos son $L_3^w=361.16$ y $U_3^w=363$, lo que da como resultado desviaciones porcentuales de $DL_3^w=0.23\%$ y $DU_3^w=0.51\%$. Así, en ambos casos redondeando el límite inferior obtenemos los valores óptimos. Mientras que el límite superior del ejemplo 86 difiere en solo una unidad del valor óptimo, la mejor solución encontrada, por ejemplo 85, tiene un valor de 467, con una diferencia de 27 del valor óptimo.

En general, los tiempos de cálculo necesarios para resolver F3 están notablemente por debajo del límite de tiempo máximo. Aparte de las instancias 85-86, que alcanzaron el límite, sólo tres instancias (71, 75 y 76) requirieron más de una hora de tiempo de cálculo; sus respectivos tiempos de cálculo son 4.044, 4.376 y 6.043 segundos.

De manera similar a lo que hemos observado con el algoritmo de 2 fases, la dificultad para resolver una instancia depende claramente de su tasa de demanda: los tiempos de cálculo promedio más altos están, en general nuevamente asociados con instancias con valores de $R$ muy cercanos a 1. Las dos instancias que alcanzaron el límite pertenecen tienen $n=150$, $b=12$, es decir, 228.000 variables binarias $\hat h$ y tienen una tasa de demanda $R=0,96$, que está bastante cerca de 1 y es la tasa de demanda más grande entre todas las clases de instancias con $n=150$. Esto se puede apreciar claramente en la figura x1-15003r3 donde hemos trazado los tiempos de cálculo del conjunto completo de instancias individuales tanto para F2 como para F3.

Figura: Tiempos de cálculo para $F2$, $F3$ para el conjunto completo de instancias de referencia.
\includegraphics[width=0.8\textwidth]{TimesF2F3.pdf}

Una mirada detallada a los límites superiores e inferiores individuales para cada una de las instancias (consulte las tablas x1-19001r7-x1-19006r12 en el apéndice) resalta la notable calidad de los límites inferiores y superiores individuales para cada una de las instancias, las cotas obtenidas tanto con F2 como con F3, que ya son el valor óptimo o se desvían muy pocas unidades de él. Además, estos límites (u otros con menos de una unidad de diferencia con respecto a ellos) generalmente ya se alcanzan en el nodo raíz del árbol de enumeración. Obtener soluciones factibles óptimas o casi óptimas suele ser más exigente, aunque los resultados obtenidos son igualmente satisfactorios, particularmente los de F3, que resolvió con optimalidad probada todos los casos excepto dos. En total, sólo cinco de los 96 casos considerados consumieron más de una hora.

Siguiente: Comparación de F2 y Subir: Experimentos computacionales Anterior: Resultados numéricos para instancias