Abstract FR:

L'objet de cette these est le traitement de contraintes sur les graphes dans le cadre de la programmation par contraintes (ppc). L'importance de la problematique de recouvrement d'un graphe par des circuits est isolee afin de pouvoir satisfaire de nombreuses demandes industrielles modelisees en ppc, notamment pour les tournees. Nous presentons la contrainte dite cycle qui constitue une reponse a ces besoins. La premiere variante cycle (n, g, w, min, max) etablie que la contrainte doit satisfaire le partitionnement des nuds d'un graphe oriente g par n circuits disjoints dont la somme des poids w des nuds varie entre min et max. Cependant, pour repondre aux particularites industrielles, une serie de concepts a ete introduits sous forme de parametres additionnels ; des precedences indirectes raisonnent sur une vision temporelle, une matrice de distances apporte une vision geographique ; des capacites, positives ou negatives, appliquees aux nuds du graphe etendent une vision cumulative. La prise en compte des contraintes reglementaires conduit a la definition des concepts de motifs et de shift. L'apparition de certains motifs sur les cheminements est interdite par le parametre sequence ; quant au parametre shift, il permet la gestion d'insertion de repos obligatoires entre des periodes de travail. D'un point de vue academique, la contrainte cycle permet de resoudre des problemes reputes difficiles. De plus, des resultats interessants ont ete mis a jour sur le cavalier d'euler generalise. D'un point de vue pratique, la contrainte cycle a servit pour la realisation d'applications industrielles dans le domaine des problemes de tournees de vehicules, de chargement/dechargement, de sequencement de production et des rotations d'equipage. Ces travaux de these realises dans le cadre de la programmation par contraintes, motives par des besoins industriels ont permis a la fois de revisiter certains algorithmes de graphes tout en cherchant un equilibre entre expressivite et performance.