本部分将介绍路由求解器的一些选项。
搜索限制
搜索限制会在达到指定限制值(例如最长时间限制或找到的解决方案数)后终止求解器。您可以通过求解器的搜索参数设置搜索限制。如需查看示例,请参阅时间限制。
下表介绍了最常见的搜索限制。
名称 | 类型 | 默认 | 说明 |
---|---|---|---|
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 会减慢搜索速度,并增加所有情况下的内存消耗。 |