Aplicação e análise de alguns procedimentos de contrução de rota para o problema do caixeiro viajante
O transporte, em geral, absorve em média a porcentagem mais elevada de custos do que qualquer outra atividade logística. Por isso, muitas empresas estão repensando seus processos para redução dos mesmos. A otimização da distribuição de produtos é um problema estudado há muito tempo por pesquisadores...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | Spanish |
| Published: |
Universidad del Bío-Bío
2012-04-01
|
| Series: | Ingenieria Industrial |
| Subjects: | |
| Online Access: | http://revistas.ubiobio.cl/index.php/RI/article/view/32 |
| _version_ | 1811299367735263232 |
|---|---|
| author | Paula Francis Benevides Flavia Konowalenko Deise Maria Bertholdi Costa Luiz Fernando Nunes Angela Olandoski Barboza |
| author_facet | Paula Francis Benevides Flavia Konowalenko Deise Maria Bertholdi Costa Luiz Fernando Nunes Angela Olandoski Barboza |
| author_sort | Paula Francis Benevides |
| collection | DOAJ |
| description | O transporte, em geral, absorve em média a porcentagem mais elevada de custos do que qualquer outra atividade logística. Por isso, muitas empresas estão repensando seus processos para redução dos mesmos. A otimização da distribuição de produtos é um problema estudado há muito tempo por pesquisadores de diversas áreas. Este tipo de problema é classificado como de otimização combinatória. Dentre as modelagens podem ser citados o Problema do Caixeiro Viajante (PCV) e o Problema de Roteamento de Veículos (PRV). Estes têm por objetivo encontrar o menor caminho conectando-seNlugares de destino. O presente trabalho visa analisar e comparar, em termos de desempenho computacional e qualidade das soluções obtidas, as principais heurísticas de construção de rotas, além de um Algoritmo Genético para o PCV. Também aplicou-se o algoritmo 2-opt para melhoria das rotas geradas. Foram utilizados dados reais de uma distribuidora de produtos em uma determinada região da cidade de Curitiba (PR), Brasil. As coordenadas geográficas dos pontos de visitação foram extraídas do aplicativo online Google Earth, as quais foramconvertidas em coordenadas cartesianas, para posterior aplicação dos algoritmos utilizados. Os resultados obtidos foram comparados com as rotas reais que estão sendo utilizadas por um determinado representante da referida distribuidora.
The transport in general, absorb on average the highest percentage of costs than any other logistics activities. Therefore,many companies are rethinking their processes to reduce them. The optimization of product distribution is a much studied problem time by researchers from several areas. This type of problem is classified as combinatorial optimization. Among the modeling can be cited the Traveling Salesman Problem (TSP) and the problem of Vehicle Routing (PRV). These, aims to find the lowest path connecting N places of destination. The present work analyze and compare, in terms of computational performance and quality of solutions, the main route construction heuristics, and a genetic algorithm for the TSP. We also applied the algorithm 2-opt to improve the routes generated. We used real data a distributor of products in a certain region of the city of Curitiba (PR), Brazil. The geographical coordinates of places to visit were taken from the online application Google Earth, which were converted to Cartesian coordinates for application of algorithms used. The results were compared with the actual routes being used by a particular representative distributor of that. |
| first_indexed | 2024-04-13T06:35:01Z |
| format | Article |
| id | doaj.art-d308643c606243188ffaf01e984efb42 |
| institution | Directory Open Access Journal |
| issn | 0717-9103 0718-8307 |
| language | Spanish |
| last_indexed | 2024-04-13T06:35:01Z |
| publishDate | 2012-04-01 |
| publisher | Universidad del Bío-Bío |
| record_format | Article |
| series | Ingenieria Industrial |
| spelling | doaj.art-d308643c606243188ffaf01e984efb422022-12-22T02:57:58ZspaUniversidad del Bío-BíoIngenieria Industrial0717-91030718-83072012-04-01111Aplicação e análise de alguns procedimentos de contrução de rota para o problema do caixeiro viajantePaula Francis Benevides0Flavia Konowalenko1Deise Maria Bertholdi Costa2Luiz Fernando Nunes3Angela Olandoski Barboza4Dpto. de Matemática, Universidade Tecnológica Federal do Paraná - UTFPR. Curitiba, Paraná. Brasil.Programa de Métodos Numéricos em Engenharia. Universidade Federal do Paraná. Centro Politécnico, Jardim das Americas, Curitiba, Paraná.Programa de Métodos Numéricos em Engenharia. Universidade Federal do Paraná. Centro Politécnico, Jardim das Americas, Curitiba, Paraná.Dpto. de Matemática, Universidade Tecnológica Federal do Paraná - UTFPR. Curitiba, Paraná. Brasil.Dpto. de Matemática, Universidade Tecnológica Federal do Paraná - UTFPR. Curitiba, Paraná. Brasil.O transporte, em geral, absorve em média a porcentagem mais elevada de custos do que qualquer outra atividade logística. Por isso, muitas empresas estão repensando seus processos para redução dos mesmos. A otimização da distribuição de produtos é um problema estudado há muito tempo por pesquisadores de diversas áreas. Este tipo de problema é classificado como de otimização combinatória. Dentre as modelagens podem ser citados o Problema do Caixeiro Viajante (PCV) e o Problema de Roteamento de Veículos (PRV). Estes têm por objetivo encontrar o menor caminho conectando-seNlugares de destino. O presente trabalho visa analisar e comparar, em termos de desempenho computacional e qualidade das soluções obtidas, as principais heurísticas de construção de rotas, além de um Algoritmo Genético para o PCV. Também aplicou-se o algoritmo 2-opt para melhoria das rotas geradas. Foram utilizados dados reais de uma distribuidora de produtos em uma determinada região da cidade de Curitiba (PR), Brasil. As coordenadas geográficas dos pontos de visitação foram extraídas do aplicativo online Google Earth, as quais foramconvertidas em coordenadas cartesianas, para posterior aplicação dos algoritmos utilizados. Os resultados obtidos foram comparados com as rotas reais que estão sendo utilizadas por um determinado representante da referida distribuidora. The transport in general, absorb on average the highest percentage of costs than any other logistics activities. Therefore,many companies are rethinking their processes to reduce them. The optimization of product distribution is a much studied problem time by researchers from several areas. This type of problem is classified as combinatorial optimization. Among the modeling can be cited the Traveling Salesman Problem (TSP) and the problem of Vehicle Routing (PRV). These, aims to find the lowest path connecting N places of destination. The present work analyze and compare, in terms of computational performance and quality of solutions, the main route construction heuristics, and a genetic algorithm for the TSP. We also applied the algorithm 2-opt to improve the routes generated. We used real data a distributor of products in a certain region of the city of Curitiba (PR), Brazil. The geographical coordinates of places to visit were taken from the online application Google Earth, which were converted to Cartesian coordinates for application of algorithms used. The results were compared with the actual routes being used by a particular representative distributor of that.http://revistas.ubiobio.cl/index.php/RI/article/view/32Problema do Caixeiro ViajanteProblemas de Roteamento de VeículosHeurísticasAlgoritmo Genéticos. |
| spellingShingle | Paula Francis Benevides Flavia Konowalenko Deise Maria Bertholdi Costa Luiz Fernando Nunes Angela Olandoski Barboza Aplicação e análise de alguns procedimentos de contrução de rota para o problema do caixeiro viajante Ingenieria Industrial Problema do Caixeiro Viajante Problemas de Roteamento de Veículos Heurísticas Algoritmo Genéticos. |
| title | Aplicação e análise de alguns procedimentos de contrução de rota para o problema do caixeiro viajante |
| title_full | Aplicação e análise de alguns procedimentos de contrução de rota para o problema do caixeiro viajante |
| title_fullStr | Aplicação e análise de alguns procedimentos de contrução de rota para o problema do caixeiro viajante |
| title_full_unstemmed | Aplicação e análise de alguns procedimentos de contrução de rota para o problema do caixeiro viajante |
| title_short | Aplicação e análise de alguns procedimentos de contrução de rota para o problema do caixeiro viajante |
| title_sort | aplicacao e analise de alguns procedimentos de contrucao de rota para o problema do caixeiro viajante |
| topic | Problema do Caixeiro Viajante Problemas de Roteamento de Veículos Heurísticas Algoritmo Genéticos. |
| url | http://revistas.ubiobio.cl/index.php/RI/article/view/32 |
| work_keys_str_mv | AT paulafrancisbenevides aplicacaoeanalisedealgunsprocedimentosdecontrucaoderotaparaoproblemadocaixeiroviajante AT flaviakonowalenko aplicacaoeanalisedealgunsprocedimentosdecontrucaoderotaparaoproblemadocaixeiroviajante AT deisemariabertholdicosta aplicacaoeanalisedealgunsprocedimentosdecontrucaoderotaparaoproblemadocaixeiroviajante AT luizfernandonunes aplicacaoeanalisedealgunsprocedimentosdecontrucaoderotaparaoproblemadocaixeiroviajante AT angelaolandoskibarboza aplicacaoeanalisedealgunsprocedimentosdecontrucaoderotaparaoproblemadocaixeiroviajante |