La plupart des compagnies distribuant de l’huile de chauffage résolvent des problèmes de tournées de véhicules presque quotidiennement. Ces problèmes peuvent impliquer différentes caractéristiques telles qu’une flotte de véhicules hétérogène, plusieurs dépôts, des ravitaillements intra-route, des fenêtres de temps, des quarts de travail pour les chauffeurs et des clients optionnels. Dans cet article, nous considérons un tel problème de tournées de véhicules qui survient en pratique et nous développons trois métaheuristiques pour le traiter, notamment, un algorithme de recherche avec tabous (ts), une heuristique de recherche à grands voisinages (lns) faisant appel à cet algorithme ts, et une autre heuristique lns basée sur une heuristique de génération de colonnes (cg). Des résultats numériques obtenus sur des instances provenant de données réelles indiquent que les méthodes lns sont plus performantes que l’heuristique ts. De plus, la méthode lns basée sur cg a tendance à produire des résultats de meilleure qualité que l’heuristique lns combinée à ts, en particulier lorsqu’il y a suffisamment de temps de calcul disponible.