A Circuit Constraint for Multiple Tours Problems - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

A Circuit Constraint for Multiple Tours Problems

Résumé

Routing problems appear in many practical applications. In the context of Constraint Programming, circuit constraints have been successfully developed to handle problems like the well-known Traveling Salesman Problem or the Vehicle Routing Problem. These kind of constraints are linked to the search for a Hamiltonian circuit in a graph. In this paper we consider a more general multiple tour problem that consists in covering a part of the graph with a set of minimal cost circuits. We define a new global constraint WeightedSubCircuits that generalizes the WeightedCircuit constraint by releasing the need to obtain a Hamil-tonian circuit. It enforces multiple disjoint circuits of bounded total cost to partially cover a weighted graph, the subsets of vertices to be covered being induced by external constraints. We show that enforcing Bounds Consistency for WeightedSubCircuits is NP-hard. We propose an incomplete but polynomial filtering method based on the search for a lower bound of a weighted Steiner circuit.
Fichier principal
Vignette du fichier
vismara_CP2018.pdf (386.45 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-01924361 , version 1 (15-11-2018)

Identifiants

Citer

Philippe Vismara, Nicolas Briot. A Circuit Constraint for Multiple Tours Problems. CP 2018 - 24th International Conference on Principles and Practice of Constraint Programming, Aug 2018, Lille, France. pp.389-402, ⟨10.1007/978-3-319-98334-9_26⟩. ⟨lirmm-01924361⟩
89 Consultations
321 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More