简介面向物流路径规划与运筹优化场景的取送货VRP问题这份Python实现方案覆盖从节点建模、路径更新到结果校验的完整闭环适合正在学习车辆路径问题的开发者、研究者及学生尤其适合需要快速上手带取送约束场景的初学者。压缩包共6个文件核心是3个Python脚本分别实现RouteNode节点定义、主求解逻辑与自动化测试另有3个txt文档提供依赖清单、运行说明及实验数据便于核对输入输出格式与参数配置。包体仅5KB轻量精简加载迅速。代码内嵌大量注解关键计算步骤均有注释可直接运行验证效果也能在了解逻辑后灵活修改求解策略或增加约束条件。目前已有1012人学习下载可作为课程设计、小型项目以及物流调度入门的重要参考资料也可作为进一步研究启发式算法与路径优化问题的起点。1. 取送货 VRP 不是把回程点塞进 VRP 那么简单同城配送里最容易被低估的一类问题是取送货Pickup-Delivery-VRP一张订单同时包含一个取货点和一个送货点两个点必须由同一辆车服务取货还必须在送货之前完成。这和普通 VRP 的“每个客户点访问一次”是两套约束路网看着差不多建模错一个细节解出来就会出一批超容或绕路的废路线。Python 里最常见也最可靠的落地路径是 Google OR-Tools 的 routing 库配小型 MILP 做最优解校准配遗传算法或大邻域搜索应付超大规模。下面按“先把模型写对再谈参数和坑”的顺序展开适合正在做路径规划、取送货调度或者想从普通 VRP 迁移过来的工程师。2. 把 Pickup-Delivery-VRP 的配对、先后、容量约束拆开建模标题里的 Pickup-Delivery-VRP后面统一写 PDVRP在学术界和工业界都有近亲代码实现上差距不大但约束语义差之毫厘。动手写求解器之前先分清楚在解哪一类题。2.1 PDP、VRPPD、VRPSPD 三种模型的分界与 demand 正负号常见的是三种模型混着叫。带配对关系的 Pickup and Delivery ProblemPDP要求一个请求的两个点同车、先取后送VRP with Pickups and DeliveriesVRPPD里每个客户只取或只送一种货不要求配对VRP with Simultaneous Pickup and DeliveryVRPSPD则是在同一个客户点同时卸货和装货。三者在 OR-Tools 里的落地差异从demands数组的正负号就能看出来# 节点 0 是仓库1/2/3 是取货点4/5/6 是配对送货点 pdp_demand [0, 2, 3, 1, -2, -3, -1] # 配对请求取正送负 vrppd_demand [0, 1, -1, 1, -1, 1, -1] # 每个点只取或只送 # vrpspd: 每个点同时有取量 p[i] 和送量 d[i]净需求 p[i] - d[i] vrpspd_net [0] [p[i] - d[i] for i in range(1, 7)]PDP 的 demand 必须成对抵消否则容量维度在送货点出现“凭空涨载”解出来的路线负载会朝着奇怪方向走。VRPPD 则允许正负混杂约束上只需保证全程负载不越界不关心某一单的去向。VRPSPD 最常见于空瓶回收、快递驿站这类场景求解时通常先把净需求算出来但这样会丢失“同一时刻卸了才能装”的物理细节严格场景还要加同点装卸的次序约束。模型配对约束先取后送同点同时装卸典型场景PDP必须必须无冷链、顺路捎带、退货回收VRPPD无无无门店补货与退货混跑VRPSPD无无必须饮料空瓶回收、快递驿站实际项目里需求方说“取送货”一般指的是 PDP也就是本标题对应的场景如果需求里出现“顺路取”“回程带货”这类说法先按 VRPPD 确认配对是否真的需要能省掉一半的约束代码。2.2 弧流模型里三组约束的数学表达把模型写清楚用弧流最直接。设 x_{ijk} ∈ {0,1} 表示车辆 k 走弧 (i,j)q_i 是节点 i 的净货量L_i 是服务完节点 i 后的载重u_i 是访问次序。三组硬约束可以压缩成下面这张表约束数学表达代码里的落点流守恒Σ_j x_{j,i,k} Σ_j x_{i,j,k}i≠仓库routing 库内置配对Σ_j x_{j,p,k} Σ_j x_{j,d,k}对每个 kAddPickupAndDelivery VehicleVar 相等先后u_p u_dCumulVar(pickup) ≤ CumulVar(delivery)容量0 ≤ L_i ≤ Q_kL_next L_i q_iAddDimensionWithVehicleCapacity配对约束的直觉是节点 p 被车辆 k 访问当且仅当节点 d 也被同一辆车访问写成入弧求和相等即可。先后约束优先用时间维度表达u_p service_p ≤ u_d没有时间维度时借容量维度的单调性也能做第 3 章会看到具体写法。容量约束的关键在于 q_i 带符号取货点是正的、送货点是负的任何时刻 0 ≤ L_i ≤ Q_k 才合法。这一族问题的复杂度继承自 VRP单车辆时退化为 TSP已经是 NP-难加上配对约束后解空间的可行域被切得稀碎精确解的规模分水岭比普通 VRP 更早到来。2.3 精确解的规模分水岭与选型含义我一般用这个经验值划分请求数在 1015 时MILP 配上 CBC 求解器能在几分钟内出最优解20 个请求以上求解时间开始指数膨胀接近 40 个点时除非目标函数非常稀松否则纯精确法在工程上已经没有等待价值。这不是说精确解没用它的正确用法是当“标尺”——用十几点的随机实例同时跑 MILP 和 OR-Tools比较目标值差距来确认启发式实现没有结构性问题。规模再往上行业实践基本落在 OR-Tools 的局部搜索、遗传算法和大邻域搜索三类下一章给出 OR-Tools 的最小实现。3. 用 OR-Tools 实现取送货 VRP 的最小可运行代码python 环境装好后一条pip install ortools就能把 routing 库和 CP-SAT 一起装上。下面这段代码是取送货 VRP 里最小可用的一版直接对着 PyCharm 或 vscode 的新文件贴进去就能跑。3.1 数据准备与两个回调函数OR-Tools 的 routing 模型不直接吃节点坐标它要求注册回调函数把“节点对”翻译成弧上的代价和货量。先看数据结构和距离回调from ortools.constraint_solver import routing_enums_pb2, pywrapcp def create_data_model(): data {} data[distance_matrix] [ [0, 8, 5, 9, 12, 7, 6], [8, 0, 4, 10, 5, 9, 8], [5, 4, 0, 6, 8, 3, 7], [9, 10, 6, 0, 11, 9, 4], [12, 5, 8, 11, 0, 10, 7], [7, 9, 3, 9, 10, 0, 5], [6, 8, 7, 4, 7, 5, 0], ] data[demands] [0, 2, 3, 1, -2, -3, -1] # 取货 送货 - data[pickups_deliveries] [[1, 4], [2, 5], [3, 6]] data[vehicle_capacities] [4, 4, 4] data[num_vehicles], data[depot] 3, 0 return data data create_data_model() manager pywrapcp.RoutingIndexManager( len(data[distance_matrix]), data[num_vehicles], data[depot]) routing pywrapcp.RoutingModel(manager) def dist_cb(frm, to): frm_node manager.IndexToNode(frm) to_node manager.IndexToNode(to) return data[distance_matrix][frm_node][to_node] transit routing.RegisterTransitCallback(dist_cb) routing.SetArcCostEvaluatorOfAllVehicles(transit)RoutingIndexManager把“节点 车辆”的复合索引统一管理起来回调里必须用IndexToNode把索引进制回原始节点号否则多车场景会取到错的距离。RegisterTransitCallback只是注册函数本身真正决定它怎么参与求解的是SetArcCostEvaluatorOfAllVehicles这一句。3.2 AddPickupAndDelivery 配对与先后约束的真正含义容量维度和配对约束是取送货 VRP 的核心代码只有几行但每一行都有讲究def demand_cb(frm): return data[demands][manager.IndexToNode(frm)] demand_idx routing.RegisterUnaryTransitCallback(demand_cb) routing.AddDimensionWithVehicleCapacity( demand_idx, 0, data[vehicle_capacities], True, Capacity) for p, d in data[pickups_deliveries]: p_idx, d_idx manager.NodeToIndex(p), manager.NodeToIndex(d) routing.AddPickupAndDelivery(p_idx, d_idx) routing.solver().Add(routing.VehicleVar(p_idx) routing.VehicleVar(d_idx)) routing.solver().Add(routing.CumulVar(p_idx, Capacity) routing.CumulVar(d_idx, Capacity))AddDimensionWithVehicleCapacity的第三个参数传的是每辆车的容量列表第二个参数slack_max0表示不允许车辆原地空等最后一个True强制车辆从仓库出发时载重为 0。逐请求的约束里AddPickupAndDelivery申明这两个节点构成一个配对请求VehicleVar相等保证同车容量维度上的累积变量CumulVar(p, Capacity) CumulVar(d, Capacity)利用载重在取货点上升、送货点下降的单调性逼着送货出现在取货之后。这个写法依赖 demand 严格正负配对如果某个请求的货量为 0 或负数顺序约束会静默失效这是我排查线上模型时最先怀疑的地方。3.2.1 容量维度同时承担顺序约束的机理为什么容量维度能表达先后顺序routing 的维度和距离维度不是一回事CumulVar记录的是车辆到达某个节点时的累计状态。取货点让累计载重增加 q送货点让它减少 q那么“先取后送”等价于“到达配送点时的载重 ≥ 到达取货点时的载重”不等式两边的差值恰好是 q。反过来如果求解器尝试把送货排在取货前到达取货点时载重已经被扣过一次这个不等式必然被击穿搜索会沿着这条分支直接剪掉。理解这一层才能在出现“先送后取”时快速定位是 demand 符号错了还是这一行约束被误删。提示AddPickupAndDelivery只建立配对关系本身不强加先后顺序。先后顺序必须靠容量或时间维度上的不等式显式给出漏掉这一行求解器会给出“先送后取”的合法路线。3.3 参数表第一解策略、局部搜索与时间预算模型搭完求解参数决定解的质量和耗时。默认参数对纯 VRP 够用但对取送货这种可行域碎的模型通常要显式指定params pywrapcp.DefaultRoutingSearchParameters() params.first_solution_strategy ( routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION) params.local_search_metaheuristic ( routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH) params.time_limit.seconds 30 solution routing.SolveWithParameters(params)参数推荐取值生效时机说明first_solution_strategyPARALLEL_CHEAPEST_INSERTION构造初始解对容量约束友好插入失败会自动尝试其他车local_search_metaheuristicGUIDED_LOCAL_SEARCH改进初始解带惩罚震荡比单纯 TABU 少卡局部最优time_limit.seconds30~300整个求解建议按业务允许的最长等待来设而不是目标值random_seed固定或变化全程固定便于回归变化便于多 restarts 取最优GUIDED_LOCAL_SEARCH 相对于 SIMULATED_ANNEALING 更可预测因为它会把长期惩罚加到频繁出现的坏边上对容量维度这种硬约束密集的问题更友好。时间预算建议设成业务能等的最长值因为 OR-Tools 的局部搜索在时间耗尽前几乎一直在改善目标不存在“多给时间没意义”的情况。4. 规模变大或约束定制MILP、遗传算法与惩罚松弛的分工OR-Tools 覆盖的是 15 到几百个点的区间。规模更小要最优性证明规模更大或约束太偏门就得把精确模型和元启发式请回来。这一章给出三者的分工边界和对应做法。4.1 用小型 MILP 给 OR-Tools 的解质量做校准n≤15取送货的配对约束在 MILP 里最自然的表达是给每个请求引入次序变量 u约束 u_p 1 ≤ u_d。单车辆版本的紧凑模型如下多车辆就在每条弧上补一个车辆下标 k配对变成“同一辆车访问 p 和 d”的等式import pulp N range(7) # 0 仓库1/2/3 取货4/5/6 送货 P, D [1, 2, 3], [4, 5, 6] q {1: 2, 2: 3, 3: 1, 4: -2, 5: -3, 6: -1} Q 4 # dist[i][j] 为距离矩阵这里省略构造 prob pulp.LpProblem(pdp_calib, pulp.LpMinimize) x {(i, j): pulp.LpVariable(fx_{i}_{j}, catBinary) for i in N for j in N if i ! j} u {i: pulp.LpVariable(fu_{i}, lowBound0, upBoundlen(N) - 1) for i in N} L {i: pulp.LpVariable(fL_{i}, lowBound0, upBoundQ) for i in N} prob pulp.lpSum(dist[i][j] * x[i, j] for i in N for j in N if i ! j) for i in N: if i ! 0: prob pulp.lpSum(x[j, i] for j in N if j ! i) 1 # 每点一进一出 prob pulp.lpSum(x[i, j] for j in N if j ! i) 1 for i, j in x: prob u[j] u[i] 1 - len(N) * (1 - x[i, j]) # 子回路消除 prob L[j] L[i] q[j] - Q * (1 - x[i, j]) # 容量累积 prob u[0] 0 prob L[0] 0 for p, d in zip(P, D): prob u[p] 1 u[d] # 先取后送 prob.solve(pulp.PULP_CBC_CMD(timeLimit120))u[j] u[i] 1 - M(1 - x_ij)是标准的 MTZ 子回路消除M 用节点总数代替容量约束同理走弧 (i,j) 时载重至少增加 q_j。注意L[0] 0和u[0] 0缺一不可前者让仓库出发载重归零后者让次序从仓库开始计数否则模型会解出悬浮在仓库外的不连通回路。CBC 默认不带时间限制跑不动的实例要显式传timeLimit。这个模型跑出来的最优值和第三章 OR-Tools 的结果做对比时我一般要求差距在 5% 以内才认为启发式参数设置合理。4.2 500 点以上用 route-first cluster-second 解码的遗传算法节点到了 500 以上OR-Tools 的局部搜索仍然能出解但算子移动的粒度是按单点的取送货配对让相邻交换的可行率很低。常见的做法是用遗传算法染色体存请求编号的排列解码时先用容量切分路线再在每条路线内处理先取后送def decode_pdp(genes, loads, cap): routes, cur, load [], [], 0 seen set() for g in list(genes): if g % 2 1 and (g - 1) not in seen: # 送货先出现推迟 genes.append(g) # 简单修复 continue if load loads[g] cap: # 超容则断车 routes.append(cur) cur, load [], 0 cur.append(g) load loads[g] seen.add(g) if cur: routes.append(cur) return routes这是 route-first生成一条大序列加 cluster-second按容量切开的经典组合。g % 2 1判断送货基因如果它对应的取货还没进seen就把它推迟到序列尾部换取“先取后送”的硬约束工程实现里要给推迟次数加上限否则不可行基因会无限循环。负载在解码过程中保持单调累加切分点天然满足每辆车容量不越界。遗传算法的变异算子尽量选“块重排”而不是单点交换因为单点交换极容易把配对请求拆到两辆车里后代可行率会断崖下跌。4.3 三条路线怎么选以及不可行实例的惩罚松弛三条技术路线各有明确的适用区间实际项目按实例规模和目标挑路线适用规模典型耗时优势主要代价MILPPuLP/CBC≤15 请求秒分钟最优性证明指数退化OR-Tools routing15500 节点秒5 分钟约束全、开发量小没有最优性下界自研 GA/ALNS500 或深度定制分钟级算子可定制调参成本高、易早熟当实例本身不可行——比如总货量超过所有车辆容量之和或个别节点的时间窗过窄——第一反应不该是加大搜索时间而是给病态节点加惩罚松弛。OR-Tools 里对单个节点的 optional 化写法是routing.AddDisjunction([node], penalty)允许搜索过程以付出惩罚代价的方式放弃该节点。用在配对请求上时两端各加一个 disjunction解出来后要专门检查是否有“只取不送”或“只送不取”的残端这类残端说明搜索在配对约束上做了错误取舍。先把惩罚调小、保证整体出解再人工检查被丢弃的节点清单比让求解器在无解空间里空转更接近业务可用。5. 解出来之后校验器、可视化与并行调参求解器返回 solution 不等于路线可以直接上线。先把可行性和质量两个层面过一遍再决定要不要继续调参。可行性这层我习惯用一个独立的纯 Python 校验函数兜底不依赖任何 OR-Tools 内部结构。5.1 独立于求解器的可行性校验器def verify(routes, demands, cap, pairs): for vid, route in enumerate(routes): load, at 0, {} for node in route: if node 0: continue load demands[node] assert load 0 and load cap[vid], fV{vid} 容量越界 at {node} at[node] len(at) for p, d in pairs: if p in at and d in at: assert at[p] at[d], fV{vid} 先送后取 {p}-{d}校验器要和求解器用完全独立的数据流从solution里抽 route 时只读节点顺序货量和容量从原始输入重新计算不要复用求解模型里的 cumul 变量。这样能兜住最常见的两类 bugdemand 正负写反导致的负载重以及AddPickupAndDelivery漏了先后约束后出现的先送后取。5.2 目标值之外把路线画出来看目标函数只回答“多少公里”回答不了“这路线绕不绕”。用 matplotlib 把每条车的路径按颜色画出来交叉弧和回头路一眼就能看出来。vscode 配好 python 环境后在dist_cb和demand_cb里打上断点观察哪些节点的距离被回调成了 0 或异常大数——这类数据脏问题在目标值上看不出来在图上和断点里藏不住。5.3 用 python 多进程跑多次随机重启取最优OR-Tools 的局部搜索受初始解影响明显单次 60 秒的结果方差可能不小。常见做法是用multiprocessing.Pool并行跑多个不同random_seed的求解收集所有解后取目标值最小的with Pool(4) as pool: results pool.map(run_one, range(8)) # run_one 内部重建模型并设置 seed best min(results, keylambda s: s.ObjectiveValue())注意 pywrapcp 的 RoutingModel 不支持跨进程 picklerun_one里必须重新构建 manager、routing 和回调否则会报序列化错误。8 个 seed、每个 60 秒、4 进程并行实际等待约 2 分钟比单进程跑 8 分钟拿到的最好解通常更好回归验证时把这些 seed 固定下来结果即可复现。本文还有配套的精品资源点击获取 Python实现取送货VRP：OR-Tools建模与约束拆解
简介面向物流路径规划与运筹优化场景的取送货VRP问题这份Python实现方案覆盖从节点建模、路径更新到结果校验的完整闭环适合正在学习车辆路径问题的开发者、研究者及学生尤其适合需要快速上手带取送约束场景的初学者。压缩包共6个文件核心是3个Python脚本分别实现RouteNode节点定义、主求解逻辑与自动化测试另有3个txt文档提供依赖清单、运行说明及实验数据便于核对输入输出格式与参数配置。包体仅5KB轻量精简加载迅速。代码内嵌大量注解关键计算步骤均有注释可直接运行验证效果也能在了解逻辑后灵活修改求解策略或增加约束条件。目前已有1012人学习下载可作为课程设计、小型项目以及物流调度入门的重要参考资料也可作为进一步研究启发式算法与路径优化问题的起点。1. 取送货 VRP 不是把回程点塞进 VRP 那么简单同城配送里最容易被低估的一类问题是取送货Pickup-Delivery-VRP一张订单同时包含一个取货点和一个送货点两个点必须由同一辆车服务取货还必须在送货之前完成。这和普通 VRP 的“每个客户点访问一次”是两套约束路网看着差不多建模错一个细节解出来就会出一批超容或绕路的废路线。Python 里最常见也最可靠的落地路径是 Google OR-Tools 的 routing 库配小型 MILP 做最优解校准配遗传算法或大邻域搜索应付超大规模。下面按“先把模型写对再谈参数和坑”的顺序展开适合正在做路径规划、取送货调度或者想从普通 VRP 迁移过来的工程师。2. 把 Pickup-Delivery-VRP 的配对、先后、容量约束拆开建模标题里的 Pickup-Delivery-VRP后面统一写 PDVRP在学术界和工业界都有近亲代码实现上差距不大但约束语义差之毫厘。动手写求解器之前先分清楚在解哪一类题。2.1 PDP、VRPPD、VRPSPD 三种模型的分界与 demand 正负号常见的是三种模型混着叫。带配对关系的 Pickup and Delivery ProblemPDP要求一个请求的两个点同车、先取后送VRP with Pickups and DeliveriesVRPPD里每个客户只取或只送一种货不要求配对VRP with Simultaneous Pickup and DeliveryVRPSPD则是在同一个客户点同时卸货和装货。三者在 OR-Tools 里的落地差异从demands数组的正负号就能看出来# 节点 0 是仓库1/2/3 是取货点4/5/6 是配对送货点 pdp_demand [0, 2, 3, 1, -2, -3, -1] # 配对请求取正送负 vrppd_demand [0, 1, -1, 1, -1, 1, -1] # 每个点只取或只送 # vrpspd: 每个点同时有取量 p[i] 和送量 d[i]净需求 p[i] - d[i] vrpspd_net [0] [p[i] - d[i] for i in range(1, 7)]PDP 的 demand 必须成对抵消否则容量维度在送货点出现“凭空涨载”解出来的路线负载会朝着奇怪方向走。VRPPD 则允许正负混杂约束上只需保证全程负载不越界不关心某一单的去向。VRPSPD 最常见于空瓶回收、快递驿站这类场景求解时通常先把净需求算出来但这样会丢失“同一时刻卸了才能装”的物理细节严格场景还要加同点装卸的次序约束。模型配对约束先取后送同点同时装卸典型场景PDP必须必须无冷链、顺路捎带、退货回收VRPPD无无无门店补货与退货混跑VRPSPD无无必须饮料空瓶回收、快递驿站实际项目里需求方说“取送货”一般指的是 PDP也就是本标题对应的场景如果需求里出现“顺路取”“回程带货”这类说法先按 VRPPD 确认配对是否真的需要能省掉一半的约束代码。2.2 弧流模型里三组约束的数学表达把模型写清楚用弧流最直接。设 x_{ijk} ∈ {0,1} 表示车辆 k 走弧 (i,j)q_i 是节点 i 的净货量L_i 是服务完节点 i 后的载重u_i 是访问次序。三组硬约束可以压缩成下面这张表约束数学表达代码里的落点流守恒Σ_j x_{j,i,k} Σ_j x_{i,j,k}i≠仓库routing 库内置配对Σ_j x_{j,p,k} Σ_j x_{j,d,k}对每个 kAddPickupAndDelivery VehicleVar 相等先后u_p u_dCumulVar(pickup) ≤ CumulVar(delivery)容量0 ≤ L_i ≤ Q_kL_next L_i q_iAddDimensionWithVehicleCapacity配对约束的直觉是节点 p 被车辆 k 访问当且仅当节点 d 也被同一辆车访问写成入弧求和相等即可。先后约束优先用时间维度表达u_p service_p ≤ u_d没有时间维度时借容量维度的单调性也能做第 3 章会看到具体写法。容量约束的关键在于 q_i 带符号取货点是正的、送货点是负的任何时刻 0 ≤ L_i ≤ Q_k 才合法。这一族问题的复杂度继承自 VRP单车辆时退化为 TSP已经是 NP-难加上配对约束后解空间的可行域被切得稀碎精确解的规模分水岭比普通 VRP 更早到来。2.3 精确解的规模分水岭与选型含义我一般用这个经验值划分请求数在 1015 时MILP 配上 CBC 求解器能在几分钟内出最优解20 个请求以上求解时间开始指数膨胀接近 40 个点时除非目标函数非常稀松否则纯精确法在工程上已经没有等待价值。这不是说精确解没用它的正确用法是当“标尺”——用十几点的随机实例同时跑 MILP 和 OR-Tools比较目标值差距来确认启发式实现没有结构性问题。规模再往上行业实践基本落在 OR-Tools 的局部搜索、遗传算法和大邻域搜索三类下一章给出 OR-Tools 的最小实现。3. 用 OR-Tools 实现取送货 VRP 的最小可运行代码python 环境装好后一条pip install ortools就能把 routing 库和 CP-SAT 一起装上。下面这段代码是取送货 VRP 里最小可用的一版直接对着 PyCharm 或 vscode 的新文件贴进去就能跑。3.1 数据准备与两个回调函数OR-Tools 的 routing 模型不直接吃节点坐标它要求注册回调函数把“节点对”翻译成弧上的代价和货量。先看数据结构和距离回调from ortools.constraint_solver import routing_enums_pb2, pywrapcp def create_data_model(): data {} data[distance_matrix] [ [0, 8, 5, 9, 12, 7, 6], [8, 0, 4, 10, 5, 9, 8], [5, 4, 0, 6, 8, 3, 7], [9, 10, 6, 0, 11, 9, 4], [12, 5, 8, 11, 0, 10, 7], [7, 9, 3, 9, 10, 0, 5], [6, 8, 7, 4, 7, 5, 0], ] data[demands] [0, 2, 3, 1, -2, -3, -1] # 取货 送货 - data[pickups_deliveries] [[1, 4], [2, 5], [3, 6]] data[vehicle_capacities] [4, 4, 4] data[num_vehicles], data[depot] 3, 0 return data data create_data_model() manager pywrapcp.RoutingIndexManager( len(data[distance_matrix]), data[num_vehicles], data[depot]) routing pywrapcp.RoutingModel(manager) def dist_cb(frm, to): frm_node manager.IndexToNode(frm) to_node manager.IndexToNode(to) return data[distance_matrix][frm_node][to_node] transit routing.RegisterTransitCallback(dist_cb) routing.SetArcCostEvaluatorOfAllVehicles(transit)RoutingIndexManager把“节点 车辆”的复合索引统一管理起来回调里必须用IndexToNode把索引进制回原始节点号否则多车场景会取到错的距离。RegisterTransitCallback只是注册函数本身真正决定它怎么参与求解的是SetArcCostEvaluatorOfAllVehicles这一句。3.2 AddPickupAndDelivery 配对与先后约束的真正含义容量维度和配对约束是取送货 VRP 的核心代码只有几行但每一行都有讲究def demand_cb(frm): return data[demands][manager.IndexToNode(frm)] demand_idx routing.RegisterUnaryTransitCallback(demand_cb) routing.AddDimensionWithVehicleCapacity( demand_idx, 0, data[vehicle_capacities], True, Capacity) for p, d in data[pickups_deliveries]: p_idx, d_idx manager.NodeToIndex(p), manager.NodeToIndex(d) routing.AddPickupAndDelivery(p_idx, d_idx) routing.solver().Add(routing.VehicleVar(p_idx) routing.VehicleVar(d_idx)) routing.solver().Add(routing.CumulVar(p_idx, Capacity) routing.CumulVar(d_idx, Capacity))AddDimensionWithVehicleCapacity的第三个参数传的是每辆车的容量列表第二个参数slack_max0表示不允许车辆原地空等最后一个True强制车辆从仓库出发时载重为 0。逐请求的约束里AddPickupAndDelivery申明这两个节点构成一个配对请求VehicleVar相等保证同车容量维度上的累积变量CumulVar(p, Capacity) CumulVar(d, Capacity)利用载重在取货点上升、送货点下降的单调性逼着送货出现在取货之后。这个写法依赖 demand 严格正负配对如果某个请求的货量为 0 或负数顺序约束会静默失效这是我排查线上模型时最先怀疑的地方。3.2.1 容量维度同时承担顺序约束的机理为什么容量维度能表达先后顺序routing 的维度和距离维度不是一回事CumulVar记录的是车辆到达某个节点时的累计状态。取货点让累计载重增加 q送货点让它减少 q那么“先取后送”等价于“到达配送点时的载重 ≥ 到达取货点时的载重”不等式两边的差值恰好是 q。反过来如果求解器尝试把送货排在取货前到达取货点时载重已经被扣过一次这个不等式必然被击穿搜索会沿着这条分支直接剪掉。理解这一层才能在出现“先送后取”时快速定位是 demand 符号错了还是这一行约束被误删。提示AddPickupAndDelivery只建立配对关系本身不强加先后顺序。先后顺序必须靠容量或时间维度上的不等式显式给出漏掉这一行求解器会给出“先送后取”的合法路线。3.3 参数表第一解策略、局部搜索与时间预算模型搭完求解参数决定解的质量和耗时。默认参数对纯 VRP 够用但对取送货这种可行域碎的模型通常要显式指定params pywrapcp.DefaultRoutingSearchParameters() params.first_solution_strategy ( routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION) params.local_search_metaheuristic ( routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH) params.time_limit.seconds 30 solution routing.SolveWithParameters(params)参数推荐取值生效时机说明first_solution_strategyPARALLEL_CHEAPEST_INSERTION构造初始解对容量约束友好插入失败会自动尝试其他车local_search_metaheuristicGUIDED_LOCAL_SEARCH改进初始解带惩罚震荡比单纯 TABU 少卡局部最优time_limit.seconds30~300整个求解建议按业务允许的最长等待来设而不是目标值random_seed固定或变化全程固定便于回归变化便于多 restarts 取最优GUIDED_LOCAL_SEARCH 相对于 SIMULATED_ANNEALING 更可预测因为它会把长期惩罚加到频繁出现的坏边上对容量维度这种硬约束密集的问题更友好。时间预算建议设成业务能等的最长值因为 OR-Tools 的局部搜索在时间耗尽前几乎一直在改善目标不存在“多给时间没意义”的情况。4. 规模变大或约束定制MILP、遗传算法与惩罚松弛的分工OR-Tools 覆盖的是 15 到几百个点的区间。规模更小要最优性证明规模更大或约束太偏门就得把精确模型和元启发式请回来。这一章给出三者的分工边界和对应做法。4.1 用小型 MILP 给 OR-Tools 的解质量做校准n≤15取送货的配对约束在 MILP 里最自然的表达是给每个请求引入次序变量 u约束 u_p 1 ≤ u_d。单车辆版本的紧凑模型如下多车辆就在每条弧上补一个车辆下标 k配对变成“同一辆车访问 p 和 d”的等式import pulp N range(7) # 0 仓库1/2/3 取货4/5/6 送货 P, D [1, 2, 3], [4, 5, 6] q {1: 2, 2: 3, 3: 1, 4: -2, 5: -3, 6: -1} Q 4 # dist[i][j] 为距离矩阵这里省略构造 prob pulp.LpProblem(pdp_calib, pulp.LpMinimize) x {(i, j): pulp.LpVariable(fx_{i}_{j}, catBinary) for i in N for j in N if i ! j} u {i: pulp.LpVariable(fu_{i}, lowBound0, upBoundlen(N) - 1) for i in N} L {i: pulp.LpVariable(fL_{i}, lowBound0, upBoundQ) for i in N} prob pulp.lpSum(dist[i][j] * x[i, j] for i in N for j in N if i ! j) for i in N: if i ! 0: prob pulp.lpSum(x[j, i] for j in N if j ! i) 1 # 每点一进一出 prob pulp.lpSum(x[i, j] for j in N if j ! i) 1 for i, j in x: prob u[j] u[i] 1 - len(N) * (1 - x[i, j]) # 子回路消除 prob L[j] L[i] q[j] - Q * (1 - x[i, j]) # 容量累积 prob u[0] 0 prob L[0] 0 for p, d in zip(P, D): prob u[p] 1 u[d] # 先取后送 prob.solve(pulp.PULP_CBC_CMD(timeLimit120))u[j] u[i] 1 - M(1 - x_ij)是标准的 MTZ 子回路消除M 用节点总数代替容量约束同理走弧 (i,j) 时载重至少增加 q_j。注意L[0] 0和u[0] 0缺一不可前者让仓库出发载重归零后者让次序从仓库开始计数否则模型会解出悬浮在仓库外的不连通回路。CBC 默认不带时间限制跑不动的实例要显式传timeLimit。这个模型跑出来的最优值和第三章 OR-Tools 的结果做对比时我一般要求差距在 5% 以内才认为启发式参数设置合理。4.2 500 点以上用 route-first cluster-second 解码的遗传算法节点到了 500 以上OR-Tools 的局部搜索仍然能出解但算子移动的粒度是按单点的取送货配对让相邻交换的可行率很低。常见的做法是用遗传算法染色体存请求编号的排列解码时先用容量切分路线再在每条路线内处理先取后送def decode_pdp(genes, loads, cap): routes, cur, load [], [], 0 seen set() for g in list(genes): if g % 2 1 and (g - 1) not in seen: # 送货先出现推迟 genes.append(g) # 简单修复 continue if load loads[g] cap: # 超容则断车 routes.append(cur) cur, load [], 0 cur.append(g) load loads[g] seen.add(g) if cur: routes.append(cur) return routes这是 route-first生成一条大序列加 cluster-second按容量切开的经典组合。g % 2 1判断送货基因如果它对应的取货还没进seen就把它推迟到序列尾部换取“先取后送”的硬约束工程实现里要给推迟次数加上限否则不可行基因会无限循环。负载在解码过程中保持单调累加切分点天然满足每辆车容量不越界。遗传算法的变异算子尽量选“块重排”而不是单点交换因为单点交换极容易把配对请求拆到两辆车里后代可行率会断崖下跌。4.3 三条路线怎么选以及不可行实例的惩罚松弛三条技术路线各有明确的适用区间实际项目按实例规模和目标挑路线适用规模典型耗时优势主要代价MILPPuLP/CBC≤15 请求秒分钟最优性证明指数退化OR-Tools routing15500 节点秒5 分钟约束全、开发量小没有最优性下界自研 GA/ALNS500 或深度定制分钟级算子可定制调参成本高、易早熟当实例本身不可行——比如总货量超过所有车辆容量之和或个别节点的时间窗过窄——第一反应不该是加大搜索时间而是给病态节点加惩罚松弛。OR-Tools 里对单个节点的 optional 化写法是routing.AddDisjunction([node], penalty)允许搜索过程以付出惩罚代价的方式放弃该节点。用在配对请求上时两端各加一个 disjunction解出来后要专门检查是否有“只取不送”或“只送不取”的残端这类残端说明搜索在配对约束上做了错误取舍。先把惩罚调小、保证整体出解再人工检查被丢弃的节点清单比让求解器在无解空间里空转更接近业务可用。5. 解出来之后校验器、可视化与并行调参求解器返回 solution 不等于路线可以直接上线。先把可行性和质量两个层面过一遍再决定要不要继续调参。可行性这层我习惯用一个独立的纯 Python 校验函数兜底不依赖任何 OR-Tools 内部结构。5.1 独立于求解器的可行性校验器def verify(routes, demands, cap, pairs): for vid, route in enumerate(routes): load, at 0, {} for node in route: if node 0: continue load demands[node] assert load 0 and load cap[vid], fV{vid} 容量越界 at {node} at[node] len(at) for p, d in pairs: if p in at and d in at: assert at[p] at[d], fV{vid} 先送后取 {p}-{d}校验器要和求解器用完全独立的数据流从solution里抽 route 时只读节点顺序货量和容量从原始输入重新计算不要复用求解模型里的 cumul 变量。这样能兜住最常见的两类 bugdemand 正负写反导致的负载重以及AddPickupAndDelivery漏了先后约束后出现的先送后取。5.2 目标值之外把路线画出来看目标函数只回答“多少公里”回答不了“这路线绕不绕”。用 matplotlib 把每条车的路径按颜色画出来交叉弧和回头路一眼就能看出来。vscode 配好 python 环境后在dist_cb和demand_cb里打上断点观察哪些节点的距离被回调成了 0 或异常大数——这类数据脏问题在目标值上看不出来在图上和断点里藏不住。5.3 用 python 多进程跑多次随机重启取最优OR-Tools 的局部搜索受初始解影响明显单次 60 秒的结果方差可能不小。常见做法是用multiprocessing.Pool并行跑多个不同random_seed的求解收集所有解后取目标值最小的with Pool(4) as pool: results pool.map(run_one, range(8)) # run_one 内部重建模型并设置 seed best min(results, keylambda s: s.ObjectiveValue())注意 pywrapcp 的 RoutingModel 不支持跨进程 picklerun_one里必须重新构建 manager、routing 和回调否则会报序列化错误。8 个 seed、每个 60 秒、4 进程并行实际等待约 2 分钟比单进程跑 8 分钟拿到的最好解通常更好回归验证时把这些 seed 固定下来结果即可复现。本文还有配套的精品资源点击获取