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.

• Ano de defesa: 1981
• Autor(a) principal: SANTOS, Antônio dos.
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Campina Grande; Brasil; Centro de Engenharia Elétrica e Informática - CEEI; PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO; UFCG
• Link de acesso: http://dspace.sti.ufcg.edu.br:8080/jspui/handle/riufcg/3711

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.