Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/123456789/3496| Título: | Meta-Heurística GRASP aplicada ao problema de localização de contadores de tráfego |
| Título(s) alternativo(s): | GRASP Meta-Heuristic applied to the location of traffic counters |
| Autor(es): | LIMA, Igor Luciano Cavalcanti |
| Palavras-chave: | GRASP Localização de contadores de tráfego Meta-heurística GRASP Traffic Counters Location Metaheuristic |
| Data do documento: | 12-Jul-2018 |
| Editor: | Universidade Federal do Maranhão |
| Resumo: | Muitos problemas de otimização combinatória do tipo NP-difícil têm importante aplicações práticas. Apresentar soluções ótimas exatas para esse tipo de problema geralmente requer elevado custo computacional. Esses problemas, em sua maioria, apresentam instâncias reais de grande porte e resolvê-las por meio de algoritmos exatos torna-se inviável. Por esse motivo, nas últimas décadas, diversas pesquisas voltadas para a utilização de meta-heurísticas, como proposta para resolução de problemas desta ordem, foram desenvolvidas. O principal atrativo está na qualidade das soluções apresentadas em tempo computacional aceitável, principalmente para grandes instâncias que normalmente representam dados reais dos problemas. Este trabalho propõe a utilização da meta-heurística Greedy Randomized Adaptive Search Procedure (GRASP) para resolução do Problema de Localização de Contadores de Tráfego (PLCT), um problema do tipo NP-difícil que consiste em determinar a quantidade e localização de contadores numa rede de transporte. A validação da meta-heurística é efetuada realizando-se testes em instâncias reais obtidas a partir de dados do Departamento Nacional de Infraestrutura de Transporte (DNIT) sobre estados brasileiros. Os resultados da abordagem são comparados à outras estratégias presentes na literatura. |
| Descrição: | ABSTRACT Many combinatorial optimization problems of the NP-hard type have important practical applications. Presenting exact optimal solutions for these problems often demands high computational cost. Most part of these problems present large real instances and solve them by exact algorithms becomes impracticable. For this reason, in the last decades, several studies aimed at the use of metaheuristics as a proposal to solve problems of this order were developed. The main attraction is the quality of the solutions presented in acceptable computational time, especially for large instances that usually represent real problems data. This work proposes the use of the Greedy Randomized Adaptive Search Procedure (GRASP) for the resolution of the Traffic Counters Location Problem (TCLP), a NP-hard problem that consists of determining the quantity and location of counters in a transport network. In order to validate the metaheuristic, computational experiments were performed in real instances obtained from data of Departamento Nacional de Infraestrutura de Transportes (DNIT) on Brazilian states. The approach results are compared to other strategies present in the literature. |
| URI: | http://hdl.handle.net/123456789/3496 |
| Aparece nas coleções: | TCCs de Graduação em Ciência da Computação do Campus do Bacanga |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| IGOR-Lima.pdf | Trabalho de Conclusão de Curso | 1,66 MB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.