如何配置or-tools以获取非对称旅行商问题(ATSP)的全局最优解？

• 启用精确求解模式
  OR-Tools的Routing模块默认偏向启发式快速求解，要拿到全局最优，得切换到精确求解逻辑：

  from ortools.constraint_solver import routing_enums_pb2
  
  search_parameters = pywrapcp.DefaultRoutingSearchParameters()
  # 启用完整传播，强化约束剪枝能力
  search_parameters.use_full_propagation = True
  # 设置目标gap为0，要求求解器找到无间隙的最优解
  search_parameters.target_gap = 0.0
  # 开启搜索日志，方便查看最优性证明过程
  search_parameters.log_search = True
  

  开启日志后，运行时会输出搜索细节，当出现Optimal solution found或者Current gap: 0.0%这类提示时，说明当前解就是全局最优。

• 调整终止条件与时间限制
  你之前设置的超大时间限制没问题，可以配合search_parameters.stop_when_complete = True，让求解器找到最优解后立刻停止，不用耗满时间。如果长时间运行后日志里始终没出现最优性提示，说明问题规模太大，OR-Tools的精确求解在当前时间内无法完成，这时候要么继续延长时间，要么考虑问题节点数是否超出了精确求解的可行范围（一般ATSP节点数超过50，精确求解就会非常耗时）。

• 确认ATSP模型正确性
  务必确保你正确定义了非对称成本矩阵——ATSP的往返成本不同，要通过routing.SetArcCostEvaluatorOfAllVehicles(cost_evaluator)传入非对称的成本计算逻辑，而非对称距离矩阵。如果模型定义错误，再怎么调参数也拿不到正确的最优解。

• 大规模问题的替代方案
  如果节点数超过50，OR-Tools的精确求解可能很难在合理时间内完成全局最优解。这时候可以考虑：

  • 定制分支定界的剪枝规则（需要深入修改OR-Tools的求解逻辑）
  • 先用启发式算法得到高质量初始解，再通过局部搜索持续优化，同时监控gap变化，当gap稳定为0时确认最优

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