供应链AI优化：物流路径规划(VRP/TSP)

可视化演示

问题定义：老王的三轮车该往哪儿开

老王的难题，本质上是一个数学谜题。如果今天只有一辆三轮车，要送完全部小区然后回到仓库，那么问题就是"旅行商问题"（TSP）：找一条从仓库出发、经过每个小区恰好一次、最后回到仓库的最短闭合路线。数学家把这条路线叫做"哈密顿回路"。而老王的真实情况是十辆三轮车，每辆只能装下有限的包裹，这就是"车辆路径问题"（VRP）：把客户分给多辆车，让每辆车的路线各自最优，同时所有车加起来的成本最小。

TSP 和 VRP 都属于一个令数学家头疼的类别——NP 难问题。这意味着随着小区数量增加，求解时间不是线性增长，而是指数爆炸。15 个小区的路线排列比宇宙中的恒星还多，想靠穷举法把所有可能性都试一遍，超级计算机也要算到天荒地老。

这个公式说的是：在所有可能的路段组合中，挑选一组让总距离最小的路段，组成一条完整的配送回路。

约束建模：三轮车装不下整个世界

老王发现，光找最短路线还不够。他的三轮车车厢就那么大，每辆最多装 60 件包裹——这是"车辆容量约束"。有些小区便利店只在早上 8 点到 10 点收货——这是"时间窗约束"。还有一辆车一天最多跑 80 公里——这是"最大行驶距离约束"。这些约束就像给解题戴上了镣铐，让问题从"纯数学游戏"回到了"真实世界"。

在数学建模中，我们用变量 y_ik 表示"客户 i 是否由车辆 k 服务"，用 q_i 表示客户 i 的包裹重量（或件数），Q 表示车辆容量。于是容量约束写成：任何一辆车服务的所有客户需求之和，不能超过车辆容量。时间窗约束则用 a_i 和 b_i 表示客户 i 允许的最早和最晚到达时间，要求配送车到达时刻 t_i 必须落在这个区间内。

这个公式约束每一辆车的装载总量，确保不会超载。就像老王每次装车前都要数一数包裹，不能让三轮车"吃太撑"。

经典算法：从笨办法到小聪明

早期解决 VRP 靠的是"精确算法"——分支定界法把问题不断拆分成子问题，像剥洋葱一样层层搜索。这个方法在小规模问题（比如 20 个客户）上能保证找到最优解，可一旦规模变大，搜索树就会疯长成一片"算法森林"，计算机直接内存爆炸。于是工程师们转向了"启发式算法"——不求最优，只求一个够好的解。

最直观的启发式是"构造法"：比如最近邻居法，从仓库出发，每次都去最近的未访问客户，走一步看一步。这样的解通常不坏，但离最优还差得远。于是有了改进阶段的核心工具——2-opt 搜索。它检查路径中任意两条边，如果交换端点能让总距离变短，就执行交换。这就像把一条打了结的绳子解开，把交叉的两段重新拼接。

这个公式计算"交换两条边"能带来多少改进：如果 Δ > 0，说明新路径比原路径更短，应该接受这次交换。

AI求解：让神经网络学会排路线

启发式算法虽然快，但面对几十辆车、上千个客户的大规模路网时，还是显得力不从心。AI 工程师们换了个思路：与其让人工设计"改进规则"，不如让神经网络自己学会"怎么排路线"。这就是强化学习——把路径规划当作一个序列决策游戏，智能体（Agent）每走一步选择一个客户，走完一整条路线后，获得一个与总距离相关的奖励。

强化学习的核心是策略网络 π_θ(a|s)：输入当前状态 s（比如已访问的客户集合、当前位置、剩余容量），输出选择下一个客户 a 的概率。训练时，算法不断调整网络参数 θ，让"最终总距离短"的决策序列获得更高概率。奖励函数直接设置为每一步行驶距离的负值——距离越短，奖励越大，于是网络学会了"抄近道"。

这个公式表示：在策略 π_θ 的指导下，走完一整条路线所获得的"总奖励"的期望值。训练的目标就是让这个期望值尽量大。

性能评估：好与坏，用数字说话

AI 模型训练完了，老王最关心的问题来了："你凭啥说你的路线比我的好？"这就需要一套科学的性能评估体系。最核心的指标是"解质量 gap"——把算法求得的解与已知最优解（Best Known Solution, BKS）比较，看差距多少个百分点。如果最优解是 100 公里，你的算法跑了 105 公里，gap 就是 5%。

计算时间是另一个关键指标。实际配送系统中，订单是不断涌进来的，AI 必须在秒级甚至毫秒级内给出路线调整方案。研究者通常使用公开的标准算例集（如 CVRPLIB）来统一测试——这些算例有确定的客户坐标、需求量、车辆容量和已知最优解，让不同算法能公平比武。最后是鲁棒性测试：随机生成多种不同规模、不同约束组合的算例，看算法是否在大多数场景下都稳定可靠。

这个公式把"算法解距离已知最优解的差距"转化为百分比。gap 越小，说明算法越接近最优；gap 为 0 说明恰好找到了最优解。

工程落地：从算法到每日运营

算法再好，不能落地的项目都是空中楼阁。真正的工程落地，第一步是需求分析：搞清楚客户数量、车辆型号与容量、时间窗分布、道路限行等真实数据。第二步是与现有系统集成：对接订单管理系统获取实时订单，对接地图 API 获取实时路况，把算法封装成微服务。第三步是云端部署：用容器化技术部署到云服务器，按需弹性扩容，支撑每日上千台车的调度请求。

在实际部署中，工程师们还经常采用"节约算法"（Clarke-Wright Savings）作为快速生成的起手式。它的核心思想很朴素：如果你本来要派两辆车分别去服务客户 i 和客户 j，现在让一辆车同时服务他们两个，能省下多少路？省得越多，越值得把这两个客户合并到同一条线路上。

这个公式计算"把两个客户合并到一条线路"所节省的距离。s_ij 越大，i 和 j 越应该出现在同一辆车的路线上。

AI 应用场景

Python 演示

import numpy as np class TwoOptTSP:    ""“基于2-opt的TSP求解器，演示核心的路径优化方法”""     def init(self, points):        self.points = np.array(points)        self.n = len(points)        self.route = list(range(self.n))        self.dist_mat = self._calc_distance()        self.gc_count = 0     def _calc_distance(self):        diff = self.points[:, None, :] - self.points[None, :, :]        return np.sqrt((diff ** 2).sum(axis=2))     def total_dist(self, route=None):        if route is None:            route = self.route        d = 0.0        for i in range(self.n):            d += self.dist_mat[route[i], route[(i + 1) % self.n]]        return d     def two_opt_improve(self):        improved = False        for i in range(self.n - 1):            for j in range(i + 1, self.n):                i1 = (i + 1) % self.n                j1 = (j + 1) % self.n                a, b = self.route[i], self.route[i1]                c, d = self.route[j], self.route[j1]                cur = self.dist_mat[a, b] + self.dist_mat[c, d]                new = self.dist_mat[a, c] + self.dist_mat[b, d]                if new < cur - 1e-9:                    seg = self.route[i + 1:j + 1]                    self.route[i + 1:j + 1] = seg[::-1]                    improved = True        return improved     def solve(self, max_rounds=100):        initial = self.total_dist()        for _ in range(max_rounds):            if not self.two_opt_improve():                break        return self.route, self.total_dist(), initial if name == "main":    rng = np.random.default_rng(42)    pts = rng.uniform(0, 100, (20, 2))    solver = TwoOptTSP(pts)    route, best, initial = solver.solve()    print(“初始距离：{:.2f}”.format(initial))    print(“优化后距离：{:.2f}”.format(best))    print(“提升比例：{:.1f}%”.format((1 - best / initial) * 100))

常见误区

面试题