A neighborhood search-based heuristic for the dynamic vehicle routing problem

Resumo

The Vehicle Routing Problem (VRP) is a classical optimization problem focused on determining routes for a fleet of vehicles to fulfill the demands of a set of customers. Due to its wide applicability, particularly in the logistics sector, numerous variants of the VRP have been developed. One such variant is the Dynamic Vehicle Routing Problem (DVRP), characterized by the emergence of new customer demands after the initial routing has been established. The combinatorial complexity of the DVRP poses significant challenges in finding high-quality, feasible solutions within practical runtime limits for real-world, large-scale problems, thereby driving the development of heuristic approaches. This paper introduces a novel heuristic algorithm, Dynamic Search per Neighbors Routes (DSNR), which employs neighborhood search techniques based on the 2-Opt* operator to incorporate new delivery requests into existing routes. The DSNR algorithm was tested using instances from the Loggibud benchmark, representing real-world data from three distinct Brazilian cities. In terms of distance and the number of vehicles required, the proposed approach demonstrated superior performance compared to two existing methods from the literature: the QRP Sweep (QRPS) and K-Means Greedy (KG). The DSNR achieved improvements of 15% to 17% in terms of distance and final delivery costs.