Uma solução heurística para o problema do carteiro chinês num grafo misto com aplicação à distribuição de bens e serviços públicos.

Neste trabalho sao estabelecidos variantes de algoritmos heuristicos de Edmonds e Johnson e de Frederickson, para o problema do carteiro chines num grafo misto. Estas variantes podem ser aplicadas para o problema de encontrar rotas para distribuicao de bens e servicos publicos. Como aplicacao foi usada a coleta de lixo da cidade de Aracaju, Sergipe. 0 mais importante resultado do trabalho e que estas variantes tem melhor desempenho com relacao a aplicacao em computadores que os originais de Edmonds e Johnson e de Frederickson, e que a analise do pior caso mostra que a estimacao de Frederickson, isto e, que o custo de uma rota encontrada pelo uso do seu algoritmo e menor ou igual a 5/3 do custo de uma rota otima, e tambem valida para a variante aqui apresentada. Tambem pode ser esperado que em cada caso a variante, estudada apresente um resultado com custo menor ou igual ao do resultado obtido pela aplicacao dos algoritmos originais. Isto foi verificado em todos os exemplos usados durante o desenvolvimento deste trabalho.