简介面向物流调度、运筹优化学习者这份VRP问题相关程序聚焦带时间窗约束的车辆路径规划VRPTW问题提供完整的算法实现与实验环境。资源共88个文件压缩包大小1.63MB其中txt文件如R101、C101等算例为Solomon基准测试数据及路径输出结果zip压缩包内为经典solomon_25/50/100数据集htm格式文档为Benchmarking Problems说明另有VC6.0工程源码、exe可执行程序和一篇基于多目标遗传算法求解VRPTW的PDF论文便于直接运行与对照分析。已有404人学习下载。内容涵盖模型定义、遗传算法实现、适应度统计和车辆路径输出同时附有最优解参考资料可帮助读者快速上手VRPTW求解流程比较不同算法性能适合用于课程设计、毕业设计或物流路径优化的入门研究。 搞车辆路径问题VRPVehicle Routing Problem的程序说白了就是把人脑排车变成程序排车。这事我在实际项目里做过好几轮从最初用Excel手工调度到后来用专门求解器跑几百个点的配送路径中间踩的坑不少。这篇文章不是教科书而是把我自己在VRP程序开发里用到的思路、代码、参数以及那些查文档查不到的经验完整沉淀一遍。适合两类人看一是刚接触VRP、想快速上手的算法工程师二是物流/配送系统里做调度模块、正在选型或者已经决定用程序解法替代手工排线的开发者。VRP的问题拆解先搞清你在解决什么1.1 VRP不是一道题而是一族问题我刚接触VRP的时候犯了个典型错误以为VRP就是给一批订单找最短路线。真正把数据摆到桌面上才发现现实里的配送约束远比教科书复杂。教科书里的经典VRP有一个车场、若干客户点、每个客户点有固定需求车队从车场出发送完货再回车场目标是总行驶距离最短。但真实项目里几乎不会这么干净常见的变体包括CVRPCapacitated VRP每辆车有最大载重/容积所有路径不能超载。这是最基础的版本也是绝大多数系统的起点。VRPTWVRP with Time Windows客户点有可服务时间段早到了要等晚到了要罚。生鲜配送、同城急送基本都是这种。VRPPDVRP with Pickup and Delivery既要取货又要送货且同一客户的取送通常要求同一辆车完成。跑腿平台、快递揽派一体就是这种情况。MDVRPMulti-Depot VRP多个车场车辆从不同车场出发。连锁门店的补货特别常见。程序上这些变体看起来只是多一个约束但实现复杂度完全不一样。单纯的CVRP用成熟的求解器加一个容量维度就能跑VRPTW要额外维护时间窗和车辆到达时间VRPPD则要处理成对节点的先后顺序和同车约束。所以做程序之前第一件事是把自己要解决的问题归类——你处理的是基础版还是带时间窗的版本这直接决定了程序架构怎么写也决定了后面能不能用现成工具还是必须自己推算法。1.2 为什么VRP程序能跑和好用是两回事很多第一次写VRP程序的人难点不在理解问题而在程序能跑但排出来的路径没法用。我在一个配送项目里遇到过这种情况用求解器跑出来的路径总里程确实比手工排线少但调度员一看就否决了——因为路径里有回头路有的司机路线太长有的司机只有两单明显不公平。这就是典型的数学模型最优和实际业务满意之间的冲突。原因在于VRP程序做的是多目标折中总成本最小只是一个目标实际还要考虑车辆负载均衡、司机工作时长均衡、客户优先级、道路限行、停车难度。这些在模型里不是天然存在的需要你显式地建模成约束或优化目标。所以做程序之前务必和业务方把什么算一条好路径定义清楚否则你优化出来的路径在业务眼里就是废纸。另外一个很容易忽略的点是数据质量。VRP程序跑得再好喂进去的距离矩阵不准、需求数据有错输出就全盘崩。我见过一个项目客户坐标用的是旧库导致三成订单的地址偏移了1公里以上程序算出来的所谓最优路径实际根本无法执行。程序的准确性上限取决于输入数据质量的下限这句话在VRP场景里体现得淋漓尽致。求解器选型别一上来就啃论文写算法2.1 精确求解和启发式怎么选VRP是典型的NP-hard问题这意味着随着客户点数量增长求解时间会指数级膨胀。很多刚入行的人第一反应是我写个分支定界或者我实现一个遗传算法——如果只是练手可以但生产系统里我强烈建议先用成熟的求解器而不是自己造轮子。现在业界的常用路线分三档第一档精确求解器比如Gurobi、CPLEX。它们能把小规模问题解到最优对于几十个点、约束简单的CVRP跑出来的结果就是全局最优。但到上百个点尤其加了时间窗求解时间可能从秒级变成小时级甚至直接算不动。这类工具适合对最优性要求极高、规模又不太大的场景比如工厂内部物料配送。第二档启发式/元启发式求解器比如Google OR-Tools、VROOM、jspritJava。它们不保证全局最优但通常能在几秒到几十秒内给出一个工程上足够好的解。对于上百个点甚至上千个点的实际问题这类工具是主力。第三档专用算法框架比如针对TSP的LKH-3、针对VRP的VRPLIB社区算法。它们性能很强但问题在于接口不够友好需要你花大量时间做数据适配而且很多算法对特定问题变体有针对性换一个场景就要重新搞。我的建议很直接99%的生产项目不需要自己写算法。先确认你的问题规模再选工具如果OR-Tools能覆盖就优先OR-Tools因为社区大、资料多、API相对友好后续好维护。2.2 为什么我推荐OR-Tools作为第一选择Google OR-Tools在做VRP这类组合优化问题上有非常成熟的封装。它的核心是一个名为RoutingModel的组件内置了多种路径构造策略和局部搜索元启发式如模拟退火、指导式局部搜索。最关键的是它把定义问题和搜解解耦了你只需要把距离矩阵、需求、车辆容量、时间窗等信息喂进去它负责在后台做各种路径调整和优化。它的优势有几个开箱即用支持Python、C、Java、.NET对脚本语言用户友好。内置的局部搜索策略在中等规模问题上效果相当不错。我在一个300个点、20辆车的场景里用10秒让程序搜索得到的结果比之前纯贪心构造的路径好10%-15%。参数可调性强从构造策略到元启发式算法都可以显式指定便于做实验对比。不依赖商业许可证部署环节省心。对比一下VROOM的执行速度快但约束扩展比较受限Gurobi求精确解很强但要在Python里做复杂的模型抽象开发门槛高。OR-Tools在够用、好用、可调这三者之间平衡做得最好。核心实现手把手写一个可运行的CVRP程序3.1 数据和问题定义我下面的示例使用Python和OR-Tools解决一个经典的CVRP一个车场10个客户点每辆车容量为15目标是找总行驶距离最短的路径集合。第一步是构造数据模型。这里的关键是定义好距离矩阵、需求列表、车辆容量和车场索引。import numpy as np from ortools.constraint_solver import routing_enums_pb2, pywrapcp def create_data_model(): 构造VRP的输入数据。 data {} # 节点0是车场1~10是客户点 data[num_clients] 10 coords [ (40.0, 116.0), # 车场 (40.1, 116.2), # 客户1 (40.05, 116.15), (40.12, 116.3), (39.98, 116.1), (40.08, 116.25), (40.15, 116.2), (39.95, 116.05), (40.03, 116.28), (40.1, 116.12), (40.06, 116.18), ] # 用欧氏距离生成距离矩阵生产环境建议换成实际道路距离 coords np.array(coords) * 111.0 # 粗略把经纬度转为公里 n len(coords) dist_matrix np.sqrt(((coords[:, None, :] - coords[None, :, :]) ** 2).sum(axis-1)).round(2) data[distance_matrix] dist_matrix.tolist() # 每个节点的需求车场需求为0 data[demands] [0, 3, 2, 5, 4, 2, 3, 4, 5, 2, 1] # 车辆数量 data[num_vehicles] 3 # 每辆车的容量 data[vehicle_capacities] [15, 15, 15] # 车场节点索引 data[depot] 0 return data注意我在坐标转换上做了个简化纬度方向乘以111公里来近似换算这在市内范围的粗略估算是可以的但如果跨城市这种近似误差就会很大。生产环境建议用Haversine公式或者直接调用地图API拿实际道路距离。后面我会专门讲距离矩阵的处理。3.2 核心代码注册回调、加容量约束、搜解接下来是核心部分用OR-Tools的RoutingModel定义模型注册距离回调和需求回调加上容量维度然后指定搜索策略求解。def solve_vrp(): data create_data_model() manager pywrapcp.RoutingIndexManager( len(data[distance_matrix]), data[num_vehicles], data[depot], ) routing pywrapcp.RoutingModel(manager) def distance_callback(from_index, to_index): from_node manager.IndexToNode(from_index) to_node manager.IndexToNode(to_index) return data[distance_matrix][from_node][to_node] transit_callback_index routing.RegisterTransitCallback(distance_callback) # 设置弧成本为距离 routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) def demand_callback(from_index): from_node manager.IndexToNode(from_index) return data[demands][from_node] demand_callback_index routing.RegisterUnaryTransitCallback(demand_callback) # 添加容量约束。0表示不允许超出容量 routing.AddDimensionWithVehicleCapacity( demand_callback_index, 0, # null capacity slack data[vehicle_capacities], # 每辆车最大容量 True, # start cumul to zero Capacity, ) # 配置搜索参数 search_parameters pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC ) search_parameters.local_search_metaheuristic ( routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH ) search_parameters.time_limit.FromSeconds(10) solution routing.SolveWithParameters(search_parameters) if solution: print(f总行驶距离: {solution.ObjectiveValue()}) for vehicle_id in range(data[num_vehicles]): index routing.Start(vehicle_id) route_nodes [] route_demand 0 while not routing.IsEnd(index): node manager.IndexToNode(index) route_nodes.append(node) route_demand data[demands][node] index solution.Value(routing.NextVar(index)) node manager.IndexToNode(index) route_nodes.append(node) print(f车辆 {vehicle_id}: 路径 {route_nodes}, 总需求 {route_demand}) else: print(没有找到可行解)这段代码里有几个关键点值得展开RegisterTransitCallback用于注册计算从节点A到节点B的成本的回调我这里直接用距离矩阵。如果有道路限行、堵车系数可以在这层做加权非常灵活。AddDimensionWithVehicleCapacity是OR-Tools里加约束的核心API。第一个参数是需求回调第二个参数是松弛量一般设为0表示严格不超容第三个参数是每辆车的容量列表第四个参数表示车辆出发时累计量从0开始。first_solution_strategy和local_search_metaheuristic是决定求解质量的关键参数。前者负责生成初始解后者负责在初始解基础上做局部改进。3.3 参数调优从能跑到跑得好很多人把程序跑通就以为结束了实际上VRP程序的调参空间非常大。先看first_solution_strategy。我常用的几个策略PATH_CHEAPEST_ARC贪心逐条扩展路径每次选当前节点最近的未访问节点。速度快但解质量一般适合快速给个初始解。GLOBAL_CHEAPEST_ARC全局考虑所有可能的连接每次选成本最低的边插入。通常得到的初始解比PATH_CHEAPEST_ARC好一点。SAVINGS经典的Clarke-Wright节约算法先默认所有点单独成行然后计算合并路径的节约值按节约值从大到小合并。对CVRP特别有效我经常用它做初始解。CHRISTOFIDES只适合TSP因为VRP的约束太多基本不用。再看local_search_metaheuristic。默认的AUTOMATIC会自动选但我通常显式指定为GUIDED_LOCAL_SEARCH指导式局部搜索它在跳出局部最优方面的效果很稳定。如果时间充裕也可以用SIMULATED_ANNEALING做更充分的探索如果追求快速出结果GREEDY_DESCENT也可以但容易陷入局部最优。调参的核心思路是时间换质量设置time_limit越久局部搜索的迭代次数越多解越好但收益是边际递减的。我在实战中的经验是对于几百个点的规模10-20秒是一个性价比很高的区间超过1分钟提升幅度往往很小。遇到复杂约束时先把模型跑通再用不同策略做多次对比实验而不是盲目拉长时间。实战中的坑与排查技巧4.1 没有可行解的常见原因做VRP程序最让人头疼的就是没有找到可行解。这个问题90%出在数据或模型约束设置上而不是算法本身。第一个高发原因是车辆数量或容量不足。比如总需求是50但所有车的总容量只有40那必然无解。很多初学者没做前置校验直接塞给求解器最后得到一个令人困惑的NULL结果。我的建议是在调用求解器之前先写一个简单的校验总需求是否小于等于总容量、任意一个客户点的需求是否超过单车最大容量、车辆数是否至少为1。第二个原因是距离矩阵或需求数组的维度不匹配。OR-Tools的RoutingIndexManager要求距离矩阵是N×N的方阵需求数组长度等于节点数。如果索引错位有时候程序不报错但结果荒谬比如路径出现跳变。排查方式是把距离矩阵的shape打印出来和节点数核对。第三个原因出现在带时间窗的VRP上时间窗和车辆的行驶时间严格限制导致处处不可行。这种情况通常需要放宽某个约束比如让车辆可以早到但等待或者将时间窗的上下界放宽几分钟。我在做生鲜配送项目时遇到过一次车辆必须2小时内完成所有配送但有一个客户点距离车场单程就要1.5小时这导致无论怎么排都无解。后来和业务方确认这个客户的窗口期是灵活的于是把它放到第二批配送问题迎刃而解。所以无解时先别急着调算法回到业务里看约束是否真的合理。4.2 性能瓶颈和距离矩阵的预处理当客户点数量超过500甚至1000时程序会明显变慢。这里的瓶颈往往是距离矩阵的计算而不是OR-Tools的搜解本身。如果距离矩阵是N×N的500个点就是25万个距离计算1000个点就是100万个。如果每个距离都实时调用地图API程序肯定跑不起来。我的做法是分两类处理如果只需要欧氏距离或直线距离直接用向量化计算numpy矩阵运算很快。如果需要实际道路距离必须做离线预处理把所有订单坐标去重批量调用地图API获取距离矩阵存成缓存文件。每天更新一次即可千万别在求解时实时逐个调用API。另外OR-Tools在搜解时的时间消耗也和搜索参数有关。如果出现长时间卡死可以先调大first_solution_strategy的初始解质量比如换成SAVINGS让算法从更好的起点开始减少后续局部搜索的迭代负担。4.3 常见问题速查表为了便于排查我把平时遇到的典型问题整理成一个速查表现象可能原因处理方式返回无解车辆总容量小于总需求增加车辆数或容量或拆分订单返回无解单个客户需求超过单车容量检查需求数据或允许拆单Split Delivery路径中出现孤立点距离矩阵对角线不为0或索引错位检查距离矩阵确认IndexToNode转换无误解质量差总里程明显偏高初始解策略太贪心局部搜索时间太短换用SAVINGS延长time_limit启用GUIDED_LOCAL_SEARCH运行时间过长节点数过多距离矩阵庞大离线缓存距离矩阵缩小求解规模或分区域求解结果不公平车辆负载差异大只有总成本目标缺少均衡约束增加车辆负载均衡的目标或约束比如限制最大最小负载差从Demo到生产系统数据接入与可视化5.1 数据接入和约束扩展Demo程序跑通后要想真正投入使用还有一层工程化的工作。最常见的就是数据接入订单从哪来坐标怎么标准化车辆信息怎么维护。我在项目里习惯把业务数据和求解模型解耦——先用SQL或API把订单、车辆、门店数据聚合成中间表再转换成OR-Tools的data model。这样更换数据源时只改数据层不动求解逻辑。约束扩展也会在这一步暴露出问题。比如业务方要求某辆车只能跑某几个区域司机不能连续工作超过8小时部分客户必须由固定司机配送。OR-Tools里这些都可以通过维度Dimension来实现。维度的本质是维护一条累计量比如累计行驶时间、累计载重然后对累计量施加上下界约束。理解了维度机制后很多看似复杂的约束都能用几行代码表达出来。5.2 距离矩阵的工程化处理距离矩阵是整个VRP程序的地基。我强烈建议生产环境用真实道路距离尤其是做同城配送直线距离和实际道路距离可能差30%以上。具体实现上可以用高德、百度的路线规划API或开源的OSRM。注意批量调用时要控频加缓存避免触发限流。一个容易踩的坑是距离矩阵的对称性问题。默认情况下很多算法假设从A到B和从B到A距离相同但真实道路网里因为单行道、高架桥等原因并不对称。OR-Tools支持非对称距离矩阵但如果你用欧氏距离硬算就要意识到这是一个近似且某些算法可能对非对称数据更容易陷入局部最优。5.3 可视化让调度员愿意用你的程序最后一个容易被忽视但很重要的点是可视化。调度员不信任黑盒输出如果看不到路径长什么样他们不会用。我在项目里用folium把路径渲染到地图上不同车辆用不同颜色每个客户点附带需求量和时间窗信息。这样调度员在地图上一眼就能看出路径是否合理有没有明显的回头路有没有车辆严重偏航。可视化还能反向帮你调试程序有时候程序输出最优解但地图上看起来明显绕路这种时候多半是距离矩阵有问题或者目标函数定义不对。别只看ObjectiveValue一定要把路径画出来看。踩过几次坑之后我的习惯是所有VRP程序的开发都从最小可跑的Demo开始先保证输入输出链路通加上可视化再去调参和加约束。这样每一轮改动都能快速看到效果也不至于到头来发现程序能跑但业务根本没法用。如果你现在正准备写自己的VRP程序我个人的建议是三步走第一步用OR-Tools跑通一个简单的CVRP把数据集、回调、容量约束这些基础概念摸熟第二步引入真实订单数据把距离矩阵换成实际道路距离加上时间窗第三步再考虑自定义约束、调优和可视化。每一步的产出都能用不会白做。等你走完这三步再回头去看那些学术论文里的高级算法心里就有谱了。本文还有配套的精品资源点击获取