O problema do corredor de comprimento mínimo : algoritmos exatos, aproximativos e heurísticos

Content Provider	Semantic Scholar
Author	Oliveira, Lucas De Souza, Cid C. De
Copyright Year	2012
Abstract	Esta dissertacao tem como foco a investigacao experimental de algoritmos exatos, aproximativos e heuristicos aplicados na resolucao do chamado problema do corredor de comprimento minimo (PCCM). No PCCM recebemos um poligono retilinear P e um conjunto de poligonos retilineares menores formando uma subdivisao S planar conexa de P. Uma solucao para este problema, tambem chamada de corredor, e formada por um conjunto conexo de arestas de S, e tal que cada face interna em S possui pelo menos um ponto em sua borda que pertence a alguma aresta deste conjunto. O objetivo entao e encontrar um corredor tal que a soma total dos comprimentos das arestas seja a menor possivel. Trata-se de um problema NP-dificil com aplicacoes em areas diversas, tais como telecomunicacoes, engenharia civil e projeto de circuitos VLSI. O PCCM pode ser reduzido polinomialmente a um problema em grafos denominado problema da arvore de Steiner com grupos (PASG). Considerando esta transformacao, estudamos e implementamos dois metodos aproximativos, um metodo exato de branch-and-cut, e um metodo heuristico baseado na metaheuristica GRASP combinada com um evolutionary path relinking (GRASP+EPR). Alem disso, propomos tres heuristicas de busca local que visam melhorar a qualidade de solucoes do PASG. Instâncias do PCCM foram geradas aleatoriamente, nas quais aplicamos os metodos implementados. Analisamos os resultados, e apresentamos as situacoes onde e interessante utilizar cada metodo. Verificamos que o metodo branch-and-cut foi capaz de encontrar solucoes otimas para instâncias que julgamos ser de grande porte em tempos computacionalmente aceitaveis. O melhor algoritmo aproximativo obteve corredores que na media tem comprimento 17% maior que o comprimento otimo. Se combinarmos este algoritmo com as heuristicas de melhoria propostas este percentual cai para a media de 3,5%. Finalmente, o GRASP+EPR consome mais tempo que este algoritmo aproximativo, entretanto, o comprimento dos corredores obtidos por ele e em media 0,9% maior que o comprimento otimo. Abstract
File Format	PDF HTM / HTML
Alternate Webpage(s)	http://repositorio.unicamp.br/jspui/bitstream/REPOSIP/275700/1/Oliveira_Lucasde_M.pdf
Language	English
Access Restriction	Open
Content Type	Text
Resource Type	Article