OR-Tools 约束求解器(CP Solver)与车辆路径求解器(Routing Solver)模块完全指南
OR-Tools 约束求解器(CP Solver)与车辆路径求解器(Routing Solver)模块完全指南
导读
本文聚焦 Google OR-Tools 仓库中 ortools/constraint_solver 目录所承载的两大求解器:源自人工智能技术的约束编程(Constraint Programming, CP)求解器,以及在其之上垂直构建的车辆路径(Vehicle Routing)求解器。你将系统掌握该模块的源码组织(核心头文件、参数协议缓冲区、解表示协议缓冲区)、全部关键配置参数的含义与取值,并通过 C++、Python、Java、.NET 四种语言的完整可运行示例,掌握从"建模—设置搜索—求解—解析结果"的完整实战链路。
模块定位:一个目录,两个求解器
ortools/constraint_solver/README.md 明确指出,该目录同时包含两个求解器:
- CP 求解器:约束编程是一种源自人工智能(AI)领域、被广泛用于运筹学(Operations Research)的技术,它从海量候选中寻找满足任意约束的可行解;
- Routing 求解器:车辆路径(Vehicle Routing)是建立在 CP 求解器库之上的一种实用扩展,用于在满足约束的前提下为车辆寻找最优路径。
两个求解器共享底层搜索框架与解表示(Assignment),这也是它们被放在同一目录下的原因。从 docs/README.md 可以看到 OR-Tools 的官方建议:对于新的约束编程问题,官方强烈推荐使用 CP-SAT 求解器 而非原版 CP 求解器——原版 CP 求解器主要用于为 Routing 求解器提供底层支撑。这一"推荐替代"的说明来自仓库官方文档,是理解模块演进的重要背景。
CP 求解器:核心对象与扩展接口
核心头文件:constraint_solver.h
constraint_solver.h 声明了约束求解器的全部核心对象,文件头部自带一个经典的"鸡兔同笼"入门示例(56 条腿、20 个头,求鸡兔各多少)。该示例展示了核心 API 的完整使用流程:
void pheasant() {
Solver s("pheasant");
// 创建整数变量:鸡与兔的数量,范围 [0, 20]
IntVar* const p = s.MakeIntVar(0, 20, "pheasant");
IntVar* const r = s.MakeIntVar(0, 20, "rabbit");
// 头数 = 鸡 + 兔
IntExpr* const heads = s.MakeSum(p, r);
// 腿数 = 鸡 * 2 + 兔 * 4
IntExpr* const legs = s.MakeSum(s.MakeProd(p, 2), s.MakeProd(r, 4));
// 约束:腿数 56、头数 20
s.AddConstraint(s.MakeEquality(legs, 56));
s.AddConstraint(s.MakeEquality(heads, 20));
// 定义搜索决策:优先选择第一个未绑定变量并赋最小值
DecisionBuilder* const db = s.MakePhase(p, r,
Solver::CHOOSE_FIRST_UNBOUND,
Solver::ASSIGN_MIN_VALUE);
s.NewSearch(db);
CHECK(s.NextSolution());
LOG(INFO) << "rabbits -> " << r->Value() << ", pheasants -> " << p->Value();
s.EndSearch();
}
该示例揭示 CP 求解器的五个核心抽象:
Solver:求解器实例,负责管理变量、约束与搜索;IntVar/IntExpr:整数变量与整数表达式(可由变量组合而来,如MakeSum、MakeProd);Constraint:通过MakeEquality等构造器创建、再由AddConstraint加入求解器;DecisionBuilder:由MakePhase创建,封装了变量选择策略与值选择策略;- 搜索生命周期:
NewSearch开启搜索 →NextSolution迭代取出每个解 →EndSearch结束。
扩展接口:constraint_solveri.h
constraint_solveri.h 是与核心头文件配套的扩展集合,包含用于扩展 Constraint Solver 库的对象(如自定义约束、自定义决策构建器、Demon 机制等底层设施)。如果你的目标是使用开箱即用的功能,只需关注 constraint_solver.h;若要为求解器编写自定义传播器或邻域算子,则需要深入此文件。
参数:solver_parameters.proto
solver_parameters.proto 定义了 ConstraintSolverParameters 消息,包含 CP 求解器的全部参数,按用途可分为四组:
| 参数 | 类型 | 默认语义 / 说明 |
|---|---|---|
compress_trail |
enum | 搜索期间是否压缩 trail:NO_COMPRESSION 更快但更耗内存,COMPRESS_WITH_ZLIB 以 zlib 压缩换取内存节省;压缩在 trail 块级别进行 |
trail_block_size |
int32 | trail 块默认大小,压缩作用于块级别 |
array_split_size |
int32 | 对大型数组做 sum/min/max 运算时,递归拆分为该大小的块 |
store_names |
bool | 是否存储求解器管理对象的名称 |
name_cast_variables / name_all_variables |
bool | 是否给 cast 变量 / 匿名变量命名 |
profile_propagation |
bool | 激活传播分析(propagation profiling) |
profile_file |
string | 将传播分析数据导出到指定文件 |
profile_local_search / print_local_search_profile |
bool | 激活 / 打印局部搜索分析 |
trace_propagation / trace_search |
bool | 传播追踪 / 搜索追踪 |
print_model / print_model_stats / print_added_constraints |
bool | 求解前打印模型、模型统计、已添加约束 |
disable_solve |
bool | 禁用求解(调试用) |
use_small_table |
bool | 是否使用小型 table 约束实现(内部用) |
use_cumulative_edge_finder / use_cumulative_time_table / use_cumulative_time_table_sync |
bool | 控制 cumulative 约束的传播算法(edge finder、time table 等) |
max_edge_finder_size |
int32 | edge finder 的最大规模 |
diffn_use_cumulative |
bool | 控制 diffn 约束传播 |
use_element_rmq |
bool | 是否使用 RMQ(区间最值查询)实现 element 约束 |
skip_locally_optimal_paths |
bool | 在 PathOperators 中跳过局部最优路径对;若存在跨路径约束(如优先关系),置 true 可能跳过有效邻域,其余情况仅加速搜索 |
check_solution_period |
int32 | 局部搜索中周期性校验解的间隔 |
proto 文件明确标注:use_small_table 之后的 101–114 号字段以及"控制搜索"分组中的 disable_solve 等标记为内部使用,日常业务建模无需修改。
搜索限制:search_limit.proto
search_limit.proto 定义了 RegularLimitParameters 消息,用于限制 CP 求解器的搜索空间,这是保证性能的关键:
| 字段 | 类型 | 含义 |
|---|---|---|
time |
int64 | 搜索时间上限(单位待定,proto 中以 TODO 标注) |
branches |
int64 | 分支数上限 |
failures |
int64 | 失败次数上限 |
solutions |
int64 | 找到的解个数上限 |
smart_time_check |
bool | 智能时间检查 |
cumulative |
bool | 限制是否累计 |
proto 注释明确:int64 字段的默认值为最大值 2^63-1,即默认不限。
解表示:assignment.proto 与 demon_profiler.proto
assignment.proto 保存 CP 问题的解(Assignment),是"解"的统一数据载体:
IntVarAssignment:整数变量的赋值(var_id+min/max区间 +active标记);IntervalVarAssignment:区间变量赋值(start/duration/end/performed 各自的 min/max + active);SequenceVarAssignment:序列变量赋值(前向/后向序列、未执行节点列表 + active);WorkerInfo:解的来源信息(worker_id、bns);AssignmentProto:全局容器,聚合所有变量赋值与objective目标值,并带is_valid标志。
demon_profiler.proto 保存约束与 demon(守护进程)的时间线与执行画像,用于性能剖析:当你在 solver_parameters.proto 中打开 profile_propagation 后,即可获得约束传播的逐条剖析数据。
CP 求解器实战:四语言完整示例
CP.md 给出了同构的四语言入门示例:求解 3 个取值 {0,1,2} 的变量,约束 x != y,并统计全部解。以下为各语言完整代码。
C++
#include <ostream>
#include <string>
#include "absl/base/log_severity.h"
#include "absl/log/globals.h"
#include "ortools/base/init_google.h"
#include "ortools/constraint_solver/constraint_solver.h"
namespace operations_research {
void SimpleCpProgram() {
// 实例化求解器。
Solver solver("CpSimple");
// 创建变量。
const int64_t num_vals = 3;
IntVar* const x = solver.MakeIntVar(0, num_vals - 1, "x");
IntVar* const y = solver.MakeIntVar(0, num_vals - 1, "y");
IntVar* const z = solver.MakeIntVar(0, num_vals - 1, "z");
// 约束 0: x != y。
solver.AddConstraint(solver.MakeAllDifferent({x, y}));
LOG(INFO) << "Number of constraints: "
<< std::to_string(solver.constraints());
// 求解问题。
DecisionBuilder* const db = solver.MakePhase(
{x, y, z}, Solver::CHOOSE_FIRST_UNBOUND, Solver::ASSIGN_MIN_VALUE);
// 在控制台打印解。
int count = 0;
solver.NewSearch(db);
while (solver.NextSolution()) {
++count;
LOG(INFO) << "Solution " << count << ":" << std::endl
<< " x=" << x->Value() << " y=" << y->Value()
<< " z=" << z->Value();
}
solver.EndSearch();
LOG(INFO) << "Number of solutions found: " << solver.solutions();
LOG(INFO) << "Advanced usage:" << std::endl
<< "Problem solved in " << std::to_string(solver.wall_time())
<< "ms" << std::endl
<< "Memory usage: " << std::to_string(Solver::MemoryUsage())
<< "bytes";
}
} // namespace operations_research
int main(int argc, char* argv[]) {
InitGoogle(argv[0], &argc, &argv, true);
absl::SetStderrThreshold(absl::LogSeverityAtLeast::kInfo);
operations_research::SimpleCpProgram();
return EXIT_SUCCESS;
}
要点:MakeAllDifferent({x, y}) 是"两两不同"约束;MakePhase 采用 CHOOSE_FIRST_UNBOUND(选择第一个未绑定变量)+ ASSIGN_MIN_VALUE(赋最小可行值)策略;solver.wall_time() 返回求解耗时(毫秒),Solver::MemoryUsage() 返回内存占用(字节)。
Python
#!/usr/bin/env python3
"""Simple Constraint optimization example."""
from ortools.constraint_solver import pywrapcp
def main():
"""Entry point of the program."""
# 实例化求解器。
solver = pywrapcp.Solver("CPSimple")
# 创建变量。
num_vals = 3
x = solver.IntVar(0, num_vals - 1, "x")
y = solver.IntVar(0, num_vals - 1, "y")
z = solver.IntVar(0, num_vals - 1, "z")
# 约束 0: x != y。
solver.Add(x != y)
print("Number of constraints: ", solver.Constraints())
# 求解问题。
decision_builder = solver.Phase(
[x, y, z], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE
)
# 打印解。
count = 0
solver.NewSearch(decision_builder)
while solver.NextSolution():
count += 1
solution = f"Solution {count}:\n"
for var in [x, y, z]:
solution += f" {var.Name()} = {var.Value()}"
print(solution)
solver.EndSearch()
print(f"Number of solutions found: {count}")
print("Advanced usage:")
print(f"Problem solved in {solver.WallTime()}ms")
print(f"Memory usage: {pywrapcp.Solver.MemoryUsage()}bytes")
if __name__ == "__main__":
main()
Python 侧通过 pywrapcp 包装层访问同一套 C++ 求解器,var.Name() 与 var.Value() 与 C++ 一一对应。
Java
package com.google.ortools.constraintsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.DecisionBuilder;
import com.google.ortools.constraintsolver.IntVar;
import com.google.ortools.constraintsolver.Solver;
import java.util.logging.Logger;
/** Simple CP Program.*/
public class SimpleCpProgram {
private SimpleCpProgram() {}
private static final Logger logger = Logger.getLogger(SimpleCpProgram.class.getName());
public static void main(String[] args) throws Exception {
Loader.loadNativeLibraries();
// 实例化求解器。
Solver solver = new Solver("CpSimple");
// 创建变量。
final long numVals = 3;
final IntVar x = solver.makeIntVar(0, numVals - 1, "x");
final IntVar y = solver.makeIntVar(0, numVals - 1, "y");
final IntVar z = solver.makeIntVar(0, numVals - 1, "z");
// 约束 0: x != y。
solver.addConstraint(solver.makeAllDifferent(new IntVar[] {x, y}));
logger.info("Number of constraints: " + solver.constraints());
// 求解问题。
final DecisionBuilder db = solver.makePhase(
new IntVar[] {x, y, z}, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);
// 打印解。
int count = 0;
solver.newSearch(db);
while (solver.nextSolution()) {
++count;
logger.info(
String.format("Solution: %d\n x=%d y=%d z=%d", count, x.value(), y.value(), z.value()));
}
solver.endSearch();
logger.info("Number of solutions found: " + solver.solutions());
logger.info(String.format("Advanced usage:\nProblem solved in %d ms\nMemory usage: %d bytes",
solver.wallTime(), Solver.memoryUsage()));
}
}
注意 Java 侧必须先调用 Loader.loadNativeLibraries() 加载原生库。
.NET
using System;
using Google.OrTools.ConstraintSolver;
/// <summary>
/// This is a simple CP program.
/// </summary>
public class SimpleCpProgram
{
public static void Main(String[] args)
{
// 实例化求解器。
Solver solver = new Solver("CpSimple");
// 创建变量。
const long numVals = 3;
IntVar x = solver.MakeIntVar(0, numVals - 1, "x");
IntVar y = solver.MakeIntVar(0, numVals - 1, "y");
IntVar z = solver.MakeIntVar(0, numVals - 1, "z");
// 约束 0: x != y。
solver.Add(solver.MakeAllDifferent(new IntVar[] { x, y }));
Console.WriteLine($"Number of constraints: {solver.Constraints()}");
// 求解问题。
DecisionBuilder db =
solver.MakePhase(new IntVar[] { x, y, z }, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);
// 打印解。
int count = 0;
solver.NewSearch(db);
while (solver.NextSolution())
{
++count;
Console.WriteLine($"Solution: {count}\n x={x.Value()} y={y.Value()} z={z.Value()}");
}
solver.EndSearch();
Console.WriteLine($"Number of solutions found: {solver.Solutions()}");
Console.WriteLine("Advanced usage:");
Console.WriteLine($"Problem solved in {solver.WallTime()}ms");
Console.WriteLine($"Memory usage: {Solver.MemoryUsage()}bytes");
}
}
Routing 求解器:在 CP 之上建模车辆路径问题
核心头文件:routing.h
routing.h 是车辆路径库的入口,其头部注释给出了权威定位:该库可建模并求解从旅行商问题(TSP)到带时间窗的容量受限车辆路径问题(CVRPTW)的各类通用车辆路径问题。同时指出:
- "车辆路径"是历史称谓,凡是"为若干节点寻找最优访问顺序"的问题都属于此范畴(例如播放列表最优排序);
- 该库是约束编程库之上的垂直层,用户可以访问底层全部约束变量,并用 CP 库中任意约束对模型进行增强;
- 求解主要采用近似方法(局部搜索),可结合动态规划与穷举树搜索等精确技术。
routing.h 还定义了模型的两类核心变量:
- 路径变量(path variables):
next(i):节点 i 的直接后继,用IndexToNode()将路由变量索引转换为用户节点编号;vehicle(i):节点 i 所属车辆路径;active(i):节点 i 是否被访问(可选节点或析取约束中的节点可为 false);- 不变量:
active(i) == 0 <=> next(i) == i <=> vehicle(i) == -1,且next(i) == j => vehicle(j) == vehicle(i);
- 维度变量(dimension variables),用于沿路径累积重量、容积、距离或时间等量:
cumul(i,d):到达节点 i 时维度 d 的累计值;transit(i,d):访问节点 i 后维度 d 的增加量;- 不变量:
next(i) == j => cumul(j,d) == cumul(i,d) + transit(i,d)。
该头文件还记录了调节搜索的经典命令行 flag(供快速调参,现代用法推荐用 proto 参数):routing_solution_limit、routing_time_limit、routing_first_solution、routing_no_lns(禁用大邻域搜索,默认 false)、routing_no_tsp(默认 true,禁用子 TSP 精确求解)、以及 routing_guided_local_search / routing_simulated_annealing / routing_tabu_search 三个元启发式开关。
参数:routing_parameters.proto
routing_parameters.proto 定义 RoutingSearchParameters 消息。其头部注释明确设计哲学:参数未设置(等于默认值)时,路由库自动选择其首选值——大多数参数应保持默认;如需查看这些"默认值",调用 GetDefaultRoutingSearchParameters()。该消息还导入了 solver_parameters.proto(底层 CP 参数)、routing_enums.proto 以及 CP-SAT 参数。
主要字段分组如下:
- 首解策略(first solution):
first_solution_strategy、savings_parameters、global_cheapest_insertion_first_solution_parameters、local_cheapest_insertion_parameters等; - 局部搜索邻域算子(LocalSearchNeighborhoodOperators):这是消息中最庞大的嵌套结构,包含 30+ 个开关(均用
OptionalBoolean),典型算子有:- 跨路径(inter-route):
use_relocate(移动单节点)、use_relocate_pair、use_exchange(交换两节点位置)、use_cross(交叉交换两路径起始链); - 路径内(intra-route):
use_two_opt(逆转路径子链,经典 2-opt)、use_or_opt(移动长度为 1/2/3 的子链)、use_lin_kernighan(Lin-Kernighan 算子)、use_tsp_opt(滑动 TSP,用精确动态规划求解路径子链 TSP); - 非活动节点(inactive nodes):
use_make_active、use_make_inactive、use_swap_active、use_swap_active_chain等; - 大邻域搜索(LNS):
use_path_lns(松弛两条各 3 条弧的子链,定义 n² 个邻域)、use_full_path_lns(松弛整条路径与所有非活动节点)、use_tsp_lns、use_inactive_lns,以及基于插入启发式的use_global_cheapest_insertion_path_lns、use_local_cheapest_insertion_close_nodes_lns等;
- 跨路径(inter-route):
- 元启发式(metaheuristic):
local_search_metaheuristic、local_search_metaheuristics(可配置多个并轮换)、guided_local_search_lambda_coefficient等; - 搜索控制:
use_depth_first_search(深度优先而非局部搜索)、use_cp、use_cp_sat(自 2019 年起仅支持 TSP 模型)、use_generalized_cp_sat、sat_parameters、fallback_to_cp_sat_size_threshold; - 搜索限制:
solution_limit、time_limit(google.protobuf.Duration)、lns_time_limit、secondary_ls_time_limit_ratio、improvement_limit_parameters; - 传播控制:
use_full_propagation(完整传播更慢更耗内存,仅深度优先搜索等场景需要); - 日志:
log_search(为每个解打印目标值、分支数、失败数、深度、邻居数等)、log_cost_scaling_factor、log_cost_offset、log_tag(并行求解时区分日志); - ILS:
use_iterated_local_search与iterated_local_search_parameters(迭代局部搜索)。
此外同文件还定义了 RoutingModelParameters(创建 RoutingModel 时使用),包含底层 solver_parameters、reduce_vehicle_cost_model(所有车辆成本结构相同时约简底层模型,可显著加速)、max_callback_cache_size(回调缓存上限)。
枚举定义:routing_enums.proto
routing_enums.proto 定义了四个与参数配套的枚举消息:
FirstSolutionStrategy.Value(首解策略),是局部搜索的起始点:
| 枚举值 | 说明 |
|---|---|
UNSET / AUTOMATIC |
未设置 / 由求解器按模型自动检测 |
PATH_CHEAPEST_ARC |
从路径起点出发,反复连接产生最廉价路段的下一个节点 |
PATH_MOST_CONSTRAINED_ARC |
同上,但用基于比较的选择器优先约束最强的弧 |
EVALUATOR_STRATEGY |
用 SetFirstSolutionEvaluator 传入的函数评估弧成本 |
SAVINGS / PARALLEL_SAVINGS |
Clarke & Wright 节约算法(串行 / 并行版本,可并行构建多条路径) |
SWEEP |
Wren & Holliday 扫描算法 |
CHRISTOFIDES |
Christofides 算法变体(用最大匹配,不保证 3/2 近似因子) |
ALL_UNPERFORMED |
所有节点不执行(仅当节点为可选时能找到解) |
BEST_INSERTION |
按全局成本函数迭代插入最廉价节点(仅适用于带罚成本的可选节点模型) |
PARALLEL_CHEAPEST_INSERTION |
按弧成本迭代插入,比 BEST_INSERTION 快 |
SEQUENTIAL_CHEAPEST_INSERTION |
逐条构建路径,比 PARALLEL 版本更快 |
LOCAL_CHEAPEST_INSERTION |
最远节点优先插入,比 SEQUENTIAL 更快 |
LOCAL_CHEAPEST_COST_INSERTION |
同上但基于模型成本函数而非弧成本 |
GLOBAL_CHEAPEST_ARC / LOCAL_CHEAPEST_ARC / FIRST_UNBOUND_MIN_VALUE |
基于变量的启发式(等价于 CHOOSE_FIRST_UNBOUND + ASSIGN_MIN_VALUE) |
LocalSearchMetaheuristic.Value(元启发式),用于引导搜索跳出局部最优:
UNSET/AUTOMATIC:未设置 / 求解器自选;GREEDY_DESCENT:接受改进邻居直至局部最优;GUIDED_LOCAL_SEARCH:引导式局部搜索,通常对车辆路径最有效(proto 官方注释);SIMULATED_ANNEALING:模拟退火;TABU_SEARCH:禁忌搜索;GENERIC_TABU_SEARCH:在变量列表上做禁忌搜索(需通过SetTabuVarsCallback提供变量列表)。
RoutingSearchStatus.Value(搜索状态),RoutingModel::Solve() 后通过该枚举报告结果:
| 枚举值 | 含义 |
|---|---|
ROUTING_NOT_SOLVED |
尚未求解 |
ROUTING_SUCCESS |
求解成功 |
ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED |
求解成功但未达局部最优,留更多时间可改进 |
ROUTING_FAIL |
未找到解 |
ROUTING_FAIL_TIMEOUT |
超时且未找到解 |
ROUTING_INVALID |
模型 / 参数 / flag 无效 |
ROUTING_INFEASIBLE |
问题被证明不可行 |
ROUTING_OPTIMAL |
已求解到最优 |
索引管理:routing_index_manager.h
RoutingIndexManager 负责在**路由变量索引(Index)与用户节点编号(Node)**之间转换:RoutingIndexManager(num_nodes, num_vehicles, depot) 构造时自动为每辆车分配 start 与 end 虚拟节点,IndexToNode() / NodeToIndex() 完成双向映射。在下面的实战示例中可以看到它的核心用法。
Routing 求解器实战:四语言完整示例
ROUTING.md 给出了一个最小 TSP 示例:5 个地点、1 辆车、depot 为节点 0,弧成本取两点编号之差的绝对值,首解策略用 PATH_CHEAPEST_ARC。以下为完整代码。
C++
#include <cmath>
#include <cstdint>
#include <cstdlib>
#include <sstream>
#include "ortools/constraint_solver/routing.h"
#include "ortools/constraint_solver/routing_enums.pb.h"
#include "ortools/constraint_solver/routing_index_manager.h"
#include "ortools/constraint_solver/routing_parameters.h"
namespace operations_research {
void SimpleRoutingProgram() {
// 实例化数据问题。
int num_location = 5;
int num_vehicles = 1;
RoutingIndexManager::NodeIndex depot{0};
// 创建 Routing Index Manager。
RoutingIndexManager manager(num_location, num_vehicles, depot);
// 创建 Routing Model。
RoutingModel routing(manager);
// 定义每条弧的成本。
int distance_call_index = routing.RegisterTransitCallback(
&manager -> int64_t {
// 从路由变量 Index 转换到用户 NodeIndex。
auto from_node = manager.IndexToNode(from_index).value();
auto to_node = manager.IndexToNode(to_index).value();
return std::abs(to_node - from_node);
});
routing.SetArcCostEvaluatorOfAllVehicles(distance_call_index);
// 设置首解启发式。
RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters();
searchParameters.set_first_solution_strategy(
FirstSolutionStrategy::PATH_CHEAPEST_ARC);
// 求解问题。
const Assignment* solution = routing.SolveWithParameters(searchParameters);
// 在控制台打印解。
LOG(INFO) << "Objective: " << solution->ObjectiveValue();
// 检查解。
int64_t index = routing.Start(0);
LOG(INFO) << "Route for Vehicle 0:";
int64_t route_distance = 0;
std::ostringstream route;
while (!routing.IsEnd(index)) {
route << manager.IndexToNode(index).value() << " -> ";
const int64_t previous_index = index;
index = solution->Value(routing.NextVar(index));
route_distance +=
routing.GetArcCostForVehicle(previous_index, index, int64_t{0});
}
LOG(INFO) << route.str() << manager.IndexToNode(index).value();
LOG(INFO) << "Distance of the route: " << route_distance << "m";
}
} // namespace operations_research
int main(int /*argc*/, char* /*argv*/[]) {
operations_research::SimpleRoutingProgram();
return EXIT_SUCCESS;
}
关键调用链:RegisterTransitCallback 注册成本回调 → SetArcCostEvaluatorOfAllVehicles 绑定为全局弧成本 → DefaultRoutingSearchParameters() 取默认参数并覆盖首解策略 → SolveWithParameters 求解 → 用 routing.Start(0) + routing.NextVar(index) 沿解中的后继变量回溯整条路径。
Python
#!/usr/bin/env python3
"""Vehicle Routing example."""
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def main():
"""Entry point of the program."""
# 实例化数据问题。
num_locations = 5
num_vehicles = 1
depot = 0
# 创建 routing index manager。
manager = pywrapcp.RoutingIndexManager(num_locations, num_vehicles, depot)
# 创建 Routing Model。
routing = pywrapcp.RoutingModel(manager)
# 创建并注册 transit 回调。
def distance_callback(from_index, to_index):
"""Returns the absolute difference between the two nodes."""
# 从路由变量 Index 转换到用户 NodeIndex。
from_node = int(manager.IndexToNode(from_index))
to_node = int(manager.IndexToNode(to_index))
return abs(to_node - from_node)
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
# 定义每条弧的成本。
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# 设置首解启发式。
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
) # pylint: disable=no-member
# 求解问题。
assignment = routing.SolveWithParameters(search_parameters)
# 在控制台打印解。
print(f"Objective: {assignment.ObjectiveValue()}")
index = routing.Start(0)
plan_output = "Route for vehicle 0:\n"
route_distance = 0
while not routing.IsEnd(index):
plan_output += f"{manager.IndexToNode(index)} -> "
previous_index = index
index = assignment.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
plan_output += f"{manager.IndexToNode(index)}\n"
plan_output += f"Distance of the route: {route_distance}m\n"
print(plan_output)
if __name__ == "__main__":
main()
Java
package com.google.ortools.constraintsolver.samples;
import static java.lang.Math.abs;
import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.Assignment;
import com.google.ortools.constraintsolver.FirstSolutionStrategy;
import com.google.ortools.constraintsolver.RoutingIndexManager;
import com.google.ortools.constraintsolver.RoutingModel;
import com.google.ortools.constraintsolver.RoutingSearchParameters;
import com.google.ortools.constraintsolver.main;
import java.util.logging.Logger;
/** Minimal Routing example to showcase calling the solver.*/
public class SimpleRoutingProgram {
private static final Logger logger = Logger.getLogger(SimpleRoutingProgram.class.getName());
public static void main(String[] args) throws Exception {
Loader.loadNativeLibraries();
// 实例化数据问题。
final int numLocation = 5;
final int numVehicles = 1;
final int depot = 0;
// 创建 Routing Index Manager。
RoutingIndexManager manager = new RoutingIndexManager(numLocation, numVehicles, depot);
// 创建 Routing Model。
RoutingModel routing = new RoutingModel(manager);
// 创建并注册 transit 回调。
final int transitCallbackIndex =
routing.registerTransitCallback((long fromIndex, long toIndex) -> {
// 从路由变量 Index 转换到用户 NodeIndex。
int fromNode = manager.indexToNode(fromIndex);
int toNode = manager.indexToNode(toIndex);
return abs(toNode - fromNode);
});
// 定义每条弧的成本。
routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
// 设置首解启发式。
RoutingSearchParameters searchParameters =
main.defaultRoutingSearchParameters()
.toBuilder()
.setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
.build();
// 求解问题。
Assignment solution = routing.solveWithParameters(searchParameters);
// 在控制台打印解。
logger.info("Objective: " + solution.objectiveValue());
// 检查解。
long index = routing.start(0);
logger.info("Route for Vehicle 0:");
long routeDistance = 0;
String route = "";
while (!routing.isEnd(index)) {
route += manager.indexToNode(index) + " -> ";
long previousIndex = index;
index = solution.value(routing.nextVar(index));
routeDistance += routing.getArcCostForVehicle(previousIndex, index, 0);
}
route += manager.indexToNode(index);
logger.info(route);
logger.info("Distance of the route: " + routeDistance + "m");
}
}
.NET
using System;
using Google.OrTools.ConstraintSolver;
/// <summary>
/// This is a sample using the routing library .Net wrapper.
/// </summary>
public class SimpleRoutingProgram
{
public static void Main(String[] args)
{
// 实例化数据问题。
const int numLocation = 5;
const int numVehicles = 1;
const int depot = 0;
// 创建 Routing Index Manager。
RoutingIndexManager manager = new RoutingIndexManager(numLocation, numVehicles, depot);
// 创建 Routing Model。
RoutingModel routing = new RoutingModel(manager);
// 创建并注册 transit 回调。
int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) =>
{
// 从路由变量 Index 转换到距离矩阵 NodeIndex。
var fromNode = manager.IndexToNode(fromIndex);
var toNode = manager.IndexToNode(toIndex);
return Math.Abs(toNode - fromNode);
});
// 定义每条弧的成本。
routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
// 设置首解启发式。
RoutingSearchParameters searchParameters =
operations_research_constraint_solver.DefaultRoutingSearchParameters();
searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc;
// 求解问题。
Assignment solution = routing.SolveWithParameters(searchParameters);
// 在控制台打印解。
Console.WriteLine("Objective: {0}", solution.ObjectiveValue());
// 检查解。
long index = routing.Start(0);
Console.WriteLine("Route for Vehicle 0:");
long route_distance = 0;
while (routing.IsEnd(index) == false)
{
Console.Write("{0} -> ", manager.IndexToNode((int)index));
long previousIndex = index;
index = solution.Value(routing.NextVar(index));
route_distance += routing.GetArcCostForVehicle(previousIndex, index, 0);
}
Console.WriteLine("{0}", manager.IndexToNode(index));
Console.WriteLine("Distance of the route: {0}m", route_distance);
}
}
Routing 与 CP 的关系在代码中清晰可见:Assignment 同时是两个求解器的解载体;而 routing 的 next(i) 变量本质上是 CP 的 IntVar,因此可以用 constraint_solver.h 中任意约束(如 MakeAllDifferent、析取约束)对路由模型进行增强。
Recipes:TSP / VRP / PDP 建模配方
模块文档目录 ortools/constraint_solver/docs 提供按类型分组的建模配方(Recipes),与上述基础示例配套:
这些配方覆盖了 Routing 求解器最常用的三种问题族,配合 routing_parameters.proto 中的维度机制(cumul/transit 变量用于建模载重与时间窗)即可扩展到 CVRP、VRPTW、PDPTW 等工业级模型。仓库 examples 目录还提供大量可直接运行的完整示例(CP 与 Routing 均有 C++/Python/Java/.NET 版本),适合作为上手模板。
小结
ortools/constraint_solver 模块以一套统一的搜索内核同时支撑两类求解器:CP 求解器通过 Solver/IntVar/Constraint/DecisionBuilder 四类核心对象完成约束建模,其全部行为由 solver_parameters.proto 与 search_limit.proto 控制,解由 assignment.proto 表示;Routing 求解器则在 CP 之上以 RoutingModel + RoutingIndexManager 提供 TSP/VRP/PDP 建模能力,通过 routing_parameters.proto(首解策略、30+ 邻域算子、元启发式、搜索限制)与 routing_enums.proto 完成精细调参。无论你从 CP.md 还是 ROUTING.md 入手,上述四语言示例都足以支撑你跑通第一个模型;而结合本文梳理的 proto 参数表,你就能进一步针对大规模实例调整搜索策略,获得更优的求解质量。