一种用于带配送选项的多仓库两级车辆路径问题的自适应大邻域搜索框架

《Research in Transportation Economics》:An Adaptive Large Neighborhood Search framework for the Multi-Depot Two-Echelon Vehicle Routing Problem with Delivery Options

【字体: 大 中 小 】 时间:2026年09月28日 来源:Research in Transportation Economics 4.2

编辑推荐:

   摘要本文研究带交付选项的多仓库两级车辆路径问题(MD-TEVRP-DO),该问题融合了多仓库配送、基于卫星节点的集货以及灵活的末端物流服务。该问题涉及客户交付方式、卫星节点利用以及一级和二级路径规划等高度相互依赖的决策,使得有效的跨层级协调尤为困难。一级车辆将需求从仓库运至卫

  

摘要

本文研究带交付选项的多仓库两级车辆路径问题(MD-TEVRP-DO),该问题融合了多仓库配送、基于卫星节点的集货以及灵活的末端物流服务。该问题涉及客户交付方式、卫星节点利用以及一级和二级路径规划等高度相互依赖的决策,使得有效的跨层级协调尤为困难。一级车辆将需求从仓库运至卫星节点,而二级车辆则通过上门配送(HD)或客户自提(CP)两种方式服务客户。为解决该问题,提出了一种覆盖感知、可行性保持的自适应大邻域搜索(ALNS)框架。该方法的创新之处在于将问题特定的协调机制嵌入ALNS搜索过程中。该算法联合优化客户到卫星节点的分配、交付模式选择以及二级路径,同时根据活跃卫星节点及其产生的补货需求重构一级路径,从而显式协调两个路径层级。所提出的ALNS将经典的破坏-修复算子与针对卫星节点拥塞、交付模式不匹配和耦合的卫星节点-路径插入的问题特定算子相结合。在基准MD-TEVRP–DO实例上的计算实验表明,所提出的ALNS始终优于现有的混合多群体遗传算法(HMPG)和模拟退火(SA)启发式方法。HD+CP配置与仅HD配置的对比显示,引入CP可通过改善需求集货和减少二级路径需求,将总配送成本降低约16%–17%。进一步的经济评估表明,在适当的成本传导条件下,这些节省可能改善零售商利润率或降低终端价格,从而从运营和经济两个角度证明了协调交付灵活性与多仓库两级路径规划的价值。

引言

货运运输在经济发展和城市可持续性中发挥着至关重要的作用。然而,城市物流的快速增长加剧了交通拥堵、环境影响和配送成本,特别是在人口稠密地区。因此,多级配送系统引起了广泛关注,因为中间设施可以集货并提高城市配送效率(Crainic et al., 2004)。两级车辆路径问题(2E-VRP)通过协调仓库到卫星节点和卫星节点到客户的运输来表征此类系统(Sluijk et al., 2023)。其扩展到多仓库的延伸,即多仓库两级车辆路径问题(MD-TEVRP),通过允许多个仓库为卫星节点网络供货,提供了更大的灵活性(Phuc & Anh, 2024)。尽管如此,末端配送仍然是城市物流中最具成本且运营挑战最大的组成部分之一(Gevaers et al., 2009, Wang et al., 2014)。
交付灵活性为减少这些末端低效率提供了重要机遇。在带交付选项的车辆路径问题(VRP-DO)中,客户可以通过上门配送(HD)或从指定的客户自提(CP)设施取件来获取订单。虽然HD提供了更大的便利性,但CP可以将多个客户需求集货到共同地点,从而减少单独配送停靠点并提高车辆利用率。将此类交付选项整合到多仓库和两级配送中,产生了带交付选项的多仓库两级车辆路径问题(MD-TEVRP–DO),由Zhou等(2018)首次提出。从经济角度来看,配送效率的改善也可能产生超越路径成本的影响。运输和配送成本构成商品最终成本的一部分,可能影响企业利润和消费者价格。先前的经济学研究表明,运输成本的降低可以改善市场效率并产生福利效益(Allen and Arkolakis, 2022, Donaldson, 2018, Donaldson and Hornbeck, 2016),而成本变化传导至价格的程度取决于市场和竞争条件(Atkin and Donaldson, 2015, Carrière-Swallow et al., 2023, RBB Economics, 2014)。因此,考察路径成本降低的经济含义为交付灵活性的价值提供了另一个视角。
尽管关于灵活交付、两级路径和多仓库配送的文献日益增长,但它们联合算法处理的研究仍相对有限。针对特定的MD-TEVRP–DO,Zhou等(2018)提出了混合多群体遗传算法(HMPG),而Yu等(2024)随后开发了模拟退火(SA)启发式方法。然而,该问题涉及客户分配、HD/CP服务选择、卫星节点利用以及一级和二级路径规划等高度相互依赖的决策。这产生了对能够有效协调这些决策同时保持完整候选解可行性的解决方案机制的需求。此外,交付灵活性的运营价值以及由此产生的配送成本节省的更广泛经济影响需要进一步研究。为弥补这些空白,本研究针对MD-TEVRP–DO开发了一种覆盖感知、可行性保持的自适应大邻域搜索(ALNS)。方法学贡献在于ALNS与问题结构的特定整合:二级客户分配、HD/CP决策和路径规划与卫星节点利用和一级补货协调,同时针对交付选项和卫星节点特性的问题特定破坏和修复机制加以利用。一级路径根据活跃卫星节点及其产生的补货需求重构,从而在搜索过程中显式协调两个层级。
本研究的贡献有三方面。首先,所提出的ALNS提供了一个针对相互依赖的交付模式、卫星节点和两级路径决策进行协调的问题特定框架,同时保持完整候选解的可行性。其次,使用相同求解框架对HD+CP和仅HD配置进行对照比较,量化了交付灵活性的运营价值。结果显示,最佳和平均配送成本分别降低了约17.04%和16.07%,主要节省来源于需求集货和二级路径需求的减少。第三,从经济角度考察这些运营节省,将配送成本降低与其对物流支出、零售商利润率和终端价格的潜在影响联系起来,并明确说明了成本传导假设。这提供了路径效率与交付灵活性更广泛经济价值之间的直接联系。计算实验将所提出的ALNS与HMPG(Zhou et al., 2018)和SA(Yu et al., 2024)基准方法进行比较,并进一步研究交付选项的运营和经济影响。
本文其余部分组织如下。第2节回顾相关文献并指出研究空白。第3节介绍问题描述和数学建模。第4节描述所提出的ALNS框架。第5节呈现计算结果及其管理和经济含义。最后,第6节总结全文并展望未来研究方向。

章节摘要

文献综述

MD-TEVRP–DO与四个主要研究流密切相关:(i) 带灵活交付选项的车辆路径问题,(ii) 两级和新兴末端路径系统,(iii) 多仓库、选址-路径和协作配送系统,以及 (iv) 交付选项在多级系统中的整合。
为系统且渐进地展示该研究领域的演进,文献被组织为四个相互关联的研究流。在每一

问题描述、网络与交付选项

在此,我们研究一个建模为MD-TEVRP-DO的末端配送系统。配送网络由仓库、中间"卫星节点"、可选自提设施和客户组成。基于仓库的一级车辆将集货后的需求运至卫星节点的子集。容量较小的二级车辆从卫星节点出发/返回,要么直接配送给客户(上门配送,HD),要么配送至客户自提其包裹的自提设施(客户自提,

方法论

自适应大邻域搜索(ALNS)由Ropke和Pisinger(2006)提出,扩展了Shaw(1998)的大邻域搜索(LNS)框架,通过根据多种破坏和修复算子在搜索过程中的表现自适应地选择算子。将传统ALNS直接应用于MD-TEVRP–DO具有挑战性,因为客户路径规划、客户到卫星节点分配、HD/CP交付模式选择、卫星节点利用和一级补货

实验结果与分析

计算实验使用Anaconda分发的Python 3.12.4(64位)实现,并通过Spyder 5.5.1 IDE执行。软件环境在Windows 11(build 26200)平台上包含Qt 5.15.2和PyQt5 5.15.10。所有实验均在配备Intel? Core? i7处理器和16 GB RAM的个人笔记本电脑上进行。
本研究采用Zhou等(2018)引入的MD-TEVRP–DO数据集,可在VRP-REP仓库获取(http://www.vrp-rep.org,

结论与未来工作

本研究针对MD-TEVRP–DO进行了研究,其中客户可以通过上门配送或客户自提获得服务。通过整合自适应破坏-修复算子、交付模式选择、卫星节点容量控制以及一级路径重构,开发了一种可行性保持的ALNS框架。所提出的程序通过根据二级生成的卫星节点决策重构一级供给路径,协调两个路径层级。The

CRediT作者贡献声明

Pooja Kumari:写作 – 原始草稿、验证、软件、方法论、形式化分析、概念化。Debashis Dutta:写作 – 审阅与编辑、指导。

利益冲突声明

作者声明不存在任何已知的竞争经济利益或个人关系可能影响本文所报告的工作。

致谢

对于所提交的工作,作者未收到任何组织的支持。
Pooja Kumari|Debashis Dutta
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

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

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号