Algoritmo Colonia Abelhas Clusteriza O 1

ALGORITMO DE COLÔNIA ARTIFICIAL DE ABELHAS PARA UM
PROBLEMA DE CLUSTERIZAÇÃO CAPACITADO
Luiz Augusto Canito Gallego de Andrade
Programa de Mestrado em Engenharia de Sistemas Logísticos – Escola Politécnica da USP [e-mail] Cláudio Barbieri da Cunha
Programa de Mestrado em Engenharia de Sistemas Logísticos – Escola Politécnica da USP
Av. Professor Almeida Prado, Travessa 2, nº 83 – São Paulo, SP, Brasil [e-mail] RESUMO

Este artigo trata de um algoritmo de Colônia de Abelhas baseado no comportamento de busca de alimentos desses animais, para encontrar boas soluções para um problema de clusterização capacitado que pode ser modelado como um problema de p-medianas capacitado. Este problema pode ser definido como encontrar o melhor agrupamento de pontos, caracterizados pelas suas posições e demandas, em um número pré-definido de conjuntos com uma dada capacidade. Esse problema apresenta muitas aplicações práticas, dentre as quais podem ser citadas: agrupamento de clientes em centros de distribuição, procedimentos estatísticos de agrupamento de dados, etapas iniciais de problemas de roteirização. O problema possui ordem de dificuldade não polinomial, fazendo que a sua solução até a otimalidade seja inviável em instâncias reais, por isso o algoritmo foi elaborado. Os resultados de testes foram comparados com outros resultados da literatura e uma avaliação crítica da aplicação foi feita.

ABSTRACT
In this article we propose an Artificial Bee Colony Algorithm, inspired on beehives’ foraging behavior to solve a capacitated clustering problem that can be modeled as a capacitated p-median problem.
This problem can be defined as follows: given a set of points, each of them with known coordinates and demand, partition this set into a predefined number p of clusters, each one defined by its median point, such as the allocation cost is minimal, and no cluster exceeds its capacity. There are many practical applications of this problem, such as defining