OR Tools VRPTW中同一节点多时间窗变体互斥约束实现求助

核心思路 #

同一物理节点的多个时间窗变体属于互斥选择，核心约束逻辑是：

• 用OR-Tools原生的ActiveVar标记每个变体节点是否被访问（1=访问，0=未访问）
• 对属于同一物理节点的所有变体节点，添加访问变量之和≤1的约束，确保最多选中一个变体

可测试代码示例 #

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

def create_data_model():
    data = {}
    # 节点坐标（同一物理节点的变体坐标一致）
    data['locations'] = [
        (0, 0),  # 配送中心（节点0）
        (1, 2),  # 物理节点A的变体1（节点1）
        (1, 2),  # 物理节点A的变体2（节点2）
        (3, 1),  # 物理节点B的变体1（节点3）
        (3, 1),  # 物理节点B的变体2（节点4）
    ]
    # 时间窗：(开始时间, 结束时间)
    data['time_windows'] = [
        (0, 100),  # 配送中心
        (5, 15),   # 节点A变体1时间窗
        (20, 30),  # 节点A变体2时间窗
        (10, 20),  # 节点B变体1时间窗
        (25, 35),  # 节点B变体2时间窗
    ]
    data['demands'] = [0, 1, 1, 1, 1]  # 同一物理节点变体需求相同
    data['vehicle_capacities'] = [2, 2]
    data['num_vehicles'] = 2
    data['depot'] = 0
    # 定义同一物理节点的变体分组
    data['node_variants'] = {
        'A': [1, 2],
        'B': [3, 4]
    }
    return data

def main():
    data = create_data_model()
    manager = pywrapcp.RoutingIndexManager(
        len(data['locations']), 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)
        dx = data['locations'][from_node][0] - data['locations'][to_node][0]
        dy = data['locations'][from_node][1] - data['locations'][to_node][1]
        return int((dx**2 + dy**2)**0.5)

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

    # 添加时间窗维度约束
    time_dim = routing.AddDimension(
        transit_callback_index,
        30,  # 最大等待时间
        100,  # 总时间上限
        False,
        'Time'
    )
    for loc_idx, tw in enumerate(data['time_windows']):
        if loc_idx == data['depot']:
            continue
        idx = manager.NodeToIndex(loc_idx)
        time_dim.CumulVar(idx).SetRange(tw[0], tw[1])

    # 添加容量维度约束
    def demand_callback(from_index):
        return data['demands'][manager.IndexToNode(from_index)]

    demand_idx = routing.RegisterUnaryTransitCallback(demand_callback)
    routing.AddDimensionWithVehicleCapacity(
        demand_idx,
        0,
        data['vehicle_capacities'],
        True,
        'Capacity'
    )

    # 核心：添加变体节点互斥约束
    visit_vars = {}
    for node in range(len(data['locations'])):
        if node == data['depot']:
            continue
        # 用ActiveVar获取节点访问状态的布尔变量
        visit_vars[node] = routing.ActiveVar(manager.NodeToIndex(node))

    # 对每个物理节点的变体组，约束访问变量之和≤1
    for variant_group in data['node_variants'].values():
        variant_vars = [visit_vars[node] for node in variant_group]
        routing.solver().Add(sum(variant_vars) <= 1)

    # 设置求解参数
    search_params = pywrapcp.DefaultRoutingSearchParameters()
    search_params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    search_params.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    search_params.time_limit.seconds = 5

    # 求解并输出结果
    solution = routing.SolveWithParameters(search_params)
    if solution:
        print(f'总行驶时间: {solution.ObjectiveValue()} 单位时间')
        time_dim = routing.GetDimensionOrDie('Time')
        cap_dim = routing.GetDimensionOrDie('Capacity')
        for vid in range(data['num_vehicles']):
            idx = routing.Start(vid)
            plan = f'车辆 {vid} 路径:\n'
            while not routing.IsEnd(idx):
                node = manager.IndexToNode(idx)
                time_var = time_dim.CumulVar(idx)
                cap_var = cap_dim.CumulVar(idx)
                plan += f' 节点 {node} (到达时间: {solution.Min(time_var)}-{solution.Max(time_var)}, 装载量: {solution.Value(cap_var)}) -> '
                idx = solution.Value(routing.NextVar(idx))
            node = manager.IndexToNode(idx)
            time_var = time_dim.CumulVar(idx)
            cap_var = cap_dim.CumulVar(idx)
            plan += f' 节点 {node} (到达时间: {solution.Min(time_var)}-{solution.Max(time_var)}, 装载量: {solution.Value(cap_var)})\n'
            print(plan)
    else:
        print('未找到可行解')

if __name__ == '__main__':
    main()

关键说明 #

• ActiveVar的作用：无需手动创建NewBoolVar，routing.ActiveVar(index)直接返回节点的访问状态布尔变量，简化代码
• 互斥约束逻辑：同一物理节点的所有变体访问变量求和≤1，确保最多选择一个时间窗变体
• 数据一致性：同一物理节点的变体需保持坐标、需求等参数一致，避免逻辑冲突

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