Modelagem e Desenvolvimento de Algoritmo para o Problema de Roteamento Dinâmico de Veículos

Abstract

Finding efficient routes for a vehicle fleet to minimize distance and time and maximizing service profit are some of the goals pursued in solving the Vehicle Routing Problem (VRP). The VRP and its variants are widely studied in the area, with several proposals for models, algorithms, and techniques (methods). The goal of this work is to present an approach named Dynamic Vehicle Routing Problem (DVRP). In the DVRP the set of items to be delivered are not known in advance. This is a current problem targeted to logistics companies, especially those whose focus is on marketplace, that should manage thousands of products to be delivered along a working day subject to constraints on vehicle fleets and service hours. In this work, dynamic and static routing algorithms, named Dynamic Search per Neighbors Routes (DSNR) and Kmeans, Relax-and-Fix and Optimizations (K-RFO), respectively, are proposed. The scenery for the dynamic algorithm is the routing of batches of packages (items) to be delivered at the same working day. The DVRP algorithm is based on a local search together with a 2-Opt** heuristic aiming to re-optimize neighboring routes to accommodate dynamic packages. The DSNR algorithm has been evaluated and compared to dynamic algorithms QRP-Sweep (QRPS) and Kmeans-Greedy (KG), achieving up to 17% of operational costs savings.