Skip to Main content Skip to Navigation
Conference papers

A Circuit Constraint for Multiple Tours Problems

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

Cited literature [18 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01924361
Contributor : Philippe Vismara <>
Submitted on : Thursday, November 15, 2018 - 7:04:05 PM
Last modification on : Monday, January 11, 2021 - 5:24:18 PM

File

vismara_CP2018.pdf
Files produced by the author(s)

Identifiers

Citation

Philippe Vismara, Nicolas Briot. A Circuit Constraint for Multiple Tours Problems. CP: Principles and Practice of Constraint Programming, Aug 2018, Lille, France. pp.389-402, ⟨10.1007/978-3-319-98334-9_26⟩. ⟨lirmm-01924361⟩

Share

Metrics

Record views

184

Files downloads

401