[pt] 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. / [en] 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.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:9822 |
| Date | 25 April 2007 |
| Creators | RAFAEL LORENZO SANTOS |
| Contributors | JOSE EUGENIO LEAL |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.011 seconds