如何在Google OR-Tools的CVRP模型中添加弧连通及带宽约束

1 适配部分连通无向图 #

OR-Tools的Routing库默认基于完全图构建路由问题，要限制仅使用预定义的连通弧，按以下步骤实现：

• 先构造节点间的邻接开销矩阵，不存在的连通弧对应的开销值设置为远大于所有可行路径总开销的极大值，无向图中弧(u,v)和(v,u)的开销要保持一致
• 自定义弧开销评估器，当检测到访问不存在的弧时返回OR-Tools内置的无穷大成本常量，框架会自动排除这类无效弧的使用
  示例代码如下：

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

def arc_cost_evaluator(from_index, to_index):
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    # adj_matrix为预定义的邻接矩阵，不存在的弧值为0
    return adj_matrix[from_node][to_node] if adj_matrix[from_node][to_node] > 0 else pywrapcp.RoutingModel.kInfiniteCost

• 将上述评估器绑定到路由模型即可完成部分连通性限制：
  routing.SetArcCostEvaluatorOfAllVehicles(arc_cost_evaluator)

2 实现带时间关联的弧带宽约束 #

该约束属于共享时间资源约束，核心逻辑是将每条弧作为共享资源，车辆在弧上行驶的时间段为资源占用窗口，要求任意时间点的占用量不超过容量上限x，实现步骤如下：

2.1 注册时间维度 #

首先给模型添加时间维度，记录每个节点的车辆到达时间，用于计算弧的占用窗口：

def time_evaluator(from_index, to_index):
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return adj_matrix[from_node][to_node]

time_dimension_name = "Time"
routing.AddDimension(
    time_evaluator,
    0, # 无节点等待缓冲时间
    99999, # 单车辆最大总行驶时间上限，可按需调整
    True, # 车辆从仓库出发的时间统一为0
    time_dimension_name
)
time_dimension = routing.GetDimensionOrDie(time_dimension_name)

2.2 添加弧资源累积约束 #

对每条物理弧，收集所有车辆使用该弧时对应的时间区间变量，添加累积约束限制重叠区间的最大数量：

solver = routing.solver()
ARC_MAX_CAPACITY = x # 替换为实际的弧最大通行车辆数

for u in range(num_nodes):
    for v in range(u+1, num_nodes): # 无向图仅遍历一次物理弧
        if adj_matrix[u][v] <= 0:
            continue
        travel_time = adj_matrix[u][v]
        arc_intervals = []
        for veh_id in range(num_vehicles):
            # 处理u->v方向的通行
            u_idx = manager.NodeToIndex(u)
            v_idx = manager.NodeToIndex(v)
            u_to_v = routing.NextVar(u_idx) == v_idx
            if u_to_v:
                start_time = time_dimension.CumulVar(u_idx)
                interval = solver.FixedDurationIntervalVar(
                    start_time, travel_time, f"arc_{u}_{v}_veh_{veh_id}_u2v"
                )
                arc_intervals.append(interval)
            # 处理v->u方向的通行
            v_to_u = routing.NextVar(v_idx) == u_idx
            if v_to_u:
                start_time = time_dimension.CumulVar(v_idx)
                interval = solver.FixedDurationIntervalVar(
                    start_time, travel_time, f"arc_{u}_{v}_veh_{veh_id}_v2u"
                )
                arc_intervals.append(interval)
        # 约束同一时间该弧上的车辆数不超过上限
        solver.Add(
            solver.Cumulative(
                arc_intervals, 
                [1]*len(arc_intervals), 
                ARC_MAX_CAPACITY
            )
        )

2.3 注意事项 #

• 如果弧的带宽是单向限制，仅需要将两个方向的通行分开设置独立的累积约束即可
• 若弧的行驶时间随时间动态变化，修改time_evaluator的返回逻辑即可，累积约束无需调整

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