Google OR-Tools 完整学习资料

一、OR-Tools 概述1.1 什么是 OR-ToolsOR-ToolsGoogle Optimization Tools是 Google 开发的开源组合优化工具套件专为解决复杂的运筹优化问题而设计。它采用 C 作为核心引擎保证计算性能同时提供 Python、Java、C# 等多语言绑定是工业界应用最广泛的开源优化库之一。1.2 核心技术优势多求解器集成架构内置 GLOP、CP-SAT、SCIP 等求解器支持接入 Gurobi、CPLEX 等商业求解器可根据问题特性灵活选择高性能计算核心算法采用 C 实现CP-SAT 求解器在组合优化问题上比传统 CP 求解器快 2-5 倍工程化封装针对 VRP、调度、分配等典型场景提供高层封装无需深入算法细节即可快速落地跨平台多语言支持 Windows/Linux/macOS提供 Python/C/Java/C# 统一 API1.3 典型应用场景领域典型问题推荐模块物流配送车辆路径规划、TSP、最后一公里配送Routing Solver生产制造车间调度、设备排班、工艺排序CP-SAT资源分配人员排班、任务分配、产能规划线性/整数规划网络优化最短路径、最大流、最小费用流图算法模块仓储物流装箱问题、背包问题、货位优化约束规划二、环境安装与配置2.1 Python 环境安装推荐Python 是 OR-Tools 最常用的开发语言安装极为简便# 升级 pippipinstall--upgradepip# 安装 OR-Toolspipinstallortools系统要求Python 3.8支持 Windows 10、macOS 10.14、Ubuntu 18.042.2 验证安装fromortools.linear_solverimportpywraplp# 创建求解器实例solverpywraplp.Solver.CreateSolver(GLOP)print(fOR-Tools 版本:{solver.SolverVersion()})print(安装成功)2.3 其他安装方式源码编译适合需要定制化修改的场景支持 CMake、Bazel、Make 三种构建方式C/Java/C#可通过官方包管理器或源码编译获取对应语言的 SDK三、核心模块详解3.1 线性规划模块Linear Solver核心概念线性规划用于在一组线性约束条件下求解线性目标函数的最优值。OR-Tools 内置两个线性规划求解器求解器算法原理适用场景GLOP单纯形法中等规模精确求解Google 自研PDLP一阶梯度法超大规模稀疏问题内存占用低标准建模流程fromortools.linear_solverimportpywraplp# 1. 创建求解器solverpywraplp.Solver.CreateSolver(GLOP)# 2. 定义决策变量xsolver.NumVar(lower_bound,upper_bound,x_name)# 3. 添加约束条件constraintsolver.Constraint(lb,ub)constraint.SetCoefficient(x,coefficient)# 4. 设置目标函数objectivesolver.Objective()objective.SetCoefficient(x,coefficient)objective.SetMaximization()# 或 SetMinimization()# 5. 求解并输出结果statussolver.Solve()ifstatuspywraplp.Solver.OPTIMAL:print(最优值:,objective.Value())print(x ,x.solution_value())3.2 整数规划与混合整数规划当决策变量必须取整数时如人员数量、设备台数使用整数规划。OR-Tools 通过分支定界法求解支持的求解器包括SCIP开源高性能 MIP 求解器内置CBC另一种开源 MIP 求解器Gurobi/CPLEX商业求解器需额外授权# 创建整数规划求解器solverpywraplp.Solver.CreateSolver(SCIP)# 定义整数变量xsolver.IntVar(0,10,x)# 整数变量ysolver.BoolVar(y)# 0-1 布尔变量3.3 约束规划模块CP-SAT模块定位CP-SAT 是 OR-Tools 最强大的模块之一基于可满足性理论SAT与约束传播技术擅长处理离散组合优化问题是调度、排班、分配类问题的首选。核心优势支持丰富的全局约束AllDifferent、Cumulative 等内置高效搜索策略与剪枝机制支持中间解回调可随时获取当前最优解基础示例结构fromortools.sat.pythonimportcp_model# 1. 创建模型modelcp_model.CpModel()# 2. 定义整数变量xmodel.NewIntVar(0,10,x)ymodel.NewIntVar(0,10,y)# 3. 添加约束model.Add(xy10)model.AddAllDifferent([x,y])# 全局约束变量互不相同# 4. 设置目标model.Maximize(3*x5*y)# 5. 创建求解器并求解solvercp_model.CpSolver()statussolver.Solve(model)ifstatuscp_model.OPTIMAL:print(fx {solver.Value(x)}, y {solver.Value(y)})3.4 车辆路径规划模块Routing Solver问题类型Routing 模块是 OR-Tools 的明星功能支持几乎所有主流 VRP 变体TSP旅行商问题单车辆遍历所有点VRP基础车辆路径问题CVRP带容量约束的 VRPVRPTW带时间窗的 VRPVRPPD带取送货的 VRP核心组件RoutingIndexManager管理节点索引与车辆索引的映射RoutingModel路径规划主模型Dimension维度概念用于建模容量、时间等累积量标准开发流程fromortools.constraint_solverimportpywrapcpfromortools.constraint_solverimportrouting_enums_pb2# 1. 准备数据距离矩阵、车辆数、车场data{distance_matrix:[...],# n×n 距离矩阵num_vehicles:4,# 车辆数量depot:0# 车场节点索引}# 2. 创建索引管理器与路由模型managerpywrapcp.RoutingIndexManager(len(data[distance_matrix]),data[num_vehicles],data[depot])routingpywrapcp.RoutingModel(manager)# 3. 定义代价函数两点间距离defdistance_callback(from_index,to_index):from_nodemanager.IndexToNode(from_index)to_nodemanager.IndexToNode(to_index)returndata[distance_matrix][from_node][to_node]transit_callback_indexrouting.RegisterTransitCallback(distance_callback)routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)# 4. 设置搜索参数并求解search_parameterspywrapcp.DefaultRoutingSearchParameters()search_parameters.first_solution_strategy(routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)solutionrouting.SolveWithParameters(search_parameters)3.5 图算法模块提供经典图论算法的高效实现最短路径Dijkstra、Bellman-Ford最大流 / 最小费用最大流最小生成树assignment 分配问题匈牙利算法四、标准建模方法论4.1 优化问题五步法使用 OR-Tools 解决任何优化问题都遵循统一的五步流程问题抽象明确决策变量、约束条件、优化目标求解器选型根据问题特性选择 LP/MIP/CP/Routing模型构建定义变量、添加约束、设置目标函数参数调优配置求解策略、时间限制、搜索启发式结果解析验证可行性、提取方案、分析优化效果4.2 求解器选择指南问题特征推荐求解器说明连续变量 线性约束GLOP / PDLP纯线性规划问题部分变量为整数SCIP / CBC混合整数规划复杂逻辑约束 离散变量CP-SAT调度、排班、组合问题路径优化 / 车辆调度Routing SolverVRP 及其变体图结构网络问题graph 模块最短路径、最大流五、实战案例5.1 案例一生产计划线性规划问题工厂生产 A、B 两种产品每件利润分别为 5 元和 7 元。生产每件 A 需 2 单位原料B 需 3 单位原料总原料不超过 100 单位。A 产品产量不超过 30 件。求最大利润。fromortools.linear_solverimportpywraplp# 创建求解器solverpywraplp.Solver.CreateSolver(GLOP)# 定义变量A、B 产品产量xsolver.NumVar(0,solver.infinity(),产品A)ysolver.NumVar(0,solver.infinity(),产品B)# 约束1原料约束solver.Add(2*x3*y100)# 约束2A 产量上限solver.Add(x30)# 目标最大化利润solver.Maximize(5*x7*y)# 求解statussolver.Solve()ifstatuspywraplp.Solver.OPTIMAL:print(f最大利润:{solver.Objective().Value():.2f}元)print(f产品A产量:{x.solution_value():.2f}件)print(f产品B产量:{y.solution_value():.2f}件)5.2 案例二作业车间调度CP-SAT问题多个工件在多台机器上加工每个工件有固定的工序顺序每台机器同一时间只能加工一个工件求最短完工时间。fromortools.sat.pythonimportcp_modeldefjob_shop_scheduling():# 工序数据每个工件的[(机器, 加工时长), ...]jobs_data[[(0,3),(1,2),(2,2)],# 工件0[(0,2),(2,1),(1,4)],# 工件1[(1,4),(2,3)]# 工件2]machines_count3modelcp_model.CpModel()# 定义变量每个工序的开始时间all_tasks{}forjob_id,jobinenumerate(jobs_data):fortask_id,(machine,duration)inenumerate(job):start_varmodel.NewIntVar(0,1000,fstart_{job_id}_{task_id})end_varmodel.NewIntVar(0,1000,fend_{job_id}_{task_id})model.Add(end_varstart_varduration)all_tasks[job_id,task_id](start_var,end_var,machine)# 约束1同一工件的工序顺序约束forjob_id,jobinenumerate(jobs_data):fortask_idinrange(len(job)-1):model.Add(all_tasks[job_id,task_id1][0]all_tasks[job_id,task_id][1])# 约束2同一机器不能同时加工两个工序formachine_idinrange(machines_count):machine_tasks[]for(j,t),(s,e,m)inall_tasks.items():ifmmachine_id:machine_tasks.append((s,e))model.AddNoOverlap([sfors,einmachine_tasks],[e-sfors,einmachine_tasks])# 目标最小化总完工时间makespanmodel.NewIntVar(0,1000,makespan)model.AddMaxEquality(makespan,[efor_,(_,e,_)inall_tasks.items()])model.Minimize(makespan)# 求解solvercp_model.CpSolver()statussolver.Solve(model)ifstatuscp_model.OPTIMAL:print(f最短完工时间:{solver.Value(makespan)})5.3 案例三带时间窗的车辆路径VRPTWVRPTW 在基础 VRP 上增加了每个客户点的服务时间窗约束是物流配送最常见的场景。核心要点使用时间矩阵替代距离矩阵添加时间维度Time Dimension为每个节点设置时间窗上下界考虑服务时长六、进阶技巧与最佳实践6.1 性能优化技巧变量规模控制尽量减少变量数量合理设置变量上下界约束紧化尽可能收紧约束边界缩小搜索空间启发式策略Routing 问题选择合适的初始解策略PATH_CHEAPEST_ARC、SAVINGS 等时间限制大规模问题设置合理的求解时间上限避免无限等待多线程求解设置num_search_workers启用并行搜索6.2 常见问题与避坑指南整数精度问题CP-SAT 只支持整数浮点数需放大转换为整数回调函数性能频繁的回调会严重拖慢求解速度不可行模型调试使用solver.ResponseStats()查看约束冲突大规模 VRP节点数超过 100 时建议使用启发式 局部搜索策略6.3 调参经验CP-SAT设置num_workers并行搜索max_time_in_seconds控制时长Routing先用first_solution_strategy快速得到可行解再用local_search_metaheuristic优化MIP设置mip_gap容忍度在精度与速度间权衡七、学习路径与资源推荐7.1 学习路线建议入门阶段掌握线性规划基础熟悉 OR-Tools 基本 API进阶阶段深入学习 CP-SAT 约束编程掌握调度、分配类问题建模专项阶段主攻 Routing 模块精通各类 VRP 变体与参数调优实战阶段结合真实业务场景完成端到端优化方案落地7.2 官方资源官方文档https://developers.google.com/optimizationGitHub 仓库https://github.com/google/or-tools官方示例库examples 目录下包含数百个各语言示例7.3 延伸学习运筹学基础线性规划、整数规划、对偶理论组合优化图论、网络流、动态规划启发式算法遗传算法、模拟退火、禁忌搜索