algoritmo de las hormigas

Un algoritmo híbrido basado en colonias de hormigas para la resolución de problemas de distribución en planta
orientados a procesos

UN ALGORITMO HÍBRIDO BASADO EN COLONIAS DE
HORMIGAS PARA LA RESOLUCIÓN DE PROBLEMAS
DE DISTRIBUCIÓN EN PLANTA ORIENTADOS A
PROCESOS

Ángel Cobo Ortega, Ana María Serrano Bedia
Universidad de Cantabria

RESUMEN
En este trabajo se presenta un algoritmohíbrido para resolver problemas de
distribución en planta, considerando la posibilidad de incluir restricciones de tipo
espacial o prioridades de cercanía. El algoritmo integra dos técnicas metaheurísticas:
por un lado los algoritmos basados en colonias de hormigas (ACO) y por otro lado un
algoritmo genético (AG) que permite mejorar el conjunto de soluciones obtenidas por
las hormigasartificiales. En el ACO, un conjunto de hormigas artificiales construyen,
de forma concurrente, un conjunto de posibles soluciones del problema por medio de
asignaciones parciales de secciones o talleres a áreas de la planta. En ese proceso de
asignación utilizan información heurística obtenida a partir de los datos del problema
(distancias entre áreas, flujos entre secciones, capacidades de lasáreas,...) y también la
información que las hormigas precedentes aportan sobre el grado de eficiencia de las
soluciones previamente obtenidas. En el trabajo se muestra la eficacia del algoritmo a
partir de una implementación usando el software Mathematica.

XIII Jornadas de ASEPUMA

1

Cobo Ortega, Angel y Serrano Bedia, Ana Mª

1. DISTRIBUCIÓN EN PLANTA ORIENTADA A PROCESOS
La distribución enplanta, vista como el proceso de determinar la organización
física de un sistema productivo, es una decisión de carácter estratégico en las empresas.
Una buena distribución de la planta productiva permite alcanzar ventajas competitivas
en cuanto a costes y mejorar la eficiencia del sistema productivo. En el caso de la
distribución en planta orientada a procesos, el objetivo es determinar laforma más
efectiva de localizar un conjunto de secciones o talleres en una serie de áreas en la
planta. En este caso la eficiencia se mide a partir del coste que supone el traslado de
materiales o personas entre las diferentes secciones. Este coste puede expresarse como
Coste =

n

n

∑∑

(1)

tij dij cij

i =1 j =1

donde n es el número de secciones; tij representa el número decargas o personas a
trasladar, durante un periodo de tiempo, desde la sección i a la sección j; dij es la
distancia entre dichas secciones; y cij representa el coste unitario del traslado que, sin
pérdida de generalidad, se puede suponer constante. El objetivo del problema es
minimizar la función (1) sujeta a diferentes restricciones de carácter espacial. La
existencia de restricciones, unidoal extraordinariamente elevado número de posibles
combinaciones, hace que este tipo de problemas sean muchas veces inabordables
mediante algoritmos óptimos; en tales caso se suele recurrir a técnicas heurísticas que
permitan obtener "buenas" soluciones en tiempos de respuesta razonables.

2. METAHEURÍSTICA
En las últimas décadas, muchos problemas de optimización combinatoria han
sidoabordados mediante un nuevo tipo de algoritmos llamados metaheurísticos.
Aunque no es fácil encontrar una definición comúnmente aceptada (Blum and Roli,
2003), se podría decir que una metaheurística es un proceso iterativo de generación que
guía a una heurística subordinada combinando de forma inteligente diferentes
conceptos para la exploración del espacio de búsqueda y usando estrategias deaprendizaje para estructurar la información con objeto de encontrar eficientemente
soluciones cercanas al óptimo (Osman and Laporte, 1996).
De acuerdo a una clasificación de Blum y Roli (2003), dentro de los algoritmos
metaheurísticos se distinguen los denominados métodos de trayectoria (búsqueda local,
2

XIII Jornadas de ASEPUMA

Un algoritmo híbrido basado en colonias de hormigas para...