Técnicas da pesquisa operacional na abordagem do problema de roteamento no transporte de funcionários de empresas

Abstract

Resumo: O Problema de Roteirização de Veículos (PRV) é um dos problemas mais estudados de Pesquisa Operacional devido a sua vasta gama de aplicações, sendo a roteirização de veículos aplicada ao transporte de funcionários, tema desta pesquisa, uma das aplicações com crescente valor agregado nos grandes centros urbanos. O objetivo foi propor um algoritmo que auxilie na obtenção de uma roteirização no transporte de funcionários que seja eficaz, atenda às restrições de trajeto, seja esta a distância máxima a ser percorrida ou o tempo máximo de trajeto, e que preze por utilizar menos veículos tanto quanto possível. Utilizou-se o tempo máximo em que o trajeto completo deve ser executado como fator restritivo do algoritmo para a construção da roteirização para um dos conjuntos de dados disponível. Também se utilizou a distância máxima que cada rota deve percorrer como restrição para todos os grupos de dados. O refinamento das rotas obtidas foi realizado com os procedimentos de otimização intra-rota 2-opt e inter-rotas de troca e de intercâmbio. Dois modelos de algoritmos foram propostos: o Modelo 1 roteiriza fazendo a coleta dos funcionários diretamente em suas residências e o Modelo 2 faz primeiramente o agrupamento (clusterização) dos funcionários em pontos estratégicos, respeitando uma distância máxima da residência conforme estipulado pela empresa, passando a utilizar estes pontos para a coleta dos funcionários. Aplicaram-se os modelos propostos na roteirização da coleta de funcionários de uma empresa do município de Curitiba, Paraná, para o turno administrativo e para os três turnos operacionais. Os tempos de trajeto e distâncias reais de trajeto foram obtidos no Google Maps, sendo utilizada também a distância estimada através da distância euclidiana. Compararam-se os resultados aqui obtidos com os anteriormente encontrados na literatura, onde não havia restrições de tempo nem de distância a ser percorrida. Os modelos propostos apresentaram-se viáveis, sendo que o Modelo 2, mais robusto, contribuiu com uma redução média de 47% na distância total percorrida, necessitando em média de um veículo a mais para a roteirização.

Abstract: The Vehicle Routing Problem (VRP) is one of the most studied problems of operational research due to its wide range of applications, being a vehicle routing applied to transport of employees, subject of this survey, one of the applications with increasing added value in major urban centers. The goal was to propose an algorithm that may assist in obtaining a routing in the transport of employees that is effective, respect the path constraints, this is the maximum distance to be traveled, or the maximum path and that routing by using less vehicles as much as possible. We used the maximum amount of time in which the full path must be executed as a restrictive factor of algorithm for the construction of the routing to one of the available datasets. Furthermore used the maximum distance that each route should be as a constraint for all data groups. The refinement of the routes constructed was accomplished with the optimization procedures 2-opt and changes between the routes. Two models of algorithms have been proposed: Model 1 making the routes pick-up the employees directly to their homes and the Model 2 makes grouping (clustering) of employees in strategic points, along with a maximum distance of residence as stipulated by the company, and use these points to the employee collection. The models have been proposed in the routing of employees in a company of the city of Curitiba, Paraná, to employees of administrative and of three operating turn. Travel times and distances were obtained in the real path with Google Maps, being used also the distance estimated by the Euclidean distance. We compare the results here obtained with the previously found in the literature, where there was neither time constraints of distance to be traveled. The models proposed were feasible, being the Model 2, more robust, contributing an average of 47% reduction in the total distance travelled, requiring on average to the one vehicle for the routing.