基于Google OR-Tools的VRPTW车辆工时约束问题求助

问题根源 #

你代码里的核心错误是混淆了累计行驶时长维度和实际时间戳维度，并且添加了无意义的约束，导致工时调整后求解器出现矛盾无解。

关键修正步骤 #

1. 改用时间维度跟踪实际时间：工时约束是针对车辆的实际工作时间区间，必须用跟踪节点到达时间戳的Time Dimension，而非记录累计行驶时长的Duration Dimension。
2. 关闭起始时间固定为0的设置：OR-Tools默认会把车辆起始节点的累计时间固定为0，这和不同车辆的独立起始工时冲突，必须禁用。
3. 删除无意义约束：你添加的duration_dimension.CumulVar(end_index) - duration_dimension.CumulVar(start_index) <= duration_dimension.CumulVar(end_index)化简后等价于start >=0，完全没必要保留。
4. 正确绑定车辆工时与时间维度：给每个车辆的起始/结束节点设置时间范围，确保出发时间不早于工时开始，返回时间不晚于工时结束。

修正后的代码示例 #

import ortools.constraint_solver.pywrapcp as pywrapcp

# 假设已准备好基础数据
data = {
    "time_matrix": [
        # 节点间行驶时间矩阵，根据你的实际场景填充
        [0, 100, 200],
        [100, 0, 150],
        [200, 150, 0]
    ],
    "time_windows": [
        # 每个节点的时间窗，depot可设为(0, 36000)，任务节点根据需求设置
        (0, 36000),
        (3600, 32400),
        (7200, 32400)
    ],
    "num_vehicles": 3,
    "depot": 0,
    "working_time": [
        (0, 600), 
        (0, 32400), 
        (3600, 36000)  # 第三辆车工时：1小时到10小时
    ]
}

# 初始化路由管理器与模型
manager = pywrapcp.RoutingIndexManager(
    len(data["time_matrix"]),
    data["num_vehicles"],
    data["depot"]
)
routing = pywrapcp.RoutingModel(manager)

# 注册时间回调函数（返回节点间行驶时间）
def time_callback(from_idx, to_idx):
    from_node = manager.IndexToNode(from_idx)
    to_node = manager.IndexToNode(to_idx)
    return data["time_matrix"][from_node][to_node]

transit_callback_idx = routing.RegisterTransitCallback(time_callback)

# 添加时间维度，关键设置fix_start_cumul_to_zero=False
time_dimension = routing.AddTimeDimension(
    transit_callback_idx,
    slack_max=0,  # 允许的等待时间，按需调整
    capacity=36000,  # 全局最大时间上限
    fix_start_cumul_to_zero=False,  # 禁用起始时间固定为0
    name="Time"
)

# 为每个车辆绑定工时约束
for vehicle_id in range(data["num_vehicles"]):
    start_idx = routing.Start(vehicle_id)
    end_idx = routing.End(vehicle_id)
    work_start, work_end = data["working_time"][vehicle_id]
    
    # 设置出发时间范围：不早于工时开始，不晚于工时结束
    time_dimension.CumulVar(start_idx).SetRange(work_start, work_end)
    # 设置返回时间范围：不早于工时开始，不晚于工时结束
    time_dimension.CumulVar(end_idx).SetRange(work_start, work_end)
    
    # 可选约束：确保总工作时长不超过工时长度
    routing.solver().Add(
        time_dimension.CumulVar(end_idx) - time_dimension.CumulVar(start_idx)
        <= work_end - work_start
    )

# 为任务节点设置时间窗约束
for node in range(len(data["time_matrix"])):
    if node == data["depot"]:
        continue
    node_idx = manager.NodeToIndex(node)
    tw_start, tw_end = data["time_windows"][node]
    time_dimension.CumulVar(node_idx).SetRange(tw_start, tw_end)

# 设置目标函数（最小化总行驶时间）
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_idx)

# 求解模型
search_params = pywrapcp.DefaultRoutingSearchParameters()
solution = routing.SolveWithParameters(search_params)

if solution:
    # 打印或处理求解结果
    print("找到可行解")
    # 示例：打印每辆车的路径与时间
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        route_time = 0
        print(f"\n车辆 {vehicle_id} 的路径:")
        while not routing.IsEnd(index):
            node = manager.IndexToNode(index)
            next_index = solution.Value(routing.NextVar(index))
            route_time += time_callback(index, next_index)
            print(f"节点 {node} -> ", end="")
            index = next_index
        print(f"节点 {manager.IndexToNode(index)}")
        print(f"总耗时: {route_time} 秒")
else:
    print("无解，请检查任务时间窗与车辆工时是否冲突")

额外排查方向 #

如果修正后仍无解，可能是以下原因：

• 某任务的时间窗与分配车辆的工时完全无交集
• 任务的服务时间+行驶总时长超过对应车辆的工时长度
• 车辆数量不足或任务分配逻辑存在冲突

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