A Collaborative Drone-Truck Delivery System With Memetic Computing Optimization
针对无人机与卡车协同配送的路径规划难题，提出一种新的模因算法MATSP-D，通过设计新的解表示和搜索算子，有效处理两者协作，实验表明在大规模复杂实例上显著优于现有方法。
With technological breakthroughs, drone deliveries have become increasingly popular, especially during the COVID-19 pandemic. Driven by both economical benefit and efficiency, drone-truck combined deliveries are in demand. However, it is very challenging to handle the collaboration between trucks and drones. Existing methods for truck-only routing cannot be directly applied, since their solution representations and search operators cannot consider the drone-truck collaborations effectively. In this article, we model the system as traveling salesman problem with drones (TSP-Ds), and propose a new Memetic algorithm named MATSP-D for solving it. Specifically, we design a new drone-truck solution representation and develop new crossover and local search operators under the new representation, which can modify the drone services effectively. MATSP-D conducts exploration by crossover, and exploitation by a variable neighborhood search process. The experimental results show that the proposed MATSP-D significantly outperforms the state-of-the-art algorithms for most test instances, especially the large instances with more complex collaborations between the truck and drone. Further analysis verifies the effectiveness of the newly developed local search operators in searching for better-drone-truck collaborations.