Algoritmo GRASP para la Planificación de la Asignación de amarraderos en puertos marítimos

Algoritmo GRASP para la Planificación de la Asignación de amarraderos en puertos marítimos Gisela W. Solano David S. Mauricio Glen D. Rodríguez Universidad Inca Garcilaso de la Vega, Facultad de Ingeniería de Sistemas, Cómputo y Telecomunicaciones Av. Bolívar 1848, Lima, Perú, Lima 21 [email protected] {davidmauricio,glenrodriguez}@uigv.edu.pe Abstract The scheduling problem appears frequently in industries’ manufacture and logistics, because it involves costs, time, demand and profitability. The goal of the assignment of berths in a maritime port is to support the business processes of the port in order to maximize profits and lower costs, meeting the demand and avoiding problems caused by excessive waiting time of ships in the harbour. In this paper, previous research related to maritime ports, airports and cargo trains have been used as reference, and a GRASP multi-objective method has been selected to solve the problem of assignment of berths in a certain moment of time and to scheduling the assignment in some period of time. Keywords: Scheduling of assignment of berths, GRASP, planning process, port operations, multi-objective optimization.

Resumen El problema de planeamiento es muy frecuente en el área de producción y logística de las industrias, porque involucra costos, tiempos, demanda y rentabilidad. La asignación de amarraderos en el puerto marítimo tiene por objetivo apoyar a los procesos de negocio portuario para maximizar utilidades y disminuir costos, atendiendo la demanda y evitando problemas de espera excesiva de las naves en bahía. En el presente trabajo se ha tomando como referencia otros trabajos en puertos marítimos, aeropuertos y trenes de carga, y se ha escogido atacar el problema con el método GRASP multi-objetivo para asignar amarraderos en un momento determinado y planificar la asignación a lo largo de un intervalo de tiempo. Palabras clave: Planificación de asignación de amarraderos, GRASP, proceso de planeación, operaciones portuarias, optimización multiobjetivo.

1

Introducción

La planificación destina recursos (equipos, capacidades, tiempo de procesamiento, costos, utilidades, etc.) de manera que se satisfagan objetivos especificados (numero de artículos a producir, minimizar los costos operativos de equipos, maximizar utilidades o rentabilidad). La teoría de planificación fue formalizada primero a mediados de los años cincuenta para maximizar la efectividad de los procesos de fabricación que estaban desarrollándose rápidamente. Los investigadores continuaron refinando la teoría de planificación y definiendo los muchos escenarios y las heurísticas que optimizan el rendimiento de un sistema en particular, hoy la teoría de planificación es un campo robusto y bien estudiado que es aplicado a muchos procesos industriales diariamente [2]. Los objetivos principales de planificación son la asignación y el secuenciamiento o scheduling [22]. La planificación de los recursos limitados para conseguir el mejor objetivo especificado es el resultado principal de los algoritmos de scheduling, en la que los trabajos deben

estar dispuestos para sacar el máximo provecho del tiempo disponible, los recursos, y las restricciones [14] [9]. En la teoría de planificación tradicional, los recursos son tela o máquinas que son consumidas en la producción del producto final. Los recursos tienen características con valores asociados que afectan la manera en que los recursos son usados (como las prioridades) [17]. Esas características de recurso son la capacidad, el tiempo de procesamiento, grados de degradación, los grados de reparación, y muchos otros que definen cómo puede ser consumido en la ejecución del trabajo. Para realizar una buena planificación se deben tomar en cuentas los requerimientos operativos (inputs y outputs) [18], las variables y datos de los diferentes escenarios que involucra poder realizar la planeación. Es importante decir que el modelo planteado para este caso es susceptible a cambios por factores endógenos o exógenos, por ejemplo, hay diferencias entre un puerto marítimo y uno lacustre de altura, y por alinearse con los cambios constituidos por el estado (leyes, marco regulatorio) [12] [21]. Para definir los objetivos de la planificación en este caso asignación de amarraderos se debe conocer los factores que involucran a la toma de decisiones en el área operativa, como se muestra en la figura 1, tomada de [18]. Las actividades de un administrador de puertos incluyen el remolque de naves al muelle, el servicio de atraque o amarradero, la carga y descarga, el almacenaje en los patios, etc. El problema que se atacará en este artículo es solamente el de la asignación de amarraderos o atracaderos a naves en un puerto marítimo y la planificación o scheduling de dicha asignación a lo largo de un período de tiempo. Dicha planificación se realiza en muchos casos por medios manuales, causando que las decisiones relativas a la asignación sean deficientes y se completen tarde. En este artículo, se usa un algoritmo GRASP (greedy randomized adaptive search procedure) construcción y multi-objetivo para la asignación y otro algoritmo GRASP para la planificación (scheduling). GRASP fue creado por Feo y Resende [10] para el problema de cubrimiento. plan de amarraderos barcos

grúas muelle

amarradero

amarradero Vehículos

plan de descarga

plan de carga

Plan de ruta contenedores, mercancía

grúas

grúas Patios Plan de patios (asignación de ubicación)

Figura 1. Operaciones y planificación en puertos marítimos. Adaptación de Koh et al [18] La estructura de este artículo es la siguiente: en la sección 2 se mencionaran varios métodos para planificación y se compararán con el GRASP; en la sección 3 se desarrolla el modelo formal del problema y el algoritmo GRASP construcción multi-objetivo propuesto para la asignación inicial de las naves a los amarraderos; en la sección 4 se explica el algoritmo GRASP propuesto para la planificación (asignación a lo largo del tiempo, en tiempos posteriores al tiempo inicial); en la sección 5 se presentan resultados numéricos y se hace un breve análisis de los mismos; y en la sección 6 se presentan las conclusiones.

2

Revisión de métodos para la planificación de infraestructura de transporte

El problema de asignación de amarraderos esta clasificado dentro de la categoría de problemas de optimización. Los problemas de optimización han sido estudiando por muchas décadas y han sido tema de mucha literatura importante con distintos métodos de solución ampliamente estudiados, entre ellos métodos

matemáticos y técnicas heurísticas y meta heurísticas siendo dentro de esta última donde se han desarrollado múltiples técnicas. Se sabe que el problema es de optimización y de clase NP-difícil [20] [24]. 2.1 Revisión de la literatura Cave at al [4] han presentado una solución a la planificación de procesos usando templado o recocido simulado. Los resultados obtenidos son buenos, pero el algoritmo es muy lento, demorando hora y media en una Pentium III. Díaz et al [8] ha realizado una revisión de métodos heurísticos y metaheurísticos, incluyendo la aplicación de algoritmos genéticos en la asignación de procesos, problema relacionado con el que se trata en este articulo. En Gao et al [13] se presenta un algoritmo genético híbrido y multi-objetivo para el planeamiento de tareas (múltiples tareas y múltiples máquinas), convirtiendo el multi-objetivo en mono-objetivo con sumas ponderadas, e hibridizando el algoritmo genético (que es bueno explorando el espacio total del problema para buscar óptimos globales) con uno de “bottleneck shifting” para mejorar la búsqueda de los óptimos locales; se obtienen mejores resultados que con el algoritmo genético puro. Debemos observar acá una analogía con los algoritmos GRASP, donde la fase construcción exploraría el gran espacio del problema y la fase mejoría lo aproxima al óptimo local. En Glover y Kochenberger [15] se revisaron diversas aplicaciones del GRASP, incluyendo en problemas de asignación. En Gomes et al [16], se presenta un problema de asignación resuelto con un GRASP reactivo (donde el valor del parámetro de relajación alfa es una variable estocástica, cuya distribución de probabilidad se decide experimentalmente) y se compara favorablemente contra el GRASP normal y un método de búsqueda local en calidad de soluciones (mejores o iguales) y en tiempo de ejecución (en promedio iguales). Hay otros dos métodos que también se usan para problemas de este tipo, pero no hay mucha información al respecto. Uno de ellos es el “scatter search” o búsqueda difusa que ha sido usado para la planificación de tareas [19] [1]. Otro es la búsqueda tabú, que se ha usado en planificación de tareas y es mejor que heurísticas simples [11] 2.2 Comparación de métodos En esta sub-sección se justifica la elección del método GRASP. GRASP es un método utilizado para solucionar problemas grandes y complejos pues alcanzan soluciones de alta calidad, con bajo esfuerzo computacional [23] [9]. GRASP es utilizado para la planificación de estaciones de los trenes y sus respectivas cargas en la ciudad de Boston [3], este método combinatorial GRASP es usado para la simulación de contenedores de terminales multimodales en EEUU [14]. A comparación de los métodos exactos [12] [25] [7] pretenden hallar un plan jerárquico único analizando todos los posibles ordenamientos de las tareas o procesos involucrados en la línea de producción (exploración exhaustiva), Sin embargo, una estrategia de búsqueda y ordenamiento que analice todas las combinaciones posibles es computacionalmente cara y sólo funciona para algunos tipos (tamaños) de instancia. A comparación de los métodos aproximados [10], por su parte, sí buscan resolver las variantes más complejas en las que interviene el comportamiento de tareas y máquinas, dichos métodos no analizan exhaustivamente todas las posibles combinaciones de patrones del problema, sino que más bien eligen los que cumplan determinados criterios. Obtienen finalmente soluciones lo suficientemente buenas para las instancias que resuelven, lo que justifica su uso. A comparación de la Búsqueda Tabú y el Templado (o recocido) Simulado, da como respuestas datos altamente confiables, pero el tiempo de procesamiento es lento [5] [6]. A comparación del algoritmo voraz o goloso, GRASP presenta mejores resultados (5.48% más de eficiencia) cuando se probó en un problema de programación de tareas en máquinas [26].

3

Algoritmo GRASP Construcción para la asignación

3.1 Variables Como resultado final se desea obtener las variables de decisión Xij considerando los costos, utilidades y las prioridades de la nave. Hay restricciones de tamaño de calado (la distancia vertical entre un punto de la línea de flotación y la línea base o quilla, con el espesor del casco incluido; en el caso del amarradero sería el calado máximo que entra limitado por la profundidad del agua) y eslora (el largo de una nave, desde la proa hasta la popa; en el caso del amarradero es la longitud asignada al mismo) que se resumen en la variable Dij (el valor es 1 si la nave i tiene calado y eslora menores o iguales al calado y eslora del amarradero j, 0 en caso contrario). Los parámetros y las variables de decisión consideradas son: Xij: Asignación de una nave en un amarradero ⎧1 Si se asigna la nave i en el amarradero j X ij = ⎨ Caso Contrario ⎩0

cij : Costo de la nave i en el amarradero j u ij : Utilidad de la nave i en el amarradero j

Dij : Demanda de la nave i en el amarradero j Pi : Prioridad de la nave i ⎧1 Si nave i cuenta con amarradero j Dij = ⎨ Caso Contrario ⎩0

eij : Tiempo de estadía de la nave i en el amarradero j n : Número de unidades de naves m : Número de unidades de amarraderos 3.2 Modelo formal En este modelo se asume que existe un número de amarraderos disponibles que serán cubiertos por un número de naves que cumplan las restricciones de calado y eslora, solo ingresa una nave a un amarradero y que un amarradero puede estar libre o ocupado por una nave, maximizando la utilidad, minimizando el costo operativo y maximizando la prioridad.

Maximizar

n

m

f 1 = ∑ ∑ u ij e i X ij

(1)

f 2 = ∑ ∑ (W − c ij ) ei X ij

(2)

i =1 j =1

Maximizar

n

m

i =1 j =1

Maximizar

n

f 3 = ∑ Pi (t ) i =1

m

∑ j =1

X ij

(3)

sujeto a: n

∑ i =1

m

∑ j =1

xij ≤ 1

xij ≤ Dij

X ij ∈ {0,1}

∀j = 1,..., m

(4)

∀i = 1,..., n

(5)

∀i, j

(6)

Las funciones (1), (2) y (3) corresponden respectivamente a los criterios de maximizar la utilidad, minimizar los costos operativos (minimizar la brecha entre un numero muy grande y el costo) y maximizar la prioridad. La relación (4) expresa que en un amarradero puede ingresar una nave o ninguna nave y la relación (5) expresa que la nave requiere un amarradero (que cumpla con las restricciones de calado y eslora). La restricción de integridad de la variable de decisión es dada en la relación (6).

Inicialmente se consideró que la prioridad en la función (3) debía ser una constante. Ese supuesto funcionaba bien en la asignación inicial de amarraderos (permaneciendo el resto constante, las naves con mayor prioridad tenían preferencia en la asignación inicial). Pero enn la planificación a lo largo del tiempo, una prioridad constante en la fórmula (3) no garantiza eso. Entonces se decidió que la prioridad debería ser una función decreciente del tiempo t (en horas), y se escogió una adaptación de la función sigmoidea:

Pi , 0 ⎧ ⎪ Pi (t ) = ⎨ ⎛ 1 ⎞ ⎪⎩ Pi , 0 ⎜⎝1 − 1 + e −(t −12 ) / 2 ⎟⎠

para t = 0 para t > 0

(7)

Se debe observar que este PPAA (Problema de Planificación de Asignación de Amarradero) corresponde a la programación 0-1 multi-objetivo. La solución de este modelo nos permitirá determinar la planificación de asignación de amarraderos nos permite maximizar utilidad (1), minimizar los costos operativos (2) y maximizar la prioridad (3) según sea el tipo de carga. 3.3 Esquema de solución del PPPA Para resolver el problema PPAA se ha considerado el esquema dado en la Figura 2, que consiste en dos fases. La primera fase consiste en transformar PPAA (problema multi-objetivo) a un problema monoobjetivo de sumas ponderadas PPAA-M, donde los pesos de la ponderación son establecidas por el decidor humano. La segunda fase, consiste en generar la solución del problema PPAA a través de un algoritmo (deseable aproximado); si la solución obtenida es satisfactoria el proceso termina, de lo contrario se regresa a la primera fase, para que el decisor humano establezca nuevas ponderaciones.

PPAA

Transformar

Establecer λ

PPAA -M

Algoritmo Solución S SI Fin

NO S es satisfactorio

Figura 2. Esquema de solución del PPAA (de multi-objetivo a mono-objetivo) El problema presentado en el escenario se puede transformar a un problema mono-objetivo aproximado de sumas ponderadas como:

Maximizar

λ1 f 1 (x ) + λ1 f 2 ( x ) + λ3 f 3 ( x )

(8)

s. a. n

∑

X ij ≤ 1

∑

X ij ≤ Dij

i =1 m

j =1

X ij ∈ {0,1}

∀j = 1,..., m ∀i = 1,..., n

∀i, j

Donde los parámetros de ponderación deberán verificar:

(9) (10)

(11)

λi ∈ [0,1] y

3

∑λ i =1

i

=1

(12)

3.4 Algoritmo GRASP construcción propuesto En el Algoritmo 1 (ver recuadro) se puede observar el pseudo código del GRASP construcción. En el paso 1 se muestra la lectura de las instancias las cuales contemplan los valores dato para el algoritmo propuesto, los cuales son Costos (C), Utilidades (U) de la nave i en un amarradero j, mientras que la prioridad es de la nave, al no existir exigencia de Prioridad (P) por monto de dinero ante un determinado producto (la prioridad es la necesidad de que el barco atraque ante un determinado tipo de producto que se tenga.), la Demanda (D) es una matriz que se establece previa al calculo y corresponde a las naves que cumplen con los valores de restricción (estos valores corresponden al calado y eslora de la nave para que pueda caber en el amarradero que se desee asignar) En el paso 2 se realiza la asignación de valores para el inicio del proceso, estos valores servirán, para que se realicen la asignación en el algoritmo correspondiente, cabe resaltar que tanto N y A indicaran las naves y los amarraderos respectivos. En el paso 3 se realiza la iteración del algoritmo Grasp para cada solución que se presente en el conjunto local (vecindad de solución) en donde se encontrará un valor aleatorio correspondiente (encontrándose en el paso 3.3) dentro de un rango de valores (encontrado en los pasos 3.1 y 3.2) hay que recalcar que dicho rango de valores deberá cumplir con que las naves y amarraderos, se encontraran activos para la presente iteración del algoritmo y el D (Demanda de la nave i en el amarradero j) contendrá las posibles naves y amarraderos que cumplan la restricción de calado y eslora, y el cual es dato previamente. En el paso 3.4 se realiza una verificación con la finalidad de concluir la iteración (encontrándose en el paso 3.4.1) realizar la obtención del valor y calculo de acumulados (que se encuentran en los pasos 3.4.2 y 3.4.3), esta parte es restrictiva al concepto del conjunto solución encontrado y buscara aleatoriamente la solución en el rango determinado. 1. 2.1 2.2 3. 3.1

Leer (C ,U , P, N , A, D, n, m);

X ij = 0 ∀i = 1,..., n, j = 1,..., m;

CT:=0; UT:=0; PT:=0; N := {1,..., n}; A:={1…..m} Mientras (Sw_RCLj) = True β max = Max{λ1 (u ij ) + λ2 (W − cij ) + λ3 ( Pi )} ∀i∈N , j∈A, Dij =1

3.2

β min = Min{λ1 (u ij ) + λ2 (W − cij ) + λ3 ( Pi )}∀i∈N , j∈A, D

3.3

RCL = {(i,j) i ∈ N , j ∈ A, D

3.4 3.4.1 3.4.2 3.4.3 3.4.4 3.5 4.

ij =1

ij

=1

: /βmax – α (βmax – βmin) ≤ λ1(uij ) + λ2(W − cij ) + λ3(Pi ) ≤ βmax }

Si (RCL ≠ 0) entonces (a,b):= Random (RCL) Xab = 1 , N := N – {a}, A := A – {b} UT:=UT + Uab ; CT:=CT + Cab ; PT:=PT + Pa Sino Sw_RCL= False Fin de Mientras Escribir (UT, CT, PT, X)

Algoritmo 1. Pseudo código del GRASP Construcción de asignación inicial Se debe indicar que en el estado actual de este proyecto de investigación aún no se ha formulado el correspondiente GRASP mejoría, pues el objetivo inicial es el de pasar del problema de la asignación en un momento determinado al scheduling de la asignación a lo largo del tiempo, como se verá en la siguiente sección.

4 Algoritmo de Planificación En el Algoritmo 2 (ver recuadro) se puede apreciar el pseudo código del algoritmo GRASP fase construcción para la planificación de la secuencia se asignaciones de amarraderos. Se usa como base el algoritmo de asignación tratado en la sección anterior. En el paso 1 se busca asignar los valores dato para el problema en el caso del paso del periodo t al t+1. Se necesitara algunas variables adicionales como son el periodo de llegada de la nave en la bahía (TN) y el tiempo de estadía de la nave por los valores a realizar en el amarradero (TE), tiempo adicional de existir el caso por problemas ante una operación (que se considera como dato dentro del Tiempo de estadía), también se indica un horizonte de trabajo (T), que mostrara el numero de periodos ha ser considerados en el sistema. En el paso 2, adicional a las variables asignadas en el apartado 1.4.1, se realizara un generación de matriz para el tiempo de permanencia de nave en el amarradero (TA) y el periodo en que se asigna la nave al amarradero (TT), estas dos variables son utilizadas para evaluar el uso del amarradero en el periodo en que se encuentre realizando dicho trabajo. En el paso 3 a diferencia de la sección anterior que busca generar un modelo iterativo de búsqueda de solución, lo que se hace es generar un modelo de iteración por el número de periodos en el horizonte establecidos, esto traerá como consecuencia que la búsqueda de solución queda dentro del proceso iterativo que busca en primera instancia establecer el conjunto de Naves (N) y de Amarraderos (A) para el periodo que le corresponda (encontrándose en el paso del 3.2) hay que notar que el Sw_RCL (paso 3.1) hay que inicializarlo para cada proceso, con la finalidad que pueda ser tomado en cuenta en el conjunto solución. Todo el problema solo se ve afectado en el total de horas utilizadas en el amarradero por lo tanto en el paso 3.3.4.4 se indica el tiempo asignado en el amarradero (TA) en base al tiempo asignado a la nave para su estadía (TE) y el periodo en que se realiza dicha asignación (TT) en base al periodo en que se encuentra t. 1. 2.1

Leer ( C , U , P, N , A, D, n, m, T ; TE , TN )

X ij = 0 ∀i = 1,..., n, j = 1,..., m; TA(j)=0 TT(j)=0

2.2 CT:=0; UT:=0; PT:=0; A:={1…..m} N:= 0 3 Desde t = 1 hasta T 3.1 Sw_RCL:= True 3.2 Desde i =1 to n 3.2.1 Si TN = t 3.2.1.1. Entonces N:= N + {i} 3.2.1.2. Desde j =1 to m 3.2.1.3. Si TT(j)+TA(j) = t 3.2.1.3.1. Entonces A:= A + {j} 3.2.1.4. Fin desde 3.2.3 Fin desde 3.3. Mientras (Sw_RCL) = True 3.3.1 β max = Max{λ1 (uij ) + λ2 (W − cij ) + λ3 ( pi )}

∀i∈N , j∈A, Dij =1

3.3.2

β min = Min{λ1 (uij ) + λ2 (W − cij ) + λ3 ( pi )}∀i∈N , j∈A,D =1

3.3.3

RCL = {(i,j) i ∈ N , j ∈ A, D

ij

ij

=1

: /βmax – α (βmax – βmin) ≤ λ1(uij ) + λ2 (W − cij ) + λ3 ( pi ) ≤ βmax }

3.3.4 Si (RCL ≠ 0) 3.3.4.1 entonces (a,b):= Random (RCL) 3.3.4.2 Xab := 1 , N := N – {a}, A := A – {b} 3.3.4.3 UT:=UT + Uab ; CT:=CT + Cab ; PT:=PT + Pa 3.3.4.4 TAj:= TEi; TTj:= t 3.3.4.5. Sino Sw_RCL= False 3.3.5 Fin de Mientras 3.5 Fin desde 4. Escribir (UT, CT, PT, X);

Algoritmo 2. Pseudo código del algoritmo de planificación

Hay que recalcar que el modelo de procesos basado en periodos, se da de adelante hacia atrás acumulando los valores de tiempo por cada proceso que se realiza. En resumen, se supone que en el momento inicial (periodo 1) todos los amarraderos están libres, en el tiempo 1 se asignan varias naves a un número igual de amarraderos por cierto período de tiempo. En la siguiente iteración (siguiente período) se vuelve a correr el algoritmo de asignación pero con varios amarraderos no disponibles, naves ya atendidas (fuera del problema) y posiblemente naves nuevas. Al inicio de cada iteración se debe chequear si cada amarradero esta libre, se ha liberado o sigue ocupado (3.2.1.2 hasta 3.2.1.4)

5 Resultados Numéricos Se ha efectuado una prueba con 50 naves y 13 amarraderos. En la tabla 1 se puede apreciar las características de las naves, que son datos aleatorios pero con valores dentro de los rangos comúnmente vistos en puertos peruanos. La demora es el tiempo estimado que se tardará un barco en estar anclado en el muelle; la prioridad es un valor que representa la importancia de atender pronto a un barco (por ejemplo, por que lleva carga perecible), cuanto mayor es el valor más prioridad; en la tabla aparece la prioridad inicial Pi,0 que se usa para calcular la prioridad en un tiempo arbitrario t según la ecuación (7). Nave Calado Eslora Costo Utilidad Prioridad i,0 Demora Nave Calado Eslora Costo Utilidad Prioridad i,0 Demora Nave Calado Eslora Costo Utilidad Prioridad i,0 Demora Nave Calado Eslora Costo Utilidad Prioridad i,0 Demora Nave Calado Eslora Costo Utilidad Prioridad i,0 Demora

1 33 180 200 100 90 5 11 32 181 214 114 98 11 21 31 184 240 105 89 10 31 31 192 246 69 110 9 41 32 183 344 91 124 7

2 32 175 250 90 100 7 12 29 186 324 132 87 4 22 32 170 328 130 146 4 32 29 180 222 122 85 7 42 30 176 261 132 142 6

3 35 190 210 80 110 8 13 30 180 281 114 96 8 23 28 176 326 116 121 4 33 32 173 245 133 112 7 43 29 179 319 90 136 11

4 32 185 300 70 120 10 14 33 171 241 143 122 7 24 30 193 276 88 132 10 34 30 180 335 121 131 11 44 31 177 215 144 78 11

5 31 184 202 85 120 9 15 28 179 185 147 99 10 25 30 198 213 75 87 10 35 29 177 266 148 80 10 45 29 170 192 115 121 4

6 30 175 340 115 85 7 16 34 179 293 110 105 7 26 30 170 291 110 94 8 36 35 210 286 81 95 11 46 32 181 266 113 129 10

7 33 190 210 140 130 6 17 35 183 284 132 86 10 27 32 174 331 119 144 4 37 28 179 222 146 85 11 47 35 187 283 75 124 4

Tabla 1. Datos de prueba: características de las naves

8 34 210 270 105 110 8 18 31 182 336 90 106 8 28 30 176 307 139 149 5 38 31 179 213 90 105 6 48 31 212 203 123 124 4

9 32 185 280 75 105 10 19 30 187 232 86 99 9 29 29 176 341 63 105 5 39 33 171 310 123 87 7 49 33 175 318 92 141 8

10 32 185 200 130 95 8 20 30 174 227 99 140 6 30 31 179 260 138 88 6 40 31 173 314 108 150 8 50 31 185 186 96 124 9

En la tabla 2 se encuentran las características básicas de los amarraderos. Cabe resaltar que los datos de amarraderos son reales, del puerto de Callao (Perú). Los pesos (lambdas) se fijaron en λ1 = 0.3, λ2 = 0.3, λ3 = 0.4. La constante W que se usa para convertir el problema de minimización de costo en uno de maximización es 500. Amarr. Calado Eslora

1 32 185

2 32 182.5

3 33 182.5

4 33 182.5

5 33 182.5

6 33 182.5

7 33 182.5

8 31 182.5

9 35 190

10 35 212

11 36 183

12 36 209

13 34 181

Tabla 2. Datos de prueba: características de los amarraderos Como alfa o variable de relajación se han probado los valores de 0.005, 0.025, 0.1, 0.25 y 0.5, como se ve en la tabla 3. Para cada valor de alfa, se ha corrido 10 veces un programa que en cada corrida construye 200 soluciones GRASP y memoriza la mejor como resultado final. La computadora donde se hicieron estas pruebas es una Pentium 4 de 2.80 MHz. En la tabla 3 se puede apreciar los resultados con respecto al tiempo de ejecución y el valor de la función mono-objetivo (8) para resolver el problema multi-objetivo. Se puede apreciar que en cuanto al tiempo de ejecución, no hay diferencias significativas y es muy probable que el programa pruebe los 200 GRASP construcción en menos de 11 minutos. Es de notar que se ha elegido corridas de 200 soluciones por que la solución debería lograrse en menos de 30 minutos (tiempo que permite replanificar de una hora a la siguiente y hacer correcciones a la replanificación incluso) y hay que dejar un margen de tiempo extra (asumimos 100% extra) para considerar la demora adicional cuando en el futuro próximo se incluya un GRASP mejoría en esta investigación. En cuanto a la calidad de las soluciones, los valores de alfa mayores brindan consistentemente soluciones mejores que los valores de alfa pequeños. Este hecho contrasta con muchas otras aplicaciones de GRASP, donde un alfa=0.005 es el sugerido. En este tipo de problemas, se debería escoger un alfa entre 0.25 y 0.5; el primero da soluciones algo inferiores pero con menos variabilidad, mientras que el segundo da mejores soluciones en promedio pero con mayor variabilidad. Además, el límite inferior en la calidad de soluciones es bastante parejo para ambos valores de alfa. Alfa 0.005 0.025 0.1 0.25 0.5

Tiempo promedio de ejecución (s) 627.715 629.812 627.708 628.621 619.772

Desv. Est. Tiempo de ejecución (s) 24.203 21.333 16.344 13.961 26.581

Promedio de las soluciones 6428.64865 6444.58541 6450.29106 6479.51517 6481.20518

Desv. Est. de las soluciones 13.59592 5.02186 3.18151 4.42211 7.76331

Mejor Solución

Peor Solución

6442.59901 6450.28650 6456.71629 6483.83880 6494.52391

6413.51090 6438.71446 6445.71638 6470.42497 6470.87701

Tabla 3. Resultados para distintos valores de alfa En la tabla 4 y en la figura 3 se muestra la mejor solución de todas las obtenidas, con alfa= 0.5 en un tiempo de procesamiento de 605.69 s. Se puede observar que al inicio (hasta asignar las primeras 33 naves, en las primeras 22 horas) se usan todos los amarraderos, pero posteriormente se usan menos amarraderos pues al final se dejan las naves muy grandes (menos amarraderos que cumplen las restricciones) y menos “rentables” (menores prioridades y/o utilidades, mayores costos).

6 Conclusiones y Recomendaciones El método GRASP presentado aquí apunta a resolver una parte importante de la planificación de actividades de un puerto, que es la planificación de amarraderos. Al ser la actividad que abarca desde el tiempo inicial (previo a la descarga) al final (posterior a la carga) de los procesos de una nave en puerto, es la limitante clave de las demás planificaciones (de grúas, de vehículos, de rutas, de patios). El método usa datos y restricciones reales como las medidas de calado y eslora de barcos y amarraderos, la demanda de los barcos, la prioridad de atención, los costos y las utilidades esperados, y el tiempo estimado que tardarán en el amarradero (aleatorios pero con valores realistas para cada barco). La asignación se realiza por un GRASP construcción y la planificación es una iteración de asignaciones a lo largo de los

períodos de tiempo desde el 1 al T. La planificación se puede rehacer en forma dinámica si las condiciones cambian (se puede re-planificar cuando ocurren sucesos inesperados como tardanza al cargar y descargar una nave, o retraso en la llegada a puerto), pues la planificación puede hacerse de nuevo desde un tiempo t, convirtiéndolo en el nuevo tiempo cero. Se “apresura” la asignación de barcos con carga urgente o perecible dentro del modelo disminuyendo el valor de la prioridad con el tiempo. Así se premia la asignación de barcos de mayor prioridad al inicio, pues se penaliza la solución si se dejan para después. El método es competitivo en tiempo de procesamiento comparado contra los trabajadores humanos del puerto, quienes en grupos grandes demoran no menos de 3 horas en decidir la planificación. En el futuro se espera incorporar los algoritmos GRASP mejoría. Además se desea modificar las utilidades y costos de la asignación de amarraderos a los barcos en función al área adyacente a cada amarradero para la carga y descarga, y a la distancia entre cada amarradero y el patio de almacenamiento del puerto. Así, a mayor área adyacente bajan los costos y aumentan la utilidad (más facilidad de maniobrar las grúas) y a mayor distancia más costo y menos utilidad (por el tiempo y el combustible). De esta forma la asignación resultante de este método también ayuda a una buena planificación de grúas y de carga / descarga. Nave Amarradero Hora entrada Hora salida Nave Amarradero Hora entrada Hora salida Nave Amarradero Hora entrada Hora salida Nave Amarradero Hora entrada Hora salida Nave Amarradero Hora entrada Hora salida

32 3 0 7 38 8 0 6 13 1 7 15 24 12 13 23 16 13 21 28

46 4 0 10 27 6 0 4 30 5 7 13 6 5 13 20 41 11 22 29

48 10 0 4 20 2 0 6 2 7 8 15 21 1 15 25 3 12 23 31

42 11 0 6 7 10 4 10 19 9 9 18 39 7 15 22 9 1 25 35

35 13 0 10 1 6 4 9 34 6 9 20 23 8 16 20 25 10 27 37

33 1 0 7 5 12 4 13 31 10 10 19 17 9 18 28 12 9 28 32

22 12 0 4 28 11 6 11 11 13 10 21 18 2 18 26 47 12 31 35

40 7 0 8 45 2 6 10 37 4 10 21 49 3 18 26 4 9 32 42

14 5 0 7 15 8 6 16 26 2 10 18 10 10 19 27 8 10 37 45

50 9 0 9 44 3 7 18 43 11 11 22 29 5 20 25 36 10 45 56

Tabla 4. Mejor solución del algoritmo de asignación y planificación, alfa= 0.5 Amarraderos

13 12 11 10 9 8 7 6 5 4 3 2 1

N 35 N 22

N 11 N5

N 42

N 28

N 48

N7

N 31

N1

N8

N 36

N4

N 39 N 34

N 30

N6

N 46

N 29

N 37

N 32

0

N 25 N 12

N 23

N2

N 14

N 33

N 10 N 17

N 15

N 40

N 47

N 41

N 19

N 38

N 20

N3

N 43

N 50

N 27

N 16

N 24

N 44 N 45

N 26

N 13 10

N 49 N 18 N 21

N9

20

30

40

50

tiempo

Figura 3. Mejor solución de planificación (scheduling) de los barcos y amarraderos del problema de prueba

Referencias [1] Blum, C., Roli, A. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys. Volume 35. Issue 3. Pag. 268 - 308. 2003 [2] Bruzzone, A.G., Giribone, P., Revertía, R. Operative requirements and advances for the new generation simulators in multimodal container terminals. Proceedings of the 1990 Winter Simulation Conference. [3] Carson, J.S. Using computer simulation for rapid transit operating strategies. Proceedings of the 1990 Winter Simulation Conference [4] Cave A., Nahavandi S., Kouzani A. Simulation optimization for process scheduling through simulated annealing. Proceedings of the 34th conference on Winter simulation, pag. 1909 - 1913, 2002 [5] Clark, S.J., Barnhart, C. Large-Scale Optimization Planning Methods for the Distribution-of United States Army Munitions. ELSEVIER Mathematical and Computer Modelling 39, pag. 697-714, 2004. [6] Cobos-Zaleta, N. Búsqueda Tabu para un problema de diseño de red multiproducto con capacidad finita en aristas de nodo. Tesis de maestría. Universidad Autónoma de Nuevo León. Junio 2004, en http://yalma.fime.uanl.mx/~pisis/ftp/pubs/thesis/msc/2003-dcz/tesis-2003-dcz.pdf [7] Delgado-Serna, C. Diseño de Metaheuristicos hibridos para problemas con rutas heterogenea: GRASP y Concentración Heurística. Rect@ (Revista Electrónica de Comunicaciones y Trabajos de ASEPUMA). Vol. Actas 6. No. 1, 1998, en http://www.uv.es/asepuma/VI/22.PDF [8] Díaz A., Glover F., Ghaziri H.M., González J.L., Laguna M., Moscato P. y Tseng F.T. (1996). Optimización Heurística y Redes Neurales en Dirección de Operaciones e Ingeniería. Editorial Paraninfo S.A., Madrid, España. [9] Dorigo, M., Maniezzo V., Colorni, A. The Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics - Part B, 26: 1, páginas 29-41, 1996. [10] Feo T.A., Resende M.G.C. A Probabilistic Heuristic for a computationally Difficult Set Covering Problem. Operations Research Letters, 8, pp. 67-71, 1989. [11] Finke, D.A., Medeiros, D.J., Traband, M.T.Shop scheduling using Tabu search and simulation. Proceedings of the 34th conference on Winter simulation. San Diego, California. Pag: 1013 - 1017. 2002 [12] Flor, L., De Filippi, E. Port Infrastructure: An Access Model for the Essential Facility. Maritime Economics & Logistics, 2003, 5, pag. 116–132 [13] Gao, J., Gen, M., Sun, L. A hybrid of genetic algorithm and bottleneck shifting for flexible job shop scheduling problem. Proceedings of the 8th annual conference on Genetic and evolutionary computation table of contents, Seattle. Pag. 1157 - 1164. 2006. [14] Gibson, R.R., Carpenter, B.C., Seeburger, S.P. A flexible port traffic planning model. Proceedings of the 1992 Winter Simulation Conference. [15] Glover, F.W., Kochenberger, G.A. Handbook of Metaheuristics. Kluwer Academic Publishers, Dordrecht, Paises Bajos, 2003. [16] Gomes, F.C., Pardalos, P., Oliveira, C.S., Resende, M. Reactive GRASP with path relinking for channel assignment in mobile phone networks. Proceedings of the 5th international workshop on Discrete algorithms and methods for mobile computing and communications table of contents. Rome, Italia. Pag. 60 - 67. 2001 [17] Holguin-Veras, J., Watson, C.M. On the development of a computer system to simulated port operation considering prorities. Proceedings of the 1996 Winter Simulation Conference. [18] Koh, P., Goh, J., Ng, H.S., Ng, H.C. Using simulation to preview plans of a container port operations. Proceedings of the 1994 Winter Simulation Conference. [19] Laguna, M., Martí, R., 2003. Scatter Search. Methodology and Implementations in C. Kluwer Academic Publishers. [20] Linares, P., Ramos, A., Sánchez, P., Sarabia, A., Victoriano, B. Modelos Matemáticos de

Optimización. Dpto. de Organización Industrial, Universidad Pontificia de Madrid. España. 2001, en http://www.gams.com/docs/contributed/modelado_en_gams.pdf [21] Luo, M.,Grigalunas T.A. A Spatial-Economic Multimodal Transportation Simulation Model For US Coastal Container Ports Maritime. Economics & Logistics, 2003, 5, pag. 158–178. 2003 [22] Miller, D.P. The Ro1e of Simulation in Planning. Proceedings of the 1987 Winter Simulation Conference. [23] Pérez-González, F. Una metodología de solución basada en la metaheurística Grasp para el problema de diseño de red con incertidumbre. Tesis de maestría. Universidad Autónoma de Nuevo León. Diciembre, 2005, en http://yalma.fime.uanl.mx/~pisis/ftp/pubs/thesis/msc/2006-fpg/tesis-fer-2006.pdf [24] Salazar, D. Evaluación de Métodos Evolutivos de Optimización Multiobjetivo de 2a Generación. Tesis de Maestría. Universidad Central de Venezuela. 2003, en http://neurona.ciens.ucv.ve/laboratorio/tesis/TG_03_DS.pdf [25] Stützle, T. Local Search Algorithms for Combinatorial Problems: Analysis, Improvements, and New Applications, volume 220 of DISKI. Infix, Sankt Augustin, Alemania, 1999. [26] Tupia, M., Mauricio, D. Un algoritmo voraz para resolver el problema de la programación de tareas dependientes en máquinas diferentes. Universidad Nacional Mayor de San Marcos. RISI 1(1), 9-18 (2004). Perú, 2004, en http://sisbib.unmsm.edu.pe/BibVirtualData/publicaciones/risi/N1_2004/a03.pdf