引用本文

范厚明, 刘鹏程, 刘浩, 侯登凯. 多中心联合配送模式下集货需求随机的VRPSDP问题. 自动化学报, 2021, 47(7): 1646−1660 doi: 10.16383/j.aas.c190519

Fan Hou-Ming, Liu Peng-Cheng, Liu Hao, Hou Deng-Kai. The multi-depot vehicle routing problem with simultaneous deterministic delivery and stochastic pickup based on joint distribution. Acta Automatica Sinica, 2021, 47(7): 1646−1660 doi: 10.16383/j.aas.c190519

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c190519

关键词

车辆路径问题，多中心，同时配集货，随机需求，文化基因算法，变邻域搜索算法 

摘要

针对多中心联合配送模式下集货需求随机的同时配集货车辆路径问题(MDVRPSDDSPJD), 构建了两阶段MDVRPSDDSPJD模型. 预优化阶段基于随机机会约束机制以及车载量约束为客户分配车辆, 生成预优化方案; 重优化阶段采用失败点重优化策略对服务失败点重新规划路径. 根据问题特征, 设计了自适应变邻域文化基因算法(Adaptive memetic algorithm and variable neighborhood search, AMAVNS), 针对文化基因算法易早熟、局部搜索能力弱等缺陷, 将变邻域搜索算法的深度搜索能力运用到文化基因算法的局部搜索策略中, 增强算法的局部搜索能力; 提出自适应邻域搜索次数策略和自适应劣解接受机制平衡种群进化所需的广度和深度. 通过多组算例验证了提出模型及算法的有效性. 研究成果不仅深化和拓展了VRP (Vehicle routing problem)相关理论研究, 也为物流企业制定车辆调度计划提供一种科学合理的方法.

文章导读

车辆路径问题(Vehicle routing problem, VRP)是物流配送企业的核心问题, 自Dantzig等[1]在1959年首次提出之后, 众多学者对该问题展开了研究, 并衍生出随机需求车辆路径问题(Vehicle routing problem with stochastic demand, VRPSD)、多中心车辆路径问题(Multi-depot vehicle routing problem, MDVRP)以及同时配集货车辆路径问题(Vehicle routing problem with simultaneous delivery and pickup, VRPSDP)等众多VRP拓展问题. 本文研究的多中心联合配送模式下集货需求随机的同时配集货车辆路径问题(Multi-depot vehicle routing problem with simultaneous deterministic delivery and stochastic pickup based on joint distribution, MDVRPSDDSPJD)是综合考虑了VRPSD、MDVRP、VRPSDP及联合配送特点的科学问题.

近年来, 有关MDVRP、MDVRPJD (Multi-depot vehicle routing problem based on joint distribution)、VRPSD问题已成为VRP拓展问题研究的热点. 葛显龙等[2]对基于联合配送的多中心开放式动态车辆路径问题进行研究, 针对跨区域多中心联合配送的情况, 建立“多对多”的网络配送机制, 车辆配送完成后可就近返回任意配送中心, 设计云遗传算法对问题进行求解. 杨翔等[3]研究了带有模糊时间窗的MDVRP问题, 假设虚拟配送中心对多配送中心问题进行处理, 设计了改进的蚁群算法对问题进行求解. Gruler等[4]对带有随机需求的MDVRP问题进行研究, 设计了结合迭代局部搜索算法的模拟优化算法对问题进行求解. Alinaghian等[5]研究了多车厢多类型产品的MDVRP问题, 车辆从配送中心出发最终返回原配送中心, 在配送过程中, 针对同一种产品不允许拆分服务, 设计了结合自适应大邻域搜索算法和变邻域搜索算法的混合算法对问题进行求解. 葛显龙等[6]研究了需求可拆分模式下的集配一体化MDVRP问题, 设计改进遗传算法进行求解. 陈呈频等[7]对多车型MDVRP问题进行研究, 车辆从配送中心出发对客户进行服务后, 最终返回原配送中心, 设计多染色体遗传算法对问题进行求解. Wang等[8]研究了时变网络下的多中心车辆路径问题, 提出了新的交通资源共享策略, 结合节约算法、扫描算法和多目标粒子群算法设计了混合元启发式算法对问题进行求解. Li等[9]研究了带时间窗限制的多目标绿色MDVRP问题, 设计改进蚁群算法对问题进行求解. 可见, 众多学者从时间窗、多车型、需求可拆分、随机需求以及配集货等方面进一步深化了对MDVRP问题的研究.

多中心同时配集货车辆路径问题(Multi-depot vehicle routing problem with simultaneous delivery and pickup, MDVRPSDP)是集成了MDVRP和VRPSDP问题而展开的研究. 该问题涉及多个配送中心的物流配送企业对同时具有配货需求和集货需求的客户点进行配集货服务. Li等[10]研究了闭环式MDVRPSDP问题, 车辆从配送中心出发, 服务完客户后返回原配送中心, 设计基于迭代局部搜索的元启发式算法对问题进行求解. Kachitvichyanukul等[11]研究了多中心多种配集货需求的车辆路径问题, 针对不同的客户配集货需求, 车辆可从任一位置出发, 且无须返回原配送中心, 设计基于粒子群的改进算法对问题进行求解. Soriano等[12]对两个区域多中心配集货车辆路径问题进行研究, 要求车辆服务完成后返回原配送中心, 设计了自适应大邻域搜索算法对问题进行求解. Ben Alaia等[13]对闭环式多车辆多中心配集货车辆路径问题进行研究, 采用遗传算法和粒子群算法对问题进行求解. Bouanane等[14]研究了带有库存限制的MDVRPSDP问题, 并设计了一种结合最近仓库启发式算法、扫描算法和最远插入启发式算法的混合遗传算法进行求解.

综上文献梳理可见, 在以下几个方面有待更深入的研究. 1)现有对于MDVRP问题的研究通常采用先分组后路径的方式, 将客户划分到不同的区域, 每个配送中心仅负责该区域内的客户, 将MDVRP问题转化为多个独立的单中心VRP进行求解. 该方法未能考虑到多个配送中心联合配送的优势, 客户资源不能共享, 难以对整个配送网络进行全局优化. 2)未考虑多个配送中心之间车辆资源共享并设计适合其特点的车辆返回规则. 在对闭环式MDVRP问题的研究中, 仅考虑了各配送中心对于客户资源共享, 而对于车辆资源共享方面研究不足, 导致车辆在完成配集货服务后仍需返回原配送中心, 造成路径成本的增加. 在对开放式MDVRP问题的研究中, 车辆服务完客户后, 通常采用就近返回任意配送中心的规则. 在配送中心车辆数量有限的情况下, 虽然就近返回配送中心规则会降低本次车辆调度的成本, 但未能根据配送中心的需求进行合理的车辆分配, 造成车辆的无序分配, 使得下一次规划车辆路径受到限制. 即需要先进行配送中心间的车辆调度, 增加了额外的路径成本. 3)针对MDVRPSDP方面的研究, 所涉及的客户集货量和配货量多为确定型, 然而在许多实际配送服务中, 常存在客户配货量已知、集货量不确定的情况. 例如, 在一个地区含有多个配送中心的玻璃制造公司对该地区客户进行服务, 其中配货量可以通过客户订单来确定, 而对于从客户手中收集的玻璃原材料, 客户使用过程中损坏、剩余的废旧玻璃以及玻璃残次品的回收量无法得知, 仅能根据以往的经验得知其服从的某种概率分布. 以往的研究缺乏对于不确定环境下的MDVRPSDP的研究.

MDVRPSDDSPJD问题是集成上述三个方面而展开的研究, 已有方法无法适用于MDVRPSDDSPJD问题的原因在于以下两方面. 1)已有文献对于车辆返回规则的算法设计无法应用于本文提出的适合车辆共享特点的车辆返回规则. 2)在已有研究中, 对于VRPSDP问题的算法设计未考虑随机需求对于车辆实时载重量的影响以及随机需求引起的对于服务失败点的二次配送. 在VRPSD问题的研究中, 未考虑由于客户双重需求引起的车辆初始装载量的设计. 即传统对于VRPSD问题的研究中, 车辆从配送中心出发时, 车辆初始装载量为满载(配货的情况)或者空载(集货的情况). 然而针对MDVRPSDDSPJD问题的研究, 由于集货需求的随机性, 必须考虑车辆的初始装载量情况, 不能同传统VRPSD问题一般, 满载(或空载)出发对客户进行服务.

本文针对MDVRPSDDSPJD问题展开研究, 阐述MDVRPSDDSPJD的衍生进程, 并构建了两阶段MDVRPSDDSPJD模型. 预优化阶段基于随机机会约束机制以及车载量约束为客户分配车辆, 生成预优化方案; 重优化阶段针对服务失败的客户点采用重优化策略生成重优化路径. 根据问题特征设计自适应变邻域文化基因算法对问题进行求解, 并通过三组算例对本文的模型及算法进行验证. MDVRPSDDSPJD问题之所以能应用到含有多个配送中心的物流企业实施多中心联合配送问题中, 是由于含有多个配送中心的物流企业中有着唯一的决策者或各决策者之间思想与行为高度协调一致, 且各配送中心之间不存在利益冲突或建有利益分配机制. 因此, 本文对MDVRPSDDSPJD进行研究不仅进一步拓展了VRP问题的理论研究, 也有利于提高物流配送活动的效率, 为制定科学合理的物流企业车辆调度计划提供理论依据, 具有重要的理论和实践价值.

图 1  MDVRPSDDSPJD的衍生进程

图 3  自适应变邻域文化基因算法框架图

图 4  编码方式示意图

本文针对多中心联合配送模式下集货需求随机的同时配集货车辆路径问题进行了研究, 主要结论如下.

1)本文提出的MDVRPSDDSPJD问题不仅考虑了多中心联合配送、客户及车辆资源共享, 而且考虑到客户同时具有配集货需求且集货需求为随机变量的情况, 是对MDVRP、VRPSDP等研究的进一步深化和拓展.

2)基于多中心联合配送的特点, 提出车辆返回规则. 即车辆从配送中心出发, 可返回任意配送中心, 但需保持每个配送中心车辆进出平衡. 经验证表明, 该规则较传统的车辆返回规则有明显的改进, 能够有效降低企业的路径成本.

3)设计的自适应变邻域文化基因算法, 将变邻域搜索算法引入文化基因算法的局部搜索策略中, 提高了算法的寻优性能; 设计的自适应邻域搜索次数策略和自适应劣解接受机制能够平衡算法进化所需的广度和深度, 提高了算法跳出局部最优的能力.

4)通过多组算例对本文的模型及算法进行验证, 结果表明, 所建的模型及设计的算法能有效解决MDVRPSDDSPJD问题, 同其他类型的算法进行比较, 本文算法寻优能力较强、搜索稳定, 具有较强的优势.

本文的研究能为具有多个配送中心的物流企业实施多中心联合配送提供较好的解决方案. 但需要指出的是, 物流企业可能面临多重不确定环境且车辆调度会受到客户时间窗因素的影响, 如何在时间窗约束下刻画和解决多重不确定环境下的车辆调度问题是未来需要继续研究的方向.

作者简介

范厚明

大连海事大学交通运输工程学院教授. 主要研究方向为交通运输系统规划与设计, 战略管理与系统规划. 本文通信作者. E-mail: fhm468@163.com

刘鹏程

大连海事大学交通运输工程学院硕士研究生. 主要研究方向为交通运输规划与管理. E-mail: lpc0369@163.com

刘浩

大连海事大学交通运输工程学院硕士研究生. 主要研究方向为物流工程与管理. E-mail: lhao66@126.com

侯登凯

大连海事大学交通运输工程学院博士研究生. 主要研究方向为交通运输规划与管理. E-mail: houdk@dlmusp.com