Problématique : Les méthodes de recherche dites incomplètes sont souvent utilisées en pratique pour traiter en temps contraint des problèmes d’optimisation difficiles, en s’appuyant par exemple sur des métaheuristiques type recherche tabou pour s’échapper des optima locaux. Nous nous intéressons ici au développement d’une nouvelle stratégie de recherche permettant d’améliorer la qualité des solutions produites ou de produire ces solutions plus rapidement. L’idée poursuivie consiste à réaliser une recherche incomplète guidée par les conflits rencontrés lors de la résolution, un conflit correspondant dans notre cas à une instanciation d’un sous-ensemble des variables de décision qui conduit à une violation des contraintes du problème ou à une sous-optimalité de la solution. L’objectif est de mémoriser ces conflits sur le long terme et de les utiliser pour d’une part éviter de revisiter inutilement certaines zones de l’espace de recherche et d’autre part tenter d’orienter la recherche vers les solutions les plus prometteuses. Cette idée de recherche guidée par les conflits est à rapprocher de la méthode CDCL (Conflict Driven Clause Learning) travaillant sur des problèmes SAT [1, 2]. La nouvelle méthode proposée est appliquée au problème de routage connu sous le nom d’OPTW (Orienteering Problem with Time Windows[4]), dans lequel un véhicule doit maxi-miser le profit collecté en visitant un sous-ensemble de clients candidats, sachant (1) qu’il existe pour chaque client une fenêtre temporelle autorisée pour la visite, une durée de visite et un profit associé, et (2) qu’un temps de transition est requis pour passer d’un client à un autre.