Vehicle routing problems are among the most widely studied combinatorial optimization problems. Different classes of routing problems exist which all share a common set of decisions: assigning customers to vehicles and defining the sequence of visit for each vehicle, i.e., determining vehicle routes in order to minimize a given cost function. Problems might differ in the objective function and in the presence of additional constraints. However, routing decisions (plus eventually additional problem-specific decisions) make routing problems extremely challenging. For this reason, the research community has concentrated big efforts on the development of efficient heuristic solution approaches. In this chapter, we first briefly introduce the earliest and most classical heuristic algorithms. Then we concentrate on the most recent developments on heuristics for routing problems, namely, metaheuristics, matheuristics, learning approaches, and heuristics for large-scale problems. We provide reference contributions and discuss the key features of each class of methods, concentrating on the most recent research trends.