Une contrainte de circuit adaptée aux tournées multiples

Il existe de nombreuses applications réelles contenant un problème de tournées de véhicules. La programmation par contraintes permet d'aborder ces problèmes de façon efficace. Des contraintes de circuits ont été définies pour traiter du problème de voyageur de commerce (TSP) ou de tournées de véhicules (VRP). Ces contraintes sont basées sur la recherche d'un circuit hamiltonien dans un graphe. Dans cet article, nous nous intéressons au problème plus général de tournées multiples dans lequel on cherche à couvrir une partie du graphe par un ensemble de circuits de coût minimal. Nous proposons une nouvelle contrainte globale basée sur la recherche de circuits élémentaires disjoints dans un graphe. Contrairement aux contraintes existantes, on ne cherche pas un circuit hamiltonien mais un ensemble de circuits de Steiner. Après avoir défini cette contrainte, nous montrons que le filtrage au bornes est NP-difficile. Nous proposons donc une méthode de filtrage incomplète basée sur la recherche d'une borne inférieure d'un circuit de Steiner