An improved adaptive large neighborhood search algorithm for the flexible two-tier vehicle routing problem with drone stations

The two-tier vehicle routing problem (2T-VRP) represents a novel variant differing from the traditional VRPs. It can be applied to urban logistics operations system, offering significant potential for mitigating last-mile traffic congestion and reducing delivering costs. Distinct from traditional VRPs, this scenario contains a hierarchical two-tier structure, with trucks operating on the first tier and drones at stations on the second tier. In this study, we first extend the 2T-VRP framework by relaxing the hierarchical constraints, enabling trucks to transport goods not only to robot stations but also directly to customers. This new variant is referred to as the flexible two-tier vehicle routing problem with drone stations (F2T-VRP-DS). Then we formulate the problem as a mixed-integer linear programming (MILP) model. Finally, given the complexity of this problem, an improved adaptive large neighborhood search heuristic algorithm (IALNS) is proposed. The algorithm incorporates an adapted Clark and Wright saving algorithm as the initial solution, and a simulated annealing scheme is employed as the acceptance criterion. The experimental results show that our algorithm can provide high-quality solutions. In particular, compared with the MILP method, our algorithm demonstrates strong competitiveness on large-scale instances, offering smaller time consumption and better solution quality compared to commercial solver like Gurobi. In addition, based on the results of the sensitivity analysis, we further assessed the influence of several key parameters within the F2T-VRP-DS framework.