简介基于LKH启发式算法的快递配送路径规划与优化设计源码是一份面向物流算法工程师、运筹优化学习者及快递配送调度场景的实战项目。项目围绕Lin-Kernighan启发式算法求解大规模TSP/CVRP路径优化问题展开覆盖订单数据读取、约束校验、启发式搜索与测试对比等完整流程可帮助降低运输里程、缩短配送时间提升快递调度效率。资源包共48个文件以35个Python源码为核心并辅以XML配置、CSV订单数据、readme说明与License许可整体压缩后仅206KB目录结构清晰便于阅读和二次开发。算法侧实现了LKH搜索、禁忌搜索、2-opt/3-opt局部优化等策略同时提供bench基准脚本和测试脚本读者可替换或修改CSV中的配送点数据快速观察不同算法在路径规划上的效果差异。该资源已有293人学习适合希望系统掌握LKH算法落地、路径规划工程实现以及快递配送优化的读者参考。1. 快递配送路径规划为什么绕不开 LKH 启发式算法一个配送站一天收到三四十个订单调度员凭 GPS 直觉排出的路线通常比最优解多跑 15% 到 25%。这不是经验问题而是因为路径规划在组合优化里属于 NP 难问题人力只能在拓扑上做局部排序看不到全局交叉改进的空间。快递配送路径规划落到数学模型上就是 TSP 和带容量约束的 CVRP而 LKHLin-Kernighan-Helsgaun启发式算法是过去二十年里对这类问题最有效的公开源码求解器。它在几秒到几分钟内能在数百点上逼近最优解且稳定性远好于遗传算法和模拟退火。这篇内容适合物流系统工程师、机器人路径规划开发者以及对源码有改造需求的人把订单坐标转成 LKH 能读的文件调好参数得到可复现的路径优化结果。2. LKH 启发式算法的核心机制k-opt 链、α-近邻候选集与双桥扰动2.1 从 2-opt 到 k-opt 链为什么固定 k 值反而难写快递路径规划最底层的局部搜索是 2-opt任意选出两条不邻接的路径边交换它们的连接方式让总距离变短。2-opt 足够直观实现起来只有二三十行但它每步只能“看到”两条边。当路线被卡在需要同时断掉三四条边才能改进的局部最优时2-opt 无能为力只能依赖随机重启来碰运气。于是有了固定 k 值的 k-opt每次断开 k 条边再在所有可能的连接方式里找更优组合。固定 k 的问题在于组合爆炸。k3 时已经有几百种重连方式k5 时枚举量已经不适合在大规模路径上反复执行。Lin-Kernighan 的做法是让 k 不固定从一条边开始逐步把交换链拉长每一步都只尝试一组“可行交换”直到累计收益不再是正数。这样的链长度是问题结构自己决定的有的局部改进只需要换 2 条边有的则需要换到 12 条边。LKH 在这一框架上做了两件关键的事第一用 α-近邻候选集压缩每一步的“换边”选择范围第二用 k-opt 链的标准搜索顺序减小重复努力。源码里链的扩展集中在 LinKernighan.c搜索主循环的逻辑可以用下面的骨架理解/* LKH 中 k-opt 链搜索的简化骨架非源码原样仅体现控制流 */ int depth 0; double gain 0; while (depth MAX_CHAIN_LENGTH) { if (TrySwap(t1, t2, gain, t1, t2)) { ApplySwap(t1, t2); depth; } else { break; } }这里的TrySwap是每次交换的收益判断MAX_CHAIN_LENGTH只是一个安全上界并不是固定 k。真正的收敛深度由候选集质量和边收益共同决定。调优的时候如果发现一条路线总在同一个局部最优附近停滞问题常常不在搜索深度而在候选集里没有包含最优路径上的关键边。2.2 α-近邻候选集LKH 把搜索空间裁剪到什么粒度LKH 的候选集机制是它区别于早期 LK 的核心改进。边长上万点时任意两个节点之间都保留“边”概念会让 k-opt 链的每一步都背 O(n) 甚至 O(n²) 的扫描开销。Helsgaun 给出的方案是对每条边计算 α 值即它相对于最小 1-树标准距离的“额外代价”。α 越小说明这条边越像最优路径里该出现的那条边。每个节点只保留 α 值最小的若干条边作为候选候选数量由CANDIDATE_SET_SIZE控制。默认值是 5在纯随机欧氏 TSP 上表现很好快递配送的坐标有街区、商圈、住宅区的聚集特征候选集调到 10~20 通常能覆盖最优路径中的大部分关键边。如果候选集调得过大比如超过 50k-opt 链会把大量精力花在低质量边上求解时间成倍增加而最优成本基本不再改善。候选集的构建发生在GenerateCandidates.c它只依赖问题坐标、距离定义和随机种子跟后续搜索过程完全解耦。这也是 LKH 的结果可以精确复现的原因同一份数据、同一个SEED、同一个CANDIDATE_SET_SIZE不管跑多少遍生成的候选集和搜索顺序全都一致。除了候选集LKH 的另一个有效跳出机制是双桥扰动。当 k-opt 链再也找不到正收益交换时说明当前解已经处在一个局部最优附近。LKH 会随机断开四条互不相邻的边用另一种方式重连形成一个结构不同的 tour再重新进入 k-opt 搜索。这个扰动幅度远小于随机重启动却能有效改变大尺度上的路径走向所以 LKH 在长链路和簇状点集上不会轻易陷入同一个坑。KICKS参数控制每次扰动的强度快递场景用默认值即可。2.3 LKH 源码文件地图与一次求解的数据流用源码调理路径规划先得知道哪些文件管哪些事。这里以 LKH-2.0.10 和 LKH-3.0.7 共有的结构为例文件职责LKHmain.c读参数文件控制一次求解流程ReadProblem.c解析 TSPLIB / CVRP 问题文件GenerateCandidates.c按 α 值生成候选边集合LinKernighan.ck-opt 链搜索主循环Makefile编译入口DIST 变量区分平台# LKH 系源码解开后的常见目录结构 # LKHmain.c # ReadProblem.c # GenerateCandidates.c # LinKernighan.c # Makefile一次求解的数据流是参数文件被LKHmain.c读入定位问题文件和输出文件ReadProblem.c把节点坐标、边权类型和约束都放进内存GenerateCandidates.c构建候选集随后LinKernighan.c对初始解反复做 k-opt 链改进陷入局部最优时用双桥扰动跳出最终结果写进TOUR_FILE。如果要把 LKH 改成实时调度服务需要关注的接缝点是ReadProblem.c的输出和 LinKernighan 的输入。在这两个模块之间插入自己的“路网距离计算”或“时间窗罚函数”比分叉改整个 LKH 更稳。TRACE_LEVEL参数控制日志粒度排查候选集和运行次数时设为 1 或 2上线批量任务时设 0。3. 快递配送建模把订单坐标和载重约束写成 LKH 能读的 TSPLIB / CVRP 文件3.1 单车纯距离用 Python 生成 EUC_2D 的 .tsp 文件先把问题降到最简一个车场、一辆车目标是总行驶距离最短。这是 TSPLKH-2 直接能解。要做的是把订单坐标写成 TSPLIB 的.tsp文件。delivery_points [ (116.3921, 39.9218), (116.4120, 39.9225), (116.4031, 39.9312), ] with open(delivery.tsp, w) as f: f.write(NAME: delivery_demo\n) f.write(TYPE: TSP\n) f.write(fDIMENSION: {len(delivery_points)}\n) f.write(EDGE_WEIGHT_TYPE: EUC_2D\n) f.write(NODE_COORD_SECTION\n) for idx, (x, y) in enumerate(delivery_points, start1): f.write(f{idx} {x:.6f} {y:.6f}\n) f.write(EOF\n)这段脚本把订单逐行写进NODE_COORD_SECTION。EUC_2D让 LKH 自己算欧氏距离并取整在城区配送尺度下误差可忽略。这里有一个必须先做的转换坐标必须是米制平面坐标。直接喂经纬度会让 α 近邻计算的“距离”失真因为经度方向的 0.001 度和纬度方向的 0.001 度在真实路程上差很多。先把订单坐标转成 Web Mercator 或 UTM再进这个脚本。配套参数文件delivery.parPROBLEM_FILE delivery.tsp TOUR_FILE delivery.tour RUNS 10 SEED 1 CANDIDATE_SET_SIZE 10终端执行./LKH delivery.par结束时会打印Best Cost路线写入delivery.tour。如果业务依赖真实路网距离而 LKH 输出的是欧氏距离不要直接在派单系统里用 cost 值用第五节里的校验脚本在路网上重算最终路线。3.2 多车带载重LKH-3 的 CVRP 输入与约束表达多车场景必须上 LKH-3问题文件从.tsp换成 CVRP 格式NAME: delivery_cvrp TYPE: CVRP DIMENSION: 11 EDGE_WEIGHT_TYPE: EUC_2D CAPACITY: 100 VEHICLES: 3 DEPOT: 1 NODE_COORD_SECTION 1 116.39 39.92 2 116.41 39.91 3 116.40 39.93 ... DEMAND_SECTION 1 0 2 18 3 25 ... EOF各字段含义和容易错的地方整理成表字段含义易错点DIMENSION车场节点数加客户节点数漏算车场会造成索引整体错位CAPACITY单车载重上限单位必须和 DEMAND_SECTION 一致VEHICLES可用车辆数LKH-3 允许少用几辆DEPOT车场节点编号必须落在合法节点范围内DEMAND_SECTION每节点需求量行顺序与坐标节点一一对应DEMAND_SECTION的第一行对应节点 1也就是车场需求量必须为 0。行数和DIMENSION对不上时LKH-3 不一定报错而是可能解出一个让容量校验失败的模型。原因是 LKH-3 把容量约束实现成软性惩罚解析越界后惩罚项仍然存在只是基准失真。所以在生成问题文件后先跑一个 Python 脚本统计DEMAND_SECTION行数。with open(delivery.vrp) as f: lines [line.strip() for line in f if line.strip()] start lines.index(DEMAND_SECTION) end lines.index(EOF) demand_rows [line.split() for line in lines[start1:end]] for line in lines: if line.startswith(DIMENSION): dim int(line.split(:)[1].strip()) break print(DEMAND 节点数:, len(demand_rows)) print(DIMENSION 声明:, dim)这个对照检查花不了几秒能省掉大部分“LKH 跑不出合理路线”的排查时间。3.3 时间窗与不对称路网软惩罚与 EXACT 矩阵的预处理快递订单常带“上午送到”“下午送到”之类的时间窗。LKH-3 原生支持 VRPTW但真实业务里时间窗大多是预约时段直接硬约束容易无解。更常用的做法是把早到或晚到折算成成本叠加到两点间的边权上def edge_cost(i, j, base_dist, eta_j, win_end_j, penalty_factor): if eta_j win_end_j: return base_dist (eta_j - win_end_j) * penalty_factor return base_distpenalty_factor的取值决定路径在“绕路避开晚到”和“直接走过去”之间的权衡。按单票利润的 2 到 5 倍设效果比较自然。设大了路径会为了准点绕很远的路设小了时间窗形同虚设。如果路网不对称比如单行道多、转弯惩罚明显LKH 的EUC_2D不再适用。改用EDGE_WEIGHT_TYPE: EXACT和EDGE_WEIGHT_SECTION把 n×n 的距离矩阵逐行写出。注意 EXACT 模式下 LKH 不会再求欧氏距离矩阵完全由你提供自己必须保证数据口径一致。矩阵规模在 1000 点以上时文件会很大可以先用对称 TSP 跑通链路再切 EXACT 做精度校准。提示坐标投影转换推荐在生成 .tsp 前用 pyproj 完成否则后面改一次数据就要重新跑整个优化流程。4. LKH 源码编译与参数调优快递路径规划的可复现命令行4.1 编译 LKH-2.0.10 与 LKH-3.0.7Makefile 里的 DIST 陷阱两个版本的源码都是 C 语言编译步骤完全一致。解开 tarball 后直接 maketar xzf LKH-3.0.7.tgz cd LKH-3.0.7 make ./LKH如果编译失败先查 Makefile 里的DIST变量。LKH 用DIST区分操作系统和编译器Linux x86_64 上通常对应LINUXmacOS 或 ARM 平台需要改到对应分支。新版本 GCC 偶尔会报-Wimplicit-function-declaration告警除非升级到了错误的 C 标准否则不需要处理。两个版本的建议LKH-2.0.10 保留给 pure TSP 兜底场景LKH-3.0.7 用于带容量、车辆数约束的快递主模型。源码里ReadProblem.c的规模差异最大LKH-3 多了解析 DEMAND 和车辆约束的分支。实际跑一个 100 点 CVRP 的命令行过程./LKH cvrp_100.par # 输出末尾Best Cost 47123.5 # 最优路线写入 cvrp_100.tour4.2 四个必调参数RUNS、SEED、CANDIDATE_SET_SIZE、TIME_LIMIT新手最容易一上来就调MAX_TRIALS和PATCHING_C但对快递配送数据真正起作用的参数就四个参数默认值快递场景建议影响RUNS1010~30独立运行次数取最优结果SEED1固定一个整数随机数种子直接决定回归可复现性CANDIDATE_SET_SIZE510~20每节点候选边数质量与耗时的平衡点TIME_LIMIT无60~300 秒硬时间预算到点返回当前最优RUNS是杠杆最大的参数。每次 RUN 从不同初始解出发最后取最优订单规模超过 200 时RUNS 从 10 提到 30 通常能再压低 1% 到 3% 的总成本代价是 3 倍耗时。批量调度系统里我会按规模分档500 单以内 RUNS102000 单以内 20再高 30 并配合 TIME_LIMIT。CANDIDATE_SET_SIZE不是越大越好。网格状路网下从 5 调到 20 有实质改善调到 100 之后结果几乎不再变化耗时却翻了好几倍。它影响的是 α-近邻候选集的宽度宽度太大时 k-opt 链会被大量低质量候选边干扰每一步的边选择都在噪声里找改进。SEED固定让整个求解过程可复现。这对物流系统很重要同一个订单快照白天晚上各跑一次路径和成本应该完全一致否则无法和客户对账。4.3 看 .log 文件判断收敛质量参数文件里加一行TRACE_LEVEL 2运行日志会打出每次 RUN 的成本变化。判断依据有两层先看Best Cost是否明显收敛再看不同 RUN 之间的最优成本抖动幅度。抖动在 0.5% 内说明候选集和搜索深度都合理抖动超过 3%优先提高 RUNS而不是加候选集。MAX_TRIALS默认 10000。如果日志里接近一半 RUN 都撞到 trial 上限才结束且成本还在下降说明问题规模需要的迭代次数超过默认值。此时把MAX_TRIALS提上去比单纯加 RUNS 效果更好因为每一轮搜索都更有机会找到更好的局部最优。4.4 排错对照结果不收敛与坐标失真的典型表现三个高频问题。坐标投影错误。直接喂经纬度给 EUC_2Dα-近邻计算的距离比例完全不对路线会在城市平面上“走斜线”。把坐标转成米制平面坐标即可。重复节点。同一小区不同楼栋坐标完全相同LKH 的候选集会扎堆在零距离边上链搜索反复换零代价边最后收敛到一个视觉上绕圈、成本却没有显著增加的路线。合并重复坐标或者人工加一个 10 米以内的偏移结果立刻正常。DEMAND_SECTION行数对不上DIMENSION。前面已经写过校验脚本运行时报错不是唯一形式更多时候是“软约束被撑坏”导致容量超限却不报错。生成问题文件的脚本里直接加断言从源头避免。assert len(nodes) dimension, f节点数 {len(nodes)} ! DIMENSION {dimension}assert这行命令放在写文件之前一旦数据源变更引起节点数量变化流程会立刻停止而不是等到 LKH 跑完才发现。5. 用 LKH 输出做路径校验、多车场拆解与动态加单优化5.1 解析 TOUR_FILE 并独立校验路线成本LKH 的TOUR_FILE输出格式不复杂。示例TOUR_SECTION 1 3 5 2 4 1 -1 EOF数字就是按顺序访问的节点编号最后回到起点。生产环境里delivery.tour的二进制或渲染代码不该直接用要先做一次独立校验def load_tour(path): result [] with open(path) as f: section False for line in f: line line.strip() if line TOUR_SECTION: section True elif not section: continue elif line in (-1, EOF): break else: result.append(int(line)) return result tour load_tour(delivery.tour) total 0.0 for i in range(1, len(tour)): a, b tour[i-1], tour[i] total real_dist(a, b) print(f实际路线长度: {total:.2f} 米)函数real_dist要在业务系统的路网距离上算不能直接拿 LKH 的欧氏距离否则校验没意义。如果total与 LKH 日志里的Cost相差超过 0.5%先排查坐标投影或EDGE_WEIGHT_TYPE是否和业务口径一致。5.2 多车场场景分片后分别跑 CVRP快递网络里多车场是常态。常见做法是先把订单按距离归属到车场形成多个子问题再对每个子问题跑一次 LKH。分片的粒度可以按“每车场 100 点以内”来拆这样单次求解跑进 3 秒以内业务上能够接受。分片的边界如果存在两个车场距离接近的交接带按“车场容量利用率”而非单纯距离来切避免一个车场分到 80 单另一个只有 20 单。并行时候给每个分片固定不同 SEED比如 1001、1002这样每个车场的优化过程互不相同但可复现全链路日志也容易排查。分片后的多个 LKH 进程可以直接用 shell 后台运行或用 xargs -P 限制并发数避免机器 CPU 被打满。5.3 动态加单用 INITIAL_TOUR_FILE 做增量优化最后这个技巧在实践里最常用当日新增几个加急订单全量重跑 30 轮 RUNS 会拖慢调度响应。LKH 支持把上一次的路径作为初始解继续搜索INITIAL_TOUR_FILE delivery.tour RUNS 5读取上一次的最优路径把新订单作为未访问节点插进去再让 LKH 少量迭代即可。这种做法能在 10~20 秒内拿到一条比全量重跑只差 1% 的路径。要注意INITIAL_TOUR_FILE里的节点集合必须包含当前问题文件的全部节点缺一个 LKH 会拒绝加载因此在读入后的第一件事是用集合比对一遍节点编号。本文还有配套的精品资源点击获取 LKH启发式算法在快递配送路径规划中的实践与调优
简介基于LKH启发式算法的快递配送路径规划与优化设计源码是一份面向物流算法工程师、运筹优化学习者及快递配送调度场景的实战项目。项目围绕Lin-Kernighan启发式算法求解大规模TSP/CVRP路径优化问题展开覆盖订单数据读取、约束校验、启发式搜索与测试对比等完整流程可帮助降低运输里程、缩短配送时间提升快递调度效率。资源包共48个文件以35个Python源码为核心并辅以XML配置、CSV订单数据、readme说明与License许可整体压缩后仅206KB目录结构清晰便于阅读和二次开发。算法侧实现了LKH搜索、禁忌搜索、2-opt/3-opt局部优化等策略同时提供bench基准脚本和测试脚本读者可替换或修改CSV中的配送点数据快速观察不同算法在路径规划上的效果差异。该资源已有293人学习适合希望系统掌握LKH算法落地、路径规划工程实现以及快递配送优化的读者参考。1. 快递配送路径规划为什么绕不开 LKH 启发式算法一个配送站一天收到三四十个订单调度员凭 GPS 直觉排出的路线通常比最优解多跑 15% 到 25%。这不是经验问题而是因为路径规划在组合优化里属于 NP 难问题人力只能在拓扑上做局部排序看不到全局交叉改进的空间。快递配送路径规划落到数学模型上就是 TSP 和带容量约束的 CVRP而 LKHLin-Kernighan-Helsgaun启发式算法是过去二十年里对这类问题最有效的公开源码求解器。它在几秒到几分钟内能在数百点上逼近最优解且稳定性远好于遗传算法和模拟退火。这篇内容适合物流系统工程师、机器人路径规划开发者以及对源码有改造需求的人把订单坐标转成 LKH 能读的文件调好参数得到可复现的路径优化结果。2. LKH 启发式算法的核心机制k-opt 链、α-近邻候选集与双桥扰动2.1 从 2-opt 到 k-opt 链为什么固定 k 值反而难写快递路径规划最底层的局部搜索是 2-opt任意选出两条不邻接的路径边交换它们的连接方式让总距离变短。2-opt 足够直观实现起来只有二三十行但它每步只能“看到”两条边。当路线被卡在需要同时断掉三四条边才能改进的局部最优时2-opt 无能为力只能依赖随机重启来碰运气。于是有了固定 k 值的 k-opt每次断开 k 条边再在所有可能的连接方式里找更优组合。固定 k 的问题在于组合爆炸。k3 时已经有几百种重连方式k5 时枚举量已经不适合在大规模路径上反复执行。Lin-Kernighan 的做法是让 k 不固定从一条边开始逐步把交换链拉长每一步都只尝试一组“可行交换”直到累计收益不再是正数。这样的链长度是问题结构自己决定的有的局部改进只需要换 2 条边有的则需要换到 12 条边。LKH 在这一框架上做了两件关键的事第一用 α-近邻候选集压缩每一步的“换边”选择范围第二用 k-opt 链的标准搜索顺序减小重复努力。源码里链的扩展集中在 LinKernighan.c搜索主循环的逻辑可以用下面的骨架理解/* LKH 中 k-opt 链搜索的简化骨架非源码原样仅体现控制流 */ int depth 0; double gain 0; while (depth MAX_CHAIN_LENGTH) { if (TrySwap(t1, t2, gain, t1, t2)) { ApplySwap(t1, t2); depth; } else { break; } }这里的TrySwap是每次交换的收益判断MAX_CHAIN_LENGTH只是一个安全上界并不是固定 k。真正的收敛深度由候选集质量和边收益共同决定。调优的时候如果发现一条路线总在同一个局部最优附近停滞问题常常不在搜索深度而在候选集里没有包含最优路径上的关键边。2.2 α-近邻候选集LKH 把搜索空间裁剪到什么粒度LKH 的候选集机制是它区别于早期 LK 的核心改进。边长上万点时任意两个节点之间都保留“边”概念会让 k-opt 链的每一步都背 O(n) 甚至 O(n²) 的扫描开销。Helsgaun 给出的方案是对每条边计算 α 值即它相对于最小 1-树标准距离的“额外代价”。α 越小说明这条边越像最优路径里该出现的那条边。每个节点只保留 α 值最小的若干条边作为候选候选数量由CANDIDATE_SET_SIZE控制。默认值是 5在纯随机欧氏 TSP 上表现很好快递配送的坐标有街区、商圈、住宅区的聚集特征候选集调到 10~20 通常能覆盖最优路径中的大部分关键边。如果候选集调得过大比如超过 50k-opt 链会把大量精力花在低质量边上求解时间成倍增加而最优成本基本不再改善。候选集的构建发生在GenerateCandidates.c它只依赖问题坐标、距离定义和随机种子跟后续搜索过程完全解耦。这也是 LKH 的结果可以精确复现的原因同一份数据、同一个SEED、同一个CANDIDATE_SET_SIZE不管跑多少遍生成的候选集和搜索顺序全都一致。除了候选集LKH 的另一个有效跳出机制是双桥扰动。当 k-opt 链再也找不到正收益交换时说明当前解已经处在一个局部最优附近。LKH 会随机断开四条互不相邻的边用另一种方式重连形成一个结构不同的 tour再重新进入 k-opt 搜索。这个扰动幅度远小于随机重启动却能有效改变大尺度上的路径走向所以 LKH 在长链路和簇状点集上不会轻易陷入同一个坑。KICKS参数控制每次扰动的强度快递场景用默认值即可。2.3 LKH 源码文件地图与一次求解的数据流用源码调理路径规划先得知道哪些文件管哪些事。这里以 LKH-2.0.10 和 LKH-3.0.7 共有的结构为例文件职责LKHmain.c读参数文件控制一次求解流程ReadProblem.c解析 TSPLIB / CVRP 问题文件GenerateCandidates.c按 α 值生成候选边集合LinKernighan.ck-opt 链搜索主循环Makefile编译入口DIST 变量区分平台# LKH 系源码解开后的常见目录结构 # LKHmain.c # ReadProblem.c # GenerateCandidates.c # LinKernighan.c # Makefile一次求解的数据流是参数文件被LKHmain.c读入定位问题文件和输出文件ReadProblem.c把节点坐标、边权类型和约束都放进内存GenerateCandidates.c构建候选集随后LinKernighan.c对初始解反复做 k-opt 链改进陷入局部最优时用双桥扰动跳出最终结果写进TOUR_FILE。如果要把 LKH 改成实时调度服务需要关注的接缝点是ReadProblem.c的输出和 LinKernighan 的输入。在这两个模块之间插入自己的“路网距离计算”或“时间窗罚函数”比分叉改整个 LKH 更稳。TRACE_LEVEL参数控制日志粒度排查候选集和运行次数时设为 1 或 2上线批量任务时设 0。3. 快递配送建模把订单坐标和载重约束写成 LKH 能读的 TSPLIB / CVRP 文件3.1 单车纯距离用 Python 生成 EUC_2D 的 .tsp 文件先把问题降到最简一个车场、一辆车目标是总行驶距离最短。这是 TSPLKH-2 直接能解。要做的是把订单坐标写成 TSPLIB 的.tsp文件。delivery_points [ (116.3921, 39.9218), (116.4120, 39.9225), (116.4031, 39.9312), ] with open(delivery.tsp, w) as f: f.write(NAME: delivery_demo\n) f.write(TYPE: TSP\n) f.write(fDIMENSION: {len(delivery_points)}\n) f.write(EDGE_WEIGHT_TYPE: EUC_2D\n) f.write(NODE_COORD_SECTION\n) for idx, (x, y) in enumerate(delivery_points, start1): f.write(f{idx} {x:.6f} {y:.6f}\n) f.write(EOF\n)这段脚本把订单逐行写进NODE_COORD_SECTION。EUC_2D让 LKH 自己算欧氏距离并取整在城区配送尺度下误差可忽略。这里有一个必须先做的转换坐标必须是米制平面坐标。直接喂经纬度会让 α 近邻计算的“距离”失真因为经度方向的 0.001 度和纬度方向的 0.001 度在真实路程上差很多。先把订单坐标转成 Web Mercator 或 UTM再进这个脚本。配套参数文件delivery.parPROBLEM_FILE delivery.tsp TOUR_FILE delivery.tour RUNS 10 SEED 1 CANDIDATE_SET_SIZE 10终端执行./LKH delivery.par结束时会打印Best Cost路线写入delivery.tour。如果业务依赖真实路网距离而 LKH 输出的是欧氏距离不要直接在派单系统里用 cost 值用第五节里的校验脚本在路网上重算最终路线。3.2 多车带载重LKH-3 的 CVRP 输入与约束表达多车场景必须上 LKH-3问题文件从.tsp换成 CVRP 格式NAME: delivery_cvrp TYPE: CVRP DIMENSION: 11 EDGE_WEIGHT_TYPE: EUC_2D CAPACITY: 100 VEHICLES: 3 DEPOT: 1 NODE_COORD_SECTION 1 116.39 39.92 2 116.41 39.91 3 116.40 39.93 ... DEMAND_SECTION 1 0 2 18 3 25 ... EOF各字段含义和容易错的地方整理成表字段含义易错点DIMENSION车场节点数加客户节点数漏算车场会造成索引整体错位CAPACITY单车载重上限单位必须和 DEMAND_SECTION 一致VEHICLES可用车辆数LKH-3 允许少用几辆DEPOT车场节点编号必须落在合法节点范围内DEMAND_SECTION每节点需求量行顺序与坐标节点一一对应DEMAND_SECTION的第一行对应节点 1也就是车场需求量必须为 0。行数和DIMENSION对不上时LKH-3 不一定报错而是可能解出一个让容量校验失败的模型。原因是 LKH-3 把容量约束实现成软性惩罚解析越界后惩罚项仍然存在只是基准失真。所以在生成问题文件后先跑一个 Python 脚本统计DEMAND_SECTION行数。with open(delivery.vrp) as f: lines [line.strip() for line in f if line.strip()] start lines.index(DEMAND_SECTION) end lines.index(EOF) demand_rows [line.split() for line in lines[start1:end]] for line in lines: if line.startswith(DIMENSION): dim int(line.split(:)[1].strip()) break print(DEMAND 节点数:, len(demand_rows)) print(DIMENSION 声明:, dim)这个对照检查花不了几秒能省掉大部分“LKH 跑不出合理路线”的排查时间。3.3 时间窗与不对称路网软惩罚与 EXACT 矩阵的预处理快递订单常带“上午送到”“下午送到”之类的时间窗。LKH-3 原生支持 VRPTW但真实业务里时间窗大多是预约时段直接硬约束容易无解。更常用的做法是把早到或晚到折算成成本叠加到两点间的边权上def edge_cost(i, j, base_dist, eta_j, win_end_j, penalty_factor): if eta_j win_end_j: return base_dist (eta_j - win_end_j) * penalty_factor return base_distpenalty_factor的取值决定路径在“绕路避开晚到”和“直接走过去”之间的权衡。按单票利润的 2 到 5 倍设效果比较自然。设大了路径会为了准点绕很远的路设小了时间窗形同虚设。如果路网不对称比如单行道多、转弯惩罚明显LKH 的EUC_2D不再适用。改用EDGE_WEIGHT_TYPE: EXACT和EDGE_WEIGHT_SECTION把 n×n 的距离矩阵逐行写出。注意 EXACT 模式下 LKH 不会再求欧氏距离矩阵完全由你提供自己必须保证数据口径一致。矩阵规模在 1000 点以上时文件会很大可以先用对称 TSP 跑通链路再切 EXACT 做精度校准。提示坐标投影转换推荐在生成 .tsp 前用 pyproj 完成否则后面改一次数据就要重新跑整个优化流程。4. LKH 源码编译与参数调优快递路径规划的可复现命令行4.1 编译 LKH-2.0.10 与 LKH-3.0.7Makefile 里的 DIST 陷阱两个版本的源码都是 C 语言编译步骤完全一致。解开 tarball 后直接 maketar xzf LKH-3.0.7.tgz cd LKH-3.0.7 make ./LKH如果编译失败先查 Makefile 里的DIST变量。LKH 用DIST区分操作系统和编译器Linux x86_64 上通常对应LINUXmacOS 或 ARM 平台需要改到对应分支。新版本 GCC 偶尔会报-Wimplicit-function-declaration告警除非升级到了错误的 C 标准否则不需要处理。两个版本的建议LKH-2.0.10 保留给 pure TSP 兜底场景LKH-3.0.7 用于带容量、车辆数约束的快递主模型。源码里ReadProblem.c的规模差异最大LKH-3 多了解析 DEMAND 和车辆约束的分支。实际跑一个 100 点 CVRP 的命令行过程./LKH cvrp_100.par # 输出末尾Best Cost 47123.5 # 最优路线写入 cvrp_100.tour4.2 四个必调参数RUNS、SEED、CANDIDATE_SET_SIZE、TIME_LIMIT新手最容易一上来就调MAX_TRIALS和PATCHING_C但对快递配送数据真正起作用的参数就四个参数默认值快递场景建议影响RUNS1010~30独立运行次数取最优结果SEED1固定一个整数随机数种子直接决定回归可复现性CANDIDATE_SET_SIZE510~20每节点候选边数质量与耗时的平衡点TIME_LIMIT无60~300 秒硬时间预算到点返回当前最优RUNS是杠杆最大的参数。每次 RUN 从不同初始解出发最后取最优订单规模超过 200 时RUNS 从 10 提到 30 通常能再压低 1% 到 3% 的总成本代价是 3 倍耗时。批量调度系统里我会按规模分档500 单以内 RUNS102000 单以内 20再高 30 并配合 TIME_LIMIT。CANDIDATE_SET_SIZE不是越大越好。网格状路网下从 5 调到 20 有实质改善调到 100 之后结果几乎不再变化耗时却翻了好几倍。它影响的是 α-近邻候选集的宽度宽度太大时 k-opt 链会被大量低质量候选边干扰每一步的边选择都在噪声里找改进。SEED固定让整个求解过程可复现。这对物流系统很重要同一个订单快照白天晚上各跑一次路径和成本应该完全一致否则无法和客户对账。4.3 看 .log 文件判断收敛质量参数文件里加一行TRACE_LEVEL 2运行日志会打出每次 RUN 的成本变化。判断依据有两层先看Best Cost是否明显收敛再看不同 RUN 之间的最优成本抖动幅度。抖动在 0.5% 内说明候选集和搜索深度都合理抖动超过 3%优先提高 RUNS而不是加候选集。MAX_TRIALS默认 10000。如果日志里接近一半 RUN 都撞到 trial 上限才结束且成本还在下降说明问题规模需要的迭代次数超过默认值。此时把MAX_TRIALS提上去比单纯加 RUNS 效果更好因为每一轮搜索都更有机会找到更好的局部最优。4.4 排错对照结果不收敛与坐标失真的典型表现三个高频问题。坐标投影错误。直接喂经纬度给 EUC_2Dα-近邻计算的距离比例完全不对路线会在城市平面上“走斜线”。把坐标转成米制平面坐标即可。重复节点。同一小区不同楼栋坐标完全相同LKH 的候选集会扎堆在零距离边上链搜索反复换零代价边最后收敛到一个视觉上绕圈、成本却没有显著增加的路线。合并重复坐标或者人工加一个 10 米以内的偏移结果立刻正常。DEMAND_SECTION行数对不上DIMENSION。前面已经写过校验脚本运行时报错不是唯一形式更多时候是“软约束被撑坏”导致容量超限却不报错。生成问题文件的脚本里直接加断言从源头避免。assert len(nodes) dimension, f节点数 {len(nodes)} ! DIMENSION {dimension}assert这行命令放在写文件之前一旦数据源变更引起节点数量变化流程会立刻停止而不是等到 LKH 跑完才发现。5. 用 LKH 输出做路径校验、多车场拆解与动态加单优化5.1 解析 TOUR_FILE 并独立校验路线成本LKH 的TOUR_FILE输出格式不复杂。示例TOUR_SECTION 1 3 5 2 4 1 -1 EOF数字就是按顺序访问的节点编号最后回到起点。生产环境里delivery.tour的二进制或渲染代码不该直接用要先做一次独立校验def load_tour(path): result [] with open(path) as f: section False for line in f: line line.strip() if line TOUR_SECTION: section True elif not section: continue elif line in (-1, EOF): break else: result.append(int(line)) return result tour load_tour(delivery.tour) total 0.0 for i in range(1, len(tour)): a, b tour[i-1], tour[i] total real_dist(a, b) print(f实际路线长度: {total:.2f} 米)函数real_dist要在业务系统的路网距离上算不能直接拿 LKH 的欧氏距离否则校验没意义。如果total与 LKH 日志里的Cost相差超过 0.5%先排查坐标投影或EDGE_WEIGHT_TYPE是否和业务口径一致。5.2 多车场场景分片后分别跑 CVRP快递网络里多车场是常态。常见做法是先把订单按距离归属到车场形成多个子问题再对每个子问题跑一次 LKH。分片的粒度可以按“每车场 100 点以内”来拆这样单次求解跑进 3 秒以内业务上能够接受。分片的边界如果存在两个车场距离接近的交接带按“车场容量利用率”而非单纯距离来切避免一个车场分到 80 单另一个只有 20 单。并行时候给每个分片固定不同 SEED比如 1001、1002这样每个车场的优化过程互不相同但可复现全链路日志也容易排查。分片后的多个 LKH 进程可以直接用 shell 后台运行或用 xargs -P 限制并发数避免机器 CPU 被打满。5.3 动态加单用 INITIAL_TOUR_FILE 做增量优化最后这个技巧在实践里最常用当日新增几个加急订单全量重跑 30 轮 RUNS 会拖慢调度响应。LKH 支持把上一次的路径作为初始解继续搜索INITIAL_TOUR_FILE delivery.tour RUNS 5读取上一次的最优路径把新订单作为未访问节点插进去再让 LKH 少量迭代即可。这种做法能在 10~20 秒内拿到一条比全量重跑只差 1% 的路径。要注意INITIAL_TOUR_FILE里的节点集合必须包含当前问题文件的全部节点缺一个 LKH 会拒绝加载因此在读入后的第一件事是用集合比对一遍节点编号。本文还有配套的精品资源点击获取