《Algorithms》：Performance Comparison Among Classical Metaheuristic Algorithms for Stochastic Last-Mile Delivery Routing Problem
编辑推荐：
摘要专业翻译
最后一公里配送路径规划需要同时对距离、行驶时间、服务截止时间、车辆容量、工作量均衡、运营成本、排放以及不确定性进行控制。本研究针对一个经LaDe校准的随机容量约束车辆路径问题与时间窗约束（CVRPTW）问题，开展了一项受控低预算的十种经典元启发式
摘要专业翻译
最后一公里配送路径规划需要同时对距离、行驶时间、服务截止时间、车辆容量、工作量均衡、运营成本、排放以及不确定性进行控制。本研究针对一个经LaDe校准的随机容量约束车辆路径问题与时间窗约束（CVRPTW）问题，开展了一项受控低预算的十种经典元启发式算法对比研究。遗传算法（GA）、差分进化算法（DE）、粒子群优化算法（PSO）、蚁群优化算法（ACO）、人工蜂群算法（ABC）、模拟退火算法（SA）、灰狼优化算法（GWO）、鲸鱼优化算法（WOA）、教与学优化算法（TLBO）和JAYA算法均采用相同的随机键表示方法、容量感知分割解码器、修复规则、公共随机数（CRN）场景，且每次运行严格限定50次目标函数评估。实验包含1065个固定设计条件，每个算法-条件单元执行30次带种子的独立运行，共计319,500次元启发式算法运行，并以最近邻搜索（NNS）、Clarke–Wright节约算法和OR-Tools引导式局部搜索作为基准。PSO取得了最低的总体均值加权物流成本，而WOA取得了最低的中位数和最优的Friedman平均秩。WOA与PSO之间的总体均值差异仅为125.2个目标单位，且情境优胜者在三个城市和五个客户规模层级之间发生变化（PSO：4次，WOA：2次，JAYA：2次）。因此，校正后的p值被视为条件性设计诊断指标，而实际解释优先考虑配对幅度、分层一致性、可行性和基准接近度。设计分层敏感性分析表明，优选方法随城市和客户规模的变化而改变。至关重要的是，在共同评估器下，每种元启发式算法和基准均记录了0%的完全可行性；因此，容量违规和迟到违规特征被提升为主要结果，且不宣称任何算法在运营上具有优越性。50次评估方案被解释为早期预算筛选机制，而非渐近收敛的证据。结果表明，算法选择取决于所测试的数据、权重、问题规模、不确定性设置和评估预算，且对于实际部署而言，保持可行性的解码比惩罚目标值的微小差异更为重要。
论文解读文章
一、研究背景与问题提出
城市货运和包裹配送日益需要同时满足经济、服务质量和环境要求。交通规划影响能耗、配送时间、排放、资产利用率和客户服务，因此路径决策不应仅简化为行驶距离。在供应链层面，运营预算、碳约束和随机物流能力相互依存，这意味着在名义条件下表现良好的方案可能在需求、行驶条件或可用容量发生变化时恶化。物流组织因此依赖可靠的数字决策支持系统，将运营数据转化为可执行的调度和路径决策。这一需求在最后一公里配送中尤为突出——路网拥堵、客户地理分散、工作量异构和时变交通条件直接影响配送效率。
车辆路径问题（VRP）将车辆车队的客户访问分配和排序形式化，通常以最小化总距离或运营成本为目标，同时满足特定服务要求。实际扩展引入了配送时间窗、车辆容量限制、周期性服务要求和驾驶员一致性条件。当代配送问题还可能组合多个目标，包括能耗、配送时长、运营成本、服务质量和资源利用率。随着客户数量、车辆数、不确定性来源和规划约束的增加，精确混合整数规划模型在运营时限内变得越来越难以求解。启发式和元启发式算法提供了一种务实替代方案。
然而，现有元启发式算法性能对比证据难以解读。已发表研究可能在解编码、种群规模、迭代次数、终止准则、惩罚结构、局部搜索过程、参数调优、随机种子策略和基准实例等方面存在差异。表面上的算法优势可能反映的是计算资源不平等或特定问题的实现选择，而非算法本身的搜索行为。此外，许多研究依赖合成或小型确定性实例，无法再现工业最后一公里配送的运营异构性。LaDe数据集通过提供来自多个城市的行业级配送、取件、路网和快递员轨迹观测弥补了这一经验性局限。
二、研究内容与主要结论
本研究针对经LaDe校准的随机CVRPTW问题，开展了一项十种经典元启发式算法的受控对比研究。研究不提出新的优化器，其创新在于方法论和经验层面：工业多模态校准、共同表示和解码器、精确目标评估平等、完整种子保留、求解器基准测试、依赖感知解释、可行性优先报告和目标权重敏感性被整合到一个可复现的方案中。实验包含1065个不同条件和319,500次独立元启发式运行，评估50至1000个客户群体，同时变化城市、车队规模、车辆容量、时间窗紧度、需求不确定性、行驶时间不确定性和交通中断等因素。
研究得出以下主要结论：PSO取得最低总体均值加权物流成本（106,854.5919），WOA取得最低中位数（2980.63）、最优Friedman平均秩（3.0742）和最高成功率（1.26%）。WOA与PSO之间的总体均值差异仅为125.2个目标单位。优选方法随城市和客户规模变化：JAYA在50个客户时均值最低，WOA在100和250个客户时最优，PSO在500和1000个客户时领先；城市层面，JAYA在重庆均值领先，PSO在杭州和上海领先，而WOA在三个城市均保持最低城市级中位数。Friedman和Iman–Davenport检验的p值在数值上无法与零区分，Holm校正的Wilcoxon检验拒绝了45对中的36对，WOA击败了所有对比算法。然而，所有元启发式算法和基准在共同评估器下均记录0%的完全可行性，容量违规均值约为44.88个包裹，平均累积迟到时间超过1.72亿秒。这一发现表明，目标质量并未转化为运营可行性，保持可行性的解码比惩罚目标值的微小差异更为重要。
三、关键技术方法
研究人员使用了以下主要技术方法：采用LaDe工业最后一公里配送数据集，经数据审计后保留上海、杭州、重庆三个城市，共453,299条干净配送记录用于经验校准；所有十种算法（GA、DE、PSO、ACO、ABC、SA、GWO、WOA、TLBO、JAYA）通过MEALPY 3.0.3执行，共享相同的连续随机键表示和容量感知顺序分割解码器；每次运行严格限定50次目标函数评估，每次评估为一次完整的三场景公共随机数（CRN）随机加权物流目标调用；以最近邻搜索（NNS）、并行Clarke–Wright节约算法和OR-Tools 9.14.6206引导式局部搜索作为基准，所有基准路线均经共同随机加权评估器重新评估；统计方法包括Friedman检验、Iman–Davenport校正、Holm校正的配对Wilcoxon符号秩检验、Vargha–Delaney效应量、贝叶斯配对优越性分析及Dolan–More性能剖面。
四、研究结果
4.1 经验配送背景与校准
重庆、杭州和上海在隐私保护的本地坐标系统中占据三个不重叠的区域，确认城市因素代表实质性不同的路径几何结构。城市内部客户需求形成不同的多中心模式，快递员质心从主要集中区延伸至外围服务区域。上午和下午完成高峰在各城市间存在差异，紧/中/松时间窗在重庆为4200/8100/14,220秒、杭州为3120/5460/9240秒、上海为2580/4440/7260秒，表明相同紧度标签在不同城市并不施加相同的绝对时长。
4.2 元启发式算法总体表现
PSO取得最低总体均值目标值（106,854.5919），WOA取得最低中位数（2980.63）、最优Friedman平均秩（3.0742）和最高成功率（1.26%）。TLBO产生最小的孤立最优值（13.9979），但其均值和秩不具竞争力。所有方法的目标值分布均呈强烈右偏，中心箱体重叠但上尾较长。
4.3 客户规模与城市间的表现
优选方法随规模和地理变化：JAYA在50个客户时均值最低，WOA在100和250个客户时最优，PSO在500和1000个客户时领先。城市层面，JAYA在重庆均值领先，PSO在杭州和上海领先，WOA在三个城市均保持最低城市级中位数。客户规模曲线近似平行，但小相对差异在人口升至1000时变为大绝对差异；城市间的垂直分离远大于同一城市内算法间的差异。
4.4 车队规模、容量、时间窗和不确定性的影响
最高成本水平使平均目标值增加倍数分别为：车队规模2.42倍、容量5.85倍、时间窗紧度4.98倍、需求不确定性5.83倍、行驶时间不确定性16.65倍、交通中断68.22倍。PSO在每个最高成本水平均取得最低均值。交通中断引发急剧机制转变：无中断时中位数目标值约823–838，中度中断下升至5095–5190，严重中断下达48,285–49,300。WOA在无中断和中度中断情况下最低，SA在严重中断下最低。
4.5 收敛行为与计算复杂度
WOA实现最大中位数改进（11.02%），其他方法改进约8.36–9.56%。ACO在1000个客户时运行时间为5.5733秒，明显高于其他方法的0.4204–0.6672秒，且经验增长斜率最陡。大多数改进发生在预算前半段。WOA在Dolan–More性能剖面中几乎在整个性能比范围内最高。九种方法在1000个客户时保持一秒以下运行时间，ACO明显分离于主运行时间带。
4.6 算法性能统计比较
Friedman和Iman–Davenport检验的p值在数值上无法与零区分。WOA以3.0742的平均秩排名第一，贝叶斯平均优越性为0.7690；PSO、JAYA和GA形成第二梯队；GWO排名最后。WOA与每个对比算法的差异均超过0.4151的Nemenyi临界差。Holm校正的Wilcoxon检验拒绝了45对中的36对，WOA击败所有对比算法，秩双列效应从对PSO的0.3442到对GWO的0.7297。GA-PSO、GA-JAYA、PSO-JAYA和DE-ABC等若干中梯队比较在校正后仍无法区分。
4.7 可行性、成功率与失败构成
所有方法的完全可行性均为0%，成功率范围为0.33%至1.26%，平均容量违规约44.88个包裹，平均累积迟到时间超过1.72亿秒。算法间的微小差异表明，共同解码器和限制性注册条件对残余不可行性的主导作用强于搜索规则。可行性优先的字典序排序中，WOA排名第一，但所有方法在运营上均不可执行。
五、讨论与结论
讨论部分指出，算法选择取决于所测试的数据、权重、问题规模、不确定性设置和评估预算。50次评估方案应被解释为早期预算筛选机制，而非渐近收敛的证据。可行性保持解码对于实际部署比惩罚目标值的微小差异更为重要。研究局限性包括：LaDe提供隐私保护的平面坐标而非经纬度，环境项被处理为距离比例排放指数而非二氧化碳千克数；仅三个城市集群可用，传统集群稳健标准误不稳定；所有结论均限于注册的50次评估预算制度。研究结论为：WOA在配对条件级排名中表现最优，PSO在总体均值方面领先，但两者差异很小；所有算法均未达到完全可行性；算法选择是条件性的，取决于测试数据、权重、问题规模、不确定性设置和评估预算；可行性保持解码比小目标值差异对部署更为关键。
