基于CP-SAT的TSP：如何设置节点特定访问时序约束

原tsp_sat.py示例中已经内置了用于子回路消除的u数组变量，它本质就是节点的访问顺序标记，无需额外定义新的时间戳变量（这是你之前性能差的核心原因）。直接复用u变量即可高效实现你的约束需求：

1. 固定节点为特定访问位置 #

以“节点15为第4个访问节点”为例：

• 原代码默认起点（如节点0）的u值为0，对应第1个访问节点；第k个访问节点的u值为k-1。
• 添加约束直接固定u值：

# 节点15是第4个访问节点 → u值为3
model.Add(u[15] == 3)

如果你的计数习惯是第1个节点u值为1，需先调整起点约束：

model.Add(u[0] == 1)
model.Add(u[15] == 4)

2. 限制节点最晚访问时序 #

以“节点9最晚在第5个被访问”为例：

• 同样基于u变量的顺序含义，添加上限约束：

# 节点9最晚第5个访问 → u值不能超过4（对应起点u=0的计数规则）
model.Add(u[9] <= 4)

若起点u值为1，则约束改为model.Add(u[9] <= 5)。

性能优化建议（针对150节点场景） #

• 破除对称性：固定起点的u值（如u[0] =0），避免求解器遍历对称路径，大幅减少搜索空间。
• 设置求解参数：给求解器添加时间限制、启用启发式搜索：

solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 600.0  # 10分钟超时
solver.parameters.search_branching = cp_model.PORTFOLIO_SEARCH  # 启用多策略搜索
solver.parameters.num_search_workers = 4  # 启用并行搜索（根据CPU核心数调整）

• 约束优先级：将访问顺序类约束标记为硬约束，确保求解器优先满足。

内容的提问来源于stack exchange，提问作者BRaabe99