路由选项

本部分将介绍路由求解器的一些选项。

搜索限制

搜索限制会在达到指定限制值(例如最长时间限制或找到的解决方案数)后终止求解器。您可以通过求解器的搜索参数设置搜索限制。如需查看示例,请参阅时间限制

下表介绍了最常见的搜索限制。

名称 类型 默认 说明
solution_limit int64 kint64max 限制在搜索期间生成的解决方案数量。
time_limit.seconds int64 kint64max 搜索所花的时间(以秒为单位)。
lns_time_limit.seconds int64 100 时长限制(以秒为单位),表示每个本地搜索邻居的完成搜索。

第一种解决方案策略

第一种解决方案策略是求解器用来查找初始解决方案的方法。下表列出了 first_solution_strategy 的选项。

选项 说明
AUTOMATIC 让求解器根据所解决的模型检测要使用的策略。
PATH_CHEAPEST_ARC 从路由“start”节点开始,连接到生成最便宜的路由段的节点,然后通过迭代添加到该路由的最后一个节点来扩展该路由。
PATH_MOST_CONSTRAINED_ARC PATH_CHEAPEST_ARC 类似,但弧线是使用基于比较的选择器求值的,它将优先用于限制程度最高的弧线。如需为路由模型分配选择器,请使用 ArcIsMoreConstrainedThanArc() 方法。
EVALUATOR_STRATEGY PATH_CHEAPEST_ARC 类似,但弧线费用是使用传递给 SetFirstSolutionEvaluator() 的函数进行评估。
SAVINGS 储蓄算法(Clarke 和 Wright)。 参阅 Clarke, G. 和 Wright, J.W. “Schedule the Vehicles from Central Central Depot to A number of Delivery points”,《运营研究》,1964 年第 12 卷,第 568-581 页。
SWEEP 扫描算法(Wren 和 Holliday)。 参考 Anthony Wren 和 Alan Holliday 针对从一台或多辆仓库到特定数量的交付点运营研究季度(1970-1977 年)第 23 卷第 3 期(9 月1972 年)第 333-344 页。
CHRISTOFIDES 克里斯托维德算法(实际上是克里斯托维斯算法的变体,使用最大匹配而不是最大匹配),这无法保证公差旅行销售人员近似值的 3/2 系数。通过扩展路由(使其上不能插入任何节点)来对通用车辆路由模型运行。 参考 Nicos Christofides,对旅行推销员问题进行启发式分析的最糟糕案例,报告 388,工商管理研究生院,CMU,1976 年。
ALL_UNPERFORMED 将所有节点设为非活动状态。仅当节点为可选时才是解法(节点是取值约束的元素,且有一定的处罚成本)。
BEST_INSERTION 以最便宜的位置插入最便宜的节点,反复构建解决方案;插入费用取决于路由模型的全局成本函数。从 2012 年 2 月开始,仅适用于具有可选节点(且惩罚成本有限)的模型。
PARALLEL_CHEAPEST_INSERTION 通过将费用最低的节点插入成本最低的位置反复构建解决方案;插入费用取决于弧线函数。比 BEST_INSERTION 快。
LOCAL_CHEAPEST_INSERTION 通过将每个节点以最低成本插入来迭代构建解决方案;插入费用取决于弧线函数。与 PARALLEL_CHEAPEST_INSERTION 的差异(由选择插入的节点导致);在此处,节点按照其创建顺序来考虑。比 PARALLEL_CHEAPEST_INSERTION 快。
GLOBAL_CHEAPEST_ARC 迭代连接生成最便宜的路由段的两个节点。
LOCAL_CHEAPEST_ARC 选择第一个具有未绑定后继节点的节点,并将其连接到产生最便宜的路由段的节点。
FIRST_UNBOUND_MIN_VALUE 选择具有未绑定后继的第一个节点,并将其连接到第一个可用节点。这相当于将 CHOOSE_FIRST_UNBOUND 策略与 ASSIGN_MIN_VALUE (cf.constraint_solver.h) 结合使用。

搜索状态

您可以使用路由模型的 status 方法返回搜索状态。以下用于输出搜索状态的 Python 代码:

print("Solver status: ", solver.status())

这会输出一个具有以下含义的整数:

说明
0 ROUTING_NOT_SOLVED:问题尚未解决。
1 ROUTING_SUCCESS:问题已成功解决。
2 ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED:在调用 RoutingModel.Solve() 后已成功解决的问题,除非未实现局部优化。留出更多时间有助于改进解决方案。
3 ROUTING_FAIL:找不到问题的解决方案。
4 ROUTING_FAIL_TIMEOUT:达到解决方案之前的时间限制。
5 ROUTING_INVALID:模型、模型参数或标志无效。
6 ROUTING_INFEASIBLE:已被证实无法解决的问题。

本地搜索选项

下表列出了本地搜索策略(也称为元探究)的选项。有关设置这些选项的示例,请参阅更改搜索策略

选项 说明
AUTOMATIC 让求解器选择元启发法。
GREEDY_DESCENT 接受改进(降低费用)本地搜索邻居,直到达到本地极小值。
GUIDED_LOCAL_SEARCH 使用引导式本地搜索转义本地最小值。(请参阅引导式本地搜索)这是通常最有效的车辆路线启发法。
SIMULATED_ANNEALING 使用模拟退火来逃避局部最小值(请参阅模拟退化)。
TABU_SEARCH 使用 Tabu 搜索转义本地最小值(请参阅 Tabu 搜索)。
GENERIC_TABU_SEARCH 使用 Tabu 搜索解决方案的目标值来逃避局部最小值。

传播控制

名称 类型 默认 说明
use_full_propagation 布尔值 true 在路由模型中使用完全传播的约束条件(而不是仅采用轻度传播约束条件)。只有在使用深度优先搜索或需要强传播才能使用最终变量的值时,才需要完全传播。在大多数情况下,将此设置更改为 true 会减慢搜索速度,并增加所有情况下的内存消耗。