或工具-车辆路径问题-防止从初始解决方案中删除节点

Question

我们有一个具有时间和容量约束的VRP示例。

我们的场景如下：

• 我们有5辆车

我们的问题是，算法有时在得到新请求时，会丢弃一些我们已经标记为可行并添加到车辆调度中的节点（乘客请求）。如何防止丢弃已经添加到解决方案（然后在初始解决方案中）的节点？

我们尝试从初始解决方案中为节点设置int.max惩罚，并对我们当前添加的节点设置稍微小的惩罚。当已经确认的节点稍后被删除时，它确实减少了事件的数量，但它仍然会发生。我们认为部分解决方案也不是正确的方法，因为如果符合容量和时间限制，车辆必须能够在运输乘客A时接受乘客B。锁定车辆看起来也不合适，因为它阻止我们向已解决的解决方案添加新乘客。

我们只需要一种方法，以某种方式防止某些节点被丢弃。在我们的示例中-已经添加到解决方案中的节点。换句话说，我们的初始解决方案可以更改，但不能删除任何节点。

提前谢谢你的帮助。

Answer 1

我们设法通过删除惩罚来解决这个问题。因为我们为每个请求运行算法，我们的目标是尽可能多地接收客户，所以没有必要使用惩罚。当惩罚未使用或工具将在解决方案不可行时删除所有节点。在我们的例子中，这意味着如果新请求的解决方案不可行，这意味着我们必须拒绝请求。Or-tools将删除所有节点，但我们只是跳过保存新解决方案的部分（在这种情况下——不可行）。这样我们仍然有保存之前的旧可行结果。我们对即将到来的请求使用这个“旧”解决方案。