Um problema de distritamento aplicado à antecipação do faturamento em redes de serviço [recurso eletrônico]
Luis Henrique Pauleti Mendes
DISSERTAÇÃO
Português
T/UNICAMP M522p
[A districting problem applied to billing anticipation in utilities networks ]
Campinas, SP : [s.n.], 2019.
1 recurso online (91 p.) : il., digital, arquivo PDF.
Orientadores: Fábio Luiz Usberti, Celso Cavellucci
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
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...
Ver mais
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
Ver menos
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...
Ver mais
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
Ver menos
Requisitos do sistema: Software para leitura de arquivo em PDF
Usberti, Fábio Luiz, 1982-
Orientador
Cavellucci, Celso, 1951-
Coorientador
Hokama, Pedro Henrique Del Bianco, 1986-
Avaliador
Souza, Cid Carvalho de, 1963-
Avaliador
Um problema de distritamento aplicado à antecipação do faturamento em redes de serviço [recurso eletrônico]
Luis Henrique Pauleti Mendes
Um problema de distritamento aplicado à antecipação do faturamento em redes de serviço [recurso eletrônico]
Luis Henrique Pauleti Mendes