Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inrae.fr/hal-02733550
Contributor : Migration Prodinra <>
Submitted on : Tuesday, June 2, 2020 - 12:47:18 PM
Last modification on : Tuesday, February 16, 2021 - 3:30:33 AM
Long-term archiving on: : Wednesday, December 2, 2020 - 12:51:03 PM

File

publis17-mistea-032_briot_cont...
Publisher files allowed on an open archive

Identifiers

  • 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èmes Journées Francophones de Programmation par Contraintes (JFPC 2017), Jun 2017, Montreuil-sur-Mer, France. pp.135-144. ⟨hal-02733550⟩

Share

Metrics

Record views

49

Files downloads

16