Programação de Veículos com Coleta e Entrega: metodologia heurística baseada no Recozimento Simulado

Abstract

Esta pesquisa apresenta o desenvolvimento de um aplicativo para análise da programação de veículos em problemas de roteamento com coleta e entrega. Inicialmente, foi feita uma revisão do estado da arte sobre Problemas de Roteamento de Veículos (PRVs) e suas aplicações, bem como, métodos de solução. Baseado em trabalhos da literatura, foi elaborada uma formulação matemática com restrições específicas, em que a função objetivo busca minimizar o custo de transporte no qual inclui a distância percorrida e tempos penalizados. A partir da formulação foi implementado um aplicativo computacional embasado na metaheurística Recozimento Simulado, tendo as heuríticas de Construçã de Rotas e Programação de Horários para gerar a solução inicial e os movimentos de Reordenação, Realocação e Trocas para a estrutura de vizinhança e solução final. Além disso, foi considerado no aplicativo o cálculo de custos com Pernoites, Refeições, Tempo de Espera e Consumo que não estão na função objetivo. Para testar e validar a ferramenta desenvolvida foram utilizados dados de um problema real que trata da logística operacional de roteamento dos veículos que transportam servidores desde uma universidade federal até os polos de apoio presencial em diferentes municípios do Rio Grande do Sul. Foram realizados 15 testes considerando um cenário com 5 requisições para validar o aplicativo e comparar com o problema real. Os resultados encontrados nestes testes foram adequados para o cenário analisado, onde a função objetivo foi minimizada em vários testes e algumas rotas resultantes são viáveis de serem percorridas. Assim, os resultados da pesquisa foram considerados satisfatórios, visto que a formulação matemática e aplicativo desenvolvidos mostraram bons resultados quando comparados aos dados atuais do problema real.

This research presents the development of an application for review of vehicle scheduling in routing problems with pickup and delivery. Initially, a review was made of the state of the art on Vehicle Routing Problem (VRPs) and their applications, as well as methods of solution. Based on literature, we present a mathematical formulation with specific estrictions, in which the objective function seeks to minimize the cost of transport by which includes the distance traveled and time penalized. From the formulation was implemented a software grounded in the Simulated Annealing metaheuristic, with heuristics Construction Schedule Routes and Schedules to generate the initial solution and moves reordering, Relocation and Exchanges for the neighborhood structure and the final solution. Furthermore, the application was considered in calculating costs Overnights Meal Timeout and consumption that are not in the objective function. To test and validate the developed tool we used data from a real problem dealing with operational logistics routing of vehicles carrying servers from a federal university to the poles supporting presence in different municipalities of Rio Grande do Sul 15 tests were performed considering a scenario with 5 requests to validate the application and compare with the real problem. The results of these tests were found suitable for the analyzed scenario, where the objective function was minimized in several tests and some resulting routes are feasible to be covered. Thus, the search results were considered satisfactory, since the mathematical formulation and application developed showed good results when COMPARAND the current data of the real problem.