面向拆分配送车辆路径问题异构决策结构的分块缩放灰狼优化器

《Eng》:A Block-Scaled Grey Wolf Optimizer for Heterogeneous Decision Structures in Split Delivery Vehicle Routing

【字体: 大 中 小 】 时间:2026年09月19日 来源:Eng 3.5

编辑推荐:

  拆分配送车辆路径问题(Split Delivery Vehicle Routing Problem, SDVRP)需要协调路径排序与订单拆分决策,其异构结构可能会限制在统一搜索动态下更新所有决策变量的元启发式算法的有效性。研究人员提出一种分块缩放灰狼优化器(B

  
拆分配送车辆路径问题(Split Delivery Vehicle Routing Problem, SDVRP)需要协调路径排序与订单拆分决策,其异构结构可能会限制在统一搜索动态下更新所有决策变量的元启发式算法的有效性。研究人员提出一种分块缩放灰狼优化器(Block-Scaled Grey Wolf Optimizer, BS-GWO),用于求解参数化的SDVRP变体,其中订单分配与周期时间在初始阶段确定,而主要优化过程聚焦于运营层面的车辆级拆分与路径排序。每个候选解用一个连续向量表示,该向量分为两个块:一个对应访问顺序,另一个对应产品单元在车辆间的分配。与经典灰狼优化器(Grey Wolf Optimizer, GWO)相比,所提出的BS-GWO引入了分块差分缩放和每块最大位移控制,同时保留了原始的α、β和δ领导结构。结果表明,BS-GWO比经典GWO获得了更稳定的解质量,并在所比较的元启发式算法中取得了最佳整体性能。这些发现表明,使搜索动态适应解向量的内部结构,能够增强在所考虑的公式中求解异构SDVRP表示的能力。
车辆路径问题(Vehicle Routing Problem, VRP)是物流运输规划的核心模型,运输成本约占物流总成本的40%–60%,并影响最终产品价格的6%–7%。经典VRP要求每个顾客由单辆车一次访问,但实际物流中该约束过于刚性。拆分配送车辆路径问题(Split Delivery Vehicle Routing Problem, SDVRP)允许需求在多辆车之间拆分,提高了调度灵活性,但也使解空间急剧扩大,属于NP-hard组合优化问题。精确算法虽能保证最优性,但计算量随规模指数增长,难以应用于现实场景。为此,元启发式算法成为求解此类问题的主流工具。

灰狼优化器(Grey Wolf Optimizer, GWO)是典型的群体智能(Swarm Intelligence, SI)算法,通过模拟灰狼的社会等级和狩猎行为进行搜索。然而,GWO在复杂或高维搜索空间存在收敛速度慢、易陷入局部最优以及探索与开发失衡等缺陷。更关键的是,SDVRP的候选解同时包含路径排序与数量拆分两类异构决策,而标准GWO对所有维度施加统一的更新动力学,无法反映不同决策块在问题中的不同作用。现有GWO改进多集中于领导结构、变异算子和邻域学习等机制,尚未直接针对解向量内部的功能分区设计搜索策略。因此,研究人员提出分块缩放灰狼优化器(Block-Scaled Grey Wolf Optimizer, BS-GWO),在保留GWO原有α、β、δ领导结构的基础上,引入分块差异化缩放与最大位移控制,使不同决策块以不同强度进化。实验表明,BS-GWO可获得比经典GWO更稳定的解质量,并在多种对比元启发式中取得最优整体性能。这一结果说明,使搜索动力学适应解向量的内部结构,有助于提升异构SDVRP表示的求解能力。

关键技术方法方面,研究人员采用两阶段求解框架。预处理阶段基于多供应商-单买方(Multi-Vendor Single-Buyer, MVSB)框架的分解逻辑,确定供应商-产品分配比例与周期时间T,使主问题成为参数化SDVRP。主优化阶段采用连续向量编码:顺序块决定各车辆访问供应商的优先级,拆分块通过softmax映射将预定义数量分配到各车辆;解码后使用含容量、路线时长等惩罚项的适应度函数评估。BS-GWO在经典GWO更新中增加按块缩放和按块最大位移裁剪两个操作,其他结构不变。实验使用48个人工合成实例,由4种供应商规模(10、30、50、70)、4种产品数(5、10、20、30)和3种车队规模(1、2、3)组合生成,每实例独立运行30次,采用Wilcoxon符号秩检验、Friedman检验和Iman–Davenport检验进行分析。

研究结果部分,参数校准(Parameter Calibration of BS-GWO)通过26全因子设计比较64组参数,以按供应商规模分组后的平均秩为准则,选择整体表现最稳健的配置。敏感性分析显示,拆分块缩放因子对目标函数影响最大,且其最优水平随问题规模变化,支持分块差异化控制的必要性。与经典GWO比较(Comparison Between BS-GWO and Classical GWO)中,BS-GWO在48个实例中的33个取得更优平均目标值,其中30个差异显著;优势随供应商数和车辆数增加而扩大,例如3辆车时16/16实例占优。全局消融分析显示,相对经典GWO,BS-GWO使目标函数平均降低10.266%,中位数降低13.794%;在供应商为70时平均降低15.794%,在车辆数为3时平均降低19.568%。收敛曲线表明BS-GWO在早期下降更快并在中后期持续改进。与其他元启发式比较(Comparison of BS-GWO Against Other Metaheuristics)中,BS-GWO与粒子群优化(Particle Swarm Optimization, PSO)、蚁群优化(Ant Colony Optimization, ACO)、鲸鱼优化算法
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

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

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号