or-tools - 为什么路由求解器不使用所有可用时间？

Question

我正在尝试解决具有数百个取货和交付限制、时间窗口和需求的大型路由问题。在 2 秒内，求解器状态“未找到分配”。当然，如果它继续寻找解决方案的时间更长一点，它可能会找到一个解决方案吗？或者，如果它有证据证明问题不可行，它可以提供一些细节？这里发生了什么？

标签： or-toolsvehicle-routing

Answer 1

求解器使用不同的状态码，您可以在官方文档中看到：https ://developers.google.com/optimization/routing/routing_options 。

FAIL 有两种不同的状态：ROUTING_FAIL_TIMEOUT 和 ROUTING_FAIL，因此求解器证明不可行似乎是合理的。然而，求解器依赖于启发式算法来寻找初始解决方案并改进现有解决方案，同时依赖于约束编程技术（例如传播）来检查分配是否可行。

对于复杂的 VRP 问题，证明不可行是非常困难的，因为您需要识别一些相互不可行的约束子集，并能够推断出没有解决方案可以同时满足它们。即使对于 3-SAT 来说，这也是一个 NP 完全问题，虽然您通常可以在实践中对 SAT 问题执行此操作，但当变量的域很大时，这会变得非常困难。因此，我怀疑当求解器失败时是否存在您意义上的证据，而是“启发式”失败。

关于详细信息，可以通过 SearchLog 或 InitGoogleLogging 记录搜索。查看nurses_cp.cpp 示例： google::InitGoogleLogging(argv[0]);