仓内拣货路径优化：从订单分批到TSP建模与2-opt实现

简介：2020年MathorCup高校数学建模挑战赛C题仓内拣货优化问题的完整赛题方案，以PDF形式封装，共1个文件，文件大小约2.96MB。资源面向数学建模参赛者、物流仓储优化研究者及运筹学课程学习者，围绕订单拣货中的距离计算、任务分配、路线规划与复核台效率提升展开，系统呈现了基于曼哈顿距离的货格与复核台间距模型、结合互换法/倒位法/易位法的模拟退火优化路线、贪心算法均衡复核台负载、畅销品分区摆放与货架交错策略等核心内容。方案完整覆盖问题一至问题六的建模思路、公式推导与关键数值结论，例如任务单T0001最短出库时间732.867秒、49份任务单最短出库时间5540.87秒及各复核台利用率区间，便于读者对照验算、复现模型并拓展到实际仓储调度场景。目前已有1790人浏览学习，适合作为数学建模竞赛备赛、仓库拣货问题仿真以及物流优化项目设计的参考资料。

1. 这道竞赛题，本质是给仓库拣货员排一条“不回头”的路

打开 2020 年 MathorCup 高校数学建模挑战赛的 C 题，第一眼看到的往往是成百上千行的订单明细和货位坐标。很多队伍以为它考的是“启发式算法背得熟不熟”，实际考的是把现实问题翻译成路径优化模型的能力。简单说，仓内拣货优化要做的是：给定仓库平面布局和订单内容，为拣货员或 AGV 设计一条从出发点到各货位、再回到打包点的行走方案，让所有订单的总行走距离最短。这个题能帮你解决的不只是竞赛拿奖，还有仓储管理里最容易被低估的“拣货劳动成本”。适合读这篇笔记的人：准备数学建模竞赛的学生、做 WMS 或物流仿真的开发者，以及想给仓库调度模块加一个优化引擎的从业者。

2. 先过数据建模关：订单、商品、货位怎么变成一张距离矩阵

2.1 三个输入表如何合并：从订单明细到“每个订单的货位集合”

拿到赛题先别急着写模型，先把数据结构理顺。这种优化题通常给你三个信息：订单明细（哪张订单买了哪些 SKU）、库存表（每个 SKU 放在哪个货位、货位的 x/y 坐标）、仓库平面图（出发点和过道布局）。第一步就是把订单和库存按 SKU 关联起来，得到“每个订单需要访问哪些货位”。我一般会先把两个 CSV 读进来，用 Pandas 做一次 left join：

import pandas as pd # orders.csv: order_id, sku_id # inventory.csv: sku_id, x, y orders = pd.read_csv("orders.csv", dtype={"order_id": str, "sku_id": str}) inventory = pd.read_csv("inventory.csv", dtype={"sku_id": str}) # 订单明细关联货位坐标，缺失的 sku 会暴露数据问题 detail = orders.merge(inventory, on="sku_id", how="left") print(detail.isna().sum())

逻辑说明：合并之后每一行就是“某订单需要去某货位”，如果 isna 统计出现非零值，说明库存表里有 SKU 缺失，这是后续建模最容易翻车的点。参数说明：dtype 强制把 ID 当字符串读，避免订单号长数字被读成科学计数法；how="left" 保证订单里出现但库存表缺失的 SKU 不会被静默丢弃，而是留下 NaN 方便排查。

接下来要把明细转成“订单 -> 货位坐标数组”的结构，后面做距离矩阵和批次划分都要用这个结构：

order_positions = {} for order_id, g in detail.groupby("order_id"): coords = g[["x", "y"]].dropna().values if len(coords) > 0: order_positions[order_id] = coords

逻辑说明：order_positions 是一个字典，键是订单号，值是一个 (N, 2) 的 numpy 数组，表示这个订单要访问的 N 个货位。dropna 的作用是过滤掉前面 join 失败产生的空货位，避免后面数值运算报 NaN 错误。参数说明：如果同一个 SKU 在库存表里出现多行（一个商品放多个货位），这里的 groupby 会把所有坐标都算进去，意味着拣货员可能被要求访问同一个 SKU 的多个货位，属于“多货位”建模，实际项目里需要根据自己的规则决定是取最近货位还是全部访问。

2.2 距离度量选欧氏还是曼哈顿：仓库过道对路径的真实约束

货位坐标到手后，最核心的问题来了：两个货位之间的距离怎么算。常见做法有两种，欧氏距离和曼哈顿距离，但它们对仓库场景的拟合程度差别很大。货架通常是横平竖直排列的，拣货员要在通道里走直线，不太可能斜穿货架。所以如果赛题没有提供额外的通道网络，曼哈顿距离比欧氏距离更贴近真实行走距离；如果题目给的是开放场地或明确允许直线行走，再用欧氏距离。

我一般先默认曼哈顿距离跑通全流程，最后如果题目有通道约束，再替换成最短路矩阵。距离矩阵的计算用向量化实现，否则几千个货位两两算距离会卡到怀疑人生：

import numpy as np def build_distance_fast(pos, metric="manhattan"): # pos: (n, 2) 数组，每行是一个货位坐标 diff = pos[:, None, :] - pos[None, :, :] if metric == "euclidean": return np.sqrt((diff ** 2).sum(axis=-1)) return np.abs(diff).sum(axis=-1) d = build_distance_fast(order_positions["OD001"], "manhattan")

逻辑说明：用 numpy 广播把 (n, 2) 扩展成 (n, n, 2)，一次算出所有点对差值，再按轴求和。这样避免两层 Python for 循环，两千个点以内都是毫秒级。参数说明：metric 决定距离类型；注意内存占用，n=2000 时距离矩阵是 2000×2000 的 float64 数组，约 32MB，跑到一万个货位时就是 800MB，务必分批或降精度。

3. 核心建模：拣货路径的 TSP 形式化与两段式求解框架

3.1 一个批次内的路径问题为什么是 TSP：目标函数与三个约束

当一批订单被分给同一个拣货员之后，他要从出发点出发，依次访问这个批次涉及的货位，再回到出发点。这个子问题本身就是一个典型的 TSP（旅行商问题）：给定出发点和一个货位集合，找一条访问所有货位一次且回到起点的最短闭合路径。注意这里的节点数是“该批次涉及的货位去重后的数量”，不是订单数量，更不是商品件数。多个订单都买同一个货位的商品，拣货员只需要走到那个货位一次，一次拣完。

形式化地说，设节点 0 为出发点，其余节点是货位，目标函数是路径上所有相邻节点距离之和，约束有三条：每个货位恰好访问一次；路径从 0 出发并回到 0；整条路径是一个连通环，不能出现多个分离的小环。第三条约束在数学建模里要写成子环路消除约束（常见的是 MTZ 约束），但在启发式算法实现里，只要用“一条排列 + 首尾相连”的方式构路，自然就不会产生子环。

3.2 初始解 + 2-opt 改进：用几十行 Python 逼近最优解

TSP 是 NP-hard 的，赛题规模下指望精确求解不现实，最常见且稳妥的方案是“最近邻构造初始解 + 2-opt 局部搜索”。最近邻的思路很直接：从出发点开始，每次都去当前还没访问且距离最近的货位，直到全部走完。它给出的解通常不是最优，但它能在 O(n²) 内给你一条合理路径，作为 2-opt 的起点。2-opt 的核心思想是：如果路径上有两条边交叉或绕远，就把中间那段路径反向，形成一条更短的路径，反复尝试直到没有改进。

def nearest_neighbor(d, start=0): n = len(d) unvisited = set(range(n)) route = [start] unvisited.remove(start) cur = start while unvisited: nxt = min(unvisited, key=lambda j: d[cur][j]) route.append(nxt) unvisited.remove(nxt) cur = nxt return route def two_opt(route, d): n = len(route) improved = True while improved: improved = False for i in range(0, n - 2): for j in range(i + 1, n): if j - i == 1: continue a, b, c, e = route[i], route[i + 1], route[j], route[(j + 1) % n] # 反转 i+1 到 j 段，新旧边的距离差为 delta delta = d[a][c] + d[b][e] - d[a][b] - d[c][e] if delta < -1e-9: route[i + 1:j + 1] = reversed(route[i + 1:j + 1]) improved = True return route def route_distance(route, d): return sum(d[route[i]][route[(i + 1) % len(route)]] for i in range(len(route)))

逻辑说明：nearest_neighbor 用 set 管理未访问节点，每次用 min 按距离挑最近点，复杂度是 O(n²)。two_opt 的核心是 delta 公式：反转一段路径后，只有两对边发生变化，如果新边总长比旧边短就执行反转。参数说明：j 从 i+1 开始，j - i == 1 时反转长度为 0 没有意义，跳过；判断阈值用 -1e-9 是为了避免浮点数精度导致无效更新；route 最后隐式回到起点，不需要在列表里重复写节点 0。

3.3 订单分批：容量约束下的批次划分怎么写

单张订单的路径问题解决了，接下来是更难的订单分批：把哪些订单放进同一批，让拣货员一次走完？这个问题的组合爆炸比 TSP 更严重，竞赛阶段几乎所有队伍都会用两段式贪心：先分批，再逐批优化路径。我见过不少队伍把 capacity 理解成“最多几个订单”，其实题目更多时候限制的是“一次最多拣多少件商品”或“最多能访问多少个货位”。分批代码要把容量单位搞清楚。

def greedy_batch(order_positions, capacity): # capacity: 一批次最多包含的商品件数（或货位数，按题目定义） items = [] for oid, pos in order_positions.items(): items.append((oid, len(pos), pos.mean(axis=0))) # 按订单质心到原点的曼哈顿距离排序，让空间上相近的订单优先凑批 items.sort(key=lambda x: x[2][0] + x[2][1]) batches, cur, cur_load = [], [], 0 for oid, cnt, _ in items: if cur and cur_load + cnt > capacity: batches.append(cur) cur, cur_load = [], 0 cur.append(oid) cur_load += cnt if cur: batches.append(cur) return batches

逻辑说明：先算每张订单的货位质心，按质心的 x+y 排序，让空间位置接近的订单尽量进入同一批。这样批次内部的货位分布紧凑，后续 TSP 的路径不会跨越大半个仓库。参数说明：capacity 是硬约束，不能超；排序键可以换成欧氏距离、按巷道等，但“空间相近优先”是基本原则。这里的贪心不能保证全局最优，但能稳定拿到一个不差的可行解，后续如果用遗传算法做批次优化，这也是一个非常好的初始个体。

4. 仓内拣货优化的四个常见翻车点与排查手册

4.1 现象一：优化后的总距离比“一单一拣”还远

有一类结果特别打击人：辛辛苦苦把订单分批、跑完 2-opt，结果总距离比每张订单单独拣还长。我排查下来，原因通常出在三个地方。第一，距离矩阵里混入了重复货位，两个订单访问同一个货位却被当成两个节点，路径被迫绕回去；第二，分批只看容量不看位置，把仓库两头各一个偏远订单硬凑进同一批，拣货员要多走一整个来回；第三，最近邻初始解选错起点，导致 2-opt 陷入一个局部很差的山谷。

解决方式也很直接：先检查 order_positions 里有没有重复坐标，按 (x, y) 去重；然后把分批排序从“按订单编号”改成“按订单质心距离”，让空间相近的订单优先合批；最后给最近邻换不同的起点跑几次，取总距离最短的作为初始解。多次随机启动是最容易被忽略的免费优化，竞赛和项目里都值得养成习惯。

4.2 现象二：几千个货位时程序卡死，2-opt 变成“跑不完的循环”

两段式框架跑小数据很快，但数据一放大就露馅。2-opt 的全邻域枚举是 O(n²) 的，一层改进循环往往要扫几十轮，n 超过五百就开始体感卡顿，超过两千基本没法等。这不是算法错了，是复杂度上去了。

解决思路有三个。第一，控制批次规模，把 capacity 调小，让每个批次的货位节点数限制在一百以内，几千个货位分散到几十个批次里，每个批次都是独立的小 TSP；第二，给 two_opt 加最大迭代轮数，连续五轮没有改进就提前退出，不要等它“完善”到最后一轮；第三，把内层 delta 计算向量化，用 numpy 批量算所有候选反转的收益，而不是在 Python 里逐对 if 判断。我一般会在代码里同时保留“全部改进”和“最多改进 200 次”两种模式，数据大了用后者。

4.3 现象三：路径图画出来很漂亮，但实际拣货装不下

输出路径和批次方案看起来合理，但一对照题目就发现，某个批次里商品总件数超过了拣货车容量。这种翻车最隐蔽是因为它不会报错——代码跑通了，结果也能看，但放在真实场景里根本不可行。原因在于 capacity 的单位搞错了，把“货位数”当成“商品件数”。一个订单买了 20 件同一个商品，只访问一个货位，但容量消耗是 20 件而不是 1 次访问。

解决方式是把分批逻辑里的 cnt 从 len(pos) 改成订单商品总件数，分批代码里的 capacity 相应改成“最大可拣件数”。如果你的模型里同时有“件数上限”和“货位上限”，那就选更严格的那个作为容量。血泪经验是：比赛题目给的容量约束，一定要先在读数据阶段确认单位，再看代码里用的是哪个字段。

4.4 现象四：同一次运行两次结果不一样，论文里没法复现

启发式算法里最常见的“玄学”就是结果不可复现：上午跑出 5800 米，下午变成 6200 米，worse 的是代码里根本找不到哪里用了随机数。问题往往出在三个地方：用了 Python 的 set 或 dict 做遍历，迭代顺序不稳定；没有固定 numpy 随机种子，而某个初始化步骤隐式调用了随机函数；或者分批排序依赖了原始 CSV 的行序。

解决方式很简单但容易被忽略：程序入口固定 np.random.seed(42)；所有集合结构统一换成 list 并显式排序；把整个求解流程封装成 run(seed, capacity, metric) 函数，每次返回总距离和参数快照。你在竞赛论文里写“算法运行 10 次取最优”，就一定需要这样的可复现框架，否则评审质疑结果时你连同一组数字都拿不出来。

5. 把结果做稳：参数调节、下界验证与求解器选型

5.1 什么时候自己写启发式，什么时候交给求解器

很多队伍看到 TSP 第一反应是调 MATLAB 自带的函数，或者安装 OR-Tools。但比赛现场未必能联网装包，就算能装，环境版本冲突也足够让人心态崩掉。我一般按规模做选型：货位节点少于 15 个时，直接全排列穷举，结果最优且实现最简单；节点在 20 到 200 之间，最近邻 + 2-opt 或再加一个模拟退火就够用；节点几千甚至上万时，建议先做聚类拆分成子问题，再对每个子问题用启发式，硬上精确求解器反而不划算。

自写启发式的另一个好处是能在论文里展示完整的算法流程和参数分析。直接用现成黑匣子求解器，冲刺阶段确实省时间，但答辨时很难说出“为什么这个参数取 200”。我倾向于在代码里留一个 solver 参数，默认用自写启发式，如果环境里能装 OR-Tools 再切换过去做对照实验。

5.2 用下界和多次实验验证“我的解到底好在哪”

拿到一个解之后，怎么判断它有没有继续优化的空间？一个实用技巧是算下界。TSP 最优路径删除任意一条边后都会变成一棵生成树，所以最小生成树（MST）的权值是 TSP 最优解的一个下界。如果你的启发式结果比 MST 权值高 5%，那基本可以认为解已经很接近最优；如果高出 30%，说明算法还有明显改进空间。

from scipy.sparse.csgraph import minimum_spanning_tree def mst_lower_bound(dist): mst = minimum_spanning_tree(dist) return mst.toarray().sum() base = 7840.0 # 比如“逐单拣货”的总距离 optimized = 5630.0 mst_lb = mst_lower_bound(build_distance_fast(pos_array, "manhattan")) improvement = (base - optimized) / base gap_to_lb = (optimized - mst_lb) / optimized print(f"改进率: {improvement:.2%}, 与下界的差距: {gap_to_lb:.2%}")

逻辑说明：minimum_spanning_tree 返回一个稀疏矩阵，用 toarray().sum() 得到生成树总权值。gap_to_lb 越小说明解越接近理论上限附近的水平。参数说明：这个下界只适用于单个批次的 TSP，多批次场景下要分别计算所有批次的下界之和再对比。

5.3 三个必须保留的参数痕迹：种子、迭代上限、距离类型

无论竞赛还是工程项目，最终提交的代码里都要把算法参数“显性化”，不要写死。我每次跑实验都会在代码开头定义一个 params 字典，把 seed、capacity、metric、max_iter、restarts 全部放进去，然后保存到 JSON。一来方便做参数敏感性分析，二来论文里可以放一张参数表说明每个值的选取理由。

params = { "seed": 42, "capacity": 30, "metric": "manhattan", "max_iter": 200, "restarts": 10, "distance_unit": "meter" }

逻辑说明：restarts 对应多次随机启动次数，10 次是比较划算的选择，超过之后收益递减。max_iter 是 2-opt 的最大迭代轮数，这个参数直接决定运行时间上限。参数说明：如果换了数据集，capacity 要按商品密度重新标定；metric 切换成 euclidean 时，结果会整体变小，不要拿它跟曼哈顿距离的结果直接对比。

6. 一个能立刻上手的技巧：把上文代码拼成最小可运行流程

到这里，前面所有模块其实可以拼成一个最小的可运行流程。我每次接到新的拣货优化问题，都会先把它跑通，确认数据没有低级错误，再往里面加复杂算法。这个流程的输入只有三个东西：订单明细、库存坐标表、一个 capacity 参数，输出是总距离和每批路径。

import numpy as np np.random.seed(params["seed"]) start = np.array([0.0, 0.0]) # 假设出发点在原点 total_distance = 0.0 for batch in greedy_batch(order_positions, params["capacity"]): pos = np.vstack([start] + [order_positions[oid] for oid in batch]) dist = build_distance_fast(pos, params["metric"]) route = two_opt(nearest_neighbor(dist), dist) total_distance += route_distance(route, dist) print("total_distance:", total_distance)

逻辑说明：每个批次都把起点 0 拼在货位坐标数组最前面，距离矩阵的第 0 行第 0 列就是起点到各货位的距离。two_opt 的输入是最近邻给出的初始 route，输出是局部最优路径。参数说明：capacity 和 metric 通过 params 字典传入，想要报告多次运行结果就再包一层循环。

这个最小流程最大的价值是当基线。后续无论你想换成遗传算法分批、改用最短路矩阵、还是接入真实仓库的墙障数据，都不需要重写数据加载部分，只需要替换中间的一两个函数。我第一次做这类赛题时，把八成时间花在数据清洗上，后来意识到真正决定结果质量的分水岭是容量约束的理解和距离度量的选择，算法反而排在第三位。到现在做仓储优化项目，我还是会先把这个基线跑通，用它的结果验证新方案到底改进了多少。希望帮到你。

本文还有配套的精品资源，点击获取