Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

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

Résumé : 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.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inrae.fr/hal-02733550
Déposant : Migration Prodinra <>
Soumis le : mardi 2 juin 2020 - 12:47:18
Dernière modification le : lundi 23 novembre 2020 - 10:07:07
Archivage à long terme le : : mercredi 2 décembre 2020 - 12:51:03

Fichier

publis17-mistea-032_briot_cont...
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-02733550, version 1
  • PRODINRA : 457300

Citation

Nicolas Briot, Philippe Vismara, Christian Bessière. Une contrainte de circuit adaptée aux tournées multiples. 13. Journées Francophones de Programmation par Contraintes (JFPC 2017), Jun 2017, Montreuil-sur-Mer, France. 275 p. ⟨hal-02733550⟩

Partager

Métriques

Consultations de la notice

16

Téléchargements de fichiers

15