We propose a heuristic algorithm capable of handling eight possible versions of the vehicle routing problems with drones (VRPD). These are characterized according to three axes, 1) single or multiple trucks each equipped with a single drone, 2) allowing the drone to land and wait or not, and 3) minimizing the transportation cost or minimizing the makespan. One of our main algorithmic contributions relates to a subproblem of the VRPD, which we refer to as the fixed route drone dispatch problem (FRDDP). Given a sequence of customers being visited by a truck, the FRDDP determines a subset of customers to be visited by the drone. Solving the FRDDP exactly with dynamic programming entails a computational complexity of Opn 3 q, where n is the number of customers contained in the route. Considering that the FRDDP is very frequently solved in local search algorithms, we introduce a heuristic dynamic program (HDP) with a computational complexity of Opn 2 q for each of the two FRDDP objectives. We embed HDPs in a hybrid variable neighborhood search algorithm, which we reinforce by developing filtering strategies based on the HDP. We compare via seven benchmarks the performance of our algorithm on four versions of the VRPD that have been studied in the literature. Considering the VRPD with minimizing the transportation cost, our method identifies new best-known solutions for 42 of 112 instances. For the VRPD with minimizing the makespan, our method computes 607 out of 644 optimal solutions and identifies 119 new best-known solutions among the 798 instances.