Aplicação da otimização por colônia de formigas ao problema de múltiplos caixeiros viajantes no atendimento comercial e emergencial em uma empresa de distribuição de energia elétrica
The commercial and emergency service consist of the execution of service orders by electrician teams in different points of the electric power distribution system, comprising the activities required for corrective maintenance of the distribution system and the commercial management of consumers. Thi...
Autor principal: | Barbosa, Denilson Fagundes |
---|---|
Formato: | Dissertação |
Idioma: | Português |
Publicado em: |
Universidade Tecnológica Federal do Paraná
2018
|
Assuntos: | |
Acesso em linha: |
http://repositorio.utfpr.edu.br/jspui/handle/1/2953 |
Tags: |
Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
|
id |
riut-1-2953 |
---|---|
recordtype |
dspace |
spelling |
riut-1-29532018-02-28T20:15:57Z Aplicação da otimização por colônia de formigas ao problema de múltiplos caixeiros viajantes no atendimento comercial e emergencial em uma empresa de distribuição de energia elétrica Applying the ant colony optimization to solve the multiple traveling salesmen problem to execution of commercial and emergency services in a electric power distribution company Barbosa, Denilson Fagundes Kashiawabara, Andre Yoshiaki http://lattes.cnpq.br/3194328548975437 Silla Junior, Carlos Nascimento http://lattes.cnpq.br/0755283890960491 Kashiwabara, Andre Yoshiaki Silla Junior, Carlos Nascimento Constantino, Ademir Aparecido Boscarioli, Clodis Energia elétrica - Distribuição Otimização matemática Algorítmos Electric power distribution Mathematical optimization Algorithms CNPQ::CIENCIAS EXATAS E DA TERRA Ciência da Computação The commercial and emergency service consist of the execution of service orders by electrician teams in different points of the electric power distribution system, comprising the activities required for corrective maintenance of the distribution system and the commercial management of consumers. This activity directly reflects in the quality of the power distribution companies, which seek to execute the services in order to meet the rules of the Brazilian National Agency of Electric Energy and to reduce the response time of customer requests. From the analysis of manual method used in an actual company to assign the services to the teams, we found the need for a computational method that uses the available data in the information systems of company to guide the dispatching services, in order that teams execute more services in the same time interval. We approach the problem in two steps. In the first step, we configure the Static Dispatch Problem, in which all services are known before the optimization. In the second step, we approach the Dynamic Dispatch Problem, in which new services arise and are dispatched to the teams during the workday and can be emergency orders. For the static problem, we build instances of the Multiple Traveling Salesmen Problem with the locations of orders, which were submitted to two Ant Colony Optimization algorithms. For the dynamic problem, we developed a system prototype called Dynamic Dispatch System to guide the dispatch of orders during the workday, which applies the static approach until the appearance of a new order. When a new order arises, the system reacts accordingly to the type of order: if it is an emergency order, then it is dispatched immediately to the nearest team; if it is a commercial order, a new instance is constructed and optimized again. For the static methodology, we performed experiments using 17 instances constructed from actual data. The experiments with the static methodology has reduces the largest route of single teams by an average of 44.43%, using predicted time costs for representation of instances. The experiments for the dynamic methodology, which simulated the appearance of new orders during the workday from actual dispatch times, reduced the total cost by 15.48% on average and the cost of larger individual routes by 17.18% on average. These results show that both the static and the dynamic methodologies are able to balance the workload of the teams, enabling that more services are performed in the same time interval, improving the current method of dispatching services in the company. O atendimento comercial e emergencial consiste basicamente na execução de serviços por equipes de eletricistas em diferentes pontos do sistema de distribuição de energia elétrica, compreendendo as atividades necessárias para a manutenção corretiva do sistema de distribuição e para a gestão comercial dos consumidores. Esta atividade reflete diretamente na qualidade das empresas de distribuição de energia, que procuram executar os serviços de forma a cumprir as metas da Agência Nacional de Energia Elétrica e a diminuir o tempo de resposta às solicitações dos clientes. A partir da análise do método manual utilizado em uma empresa real para designará os serviços às equipes, foi constatada a necessidade de uma metodologia computacional que utilize os dados disponíveis nos sistemas de informação da empresa para orientar o despacho de serviços, a fim de que mais serviços sejam atendidos pelas equipes no mesmo intervalo de tempo. O problema foi abordado em duas etapas. Na primeira etapa, foi configurado o Problema de Despacho Estático, no qual todos os serviços são conhecidos antes da otimização. Na segunda etapa, foi abordado o Problema de Despacho Dinâmico, no qual novos serviços surgem e são despachados às equipes durante o dia de trabalho, podendo ser emergenciais. Para o problema estático foram construídas instâncias do Problema de Múltiplos Caixeiros Viajantes a partir das posições dos serviços, que foram submetidas a dois algoritmos da Otimização por Colônia de Formigas. Para o problema dinâmico, foi desenvolvido um protótipo de um sistema para orientar o despacho dos serviços durante o dia de trabalho, denominado Sistema de Despacho Dinâmico, que aplica a metodologia estática até o surgimento de um novo serviço. Quando surge um novo serviço, o sistema reage de acordo com o tipo do serviço: se emergencial, é despachado imediatamente à equipe mais próxima; se comercial, uma nova instância é construída e novamente otimizada. A experimentação da metodologia estática foi realizada com 17 instâncias construídas a partir de dados reais, e reduziu em 44,43%, em média, a maior rota individual dos dias de trabalho utilizando custos temporais previstos para representação das instâncias. Os experimentos para a metodologia dinâmica, que simularam o surgimento de novos serviços durante o dia de trabalho a partir dos seus horários de despacho reais, reduziram em média 15,48% o custo total e 17,18% o custo da maior rota individual dos dias de trabalho. Esses resultados comprovam que tanto a metodologia estática quanto a dinâmica são capazes de equilibrar a carga de trabalho das equipes, possibilitando que mais serviços sejam executados no mesmo intervalo de tempo, melhorando o método atual de despacho de serviços na empresa. 2018-02-28T20:15:57Z 2018-02-28T20:15:57Z 2015-12-03 masterThesis BARBOSA, Denilson Fagundes. Aplicação da otimização por colônia de formigas ao problema de múltiplos caixeiros viajantes no atendimento comercial e emergencial em uma empresa de distribuição de energia elétrica. 2015. 121 f. Dissertação (Mestrado em Informática) - Universidade Tecnológica Federal do Paraná, Cornélio Procópio, 2015. http://repositorio.utfpr.edu.br/jspui/handle/1/2953 por openAccess application/pdf Universidade Tecnológica Federal do Paraná Cornelio Procopio Brasil Programa de Pós-Graduação em Informática UTFPR |
institution |
Universidade Tecnológica Federal do Paraná |
collection |
RIUT |
language |
Português |
topic |
Energia elétrica - Distribuição Otimização matemática Algorítmos Electric power distribution Mathematical optimization Algorithms CNPQ::CIENCIAS EXATAS E DA TERRA Ciência da Computação |
spellingShingle |
Energia elétrica - Distribuição Otimização matemática Algorítmos Electric power distribution Mathematical optimization Algorithms CNPQ::CIENCIAS EXATAS E DA TERRA Ciência da Computação Barbosa, Denilson Fagundes Aplicação da otimização por colônia de formigas ao problema de múltiplos caixeiros viajantes no atendimento comercial e emergencial em uma empresa de distribuição de energia elétrica |
description |
The commercial and emergency service consist of the execution of service orders by electrician teams in different points of the electric power distribution system, comprising the activities required for corrective maintenance of the distribution system and the commercial management of consumers. This activity directly reflects in the quality of the power distribution companies, which seek to execute the services in order to meet the rules of the Brazilian National Agency of Electric Energy and to reduce the response time of customer requests. From the analysis of manual method used in an actual company to assign the services to the teams, we found the need for a computational method that uses the available data in the information systems of company to guide the dispatching services, in order that teams execute more services in the same time interval. We approach the problem in two steps. In the first step, we configure the Static Dispatch Problem, in which all services are known before the optimization. In the second step, we approach the Dynamic Dispatch Problem, in which new services arise and are dispatched to the teams during the workday and can be emergency orders. For the static problem, we build instances of the Multiple Traveling Salesmen Problem with the locations of orders, which were submitted to two Ant Colony Optimization algorithms. For the dynamic problem, we developed a system prototype called Dynamic Dispatch System to guide the dispatch of orders during the workday, which applies the static approach until the appearance of a new order. When a new order arises, the system reacts accordingly to the type of order: if it is an emergency order, then it is dispatched immediately to the nearest team; if it is a commercial order, a new instance is constructed and optimized again. For the static methodology, we performed experiments using 17 instances constructed from actual data. The experiments with the static methodology has reduces the largest route of single teams by an average of 44.43%, using predicted time costs for representation of instances. The experiments for the dynamic methodology, which simulated the appearance of new orders during the workday from actual dispatch times, reduced the total cost by 15.48% on average and the cost of larger individual routes by 17.18% on average. These results show that both the static and the dynamic methodologies are able to balance the workload of the teams, enabling that more services are performed in the same time interval, improving the current method of dispatching services in the company. |
format |
Dissertação |
author |
Barbosa, Denilson Fagundes |
author_sort |
Barbosa, Denilson Fagundes |
title |
Aplicação da otimização por colônia de formigas ao problema de múltiplos caixeiros viajantes no atendimento comercial e emergencial em uma empresa de distribuição de energia elétrica |
title_short |
Aplicação da otimização por colônia de formigas ao problema de múltiplos caixeiros viajantes no atendimento comercial e emergencial em uma empresa de distribuição de energia elétrica |
title_full |
Aplicação da otimização por colônia de formigas ao problema de múltiplos caixeiros viajantes no atendimento comercial e emergencial em uma empresa de distribuição de energia elétrica |
title_fullStr |
Aplicação da otimização por colônia de formigas ao problema de múltiplos caixeiros viajantes no atendimento comercial e emergencial em uma empresa de distribuição de energia elétrica |
title_full_unstemmed |
Aplicação da otimização por colônia de formigas ao problema de múltiplos caixeiros viajantes no atendimento comercial e emergencial em uma empresa de distribuição de energia elétrica |
title_sort |
aplicação da otimização por colônia de formigas ao problema de múltiplos caixeiros viajantes no atendimento comercial e emergencial em uma empresa de distribuição de energia elétrica |
publisher |
Universidade Tecnológica Federal do Paraná |
publishDate |
2018 |
citation |
BARBOSA, Denilson Fagundes. Aplicação da otimização por colônia de formigas ao problema de múltiplos caixeiros viajantes no atendimento comercial e emergencial em uma empresa de distribuição de energia elétrica. 2015. 121 f. Dissertação (Mestrado em Informática) - Universidade Tecnológica Federal do Paraná, Cornélio Procópio, 2015. |
url |
http://repositorio.utfpr.edu.br/jspui/handle/1/2953 |
_version_ |
1805316033182957568 |
score |
10,814766 |