For vehicle routing problems, strong dual bounds on the optimal value are needed to develop scalable exact algorithms, as well as to evaluate the performance of heuristics. In this work, we propose an iterative algorithm to compute dual bounds motivated by connections between decision diagrams (DDs) and dynamic programming (DP) models used for pricing in branch-and-cut-and-price algorithms. We apply techniques from the DD literature to generate and strengthen novel route relaxations for obtaining dual bounds, without using column generation. Our approach is generic and can be applied to various vehicle routing problems where corresponding DP models are available. We apply our framework to the traveling salesman with drone problem, and show that it produces dual bounds competitive to those from the state-of-the-art. Applied to larger problem instances where the state-of-the-art approach does not scale, our method outperforms other bounding techniques from the literature.