We consider a variant of the Vehicle Routing Problem (VRP) where each customer has a unit demand and the goal is to minimize the total cost of routing a fleet of capacitated vehicles from one or multiple depots to visit all customers. We propose two parallel algorithms to efficiently solve the column-generation based linear-programming relaxation for this VRP. Specifically, we focus on algorithms for the ``pricing problem'' which corresponds to the resource-constrained elementary shortest path problem. The first algorithm extends the pulse algorithm by Lozano et al. (2015), for which we derive a new bounding scheme on the maximum load of any route. The second algorithm is based on random coloring from parameterized complexity (Alon et al. (1995)), which can be also combined with other techniques in the literature for improving VRPs, including cutting planes and column enumeration. We conduct numerical studies using VRP benchmarks (with 50--957 nodes) and instances of a medical home care delivery problem using census data in Wayne County, Michigan. Using parallel computing, both pulse and random coloring can significantly improve column generation for solving the linear programming relaxations and we can obtain heuristic integer solutions with small optimality gaps. Combining random coloring with column enumeration, we can obtain improved integer solutions having less than 2\% optimality gaps for most VRP benchmark instances, and less than 1\% optimality gaps for the medical home care delivery instances, both under a 30-minute computational time limit. The use of cutting planes (e.g., robust cuts) can further reduce optimality gaps on some hard instances, without much increase in the runtime.