The multi-visit parallel drone scheduling pickup and delivery problem considering multiple trips and time windows

We study a new variant of the parallel drone scheduling vehicle routing problem with time windows, where multiple homogeneous trucks and drones operate in parallel to provide parcel pickup and delivery services to customers with the minimum total cost. Additionally, some paired customer requests where each package must be shipped from a pickup customer to another delivery customer by the same vehicle are considered. Each drone has the ability to serve multiple customers in a trip and can make multiple trips to increase utilisation. To better model reality, we propose a large-scale mixed-integer bilinear program that uses a bilinear term to define the energy consumed by drones while hovering at customer locations due to time windows. Later, several strengthening inequalities are added to accelerate the model-solving process. To handle large-size problems, we develop a metaheuristic based on the large neighbourhood search concept with custom destroy and repair operators and complementary local searches, embedding acceleration strategies to avoid infeasible searches. Moreover, a novel algorithm is designed to efficiently optimise the drone waiting times at the depot for each trip, which is key to the problem solution given the constraints of time windows. Finally, various numerical tests and comparisons demonstrate the superior performance of the developed metaheuristic and confirm the effectiveness of strengthening inequalities in model solving. The results highlight the superiority of the parallel mode in terms of cost reduction over the truck-only mode and the advantages of considering drone waiting times and allowing multiple drone visits and trips. Our algorithm outperforms the benchmark algorithms in the literature. The average gaps related to the solution quality from the improved large neighbourhood search are approximately 5%.