Título: UMA HEURÍSTICA CONSTRUTIVA PARA O PROBLEMA DE PARTICIONAMENTO DE ARESTAS EM DISTRITOS EULERIANOS

Autoria de: Alvaro Martins Espindola

Orientação de: Mayron Cesar de Oliveira Moreira

Presidente da banca: Mayron Cesar de Oliveira Moreira

Primeiro membro da banca: Bruno de Abreu Silva

Segundo membro da banca: Julio Cesar Alves

Palavras-chaves: Particionamento de Arestas, Distritos, Grafos Eulerianos, Heurística Construtiva, Distritamento

Data da defesa: 29/04/2022

Semestre letivo da defesa: 2021-2

Data da versão final: 05/05/2022

Data da publicação: 05/05/2022

Referência: Espindola, A. M. UMA HEURÍSTICA CONSTRUTIVA PARA O PROBLEMA DE PARTICIONAMENTO DE ARESTAS EM DISTRITOS EULERIANOS. 2022. 41 p. Trabalho de Conclusão de Curso (Graduação em Ciência da Computação Bacharelado)-Universidade Federal de Lavras, Lavras, 2022.

Resumo: Este trabalho propõe uma solução heurística para o problema de particionamento de arestas considerando distritos Eulerianos, o qual se revela presente em contextos como entrega de correspondências, leitura de medidores, coleta de neve, manutenção de estradas e coleta de lixo em municípios. O objetivo do problema consiste em dividir um grafo em distritos que possam ser percorridos evitando a repetição de vias e distribuindo a demanda total da forma mais igualitária possível. Instâncias de até 401 vértices e 764 arestas provenientes da literatura foram utilizadas para teste baseadas no estado da arte, as quais foram todas resolvidas considerando demanda, paridade dos vértices, compacidade e continuidade dos distritos com tempo máximo de execução de 6.9 segundos. O algoritmo proposto encontra soluções factíveis para o problema, e pode ser um caminho para resolução de instâncias de larga escala considerando que o mesmo não necessita considerar a conexidade dos distritos, contrário ao estado da arte.

URI: sip.prg.ufla.br/publico/trabalhos_conclusao_curso/acessar_tcc_por_curso/
ciencia_da_computacao/20212201811162

URI alternaviva: repositorio.ufla.br/handle/1/54830

Curso: G010 - CIÊNCIA DA COMPUTAÇÃO (BACHARELADO)

Nome da editora: Universidade Federal de Lavras

Sigla da editora: UFLA

País da editora: Brasil

Gênero textual: Trabalho de Conclusão de Curso

Nome da língua do conteúdo: Português

Código da língua do conteúdo: por

Licença de acesso: Acesso aberto

Nome da licença: Licença do Repositório Institucional da Universidade Federal de Lavras

URI da licença: repositorio.ufla.br

Termos da licença: Acesso aos termos da licença em repositorio.ufla.br

Detentores dos direitos autorais: Alvaro Martins Espindola e Universidade Federal de Lavras

Baixar arquivo