1

我想知道是否可以使用 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。

它可以工作，但它会产生次优解决方案，因为车辆数量是固定的，并且约束节点的数量将大于可能的路线数量，从而导致次优解决方案。

4

1 回答 1

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

于 2021-03-23T08:16:22.963 回答