Reducing the vehicle routing problem complexity by mapping and sequencing clusters of high-density deliveries in urban regions

In urban logistics, a massive number of parcels need to be delivered on a daily basis to individual customer's doors. This is known as last-mile delivery, and logistics companies commonly use Vehicle Routing Problem (VRP) solutions to create intelligent route plans to support the execution of their work. Route planning can be optimized for different cost functions, such as cost-based optimization, time-based optimization, CO2 emission optimization, service-level optimization, workload-balancing optimization, and more. In this work, we propose a Kernel Density Estimation (KDE) task on past deliveries to identify central and peripheral areas. Then, a density-based clustering method is used to segment dense delivery regions within peripheral areas. These dense regions are further sequenced in order to simplify the VRP optimization space. The method was tested on real-world datasets containing thousands of deliveries from some of the largest Brazilian cities, and initial results suggest a transportation cost reduction of around 7 percent compared to other traditional user demand segmentation methods.