大規模かつ多様な問題に対応可能な3次元パッキング問題解法

可处理大规模、多样化问题的3D打包问题求解方法

基本信息

批准号：
21K12030
负责人：
間下以大
金额：
$ 2.66万
依托单位：
Osaka University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2021
资助国家：
日本
起止时间：
2021-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

Bin Packing問題とは，いくつかの荷物をContainerの中に詰め込む時，Container内の稠密度を最大とするためにはどのような詰め込み方をするとよいかを求める問題のことである．現実問題におけるPackingを考えた時，3次元のBin Packing問題は非常に複雑であり，現実的な時間内に厳密解を求めることができない.そのため，ヒューリスティックな手法をはじめとし，遺伝的アルゴリズムや深層強化学習を用いた手法など様々な近似解法が提案されている．特に深層強化学習を用いた手法は高い精度を示しており，人手による詰め込みを上回る精度の詰め込みが期待されている．しかし深層強化学習によるBin Packing問題の学習は，その問題の複雑さから非常に大きな計算コストを必要とし，様々な条件が求められるBin Packing問題において小さなインスタンスのみによる研究が主となっている．深層強化学習の学習過程の効率化はより大きなインスタンス，または複雑な制約にもとづくBin Packing問題への適用を簡単にし，より現実問題に則したBin Packing問題への深層強化学習の適用を可能とする．本研究では深層強化学習を用いたBin Packing問題の解法においてヒューリスティックな手法による探索範囲の制限を取り入れる手法の提案を行った．Container内のすべての空間について探索を行わず，Bottom-Left法やBest-Fit法といった考えを適用することにより解の候補を事前に提示する．これにより解の精度を保ちつつ，探索空間が大幅に減少し，効率的な学習及び計算コストの削減の効果があることを示した．この研究成果は国際会議，International Symposium on Grids & Clouds (ISGC) 2023にて発表を行なった．

垃圾箱包装问题是寻求如何在容器中打包一些行李以最大化容器中的密度。当考虑到现实中的包装时，已经提出了各种近似解决方案，例如使用增强学习的方法，就无法在现实的时间内寻求严格的解决方案。特别是，使用深度增强学习的方法表现出很高的精度，并有望用手工填充的精度包装。但是，通过深度增强学习来学习垃圾箱包装问题需要由于问题的复杂性而产生的计算成本很高，并且主要由需要各种条件的垃圾箱包装问题中的小实例进行研究。深度增强学习的学习过程的效率使得基于更大实例或复杂的约束将垃圾包装问题应用于更容易问题。。在这项研究中，我们提出了一种使用人文主义方法来通过深层增强学习来解决垃圾箱包装问题的方法，以纳入搜索范围的限制。我们将通过应用诸如左下和最佳拟合方法之类的想法的情况下提前提出解决方案的候选人，而无需探索容器中的所有空间。这表明在保持解决方案的准确性时，搜索空间已大大降低，并且有效学习和计算成本的效果降低了。这项研究的结果在国际网格和班级国际会议上宣布了2023年。