Otimização de rotas utilizando abordagens heurísticas em um ambiente georreferenciado
Autor(es):
Silva, Bruno de Castro Honorato
Palavras Chaves:
Não informado
Ano de Publicação:
2013
Resumo:
Mediante ao anseio de organizações empresariais em minimizar os custos com transporte,
pesquisas sobre métodos que venham a otimizar o processo de roteirização têm sido
realizadas. O termo roteirização pode ser descrito como um processo de sequências de
paradas determinadas que um veículo deva percorrer, com o objetivo de atender pontos
dispersos geograficamente. Na literatura, o problema relacionado com roteirização mais
conhecido é o clássico Problema do Caixeiro Viajante (PCV). Neste trabalho, o PCV será
abordado por meio de métodos heurísticos propostos a partir de um estudo realizado sobre
métodos computacionais aplicados na resolução do problema. Ainda como consequência
deste estudo, desenvolveu-se também uma ferramenta computacional que pode dar suporte a
vários tipos de empresas que dependem da roteirização para distribuir seus produtos ou
serviços com custo mínimo de transporte, através da aplicação prática do PCV clássico
podendo atender outros tipos de restrições. Após analisar, desenvolver, implementar e validar
os métodos heurísticos propostos resolveu-se ambientá-los à ferramenta computacional sobre
uma perspectiva espacial, gerando um Ambiente Georreferenciado de Resolução, composto
por um Sistema de Informações Georreferenciadas (SIG) robusto, permitindo que instâncias
do PCV possam ser criadas e analisadas as suas resoluções com acompanhamento gráfico. Os
métodos de resolução proposto para o problema são bastante rápidos e fáceis de serem
implementados, adequando-se muito bem a parte prática do problema.
Palavras-chave: Otimização de rotas; Computação – métodos heurísticos; Sistema de
informações georreferenciadas; Problema do Caixeiro Viajante
Abstract:
Through the desire of business organizations to minimize transportation costs, research on
methods that will optimize the routing process has been conducted. The routing can be
described as a process of certain sequences of stops that a vehicle must traverse in order to
meet geographically scattered points. In the literature, the problem related to routing best
known is the classic Traveling Salesman Problem (TSP). In this work, the TSP will be
addressed through heuristic methods proposed from a study of computational methods applied
in solving the problem. As result of this study also was developed a computational tool used
in the support for the businesses deliver your products or services with minimum
transportation cost, through the practical application of classic TSP with other restrictions.
After analyze, develop, implement and validate the proposed heuristic methods was created a
Computational Environment on a spatial perspective, called Resolution Georeferenced
Environment, composed of a robust Georeferenced Information System (GIS), allowing
create TSP instances and analyze their resolutions with accompanying graphic. The proposed
heuristics are very fast and low cost computational, adapting itself very well to the practical
problem.
Silva, Bruno de Castro Honorato. Otimização de rotas utilizando abordagens heurísticas em um ambiente georreferenciado. 2013. 93 f. Dissertação (Mestrado Acadêmico ou Profissional em 2013) - Universidade Estadual do Ceará, , 2013. Disponível em: Acesso em: 21 de maio de 2024
Universidade Estadual do Ceará - UECE | Departamento de Tecnologia da Informação e Comunicação - DETIC
Política de Privacidade e Segurança Build 1
