如何在OR-Tools VRP中实现带班次约束的CVRPTW车队优化？

约束1：每辆车每日最多执行2次任务（白班+夜班） #

实现思路 #

通过任务计数约束和时间窗绑定限制车辆任务量与班次时间：

• 给所有任务节点（含拆分节点）设置对应班次的时间窗：白班节点时间窗设为[6*3600, 18*3600]，夜班节点设为[18*3600, 24*3600]（时间单位为秒）。
• 为每辆车创建累计任务数变量，用RoutingModel的累计维度实现：

  # 创建任务计数维度
  task_count_dimension = routing.AddDimension(
      lambda from_index, to_index: 1 if from_index != to_index else 0,
      0,  # 松弛量
      2,  # 最大任务数
      True,  # 从零开始累计
      "TaskCount"
  )
  

• 若允许车辆跨班次执行任务（白班+夜班），需添加时间不重叠约束：确保白班任务结束时间≤183600，夜班任务开始时间≥183600，通过时间维度的累计变量实现：

  time_dimension = routing.GetDimensionOrDie("Time")
  solver = routing.solver()
  for vehicle_id in range(manager.GetNumberOfVehicles()):
      # 获取车辆的任务节点索引（需根据实际路由逻辑调整）
      task_indices = [manager.NodeToIndex(node) for node in vehicle_tasks[vehicle_id]]
      if len(task_indices) >= 2:
          # 第一个任务结束时间 ≤ 18:00
          solver.Add(time_dimension.CumulVar(task_indices[0]) <= 18*3600)
          # 第二个任务开始时间 ≥ 18:00
          solver.Add(time_dimension.CumulVar(task_indices[1]) >= 18*3600)
  

约束2&3：同一原始地点的拆分节点访问需覆盖至少两个班次（访问≥2次时） #

实现思路 #

先将同一原始地点的拆分节点分组，再通过逻辑约束强制多班次覆盖：

1. 建立原始地点到拆分节点的映射：

   # 示例：location_id为原始地点ID，nodes为对应的拆分节点索引列表
   location_to_nodes = {
       0: [1,2,3],
       1: [4,5],
       # ... 其他地点
   }
   

2. 对每个地点的节点组，统计总访问次数、白班/夜班访问次数，添加条件约束：

   solver = routing.solver()
   time_dimension = routing.GetDimensionOrDie("Time")
   for location_id, nodes in location_to_nodes.items():
       # 统计该地点的总访问次数（ActiveVar表示节点是否被访问）
       total_visits = solver.Sum([routing.ActiveVar(node) for node in nodes])
       # 统计白班访问次数：节点被访问且时间落在白班区间
       day_visits = solver.Sum([
           routing.ActiveVar(node) 
           for node in nodes 
       ]).OnlyEnforceIf(time_dimension.CumulVar(node) <= 18*3600)
       # 夜班访问次数 = 总次数 - 白班次数
       night_visits = solver.Sub(total_visits, day_visits)
       
       # 添加约束：当总访问次数≥2时，必须至少有1次白班和1次夜班访问
       solver.Add(day_visits >= 1).OnlyEnforceIf(solver.MakeGreaterOrEqual(total_visits, 2))
       solver.Add(night_visits >= 1).OnlyEnforceIf(solver.MakeGreaterOrEqual(total_visits, 2))
   

   该约束自动满足“访问3次及以上时允许同一班次多次”的要求，只要同时存在白班和夜班访问即可，不限制同一班次的访问次数。

替代方案：按车辆班次类型统计 #

如果车辆固定为白班/夜班类型（某辆车只跑单一班次），可直接按车辆类型统计：

# 标记车辆类型：0=白班，1=夜班
vehicle_shift = [0,0,1,1]  # 示例：前2辆车白班，后2辆夜班
solver = routing.solver()
for location_id, nodes in location_to_nodes.items():
    total_visits = solver.Sum([routing.ActiveVar(node) for node in nodes])
    # 统计白班车辆访问次数
    day_vehicle_visits = solver.Sum([
        routing.ActiveVar(node) * (routing.VehicleVar(node) == vid)
        for node in nodes
        for vid in range(len(vehicle_shift))
        if vehicle_shift[vid] == 0
    ])
    # 夜班车辆访问次数
    night_vehicle_visits = solver.Sub(total_visits, day_vehicle_visits)
    
    solver.Add(day_vehicle_visits >= 1).OnlyEnforceIf(solver.MakeGreaterOrEqual(total_visits, 2))
    solver.Add(night_vehicle_visits >= 1).OnlyEnforceIf(solver.MakeGreaterOrEqual(total_visits, 2))

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