State-of-the-art exact methods for solving vehicle routing problems rely on a dynamic program that enumerates the set of feasible routes and their distances. Using relaxations of the dynamic program improves these exact methods. This work is motivated by two observations. First, the dynamic program enumerates some routes with a suboptimal permutation of the locations. Second, the relaxations only relax the feasibility of routes and maintain their exact distances. We propose a novel dynamic program that enumerates the feasible sets of locations that can be visited on a route and associates with each set the distance of a route with an optimal permutation of the locations. We develop relaxations of our novel dynamic program that relax both the feasibility and distances of the routes. We embed the dynamic program in an arc-flow formulation and use relaxations to compute dual bounds for the capacitated vehicle routing problem. We give experimental results for instances with up to 10,000 locations and are the first to compute dual bounds for the XL set of benchmark instances.