Unmanned aerial vehicles (UAVs) are increasingly used in instant delivery scenarios. The combined delivery of vehicles and UAVs has many advantages compared to their respective separate delivery, which can greatly improve delivery efficiency. Although a few studies in the literature have explored the issue of vehicle-assisted UAV delivery, we did not find any studies on the scenario of an UAV serving several customers. This study aims to design a new vehicle-assisted UAV delivery solution that allows UAVs to serve multiple customers in a single take-off and takes energy consumption into account. A multi-UAV task allocation model and a vehicle path planning model were established to determine the task allocation of the UAVs as well as the path of UAVs and the vehicle, respectively. The model also considered the impact of changing the payload of the UAV on energy consumption, bringing the results closer to reality. Finally, a hybrid heuristic algorithm based on an improved K-means algorithm and ant colony optimization (ACO) was proposed to solve the problem, and the effectiveness of the scheme was proven by multi-scale experimental instances and comparative experiments.
Keywords: instant delivery; unmanned aerial vehicle; vehicle routing problem.