UPS背后的ORION系统，正是在解决学术界所称的"车辆路径问题"（Vehicle Routing Problem，简称VRP）。在当今竞争激烈的商业环境中，一辆配送车辆的行驶路线不仅决定了运营成本的高低，还直接影响着顾客满意度、环境足迹乃至整个企业的市场竞争力。从电商的次日达到外卖平台的热餐送达，从医疗物资的应急调配到城市垃圾的定时收集，VRP已经无声地渗透到现代城市生活的每个角落。
从旅行商到车队管理：VRP的起源与基础理论
旅行商问题的扩展
现代城市物流路径优化研究可以追溯到1959年。当时，数学家George Dantzig和John Ramser在权威期刊Management Science上发表了题为"The Truck Dispatching Problem"的开创性论文，正式提出了车辆路径问题。
这项研究的背景是为一家炼油厂优化汽油运输卡车的配送路线，将散装汽油从一个中心油库运往多个服务站。论文不仅定义了问题——即如何为一组车辆规划最优的路线集合以服务给定的客户群——还提出了首个求解该问题的算法方法。这篇论文被广泛认为是VRP作为一个独立研究领域在运筹学中诞生的标志。
而VRP的提出并非凭空产生，它与更早被研究的旅行商问题（Traveling Salesman Problem, TSP）有着紧密的联系。旅行商问题寻求一条访问每个给定城市（客户点）一次且仅一次，并最终返回起点的最短回路。TSP的研究历史可以追溯到19世纪的数学家Hamilton和Kirkman，并在20世纪30年代由Menger、Whitney等学者在维也纳和哈佛等地进行了数学上的探讨。
VRP与TSP的关键区别在于，TSP通常只考虑单个"销售员"（或车辆）的单一路径，而VRP则需要为一个车队规划多条路径，并需要考虑车辆容量、服务时间等更复杂的约束。VRP通常被视为TSP的一般化形式，是对经典TSP框架的一种必要扩展，其直接动因来自于解决现实世界物流配送中的实际挑战。
VRP旨在为一组车辆规划最佳行驶路线，以便在满足客户需求和各种运营约束的前提下，高效地完成货物配送或服务提供。其核心目标通常是最小化总成本，这可以体现为运输距离、行驶时间、车辆使用数量或综合运营费用。
VRP被证明是NP难（NP-hard）问题，这意味着随着问题规模（客户数量）的增加，找到最优解所需的计算时间会呈指数级增长。这一固有的计算复杂性是推动VRP算法不断演进的核心动力，也是学界和业界长期关注这一问题的根本原因。
从精确计算到效率提升
"在理论上，理论和实践是没有区别的；但在实践中，它们有区别。"当我与一位资深物流规划师讨论VRP问题时，他引用这句名言来形容VRP的求解困境。虽然数学上可以精确定义最优路径，但现实中，我们常常需要在有限时间内找到"足够好"的解决方案。这种理论与实践的张力，恰恰驱动了VRP求解算法在过去六十年中的三次重大演进。
初期的VRP研究者们，受到严谨的数学训练，自然而然地追求问题的最优解。20世纪60至80年代，各种精确算法被提出并不断完善。其中，分支定界法（Branch-and-Bound）成为最早应用于VRP的主流精确算法之一。这种算法的核心思想非常直观：通过系统地搜索所有可能的解空间，并利用上下界计算"剪枝"掉那些不可能包含最优解的分支，从而提高搜索效率。Christofides和Eilon在1969年的工作奠定了这一方向的基础，随后Christofides团队在80年代初引入的k-度中心树和q-路径概念进一步提升了算法性能。
同时，研究者们也尝试将VRP表述为各种整数规划模型，如车辆流模型（跟踪车辆如何在网络中移动）、集合划分模型（从所有可能路径中选择最优组合）以及商品流模型（跟踪货物在网络中的流动）。这些数学模型不仅在理论上优雅，也为商业优化软件的应用提供了基础。
然而，精确算法很快遭遇了"维度灾难"—随着客户数量的增加，计算复杂度呈指数级增长。即使到了21世纪初，最先进的精确算法也只能在可接受的时间内求解约100个客户点的问题。而现实中，一个普通的配送中心可能需要服务数百甚至上千个客户点。对于UPS或亚马逊这样的物流巨头，其日常操作涉及的客户点数量更是天文数字。这种巨大的差距促使研究者们转向了第二条道路—启发式算法。
启发式算法代表了一种实用主义的转向：放弃追求绝对最优，而是在可接受的时间内寻找"足够好"的解决方案。这类算法往往基于人类解决问题的直觉和经验，设计简单却往往出奇地有效。其中最具代表性的当属Clarke和Wright在1964年提出的节约算法（Savings Algorithm）。这个算法的思路如此简单，以至于可以用几句话说清楚：起初假设每个客户都由一辆专车服务，然后尝试合并路线，每次选择能节省最多距离的合并操作。尽管简单，这个算法却能在短时间内生成质量相当不错的路线方案，至今仍被广泛应用于教学和实践。
此外，扫描算法（Sweep Algorithm）和先聚类后路径法（Cluster-First, Route-Second）也成为那个时代的经典方法。扫描算法以仓库为中心，像雷达扫描一样按角度顺序将客户分配给车辆；而聚类-路径法则先将地理位置相近的客户分组，再为每组客户规划一条路径。这些方法虽然在数学上无法保证最优，但其速度快、易于实现和理解的特性使其在实际应用中大放异彩。
然而，经典启发式算法也存在明显的局限性—它们容易陷入"局部最优"陷阱。想象一下，当你在山区徒步寻找最高峰时，如果只允许自己向上走，很可能会被困在一个小山头上，而错过远处的真正高峰。这正是传统启发式算法的困境。
为了解决这个问题，20世纪80年代末至90年代初，一波受自然现象启发的新型算法（通称"元启发式算法"）开始兴起。这些算法通常包含一些机制，允许在搜索过程中暂时接受"看似更差"的解，从而有机会跳出局部最优，发现全局更优的解决方案。
元启发式算法代表了一种更具全局眼光的思维模式——有时候必须先苦后甜，才能获得更大的回报。以禁忌搜索为例，它模拟了我们学习避免重复错误的过程。想象一位购物者在城市中寻找最佳购物路线，她会记下已经尝试过的路线（哪怕是看似不错的路线），暂时"禁止"自己再走这些路，从而强迫自己探索新的可能性。这种策略所体现的不再是简单的"就近原则"，而是一种更复杂的探索与利用平衡。
模拟退火算法则借鉴了金属冶炼的原理，以一种更为哲学的方式处理决策问题。在算法的早期阶段（高温状态），系统愿意以较大概率接受看似较差的方案，类似于我们在面对新环境时保持开放心态，愿意尝试各种可能性。随着搜索的深入（温度降低），系统变得越来越"挑剔"，更多地专注于优化已发现的有希望区域。这种从"探索"到"精炼"的渐进转变，反映了成熟决策者的思维方式。
而遗传算法和蚁群优化则分别模拟了生物进化和集体智能，它们不再局限于单一解的改进，而是维护和发展一个多样化的"解的生态系统"，通过竞争、协作和信息共享来逐步接近最优解。这种集体智能的思路，已经超越了传统意义上的优化算法，向更广泛的组织学习和知识管理延伸。
（第一部分结束，第二部分会讨论AI介入后的算法迭代和UPS落地案例，敬请期待）
不被数据"窥伺",只被算法"理解"-MIT用数字 技术为卡车司机"代言",重塑劳资关系新样本