Vehicle routing problems (VRPs) are challenging combinatorial optimization problems that, given their significant impact on distribution logistics, continue to attract considerable research efforts to develop efficient and effective solution methods. As the instance size grows, the combinatorial nature of these problems makes traditional approaches unable to find adequate solutions within a reasonable computing time. Large problem instances typically require the use of specialized scalability techniques that, coupled with the raw computing power of modern machines, make their heuristic resolution possible. This chapter reviews some of the most effective techniques for designing heuristics for large-scale VRPs.