or-tools - 具有自己的元启发式的 Python 上的 Google Or-tools

Question

我想使用 Google OR-Tools 解决车辆路线问题 (vrp)，但使用与所提供的不同的元启发式方法，它们是：贪婪下降、引导本地搜索、模拟退火、禁忌搜索和客观禁忌搜索。这就是此处文档中所解释的内容：https ://developers.google.com/optimization/routing/routing_options

从手册（https://acrogenesis.com/or-tools/documentation/user_manual/manual/metaheuristics/metaheuristics.html）我了解到可以使用我自己的元启发式。此外，我在这里找到了一个可以做到这一点的人：https ://medium.com/gogovan-technology/improving-operations-with-route-optimization-e032d8bf5edc 。但是，我找不到用 python 实现的示例。实际上，我还没有找到任何关于如何使用我自己的元启发式算法的示例。尽管文档和存储库中提供了几个示例（https://github.com/google/or-tools/blob/0777e4d12ff9b45397c3aa6bbe14fc72b19bf453/examples/python/vrp.py），但他们只专注于使用自己的元启发式。

由于我对编码的了解并不高，我需要一些关于如何实现它的指南和想法。有没有人这样做过，可以和我分享一些例子吗？或者你知道我在哪里可以找到一些很好的友好例子吗？非常感谢任何帮助或建议。

标签： or-tools

Answer 1

你必须在适应度（成本）函数上解决它，注意：输入算法在最大和最小解决方案之间是随机的（例如这是问题中的节点在 0 - 100 之间）。算法的输出是适应度函数的结果，以及如何路由的结果以及有关最佳路由的任何事情。所以首先你必须对它的适应度函数提出问题。假设，用于遗传算法的适应度函数 F 是 的线性组合。路线上所有乘客的等待时间向量 w 和旅行时间（距离） d。因此，下层 GA 的目标函数是 F(w,d)= min (sum( c1*w+c2*d)) 所以你必须为算法选择节点....算法选择 1,5, 6,8,8 个节点。并且您必须为此节点计算上述公式。在每次迭代中，您必须为所有人口计算此公式，