Nous proposons de reformuler le VRPBB comme un problème de partitionnement d'ensembles que nous optimisons à l'aide d'une approche (heuristique) de génération de colonnes. Des fourmis collectrices génèrent et collectionnent des colonnes (tournées) de façon heuristique, tout en étant guidées par des dépôts de phéromones provenant d'un oracle externe. Cet oracle calcule les dépôts de phéromones en fonction de la solution actuelle à la relaxation du problème. L'approche nous permet d'améliorer de manière itérative la borne inférieure du problème considéré. Une solution entière est trouvée en résolvant le problème de partitionnement d'ensembles avec solveur MIP. Cet article présente trois contributions. D'abord, nous proposons un nouveau problème générique, le problème de tournées de véhicules avec faisabilité boîte noire, qui permet de représenter des problèmes de tournées de véhicules exigeant la résolution d'un problème combinatoire par tournée. Deuxièmement, nous proposons un algorithme pour résoudre ce problème générique. Notre méthode est donc indépendante du problème combinatoire à résoudre pour chaque tournée. Elle peut facilement être appliquée à un nouveau problème en utilisant une autre fonction de faisabilité boîte noire. Enfin, nous démontrons l'applicabilité de la méthode proposée sur deux problèmes, le VRP avec chargement en trois dimensions (3L-CVRP) et le VRP à piles multiples (MP-VRP). Nous comparons nos résultats avec ceux des approches dédiées existantes pour montrer que notre approche générique est très compétitive.