UMA APLICAÇÃO DE ALGORITMOS DE COLÔNIAS DE FORMIGAS EM PROBLEMAS DE ROTEIRIZAÇÃO DE VEÍCULOS COM JANELAS DE TEMPO

Muitos avanços da ciência foram obtidos a partir da observação da natureza. Milênios de seleção natural e evolução fizeram com que certos seres vivos desenvolvessem habilidades e características realmente notáveis, e que ainda hoje surpreendem pela sua complexidade e adaptabilidade. Alguns ramos da ciência fazem uso constante da observação intensiva dessas características, na tentativa de reproduzi-las em um ambiente controlado, com o objetivo de desenvolver métodos e ferramentas nelas baseados. Exemplos de métodos desenvolvidos dessa forma são os algoritmos de colônias de formigas. Sistemas de colônias de formigas (Ant Colony Systems - ACS) são modelos matemáticos baseados no comportamento de formigas quando imersas em colônias de indivíduos semelhantes. Formigas são indivíduos simples, porém capazes de interagir entre si, obtendo muitos benefícios desta prática. Estes modelos são muito úteis na resolução de grandes problemas de otimização combinatória, geralmente muito complexos para serem resolvidos por métodos exatos de otimização e representam um incipiente e importante campo de estudos da engenharia de produção. Este trabalho se propõe a descrever alguns algoritmos de colônias de formigas, utilizados em problemas de otimização combinatória/discreta. Particularmente, o foco do trabalho será na aplicação destes algoritmos no problema de roteirização de veículos com janelas de tempo. Uma forma de implementação do algoritmo no ambiente Matlab será proposta e testada em problemas padrão usados como benchmarking na literatura.Many advances in science were achieved from the observation of nature. Thousands of years of natural selection and evolution made certain living beings develop notable abilities and characteristics, that still nowadays surprise us with their complexity and adaptability. Some fields of science make constant use of intensive observation of these characteristics, in order to reproduce them in a controlled environment, with the objective of developping methods and tools based on them. Examples of methods developped this way are ant colony algorithms. Ant Colony Systems are mathematical models based on the behavior of ants when immersed in colonies of likely individuals. Ants are simple individuals, however capable of interacting with each other, obtaining benefits from this practice. These models are very useful in solving large combinatory optimization problems, usually too complex to be solved by exact optimization methods, and represent an important and incipient field of study in production engineering. This work aims to describe some ant colony algorithms, used in combinatory/discrete optimization problems. Particularly, the focus of this work will be in the application of these algorithms to the vehicle routing problem with time windows. A form of implementation of the algorithm in Matlab environment will be proposed and tested in standard problems used as benchmarking in the literature