OR-Tools中VRPTW时间窗口需为整数的原因及小数窗口实现方法

为什么时间窗口必须是整数？ #

• OR-Tools的VRPTW实现（尤其是基于CP-SAT的求解逻辑）默认将时间变量定义为整数类型。这是因为整数规划求解器处理整数变量时效率更高，且能完全规避浮点数运算带来的精度误差问题。
• 底层约束的比较、计算逻辑都是基于整数设计的，直接传入小数时间窗会触发类型校验，也就是你遇到的time windows are expected to be integers报错。

如何实现小数时间窗口？ #

核心解决方案是时间单位缩放：把所有带小数的时间参数统一转换为整数单位，求解完成后再反向转换回原时间格式。具体步骤如下：

1. 确定缩放倍数 #

根据你的精度需求选择缩放比例：

• 若需要精确到分钟，将小时转换为分钟（缩放60倍）
• 若需要精确到秒，将小时转换为秒（缩放3600倍）

2. 统一转换所有时间参数 #

所有和时间相关的参数（时间窗、服务时间、行驶时间）都要同步缩放：

• 示例：7:30am → 7×60+30=450分钟；10:30am →10×60+30=630分钟，用(450, 630)作为整数时间窗
• 服务时间如果是0.5小时（30分钟），直接写30
• 行驶时间如果是1.2小时（72分钟），直接写72

3. 求解后反向转换时间结果 #

得到求解器输出的整数时间后，除以缩放倍数即可还原为原时间单位。

代码示例（Python） #

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def create_data_model():
    data = {}
    # 以分钟为单位（缩放60倍）
    data['time_windows'] = [
        (0, 0),  # 起点时间窗
        (450, 630),  # 对应原时间7:30-10:30
        (540, 720),  # 对应原时间9:00-12:00
    ]
    data['service_time'] = [0, 30, 20]  # 服务时间（分钟）
    data['travel_time'] = [
        [0, 60, 90],  # 行驶时间（分钟）
        [60, 0, 45],
        [90, 45, 0],
    ]
    data['num_vehicles'] = 1
    data['depot'] = 0
    return data

def main():
    data = create_data_model()
    manager = pywrapcp.RoutingIndexManager(
        len(data['time_windows']), data['num_vehicles'], data['depot']
    )
    routing = pywrapcp.RoutingModel(manager)

    # 时间回调函数：行驶时间+服务时间
    def time_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['travel_time'][from_node][to_node] + data['service_time'][to_node]

    transit_callback_index = routing.RegisterTransitCallback(time_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # 添加时间窗约束维度
    time_dim = routing.AddDimension(
        transit_callback_index,
        30,  # 最大等待时间（分钟）
        1440,  # 车辆总工作时长上限（24小时=1440分钟）
        False,
        'Time'
    )

    # 为每个节点设置时间窗
    for loc_idx, time_window in enumerate(data['time_windows']):
        if loc_idx == data['depot']:
            continue
        index = manager.NodeToIndex(loc_idx)
        time_dim.CumulVar(index).SetRange(time_window[0], time_window[1])

    # 设置求解策略
    search_params = pywrapcp.DefaultRoutingSearchParameters()
    search_params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC

    # 求解并输出结果
    solution = routing.SolveWithParameters(search_params)
    if solution:
        print('车辆路径及到达时间：')
        index = routing.Start(0)
        while not routing.IsEnd(index):
            node_idx = manager.IndexToNode(index)
            time_var = time_dim.CumulVar(index)
            # 转换回小时格式，保留1位小数
            arrival_hour = solution.Min(time_var) / 60
            print(f'节点 {node_idx}：{arrival_hour:.1f} 小时')
            index = solution.Value(routing.NextVar(index))
        # 输出终点时间
        node_idx = manager.IndexToNode(index)
        time_var = time_dim.CumulVar(index)
        arrival_hour = solution.Min(time_var) / 60
        print(f'节点 {node_idx}：{arrival_hour:.1f} 小时')

if __name__ == '__main__':
    main()

注意事项 #

• 所有时间相关参数必须使用相同的缩放单位，避免因单位不一致导致逻辑错误
• 缩放倍数越大（比如秒级），求解器计算量会增加，需要平衡精度和求解效率
• 若需要转换为时分格式（如7:30），可以将整数时间（分钟）进一步拆分：小时 = 总分钟 // 60，分钟 = 总分钟 % 60

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