CAXEIRO VIAJANTE

O PROBLEMA DO CARTEITO CHINÊS

1- OBJETIVO DO TRABALHO
O objetivo principal deste estudo, e o desenvolvimento de uma metodologia, que solucione o "Problema do Carteiro Chinês", em grafos mistos, visando aplicações diretas na distribuição de bens e serviços públicos. No conteúdo dessas aplicações, foram levantadas algumas restrições, associadas às leis de trânsito e manobras de veículos, quando essas se fazem necessárias. São apresentadas soluções, que adaptam essas restrições, aos algoritmos e à rota final. Com o intuito de alcançar um melhor desempenho da metodologia proposta, foram pesquisados vários algoritmos, con- siderados, como os mais eficientes, nas questões envolvidas no problema. Através da utilização destes algoritmos, e de procedimentos heurísticos, o grafo original, é modificado e transformado em um grafo euleriano, onde será aplicada a rota fi­nal. Todos os algoritmos, relativos a esses procedimentos, e à rota final, são apresentados de uma forma estruturada, e para facilitar a sua compreensão e implementação, foram colocados alguns exemplos ilustrativos, nos casos em que foi julgado como necessário.
Nas conclusões, são apresentados alguns aspectos, que podem ser abordados futuramente, visando uma posterior e se possível, melhor adaptação do trabalho ao problema real.

2- JUSTIFICATIVA DO TRABALHO

Os problemas de Percurso em Arcos são dos mais antigos relacionados a grafos. A primeirareferência que se conhece sobre eles vem do famoso problema das sete pontes de Königsberg, resolvido por Leonard Euler. Euler mostrou que não havia solução que satisfizesse aquele caso particular. Nasce aí a Teoria dos Grafos.

3-RESUMO DO TRABALHO O Problema do Carteiro Chinês caracteriza-se pela roteirização de arcos e tem como objetivo a cobertura de arcos de um grafo, criando uma rota que passe ao menos uma vez em cada um destes arcos. O problema pode ser subdividido em casos, de acordo com o tipo do grafo analisado.