Título: IMPLEMENTAÇÃO DE UM MODELO MATEMÁTICO PARA O PROBLEMA DE PARTICIONAMENTO DE ARESTAS EM DISTRITOS EULERIANOS

Autoria de: Marcos José Pimentel Salles

Orientação de: Mayron Cesar de Oliveira Moreira

Presidente da banca: Mayron César de Oliveira Moreira

Primeiro membro da banca: Júlio César Alves

Segundo membro da banca: Vinícius Vitor dos Santos Dias

Palavras-chaves: Parcelamento de arestas, Distritos Eulerianos, Modelo matemático, Gurobi, Pesquisa operacional

Data da defesa: 28/07/2023

Semestre letivo da defesa: 2023-1

Data da versão final: 02/08/2023

Data da publicação: 02/08/2023

Referência: Salles, M. J. P. IMPLEMENTAÇÃO DE UM MODELO MATEMÁTICO PARA O PROBLEMA DE PARTICIONAMENTO DE ARESTAS EM DISTRITOS EULERIANOS. 2023. 52 p. Trabalho de Conclusão de Curso (Graduação em Ciência da Computação Bacharelado)-Universidade Federal de Lavras, Lavras, 2023.

Resumo: O trabalho considera um modelo de grafos planar, não-direcionado, ponderado e conexo, e aborda o problema de parcelamento de arestas. Trata-se de um problema presente em contextos como entrega de correspondências, coleta de lixo e recolhimento de neve. O objetivo consiste em gerar k subgrafos induzidos (ou distritos) que sejam equilibrados quanto à distribuição de demanda, representada pelo peso das arestas. Além disso, a quantidade de vértices de grau ímpar em cada partição é limitada, tornando cada subgrafo gerado o mais Euleriano possível. Tomando um vértice referência (ou vértice que indica um ??depósito??, dependendo da aplicação) para cada subgrafo, a função de otimização trabalha a compacidade dos subgrafos, minimizando o somatório da distância de cada aresta designada a um subgrafo para seu respectivo vértice referência. A literatura desse problema já possui um algoritmo exato, baseado na geração iterativa de cortes de conexidade. No entanto, tal implementação não encontra-se disposível para acesso. Diante disso, propõese, neste trabalho, a codificação de tal algoritmo, utilizando frameworks modernos tal como o GUROBIPY, implementando a inserção dos cortes de forma dinâmica através de funções callback. Os resultados computacionais atestam a eficácia da formulação implementada.

Abstract: The paper discusses a model of a planar, undirected, weighted, and connected graph. It addresses the issue of edge partitioning, which arises in various contexts like mail delivery, waste collection, and snow removal. The objective is to generate k induced subgraphs, also known as districts, that achieve a balanced distribution of demand represented by the edge weights. Additionally, there is a constraint on the number of odd-degree vertices in each partition, aiming to maximize the Eulerian property of the subgraphs. To accomplish this, each subgraph is associated with a reference vertex, which can be interpreted as a depotdepending on the application. The optimization function evaluates the compactness of the subgraphs by minimizing the total distance between each edge assigned to a subgraph and its corresponding reference vertex. Although an exact algorithm for this problem exists in the literature, which utilizes iterative generation of connectivity cuts, it is currently unavailable for access. Thus, we propose in this study the implementation of the algorithm using modern frameworks such as GUROBIPY. The implementation includes the dynamic insertion of cuts through callback functions. Our computational experiments demonstrate the effectiveness of the formulated approach.

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

URI alternaviva: sem URI do Repositório Institucional da UFLA até o momento.

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: Marcos José Pimentel Salles e Universidade Federal de Lavras

Baixar arquivo