Hybrid Approach for Solving Real-World Bin Packing Problem Instances Using Quantum Annealers

• URL: http://arxiv.org/abs/2303.01977v3
• Date: Thu, 25 May 2023 15:07:46 GMT
• Title: Hybrid Approach for Solving Real-World Bin Packing Problem Instances Using Quantum Annealers
• Authors: Sebasti\'an V. Romero, Eneko Osaba, Esther Villar-Rodriguez, Izaskun Oregi and Yue Ban
• Abstract summary: We introduce a hybrid quantum-classical framework for solving real-world three-dimensional Bin Packing Problems (Q4RealBPP) Q4RealBPP permits the solving of real-world oriented instances of 3dBPP, contemplating restrictions well appreciated by industrial and logistics sectors.
• Score: 0.8434687648198277
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Efficient packing of items into bins is a common daily task. Known as Bin Packing Problem, it has been intensively studied in the field of artificial intelligence, thanks to the wide interest from industry and logistics. Since decades, many variants have been proposed, with the three-dimensional Bin Packing Problem as the closest one to real-world use cases. We introduce a hybrid quantum-classical framework for solving real-world three-dimensional Bin Packing Problems (Q4RealBPP), considering different realistic characteristics, such as: i) package and bin dimensions, ii) overweight restrictions, iii) affinities among item categories and iv) preferences for item ordering. Q4RealBPP permits the solving of real-world oriented instances of 3dBPP, contemplating restrictions well appreciated by industrial and logistics sectors.

Related papers

• Solving a Real-World Package Delivery Routing Problem Using Quantum Annealers [0.44241702149260353]
  This research focuses on the conjunction between quantum computing and routing problems. The main objective of this research is to present a solving scheme for dealing with realistic instances.
  arXiv  Detail & Related papers  (2024-03-22T11:16:11Z)
• Machine Learning for the Multi-Dimensional Bin Packing Problem: Literature Review and Empirical Evaluation [52.560375022430236]
  Bin Packing Problem (BPP) is a well-established optimization (CO) problem. In this article, we first formulate BPP, introducing its variants and practical constraints. Then, a comprehensive survey on machine learning for multi-dimensional BPP is provided.
  arXiv  Detail & Related papers  (2023-12-13T12:39:25Z)
• Fast Neighborhood Search Heuristics for the Colored Bin Packing Problem [0.0]
  The Colored Bin Packing Problem (CBPP) is a generalization of the Bin Packing Problem (BPP) CBPP consists of packing a set of items, each with a weight and a color, in bins of limited capacity. We propose an adaptation of BPPs and new algorithms for the CBPP.
  arXiv  Detail & Related papers  (2023-10-06T04:14:11Z)
• Solving Logistic-Oriented Bin Packing Problems Through a Hybrid Quantum-Classical Approach [0.44241702149260353]
  Bin Packing Problem is a classic problem with wide industrial applicability. We resort to our previously published quantum-classical framework known as Q4RealBPP.
  arXiv  Detail & Related papers  (2023-08-05T04:36:33Z)
• Convolutional Occupancy Models for Dense Packing of Complex, Novel Objects [75.54599721349037]
  We present a fully-convolutional shape completion model, F-CON, that can be easily combined with off-the-shelf planning methods for dense packing in the real world. We also release a simulated dataset, COB-3D-v2, that can be used to train shape completion models for real-word robotics applications. Finally, we equip a real-world pick-and-place system with F-CON, and demonstrate dense packing of complex, unseen objects in cluttered scenes.
  arXiv  Detail & Related papers  (2023-07-31T19:08:16Z)
• CAR: Conceptualization-Augmented Reasoner for Zero-Shot Commonsense Question Answering [56.592385613002584]
  We propose Conceptualization-Augmented Reasoner (CAR) to tackle the task of zero-shot commonsense question answering. CAR abstracts a commonsense knowledge triple to many higher-level instances, which increases the coverage of CommonSense Knowledge Bases. CAR more robustly generalizes to answering questions about zero-shot commonsense scenarios than existing methods.
  arXiv  Detail & Related papers  (2023-05-24T08:21:31Z)
• Benchmark dataset and instance generator for Real-World Three-Dimensional Bin Packing Problems [1.035593890158457]
  The benchmark was initially proposed to evaluate the performance of quantum solvers. The characteristics of this set of instances were designed according to the current limitations of quantum devices. The data introduced in this article provides a baseline that will encourage quantum computing researchers to work on real-world bin packing problems.
  arXiv  Detail & Related papers  (2023-04-28T09:29:43Z)
• MetaGraspNet: A Large-Scale Benchmark Dataset for Scene-Aware Ambidextrous Bin Picking via Physics-based Metaverse Synthesis [72.85526892440251]
  We introduce MetaGraspNet, a large-scale photo-realistic bin picking dataset constructed via physics-based metaverse synthesis. The proposed dataset contains 217k RGBD images across 82 different article types, with full annotations for object detection, amodal perception, keypoint detection, manipulation order and ambidextrous grasp labels for a parallel-jaw and vacuum gripper. We also provide a real dataset consisting of over 2.3k fully annotated high-quality RGBD images, divided into 5 levels of difficulties and an unseen object set to evaluate different object and layout properties.
  arXiv  Detail & Related papers  (2022-08-08T08:15:34Z)
• Multi-Objective Constrained Optimization for Energy Applications via Tree Ensembles [55.23285485923913]
  Energy systems optimization problems are complex due to strongly non-linear system behavior and multiple competing objectives. In some cases, proposed optimal solutions need to obey explicit input constraints related to physical properties or safety-critical operating conditions. This paper proposes a novel data-driven strategy using tree ensembles for constrained multi-objective optimization of black-box problems.
  arXiv  Detail & Related papers  (2021-11-04T20:18:55Z)
• A Generalized Reinforcement Learning Algorithm for Online 3D Bin-Packing [7.79020719611004]
  We propose a Deep Reinforcement Learning (Deep RL) algorithm for solving the online 3D bin packing problem. The focus is on producing decisions that can be physically implemented by a robotic loading arm. We show that the RL-based method outperforms state-of-the-art online bin packings in terms of empirical competitive ratio and volume efficiency.
  arXiv  Detail & Related papers  (2020-07-01T13:02:04Z)
• Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive [57.47546090379434]
  We study the public persuasion problem in the general setting with: (i) arbitrary state spaces; (ii) arbitrary action spaces; (iii) arbitrary sender's utility functions. We provide a quasi-polynomial time bi-criteria approximation algorithm for arbitrary public persuasion problems that, in specific settings, yields a QPTAS.
  arXiv  Detail & Related papers  (2020-02-12T18:59:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.