基于候选包裹柜合并点的扰动感知最后一英里路由:求解器无关的MAPPO框架

《Computation》:Solver-Independent MAPPO for Disruption-Aware Last-Mile Routing via Candidate Parcel-Locker Consolidation Points

【字体: 大 中 小 】 时间:2026年09月22日 来源:Computation 2.6

编辑推荐:

  城市最后一英里路线在分派后必须适应需求和网络条件的变化。本研究提出一种求解器无关的多智能体近端策略优化(multi-agent proximal policy optimization, MAPPO)框架,该框架结合共享车队策略、动态排序的候选包裹柜合并点、扰

  
城市最后一英里路线在分派后必须适应需求和网络条件的变化。本研究提出一种求解器无关的多智能体近端策略优化(multi-agent proximal policy optimization, MAPPO)框架,该框架结合共享车队策略、动态排序的候选包裹柜合并点、扰动感知观测、车队级价值学习以及结构可行性掩码。在洛杉矶道路网络模拟上的评估使用了按时间顺序的数据划分、十组随机种子、匹配的路由基线以及复合扰动压力测试。MAPPO服务了98.4%的需求,而静态OR-Tools为96.6%,失败包裹减少了52.2%;在严重复合扰动下,服务率从89.4%提升至93.0%。服务率更高的自适应方法达到99.6%–99.7%,每集在线计算总时间为0.111–0.503秒,而MAPPO为0.029秒。因此,该集成框架在静态规划基础上改善了扰动恢复,同时与自适应搜索相比揭示了明确的质量–计算权衡。
城市最后一英里路由在分派后可能遭遇需求修正、道路封闭、风险和天气等扰动,导致静态计划失效。共享投递点(如包裹柜)通过聚合需求减少停靠,但增加了车辆间的耦合决策。现有研究分别关注动态需求、安全电动车路由、预测控制、候选投递选项或合作车队,但很少将候选合并点、复合道路扰动、显式可行性、合作策略执行和广泛自适应基线整合在同一框架中。为填补这一空白,研究人员提出一种求解器无关的MAPPO框架,旨在改善扰动恢复并量化质量–计算权衡。

该框架包含共享车队策略、动态排序的候选包裹柜合并点观测、扰动感知特征、车队级价值学习和结构性可行性掩码。在洛杉矶道路网络模拟中,使用保存的OSRM矩阵、按时间顺序划分的24个训练日/8个验证日/12个测试日、10个随机种子和7种预测场景,与贪婪最近、蚁群优化(ant colony optimization, ACO)、自适应大邻域搜索(adaptive large neighborhood search, ALNS)修复、静态OR-Tools、有限OR-Tools修复、完整OR-Tools动态再优化等匹配比较。结果表明,MAPPO相对静态OR-Tools提高了服务率(98.4% vs 96.6%)、减少失败包裹52.2%、缩短恢复时间;但在严重复合扰动下服务率低于ACO、ALNS修复和完整OR-Tools动态再优化(99.6–99.7% vs 93.0%)。MAPPO在线计算时间每集0.029秒,远低于自适应搜索方法(0.111–0.503秒)。因此,框架改善了静态计划的扰动恢复,但揭示了直接策略执行与自适应搜索之间的质量–计算权衡。

主要关键技术方法包括:研究采用洛杉矶道路网络模拟,数据来自地理编码投递点、OSRM路线成本矩阵和洛杉矶市碰撞数据。候选包裹柜合并点通过对24个训练日停靠点进行k-means++聚类生成,并固定用于验证/测试集分配。需求预测使用指数加权移动平均。道路风险通过高斯核估计碰撞空间强度。复合扰动生成器按严重度水平耦合需求、风险、行驶时间退化与封闭弧。MAPPO使用共享actor和集中critic,采用集中训练与分散执行(centralized training with decentralized execution, CTDE);每个决策点对候选节点按得分排序取top-10,并构建可行性掩码剔除已服务、容量不兼容、封闭弧和无效仓库动作。外部基线包括OR-Tools、ACO、ALNS等,均在相同实例上运行。

7.1 总体方法比较:通过七种方法在12个测试日、10个种子、7个场景上的匹配比较,MAPPO服务98.4%需求,静态OR-Tools为96.6%,失败包裹从180.461降至86.328,恢复时间缩短,未恢复率从18.3%降至9.2%。ACO、ALNS修复和完整OR-Tools动态再优化达到99.6–99.7%服务。

7.2 严重复合扰动结果:在严重复合场景下,MAPPO服务93.0% vs 静态OR-Tools 89.4%,失败包裹从622.200降至397.260,恢复时间缩短,未恢复率从31.7%降至22.5%;ACO和最强自适应方法达98.8–99.0%。

7.3 场景特异性异质性:MAPPO在所有单因素场景中均超过静态OR-Tools,在封闭和复合扰动下差异最大。

7.4 服务质量与运行时权衡:MAPPO每集在线计算0.029秒,ACO、完整OR-Tools、ALNS分别为0.111、0.302、0.503秒,所有方法均亚秒。

7.5 鲁棒性与可扩展性:冻结策略在两辆车或0.8倍参考容量下服务率保持0.94以上,1.4倍需求下为0.919;计算时间随车辆数近似线性增长。

7.6 Top-k敏感性:匹配策略在k=10时服务率从0.968增至0.984,超过10后增益减小但运行时间增加,因此选择k=10。

7.7 特征与组件消融:移除动作掩码导致服务率降至0%;移除封闭、预测、风险信息分别降至0.453、0.924、0.944;扩展观测消融为0.973;集中critic和环境奖励变体接近参考。

7.8 环境奖励与CTDE分离:移除环境项使能耗从202.121增至207.864 kWh,距离指数增加2.7%;共享actor加局部critic服务为0.987,集中critic参考为0.985,独立actor-critic为0.977,说明共享策略学习贡献最大。

7.9 统计比较:记录级配对检验保持主要排序:MAPPO优于静态OR-Tools,完整OR-Tools动态再优化优于MAPPO。

7.10 依赖感知推断与恢复阈值:跨种子/天交叉推断确认所有主要指标方向一致,Holm调整后种子级p<0.05,交叉95%区间不包含零;MAPPO优势在90%、95%、98%恢复阈值下仍存在。

讨论部分指出,该框架填补了研究空白,将合作策略执行、动态合并点观测、复合扰动特征和结构可行性整合在一个路由环境中。MAPPO相对静态规划的优势源于在每个决策时刻刷新封闭、风险、预测和剩余需求信息;而ACO、ALNS和完整OR-Tools通过搜索已揭示实例获得更高服务,MAPPO则通过摊销策略降低计算。封闭信息是最重要的特征,其次是预测和风险;掩码提供了结构可行性。共享策略学习比集中critic贡献更明显。环境项影响运行能耗而非主要服务排序。管理上,MAPPO适合重复、并行或时间紧迫的决策;修复方法保留可用计划段;广泛自适应搜索适合边际服务价值较高的情况。物理包裹柜部署还需考虑场地、容量、客户选择等因素。环境结果仅为路由层面电动车队代理。未来可结合MAPPO动作或暖启动与事件触发的ALNS和完整OR-Tools再优化。

研究结论可翻译为:本研究提出了一个针对特定问题的MAPPO框架,该框架整合了共享多智能体动作选择、动态合并点观测、车队级价值学习、复合扰动信息和结构可行性,用于通过解析候选包裹柜合并点进行路由。MAPPO服务了98.4%的需求,而静态OR-Tools为96.6%,失败包裹减少52.2%,严重场景下的服务率从89.4%提升至93.0%。其每集在线计算总时间为0.029秒,而服务率更高的自适应方法在0.111–0.503秒内达到99.6–99.7%。所有方法在测试硬件上均保持亚秒级,这使得MAPPO的价值体现在重复或时间紧迫决策的计算余量上。消融研究确定封闭信息、预测、风险、共享策略学习和显式可接受性为框架的主要组成部分。结果确立了直接策略执行与自适应搜索之间的质量–计算权衡。向已安装包裹柜运营的迁移需要设施和客户状态、更广泛的地理验证以及现场校准;环境结果仍然是运营路由代理。未来工作可以将MAPPO动作或暖启动与事件触发的ALNS和完整OR-Tools动态再优化相结合。
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号