如何为OR-Tools取送问题添加“先完成配送再取货”约束？

要实现每个配送任务必须完成后才能执行新的取货任务（即任务不能交叉执行，必须完成一个完整的取送闭环再开始下一个），可通过以下两种方式修改代码：

方式一：强制所有任务串行（无交叉） #

适用于要求所有任务必须逐个完成，不能同时处理多个未配送的取货任务。

步骤1：计算大M值 #

大M是一个足够大的常数，用于线性约束中的松弛项，确保约束在布尔变量切换时生效：

# 假设time_callback是原代码中计算节点间时间的函数
max_time = 0
for from_node in range(routing.Size()):
    for to_node in range(routing.Size()):
        if from_node != to_node:
            max_time = max(max_time, time_callback(from_node, to_node))
# M取最大单段时间乘以总节点数，确保足够大
M = max_time * routing.Size()

步骤2：遍历任务对，添加约束 #

假设原代码中任务列表为tasks（每个元素是(pickup_node, delivery_node)），添加约束确保任意两个任务不会交叉：

tasks = [(1,5), (2,6)]  # 替换为你的任务列表
manager = pywrapcp.RoutingIndexManager(...)  # 原代码中的manager实例
routing = pywrapcp.RoutingModel(...)  # 原代码中的routing实例
time_dimension = routing.GetDimensionOrDie('Time')

for i in range(len(tasks)):
    for j in range(i+1, len(tasks)):
        # 转换任务节点为路由索引
        i_pickup_idx = manager.NodeToIndex(tasks[i][0])
        i_delivery_idx = manager.NodeToIndex(tasks[i][1])
        j_pickup_idx = manager.NodeToIndex(tasks[j][0])
        j_delivery_idx = manager.NodeToIndex(tasks[j][1])
        
        # 创建布尔变量，标记任务i是否在任务j之前完成
        b_ij = routing.NewBoolVar(f"task_order_{i}_{j}")
        
        # 约束1：若i在j前完成，则i的配送时间 ≤ j的取货时间
        routing.AddConstraint(
            time_dimension.CumulVar(i_delivery_idx) <= 
            time_dimension.CumulVar(j_pickup_idx) + M * (1 - b_ij)
        )
        
        # 约束2：若j在i前完成，则j的配送时间 ≤ i的取货时间
        routing.AddConstraint(
            time_dimension.CumulVar(j_delivery_idx) <= 
            time_dimension.CumulVar(i_pickup_idx) + M * b_ij
        )

方式二：强制特定任务顺序 #

如果只需要指定某几个任务的执行顺序（比如示例中的1→5→2→6），可以直接添加单向时间约束：

# 任务1的配送节点是5，任务2的取货节点是2
task1_delivery_idx = manager.NodeToIndex(5)
task2_pickup_idx = manager.NodeToIndex(2)
time_dimension = routing.GetDimensionOrDie('Time')

# 强制任务1的配送完成时间 ≤ 任务2的取货开始时间
routing.AddConstraint(
    time_dimension.CumulVar(task1_delivery_idx) <= time_dimension.CumulVar(task2_pickup_idx)
)

注意事项 #

• 确保time_dimension已正确定义（原代码中通常会添加时间维度，包含车辆速度、服务时间等）
• 大M值需足够大，避免约束失效，可根据实际场景调整（比如取所有任务总耗时的2倍）
• 如果是多车辆场景，需要针对每辆车单独添加约束，或者确保任务分配到同一车辆后再应用上述约束

内容的提问来源于stack exchange，提问作者SEREEN AHMED QURBAN