Highly feasible, energy-minimizing and time window-guaranteeing last-mile delivery routes generation based on clustering and local search considering package densities

摘要

The last-mile, which is the final stage of delivery, has great meaning for both consumers and suppliers. Consumers first form user experiences with a company in the final delivery stage, and the efficient last mile delivery for suppliers must be achieved by guaranteed delivery time window and minimized delivery cost in energy and time. Execution feasibility is also important, because the optimal route is optimal only when it is actually executed by drivers. In this study, we aim to create an optimal route with high feasibility and minimal energy consumption for green delivery. The proposed method minimizes the sum of volume-weighted delivery time of packages and determines the priority of the visit by considering clusters made from the zone ID sequences systematically extracted from the collected delivery routes. The optimal route is generated by determining the order of visits of inter- and intra-clusters through local search based minimization. Case studies using the actual delivery data provided by the Amazon Last-mile Routing Challenge in year 2021 show its efficiency in achieving green delivery.