ORTools 在访问节点上添加约束

Question

我想知道是否可以使用 ORTools VRPTWs 问题为不同的路线设置旅行约束。

例如，如果我有一个节点列表
A、B、C、D、E
其中 C 不能与 D 和 E 一起路由。

因此可能的路线是（仅举几个例子）：

B -> A -> C

A -> B

D -> E

A -> D

B -> E

请注意，没有解决方案包含 C -> [D|E]

如何在 ORTools 中对此类约束进行建模？可能吗？

一些解决方案建议设置节点约束的车辆，例如一半车辆包含C，一半车辆包含D和E。

它有效，但它会生成次优解，因为车辆数量是固定的，约束节点的数量将大于可能的路径数量，从而导致次优解。

Answer 1

你试过了吗：

# C != D
active_c_d = routing.ActiveVar(c) * routing.ActiveVar(d)
routing.solver().Add(
    active_c_d * (routing.VehicleVar(c) - routing.VehicleVar(d)) != (1 - active_c_d))

# C != E
active_c_e = routing.ActiveVar(c) * routing.ActiveVar(e)
routing.solver().Add(
    active_c_e * (routing.VehicleVar(c) - routing.VehicleVar(e)) != (1 - active_c_e))

示例：https://gist.github.com/Mizux/9e37c370a459bd472a6ac13c304f0b54

否则你也可以使用Solver::MakeAllDifferent()进行测试（未测试）

routing.solver().AllDifferent([routing.VehicleVar(c), routing.VehicleVar(d)])
routing.solver().AllDifferent([routing.VehicleVar(c), routing.VehicleVar(e)])

参考：https://github.com/google/or-tools/blob/fa84bc05e72641dddfbb98164d81b8bc9bef6ea5/ortools/constraint_solver/constraint_solver.h#L1500-L1513

ORTools 在访问节点上添加约束

ORTools add constraint on visited nodes

python

or-tools