or-tools 车辆路径问题求解库:Routing 模块从模型构建到参数调优完整指南
or-tools 车辆路径问题求解库:Routing 模块从模型构建到参数调优完整指南
导读
本文围绕 or-tools 仓库中 ortools/routing/README.md 所指向的车辆路径(Vehicle Routing)求解能力展开,系统讲解其核心模型类 routing.h、参数定义 routing_parameters.proto 与 routing_enums.proto、解的表达方式 assignment.proto,以及 ortools/routing/parsers 子目录中丰富的标准文件格式解析器。读完本文,你将掌握:如何用 Routing 模型表达从旅行商问题(TSP)到带时间窗的容量受限车辆路径问题(CVRPTW)的一整类问题,如何配置首解启发式、局部搜索邻域与元启发式参数,以及如何接入 TSPLIB、Solomon、CARPLIB 等业界标准测试数据。
Routing 模块定位:构建在 CP 求解器之上的车辆路径库
README 的第一句话就点明了模块的本质:
Vehicle Routing 是一个构建在 CP solver 库之上的有用扩展。
这里的 CP solver 指的是 ortools/constraint_solver 中的约束规划库。车辆路径库是叠加在约束编程库之上的一个垂直层(vertical layer),因此你可以在路由模型之上继续访问其底层所有受约束的变量,并用约束编程库提供的任意约束对模型进行增强。routing.h 的文档注释明确写道:这一层使得你能够建模并求解通用的车辆路径问题,范围从旅行商问题(TSP)一直到更复杂的带时间窗容量受限车辆路径问题(CVRPTW)。
需要特别强调的一点是,"车辆路径"只是历史叫法。任何"需要以最优方式访问给定数量节点的路径规划"问题都可以归入这一类——例如为一首歌排定最优播放顺序(playlist sequencing)。目标通常是:在满足问题特定约束(如路线长度限制)的前提下,构建覆盖全部节点的路径集合,并最小化整体成本(通常正比于路径各段长度之和);一条路线等价于连接节点的路径,从指定起点出发、在指定终点结束(见 routing.h)。
从源码结构看,该库的核心部件包括:
| 组件 | 文件 | 作用 |
|---|---|---|
| 模型类 | routing.h | 建模与求解的主入口(RoutingModel、RoutingDimension 等) |
| 求解参数 | routing_parameters.proto | 搜索参数(首解启发式、局部搜索邻域、元启发式等) |
| 枚举定义 | routing_enums.proto | 定义参数取值(首解策略、元启发式、求解状态) |
| 解的表达 | assignment.proto | 以约束问题赋值(Assignment)的形式保存路由问题的解 |
| 文件解析器 | ortools/routing/parsers | 解析 TSPLIB、Solomon、CARPLIB 等标准数据格式 |
核心模型:routing.h 中的变量体系与求解框架
模型中的两类变量
RoutingModel 暴露了两组底层变量(见 routing.h):
路径变量(path variables),描述"谁连谁":
next(i):节点i的直接后继节点。注意节点索引是强类型整数(strongly typed integers),需要通过IndexToNode()将"next 变量的值"转回节点编号;vehicle(i):节点i所属的车辆路线;active(i):布尔变量,为真表示节点i被访问。当节点是可选节点(optional)或属于某个析取约束(disjunction)时,该值可以为假。
对任意节点 i,下列关系恒成立:
active(i) == 0 ⇔ next(i) == i ⇔ vehicle(i) == -1
next(i) == j ⇒ vehicle(j) == vehicle(i)
即"节点未激活"等价于"它的后继是自己"等价于"它不属于任何车辆";一旦节点 j 是 i 的后继,二者必然属于同一辆车。
维度变量(dimension variables),用于沿路线累积某种数量(重量、体积、距离或时间):
cumul(i,d):到达节点i时维度d的累积量;transit(i,d):访问节点i之后维度d的增加量。
对任意 (i,d) 恒有:
next(i) == j ⇒ cumul(j,d) == cumul(i,d) + transit(i,d)
这是后续容量约束(累积载重不超过车辆容量)与时间窗约束(到达时间落在窗口内)的代数基础。
求解方式:局部搜索为主,精确方法为辅
RoutingModel 的求解主要依赖近似方法——即局部搜索(local search),可以结合基于动态规划和穷举树搜索的精确技术。本地搜索从一个可行解出发,反复用邻域算子生成候选邻居并接受改进,直至达到局部最优或搜索限制(见 routing.h)。
顶层搜索调优 Flags
在 RoutingModel 的文档注释中(见 routing.h),给出了一组直接可用的顶层 flag 作为快速调优入口:
限制搜索:
routing_solution_limit(默认kint64max):找到routing_solution_limit个改进解后停止搜索;routing_time_limit(默认kint64max):搜索超过routing_time_limit毫秒后停止。
定制搜索方式:
routing_first_solution:选择构建初始解的启发式,初始解随后交给局部搜索改进。可能取值包括GlobalCheapestArc(反复连接能产生最便宜路径段的一对节点)、LocalCheapestArc(选取第一个后继未绑定的节点,连接到能产生最便宜路径段的节点)、PathCheapestArc(从路线起点出发连接到最便宜的节点,然后不断沿最后加入的节点扩展路线);routing_no_lns(默认 false):禁止使用大邻域搜索(LNS)。LNS 能找到优质解,但通常很慢;routing_no_tsp(默认 true):禁止用精确方法求解当前模型的"子 TSP"(如路线的一部分,或多路线问题中的单条路线)。这类 TSP 用动态规划求解,最大规模由cp_local_search_tsp_opt_size控制(默认 13 个节点)。默认关闭是因为它可能拖慢搜索。
元启发式(跳出局部最优)。注意:开启元启发式后,搜索通常不会自然停止,必须显式设置搜索限制:
routing_guided_local_search(默认 false):激活引导式局部搜索(Guided Local Search),通常是对车辆路径问题最有效的元启发式;routing_simulated_annealing(默认 false):模拟退火;routing_tabu_search(默认 false):禁忌搜索。
一个最小的 TSP 代码骨架
routing.h 给出了一个求解 TSP 的最小可运行流程:给定成本回调(返回任意两个节点之间路径段的代价),即可建模求解。
// 1. 自定义距离/成本函数(这里简单返回索引之和)
int64_t MyDistance(int64_t from, int64_t to) {
return from + to;
}
// 2. 创建路由模型:指定节点数与路线数(这里为 1)
RoutingIndexManager manager(...number of nodes..., 1);
RoutingModel routing(manager);
// 3. 注册成本回调并设为所有车辆的弧成本
const int cost = routing.RegisterTransitCallback(MyDistance);
routing.SetArcCostEvaluatorOfAllVehicles(cost);
// 4. 求解(解由 routing 持有)
const Assignment* solution = routing.Solve();
CHECK(solution != nullptr);
// 5. 读取解的成本与路线
LOG(INFO) << "Cost " << solution->ObjectiveValue();
const int route_number = 0;
for (int64_t node = routing.Start(route_number);
!routing.IsEnd(node);
node = solution->Value(routing.NextVar(node))) {
LOG(INFO) << manager.IndexToNode(node);
}
RoutingIndexManager 负责把"节点编号"与"路径变量索引"相互转换,是建模的第一步;RegisterTransitCallback 将 std::function<int64_t(int64_t, int64_t)> 注册进模型并返回回调索引,随后通过 SetArcCostEvaluatorOfAllVehicles 将其作为成本函数。
参数体系:routing_parameters.proto
routing_parameters.proto 中定义了求解搜索所用的全部参数。文件开头的注释给出一个重要约定:如果某个参数未设置(即保持默认值),路由库会自动挑选它偏好的取值——大多数参数都应保持这种"让库自己决定"的状态。若要查看这些实际生效的默认参数,调用 GetDefaultRoutingSearchParameters() 即可。
RoutingSearchParameters:核心消息
RoutingSearchParameters(见 routing_parameters.proto)按功能可分为以下几组:
首解策略(First solution strategies):
first_solution_strategy:作为局部搜索起点的首解策略,取值为FirstSolutionStrategy.Value枚举(见下节);use_unfiltered_first_solution_strategy:若存在过滤版本,是否使用未过滤的首解策略(高级设置,默认不动);savings_parameters:Savings 启发式的参数(Clarke & Wright 算法);global_cheapest_insertion_first_solution_parameters/global_cheapest_insertion_ls_operator_parameters:全局最便宜插入启发式的参数(分别用于首解阶段与局部搜索算子阶段);local_cheapest_insertion_parameters/local_cheapest_cost_insertion_parameters:局部最便宜插入启发式参数;christofides_use_minimum_matching:Christofides 算法中使用最小匹配而非最大匹配;first_solution_optimization_period:非零时表示每完成p次节点插入/添加就对当前部分解做一次优化(截至 2023/12,要求主模型传入次级路由模型,且仅支持LOCAL_CHEAPEST_INSERTION与LOCAL_CHEAPEST_COST_INSERTION)。
局部搜索邻域算子(LocalSearchNeighborhoodOperators):local_search_operators 嵌套消息用 OptionalBoolean 开关逐个控制每个邻域算子(见下节)。另有 ls_operator_neighbors_ratio、ls_operator_min_neighbors 控制邻域规模,use_multi_armed_bandit_concatenate_operators 让求解器用多臂老虎机动态挑选下一个邻域算子以获得最优目标改进。
元启发式(Metaheuristics):
local_search_metaheuristic:引导搜索跳出局部最优的元启发式;local_search_metaheuristics+num_max_local_optima_before_metaheuristic_switch:每隔若干局部最优切换元启发式;guided_local_search_lambda_coefficient:GLS 中惩罚弧成本用的 λ 系数(必须为正);guided_local_search_reset_penalties_on_new_best_solution:找到新最优解时是否重置惩罚。
搜索控制与限制:
use_depth_first_search:使用深度优先搜索而非局部搜索;use_cp/use_cp_sat/use_generalized_cp_sat:选择底层求解器。若同时启用 CP 与 CP-SAT,CP-SAT 会在剩余时间内运行,并以 CP 解作为提示。截至 2019/5,use_cp_sat只能解 TSP 模型;sat_parameters:启用 CP-SAT 时使用的 SAT 算法参数;fallback_to_cp_sat_size_threshold:模型规模小于该阈值且未找到解时,尝试一轮 CP-SAT;solution_limit:生成的解数量上限(0 表示未指定);time_limit(google.protobuf.Duration):搜索时间上限;lns_time_limit:每个局部搜索邻居的完成搜索时间上限;secondary_ls_time_limit_ratio:在只含路线内与插入算子的第二阶段 LS 上花费的时间占整体时间上限的比例(用于"清理"当前解);optimization_step:局部搜索中解必须改进的最小步长(0 表示未指定);number_of_solutions_to_collect:搜索中要收集的解数量(0 表示未指定)。
传播控制与杂项:
use_full_propagation:是否在路由模型中使用全传播约束而非"轻量"传播。全传播只在深度优先搜索或需要强传播确定次级变量值时必要,开启通常拖慢搜索并增加内存;log_search:开启搜索日志,对每个找到的解输出目标值、已用时间、分支/失败次数、局部搜索邻居数、内存占用、搜索完成百分比等;log_cost_scaling_factor/log_cost_offset:日志中成本的缩放与偏移(按log_cost_scaling_factor * (cost + log_cost_offset)展示);log_tag:每行新解日志附加的标签,便于并行求解时区分日志;use_iterated_local_search与iterated_local_search_parameters:是否使用迭代局部搜索框架。
RoutingModelParameters:建模型时的参数
同文件还定义了创建 RoutingModel 时必须设置的参数(见 routing_parameters.proto):
solver_parameters:底层约束求解器的参数;reduce_vehicle_cost_model:当所有车辆具有完全相同的成本结构时,尝试约简底层约束模型,可带来显著加速;max_callback_cache_size:当模型节点数不超过该值时,缓存回调调用结果。
枚举定义:routing_enums.proto
routing_enums.proto 提供定义路由参数所需的全部枚举。
FirstSolutionStrategy.Value:首解启发式全集
UNSET(0):未设置,行为同AUTOMATIC,但在 protoMergeFrom时不会覆盖其他值;AUTOMATIC(15):让求解器根据模型自动选择策略;- 路径添加类启发式:
PATH_CHEAPEST_ARC(3,从起点出发不断接最便宜的弧扩展路线)、PATH_MOST_CONSTRAINED_ARC(4,用基于比较的选择器优先考虑约束最强的弧)、EVALUATOR_STRATEGY(5,用SetFirstSolutionEvaluator()传入的求值函数)、SAVINGS(10,Clarke & Wright 节约算法)、PARALLEL_SAVINGS(17,节约算法的并行版)、SWEEP(11,扫描算法)、CHRISTOFIDES(13,Christofides 算法变体); - 路径插入类启发式:
ALL_UNPERFORMED(6,全部节点不执行,仅当节点为可选且有有限惩罚成本时可行)、BEST_INSERTION(7,按全局成本函数做最便宜插入)、PARALLEL_CHEAPEST_INSERTION(8,按弧成本做并行最便宜插入,比前者快)、SEQUENTIAL_CHEAPEST_INSERTION(14,按弧成本逐路线顺序插入,更快)、LOCAL_CHEAPEST_INSERTION(9,按弧成本插入且最远节点优先,比顺序版更快)、LOCAL_CHEAPEST_COST_INSERTION(16,同前但基于模型成本函数而非仅弧成本); - 基于变量的启发式:
GLOBAL_CHEAPEST_ARC(1,反复连接产生最便宜路径段的一对节点)、LOCAL_CHEAPEST_ARC(2,选第一个后继未绑定的节点连到最便宜节点)、FIRST_UNBOUND_MIN_VALUE(12,选第一个后继未绑定节点连到第一个可用节点)。
LocalSearchMetaheuristic.Value:元启发式全集
UNSET(0)与AUTOMATIC(6):同前约定;GREEDY_DESCENT(1):只接受改进邻居直到局部最优;GUIDED_LOCAL_SEARCH(2):引导式局部搜索,一般对车辆路径最有效;SIMULATED_ANNEALING(3):模拟退火;TABU_SEARCH(4):禁忌搜索;GENERIC_TABU_SEARCH(5):对一组变量做禁忌搜索,变量列表需通过SetTabuVarsCallback回调提供。
RoutingSearchStatus.Value:求解状态
RoutingModel::Solve() 之后可通过该枚举获知求解结果:
ROUTING_NOT_SOLVED(0):尚未求解;ROUTING_SUCCESS(1):成功求解;ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED(2):成功求解但未达到局部最优,留更多时间可改进;ROUTING_FAIL(3):未找到解;ROUTING_FAIL_TIMEOUT(4):超时未找到解;ROUTING_INVALID(5):模型、参数或 flags 不合法;ROUTING_INFEASIBLE(6):问题被证明不可行;ROUTING_OPTIMAL(7):已求解到最优。
解的表达:assignment.proto
路由问题的解以约束编程问题的赋值(Assignment)形式保存,这在 assignment.proto 中定义。AssignmentProto 是容纳所有赋值变量与目标的全局容器,包含:
IntVarAssignment:整数变量赋值(var_id、min/max区间、active);IntervalVarAssignment:区间变量赋值(起止时间、时长、是否执行);SequenceVarAssignment:序列变量赋值(正序/逆序序列、未执行节点);objective:目标函数对应的整型变量赋值;worker_info:该赋值由哪个 worker 产生;is_valid:该赋值是否有效。
在 API 层,RoutingModel::Solve() 返回的 const Assignment*(由模型持有)同样提供了 ObjectiveValue()、Value(IntVar) 等方法供读取目标值与每条路线的节点序列,如上面 TSP 骨架示例所示。
实战:CVRPTW 完整示例
仓库中的 ortools/routing/samples/cvrptw.cc 是一个完整的"带时间窗的容量受限车辆路径问题(CVRPTW,可含可选订单)"示例,把上述 API 全部串了起来。其建模流程与 README 的指引一一对应:
1. 创建索引管理器与模型(cvrptw.cc):订单数为 FLAGS_vrp_orders,节点编号从 0 开始,起点与终点都在 depot(节点 0):
const RoutingIndexManager::NodeIndex kDepot(0);
RoutingIndexManager manager(orders + 1, vehicles, kDepot);
RoutingModel routing(manager);
2. 设置成本函数(cvrptw.cc):注册一个返回曼哈顿距离的回调并设为所有车辆的弧成本:
const int vehicle_cost = routing.RegisterTransitCallback(
&locations, &manager {
return locations.ManhattanDistance(manager.IndexToNode(i),
manager.IndexToNode(j));
});
routing.SetArcCostEvaluatorOfAllVehicles(vehicle_cost);
3. 添加容量维度(cvrptw.cc):AddDimension 接受四个关键参数——注册的回调索引(返回两个节点间的 transit 量)、最大松弛量(此处为 0,即不允许等待)、容量(此处为 40)、是否将起点累计量固定为 0,以及维度名:
routing.AddDimension(routing.RegisterTransitCallback(
&demand, &manager {
return demand.Demand(manager.IndexToNode(i),
manager.IndexToNode(j));
}),
kNullCapacitySlack, kVehicleCapacity,
/*fix_start_cumul_to_zero=*/true, kCapacity);
4. 添加时间维度与时间窗口(cvrptw.cc):时间维度同样用 AddDimension 创建(服务水平线为 24 小时),随后通过 GetDimensionOrDie(kTime) 取回维度对象,再对每个订单的 CumulVar 用 SetRange(start, start + kTWDuration) 限定到达时间窗口:
const RoutingDimension& time_dimension = routing.GetDimensionOrDie(kTime);
time_dimension.CumulVar(order)->SetRange(start, start + kTWDuration);
5. 允许跳单(析取约束)(cvrptw.cc):对每个订单单独构造一个含该节点的集合调用 AddDisjunction(orders, kPenalty),用一个大惩罚成本让求解器在"跳过该订单"与"付出代价访问它"之间权衡:
std::vector<int64_t> orders(1, manager.NodeToIndex(order));
routing.AddDisjunction(orders, kPenalty);
6. 软性同车约束(cvrptw.cc):用 AddSoftSameVehicleConstraint(group, kSameVehicleCost) 让一组节点尽量由同一辆车服务。
7. 求解(cvrptw.cc):先取默认参数 DefaultRoutingSearchParameters(),再用文本格式 proto 覆盖(TextFormat::MergeFromString,可通过 --routing_search_parameters 传入部分字段),最后调用 SolveWithParameters:
RoutingSearchParameters parameters = DefaultRoutingSearchParameters();
CHECK(google::protobuf::TextFormat::MergeFromString(
absl::GetFlag(FLAGS_routing_search_parameters), ¶meters));
const Assignment* solution = routing.SolveWithParameters(parameters);
该示例还演示了其余常用建模 API:AddDimensionWithVehicleCapacity(每辆车独立容量)、AddConstantDimension(常量 transit)、AddPickupAndDelivery(取送货配对)、SetAllowedVehiclesForIndex(限制节点可用的车辆集合)、AddResourceGroup(资源组)以及 RoutingDimension::SetBreakIntervalsOfVehicle(车辆休息区间)等,均可从 routing.h 的类定义中找到。同目录下 ortools/routing/samples 还提供了带中途休息、加油、资源、时间依赖成本、软容量、前置约束等扩展变体(如 cvrptw_with_breaks.cc、cvrptw_with_resources.cc、cvrptw_with_time_dependent_costs.cc),并有对应的 .bintest 测试脚本验证求解结果。
标准文件格式解析器:ortools/routing/parsers
README 指出:文件格式的解析工具位于 parsers 子目录。该目录的 README.md 给出了一个完整的格式对照表:
| 问题类型 | 文件格式 | 对应解析器 | 数据存储 | 数据集 |
|---|---|---|---|---|
| TSP | TSPLIB | tsplib_parser.h |
— | TSPLIB95 |
| TSPTW | TSPTW | tsptw_parser.h |
— | TSPTW |
| PDTSP / TSPPD | PDTSP | pdtsp_parser.h |
— | PDTSP |
| CVRP | TSPLIB | tsplib_parser.h |
— | TSPLIB95 |
| VRPTW | Solomon | solomon_parser.h |
— | Solomon、Homberger |
| CARP | CARPLIB | carp_parser.h |
— | CARPLIB |
| NEARP | NEARPLIB | nearp_parser.h |
— | NEARPLIB |
| PDPTW | LiLim | lilim_parser.h |
— | LiLim |
| MCND | Dow | dow_parser.h |
capacity_planning.proto |
Canad |
每个解析器都有对应的实现与单元测试,例如 solomon_parser.cc/solomon_parser_test.cc、carp_parser.cc/carp_parser_test.cc、nearp_parser.cc/nearp_parser_test.cc、tsplib_parser.cc/tsplib_parser_test.cc 等。解析器均提供统一的 LoadFile() 接口,例如 solomon_parser.h 中的 SolomonParser::LoadFile(file_name)(失败时返回 false,重新加载会清空之前实例),还支持从 zip 压缩包内加载实例;SolomonSolutionParser 则用于加载对应的已知最优解文件,便于验证你的解与业界最优解的差距。
测试数据集中在 ortools/routing/parsers/testdata,包括:
- Solomon 基准集(
solomon.zip、C1_10_2.TXT、n20w20.001.txt等 VRPTW 实例); - TSPLIB 实例(
tsplib_F-n45-k4.vrp、tsplib_ar9152.tsp及其.tour解文件); - CARPLIB 实例(
carp_gdb19.dat及一组故意构造的错误格式文件,用于校验解析器的容错性); - LiLim PDPTW 集(
lilim.zip、pdptw_LRC2_10_6.txt); - NEARP 实例(
nearp_BHW1.dat、nearp_toy.dat)。
此外,solution_serializer.h 提供了一个通用的路由解序列化器,可将求解结果输出为多种格式。parsers 目录的 README 还预告:未来该目录将承载整个路由求解器。
总结
or-tools 的 Routing 模块以约束编程库为底座,用 RoutingModel 暴露 next/vehicle/active 路径变量与 cumul/transit 维度变量,将 TSP 到 CVRPTW 的一整类路径优化问题统一建模;配合 routing_parameters.proto 中的首解启发式、局部搜索邻域、元启发式与搜索限制参数,以及 routing_enums.proto 中的枚举体系,可以精细控制搜索过程;求解结果以 assignment.proto 形式的赋值保存,通过 SolveWithParameters 返回。对于工程落地,ortools/routing/parsers 提供的 TSPLIB、Solomon、CARPLIB、NEARP、LiLim、Dow 等标准格式解析器,可以让你直接接入业界公开测试集验证算法效果。进一步的可运行参考,可研读 ortools/routing/samples/cvrptw.cc 及其同目录下的扩展变体示例。