如何处理Google OR Tools中用浮点数求解VRPTW的输出异常问题

问题原因 #

该异常确实是由于时间矩阵使用了浮点数，且时间单位未做统一转换导致的。Google OR-Tools路由求解器底层运算仅支持整型数值，传入浮点数会出现隐式类型转换错误、精度丢失，再加上时间单位为小时但没有和时间窗的单位做统一映射，才会出现车辆停在起点却显示耗时7分钟的异常结果。

单位转换方法 #

你只需要把所有时间相关的参数统一转换为分钟单位的整型数值即可，转换逻辑如下：

• 时间矩阵转换 #

  每个浮点型的小时数值乘以60后取整即可，为避免精度丢失建议用四舍五入处理，Python示例代码：

  # 原时间矩阵，单位：小时，浮点型
  time_matrix = [[0.0, 1.5666666666666667, 1.3166666666666667, ...], ...]
  # 转换后时间矩阵，单位：分钟，整型
  time_matrix_min = [[round(t * 60) for t in row] for row in time_matrix]
  

• 时间窗转换 #

  原时间窗的起止时间都是小时单位的整型，直接乘以60即可得到分钟单位的时间窗，Python示例代码：

  # 原时间窗，单位：小时，整型
  time_windows = [[7, 24], [8, 18], [8, 18], ...]
  # 转换后时间窗，单位：分钟，整型
  time_windows_min = [[tw[0] * 60, tw[1] * 60] for tw in time_windows]
  

后续注意事项 #

• 转换完成后，所有传入求解器的时间相关参数（回调返回值、时间维度上限等）都要统一使用分钟单位的整型
• 输出结果时如果需要还原为小时单位，将分钟数值除以60即可得到原本的小时计量值

内容的提问来源于stack exchange，提问作者vojtam