《European Journal of Operational Research》:A Tree Search-Based Heuristic for the Three-Dimensional Single Container Loading Problem
编辑推荐:
三维单容器装载问题(3D-SCLP)旨在用物品填充容器以最大化体积利用率。物品为矩形,可旋转,但仅允许正交放置。该问题与工业界高度相关,尤其在供应链物流中。启发式方法仍然是中小型和大规模实例最合适且广泛使用的方法。研究人员考虑将波束搜索(beam search
三维单容器装载问题(3D-SCLP)旨在用物品填充容器以最大化体积利用率。物品为矩形,可旋转,但仅允许正交放置。该问题与工业界高度相关,尤其在供应链物流中。启发式方法仍然是中小型和大规模实例最合适且广泛使用的方法。研究人员考虑将波束搜索(beam search)启发式嵌入双重努力机制(double-effort mechanism)中。它使用带有最大空余空间(maximal empty spaces)的覆盖表示(cover representation)来表示剩余空间,并以断头台模式(guillotine pattern)生成物品块。两阶段适应度函数(two-stage fitness function)选择块,贪婪搜索(greedy search)选择最有前途的部分装载。研究人员对该启发式提出了多项改进,包括用于表示剩余空间的特定数据结构、对元参数进行更深入的校准、避免重新计算装载的哈希结构(hash structures),以及两阶段适应度函数。在1,600个基准实例上的计算实验证明了所提出启发式的高性能。使用同一台计算机,研究人员的方法在30秒内实现了95.91%的平均体积利用率,在30秒时限内比现有技术(state-of-the-art)提高了+0.59%。在5秒内,实现了95.40%的结果,仍比现有技术高出+0.08%。所有这些改进在统计上显著,并在历史背景下代表了相当大的进步。2014年的文献方法需要500秒,实现了+0.42%的增益,而2017年的现有技术方法将运行时间减少到30秒,实现了+0.13%的增益。
**论文解读:基于树搜索的三维单容器装载问题启发式方法**
**研究背景与问题**
三维单容器装载问题(3D-SCLP)是物流与供应链管理中的核心优化问题,旨在将矩形物品正交放置于矩形容器内,最大化体积利用率。该问题被归类为NP-hard,实际应用中(如集装箱运输)常涉及中大规模实例,精确算法因计算时间过长而难以适用,启发式方法成为主流。过去15年间,基于树搜索的启发式方法(如波束搜索)取得了显著进展,但仍有改进空间:现有方法在30秒时间限制下平均体积利用率约为95.53%,且提升愈发困难。例如,2014年方法需500秒实现+0.42%的增益,2017年方法将时间降至30秒但仅提升+0.13%。因此,研究人员旨在进一步优化效率与质量,通过创新数据结构、参数自动配置、记忆化技术和自适应适应度函数,突破现有瓶颈。
**研究内容与结论**
研究人员提出了一种新的树搜索启发式方法,嵌入双重努力机制(double-effort mechanism),采用波束搜索(beam search)策略。该方法利用覆盖表示(cover representation)管理剩余空间,以断头台模式(guillotine pattern)生成物品块,并通过两阶段适应度函数(two-stage fitness function)和贪婪搜索(greedy search)选择块。提出的创新包括:缓存友好的数据结构(数组存储)、基于Zhu和Lim (2012)的体积损失估计、自动参数配置(通过irac工具)、记忆化表(memoization table)避免重复计算,以及基于容器利用率的两阶段适应度函数。在1,600个BR基准实例(Bischoff & Ratcliff, 1995; Davies & Bischoff, 1999)上,同一计算机条件下,30秒内平均体积利用率达95.91%,比现有技术(Araya et al., 2017a)高+0.59%;5秒内达95.40%,仍领先+0.08%。所有改进统计显著(贝叶斯分析与Wilcoxon符号秩检验证实)。该成果发表在《European Journal of Operational Research》。
**主要关键技术方法**
研究人员采用波束搜索(beam search)嵌入双重努力机制(double-effort mechanism),使用覆盖表示(cover representation)和最大空余空间(maximal empty spaces)管理剩余空间,并基于断头台模式(guillotine pattern)生成物品块。关键技术包括:缓存友好的数组数据结构存储剩余空间、基于Zhu和Lim (2012)的体积损失估计、通过irac工具自动配置两阶段适应度函数参数、记忆化表(memoization table)避免重复计算贪婪搜索中的状态。样本来源为Bischoff & Ratcliff (1995)和Davies & Bischoff (1999)的BR基准实例,共16类1,600个实例,涵盖从弱异质到强异质的物品类型。
**研究结果**
**数据结构与搜索算法的改进**:通过比较启发式VAN-H(使用研究人员提出的数据结构与接触搜索算法)与A(现有技术,采用Araya et al. (2017a)的实现),发现平均体积利用率提高0.20%,表明缓存友好的数据结构和优化接触搜索可加速探索。
**体积损失估计的影响**:比较VAN-H(使用Araya et al. (2017a)的体积损失估计)与AN-H(使用Zhu和Lim (2012)的估计),发现后者提高0.07%,说明Zhu和Lim (2012)的估计在重计算过程中具有优势。
**参数配置的影响**:比较AN-H(使用araya-config参数)与ON-H(使用研究人员自动配置的one-stage-config参数),发现后者提高0.16%,表明自动参数配置工具(irac)优于手动调参。
**记忆化的效果**:比较ON-H(无记忆化)与O-H(启用记忆化),发现平均体积利用率提高0.08%,同时运行时间减少约40%,说明记忆化可避免冗余计算且不影响决策质量。
**两阶段适应度函数的效果**:比较O-H(单阶段适应度函数)与H(两阶段适应度函数),发现总体提高0.08%,其中对于强异质实例(BR8-BR15)提高0.12%,表明两阶段函数在挑战性实例中更有效。
**与现有技术的整体比较**:启发式H在30秒内平均体积利用率95.91%,比现有技术A(95.31%)高0.59%;5秒版本(5-H)达95.40%,仍高于A的30秒结果。此外,H在500秒内达到96.36%,而A需约16倍时间才能达到相同结果。
**统计显著性**:贝叶斯分析显示,H在所有比较中优于A的概率接近1,Wilcoxon符号秩检验的p值均小于1.2×10
-89,证实改进统计显著。
**总结与结论**
研究人员提出了一种新颖的基于树搜索的三维单容器装载问题(3D-SCLP)启发式方法,整合了缓存友好数据结构、两阶段适应度函数和记忆化技术,提升了效率与解质量。在1,600个基准实例上的全面计算实验表明,所提出的启发式(及其所有版本)一致优于现有技术,在体积利用率上取得统计显著的增益,同时保持或缩短了计算时间,尤其在强异质实例中。研究结果得出几点重要见解:首先,经验评估与理论设计同等重要,缓存友好数据结构和接触搜索的优化带来了性能提升;其次,冗余消除(特别是记忆化)可显著减少搜索努力,应作为主要优化方向;第三,参数自动配置工具(如irac)优于手动方法;最后,有效启发式必须纳入提供决策影响全面信息的评估因素,使算法能适应问题场景变化,如将体积利用率融入块评估函数所展示的成功。尽管取得了进展,未来工作可探索改进的剩余空间表示算法(如混合或动态分区策略)、高级接触检测算法、动态参数调优、考虑实际约束(如货物稳定性、承重能力),以及将启发式与混合元启发式或精确算法集成。