OR-Tools Python版：多取单送订单组约束实现方案咨询

核心问题拆解 #

订单组要求：要么全部由同一车辆完成所有取货+统一送货，要么全不执行。每个订单自带取货析取集（选1个节点）、送货析取集（选1个节点），但订单组的送货必须指向同一地点，且需和所有取货操作强绑定。

可行实现思路 #

1. 用虚拟节点统一订单组送货逻辑 #

为每个订单组创建一个虚拟送货节点，替代原订单各自的送货析取集：

• 保留订单组内每个订单的取货析取集（通过AddDisjunction设置正惩罚、最大基数1）
• 移除原送货析取集，改为约束每个取货节点的NextVar必须指向虚拟送货节点（确保取货后必须进入统一送货流程）
• 给虚拟送货节点单独创建析取集：设置正惩罚、最大基数1，以此代表整个订单组是否执行

2. 绑定同一车辆与全执行/全不执行约束 #

• 同一车辆约束：用AddSameVehicleConstraint将虚拟送货节点与订单组内所有取货候选节点绑定，确保只要执行就必须同车完成
• 全执行逻辑约束：通过solver.Add()结合OnlyEnforceIf实现双向约束：
  • 若虚拟送货节点执行，则所有取货析取集必须执行
  • 若任意取货析取集执行，则虚拟送货节点必须执行

3. 映射到真实送货地点 #

如果需要将虚拟节点对应到真实送货地点，直接把虚拟节点的位置参数设为目标地点即可；若需强制经过真实节点，可在虚拟节点后添加一个无惩罚的真实送货节点，约束虚拟节点的NextVar指向该真实节点。

代码示例片段 #

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

def create_data_model():
    data = {}
    # 订单组1包含2个订单，每个订单有2个取货候选节点，统一送货到地点5
    data["pickup_candidates_group1"] = [[1, 2], [3, 4]]
    data["unified_delivery_node"] = 5
    data["num_vehicles"] = 2
    data["depot"] = 0
    # 自定义节点间成本（示例用距离）
    data["distance_matrix"] = [
        [0, 2, 4, 5, 7, 6],
        [2, 0, 1, 3, 5, 4],
        [4, 1, 0, 2, 4, 3],
        [5, 3, 2, 0, 2, 1],
        [7, 5, 4, 2, 0, 1],
        [6, 4, 3, 1, 1, 0],
    ]
    return data

def main():
    data = create_data_model()
    node_count = len(data["distance_matrix"])
    manager = pywrapcp.RoutingIndexManager(node_count, data["num_vehicles"], data["depot"])
    routing = pywrapcp.RoutingModel(manager)
    solver = routing.solver()

    # 注册成本回调函数
    def distance_callback(from_idx, to_idx):
        from_node = manager.IndexToNode(from_idx)
        to_node = manager.IndexToNode(to_idx)
        return data["distance_matrix"][from_node][to_node]
    transit_idx = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_idx)

    # 1. 添加订单组的取货析取集
    pickup_disjunctions = []
    for candidates in data["pickup_candidates_group1"]:
        idx_list = [manager.NodeToIndex(node) for node in candidates]
        disj = routing.AddDisjunction(idx_list, penalty=1500, max_cardinality=1)
        pickup_disjunctions.append(disj)

    # 2. 添加统一送货节点的析取集
    delivery_idx = manager.NodeToIndex(data["unified_delivery_node"])
    delivery_disj = routing.AddDisjunction([delivery_idx], penalty=2000, max_cardinality=1)

    # 3. 约束取货节点执行后必须前往送货节点
    for candidates in data["pickup_candidates_group1"]:
        for node in candidates:
            node_idx = manager.NodeToIndex(node)
            routing.AddNextVarLiteral(node_idx, delivery_idx).OnlyEnforceIf(routing.ActiveVar(node_idx))

    # 4. 绑定同一车辆 + 全执行/全不执行逻辑
    for disj in pickup_disjunctions:
        # 送货执行 → 所有取货必须执行
        solver.Add(disj.PerformedVar() == 1).OnlyEnforceIf(delivery_disj.PerformedVar())
        # 取货执行 → 送货必须执行
        solver.Add(delivery_disj.PerformedVar() == 1).OnlyEnforceIf(disj.PerformedVar())
        # 取货候选节点与送货节点必须同车
        for node in disj.nodes():
            routing.AddSameVehicleConstraint(node, delivery_idx)

    # 配置求解参数
    search_params = pywrapcp.DefaultRoutingSearchParameters()
    search_params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    search_params.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    search_params.time_limit.seconds = 10

    # 求解并输出结果
    solution = routing.SolveWithParameters(search_params)
    if solution:
        for vehicle_id in range(data["num_vehicles"]):
            index = routing.Start(vehicle_id)
            route = []
            while not routing.IsEnd(index):
                route.append(manager.IndexToNode(index))
                index = solution.Value(routing.NextVar(index))
            route.append(manager.IndexToNode(index))
            print(f"车辆 {vehicle_id+1} 路径: {' -> '.join(map(str, route))}")

if __name__ == "__main__":
    main()

关键注意事项 #

• 析取集的惩罚值需合理设置：确保算法选择不执行订单组时的惩罚成本，与执行订单组的实际成本匹配（按需调整）
• AddSameVehicleConstraint需覆盖所有取货候选节点，避免漏绑导致同组订单分车执行
• 双向逻辑约束必须同时配置，才能严格保证订单组“全执行或全不执行”的规则

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