颜 瑞，朱晓宁，张 群，戚耀元，蔺俞铮

(1. 北京信息科技大学，北京 100192；2.北京科技大学，北京 100083)



考虑二维装箱约束的多车场带时间窗的车辆路径问题模型及算法研究

颜 瑞1，朱晓宁2，张 群2，戚耀元2，蔺俞铮1

(1. 北京信息科技大学，北京 100192；2.北京科技大学，北京 100083)

研究包含时间窗、多车场因素的二维装箱车辆路径问题，建立相应的数学模型，并提出求解该问题的一种新的混合算法，混合算法由量子粒子群算法和引导式局部搜索算法组成。其中，量子粒子群算法用于求解车辆路径问题，引导式局部搜索算法用于求解可行装箱方案。在引导式局部搜索算法中，提出一种基于最小浪费原则的启发式装箱规则，以灵活确定待装货物和装货空间之间的匹配关系，减少重复确定装箱方案所消耗的时间。设计了两组数值试验：第一组基于标准算例库，并将混合算法计算结果与已有文献中的结果进行对比；第二组基于随机生成的新算例，新算例给出多车场和时间窗数据，用于演示混合算法对新模型的计算过程和计算结果。两组数值试验的结果表明，混合算法在效率和性能方面均有较好的表现，计算结果和计算时间均优于已有文献，且混合算法能够较好的求解包含时间窗、多车场因素的二维装箱车辆路径问题模型。

车辆路径问题；二维装箱问题；量子粒子群算法；多车场；时间窗

1 引言

二维装箱约束的车辆路径问题(Two-Dimensional Loading Capacitated Vehicle Routing Problem，2L-CVRP)是带容量约束的车辆路径问题(Capacitated Vehicle Routing Problem，CVRP)和二维装箱问题(Two-Dimensional Bin Packing Problem，2BPP)的联合优化问题，近年来逐渐引起了相关领域学者的关注。……