本文介绍一种巧妙利用计数维度（count dimension）在 or-tools 的 cp-sat 或 routing solver 中建模“条件性连续访问”约束的方法：当某组关键点（如 a、c、e）中任一被访问，则其余必须紧邻访问、中间不得插入其他非组内点。
本文介绍一种巧妙利用计数维度（count dimension）在 or-tools 的 cp-sat 或 routing solver 中建模“条件性连续访问”约束的方法：当某组关键点（如 a、c、e）中任一被访问，则其余必须紧邻访问、中间不得插入其他非组内点。
在 OR-Tools 的 RoutingModel 中，原生不支持 OnlyEnforceIf 等逻辑条件约束直接作用于路径顺序（因路由变量为 IntVar 类型的索引链，而非布尔表达式），因此无法直接写出 “若访问 A，则 C 和 E 必须紧邻其后” 这类命题逻辑。但可通过引入计数维度（Count Dimension），将“相对访问顺序”转化为“访问序号差值约束”，从而间接实现目标。
核心思路：用访问序号控制相对位置
为每个节点分配一个全局访问序号（从 0 开始递增），记为 count[i]。若要求集合 S = {A, C, E} 满足“触发即连续”——即只要其中任意一点被访问，其余两点必须在其前后最多间隔 1 个位置（即三者在路径中构成长度 ≤3 的连续子序列，且内部可重排），则只需对每一对节点 (i, j) ∈ S × S 强制：
Skill Weave Chains — 技能链路由引擎
下载
开箱即用的技能链路由引擎。13 条预定义链覆盖搜索、开发、审查、MLOps、法律、创意等场景，三层路由架构（触发词→SAD反馈→DAG编排），recall@10=96.97%。配置驱动（chains.yaml），零代码扩展。pip install skill-weave-chains 一键安装。
model.AddAbs(model.CumulVar(routing.NodeToIndex(i), "count")
- model.CumulVar(routing.NodeToIndex(j), "count")) <p>该约束确保任意两个组内节点的访问序号差不超过 2，从而强制三者在路径中占据至多 3 个连续位置（例如序号 5,6,7 或 5,7,6），天然排除了如 A→D→E 这类被非组内点隔开的情形。</p><h3>实现步骤（Routing Solver 示例）</h3><pre class="brush:php;toolbar:false;">from ortools.constraint_solver import routing_enums_pb2, pywrapcp
# 假设 waypoints 映射为索引：A=0, B=1, C=2, D=3, E=4
waypoint_to_index = {"A": 0, "B": 1, "C": 2, "D": 3, "E": 4}
group = [0, 2, 4] # A, C, E
# 创建模型
routing = pywrapcp.RoutingModel(num_locations, num_vehicles, depot)
transit_callback = ... # 定义距离回调
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback)
# 添加计数维度：每经过一个节点，计数 +1
def count_callback(from_index, to_index):
return 1 # 每条弧贡献 1 单位计数
count_dim_name = "count"
routing.AddDimension(
count_callback,
0, # 容量无硬限制（足够大即可）
len(waypoints), # 最大计数值
True, # 启用起点计数（start_cumul_to_zero=False 可选）
count_dim_name
)
count_dimension = routing.GetDimensionOrDie(count_dim_name)
# 添加组内节点两两序号差 ≤2 的约束
for i in group:
for j in group:
if i != j:
node_i = routing.NodeToIndex(i)
node_j = routing.NodeToIndex(j)
cumul_i = count_dimension.CumulVar(node_i)
cumul_j = count_dimension.CumulVar(node_j)
routing.solver().Add(cumul_i - cumul_j <h3>注意事项与优化建议</h3>
- ✅ 有效性保障：该方法不依赖节点是否实际被访问——若某组内点未被选中（如路径完全绕过 A、C、E），则对应 CumulVar 可能为未激活状态，约束自动失效；仅当至少一个被访问时，差值约束才生效并强制其余进入邻近位置。
- ⚠️ 灵活性权衡：差值上限 2 对应 3 元组的紧密连续；若需更宽松（如允许间隔 1 个非组内点），可改为
- ? 性能提示：对大型组（|S| > 5），O(n²) 约束可能影响求解效率，此时建议结合 AllowedAssignments 或预定义子路径模式（Pattern-Based Routing）进一步建模。
- ? 替代方案：若问题复杂度升高（如多组嵌套约束），推荐迁移到 CP-SAT Solver，直接使用 BoolVar 和 IntervalVar 表达逻辑条件，表达力更强。
综上，借助计数维度将顺序逻辑转化为数值差约束，是 OR-Tools 路由场景下实现条件性连续访问的稳健、高效且易于集成的工程实践。
