Formulaciones de programación matemática para el SBTP

En esta sección desarrollamos varias formulaciones de programación matemática para el SBTP. Todos ellas utilizan variables de decisión binarias para determinar las decisiones estratégicas sobre los barcos que son atendidos/rechazados:

$z_k\in\{0, 1\}$ , $k\in K$ . $z_k=1 \iff$ se sirven los barcos de la clase .

Dado que la función objetivo depende de los tiempos de espera de los barcos atendidos, los cuales, a su vez, dependen de sus tiempos de inicio del servicio, definimos las siguientes variables de decisión adicionales:

: hora de inicio del servicio (o simplemente hora de inicio) del barco $i\in V$ .
: tiempo de espera del barco servido $i\in V$ . Este es el tiempo desde que el barco llega a la terminal hasta el comienzo de su servicio.

Usando las variables $z$ y $w$ la función objetivo se puede escribir como

$\begin{subequations}\begin{align} & \min \qquad g \sum\limits_{k\in K}C_k(1-z_k) + \sum\limits_{i\in V}w_i. && \end{align}\end{subequations}$

Las condiciones que regulan la relación entre las variables anteriores, y su relación con la duración del ciclo, dependen de si coinciden o no los ciclos de llegada, servicio y terminación de los buques atendidos involucrados. Por ejemplo, para barcos cuyos ciclos de llegada y servicio coinciden, se cumple que $s_i\geq a_i$ . Por el contrario, este límite inferior del valor de $s_i$ ya no es válido para los barcos cuyo servicio comienza en el siguiente ciclo después de su llegada, para los cuales $s_i\leq a_i-1$ debe cumplirse para garantizar que se respeta la duración del ciclo. Teniendo en cuenta que la duración del ciclo debe incluir los tiempos de servicio, la cota anterior se puede reforzar a $s_i\leq a_i-c_i$ . Se puede hacer una observación similar con respecto a los tiempos de espera. Mientras que la duración del ciclo impone ese $w_i\leq H-a_i-c_i$ para los barcos cuyos ciclos de llegada y servicio coinciden, para barcos con diferentes ciclos de llegada y servicio tenemos que $w_i\geq H-a_i$ .

La observación anterior indica que, para calcular con precisión los tiempos de espera derivados de planificaciones de servicio factibles, se necesita información adicional que indique si el ciclo de servicio de cada barco atendido coincide o no con su ciclo de llegada. Para ello, asociadas a cada $i\in V$ definimos dos nuevas variables binarias complementarias $x_i$ y $y_i$ , donde $x_i=1$ (y $y_i=0$ ) si y solo si el envío $i$ es atendido y su ciclo de servicio coincide con su ciclo de llegada, mientras que $x_i=0$ (y $y_i=1$ ) si y solo si el barco $i$ es atendido pero su ciclo de servicio es el ciclo siguiente a su ciclo de llegada. Por lo tanto,

$\begin{subequations}\begin{align} & \hspace{-0.6cm}\hspace{1.23cm}z_{k(i)}=x_i+y... ...ace{1.23cm}w_i=s_i-a_iz_{k(i)}+ H\, y_i && i\in V. \end{align}\end{subequations}$

Las restricciones () también garantizan que se respete la relación de los barcos de cada clase.

La transición entre ciclos consecutivos se controla mediante un conjunto adicional de variables binarias $f_i$ , $i\in V$ tal que $f_i=1$ si y sólo si el barco $i$ está atendido y su ciclo de servicio no coincide con su ciclo de terminación. Esto significa que el ciclo de servicio del barco $i$ coincide con su ciclo de llegada ( $x_i=1$ ) pero no coincide con su ciclo de terminación ( $s_i+c_i>H$ ). Además, con la ayuda de las variables $f_i$ , $i\in V$ también podemos relacionar las horas de salida de los barcos servidos con las variables $x$ e $y$ . Esto es:

$\begin{subequations}\begin{align} & \hspace{-0.6cm}\hspace{1.23cm}f_i\leq x_i &&... ...\leq (H-c_i)x_i+ c_i f_i+(a_i - c_i)y_i && i\in V. \end{align}\end{subequations}$

La figura x1-4001r1 ilustra la definición de las variables anteriores con un ejemplo con dos atraques, cinco barcos, clases de barco de un solo barco y un horizonte temporal $H=10$ . Los tiempos de llegada y servicio están dados por $a=(1, 1, 5, 9, 10)$ y $c=(3, 3, 3, 3, 2)$ , respectivamente. La figura muestra una solución en la que los barcos $\{1, 4, 5\}$ reciben servicio en el atraque 1 (en ese orden) y los barcos $\{2, 3\}$ en el atraque 2. Dado que todos los barcos reciben servicio, tenemos $z_k=1$ , $k\in\{1, \dots, 5\}$ . En la solución mostrada, los tiempos de inicio vienen dados por $s=(4, 1, 5, 9, 2)$ , con tiempos de espera asociados $w=(2, 0, 0, 0, 2)$ . Como $a_i\geq s_i$ de $i\in \{1, 2, 3, 4\}$ tenemos $x_1=x_2=x_3=x_4=1$ , ya que sus ciclos de servicio y llegada coinciden; en cambio, $s_5=1<a_5=9$ , lo que significa que el servicio para el 5 comienza en el siguiente ciclo al que llega, por lo que $y_5=1$ . Además $f_4=1$ ya que su ciclo de servicio no coincide con su ciclo de terminación.

**Figura:** Ejemplo de definición de variables con , y
$\includegraphics[width=1.\textwidth]{Ejemplo_variables.pdf}$

Para obtener el cronograma real de cada amarre y garantizar que el tiempo total de procesamiento de todos los barcos atendidos en el mismo atraque no exceda el horizonte de tiempo cíclico $H$ , definimos variables predecesoras adicionales, que, incluso si no dan una asignación explícita de barcos a los atracaderos, permiten determinar la secuencia de servicio en los atraques, ya que definen el orden en que los barcos son atendidos en cada ciclo e, implícitamente, definen grupos de barcos atendidos cíclicamente en el mismo atraque. En particular, sea:

$p_{ij}\in\{0, 1\}$ , $i,j\in V$ . Cuando $i\ne j$ , $p_{ij}=1 \iff$ los barcos y se procesan consecutivamente en el mismo muelle y el barco se sirve inmediatamente antes que el barco , permitiendo que haya un tiempo de inactividad en el atraque después de la terminación de . Cuando $p_{ij}=1$ diremos indistintamente que es el predecesor de , precede a , o sigue a . Cuando , $p_{ii}=1$ significa que el barco es su propio predecesor, es decir, se designa como el primer barco procesado en su atraque.

Las restricciones que regulan la secuencia de servicios de cada atraque son:

$\begin{subequations}\begin{align} & \hspace{-0.6cm}\hspace{1.23cm}\sum\limits_{j... ....6cm}\hspace{1.23cm}\sum_{i\in V} p_{ii}\leq b. && \end{align}\end{subequations}$

Las restricciones () imponen que cada barco servido tenga un predecesor único, mientras que () indican que cada barco servido puede preceder como máximo a un barco. El último barco atendido en cada atraque en cada ciclo no precederá a ningún otro barco. Las restricciones () también garantizan que todos los barcos de cada clase sean atendidos o rechazados. Las restricciones () imponen que no se utilicen más de $b$ atraques.

Tengase en cuenta que debido a la naturaleza cíclica de la plantilla de atraque, con las variables predecesoras anteriores puede haber múltiples representaciones de la plantilla de atraque asociadas con una secuencia determinada de barcos. La única diferencia entre todas las representaciones equivalentes es, en esencia, el barco de la secuencia que se designa como el primer barco procesado en el atraque. Cualquier barco atendido puede seleccionarse como el primer barco en su atraque y el período de tiempo en que comienza su servicio puede usarse como referencia para garantizar que la duración de la secuencia de todos los barcos atendidos en ese atraque no exceda la duración del ciclo $H$ . Por ejemplo, en el ejemplo de la Figura x1-4001r1 podríamos elegir $p_{11}=p_{41}=p_{54}=1$ , $p_{22}=p_{32}=1$ .

Definimos un conjunto final de variables de decisión asociadas a los momentos en los que tienen lugar algunos eventos:

: tiempo de finalización del buque $i\in V$ , es decir, el instante en que se ha completado el servicio al buque $i\in V$ . Este es el primer período de tiempo en el que el atraque ya está disponible para dar servicio al siguiente barco en la secuencia del atraque.
: tiempo de inactividad del atraque donde se sirve al buque $i\in V$ , inmediatamente antes de iniciar su servicio. Este es el tiempo transcurrido desde la finalización del servicio al predecesor de y la llegada a la terminal del barco .
: tiempo que ha estado ocupado el atraque donde se sirve al buque desde el inicio del servicio al primer buque en el atraque hasta que inicia el servicio al buque .

Junto con las restricciones que determinan los valores de las variables $e_i$ , los pares de barcos procesados consecutivamente en el mismo atraque deben satisfacer los siguientes conjuntos de restricciones:

$\begin{subequations}\begin{align} & \hspace{-0.6cm}\hspace{1.23cm}e_i=s_i+c_i z_... ...\geq o_j+c_j+v_i- H(1-p_{ij}) && i,j\in V, i\ne j. \end{align}\end{subequations}$

Las restricciones ()-() solo se activan para pares de barcos $i,j\in V$ , $i\ne j$ , tales que $p_{ij}=1$ . En particular, () establece que, si $i$ sigue a $j$ , entonces el servicio de $i$ no puede comenzar antes de la terminación del servicio de $j$ . De manera similar, () impone que, si $i$ sigue a $j$ , el tiempo de inactividad inmediatamente antes del servicio de $i$ debe ser al menos la diferencia entre el tiempo de inicio de $i$ y el tiempo de finalización de $j$ . Los tiempos de ocupación de buques consecutivos en un mismo atraque están regulados por ().

Las desigualdades () y () que aparecen a continuación establecen límites superiores para la ocupación y los tiempos de inactividad, respectivamente.

$\begin{subequations}\begin{align} & \hspace{-0.6cm}\hspace{1.23cm}v_i\leq a_ix_i... ...{1.23cm}o_i\leq (H-c_i)(z_{k(i)}-p_{ii}) && i\in V.\end{align}\end{subequations}$

Tenga en cuenta que los tiempos de ocupación se reducen a cero para los barcos que no reciben servicio, así como para los primeros barcos atendidos en cada atraque. Los límites superiores $H-c_i$ , $i\in V$ , garantizan que se respete la duración del ciclo. Los tiempos de inactividad distintos de cero solo pueden aparecer para barcos cuyos ciclos de llegada y servicio coincidan (de lo contrario, el barco será atendido tan pronto como el atraque esté disponible en el siguiente ciclo). Es decir, para cada atraque, implícitamente establecemos el inicio de su ciclo en la hora de inicio del primer barco atendido en el atraque.

Se puede comprobar fácilmente que en el ejemplo de la figura x1-4001r1, los valores de estas variables son $e=(7, 4, 8, 2, 4)$ , $v=(0, 0, 1, 1, 0)$ , $o=(0, 0, 4, 5, 8)$ .

Por lo tanto una formulación válida para el SBTP es:

$\begin{subequations} % latex2html id marker 7111 \begin{align} \text{F0}\qquad &... ...ace{1.23cm}s_i, w_i, e_i, v_i, o_i\ge 0 && i\in V. \end{align}\end{subequations}$

La formulación F0 se puede reforzar agregando límites inferiores y superiores más estrictos a los tiempos de inicio, tiempos de espera y tiempos de terminación (ver ()-() a continuación), que se reducen a cero para los barcos sin servicio:

$\begin{subequations}\begin{align} & \hspace{-0.6cm}\hspace{1.23cm}(H-a_i+1)y_i\l... ..._i\leq H (x_i-f_i)+ c_if_i+ a_i y_i && i\in V.%\\ \end{align}\end{subequations}$

Desafortunadamente, a pesar de los refuerzos anteriores (u otros de naturaleza similar), las cotas de programación lineal (LP) de la formulación F0 tienden a ser muy débiles, lo cual se debe al tipo M-grande de restricciones ()-(). Por esta razón, en las siguientes secciones desarrollaremos otras formulaciones en las que estas restricciones pueden eliminarse, a expensas de introducir conjuntos adicionales de variables de decisión binarias.

Subsecciones