OR-Tools Python CVRP按组限制节点类型访问数的回调函数问题

针对你提出的带节点组类型访问上限的CVRP需求，以下是修正后的回调函数与维度添加代码，解决原代码崩溃问题并实现约束逻辑：

预处理参数与基础定义 #

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

# 问题参数
groups = [0, 1]
node_type = [0, 0, 2, 2, 1, 3, 3, 3, 4]
node_group_type = [0, 0, 0, 0, 0, 1, 1, 1, 1]
max_visits_per_type_group = [2, 1]
num_nodes = len(node_type)
depot = 0  # 假设 depot 为节点0
num_vehicles = 2  # 根据实际场景调整车辆数量

# 预处理：为每个组映射类型到位掩码（用于跟踪已访问的类型）
group_to_types = {0: {0, 1, 2}, 1: {3, 4}}
group_type_bit_map = {}
for group in groups:
    sorted_types = sorted(group_to_types[group])
    group_type_bit_map[group] = {t: 1 << idx for idx, t in enumerate(sorted_types)}

路由模型与回调函数定义 #

# 初始化路由管理器与模型
manager = pywrapcp.RoutingIndexManager(num_nodes, num_vehicles, depot)
routing = pywrapcp.RoutingModel(manager)

# 为每个组创建状态回调函数，跟踪已访问类型的位掩码
def create_group_type_mask_callback(group):
    def callback(from_index):
        from_node = manager.IndexToNode(from_index)
        # 若当前节点是depot，返回初始掩码0（无类型访问）
        if from_node == depot:
            return 0
        
        current_mask = routing.GetDimensionOrDie(f"group_{group}_type_mask").CurrentValue(from_index)
        return current_mask
    return callback

# 为每个组创建更新掩码的回调（用于维度转移）
def create_group_type_transit_callback(group):
    def callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        
        # 到达depot时重置掩码为0
        if to_node == depot:
            return 0
        
        to_group = node_group_type[to_node]
        if to_group != group:
            # 目标节点不属于当前组，掩码保持不变
            return routing.GetDimensionOrDie(f"group_{group}_type_mask").CurrentValue(from_index)
        
        # 目标节点属于当前组，更新掩码（标记已访问该类型）
        to_type = node_type[to_node]
        bit = group_type_bit_map[group][to_type]
        old_mask = routing.GetDimensionOrDie(f"group_{group}_type_mask").CurrentValue(from_index)
        new_mask = old_mask | bit
        return new_mask
    return callback

添加维度与类型数量约束 #

# 为每个组添加类型掩码维度，并设置访问数量约束
for group_idx, group in enumerate(groups):
    max_mask = (1 << len(group_to_types[group])) - 1  # 该组的最大可能掩码值
    max_type_count = max_visits_per_type_group[group_idx]
    
    # 注册转移回调
    transit_callback = routing.RegisterBinaryTransitCallback(create_group_type_transit_callback(group))
    # 添加状态维度
    routing.AddDimension(
        transit_callback,
        0,  # 无松弛量
        max_mask,  # 掩码的最大允许值
        True,  # 起始状态为0（depot出发时无类型访问）
        f"group_{group}_type_mask"
    )
    
    mask_dim = routing.GetDimensionOrDie(f"group_{group}_type_mask")
    solver = routing.solver()
    
    # 为每辆车约束：路径结束时该组已访问的类型数量不超过上限
    for vehicle_id in range(num_vehicles):
        end_index = routing.End(vehicle_id)
        end_mask_var = mask_dim.CumulVar(end_index)
        
        # 计算掩码中1的个数（即已访问的类型数量）
        type_count_var = solver.IntVar(0, max_type_count, f"group_{group}_count_vehicle_{vehicle_id}")
        solver.Add(solver.CountBits(end_mask_var) == type_count_var)
        solver.Add(type_count_var <= max_type_count)

关键修正说明 #

1. 位掩码状态跟踪：用位掩码记录路径中已访问的节点类型，避免直接计数导致的状态混乱，符合OR-Tools状态维度的设计要求。
2. 分组建回调：为每个节点组单独创建回调函数，确保只处理对应组内的节点类型更新，避免跨组逻辑干扰。
3. 正确的维度约束：通过CountBits函数将掩码转换为已访问类型数量，再与上限值对比，替代原代码中错误的直接使用max_visits_per_type_group的逻辑。
4. 状态初始化与重置：明确depot节点的掩码初始值为0，车辆返回depot时重置掩码，避免路径间的状态污染。

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