A hybrid algorithm for drone routing problem with time windows

Drone Routing Problem with Time Window (DRPTW) is an important extension of the logistics service routing optimization problem and has been proved to be an NP-hard problem. In this paper, DRPTW is formulated as a mixed integer nonlinear programming model considering nonlinear energy constraints. To solve this problem efficiently, we propose a hybrid metaheuristic algorithm combined with a genetic algorithm (GA) to generate a set of feasible routes. In addition, we incorporate a tabu search algorithm (TS) that uses a taboo table to store previously encountered solutions, ensuring that the best solution is not overlooked. To evaluate its performance, we test it with Solomon's VRPTW benchmark instances. The results show that a good solution can be obtained within an acceptable computation time. Furthermore, for the solution of the same delivery sequence route, we compared the impact on delivery completion with and without energy constraints, and found that the original delivery solution would be ineffective if the nonlinear energy constraints of the drone are not considered or approximated.