OR-Tools 约束求解器与车辆路径求解器全指南:CP Solver 与 Routing Solver 建模实战
OR-Tools 约束求解器与车辆路径求解器全指南:CP Solver 与 Routing Solver 建模实战
本篇技术指南以 OR-Tools 官方文档入口(ortools/constraint_solver/docs/)为核心,系统讲解约束编程(Constraint Programming)求解器与车辆路径(Vehicle Routing)求解器的定义、使用场景与建模方法。文中完整覆盖 CP 求解器与 Routing 求解器的四语言(C++/Python/Java/.Net)入门示例、TSP/VRP/PDP 三类建模食谱,并结合仓库源码(routing_enums.proto、routing.h、示例程序等)深入剖析其核心 API 与求解原理。读者读完可独立编写并运行第一个约束规划程序与车辆路径规划程序,并掌握向带容量、时间窗、取送货等真实约束扩展的建模路径。
概览:两大求解组件
OR-Tools 的 ortools/constraint_solver 目录集中了两大相互关联的求解组件,其入口文档见 README:
CP Solver:通用约束求解器
约束编程(Constraint Programming,CP) 是从一个极大的候选集合中识别可行解的方法,其核心特点是问题可以用"任意约束"(arbitrary constraints)来建模——变量、值域、以及变量之间必须满足的关系。CP 求解器通过"变量赋值 + 约束传播 + 搜索"的机制求解,详细使用说明见 CP.md。
需要特别强调的是,OR-Tools 官方文档强烈建议使用 CP-SAT 求解器 而非原始的 CP 求解器:CP-SAT 基于布尔可满足性问题(SAT)技术,性能更强、功能更完善,是 Google 推荐用于约束优化问题的主力求解器;原始的 CP 求解器仍被保留用于兼容旧代码,且是 Routing 求解器的底层基础。
Routing Solver:车辆路径求解器
车辆路径求解器(Vehicle Routing solver) 是一个在给定约束下寻找最优车辆路径的专用库,例如 TSP(旅行商问题)、VRP(车辆路径问题)、PDP(取送货问题)。该库构建于 CP Solver 库之上,通过把路径问题编码为约束满足问题来求解。其核心用法与建模食谱见 ROUTING.md。
文档与示例结构:四种语言的建模食谱
constraint_solver/docs 下的文档结构如下:
| 文档 | 主题 |
|---|---|
| CP.md | 原始 CP 求解器的基本用法与四语言示例 |
| ROUTING.md | Routing 求解器的基本用法与四语言示例 |
| TSP.md | 旅行商问题建模食谱(坐标位置 / 距离矩阵两种建模) |
| VRP.md | 车辆路径问题建模食谱(容量、时间窗、多起点终点等) |
| PDP.md | 取送货问题建模食谱(ANY/FIFO/LIFO 三种装卸策略) |
OR-Tools 为每个问题都提供了 C++、Python、Java、.Net 四种语言的示例代码,它们位于 ortools/constraint_solver/samples 目录,统一由 BUILD.bazel 与 CMakeLists.txt 组织构建。每种语言的运行环境与代码要求略有差异,例如 Java 需要先调用 Loader.loadNativeLibraries() 加载原生库,.Net 需要引用 Google.OrTools.ConstraintSolver 命名空间。
文档中配图(如各 TSP/VRP 变体的数据与求解示意图)由脚本 routing_svg.py 生成,并通过 bash 脚本 generate_svg.sh 批量执行。
使用 CP 求解器
CP 求解器的使用遵循一个固定的五步流程:实例化求解器 → 创建变量 → 添加约束 → 定义搜索决策(Phase/DecisionBuilder)→ 遍历解。
以最经典的"三变量 x、y、z 取值 0~2,且 x ≠ y"问题为例,以下是四种语言的完整实现(源自 CP.md)。
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() {
// Instantiate the solver.
Solver solver("CpSimple");
// Create the variables.
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");
// Constraint 0: x != y..
solver.AddConstraint(solver.MakeAllDifferent({x, y}));
LOG(INFO) << "Number of constraints: "
<< std::to_string(solver.constraints());
// Solve the problem.
DecisionBuilder* const db = solver.MakePhase(
{x, y, z}, Solver::CHOOSE_FIRST_UNBOUND, Solver::ASSIGN_MIN_VALUE);
// Print solution on console.
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;
}
Python 示例
#!/usr/bin/env python3
"""Simple Constraint optimization example."""
from ortools.constraint_solver import pywrapcp
def main():
"""Entry point of the program."""
# Instantiate the solver.
solver = pywrapcp.Solver("CPSimple")
# Create the variables.
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")
# Constraint 0: x != y.
solver.Add(x != y)
print("Number of constraints: ", solver.Constraints())
# Solve the problem.
decision_builder = solver.Phase(
[x, y, z], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE
)
# Print solution on console.
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()
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();
// Instantiate the solver.
Solver solver = new Solver("CpSimple");
// Create the variables.
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");
// Constraint 0: x != y..
solver.addConstraint(solver.makeAllDifferent(new IntVar[] {x, y}));
logger.info("Number of constraints: " + solver.constraints());
// Solve the problem.
final DecisionBuilder db = solver.makePhase(
new IntVar[] {x, y, z}, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);
// Print solution on console.
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()));
}
}
.Net 示例
using System;
using Google.OrTools.ConstraintSolver;
/// <summary>
/// This is a simple CP program.
/// </summary>
public class SimpleCpProgram
{
public static void Main(String[] args)
{
// Instantiate the solver.
Solver solver = new Solver("CpSimple");
// Create the variables.
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");
// Constraint 0: x != y..
solver.Add(solver.MakeAllDifferent(new IntVar[] { x, y }));
Console.WriteLine($"Number of constraints: {solver.Constraints()}");
// Solve the problem.
DecisionBuilder db =
solver.MakePhase(new IntVar[] { x, y, z }, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);
// Print solution on console.
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");
}
}
关键 API 与求解流程解析
Solver(Python 中为pywrapcp.Solver):所有变量、约束与搜索的容器。MakeIntVar(lb, ub, name)创建一个值域为[lb, ub]的整数变量。MakeAllDifferent({x, y})/solver.Add(x != y):添加约束。本例中x != y使问题产生多个解(共 16 个),因此示例采用NewSearch+NextSolution循环遍历全部解而非只求一个解。MakePhase(vars, CHOOSE_FIRST_UNBOUND, ASSIGN_MIN_VALUE):构造决策构建器(DecisionBuilder),决定变量选择顺序(CHOOSE_FIRST_UNBOUND取第一个未赋值的变量)与取值顺序(ASSIGN_MIN_VALUE优先赋最小值)。- 统计信息:
solver.wall_time()返回求解耗时(毫秒),Solver::MemoryUsage()返回内存占用(字节),solver.solutions()返回找到的解数量,可用于评估求解规模。
C++ 的 Solver 类定义在 constraint_solver.h,Python 绑定由 pywrapcp 提供(SWIG 封装)。同目录下还有更多 CP 示例,如 nqueens_cp.py、nurses_cp.cc、minimal_jobshop_cp.cc、rabbits_and_pheasants_cp.cc、cp_is_fun_cp.py,均可作为进一步学习的起点。
使用 Routing 求解器
Routing 求解器的基本使用同样遵循固定流程:定义数据 → 创建 RoutingIndexManager → 创建 RoutingModel → 注册 transit callback(代价回调)→ 设置搜索参数 → 求解并解析路径。以"5 个地点、1 辆车、0 号点为车场、弧代价为两点编号之差的绝对值"为例,以下是四种语言的完整实现(源自 ROUTING.md)。
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() {
// Instantiate the data problem.
int num_location = 5;
int num_vehicles = 1;
RoutingIndexManager::NodeIndex depot{0};
// Create Routing Index Manager
RoutingIndexManager manager(num_location, num_vehicles, depot);
// Create Routing Model.
RoutingModel routing(manager);
// Define cost of each arc.
int distance_call_index = routing.RegisterTransitCallback(
&manager -> int64_t {
// Convert from routing variable Index to user 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);
// Setting first solution heuristic.
RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters();
searchParameters.set_first_solution_strategy(
FirstSolutionStrategy::PATH_CHEAPEST_ARC);
// Solve the problem.
const Assignment* solution = routing.SolveWithParameters(searchParameters);
// Print solution on console.
LOG(INFO) << "Objective: " << solution->ObjectiveValue();
// Inspect solution.
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;
}
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."""
# Instantiate the data problem.
num_locations = 5
num_vehicles = 1
depot = 0
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(num_locations, num_vehicles, depot)
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
def distance_callback(from_index, to_index):
"""Returns the absolute difference between the two nodes."""
# Convert from routing variable Index to user 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)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
) # pylint: disable=no-member
# Solve the problem.
assignment = routing.SolveWithParameters(search_parameters)
# Print solution on console.
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();
// Instantiate the data problem.
final int numLocation = 5;
final int numVehicles = 1;
final int depot = 0;
// Create Routing Index Manager
RoutingIndexManager manager = new RoutingIndexManager(numLocation, numVehicles, depot);
// Create Routing Model.
RoutingModel routing = new RoutingModel(manager);
// Create and register a transit callback.
final int transitCallbackIndex =
routing.registerTransitCallback((long fromIndex, long toIndex) -> {
// Convert from routing variable Index to user NodeIndex.
int fromNode = manager.indexToNode(fromIndex);
int toNode = manager.indexToNode(toIndex);
return abs(toNode - fromNode);
});
// Define cost of each arc.
routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
// Setting first solution heuristic.
RoutingSearchParameters searchParameters =
main.defaultRoutingSearchParameters()
.toBuilder()
.setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
.build();
// Solve the problem.
Assignment solution = routing.solveWithParameters(searchParameters);
// Print solution on console.
logger.info("Objective: " + solution.objectiveValue());
// Inspect solution.
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)
{
// Instantiate the data problem.
const int numLocation = 5;
const int numVehicles = 1;
const int depot = 0;
// Create Routing Index Manager
RoutingIndexManager manager = new RoutingIndexManager(numLocation, numVehicles, depot);
// Create Routing Model.
RoutingModel routing = new RoutingModel(manager);
// Create and register a transit callback.
int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) =>
{
// Convert from routing variable Index to
// distance matrix NodeIndex.
var fromNode = manager.IndexToNode(fromIndex);
var toNode = manager.IndexToNode(toIndex);
return Math.Abs(toNode - fromNode);
});
// Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
// Setting first solution heuristic.
RoutingSearchParameters searchParameters =
operations_research_constraint_solver.DefaultRoutingSearchParameters();
searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc;
// Solve the problem.
Assignment solution = routing.SolveWithParameters(searchParameters);
// Print solution on console.
Console.WriteLine("Objective: {0}", solution.ObjectiveValue());
// Inspect solution.
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);
}
}
核心概念与源码级原理解析
1. RoutingIndexManager:内部索引与用户节点的桥梁
Routing 求解器内部使用整数"索引"(Index)表示节点,而用户通常有自己的一套节点编号(NodeIndex)。RoutingIndexManager(num_locations, num_vehicles, depot) 负责两者之间的映射,并通过 manager.IndexToNode(index) 将内部索引转回用户节点。其声明见 routing_index_manager.h。
2. TransitCallback:弧代价回调
RegisterTransitCallback(callback) 注册一个"从节点 i 到节点 j 的代价"回调(如距离、时间、油耗),返回一个回调索引;SetArcCostEvaluatorOfAllVehicles(index) 让所有车辆统一使用该代价作为目标函数。真实场景中回调通常查一张距离矩阵,参见 tsp_distance_matrix.py 与 tsp_distance_matrix.cc。
3. FirstSolutionStrategy:首解启发式
求解器需要先用启发式算法构造一个初始可行解,再通过局部搜索改进。DefaultRoutingSearchParameters()(定义于 routing_parameters.h)返回默认参数,示例中将 first_solution_strategy 设为 PATH_CHEAPEST_ARC。该枚举完整定义于 routing_enums.proto,主要包括:
| 策略 | 枚举值 | 语义(源自 proto 注释) |
|---|---|---|
AUTOMATIC |
15 | 由求解器根据模型自动选择 |
PATH_CHEAPEST_ARC |
3 | 从路径起点出发,不断连接"最便宜"的弧来逐段扩展路径(路径添加类) |
PATH_MOST_CONSTRAINED_ARC |
4 | 同 PATH_CHEAPEST_ARC,但用比较选择器优先选择约束最多的弧 |
EVALUATOR_STRATEGY |
5 | 使用 SetFirstSolutionEvaluator() 传入的函数评估弧代价 |
SAVINGS |
10 | Clarke & Wright 节约算法(串行版) |
PARALLEL_SAVINGS |
17 | 节约算法的并行版,可同时构建多条路线 |
SWEEP |
11 | Wren & Holliday 扫描算法 |
CHRISTOFIDES |
13 | Christofides 算法变体(适用于度量 TSP) |
BEST_INSERTION |
7 | 迭代把最便宜节点插入最便宜位置(基于全局代价函数) |
PARALLEL_CHEAPEST_INSERTION |
8 | 基于弧代价的最便宜插入(并行版,比 BEST_INSERTION 快) |
SEQUENTIAL_CHEAPEST_INSERTION |
14 | 逐条路线构建的串行最便宜插入 |
LOCAL_CHEAPEST_INSERTION |
9 | 按距起点/终点距离降序逐个插入节点(最远优先) |
GLOBAL_CHEAPEST_ARC |
1 | 每次连接"全局最便宜"的两个节点 |
LOCAL_CHEAPEST_ARC |
2 | 选第一个未绑定后继的节点连接最便宜节点 |
FIRST_UNBOUND_MIN_VALUE |
12 | 等价于 CP 的 CHOOSE_FIRST_UNBOUND + ASSIGN_MIN_VALUE |
选择不同策略会显著影响初始解质量与求解速度:路径添加类适合小规模问题,插入类适合带可选节点/罚金的模型,大规模 VRP 常配合 LocalSearchMetaheuristic(同样定义于 routing_enums.proto)做元启发式改进。
4. 求解与路径解析
SolveWithParameters(searchParameters) 返回 Assignment(一个解),其中记录了每个变量的取值。解析路径时从 routing.Start(0)(车辆 0 的起点)出发,用 assignment.Value(routing.NextVar(index)) 顺着"下一节点"链一直走到 routing.IsEnd(index) 为真,并用 GetArcCostForVehicle(prev, next, 0) 累加路径总代价。assignment.ObjectiveValue() 返回目标函数值。
Routing 建模食谱:TSP / VRP / PDP
ROUTING.md 将路径建模问题按类型整理为三类食谱文档,每个变体都配有问题示意图、求解示意图和四语言示例代码。
TSP:旅行商问题(TSP.md)
车辆路径求解器可以直接用于求解旅行商问题,官方给出两种建模方式:
使用坐标位置(Locations):直接给定各城市坐标,问题与解如下:
对应示例:tsp.cc、tsp.py、Tsp.java、Tsp.cs。
使用距离矩阵(Distance Matrix):直接以距离矩阵驱动求解,避免坐标与距离换算:
对应示例:tsp_distance_matrix.cc、tsp_distance_matrix.py、TspDistanceMatrix.java、TspDistanceMatrix.cs。
VRP:车辆路径问题(VRP.md)
车辆路径求解器可求解各种 VRP 变体,文档按约束类型整理了七个建模食谱:
1. 基本 VRP(多辆车)
示例:vrp.cc、vrp.py、Vrp.java、Vrp.cs。
2. 全局跨度约束(Global Span):限制整条路线的最大长度(所有车辆中最长路线的上界),用于平衡各车工作量:
示例:vrp_global_span.cc、vrp_global_span.py、VrpGlobalSpan.java、VrpGlobalSpan.cs。配图见 vrp_global_span.svg 与 vrp_global_span_solution.svg。
3. 容量约束(Capacity):每个节点有需求(demand),每辆车有容量上限,通过 AddDimensionWithVehicleCapacity 建模,是带容量约束的 CVRP:
示例:vrp_capacity.cc、vrp_capacity.py、VrpCapacity.java、VrpCapacity.cs。
4. 可跳过的节点(Drop Nodes):通过 Disjunction(析取约束)给节点设置惩罚代价,允许某些节点被"放弃"(不访问),适用于无法访问所有节点或节点数超过车辆承载能力的场景:
示例:vrp_drop_nodes.cc、vrp_drop_nodes.py、VrpDropNodes.java、VrpDropNodes.cs。配图见 vrp_drop_nodes.svg 与 vrp_drop_nodes_solution.svg。
5. 多起点/终点(Multiple Starts/Ends):各车辆的起点与终点可以不统一(如车场分布在多处),通过给 RoutingIndexManager 传起点/终点数组实现:
示例:vrp_starts_ends.cc、vrp_starts_ends.py、VrpStartsEnds.java、VrpStartsEnds.cs。配图见 vrp_starts_ends.svg 与 vrp_starts_ends_solution.svg。
6. 时间窗约束(Time Windows):每个节点规定最早/最晚到达时间,通过 AddDimension 建立时间维度,是带时间窗的 VRPTW:
示例:vrp_time_windows.cc、vrp_time_windows.py、VrpTimeWindows.java、VrpTimeWindows.cs。
7. 资源约束(Resources):建立多个维度(如同时约束行驶里程与装载量)模拟多种资源共同受限的模型:
示例:vrp_resources.cc、vrp_resources.py、VrpResources.java、VrpResources.cs。配图见 vrp_resources.svg 与 vrp_resources_solution.svg。
PDP:取送货问题(PDP.md)
取送货问题要求同一辆车完成"取货点 → 送货点"配对访问,且取货必须早于送货。官方提供三种装卸策略:
1. 默认策略(ANY):取货与送货间的顺序无额外限制,只保证取货先于送货:
示例:vrp_pickup_delivery.cc、vrp_pickup_delivery.py、VrpPickupDelivery.java、VrpPickupDelivery.cs。
2. FIFO 策略:严格先进先出——先取货的货物必须先送达,适合"先入先出"的仓储/配送规则:
示例:vrp_pickup_delivery_fifo.cc、vrp_pickup_delivery_fifo.py、VrpPickupDeliveryFifo.java、VrpPickupDeliveryFifo.cs。
3. LIFO 策略:严格后进先出——最后取货的货物最先送达,模拟"堆叠装卸"的运输场景:
示例:vrp_pickup_delivery_lifo.cc、vrp_pickup_delivery_lifo.py、VrpPickupDeliveryLifo.java、VrpPickupDeliveryLifo.cs。
更多示例与进阶阅读
- 路径求解器的核心头文件:routing.h(RoutingModel 全部建模 API)、routing_index_manager.h、routing_parameters.h、routing_enums.proto(首解策略与局部搜索元启发式枚举)。
- 更多四语言完整示例集中在 samples 目录,例如带时间限制的 vrp_with_time_limit.py、带休息时段的 vrp_breaks.py、带初始路线的 vrp_initial_routes.py、以及求解过程回调 vrp_solution_callback.py。
- 若追求更强的求解性能与更丰富的约束表达能力,官方文档明确建议在约束规划类问题中使用 CP-SAT 求解器(位于 ortools/sat 目录)。
小结
本文以 OR-Tools constraint_solver 文档体系为主线,完整覆盖了两大组件的定义、四语言入门示例与全部建模食谱:CP 求解器遵循"变量—约束—搜索"三步范式;Routing 求解器在其之上以"索引管理 + 代价回调 + 首解启发式"的方式建模路径问题,并可扩展出 TSP、容量约束 VRP、时间窗 VRP、取送货 PDP 等一整套工业级变体。掌握了这些基础与源码级原理之后,无论是编写第一个 CP 程序,还是搭建真实的车辆调度系统,都已具备可直接落地的建模能力。