Localização e roteamento para serviços de atendimento emergencial : o caso da segurança eletrônica

Abstract

Resumo: Neste trabalho é apresentada uma proposta de solução para o problema de determinar a localização espacial de centros de serviços emergenciais e o subseqüente roteamento dos veículos que realizam estes atendimentos em uma empresa particular. Analisou-se o caso de uma empresa de segurança eletrônica situada no município de Pato Branco, no Sudoeste do Paraná. A localização dos centros de serviços emergenciais é obtida como solução de um problema de p-medianas, visando minimizar a distância média de deslocamento dos agentes de segurança e, conseqüentemente, realizar o atendimento em tempo hábil menor. Para resolver esse problema são propostas duas heurísticas adaptadas, sendo a primeira, baseada em um algoritmo de busca exaustiva através da troca de vértices e a segunda, baseada em um algoritmo genético simples que utiliza os operadores genéticos usuais. Após a localização é realizada a designação dos pontos às medianas, havendo a formação de dois clusters (agrupamentos), utilizando um algoritmo baseado nas razões entre as duas menores distâncias desses pontos às medianas encontradas. O roteamento, em cada agrupamento, é obtido como solução de um problema dos Múltiplos Caixeiros Viajantes, visando a construção de vários roteiros otimizados que minimizam a distância total percorrida pelos veículos. Foi utilizado, para isso, um algoritmo baseado na inserção de pontos que resultem em economias nos roteiros obtidos.

Abstract: It is presented in this work a proposal of solution to the problem of determining the spatial location of centers of emergency Services and the subsequent routing of the vehicles that execute these Services in a particular company. The case of an electronic security company situated in the city of Pato Branco, in the Southwest of the Paraná, was analyzed. The location of the centers of emergency Services is obíained as a solution to a problem of p-medians, aiming at minimizing the average distance of the security agents and consequently executing the attendance in shorter skillíul time. To solve this problem two adapted heuristics are proposed, being the first one based on an algorithm of exhaustive search through the changing of vertices, and the second based on a simple genetic algorithm that uses the usual genetic operators. After the location, the designation of the points to the medians is determined, having the formation of two clusters (groupings), using an algorithm based on the ratios between the two shorter distances of these points to the detected medians ones. The routing in each clustering is obtained as a solution to the Multiple Salesperson problem, aiming at the construction of various optimized routes, which minimize the total distance covered by the vehicles. For this purpose, an algorithm based on the insertion of points was used and which can result in economy regarding the obtained routes.