Aerial-ground collaborative routing with time constraints

The advancement of autonomous technology makes electric-powered drones an excellent choice for flexible logistics services at the last mile delivery stage. To reach a balance between green transportation and competitive edge, the collaborative routing of drones in the air and trucks on the ground is increasingly invested in the next generation of delivery, where it is particularly reasonable to consider customer time windows and time-dependent travel times as two typical time-related factors in daily services. In this paper, we propose the Vehicle Routing Problem with Drones under Time constraints (VRPD-T) and focus on the time constraints involved in realistic scenarios during the delivery. A mixed-integer linear programming model has been developed to minimize the total delivery completion time. Furthermore, to overcome the limitations of standard solvers in handling large-scale complex issues, a space-time hybrid heuristic-based algorithm has been developed to effectively identify a high-quality solution. The numerical results produced from randomly generated instances demonstrate the effectiveness of the proposed algorithm.