大規模かつ多様な問題に対応可能な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にて発表を行なった．

装箱问题是询问如何将多个物品装入一个容器中以使容器内的密度最大化的问题。在考虑实际问题中的打包时，三维装箱问题极其复杂，不可能在现实时间内找到精确的解决方案，人们提出了各种近似解决方法，包括使用强化学习的方法。特别是，使用深度强化学习的方法已显示出较高的准确性，并且有望提供比手动打包更准确的打包。然而，由于问题的复杂性，使用深度强化学习来学习装箱问题需要非常大的计算成本，并且研究主要集中在仅使用需要各种条件的装箱问题的小实例。提高深度强化学习的学习过程效率，使其更容易应用于基于较大实例或复杂约束的装箱问题，使得深度强化学习应用于更符合现实生活的装箱问题成为可能问题．．在本研究中，我们提出了一种结合启发式方法来限制使用深度强化学习解决装箱问题的搜索范围的方法。不是搜索容器内的所有空间，而是通过应用左下法和最佳拟合法等思想提前提出候选解决方案。事实证明，这可以显着减少搜索空间，同时保持解决方案的准确性，从而实现高效学习并降低计算成本。这项研究的结果已在国际会议“网格与云国际研讨会 (ISGC) 2023”上公布。