Sequence Variables: A Constraint Programming Computational Domain for Routing and Sequencing
Constraint Programming (CP) offers an intuitive, declarative framework for modeling Vehicle Routing Problems (VRP), yet classical CP models based on successor variables cannot always deal with optional visits or insertion based heuristics. To address these limitations, this paper formalizes sequence variables within CP. Unlike the classical successor models, this computational domain handle optional visits and support insertion heuristics, including insertion-based Large Neighborhood Search. We provide a clear definition of their domain, update operations, and introduce consistency levels for constraints on this domain. An implementation is described with the underlying data structures required for integrating sequence variables into existing trail-based CP solvers. Furthermore, global constraints specifically designed for sequence variables and vehicle routing are introduced. Finally, the effectiveness of sequence variables is demonstrated by simplifying problem modeling and achieving competitive computational performance on the Dial-a-Ride Problem.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
GPU Accelerated Compact-Table Propagation
Constraint Programming developed within Logic Programming in the Eighties; nowadays all Prolog systems encompass modules capable of handling constraint programming on finite domains demanding their solution to a constrai…
NP-hardness of sortedness constraints
In Constraint Programming, global constraints allow to model and solve many combinatorial problems. Among these constraints, several sortedness constraints have been defined, for which propagation algorithms are availabl…
Domain Views for Constraint Programming
Views are a standard abstraction in constraint programming: They make it possible to implement a single version of each constraint, while avoiding to create new variables and constraints that would slow down propagation.…
Bounds of MIN_NCC and MAX_NCC and filtering scheme for graph domain variables
Graph domain variables and constraints are an extension of constraint programming introduced by Dooms et al. This approach had been further investigated by Fages in its PhD thesis. On the other hand, Beldiceanu et al. pr…
A global constraint for closed itemset mining
Discovering the set of closed frequent patterns is one of the fundamental problems in Data Mining. Recent Constraint Programming (CP) approaches for declarative itemset mining have proven their usefulness and flexibility…