Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia de Produção. / Made available in DSpace on 2012-10-15T23:13:51Z (GMT). No. of bitstreams: 0Bitstream added on 2013-07-16T17:01:44Z : No. of bitstreams: 1 261413.pdf: 1366941 bytes, checksum: b7b9ae8617c04ca0ee56adc05aa8c9f4 (MD5)

Tese (doutorado) - Universidade Federal de Santa Catarina. Centro Tecnológico. Programa de Pós-Graduação em Engenharia de Produção / Made available in DSpace on 2012-10-21T10:13:22Z (GMT). No. of bitstreams: 1 203794.pdf: 1456519 bytes, checksum: b373b1757509e2b213390cfd4962afd8 (MD5) / Nos problemas de roteamento o objetivo é determinar um circuito de custo mínimo que cobre um dado conjunto de arcos ou nós de um grafo, sujeito a algumas restrições. Existem duas classes bem conhecidas de tais problemas, denominadas como o Problema de Caixeiro Viajante (PCV), e o Problema do Carteiro Chinês (PCC). Com raras exceções, todos os problemas já formulados nessas duas classes são NP-completos. Portanto, para os problemas de maior porte existem apenas soluções aproximadas. Nessa Tese foi considerado o problema de determinar um circuito de custo mínimo que cobre um dado subconjunto de arcos, de arestas e de nós de um grafo misto, sujeito a algumas restrições nos vértices (restrições que proíbem conversões indesejáveis nos cruzamentos de malhas urbanas). Obviamente, o PCV, PCC e a maior parte de suas variações, como: o Problema do Carteiro Chinês Misto e o Problema do Carteiro Rural são casos particulares deste problema geral. A solução proposta é baseada numa transformação polinomial do grafo que possibilita a solução do problema resultante como um PCV padrão. Resultados computacionais confirmam a eficiência do método na obtenção de soluções próxima a ótimas para problemas razoavelmente grandes.