A Circuit Constraint for Multiple Tours Problems - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2018

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

Dates and versions

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

Identifiers

Cite

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⟩
86 View
315 Download

Altmetric

Share

Gmail Facebook X LinkedIn More