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

Abstract

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.