ALGORITMOS HEURÍSTICOS CONSTRUTIVOS APLICADOS AO PROBLEMA DO CAIXEIRO VIAJANTE PARA A DEFINIÇÃO DE ROTAS OTIMIZADAS

Autores

  • Gabriel Altafini Neves da Silva UNOESTE
  • Francisco Assis da Silva UNOESTE
  • Daniela Tereza Ascencio Russi UNOESTE
  • Mário Augusto Pazoti UNOESTE
  • Robson Augusto Siscoutto FIPP/UNOESTE

Palavras-chave:

Problema do Caixeiro Viajante, Algoritmos heurísticos construtivos, Otimização de rotas

Resumo

Definir uma rota otimizada, por exemplo, para transporte de cargas com vários pontos de entrega a serem percorridos sem planejamento prévio, pode acarretar um alto custo e tempo demasiado. Este problema pode ser abordado como o Problema do Caixeiro Viajante, que consiste em estabelecer uma única rota que passe em cada vértice de um percurso uma única vez, retornando ao vértice inicial no final do percurso de maneira que o custo seja mínimo. Este trabalho está focado em analisar os algoritmos heurísticos construtivos para resolver o Problema do Caixeiro Viajante, que constroem uma rota através de um conjunto inicial de vértices e modificam esse conjunto utilizando um critério de escolha a cada iteração. Os algoritmos heurísticos utilizados para a otimização de rotas e avaliados foram: vizinho mais próximo, inserção do mais distante, inserção do mais rápido, inserção do mais próximo. Através de um aplicativo móvel definido e implementado neste trabalho, foram obtidas as coordenadas geográficas para os vértices das rotas utilizadas nos experimentos realizados. Os resultados obtidos de cada algoritmo foram comparados entre si para a obtenção do melhor algoritmo na determinação de rota otimizada. A partir dos resultados, observou-se a vantagem do uso do algoritmo de inserção do mais distante.

Downloads

Não há dados estatísticos.

Biografia do Autor

Robson Augusto Siscoutto, FIPP/UNOESTE

Possui graduação em Bacharelado em Ciência da Computação pela Universidade do Oeste Paulista (1994), mestrado em Ciências da Computação e Matemática Computacional pela Universidade de São Paulo (1997) e doutorado em Engenharia da Computação e Sistemas Digitais pela Universidade de São Paulo (2003). Atualmente é professor titular da Faculdade de Informatica de Presidente Prudente da Universidade do Oeste Paulista - Unoeste. Realiza suas pesquisas na área de Realidade Virtual e Aumentada, atuando principalmente nos seguintes temas: realidade virtual, Realidade Aumentada - Artoolkit e Flartoolkit, Redes de Computadores, Analise Orientado a Objetos. Publicou diversos artigos na área bem com escreveu diversos capitulos de livros.

Publicado

2013-11-22

Como Citar

Silva, G. A. N. da, Silva, F. A. da, Russi, D. T. A., Pazoti, M. A., & Siscoutto, R. A. (2013). ALGORITMOS HEURÍSTICOS CONSTRUTIVOS APLICADOS AO PROBLEMA DO CAIXEIRO VIAJANTE PARA A DEFINIÇÃO DE ROTAS OTIMIZADAS. Colloquium Exactarum. ISSN: 2178-8332, 5(2), 30-46. Recuperado de http://revistas.unoeste.br/index.php/ce/article/view/939

Edição

Seção

Artigos Originais

##plugins.generic.recommendByAuthor.heading##

1 2 3 4 5 6 > >>