如何用pywrapcp库获取车辆路径问题的最优解？

用pywrapcp获取VRP-PD最优解的配置方法 #

pywrapcp默认采用启发式搜索策略，要拿到最优解，需要调整参数强制完成最优性验证，以下是关键步骤：

1. 启用最优性导向的求解参数 #

修改求解器的搜索分支策略，并设置足够的求解时间，让求解器有机会完成完整搜索：

from ortools.linear_solver import pywrapcp

solver = pywrapcp.Solver("VRP-PD")
# 选择偏向最优性的分支策略，FIXED_ORDER_SEARCH配合自定义决策构建器效果更可控
solver.parameters.search_branching = pywrapcp.Solver.FIXED_ORDER_SEARCH
# 设置足够长的求解时间（根据问题规模调整，比如300秒）
solver.parameters.max_time_in_seconds = 300
# 可选：开启搜索日志，便于排查搜索瓶颈
solver.parameters.log_search = True

2. 迭代缩小目标上界（剪枝法） #

利用启发式解的结果作为初始上界，逐步添加约束缩小搜索范围，直到求解器证明无法找到更优解：

# 初始上界为pywrapcp启发式解的最大距离
current_upper_bound = 2192
best_max_distance = current_upper_bound

while True:
    # 每次循环重新构建模型（或复用模型修改约束）
    solver = pywrapcp.Solver("VRP-PD")
    # ... 此处省略VRP-PD模型构建代码（节点分配、路径顺序、距离计算等） ...
    
    # 添加最大距离约束
    max_distance_var = solver.IntVar(0, current_upper_bound, "max_distance")
    solver.Add(max_distance_var == solver.Max([vehicle_distance_vars[i] for i in range(num_vehicles)]))
    solver.Add(max_distance_var <= current_upper_bound)
    
    # 自定义决策构建器，优先处理距离接近上界的车辆
    decision_builder = solver.Phase(
        vehicle_distance_vars,
        solver.CHOOSE_MAX_VALUE,  # 优先选择当前距离最大的车辆变量
        solver.ASSIGN_MIN_VALUE   # 尝试给该车辆分配更小的距离值
    )
    
    status = solver.Solve(decision_builder)
    if status == solver.OPTIMAL or status == solver.FEASIBLE:
        # 更新最优解和上界
        best_max_distance = solver.Value(max_distance_var)
        current_upper_bound = best_max_distance - 1
    else:
        # 无解，说明当前上界以下无可行解，停止迭代
        break

print(f"最优最大行驶距离: {best_max_distance}")

3. 自定义分支决策策略 #

通过Phase()方法指定变量选择和值选择逻辑，引导求解器优先探索更优的解空间：

• 变量选择：优先选择未完成任务最多、或当前行驶距离最大的车辆对应的变量
• 值选择：优先选择能减少车辆行驶距离的任务分配方案

CPSAT代码通用改进建议 #

基于VRP-PD的CPSAT建模常规优化方向，给出以下建议：

1. 目标函数优化 #

直接使用CPSAT原生的MinimizeMax约束处理最小化最大行驶距离的目标，避免手动构建复杂的目标函数：

from ortools.sat.python import cp_model

model = cp_model.CpModel()
# vehicle_distances为每个车辆的行驶距离变量列表
model.MinimizeMax(vehicle_distances)

2. 约束精简与强化 #

• 对于取货-送货的顺序约束，使用AddSequenceConstraint替代多个顺序约束，提升求解效率：

  # pickup_vars[i]为取货点i的访问时间变量，delivery_vars[i]为对应送货点的访问时间变量
  model.AddSequenceConstraint([pickup_vars[i], delivery_vars[i]], [], [])
  

• 车辆容量约束使用Cumulative约束建模，而非手动累加，求解器对累积约束的处理更高效。

3. 缩小变量域范围 #

• 为车辆行驶距离变量设置合理的上下界：下界为车辆必须完成任务的最短路径之和，上界用启发式解的最大距离，减少搜索空间
• 严格设置时间窗变量的上下界（若问题包含时间窗约束），避免不必要的取值范围。

4. 求解器参数调优 #

• 设置足够的求解时间：model.parameters.max_time_in_seconds = 300（根据问题规模调整）
• 开启搜索日志：model.parameters.log_search = True，便于定位搜索瓶颈
• 尝试组合搜索策略：model.parameters.search_branching = cp_model.PORTFOLIO_SEARCH，让求解器自动选择最优分支策略

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