Une contrainte de circuit adaptée aux tournées multiples - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2017

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.
Fichier principal
Vignette du fichier
JFPC_2017_paper_26.pdf (1.33 Mo) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-01711547 , version 1 (18-10-2018)

Identifiers

  • HAL Id : lirmm-01711547 , version 1
  • PRODINRA : 457300

Cite

Nicolas Briot, Philippe Vismara, Christian Bessiere. Une contrainte de circuit adaptée aux tournées multiples. JFPC 2017 - 13es Journées Francophones de Programmation par Contraintes, Jun 2017, Montreuil-sur-Mer, France. pp.137-144. ⟨lirmm-01711547⟩
192 View
132 Download

Share

More