Por favor, use este identificador para citar o enlazar este ítem: http://www.monografias.ufop.br/handle/35400000/3660
Título : Aplicação de uma metaheurística para o problema de orientação de redes fortemente conexas.
Autor : Martino, Diego Perdigão
metadata.dc.contributor.advisor: Martins, Alexandre Xavier
Oliveira, Paganini Barcellos de
metadata.dc.contributor.referee: Martins, Alexandre Xavier
Oliveira, Paganini Barcellos de
Cruz, Clarissa Barros da
Fonseca, Gabriela Braga
Miranda Júnior, Gilberto de
Palabras clave : Algoritmos
Grafos de ligação
Otimização combinatória
Pesquisa operacional
Fecha de publicación : 2021
Citación : MARTINO, Diego Perdigão. Aplicação de uma metaheurística para o problema de orientação de redes fortemente conexas. 2021. 54 f. Monografia (Graduação em Engenharia de Produção) - Instituto de Ciências Exatas e Aplicadas, Universidade Federal de Ouro Preto, João Monlevade, 2021.
Resumen : A gestão da mobilidade em grandes centros urbanos pode ser vista como um desafio no que se refere à adoção de alternativas para mitigar problemas comuns de mobilidade urbana, sejam eles previamente planejados ou inesperados. Um deles é a orientação de ruas e avenidas de forma a garantir um deslocamento eficiente em termos de distância percorrida, bem como a reestruturação da malha urbana, quando surgem situações que possam bloquear determinados pontos de conexão. Nesse sentido, um estudo sobre o Problema da Orientação de Redes Fortemente Conexas (Strong Network Orientation Problem) é explorado neste trabalho. O objetivo do problema consiste em determinar a orientação de uma rede de forma que a soma das distâncias percorridas a partir de cada ponto em relação aos demais seja mínima e que a configuração final permita que todos os pontos da rede sejam alcançáveis pelos demais. Trata-se de um problema de natureza combinatória pertencente à classe de problemas não determinísticos “difíceis” (NP-Difícil) e que, por este motivo, algoritmos de resolução exata não são suficientes para a resolução do problema em um curto intervalo de tempo dependendo do tamanho da rede. Este trabalho propõe um algoritmo metaheurístico baseado na variação de estruturas de vizinhança como forma de explorar um espaço diversificado de busca por soluções adequadas para o problema. Um novo conjunto de instâncias reais, baseadas em um centro urbano brasileiro, também é proposto neste trabalho. Um conjunto de experimentos computacionais são realizados tanto para o algoritmo proposto quanto para o resolvedor comercial CPLEX. Os resultados indicam que a metaheurística é eficiente e permite encontrar soluções de igual ou melhor qualidade que o resolvedor comercial, considerando o fato de que a otimalidade não é provada pelo CPLEX para todas as instâncias testadas, dentro do limite de tempo pré-estabelecido.
metadata.dc.description.abstracten: Mobility management in large urban centers can be seen as a challenge regarding the alternatives to mitigate common urban mobility problems, whether previously planned or unexpected. Orienting streets and avenues to guarantee an efficient displacement related to the total distance covered is one of these problems, as well as restructuring urban roads when some connection points are interrupted. In this sense, this work studies the Strong Network Orientation Problem (SNOP) which aims to determine the orientation of a network whose the sum of the distances covered from each point to the others is minimal. Moreover, the final configuration must allow all points belonging to the network to be reached by all others. Due the fact that the SNOP is a combinatorial optimization problem classified as NP-Hard, the exact resolution algorithms are not enough to solve it in a reasonable time depending on the size of the network. This work proposes then a metaheuristic algorithm based on variable neighborhood search structures in order to explore the search space and find suitable solutions. Also, a new set of real instances based on a Brazilian urban center is introduced. A set of computational experiments are performed for both the proposed algorithm and the commercial CPLEX solver. The results show that the metaheuristic is efficient and allows finding equal or better solutions than the CPLEX, taking into account that the optimality is not proven by CPLEX for all tested instances within a pre-established time limit.
URI : http://www.monografias.ufop.br/handle/35400000/3660
Aparece en las colecciones: Engenharia de Produção - JMV

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
MONOGRAFIA_AplicaçãoMetaheurísticaProblema.pdf1,74 MBAdobe PDFVisualizar/Abrir


Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons Creative Commons