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. - SANTOS, Antônio dos. (1981)
Neste trabalho são estabelecidos variantes de algoritmos heurísticos de Edmonds e Johnson e de Frederickson, para o problema do carteiro chinês num grafo misto. Estas variantes podem ser aplicadas para o problema de encontrar rotas para distribuição de bens e serviços públicos. Como aplicação foi usada a coleta de lixo da cidade de Aracaju, Sergipe. 0 mais importante resultado do trabalho é que estas variantes têm melhor desempenho com relação a aplicação em computadores que os originais de Edmonds e Johnson e de Frederickson, e que a análise do pior caso mostra que a estimação de Frederickson, isto é, que o custo de uma rota encontrada pelo uso do seu algoritmo é menor ou igual a 5/3 do custo de uma rota ótima, é também válida para a variante aqui apresentada. Também pode ser esperado que em cada caso a variante, estudada apresente um resultado com custo menor ou igual ao do resultado obtido pela aplicação dos algoritmos originais. Isto foi verificado em todos os exemplos usados durante o desenvolvimento deste trabalho.