Dans cet article, nous résolvons un problème intégré d'ordonnancement et de routage sans conflits d'une flotte de chariots dans une mine souterraine. Nous présentons un algorithme de décomposition hybride qui combine la programmation par contraintes (PC) et la programmation linéaire en nombre entiers (PLNE). Notre approche décompose le problème en deux parties : la première partie consiste en l'ordonnancement des tâches de chargement et déchargement de minerai tandis que la seconde partie s'occupe du routage sans conflits des chariots avec prise en compte de l'orientation des pelles mécaniques des chariots. Le réseau de galeries de la mine souterraine est en forme d'arbre. La partie ordonnancement est modélisée en PC avec un traitement préventif des conflits tandis que le routage sans conflits est modélisé en PLNE. En outre, le modèle de PLNE assure une orientation cohérente des chariots aussi bien aux points de chargement/déchargement que pendant leur routage. Nous avons testé notre algorithme sur trois réseaux de galeries différents pour analyser certains scénarios comme la croissance de la mine et la non disponibilité partielle ou totale de galeries suite à des événements imprévus (bris de chariots, chutes de roches, fuites d’eau etc.). Notre méthode de décomposition constitue un outil de dimensionnement de flotte de chariots dans une mine souterraine.