Matemática Computacional - Aula 20/11/2012

Problema do Carteiro Rural

É uma generalização do Problema do Carteiro Chinês, e, juntamente com o Problema do Caixeiro Viajante, constitui um dos principais Problemas de Roteamento de Veículos (PRV). Esses problemas estão dentro de uma classe maior de problemas denominados Problemas de Roteamento Geral (ver Letchford [1996]), e inclui um grande número de casos particulares e importantes.

O Problema do Carteiro Chinês (PCC)

A importância do modelo do carteiro chinês para a área de roteamento de veículos

As aplicações dos caminhos eulerianos se relacionam, basicamente, com problemas de atendimento sequencial, sobre um conjunto de usuários de um serviço oferecido no interior de uma rede de tráfego, tais como, entrega de correio, coleta de lixo, vendas por atacado etc.

Um problema interessante ligado ao conceito de grafo semi-euleriano é o Problema do Carteiro Chinês. Imagine um carteiro que deve percorrer um roteiro todo dia. O problema é de identificar esse roteiro de maneira a minimizar a distância total percorrida. Essa situação pode ser representada por um grafo onde as arestas correspondem às ruas e os vértices correspondem aos cruzamentos.

Se o grafo é euleriano, a solução consiste simplesmente em achar um circuito euleriano. Mais interessante é o caso de um grafo não euleriano. Consideremos por exemplo um grafo semi-euleriano, como ilustrado na figura 4. Supondo que o carteiro quer voltar ao lugar de origem, portanto com certeza para cada um dos vértices 1 e 8, uma das arestas adjacentes será atravessada no mínimo duas vezes.

Continue lendo... (página 4)

Vídeo

Nesse vídeo, a respeito dos problemas das classes P e NP, veja uma breve explicação dos problemas intratáveis. Ao final, há uma explicação a respeito do problema do carteiro chinês, além do caso para grafos mistos, em que o problema se torna NP-difícil. -- Fonte: Video realizado para a disciplina de linguagens formais e autômatos da Universidade Federal de São Paulo.