为什么 ORTOOLS 引导本地搜索，从考虑约束规划的可行解决方案开始？

Question

我正在使用ORTOOLS库来解决 VRP 问题。我给它一个初始可行的解决方案来解决我的问题，满足我的问题的所有约束，但不是最优的。然后 ORTOOLS 执行 GUIDED_LOCAL_SEARCH 启发式，不断扰乱我的解决方案的一部分（有时可能使其不可行），直到它有望达到比我的初始解决方案更好的解决方案。

为什么要使用约束规划求解器？我的理解是，经典的约束规划从一个不可行（可能为空）的解决方案开始，传播约束以缩小我的变量的域，直到达到静止状态，然后做出决定。然后它再次迭代，直到解决问题或在到达死胡同时回溯（想想数独）。

在进行小扰动时，这些能力（传播、回溯）以什么方式需要？

Answer 1

有两个原因。

1) 初始解启发式是快速 LS 启发式搜索和标准约束规划搜索的组合。

2) 整个局部搜索实现建立在传统的约束规划求解器之上，并使用约束和传播器来验证解决方案，并完成它们。

请参阅：https : //github.com/google/or-tools/issues/920