Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/336087
Type: DISSERTAÇÃO DIGITAL
Degree Level: Mestrado
Title: Um problema de distritamento aplicado à antecipação do faturamento em redes de serviço  
Title Alternative: A districting problem applied to billing anticipation in utilities networks  
Author: Mendes, Luis Henrique Pauleti, 1992-
Advisor: Usberti, Fábio Luiz, 1982-
Abstract: Resumo: Neste projeto de pesquisa é investigado o Problema de Distritamento Econômico e Capacitado (CEDP), que tem como objetivo encontrar em um grafo não-orientado e conexo subconjuntos de arestas que definam distritos conexos, balanceados, que respeitem uma capacidade máxima e maximizam o lucro. A motivação deste trabalho consiste na aplicação prática do CEDP para empresas que administram redes de distribuição de serviços; em particular, no processo de definição dos distritos para a leitura do consumo de seus clientes. São apresentadas duas formulações matemáticas para o CEDP e são propostas metodologias para resolvê-lo. As metodologias exatas são baseadas nos paradigmas Branch-and-Bound (B\&B) e Branch-and-Cut (B\&C). Dada a complexidade do problema, também são propostas metodologias heurísticas baseadas no GRASP e na relaxação Lagrangiana. Com o intuito de avaliar as metodologias propostas, foram realizados experimentos computacionais em um benchmark de instâncias do CEDP. Analisando os resultados, pode-se notar que a metodologia GRASP obteve um bom desempenho, enquanto que a heurística Lagrangiana, que não convergiu, obteve um desempenho ruim

Abstract: In this research project the Capacitated and Economic Districting Problem (CEDP) is investigated, which aims to find in a undirected connected graph subsets of edges defining connected and balanced districts that respect a maximum capacity and maximize the profit. The motivation of this work consists in the practical application of CEDP for utilities; particularly, in their process of defining the districts for meter reading. We present two mathematical formulations for the CEDP and propose methodologies to solve it. The exact methodologies are based on the Branch-and-Bound (B\&B) and Branch-and-Cut (B\&C) paradigms. Given the problem's complexity, we also propose heuristics methodologies based on GRASP and on Lagrangian relaxation. In order to evaluate the proposed methodologies, computational experiments were performed on a benchmark. Analyzing the results, it can be noted that the GRASP methodology performed well, while the Lagrangian heuristic, which did not converge, performed poorly
Subject: Otimização combinatória
Programação linear inteira
Meta-heurística
Language: Português
Editor: [s.n.]
Citation: MENDES, Luis Henrique Pauleti. Um problema de distritamento aplicado à antecipação do faturamento em redes de serviço  . 2019. 1 recurso online (91 p.). Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação, Campinas, SP.
Date Issue: 2019
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Mendes_LuisHenriquePauleti_M.pdf1.66 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.