Localización y Distribución de Planta

...

De forma abstracta el problema puede enunciarse como: Dado un dominio D de área A con geometría conocida, desconocida o restringida, D(A), se persigue ubicar en él sin superposición, sin disgregación y con calidad geométrica un conjunto de m actividades de áreas ai, di(ai) de geometría irregular, fija o flexible, relacionadas entre sí con intensidades de relación (wij, rij) de modo que se optimice cierta función del sistema asociada a su geometría (forma), la operación y la relación(adyacencia).

[pic 10]

Se persigue minimizar, para un periodo de tiempo determinado, la anterior función multicriterio, donde wij el coste unitario de manutención entre las actividades i y j, por unidad de tiempo y de distancia, dij la distancia entre las actividades i y j, medida con la métrica adecuada, rij la relación de adyacencia especificada en la tabla relacional de actividades R(rij) para el par de actividades i y j, V(rij) es una función de valor de la relación y F(fij) la matriz de adyacencia o frontera del sistema.

La formulación cuantitativa clásica más simple de este problema es como un problema cuadrático de asignación (QAP), donde todas las actividades industriales se consideran iguales y cuadradas. Bajo este planteamiento monoárea de las actividades la planta industrial tiene una caracterización geométrica insuficiente lo que dificulta en general la adecuada representación y valoración de la distribución en planta de un proceso industrial de fabricación. En esencia el QAP es una formulación topológica propia de la teoría de grafos que no considera los aspectos geométricos fundamentales del problema real de la distribución en planta (FLP).

Para resolver las dificultades propias de la representación geométrica del modelo y las dificultades de resolución del QAP se han desarrollado diferentes modelos geométricos y aplicado diversas técnicas heurísticas y de optimización que permiten abordar problemas industriales reales con eficiencia y mejor grado de resolución. Los algoritmos de optimización basados en colonias de hormigas se han aplicado al problema de distribución en planta formulado como un problema cuadrático de asignación con todos los inconvenientes antes reseñados que esto conlleva.

- EL ALGORITMO DE COLONIAS DE HORMIGAS.

El algoritmo de colonias de hormigas se basa en el establecimiento de una analogía entre el procedimiento natural que utilizan las hormigas para encontrar y explotar una fuente de alimentos, basado en el rastro de feromona que dejan en su recorrido de búsqueda, y el proceso de optimización desarrollado. Así, cuando un conjunto de H hormigas salen del hormiguero en busca de alimento la trayectoria de cada una de ellas será aleatoria e iniciarán un proceso de búsqueda en el que cada hormiga irá dejando un rastro de feromona. La primera hormiga que encuentra alimento volverá al hormiguero siguiendo la traza que ha dejado lo que, además de permitirle regresar al punto de partida, reforzará la intensidad de la traza en ese recorrido exitoso. Cuando un nuevo conjunto de hormigas salga ahora del hormiguero la probabilidad de selección de una trayectoria es directamente proporcional a la intensidad de la traza, lo que permite la explotación de las fuentes de alimentos sin impedir, dado el carácter aleatorio de la selección del camino, la exploración de nuevas fuentes. La evaporación natural de la feromona también incide en la apertura de nuevas vías de exploración. El mecanismo de búsqueda de cada hormiga se basa en la información almacenada en la memoria colectiva del sistema grabada químicamente en el soporte físico del suelo, en la memoria a corto plazo o tabú que impide que una hormiga retorne por el mismo camino sin alimento y en el sistema de “sensorización” de cada hormiga que le permite hacer búsquedas en la vecindad y orientarse localmente. Estos tres elementos configuran la estructura del algoritmo. Un algoritmo de colonias de hormigas se configura a partir de un conjunto de H hormigas y de una sucesión de T etapas o pasos. En cada etapa de índice t, cada una de las H hormigas construye una solución s(t,k). Las hormigas construyen su solución asignando a cada posición j de s(t,k) una actividad i de modo que s(t,k,j)=i. Para una etapa t cada una de las hormigas en su proceso de construcción de la solución deja en la matriz de recorridos o de trazas (actividad, posición) un rastro de intensidad proporcional a la calidad de la solución obtenida. El incremento de traza se calcula:

[pic 11]

El incremento total de traza que dejan el conjunto de las H hormigas en una etapa t puede ponerse como:

[pic 12]

La evaporación es una operación de atenuación que permite nuevas exploraciones en el espacio de soluciones. Una evaporación nula explotaría en exceso la solución actual provocando convergencias prematuras. De este modo el total de la traza al final de una etapa t teniendo en cuenta la tasa de evaporación ρ puede ponerse como:

[pic 13]

En una etapa t, una hormiga k selecciona una actividad i para asignarla a una determinada posición j. La construcción de la solución se hace a partir de la probabilidad de que una hormiga k seleccione una actividad i para una posición j, p(t,k,i,j)=p(s(t,k,j)=i) que se determina a partir de las siguientes tres consideraciones:

- Una lista tabú constituida por el conjunto de actividades ya asignadas hasta la posición j-1 y que no son candidatas para la posición j. Esta lista tabú, incluida en el vector solución s(t,k) que construye la hormiga k constituye su memoria individual a corto plazo.

- La matriz de traza T(t,i,j) que es la información histórica del proceso modificada por la evaporación y constituye la memoria colectiva del sistema y que indica cual ha sido la mejor asignación a una determinada posición j hasta el paso t.

- Un criterio de máximo aprovechamiento o de búsqueda local por el que una hormiga k intenta seleccionar para la posición j la actividad i que potencialmente maximice el valor de la fracción de la solución construida (este criterio es similar al de la visibilidad utilizado en y la valoración es análoga a la presentada en CORELAP.

De este modo la probabilidad de que la hormiga k asigne la actividad i a la posición j en la etapa t viene definida por:

[pic 14]

Debiendo cumplirse que α+β = 1. Donde α es el coeficiente que muestra la ponderación asociada a la memoria colectiva