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

Abstract

The Vehicle Routing Problem (VRP) is a classical optimization problem that aims to find routes for a fleet of vehicles to meet the demands of a set of customers. Due to its wide applicability, especially in the logistics sector, numerous VRP variants exist. One such variant is the Dynamic Vehicle Routing Problem (DVRP), where new customer demands may arise after the initial routing has been defined. The combinatorial nature of the DVRP makes it challenging to find high-quality feasible solutions within a reasonable runtime for real-world large-sized problems, motivating the development of heuristic approaches to address this issue. This paper presents a new heuristic algorithm, Dynamic Search per Neighbors Routes (DSNR), which uses neighborhood search approaches based on the 2-Opt* operator to allocate new delivery packages to existing routes. The DSNR algorithm was evaluated on instances from the Loggibud benchmark, representing real data from three different Brazilian cities. Regarding distance and number of vehicles, the proposed approach outperforms two other techniques from the literature: the QRP Sweep (QRPS) and the K-Means Greedy (KG). The DSNR achieved gains ranging from 15% to 17% in distance and final delivery costs.

Keywords

• 2-opt*
• dsnr
• dynamic vehicle routing
• local search heuristic
• k-means greedy
• qrp sweep