python - 使用 Google OR 工具解决车辆路径问题 (CVRPTW) 所需的时间取决于车辆容量的排序
问题描述
我试图通过结合官方文档中提供的示例中的 CVRP 和 VRPTW 来创建 CVRPTW 解决方案。
由于代码很大，我无法将其粘贴在这里，所以我分享了一个 colab 笔记本，演示了一个重现问题的简短示例： https ://colab.research.google.com/drive/1YN-6kABqGqSkQKxOtWD6YA2ZDlP8RfqD?usp=sharing
在每个节点交付的数量是[0, 80, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1]
我有 22 辆车，21 辆容量为 25 的车辆和 1 辆容量为 600 的车辆。如果车辆按升序排序，则具有 14 个节点的示例需要 200 多秒才能解决，如果它们按降序排序，则相同的示例得到解决不到一秒钟。
我是第一次使用 Google OR Tools，所以我不知道这是否是预期的。我也尝试过添加引导式本地搜索，但是当我添加时间限制以停止它时，它会停止而没有给出解决方案。
我在 repo 中创建了一个问题，但它被转换为讨论。
https://github.com/google/or-tools/discussions/2554
我也在官方邮件列表中问过这个问题。
解决方案
这是 OR 求解器的一个众所周知的特性。因为它们包含许多启发式方法，所以它们对模型中变量或约束的顺序非常敏感。