Abstract
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 paper, we model the system as Traveling Salesman
Problem with Drones (TSP-D), 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.