OR-Tools求解VRP时如何为特定车辆排除指定路径组合

你需要实现的约束核心是对指定车辆，禁止其配送的节点集合恰好等于预设的排斥节点子集，不限制节点的访问顺序，也不禁止节点在搭配其他非排斥集合节点时被访问，原有节点级的访问权限控制接口粒度过粗，无法满足该需求，可以通过基于节点归属判断的自定义硬约束实现，完全匹配你给出的判定规则。

实现逻辑 #

约束的判定规则可以拆解为：对任意车辆k和它对应的排斥节点集合S，以下两个条件不能同时成立：

• S内的所有配送节点全部分配给车辆k
• 所有不在S内的配送节点都没有分配给车辆k
  只要两个条件不同时满足，路径就合法，不管S内节点的访问顺序如何，也不管S内节点是否和其他节点搭配出现。

具体实现步骤 #

• 第一步：预处理排斥规则
  提前将所有车辆的排斥路径转为无序集合存储（忽略节点访问顺序），建议用frozenset类型方便后续匹配，结构为{车辆id: [排斥节点集合1, 排斥节点集合2, ...]}。注意所有节点要提前通过manager.NodeToIndex()转为路由模型内部索引，不要直接使用原始节点编号避免索引不匹配。
• 第二步：添加自定义硬约束
  借助OR-Tools CP求解器原生支持的布尔表达式能力，直接对上述判定规则加硬约束即可，参考代码如下：

  from ortools.constraint_solver import pywrapcp
  
  # 以下代码在routing模型、index manager、depot索引初始化完成后添加
  depot_index = manager.NodeToIndex(0)  # 替换为你实际的depot节点索引
  # 提取所有配送节点（排除仓库depot）
  delivery_nodes = [
      idx for idx in range(manager.GetNumberOfIndices())
      if idx != depot_index
  ]
  # 配置每台车的排斥集合，示例对应题目中车辆A（id=0）的规则
  vehicle_forbidden_sets = {
      0: [
          frozenset([manager.NodeToIndex(X)]),  # 禁止仅访问X的单节点路径
          frozenset([manager.NodeToIndex(X), manager.NodeToIndex(Y)])  # 禁止仅访问X、Y的双节点路径（任意顺序）
      ]
      # 其他车辆的排斥规则按相同格式追加即可
  }
  
  solver = routing.solver()
  for vehicle_id, forbidden_set_list in vehicle_forbidden_sets.items():
      for forbidden_set in forbidden_set_list:
          # 表达式：禁止集合内的所有节点都分配给了当前车辆
          all_forbidden_served = sum(
              routing.VehicleVar(node_idx) == vehicle_id
              for node_idx in forbidden_set
          ) == len(forbidden_set)
          # 表达式：禁止集合外的所有配送节点都没分配给当前车辆
          no_other_node_served = sum(
              routing.VehicleVar(node_idx) == vehicle_id
              for node_idx in delivery_nodes
              if node_idx not in forbidden_set
          ) == 0
          # 加硬约束：两个表达式不能同时为真，否则为非法路径
          solver.AddConstraint(
              ~(all_forbidden_served & no_other_node_served)
          )
  

适配说明 #

• 该实现完全匹配你给出的可行/不可行判定规则：
  • 会自动禁止排斥集合节点任意顺序的全组合路径、仅包含排斥集合节点的路径
  • 不会禁止排斥集合节点搭配其他节点的路径、排斥集合的真子集路径
  • 不会限制单个节点的访问权限，节点只要不凑成完整的排斥集合就可以被对应车辆访问
• 如果需要禁止某台车不执行任何配送任务（空驶），只需要给对应车辆的排斥集合列表追加空集合frozenset()即可，无需额外编写约束。
• 常规场景下（节点数<200、车辆数<50、单车辆排斥集合数<100）该实现的性能损耗可以忽略，大规模场景下提前对重复的排斥集合做去重即可。
• 多台车辆的排斥规则完全独立，不会出现跨车辆的规则干扰。

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