如何在OR-Tools路由问题中实现分组订单的单车辆分配约束？

问题分析 #

核心需求是：同一组内的所有订单必须由同一车辆配送，组内订单不可拆分至多辆车。此前方案失败的核心原因是将Python原生逻辑直接混入求解器约束定义，未正确利用OR-Tools的变量与约束API。

正确建模方法 #

方法1：针对必选订单的直接约束 #

适用于所有订单必须被配送的场景，直接强制组内所有订单节点的分配车辆完全一致。

示例代码：

# 按组整理订单节点索引
group_nodes = {}
for i in range(self.num_items):
    group = self.items_group[i]
    node_index = self.manager.NodeToIndex(i + self.num_depots)
    if group not in group_nodes:
        group_nodes[group] = []
    group_nodes[group].append(node_index)

# 为每组添加同车约束
for group, nodes in group_nodes.items():
    if len(nodes) < 2:
        continue  # 单节点组无需约束
    # 取组内第一个节点的车辆分配变量作为基准
    base_vehicle_var = self.routing.VehicleVar(nodes[0])
    # 约束组内其他节点的分配车辆与基准一致
    for node in nodes[1:]:
        current_vehicle_var = self.routing.VehicleVar(node)
        self.routing.solver().Add(base_vehicle_var == current_vehicle_var)

方法2：针对可选订单的约束（支持订单跳过配送） #

如果存在无需强制配送的订单，需要结合节点的ActiveVar（标记节点是否被服务）来约束：若组内任意节点被服务，则组内所有节点必须被同一车辆服务。

示例代码：

# 按组整理订单节点索引
group_nodes = {}
for i in range(self.num_items):
    group = self.items_group[i]
    node_index = self.manager.NodeToIndex(i + self.num_depots)
    if group not in group_nodes:
        group_nodes[group] = []
    group_nodes[group].append(node_index)

# 为每组添加可选场景下的同车约束
for group, nodes in group_nodes.items():
    if len(nodes) < 2:
        continue
    base_node = nodes[0]
    base_active = self.routing.ActiveVar(base_node)
    base_vehicle = self.routing.VehicleVar(base_node)
    
    for node in nodes[1:]:
        current_active = self.routing.ActiveVar(node)
        current_vehicle = self.routing.VehicleVar(node)
        
        # 约束：基准节点被服务时，当前节点必须被服务且同车
        self.routing.solver().Add(base_active <= current_active)
        self.routing.solver().Add((base_active == 1) <= (base_vehicle == current_vehicle))
        
        # 约束：当前节点被服务时，基准节点必须被服务且同车
        self.routing.solver().Add(current_active <= base_active)
        self.routing.solver().Add((current_active == 1) <= (base_vehicle == current_vehicle))

原代码问题解析 #

1. Python逻辑混入求解器约束：len(used_vehicles)==0 or ... 是Python运行时的条件判断，并非求解器可识别的约束逻辑，无法处理求解过程中节点是否被服务的动态状态。
2. 错误的变量值判断：v > -1 直接用Python比较求解器变量，这是无效操作——求解器变量在约束构建阶段无具体值，必须通过OR-Tools的Add()等API定义变量间的关系。

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