Google OR-Tools中Tabu list默认值是多少？能否修改用于参数微调？

1. Tabu List 默认值与自定义支持 #

OR-Tools的禁忌搜索实现针对不同求解场景的封装逻辑存在差异，核心规则如下：

• 针对路由求解器（Routing Solver）的内置禁忌搜索启发式：默认Tabu List长度为动态计算，取值为求解问题邻域大小的1/10左右，最小值为7，最大值不超过30。
• 该参数完全支持自定义修改，你可以通过SetTabuListSize()方法直接指定固定长度，示例代码片段如下：

# Python 调用示例
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

# 初始化求解器后配置搜索参数
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.local_search_metaheuristic = (
    routing_enums_pb2.LocalSearchMetaheuristic.TABU_SEARCH
)
# 自定义Tabu List长度为15
search_parameters.tabu_search_parameters.tabu_list_size = 15

2. Tabu List 及相关禁忌搜索参数调整建议 #

• Tabu List长度调整核心逻辑
  • 短Tabu List：适合小规模问题、邻域结构简单的场景，能加快搜索收敛速度，但容易陷入局部最优，出现循环搜索的概率更高。如果你的求解结果质量波动大、多次运行得到的最优解差异大，可以先尝试调小Tabu长度。
  • 长Tabu List：适合大规模问题、多局部最优的复杂场景，能有效规避搜索循环，扩大全局搜索范围，但会拖慢收敛速度。如果你的求解结果长期卡在同一个次优解无法突破，优先尝试调大Tabu长度。
  • 通用经验值：取值范围通常在问题变量数的1%_{10%之间，对于大多数VRP、调度类场景，初始测试可以先设置为10}20，再根据运行结果迭代调整。
• 配套参数协同调整建议
  • 禁忌任期：和Tabu List长度配合调整，如果你开启了动态Tabu任期，建议任期的上下限区间和Tabu List长度保持1:2的比例，比如Tabu长度设为20，任期可以设为5~10动态变化。
  • 特赦规则：如果设置了较长的Tabu List，建议同时开启aspiration criteria（特赦准则），当禁忌操作能得到比当前全局最优解更优的结果时，直接解除禁忌，避免错过最优解。
  • 搜索终止条件：调长Tabu List后要同步拉长搜索时长/迭代次数上限，给足全局搜索的空间，否则可能还没收敛就提前终止求解。

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