Une contrainte de circuit adaptée aux tournées multiples
Abstract
Il existe de nombreuses applications r´eelles contenant un probl`eme de tourn´ees de v´ehicules. La programmation par contraintes permet d’aborder ces probl`emes de fa¸con efficace. Des contraintes de circuits ont ´et´e d´efinies pour traiter du probl`eme de voyageur de commerce (TSP) ou de tourn´ees de v´ehicules (VRP). Ces contraintes sont bas´ees sur la recherche d’un circuit hamiltonien dans un graphe. Dans cet article, nous nous int´eressons au probl`eme plus g´en´eral de tourn´ees multiples dans lequel on cherche `a couvrir une partie du graphe par un ensemble de circuits de coˆut minimal. Nous proposons une nouvelle contrainte globale bas´ee sur la recherche de circuits ´el´ementaires disjoints dans un graphe. Contrairement aux contraintes existantes, on ne cherche pas un circuit hamiltonien mais un ensemble de circuits de Steiner. Apr`es avoir d´efini cette contrainte, nous montrons que le filtrage au bornes est NP-difficile. Nous proposons donc une m´ethode de filtrage incompl`ete bas´ee sur la recherche d’une borne inf´erieure d’un circuit de Steiner.
Domains
Artificial Intelligence [cs.AI]Origin | Files produced by the author(s) |
---|
Loading...