使用 Google OR 工具解决车辆路径问题 (CVRPTW) 所花费的时间取决于车辆容量的排序
Time taken to solve a Vehicle Routing Problem (CVRPTW) using Google OR Tools depends on the ordering of vehicle capacity
我尝试通过结合官方文档中提供的示例中的 CVRP 和 VRPTW 来创建 CVRPTW 解决方案。
由于代码太大，我无法将其粘贴在这里，所以我分享了一个 colab notebook，演示了一个重现问题的简短示例：
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 工具，所以我不知道这是否符合预期。我也尝试过添加 Guided Local Search，但是当我添加一个时间限制来停止时，它会在没有给出解决方案的情况下停止。
我在回购中创建了一个问题，但它被转换为讨论。
https://github.com/google/or-tools/discussions/2554
这个问题我也在官方邮件列表里问过
这是众所周知的 属性 OR 求解器。
因为它们包含很多启发式方法，所以它们对模型中变量或约束的顺序非常敏感。
我尝试通过结合官方文档中提供的示例中的 CVRP 和 VRPTW 来创建 CVRPTW 解决方案。
由于代码太大，我无法将其粘贴在这里，所以我分享了一个 colab notebook，演示了一个重现问题的简短示例： 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 工具，所以我不知道这是否符合预期。我也尝试过添加 Guided Local Search，但是当我添加一个时间限制来停止时，它会在没有给出解决方案的情况下停止。
我在回购中创建了一个问题，但它被转换为讨论。
https://github.com/google/or-tools/discussions/2554
这个问题我也在官方邮件列表里问过
这是众所周知的 属性 OR 求解器。 因为它们包含很多启发式方法，所以它们对模型中变量或约束的顺序非常敏感。