Skip to Main content Skip to Navigation
Conference papers

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

Nicolas Briot 1 Christian Bessière 1 Philippe Vismara 1
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Résumé : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01711547
Contributor : Joël Quinqueton <>
Submitted on : Thursday, October 18, 2018 - 11:11:18 AM
Last modification on : Thursday, May 14, 2020 - 6:58:06 PM
Long-term archiving on: : Saturday, January 19, 2019 - 1:12:30 PM

File

JFPC_2017_paper_26.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-01711547, version 1

Collections

Citation

Nicolas Briot, Christian Bessière, Philippe Vismara. Une contrainte de circuit adaptée aux tournées multiples. JFPC: Journées Francophones de Programmation par Contraintes, Jun 2017, Montreuil-sur-Mer, France. pp.137-144. ⟨lirmm-01711547⟩

Share

Metrics

Record views

142

Files downloads

41