Loading...
Please wait, while we are loading the content...
Similar Documents
Introduction de contraintes structurelles pour la résolution du problème du voyageur de commerce
| Content Provider | Semantic Scholar |
|---|---|
| Author | Isoart, Nicolas Régin, Jean-Charles |
| Copyright Year | 2019 |
| Abstract | Plusieurs modeles bases sur la programmation par contraintes ont ete proposes pour resoudre le probleme du voyageur de commerce (TSP). Les plus efficaces, telle que la weighted circuit constraint (WCC), s'appuient prin-cipalement sur la relaxation lagrangienne du TSP, basee sur la recherche d'arbres recouvrants ou plus precisement de "one-trees". Le defaut de cette methode est qu'elle n'inclut pas assez de contraintes structurelles et se base presque exclusivement sur les couts des aretes. L'objectif de cet article est de corriger ce defaut. Aussi, nous cherchons des motifs empechant l'existence d'un cycle hamiltonien dans un graphe ou, a l'inverse, des motifs imposant que certaines aretes soient dans l'ensemble de solutions du TSP. Nous proposons un propagateur base sur la recherche de k-cutsets pour la contrainte de cycle hamiltonien. Sa combinaison avec la contrainte WCC permet d'obtenir, pour la resolution du TSP, des gains d'un ordre de magnitude pour le nombre de backtracks ainsi qu'une forte reduction du temps de calcul. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://hal.archives-ouvertes.fr/hal-02160046/file/jfpc.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
