提出序列变量新范式，让路径规划模型更灵活高效。
Sequence Variables: A Constraint Programming Computational Domain for Routing and Sequencing
- 用序列变量替代传统后继变量，支持可选访问和插入启发式
- 在拼车问题上简化建模并达到竞争力求解性能
- 适合需要动态路径调整的物流与调度场景
约束编程（CP）为车辆路径问题（VRP）提供了直观的声明式建模框架，但基于后继变量的经典CP模型难以处理可选访问或基于插入的启发式方法。本文在CP中正式定义了序列变量这一计算域，其不仅能处理可选访问，还支持插入类启发式算法，包括基于插入的大邻域搜索（Large Neighborhood Search）。论文给出了序列变量的定义、更新操作，并引入了该域上的一致性级别。文章描述了实现方案及集成到现有基于轨迹的CP求解器所需的数据结构。此外，设计了专用于序列变量和车辆路径问题的全局约束。最终实验表明，序列变量能显著简化问题建模，并在拼车问题（Dial-a-Ride Problem）上实现具有竞争力的计算性能。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。