Aplicação de um algoritmo genético para o problema do carteiro chinês em uma situação real de cobertura de arcos

O Problema do Carteiro Chines e um problema de otimizacao que objetiva cobrir todos os arcos de um grafo, minimizando a distância total percorrida. Pode ser aplicado a grafos nao-direcionados (ruas de mao dupla), direcionados (ruas de mao unica) ou mistos (algumas ruas de mao dupla e outras de mao unica). A busca pela rota e feita por algoritmos que geram solucoes aproximadas. Neste trabalho sera utilizado um Algoritmo Genetico para a construcao de rotas que se aproximem da solucao otima. O objetivo principal sera o de minimizar o custo do percurso da coleta e transporte dos residuos solidos urbanos, na cidade de Irati (PR), Brasil. O objetivo da modelagem foi a reducao dos gastos dos recursos publicos, gerando economia a Prefeitura da cidade. A aplicacao do algoritmo foi realizada em uma regiao central da cidade. Foram utilizados para mapeamento, dados reais cedidos por funcionarios da Prefeitura. Com o auxilio do aplicativo online Google Earth, foram obtidas as coordenadas geograficas dos vertices do grafo associado ao problema. Os resultados gerados pelo algoritmo genetico foram comparados com a solucao otima obtida atraves do software LINGO®12.0. Estes resultados se mostraram satisfatorios para a pequena instância do problema analisado. The Chinese Postman Problem is an optimization problem that aims to cover all the arcs of a graph, minimizing the total distance traveled. Can be applied to non-directed graphs (two-way streets), directed (one-way streets) or mixed (some two-way streets and other one-way).These arch for the route is done by algorithms that generate approximate solutions. In this work we used a genetic algorithm for the construction of routes that approximate the optimal solution. The main objective is to minimize the cost of the course of collection and transportation solid waste in the city of Irati (PR), Brazil. The application of the algorithm was performed in a downtown area. Were used formapping, real data courtesy of City Hall officials. With the help of the online application Google Earth, we obtained the geographical coordinates of the vertices of the graph associated with the problem. The results generated by the genetic algorithm were compared with the optimal solution obtained by LINGO ® 12.0 software. These results were satisfactory for this mall instance of problems analyzed.