Um estudo sobre o problema dinâmico de roteamento de veículos

Abstract

The number of package deliveries has increased significantly in recent years, demanding optimization algorithms-based tools for decision support. In this scenario, minimizing costs while defining delivery routes is relevant. This problem is a classic for combinatorial, known as Vehicle Routing Problem (VRP). There are many variants in the literature for VRP, such as the Dynamic Pickup and Delivery Problem (DPDPTW). In DPDPTW, the requests arrive during the route's designation. Furthermore, a package must be picked up at one point and delivered to another. Finally, the attendance to a point must be within a time interval. The DPDPTW/UR is a variant derivated from this problem and classifies the points into rural or urban and restricts vehicle attendance. Inspired by a real-world problem, this work adapts a literature algorithm to solve the DPDPTW. Additionally, it proposes methods to simplify the solutions generalization. Further, the approach for the DPDPTW is adjusted for DPDPTW/UR as an example. Extensions of the implemented heuristics are compared in experiments with DPDPTW and its static version. Finally, the DPDPTW/UR is tested with the best variation, and the results show that the methods proposed for DPDPTW and DPDPTW/UR are equally efficient.