Experimentos computacionales
Siguiente: Resultados numéricos para instancias Subir: Nuevas formulaciones y soluciones Anterior: Marco algorítmico para encontrar


Experimentos computacionales

Para estudiar el rendimiento empírico de las formulaciones introducidas en las secciones anteriores hemos llevado a cabo una serie de experimentos computacionales cuyos resultados numéricos se presentan y analizan en esta sección.

Todas las pruebas computacionales se han realizado en un DELL XPS 159550 Intel i7-6700HQ 2.6GHz con 16 GB de RAM, bajo Windows 10 Pro como sistema operativo. Todas las formulaciones han sido codificadas en Mosel 5.2.0 con Xpress Optimizer versión 36.01.03 utilizado como solucionador Xpress ().

Para los experimentos hemos utilizado el conjunto de 96 instancias de referencia SBTP generadas por los autores de Iris et al. (2018) basadas en una instancia prototípica de Imai et al. (2014), que utilizaron en sus experimentos computacionales. Estas instancias se clasifican según su número de barcos que hacen escala $n\in\{50, 70, 100, 150\}$, número de atraques $b\in\{4, 8, 12\}$, así como el siguientes características:

Cada instancia se identifica con una etiqueta “i_n_b_c_s”, donde $i$ es la etiqueta numérica asignada a la instancia en Iris et al. (2018), $n\in\{50, 70, 100, 150\}$ su número de barcos, $b\in\{4, 8, 12\}$ el número de atraques, $c\in\{A, E\}$ el tipo de composición y $s \in\{S, L\}$ el tipo de servicio. En todos los casos, el horizonte de planificación tiene una duración de 152 horas, que es una semana prototipo que se repetirá cíclicamente. El número de conexiones entre barcos nodriza/alimentador depende del tamaño de la instancia, aunque normalmente está entre el 10 y el 20% de todos los barcos están en un enlace nodriza-alimentador. Finalmente, la penalización por cada petición rechazada es $g=10,000$ (ver Iris et al. (2018) para más detalles). La tabla x1-13001r2 resume las características de las instancias. Las primeras tres columnas indican el número de atraques, $b$, la capacidad de servicio $B=b\times H$ general y el número $n$ de barcos que hacen escala, respectivamente. Las siguientes dos columnas indican si los tiempos de servicio son S/L y si la proporción de barcos pequeños/grandes/jumbo que hacen escala es A/E, respectivamente. La columna etiquetada Instancias indica el rango de etiquetas numéricas de las cuatro instancias de referencia con esos parámetros específicos, mientras que las columnas bajo $D=\sum_{i\in V}c_i$ y $R={D}/{B} $ dan los promedios, en esos cuatro casos, de la demanda general del servicio $D$ y la tasa de demanda, $R$, respectivamente. A continuación, el conjunto que consta de las cuatro instancias *_n_b_c_s que comparten los mismos valores de parámetros para $n$, $c$, $b$ y $s$ se denotará por $\mathcal{C} _{n\_b\_c\_s}$. En la tabla x1-13001r2 y el resto de esta sección, se presentan los resultados para los diferentes grupos que, para el mismo número de atraques y barcos que hacen escala, se ordenan por valor creciente de la tasa de demanda. Tenga en cuenta que esta agrupación no corresponde a valores crecientes de las etiquetas numéricas de las instancias, que siempre indicamos para poder identificar las instancias específicas a las que corresponden los resultados.

Observamos que, debido al altísimo valor de la penalización $g$, se puede demostrar que las soluciones óptimas para todas las instancias consideradas maximizan su capacidad de servicio. De hecho, el tiempo máximo de espera de cualquier instancia atendida es $w_i\le H$, por lo tanto, un límite superior muy aproximado del tiempo total de espera de los barcos atendidos en cualquier solución factible es $\sum_{i\in \overline V}w_i\le n\times H$, que para $n\le 150$ y $H=152$ es menor que la menor penalización posible correspondiente a rechazar un solo barco con tiempo de servicio de una sola unidad, $g=10.000$. Esto significa que si $S^*$ es la capacidad máxima de la instancia en términos del tiempo de servicio general de los barcos aceptados, entonces, en cualquier solución óptima, el tiempo de servicio general de los barcos aceptados será precisamente $S^*$. En otras palabras, en cualquier solución óptima, el tiempo total de servicio de los barcos rechazados es $\sum_{j\in V}c_j-S^*$, por lo que la penalización general para los barcos rechazados es una constante $P^*=g\times. \left(\sum_{j\in V}c_j-S^*\right)$. Tenga en cuenta finalmente que el valor de la capacidad máxima de servicio de una instancia determinada, $S^*$, se puede calcular fácilmente resolviendo un problema de empaquetado de contenedores (ver, por ejemplo. capítulo 8 en Martello and Toth, 1990) en el cual hay $b$ contenedores cada uno de ellos con capacidad $B$ y la demanda de los artículos es $c_i$, $i\in V$. Para cada caso, hemos calculado previamente el valor de su penalización $P^*$; la última columna de la tabla x1-13001r2 proporciona valores promedio de $P^*$ para las diferentes clases de instancia.


Tabla: Resumen de características de las instancias
$b$ $B=H\times b$ $n$ L/S A/E Instances $D=\sum_{i\in V}c_i$ $R={D}/{B} $ $P^*$
4 608 50 S A 1-4   $\,\,\quad$341 .50 0.56 0
E 5-8 399 .75 0.66 0
L A 13-16 551 .00 0.91 1367500
E 9-12 634 .50 1.04 2562500
70 S A 71-20 464 .00 0.76 0
E 21-24 559 .25 0.92 0
L A 29-32 744 .75 1.22 0
E 25-28 864 .25 1.42 265000
100 S A 33-36 676 .25 1.11 682500
E 37-40 810 .50 1.33 2025000
L A 45-48 1067 .50 1.76 4595000
E 41-44 1195 .25 1.97 5872500
8 1216 70 S A 61-64 396 .00 0.33 0
E 57-60 487 .25 0.40 0
L A 49-52 784 .50 0.65 0
E 53-56 919 .50 0.76 0
100 S A 65-68 581 .50 0.48 0
E 77-80 700 .25 0.58 0
L A 69-72 1016 .25 0.84 0
E 73-76 1234 .75 1.02 202500
12 1824 150 S A 93-96 865 .25 0.47 0
E 81-84 1054 .00 0.58 0
L A 89-92 1492 .75 0.82 0
E 85-88 1752 .75 0.96 0


Subsecciones
Siguiente: Resultados numéricos para instancias Subir: Nuevas formulaciones y soluciones Anterior: Marco algorítmico para encontrar