OR-Tools 约束求解器(CP Solver)与车辆路径求解器(Routing Solver)模块完全指南

原创2026-09-21 23:16:182,180 阅读
文章标签:科学计算高性能计算

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 求解器的五个核心抽象:

  1. Solver:求解器实例,负责管理变量、约束与搜索;
  2. IntVar / IntExpr:整数变量与整数表达式(可由变量组合而来,如 MakeSum、MakeProd);
  3. Constraint:通过 MakeEquality 等构造器创建、再由 AddConstraint 加入求解器;
  4. DecisionBuilder:由 MakePhase 创建,封装了变量选择策略与值选择策略;
  5. 搜索生命周期: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 等;
  • 元启发式(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),与上述基础示例配套:

  • TSP.md:旅行商问题建模;
  • VRP.md:带容量、时间窗等约束的车辆路径问题建模;
  • PDP.md:取送问题(Pickup and Delivery Problem)建模。

这些配方覆盖了 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 参数表,你就能进一步针对大规模实例调整搜索策略,获得更优的求解质量。

登录后查看全文
or-tools