OR-Tools VRP框架中如何实现节点集合的互斥路径？

要实现**要么访问集合[0,1,2,6]，要么访问集合[3,4,5,6]**的互斥逻辑，不能直接用AddDisjunction（它仅支持单个节点的可选访问），需要通过自定义约束控制整个节点集合的访问状态，具体步骤如下：

核心思路 #

1. 强制节点6必须被访问（因为两个路径都包含它）；
2. 约束集合[0,1,2]的节点要么全被访问，要么全不访问；
3. 约束集合[3,4,5]的节点要么全被访问，要么全不访问；
4. 添加互斥约束：两个集合只能二选一被访问。

代码实现示例 #

# 假设已初始化manager和routing对象
solver = routing.solver()

# 1. 映射地点到路由索引
node0 = manager.NodeToIndex(0)
node1 = manager.NodeToIndex(1)
node2 = manager.NodeToIndex(2)
node3 = manager.NodeToIndex(3)
node4 = manager.NodeToIndex(4)
node5 = manager.NodeToIndex(5)
node6 = manager.NodeToIndex(6)

set_a = [node0, node1, node2]  # 第一个互斥集合
set_b = [node3, node4, node5]  # 第二个互斥集合

# 2. 强制访问节点6（惩罚设为0表示必须访问）
routing.AddDisjunction([node6], 0)

# 3. 约束集合A的节点必须同访问/同不访问
a_switch = solver.BoolVar("visit_set_a")
for node in set_a:
    # 将节点的访问状态与集合开关变量绑定
    solver.Add(routing.ActiveVar(node) == a_switch)

# 4. 约束集合B的节点必须同访问/同不访问
b_switch = solver.BoolVar("visit_set_b")
for node in set_b:
    solver.Add(routing.ActiveVar(node) == b_switch)

# 5. 添加互斥约束：只能选择其中一个集合
solver.Add(a_switch + b_switch == 1)

关键说明 #

• routing.ActiveVar(node)：OR-Tools内置布尔变量，值为1表示节点被访问，0表示未被访问；
• 集合开关变量a_switch/b_switch：控制整个集合的访问状态，确保集合内所有节点的访问状态一致；
• 最后的互斥约束a_switch + b_switch == 1：保证两个集合只能有一个被激活访问。

配置完成后，求解器会自动生成符合要求的路径：要么包含[0,1,2,6]，要么包含[3,4,5,6]，且路径顺序会自动优化。

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