La génération de colonnes est une méthode dédiée à la résolution de problèmes d'optimisation combinatoire de grande taille. Les méthodes utilisant cette approche de résolution ont souvent des problèmes de convergence, particulièrement lorsqu'elles sont utilisées pour résoudre des problèmes pratiques de très grandes dimensions. Nous nous sommes intéressés dans cette thèse à l'accélération de la méthode de génération de colonnes. Nous avons proposé des techniques de diversification pour diminuer le nombre total de colonnes générées ainsi que le temps de résolution des problèmes maîtres. Nous nous sommes également intéressés à la résolution efficace des sous-problèmes en utilisant des techniques de ré-optimisation, mais aussi en proposant des améliorations de la méthode de programmation dynamique. Ces approches ont été validées expérimentalement sur le problème de tournées de véhicules avec fenêtres de temps.