MÉTODOS

MULTI-ARRANQUE

Rodolfo 1535346

Perla 1449279

Sergio 1451948

¿QUÉ SON?

En los Métodos Multi-arranque se alternan una

fase de generación de soluciones con otra de

mejora de las mismas. El proceso se repite

hasta que se cumpla un criterio de parada.

Este esquema sencillo suministra un

procedimiento que combina adecuadamente

el poder de exploración de los métodos de

construcción con el poder de explotación de

los métodos de mejora.

COMO SURGIÓ EL MÉTODO

Debido al inconveniente de las Búsquedas locales

para suministrar soluciones cercanas al optimo, se

encontró que una manera de solventar el

inconveniente era el aplicar búsquedas locales

dese varias soluciones de partida, La repetición de

los procesos Generar Solución Inicial y Búsqueda

Local constituye el primer Método Multi-arranque

ALGORITMO DE MÉTODO MULTI-ARRANQUE

Mientras (Condición de parada) Fase de

Generación Construir una solución.

Fase de Búsqueda Aplicar un método de búsqueda

para mejorar la solución construida

Actualización Si la solución obtenida mejora a la

mejor almacenada, actualizarla.

Podemos hablar de dos fases en cada

paso i. En la primera, se construye una

solución xi y en la segunda se trata de

mejorar mediante la aplicación de un

método de búsqueda, obteniendo la

solución xi

(que eventualmente puede ser

igual a xi

)

EJEMPLO-STRIP PACKING PROBLEM

Pertenece a la categoría de problemas combinatorios de corte y empaquetado.

Colocación sobre determinados patrones de objetos de diferentes tamaños y formas sin superposicionarse.

Objetivo: minimizar el área desperdiciado o residuos

Clasificación:

-Bin Packing: Objetos han de ser colocados sobre patrones de tamaño fijo, minimizando el numero de patrones utilizados.

- Strip Packing: Patrón único, con anchura fija y altura indeterminada.

STRIP PACKING PROBLEM

Problema de optimización consiste en empaquetar un conjunto de rectángulos en una banda de anchura fija(w) y altura indeterminada.

Dichos rectángulos han de ser colocados de manera que la altura alcanzada sea la menor posible.

Datos de interés:

- Condición mínima: Uno de los lados de cada rectángulo tiene que tener longitud menor o igual a w.

- Los lados de los rectángulos han de estar paralelos a los ejes de la banda.

- Los rectángulos pueden o no ser rotados 90 grados.

ALGORITMO APLICANDO MULTI-ARRANQUE

Ordenación de las piezas(heurística).

Estrategía: BLF (Bottom- Left Fill).

Procedimiento de selección: LRC (Lista

Restringida de Candidatos)

Iteraciones.

ORDENACIÓN (HEURÍSTICA)

Los objetos fueron ordenados en orden decreciente

en función de cuatro heurísticas:

– Lado mayor.

– Perímetro.

– Área total.

– Ratio (LM/lm).

Algoritmo de

ordenación

(Ej: perímetro)

ESTRATEGIAS DE COLOCACIÓN

Estrategia BL: Cada rectángulo es situado en la

posición más profunda dentro de la banda

(strip) y seguidamente en la posición más a la

izquierda. Si es posible el proceso se repite

hasta llegar a una posición fija.

Estrategia BLF: Se comprueba primeramente si

cabe en un hueco situado a una profundidad

mayor que en la quedaría con la estrategia BF.

Hemos usado la estrategia común del Bottom Left

Fill

(BLF)

Estrategia Bottom-Left Estrategia Bottom-Left Fill

PROCEDIMIENTO DE SELECCIÓN: LRC

De la lista ordenada de objetos que quedan por

colocar en cada paso creamos una sublista (LRC):

– Elementos: aquellos con función heurística igual o

superior a un determinado valor.

– Valor: evaluación heurística media de los

elementos extremos que quedan sin colocar.

– Se va actualizando después de cada colocación.

PROCEDIMIENTO DE SELECCIÓN: LRC

1ª Pieza

Perímetro medio:22 Aleatoriedad

PROCEDIMIENTO DE SELECCIÓN: LRC

2ª Pieza

Perímetro medio:20 Aleatoriedad

ITERACIÓN

El proceso se reinicia después de la obtención decada solución, repitiéndose una serie de veces y

almacenado la mejor de las soluciones obtenidas

en todas la iteraciones.

SOLUCIÓN DE ALTA CALIDAD

LM lm Or. Inicial Pos. X Pos.Y

10 3 TRUE 1 1

14 4 FALSE 11 1

9 7 TRUE 1 4

6 3 TRUE 15 1

6 2 TRUE 15 4

6 5 TRUE 15 6

6 3 TRUE 1 11

6 4 TRUE 15 11

7 7 TRUE 1 14

10 3 FALSE 8 11

5 3 TRUE 11 15

5 5 TRUE 16 15

5 2 TRUE 11 18

5 2 TRUE 11 20

3 2 TRUE 16 20

2 2 TRUE 19 20

Áreas

interiores

de

desperdici

os

Altura

óptima

Áreas exteriores

de desperdicios

SOLUCIÓN ÓPTIMA

Altura

óptima

LM lm Or. Inicial Pos. X Pos. Y

14 4 TRUE 1 1

10 3 FALSE 15 1

5 5 TRUE 1 5

10 3 FALSE 18 1

7 7 TRUE 6 5

6 5 FALSE 1 10

6 4 TRUE 13 11

9 7 FALSE 6 12

6 2 FALSE 13 5

6 3 TRUE 13 15

5 3 TRUE 1 16

6 3 TRUE 13 18

5 2 FALSE 19 11

5 2 FALSE 19 16

3 2 TRUE 1 19

2 2 TRUE 4 19

RESULTADOS

CONCLUSIONES

Strip Packing Problem es un problema de interés y

de aplicación actual.

Los resultados obtenidos a partir de la aplicación

del algoritmo Multi-Arranque al SPP produce

resultados comparable a los obtenidos a partir de

otros procedimientos.

BIBLIOGRAFIA

http://gavab.es/ssi06/documentos/alfonsoFernande

z_Strip_III_02.pdf

http://gavab.escet.urjc.es/metaheuristicas/documen

tos/Tema05.pdf

http://www.uv.es/rmarti/paper/docs/multi1.pdf