Dans ces travaux, nous introduisons des méthodes incomplètes pour traiter des problèmes de voyageur de commerce où une fenêtre temporelle est associée à chaque client à visiter, et où les temps de transition entre visites peuvent être dépendants du temps. Pour les problèmes statiques, nous utilisons une recherche à voisinage large qui exploite intensivement un graphe de précédences obligatoires entre visites de clients. Pour les problèmes dynamiques, nous utilisons une combinaison entre une méthode gloutonne très rapide et une recherche à voisinage large. Ces approches ont été implémentées et testées, ce qui a permis de démontrer leur efficacité.