Solving Logistic-Oriented Bin Packing Problems Through a Hybrid Quantum-Classical Approach

• URL: http://arxiv.org/abs/2308.02787v2
• Date: Mon, 21 Aug 2023 06:30:52 GMT
• Title: Solving Logistic-Oriented Bin Packing Problems Through a Hybrid Quantum-Classical Approach
• Authors: Sebasti\'an V. Romero, Eneko Osaba, Esther Villar-Rodriguez and Ant\'on Asla
• Abstract summary: Bin Packing Problem is a classic problem with wide industrial applicability. We resort to our previously published quantum-classical framework known as Q4RealBPP.
• Score: 0.44241702149260353
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Bin Packing Problem is a classic problem with wide industrial applicability. In fact, the efficient packing of items into bins is one of the toughest challenges in many logistic corporations and is a critical issue for reducing storage costs or improving vehicle space allocation. In this work, we resort to our previously published quantum-classical framework known as Q4RealBPP, and elaborate on the solving of real-world oriented instances of the Bin Packing Problem. With this purpose, this paper gravitates on the following characteristics: i) the existence of heterogeneous bins, ii) the extension of the framework to solve not only three-dimensional, but also one- and two-dimensional instances of the problem, iii) requirements for item-bin associations, and iv) delivery priorities. All these features have been tested in this paper, as well as the ability of Q4RealBPP to solve real-world oriented instances.

Related papers

• A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [66.61399765513383]
  We develop a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints. We demonstrate its effectiveness on two well-known real-world applications.
  arXiv  Detail & Related papers  (2024-06-14T15:59:36Z)
• QOPTLib: a Quantum Computing Oriented Benchmark for Combinatorial Optimization Problems [0.4972323953932129]
  We propose a quantum computing oriented benchmark for optimization. This benchmark, coined as QOPTLib, is composed of 40 instances equally distributed over four well-known problems. In this paper, we introduce a first full solving of QOPTLib using two solvers based on quantum annealing.
  arXiv  Detail & Related papers  (2024-04-24T13:02:33Z)
• 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)
• QAL-BP: An Augmented Lagrangian Quantum Approach for Bin Packing [4.589533935256401]
  The bin packing is a well-known NP-Hard problem in the domain of artificial intelligence. Recent advancements in quantum technologies have shown promising potential for achieving substantial computational speedup. We introduce QAL-BP, a novel Quadratic Unconstrained Binary Optimization (QUBO) formulation designed specifically for bin packing.
  arXiv  Detail & Related papers  (2023-09-22T07:37:20Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
  arXiv  Detail & Related papers  (2023-06-14T13:44:35Z)
• 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)
• Hybrid Approach for Solving Real-World Bin Packing Problem Instances Using Quantum Annealers [0.8434687648198277]
  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.
  arXiv  Detail & Related papers  (2023-03-01T14:04:50Z)
• Assessing requirements to scale to practical quantum advantage [56.22441723982983]
  We develop a framework for quantum resource estimation, abstracting the layers of the stack, to estimate resources required for large-scale quantum applications. We assess three scaled quantum applications and find that hundreds of thousands to millions of physical qubits are needed to achieve practical quantum advantage. A goal of our work is to accelerate progress towards practical quantum advantage by enabling the broader community to explore design choices across the stack.
  arXiv  Detail & Related papers  (2022-11-14T18:50:27Z)
• 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)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)

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.