Contando el número de barcos atendidos en un período de tiempo determinado

Una de las principales dificultades del SBTP es controlar de manera efectiva que el número de barcos atendidos simultáneamente en cualquier periodo de tiempo $t\in T=\{1, \dots , H\}$ no exceda el número disponible de atraques. Con el conjunto actual de variables de decisión, la limitación del número máximo de atraques disponibles sólo se controla mediante la restricción (), que cuenta el número total de “primeros barcos”. En esta sección introducimos un conjunto adicional de variables de decisión que nos permite obtener una expresión lineal para el número de barcos atendidos en cualquier período de tiempo.

Identifiquemos el conjunto de barcos atendidos cuyo estado es “en servicio” en un período de tiempo dado $t\in T$ . Este conjunto puede contener barcos cuyo ciclo de servicio coincida con el ciclo actual (es decir, $s_i\le t$ ) así como barcos cuyo servicio comenzó en el ciclo anterior al de $t$ (es decir, $t < s_i$ ). Denotamos respectivamente por ${Z^t}^=$ y ${Z^t}^-$ el conjunto índice de barcos de estas dos clases cuyo servicio permanece activo en el período de tiempo $t$ . En particular, ${Z^t}^=$ consta de los índices de todos los barcos servidos con $s_i\le t$ tales que $s_i+c_i-1\geq t$ , mientras que ${Z^t}^-$ consta de los índices de todos los barcos atendidos con $s_i> t$ cuyo servicio permanece activo en el período de tiempo $t$ del siguiente ciclo, es decir, $s_i+c_i-1-H \geq t$ . Si bien los índices del conjunto ${Z^t}^=$ solo pueden corresponder a barcos con $c_i\le t$ , solo los barcos con $c_i>t$ pueden aparecer en el conjunto ${Z^t}^-$ . Por lo tanto, teniendo en cuenta que $1\le s_i\leq H$ , los dos conjuntos anteriores están dados por ${Z^t}^==\{i\in V \mid c_i\le t$ y $s_i \in [t-c_i+1, \, t]\}$ , y ${Z^t}^-=\{i\in V \mid c_i>t$ y $s_i \in [t-c_i+ 1 + H, \, H]\}$ . En particular, cualquier barco atendido $i\in {Z^t}^=\cup {Z^t}^-$ seguirá siendo atendido en el período de tiempo $t$ , y el número total de barcos que están siendo procesados en un período de tiempo dado $t\in T$ es precisamente la cardinalidad del conjunto ${Z^t}^=\cup {Z^t}^-$ .

Desafortunadamente, no es posible expresar esta cardinalidad como una expresión lineal de las variables $s$ . Para superar esta limitación, a continuación introducimos un nuevo conjunto de variables de decisión binarias:

$h_{it}\in\{0, 1\}$ , $i\in V, t\in T=\{1, \dots , H\}$ . $h_{it}=1 \iff$ el servicio del barco comienza en el período de tiempo .

Es decir, $h_{it}=1 \, \iff \, s_i=t$ .

Con la ayuda de las variables $h$ podemos obtener expresiones lineales para $\vert{Z^t}^=\vert$ y $\vert{Z^t}^-\vert$ , es decir

$\displaystyle \vert{Z^t}^=\vert=\sum\limits_{ \substack{i\in V:\\ c_i\leq t}}\... ...m\limits_{\substack{i\in V:\\ c_i > t}}\,\,\sum\limits_{t'=t-c_i+1+H}^Hh_{it'}.$

Por lo tanto, el número total de barcos que se procesan en un período de tiempo determinado $t\in T$ se puede escribir como:

$\displaystyle \sum\limits_{ \substack{i\in V:\\ c_i\leq t}}\,\,\sum\limits_{t'... ...m\limits_{\substack{i\in V:\\ c_i > t}}\,\,\sum\limits_{t'=t-c_i+1+H}^Hh_{it'},$

por lo que el siguiente conjunto de restricciones es válido para el SBTP:

$\begin{subequations}\begin{align} \sum\limits_{ \substack{i\in V:\\ c_i\leq t}}\... ...um\limits_{t'=t-c_i+1+H}^Hh_{it'}\leq b && t\in T. \end{align}\end{subequations}$

Las restricciones que garantizan que las nuevas variables estén bien definidas y vinculadas a las variables $s$ son:

$\begin{subequations}\begin{align} & \hspace{-0.6cm}\hspace{1.23cm}\sum_{t\in T} ... ...m}s_i=\sum_{t\in T} t\; h_{it} && i\in V \tag{9c}. \end{align}\end{subequations}$

La relación entre las variables $h$ y las variables $x$ existentes es bastante directa:

$\begin{subequations}\begin{align} & \hspace{-0.6cm}\hspace{1.23cm}x_i=\sum_{t = a_i}^H h_{it} && i\in V, \end{align}\end{subequations}$

mientras que para relacionar las variables $h$

con las variables $y$

existentes, tenemos que observar que cuando el servicio a un barco $i\in V$ comienza en el ciclo siguiente a su ciclo de llegada (es decir, $y_i=1$

), entonces su hora de inicio debe ser algún período de tiempo menor o igual a $a_i-c_i$

, ya que de lo contrario el tiempo entre la llegada del barco y la terminación de su servicio excedería la duración del ciclo. Esto significa que

$\begin{subequations}\begin{align} & \hspace{-0.6cm}\hspace{1.23cm}y_i=\begin{cas... ...0 & i\in V \text{ s.t. } a_i-c_i\leq 0 \end{cases} \end{align}\end{subequations}$

Como se verá en la sección x1-130006, donde se muestran resultados numéricos de pruebas computacionales, introduciendo el nuevo conjunto de variables de decisión $h$ junto con el conjunto de restricciones ()-(), tiene un efecto notable sobre la calidad de las cotas LP asociadas con la formulación resultante (ver formulación F1 a continuación), que se vuelven extremadamente ajustadas.

$\begin{subequations} % latex2html id marker 7222 \begin{align} \text{F1}\qquad \... ... a_i-c_i\leq 0 \\ \end{cases}\tag{\ref{y-h-2}}\\ \end{align}\end{subequations}$