A Collaborative Drone-Truck Delivery System With Memetic Computing Optimization

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.