OR-Tools单取送对路径不合理问题排查求助

以下是导致OR-Tools求解路径不符合预期的核心原因及对应解决方法：

• 未添加取送任务的依赖约束
  OR-Tools不会自动识别取货和送货节点的关联关系，必须显式绑定取送配对并约束执行逻辑。如果仅将两个节点作为普通任务加入模型，求解器会将它们视为独立节点，进而生成包含冗余节点的路径。
  解决：通过AddPickupAndDelivery绑定取送对，同时约束同一车辆执行：

# 假设取货点在模型中的索引是1，送货点是2
routing.AddPickupAndDelivery(1, 2)
solver = routing.solver()
# 确保取货和送货由同一车辆完成
solver.AddConstraint(routing.VehicleVar(1) == routing.VehicleVar(2))

• 节点索引映射错误
  你提到的取货点52、送货点41是原始数据中的编号，但OR-Tools模型的节点索引通常从0（depot）开始。如果直接将原始编号作为模型节点索引，会导致模型包含0到52的所有节点，求解器会默认这些节点都是可访问的，从而生成遍历大量节点的路径。
  解决：仅保留需要的节点，重新映射索引：

# 示例：仅保留depot、取货点52、送货点41
original_nodes = [0, 52, 41]  # 0是depot的原始编号
# 生成模型索引到原始节点的映射，模型索引为0(depot),1(取货),2(送货)
# 再基于这三个节点的坐标生成距离矩阵

• 未强制要求完成取送任务
  如果没有设置取货和送货节点的必须访问约束，求解器可能会跳过这些节点，或者选择其他节点凑路径。另外，错误的容量设置（比如取货需求为正，但车辆容量为0）也会导致异常路径。
  解决：用AddDisjunction设置极高惩罚值确保节点必须被访问，同时正确配置容量约束：

# 设置取货和送货节点必须访问（惩罚值设为极大，不能跳过）
penalty = 10**6
routing.AddDisjunction([1], penalty)
routing.AddDisjunction([2], penalty)

# 设置容量维度，取货需求+1，送货需求-1
capacity_dimension = routing.AddDimension(
    demand_callback,
    0,  # 允许的负 slack（此处不需要）
    1,  # 车辆容量
    True,  # 从depot出发时容量为0
    "Capacity"
)

• 距离矩阵包含冗余节点
  如果距离矩阵是基于所有原始节点生成的（比如0到52），即使你只需要三个节点，求解器会认为所有节点都是可选任务，可能生成包含其他节点的路径。
  解决：仅生成目标节点的欧式距离矩阵：

# 假设各节点坐标：depot(0,0)，取货点52(x1,y1)，送货点41(x2,y2)
coords = [(0, 0), (x1, y1), (x2, y2)]
# 生成3x3的距离矩阵
distance_matrix = [
    [int(((x_i - x_j)**2 + (y_i - y_j)**2)**0.5) for (x_j, y_j) in coords]
    for (x_i, y_i) in coords
]

• 求解器参数配置不当
  如果搜索时间过短，求解器可能返回次优解；或者使用的启发式算法导致路径偏离最优。
  解决：针对小规模问题，配置合适的搜索参数：

from ortools.constraint_solver import routing_enums_pb2
import pywrapcp

search_params = pywrapcp.DefaultRoutingSearchParameters()
# 设置时间限制，确保求解器找到最优解
search_params.time_limit.seconds = 15
# 或者使用自动选择的精确搜索策略
search_params.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.AUTOMATIC

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