Ce mémoire traite de méthodes arborescentes pour la résolution de problèmes combinatoires d’optimisation ou de décision. Le premier chapitre présente les contributions apportées pour les méthodes à divergences : modes de comptage, heuristique dynamique à pondération de variables et utilisation de bornes ou de règles de sélection des divergences. Le deuxième chapitre traite de propagation de contraintes pour l’ordonnancement disjonctif avec contraintes temporelles généralisées. Des extensions de propagations efficaces pour ces contraintes sont proposées et des applications à la résolution de différents problèmes pratiques d’ordonnancement sont présentées. Le troisième chapitre s’intéresse à un problème de calcul d’itinéraires en transport multimodal intégrant des contraintes de faisabilité des itinéraires. Le problème étudié (minimisation du temps de trajet et du nombre de transferts) est polynomial et différentes variantes basées sur l’algorithme de Dijkstra sont présentées et évaluées sur un cas réel.