SVRPBench：MBZUAI研究团队打造的首个真实场景随机车辆路径规划基准测试平台

在物流和快递行业中，如何高效地规划送货路线一直是一个关键挑战。想象一下，你需要安排一辆送货车在一天内完成城市中数十个甚至上百个包裹的派送，还要考虑各种可能出现的意外情况：早高峰和晚高峰的交通拥堵、随机发生的交通事故、不同客户对送货时间的特殊要求。这些不确定因素给路线规划带来了巨大挑战。

来自阿联酋穆罕默德·本·扎耶德人工智能大学(MBZUAI)的研究团队，包括Ahmed Heakl、Yahia Salaheldin Shaaban、Martin Takác、Salem Lahlou和Zangir Iklassov，于2025年5月发表了一项重要研究成果。这篇题为《SVRPBench: A Realistic Benchmark for Stochastic Vehicle Routing Problem》的论文提出了首个开源的随机车辆路径问题(SVRP)基准测试平台，旨在模拟真实世界的物流配送环境。有兴趣深入了解的读者可以通过GitHub（https://github.com/yehias21/vrp-benchmarks）和Hugging Face（https://huggingface.co/datasets/MBZUAI/svrp-bench）获取完整代码和数据集。

传统的车辆路径问题（VRP）基准测试通常假设所有条件都是静态且理想化的：车辆按照固定速度行驶，客户总是在预定时间段内可用，路况永远保持稳定。然而，这些假设与现实世界相去甚远。真实的物流配送面临着各种不确定性：交通拥堵会随时间变化（早晚高峰尤为严重），路上可能突发交通事故，不同类型的客户（居民区和商业区）有着完全不同的时间窗口需求。

这就是SVRPBench的创新所在。它不再局限于静态、理想化的环境，而是精心模拟了城市规模的随机动态配送条件。该平台包含500多个测试实例，每个实例最多可包含1000个客户点，并模拟了时间依赖的交通拥堵、符合对数正态分布的延误、概率性交通事故，以及基于经验数据构建的居民和商业客户时间窗口分布。

这支研究团队不仅开发了数据集，还提供了全面的评估工具包，用于测试各类求解算法的性能。他们的实验结果令人深思：当面对分布偏移（即测试条件与训练条件不同）时，最先进的强化学习求解器如POMO和AM的性能下降超过20%，而传统的经典方法和元启发式方法却表现出更强的稳健性。

这个发现对物流行业有着重要启示：虽然人工智能方法在理想条件下表现优异，但在充满不确定性的真实世界中，传统算法可能具有更好的适应性。SVRPBench为研究者们提供了一个测试平台，挑战他们设计出能够适应真实世界不确定性的求解器，而不仅仅是在理想化的环境中表现良好。

一、真实世界的不确定性建模

想象你正在使用导航软件规划一次城市旅行。通常情况下，导航软件会告诉你从A点到B点需要多长时间，但我们都知道，实际驾驶时间可能会因为各种因素而波动：早晚高峰时段路上车辆增多导致的拥堵、突发的交通事故、路面施工等。SVRPBench正是抓住了这一现实生活中的不确定性，并将其系统化地融入到了路径规划基准测试中。

研究团队基于现实世界的经验数据和理论文献，精心设计了四种关键的不确定性因素：时间依赖的交通拥堵、随机的行驶时间延误、事故引起的道路中断，以及客户特定的时间窗口分布。

首先，研究团队构建了一个全面的行驶时间模型。想象一下，从地点a到地点b的行驶时间不再是一个固定值，而是由多个因素共同决定的：基本行驶时间（由距离和平均速度决定）、时间相关的拥堵因子、随机延误，以及可能发生的交通事故造成的额外延误。这个模型用数学表达式可以写为：

T(a, b, t) = D(a,b)/V + B(a, b, t) · R(t) + Iaccidents(t) · Daccident

其中，D(a,b)是欧几里得距离，V是平均道路速度。拥堵因子B(a, b, t)通过两个关键模式进行建模：一是时间模式，模拟早高峰（上午8点左右）和晚高峰（下午5点左右）的交通高峰；二是距离衰减模式，反映了较长行程更容易遇到拥堵的经验事实。

就像现实生活中的交通延误往往不是均匀分布的一样（小延误比大延误更常见），研究团队使用对数正态分布来模拟随机延误R(t)。这种分布能够很好地捕捉到交通延误的偏斜和突发性特点。在高峰时段，不仅平均延误会增加，延误的变异性也会上升，这与我们的日常经验非常吻合。

交通事故则是使用时间非齐次泊松过程进行建模的。简单来说，这意味着事故发生的概率不是恒定的，而是随时间变化的，特别是在夜间（晚上9点左右）风险会上升，这符合疲劳驾驶和醉酒驾驶增加导致的夜间事故高发的现实情况。每次事故可能导致的延误时间从0.5小时到2小时不等，这与行业报告中的事故清理时间相符。

对于客户时间窗口的建模，研究团队区分了居民客户和商业客户的不同模式。居民客户的送货时间窗口遵循双峰高斯混合模型，反映了上午时段（平均在上午8:00，标准差为90分钟）和晚上时段（平均在晚上7:00，标准差为120分钟）两个高峰期，这与联邦快递和挪威Bring等包裹服务公司的实际配送选项一致。而商业客户则遵循单峰高斯模型，集中在下午1:00左右（标准差为60分钟），窗口持续时间通常不超过120分钟，反映了标准的工作时间和商业配送规范。

这种概率性的时间窗口模型鼓励算法在各种服务约束之间寻找平衡，模拟了最后一公里配送系统中的现实调度权衡。就像真实世界的送货司机需要根据不同客户的时间偏好来灵活安排行程一样，算法也需要适应这种多样性和不确定性。

二、数据集构建流水线

为了使研究人员能够进行可扩展和可重复的实验，研究团队开发了一个统一的流水线，用于生成多样化、约束丰富的SVRP实例。这个流水线集成了客户行为模型、交通模式、空间布局和路由约束，以产生适合评估各类求解算法的问题场景。

首先是位置采样环节。研究团队根据客户总数（从10、20、100、500到1000不等）计算城市数量（通常为客户数除以50，至少为1）。为了模拟城市群之间的空间分离，他们应用K-均值聚类生成尽可能相互远离的城市中心，然后使用二维高斯分布在每个城市中心周围采样客户位置。这就像在地图上先确定几个主要城市的位置，然后在每个城市周围按照一定的概率分布放置客户点。

在需求分配环节，每个客户被随机分配一个离散需求值（从1到最大需求值之间）。车辆数量和容量基于客户总需求计算，以确保跨实例规模的平衡可行性。这类似于根据一天内的总包裹量来决定需要派出多少辆车以及每辆车的载重能力。

客户时间窗口的分配按照前面描述的随机模型进行，区分居民客户和商业客户的不同时间偏好。

接下来，研究团队计算所有位置对之间的完整行驶时间矩阵T(a, b, t)，结合确定性基本时间、时间依赖的拥堵模式、对数正态随机变异和随机事故延误。这捕捉了城市交通系统的非线性、时变特性。

在约束集成环节，该平台支持单仓库和多仓库配置。在多仓库设置中，仓库可以随机放置或与城市中心对齐（每个城市一个）。系统使用同质车队，并根据需求和容量配置车辆数量。所有客户时间窗口的采样确保在指定的行驶时间模型下具有可行性。

每个生成的实例都经过自动验证，以确保在容量和时间约束下的可行性。对于CVRP（带容量约束的车辆路径问题），系统验证总车辆容量（车辆数量×每辆车容量）是否超过所有客户需求之和，确保存在覆盖所有客户的可行路线。对于TWVRP（带时间窗口的车辆路径问题），系统通过将时间轴分箱并累积每个箱的客户需求来构建时间窗口需求直方图。然后识别需求高峰箱，并确保车队容量足以服务这种最坏情况需求。这提供了一个保守保证，即即使在时间需求集中的情况下，仍然可能存在可行的调度方案。不可行的实例（例如，无法到达的节点或不兼容的时间窗口）会被过滤或重新生成。

为了验证空间采样策略的真实性，研究团队将合成路由实例与真实世界城市的卫星图像进行了视觉比较。生成的布局成功模仿了关键结构模式：密歇根的网格状结构、米兰的放射状结构和阿布扎比的分散式结构，证明了流水线能够模拟多样的城市形态，这对于在地理上有根据的场景中评估路由算法至关重要。

三、评估协议和性能指标

为了确保公平、严谨和可重复的比较，研究团队提出了一个标准化的评估协议，专为随机车辆路径基准测试设计。该协议不仅评估解决方案质量，还评估在现实不确定性条件下的稳健性、可行性和可扩展性。

总成本(TC)衡量所有车辆的累积行驶时间，包括拥堵导致的延误和事故导致的中断。这相当于计算整个车队在完成所有配送任务过程中的总时间花费。

约束违反率(CVR)量化了服务违反时间窗口或超过车辆容量的客户比例，反映了解决方案的可行性。这就像评估一个配送计划有多少客户收到了迟到的包裹或者有多少订单因为车辆超载而无法满足。

可行率(FR)反映了解决方案在实例和求解器间的稳健性。它被定义为满足所有路由约束的问题实例比例。这衡量了一个算法能够成功处理各种挑战性场景的能力。

运行时间(RT)捕获了求解过程所需的实际计算时间，作为可扩展性和实际部署可能性的代理指标。这对于需要快速响应的实时调度系统尤为重要。

稳健性(ROB)通过计算同一实例的N个独立样本的成本方差来衡量由随机元素引起的成本变异性。这表明了一个解决方案在面对不确定因素时的稳定性有多强。

四、实验结果分析

研究团队对基线方法进行了全面评估，系统地变化了四个关键维度：实例大小、问题类型、仓库配置和车辆配置。

他们为每种组合生成了10个实例，实例大小从10、20、50、100、200、500到1000客户不等，问题类型包括CVRP和TWVRP，仓库配置包括单仓库和多仓库，车辆设置包括单车辆和多车辆，形成了一个大规模、结构化的测试套件。此外，他们还提供了用于训练的可扩展数据生成器。强化学习模型在单仓库、单车辆CVRP和TWVRP模式下在10万个合成实例上进行了训练。

所有方法都在第2节定义的随机设置下进行评估。报告的指标包括总成本（包含所有随机因素）、约束违反率(CVR)、可行率、运行时间和稳健性（测量为随机样本间的方差）。

经典算法（最近邻+2-opt、禁忌搜索和蚁群优化）在不修改的情况下在所有设置中进行了评估。它们的灵活性使它们能够开箱即用地处理各种配置。所有基线都在消费级CPU（英特尔i7，16GB RAM）上进行评估，学习模型使用单个NVIDIA RTX 4080。训练是在10万个合成实例上完成的。

总体表现上，OR-Tools算法取得了最佳总体成本（40,259），其次是蚁群优化（40,566；+0.8%）和POMO（40,650；+1.0%），而OR-Tools和NN+2opt保持了最高的可行率（98.4%），同时NN+2opt提供了最快的运行时间（0.697秒）。基于学习的方法展示了可行性和速度的权衡，POMO以具有竞争力的运行时间（1.421秒）提供比NN+2opt更好的解决方案质量，而注意力模型显示出更高的约束违反（CVR：1.9%），但在其他指标上表现合理。

引入时间窗口（TWVRP）会显著增加复杂性，将所有求解器的总成本增加536-648%。OR-Tools遭受了最高的相对惩罚（+647.6%），而注意力模型显示了最低的相对增加（+536.2%）。基于学习的方法对时间约束表现出中等的弹性，POMO维持87.9%的可行性，注意力模型达到85.4%，它们介于表现最好的（NN+2opt和OR-Tools >96%）和struggling的元启发式方法（ACO和禁忌搜索38.1%）之间。

从规模可扩展性来看，成本从小型（≤50个节点）到大型（≥500个节点）实例大约扩大了16倍，NN+2opt和OR-Tools在所有规模上保持>97%的可行性，而基于学习的方法显示出中等程度的退化（POMO：86%，注意力模型：83.5%）。基于学习的方法展示了有竞争力的性能-运行时间权衡，POMO在小型实例上提供最快的运行时间（29.7秒），并在大型实例上保持显著优于ACO和禁忌搜索（50%）的可行性，尽管传统启发式方法仍对最大规模问题保持优势。

关于仓库配置的影响，多仓库设置一致地降低了所有方法的成本并提高了可行性，OR-Tools实现了72%的成本减少（从34,611到9,561），POMO展示了同样令人印象深刻的收益（71%减少到10,178）。基于学习的方法特别受益于多仓库配置，POMO和注意力模型都达到了完美的可行性（100%），尽管它们在单仓库场景中表现各异（92-96.5%），支持了那个反直觉的发现，即更灵活的仓库放置无论算法类型如何都改善了计算和解决方案效率。

实验结果给我们带来了几个重要的见解：OR-Tools是大规模离线优化最可靠的选择，平衡了质量和可行性，尽管运行时间较高；NN+2opt提供了一个稳健的低延迟替代方案，用于实时部署，对成本或可行性的妥协最小；元启发式方法在规模上表现不佳，而基于学习的方法如POMO虽提供了更好的可扩展性的可行解决方案，但仍落后于顶级启发式方法；注意力模型展示了潜力，但需要进一步改进以匹配顶级方法的性能，特别是对于大型实例；时间窗口施加了最显著的复杂性，大幅降低了非自适应求解器的性能，尽管基于学习的方法显示出中等的弹性；多仓库设置改善了所有求解器类型的可行性和运行时间，为物流规划提供了一个实用的设计考虑。

五、局限性与未来方向

虽然SVRPBench推进了随机车辆路径中的真实性，但仍存在一些局限性。研究团队的延误模型依赖于高斯和对数正态分布来模拟交通高峰和随机性——高效且可解释，但无法捕捉网络级动态，如瓶颈、级联拥堵或实时重新路由。不过，这些假设是用户可修改的，允许注入领域特定的不确定性。

强化学习方法如注意力模型和POMO对更大实例的可扩展性有限，反映了过拟合和弱泛化。此外，目前的评估协议缺乏跨实例规模和分布偏移评估稳健性的标准化程序，这促使未来在课程学习和分层求解器设计上进行工作。

为了进一步缩小与现实世界物流的差距，未来的扩展将纳入从OpenStreetMap或GIS数据派生的道路约束实例，实现地理上有根据的路由行为。动态和多日设置——具有在线更新和滚动视野——将支持评估自适应策略。研究团队还计划引入诊断任务，以探测模型稳健性、分布偏移下的泛化和少样本性能，使复杂环境中的算法可靠性分析更加细粒度。

六、结论

SVRPBench是一个模块化、开源的基准测试，用于评估现实随机动态下的车辆路径规划。通过纳入时间依赖的拥堵、概率性延误和异质客户时间窗口，这个基准测试突破了静态假设，反映了真实物流的运营不确定性。

对500多个实例的实证结果显示，经典和元启发式方法在可行性和运行时间上保持竞争力，而强化学习模型如POMO和注意力模型，尽管在训练环境中表现强劲，但在多仓库泛化上挣扎，在分布偏移下展示了>20%的成本退化。令人惊讶的是，多仓库配置一致地改善了成本和稳健性，即使对于基于学习的求解器也是如此，强调了在实际设置中灵活仓库放置的重要性。

通过支持大规模、可重复的评估，SVRPBench为基准测试求解器提供了一个社区平台。研究团队呼吁研究界开发自适应、感知噪声的路由算法，弥合合成优化与可部署、弹性物流解决方案之间的差距。