Pick-up Service Vehicle Routing Problem With Flexible Assignment of Depots

We address a vehicle routing problem for pick-up services, with flexible assignment of decentralized depots by utilizing parking lots throughout urban areas. The problem involves determining vehicle routes, which include deciding which demand locations each vehicle will visit, as well as depot assignments, while minimizing the operational costs including travel cost, parking cost, and tardiness cost. A mixed integer linear programming model is formulated to optimally solve the small-sized problem instances. To solve the problem efficiently, we propose a three-stage heuristic including clustering-based approach to group demand locations. For large-sized problem instances, a three-stage solution approach is proposed: (1) clustering demand locations into small-sized groups, (2) assignment of clusters to vehicles based on the distance between each vehicle and the cluster centroid, and (3) determining optimized routes for each vehicle by applying a meta-heuristic algorithm with iterative cluster reassignment. The effectiveness of the proposed approach is demonstrated through computational experiments showing significant cost reductions compared to conventional single-depot operations. This study provides operational insights into sustainable urban logistics and highlights the benefits of flexible depot utilization to enhance operational efficiency.