The Capacitated Vehicle Routing Problem (CVRP) is a classic combinatorial optimization problem, for which many heuristics, relaxations and exact algorithms have been proposed. Since the CVRP is NP-hard in the strong sense, a natural research topic is relaxations that can be solved in pseudo-polynomial time. We consider four relaxations of this kind, all of which are based on column generation, and two of which are completely new. Computational experiments demonstrate that the strongest of our relaxations yields very tight lower bounds in reasonable computing times. This work is a continuation of a previous work published in EJOR 244 (2015) 730-738. doi:10.1016/j.ejor.2015.02.028