Algoritmos heurísticos de cobertura de arcos
Show full item record
Title:
|
Algoritmos heurísticos de cobertura de arcos |
Author:
|
Sherafat, Hassan
|
Abstract:
|
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. |
Description:
|
Tese (doutorado) - Universidade Federal de Santa Catarina. Centro Tecnológico. Programa de Pós-Graduação em Engenharia de Produção |
URI:
|
http://repositorio.ufsc.br/xmlui/handle/123456789/86744
|
Date:
|
2004 |
Files in this item
This item appears in the following Collection(s)
Show full item record
Search DSpace
Browse
-
All of DSpace
-
This Collection
My Account
Statistics
Compartilhar