Identify patterns in online bin packing problem: an adaptive pattern-based algorithm

Research output: Journal PublicationArticlepeer-review

Abstract

Bin packing is a typical optimization problem with many real-world application scenarios. In the online bin packing problem, a sequence of items is revealed one at a time, and each item must be packed into a bin immediately after its arrival. Inspired by duality in optimization, we proposed pattern-based adaptive heuristics for the online bin packing problem. The idea is to predict the distribution of items based on packed items, and to apply this information in packing future arrival items in order to handle uncertainty in online bin packing. A pattern in bin packing is a combination of items that can be packed into a single bin. Patterns selected according to past items are adopted and periodically updated in scheduling future items in the algorithm. Symmetry in patterns and the stability of patterns in the online bin packing problem are discussed. We have implemented the algorithm and compared it with the Best-Fit in a series of experiments with various distribution of items to show its effectiveness.

Original languageEnglish
Pages (from-to)1301
JournalSymmetry
Volume14
Issue number7
DOIs
Publication statusPublished - Jul 2022

Keywords

  • bin packing problem
  • heuristic
  • pattern recognition
  • stability

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Chemistry (miscellaneous)
  • Mathematics (all)
  • Physics and Astronomy (miscellaneous)

Fingerprint

Dive into the research topics of 'Identify patterns in online bin packing problem: an adaptive pattern-based algorithm'. Together they form a unique fingerprint.

Cite this