Column generation based hybrid optimization method for last-mile delivery service with autonomous vehicles

The research addresses the Last-Mile Delivery Service with Autonomous Vehicles (LMS-AV), which focuses on the multiple trips made by autonomous vehicles (AVs). This feature, widely utilized in real-world applications, has the potential to not only reduce the number of required vehicles and drivers but also lower operating costs. Recognizing these benefits as opportunities, we aim to enhance these advantages further. To this end we propose a novel branch-and-price-and-cut (BPC) algorithm based on the trip-based set partitioning model. Additionally, building upon the BPC algorithm, a column generation (CG) based heuristic algorithm is built to solve larger size instances. This model utilizes a two-phase CG algorithm to solve the linear relaxation sub-problem. A label-setting algorithm is tailored to generate feasible paths, and we introduce a strategy, named ’Finding A Time Point to Minimize the Reduced Cost of A Path’ to identify trips with minimal reduced costs. Furthermore, k-path and subset-row inequalities are introduced to tighten the relaxation gap. To accelerate the sub-problem's solution process, we propose several methods, including bidirectional search techniques, heuristic labeling, completion bounds, and ng-route relaxation. Results indicate that our BPC algorithm can solve instances with up to 100 customers, and our heuristic algorithm not only efficiently solves all instances but also maintains a minimal gap when compared to the BPC algorithm.