Dissertação de Mestrado

A integração de drones com a finalidade de realizarem entregas de encomendas aos clientes finais (entregas de última milha) tende a ser um fator determinante de aperfeiçoamento dos serviços prestados pelo setor logístico. Desta forma, este trabalho tem por objetivo definir um modelo de Programação Linear Inteira Mista (PLIM) com a finalidade de estudar o Problema de Roteamento de Veículos com Drone (PRV-D). A formulação matemática tem como base o Problema do Reparador Viajante Simultâneo com Drone (PRVSD) no qual um veículo com um ou mais drones sai de um depósito para realizar entregas de encomendas com o objetivo de reduzir o tempo de espera de atendimento dos clientes. Enquanto no PRVSD o drone só pode atender um cliente por viagem, no estudo proposto o drone pode atender mais de um cliente por viagem, contudo o tempo de voo é limitado pelo consumo de bateria que, por sua vez, é em função do peso transportado pelo drone. Este novo problema foi nomeado Problema do Reparador Viajante Simultâneo com Drone com Múltiplas Visitas (PRVSDMV) e a validação do modelo foi realizada a partir da análise de 65 instâncias. Devido à impossibilidade de se obter resultados para algumas instâncias com vinte clientes ou mais, foi elaborada uma heurística com o propósito de encontrar soluções factíveis com tempo de processamento reduzido. Além disso, 43 novas instâncias foram criadas e analisadas alterando o parâmetro velocidade ou do drone ou do veículo. Após as análises dos resultados, demonstrou-se a economia de tempo proporcionada pelo novo modelo e avaliaram-se os impactos nos resultados gerados pela modificação da velocidade.

The integration of drones for the purpose of delivering parcels to the final customers (last-mile deliveries) tends to be a determining factor in improving the services provided by the logistics sector. Therefore, this work aims to define a Mixed Integer Linear Programming (MILP) model in order to study the Vehicle Routing Problem with Drones (VRP-D). The mathematical formulation is based on the Simultaneous Traveling Repairman Problem with Drone (STRPD), in which a vehicle with one or more drones departs from a depot to deliver parcels, with the goal of reducing customer waiting times. While in the STRPD the drone can only serve one customer per trip, in the proposed study the drone can serve multiple customers per trip. However, its endurance is limited by battery energy consumption, which depends on the weight carried by the drone. This new problem is called the Simultaneous Traveling Repairman Problem with Drone with Multiple Visits (STRPDMV), and the model was validated through the analysis of 65 instances. Due to the inability to obtain results for some instances with twenty or more customers, a heuristic was developed to find feasible solutions within reduced processing times. Additionally, 43 new instances were created and analyzed by modifying the speed parameter of either the drone or the vehicle. After analyzing the results, the time savings provided by the new model were demonstrated and the impacts on the results generated by speed variations were evaluated.