Hybrid approach for solving real

Scientific Reports volume 13, Article number: 11777 (2023) Cite this article

418 Accesses

2 Altmetric

Metrics details

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: (1) package and bin dimensions, (2) overweight restrictions, (3) affinities among item categories and (4) preferences for item ordering. Q4RealBPP permits the solving of real-world oriented instances of 3 dBPP, contemplating restrictions well appreciated by industrial and logistics sectors.

The optimization on the packaging of products into a finite number of containers is a crucial daily task in the field of production and distribution. Depending on the characteristics of both packages and containers, multiple packaging problems can be formulated, generally known as Bin Packing Problems (BPP)1. Within this category, the one-dimensional BPP (1 dBPP) is considered as the simplest one2, whose goal is to pack all items into as few containers as possible. Many variants with a variable number of constraints have been proposed to deal with real situations in logistics and industry3. The three-dimensional BPP (3 dBPP)4, in which each package has three dimensions: height, width and depth, is the best-known and the most challenging variant. Highlighted in several studies5,6,7, 3 dBPP has a practical interest in many industrial settings. In recent years, it has been formulated to possess diverse and practical applications such as pallet loading8, road transportation9, air cargo10, etc. Due to its complexity, 3 dBPP is also recurrently employed as a benchmark for testing newly developed methods and mechanisms11,12.

On another front, quantum computing is still at its early stage but has gathered a lot of attention from the scientific community as it offers researchers and practitioners a revolutionary paradigm for tackling different kinds of practical optimization problems13,14,15,16. In particular, quantum annealers have been recently applied to a wide variety of optimization problems inspired by the fields from industry17, logistics18 and economics19. However, the research on BPP carried out in the quantum community is still scarce, even though BPP has been widely studied classically as an optimization problem.

The pioneering work on BPP in the field of quantum computing presents a hybrid quantum-classical method for solving the 1 dBPP20, whose solver is composed of two modules: (1) a quantum subroutine with which to search a set of feasible configurations to fill one single bin and (2) a classical computational heuristic which builds complete solutions employing the subsets given by the quantum subroutine. To deepen the performance of the quantum subroutine developed, further tests were conducted against a random sampling and a random walk-based heuristic21. Besides those two papers, an additional study formulates an atomic energy industry related problem as a 1 dBPP, solving it using the D-Wave quantum annealer22. Another works show quantum-inspired evolutionary computation techniques as an alternative to tackle BPP related problems23,24,25. Quantum-inspired techniques are a specific class of evolutionary algorithms which make use of quantum physics to define their operations and are designed to be executed on a classical computer26. Thus, they can not be executed on any quantum machine.

In contrast to 1 dBPP, tackling 3 dBPP in the quantum domain is much more challenging due to two related grounds: (1) its complexity, which increases as constraints from the real-world are taken into account and (2) the incipient state of development of the current commercial quantum computers with capacities still limited by decoherence and errors, which could be an obstacle to solve highly-constrained problems. In this paper, we present a hybrid quantum-classical computing framework for the real-world oriented 3 dBPP, which is coined as Quantum for Real Bin Packing Problem (Q4RealBPP). The proposed framework resorts to the the Leap Constrained Quadratic Model (CQM) Hybrid Solver (LeapCQMHybrid27) of D-Wave. At the same time, Q4RealBPP is built on an existing code28. This reference code is an excellent starting point, which paved the way for these two main contributions developed in this this work:

Efficiency of the code: in the reference code, the problem is formulated such that lots of variables (thus qubits) are needed. This issue meets the problem of feasibility in the context of quantum hardware in the noisy intermediate-scale quantum (NISQ) era29. Therefore, the optimization of the code is crucial for dealing with complex problems. Q4RealBPP provides a step forward on this aspect by exploring how the constraints coined as Intrinsic restrictions can be polished. These restrictions are the ones needed for the BPP definition (e.g. do not place cases outside a bin), and they were previously introduced in the reference code. Thus, the novel work performed on this specific facet has involved, among others, the redefinition of some mathematical formulas that define these intrinsic restrictions, and the elimination of a redundant optimization objective. Thanks to this procedure, problems can be formulated by using fewer variables, which directly impacts the capacity of the framework to address larger instances.

Applicability of the tool: the reference code is oriented toward solving the most basic variant of the 3 dBPP by only considering the dimension of both packages and bins. This setting falls far from real client demands, where other features such as weights, load balancing or incompatibilities,among others, are likely to take part. We have elaborated on this direction by implementing a set of constraints named Real-World BPP Restrictions. All these constraints represent an added value for Q4RealBPP, having required a significant extension of the mathematical formulation of the problem. We deepen in this aspect in following sections.

Taking these factors into account, Q4RealBPP is oriented to industrial and logistics related fields, contemplating problems such as the organization of port containers, the introduction of packages in delivery vans and trucks or the placement of foodstuffs on distribution pallets, among others. With the aid of a hybrid quantum-classical method, Q4RealBPP represents a solid step forward to solve 3 dBPP with the clear purpose of facing real-world focused problems well appreciated by final users and companies. Features contemplated by Q4RealBPP involve (1) dimensions of packages and bins, (2) maximum weight allowed per bin, (3) positive and negative affinities among item categories and (4) preferences for package ordering (in terms of load bearing and load balancing). To demonstrate its application, we have conducted an experimentation composed of 12 different instances serving as illustrative examples. Additionally, Q4RealBPP allows users to easily build flexible and well-defined instances to adapt a plethora of real-world situations to be solved in the quantum computer.

The rest of the article is organized as follows: in “Mathematical formulation” the 3 dBPP formulation and its corresponding notation are presented. Moreover, a detailed study of the computational resources needed for arbitrary instances is carried out. In “Experimental results”, the applicability of this tool is tested using a set of realistic instances as input. Finally, the conclusions led by the presented results and our future plans are given in “Conclusions and future work”.

In this section, we describe in detail the mathematical formulation of the 3 dBPP variant tackled in this research. First, input parameters and variables that compose the problem are shown in Table 1.

The 3 dBPP can be solved as an optimization problem where a suitable cost function to minimize must be defined. In our case, this cost function is represented as the sum of three objectives. The strength given to each objective, i.e. the relevance accounted for each one, is up to the user preferences just by multiplying each objective with a suitable weight. Thus, the problem can be stated as \(\min \text { }\sum _{i=1}^3\omega _io_i\) with \(\omega _i\) the weights of each objective \(o_i\). In our study, we will not consider this bias, i.e. \(\omega _i=1\text { }\forall i\).

The first and main objective minimizes the total amount of bins used to locate the packages. This can be achieved by minimizing

Additionally, for ensuring that items are packed from the floor to the top of the bin, avoiding solutions with floating packages, a second objective is defined by minimizing the average height of the items for all bins

Besides these two objectives reformulated from the reference code28, we further add a third optional objective \(o_3\) to take into account the load balancing feature. This concern is particularly important when air cargo planes and sailings are the chosen conveyance30,31, for example. In those situations, packages should be uniformly distributed around a given xy-coordinate inside the bin. We can tackle this by computing the so-called taxicab or Manhattan distance between items and the desired center of mass for each bin. As a result, the gaps between items are also reduced. Concerning this, the third objective to be minimized is

with

where \(0\le x_i< nL\) (bins stacked horizontally) and \(0\le y_i< W\) \(\forall i\in I\). This objective term minimizes for each item the distance between the center of mass projection in the xy-plane and the \(({\tilde{L}},{\tilde{W}})\) coordinate of each bin.

The objectives above defined are subject to certain restrictions, which are essential to derive realistic solutions. The whole pool of constraints is separated into two categories: the ones intrinsic to the BPP definition (intrinsic restrictions), and the ones relevant from a real-world perspective (real-world BPP restrictions).

Item orientations: the fact that inside a bin each item must have only one orientation can be implemented by using

Set of possible orientations \(k\in K_i\) for a given item i of dimensions \((l_i,w_i,h_i)\). (a) \(k = 1\), (b) \(k = 2\), (c) \(k = 3\), (d) \(k = 4\), (e) \(k = 5\), (f) \(k = 6\). See Table 2.

Orientations give rise to the effective length, width, and height of the items along x, y and z axes

and because of (5), only one term \(r_{i,k}\) is nonzero in each equation.

It should be deemed that there could be items with geometrical symmetries, as with cubic ones where rotations do not apply. Redundant and non-redundant orientations are considered in the reference code28. In our formulation, we previously check if these symmetries exist to define \(K_i\) for each item. Thanks to this, (6)–(8) are simplified filtering out redundant orientations and leading to a formulation which uses less variables (thus qubits) to represent the same problem, where \(\kappa =\sum _{i=1}^m|K_i|\le 6m\) variables \(r_{i,k}\) are needed. For \(i\in I_\text {c}\) with \(I_\text {c}{:}{=}\{i\in I\,|\,l_i=w_i=h_i\}\) (cubic items), we can set \(r_{i,1}=1\) and 0 otherwise, thus satisfying (5) in advance. In Table 2, we can see the non-redundant orientation sets for an item i depending on its dimensions. This simple mechanism reduces the complexity of the problem, being favourable for the quantum hardware to implement.

Non-overlapping restrictions: since we are considering rigid packages, i.e. they can not overlap, a set of restrictions need to be defined to overcome these configurations. For this purpose, at least one of these situations must occur (see Fig. 2)

As discussed with the orientation variable \(r_{i,k}\) in (5), the relative position between items i and k must be unique, so

Representation of \(b_{i,k,q}\) activated for all relative positions \(q\in Q\) between items i and k. See (9)–(14). Both are in contact but it is not mandatory. (a) \(b_{{i},{k},1}=1\), (b) \(b_{{i},{k},2}=1\), (c) \(b_{{i},{k},3}=1\), (d) \(b_{{i},{k},4}=1\), (e) \(b_{{i},{k},5}=1\), (f) \(b_{{i},{k},6}=1\).

Item and container allocation restrictions: the following set of restrictions guarantees an appropriate behaviour during item and bin assignment. In order to avoid packing duplicates of the same item, each item must go to exactly one bin, where

The following formula verifies if items are being packed inside bins that are already in use

so it activates \(v_j\) if needed during packaging. Bins can be activated sequentially to avoid duplicated solutions ensuring that

Bin boundary constraints: in order to contemplate bin boundaries, the following set of restrictions must be met

where (19) guarantees that items i placed inside the bin j are not outside of the last bin (n-th bin) along the x axis, (20) ensures that item i is located inside of its corresponding bin j along the x axis (activated if \(n>1\)), (21) confirms that item i placed inside the bin j is not outside along the y axis, while (22) ensures that item i allocated inside the bin j is not outside along the z axis.

In this subsection we introduce those restrictions related with the operative perspective of the problem, i.e. the ones that consider real-world industrial situations. All of the following constraints are optional in our formulation.

Overweight restriction: the weight of each package and the maximum capacity of containers are common contextual data to avoid exceeding the maximum weight capacity of bins, so avoid overloaded containers. We can introduce this restriction as

This restriction is activated if the maximum capacity M is given.

Affinities among package categories: there are commonly preferences for separating some packages into different bins (negative affinities or incompatibilities) or, on the contrary, gathering them into the same container (positive affinities). Let us consider \(I_\alpha {:}{=}\{i\in I\text { }|\text { }{} \texttt {id}\text { of }i\text { is equal to }\alpha \}\), i.e. \(I_\alpha \subset I\) is a subset of all items labelled with id equal to \(\alpha\). Given a set of p negative affinities \(A^\text {neg}{:}{=}\{(\alpha _1,\beta _1),\dots ,(\alpha _p,\beta _p)\}\), then the restriction will be

To activate this restriction, a set of incompatibilities must be given. Moreover, we can satisfy in advance \(\nu {:}{=}6n\sum _{(\alpha ,\beta )\in A^\text {neg}}|I_\alpha ||I_\beta |\) non-overlapping constraints (see (9)–(14)), leading to a simpler formulation. Conversely, given a set of positive affinities \(A^\text {pos}\) as stated with \(A^\text {neg}\), then the restriction will be posed such that

This restriction is activated if a set of positive affinities is given. If \(A^\text {pos}\) and \(A^\text {neg}\) are given, then both restrictions can be introduced using just one formula adding (24) and (25).

Preferences in relative positioning: relative positioning of items demands that some of them must be placed in a specific position with respect other existing items. This preference allows introducing the ordering of a set of packages according to their positions with respect to the axes. Thus, this preference assists in ordering for many real cases such as: parcel delivery (an item i that has to be delivered before item k will be preferably placed closer to the trunk door) or load bearing (no heavy package should rest over flimsy packages), among others.

Regarding this preference, we can define two different perspectives to treat relative positioning:

Positioning to avoid (\(P_q^{-}\)): list of items (i, k) should not be in the relative position \(q\in Q\) specified. So, \(b_{i,k,q}=0\) is expected, favouring configurations where the solver selects \(q'\in Q\) with \(q'\ne q\) for the relative positioning of items (i, k).

Positioning to favour (\(P_q^{+}\)): list of items (i, k) should be in a certain relative position q. Activated this preference, \(b_{i,k,q}=1\) ought to hold and consequently, \(b_{i,k,q'}=0 \ \forall q'\ne q\).

Formally, these preferences are written as

These preferences could be also treated as compulsory pre-selections. In such case, the number of variables needed would be reduced, so would the search space. If we let \(\smash [t]{p^{-}=\sum _{q\in Q}|P_q^{-}|}\) and \(\smash [t]{p^{+}=\sum _{q\in Q}|P_q^{+}|}\) with \(\smash [t]{P^{-}_q\cap P^{+}_{q'}=\varnothing }\), based on (15), the amount of variables reduced would be given by \(\smash [t]{p^{-}+6p^{+}}\). Moreover, \(\smash [t]{n(p^{-}+5p^{+})}\) non-overlapping constraints (see (9)–(14)) are satisfied directly and can be ignored, thus simplifying the problem. In this paper, for the sake of clarity, these preferences have been applied for load bearing purposes as hard constraints (HC), as explained in the upcoming “Experimental results”.

Load balancing: to activate this restriction, a target center of mass must be given. Global positions with respect to the bin as a whole (as described in objective \(o_3\) in (3)), are fixed using the following constraints

This feature is represented in Fig. 3 for \(({\tilde{L}},{\tilde{W}})=(L/2,W/2)\), whose red line shows the available \({\tilde{x}}_i\) and \({\tilde{y}}_i\) values (see (4)).

Representation of available \({\tilde{x}}_i\) and \({\tilde{y}}_i\) values ensured by the constraints given in (27) for \(({\tilde{L}},{\tilde{W}}) = (L/2,W/2)\).

Regarding the complexity of the 3 dBPP proposed in this research, the total amount of variables needed to tackle an arbitrary instance is given in Table 3, where our formulation scales as \({\mathscr {O}}[m^2+nm]\) in terms of variables. Additionally, the total amount of constraints required is provided in Table 4, whose quantity grows quadratically as \({\mathscr {O}}[m^2+nm]\).

In this section, we conduct an experimentation to demonstrate the applicability of Q4RealBPP, where the problem has been modelled as a CQM and then solved by the LeapCQMHybrid provided by D-Wave27. Initially, it should be made clear that CQM refers to the mathematical model that uses quadratic objective functions and quadratic constraints on binary and integer variables. As this concept was introduced by D-Wave Systems, this company developed the hybrid solver LeapCQMHybrid, which also supports the definition of equality and inequality requirements. This feature brings an advantage compared to Quadratic Unconstrained Binary Optimization (QUBO), which is the native formulation for the QPUs. The CQM model and the LeapCQMHybrid introduce some interesting shortcuts for a more friendly use, allowing the user to provide a problem in a more intuitive and descriptive way, avoiding the translation into a mathematical formulation in the shape of a QUBO matrix.

More specifically, the LeapCQMHybrid workflow is as follows: first, a classical front end receives the CQM formulation of the problem as input. Then, it runs a number of parallel computation threads, where each of them are composed of two parts: a heuristic module (HM) and a quantum module (QM). On the one hand, HM tries to solve the problem by using a state of the art heuristic solver. On the other hand, QM aids this resolution by formulating different quantum queries aiming to guide the HM toward promising regions of the search space, or finding improvements to already existing solutions. This QM performs its operations by acceding the latest available quantum computer of D-Wave. At the time of writing this paper, the most updated architecture is the Advantage_system, composed of 5616 qubits organized in a Pegasus topology. Hybrid solvers from D-Wave Systems are proprietary, so additional details regarding the quantum subroutines and the number of qubits used to solve a problem are not publicly available. Interested readers can refer to the related report provided by D-Wave for more information32.

Having said that, for demonstrating the applicability of Q4RealBPP, we have built an ad-hoc benchmark composed of 12 different instances of the 3 dBPP. In order to analyze the impact of every restriction, each instance is devoted to evaluate a specific feature of the problem. Also, we have generated two specific instances that bring together all the restrictions of our modelled 3 dBPP. We describe in Table 5 the main characteristics of the 12 used instances.

The whole dataset has been generated employing an own-developed Python script (coined as Q4RealBPP-DataGen). In order this paper to be as self-contained as possible, we briefly explain how Q4RealBPP-DataGen works. This script performs two steps to generate Q4RealBPP-compliant instances: firstly Q4RealBPP-DataGen randomly generates a defined number of items, following the package distribution and dimensions established in Ref.8. Then, the attributes regarding overweight restriction, affinities among item categories, load bearing and load balancing are completed by means of Q4RealBPP-DataGen. These constraints are randomly configured by the generator, except for the last two (load bearing and load balancing). These last features, as well as the bin dimensions, have been empirically set, in the search of a realistic scenario. It should be clarified that Q4RealBPP is a flexible framework, letting users to build their own setting not only configuring the instance of the problem but also by activating or deactivating the real-world oriented restrictions. For more information, the complete benchmark of instances and Q4RealBPP-DataGen are openly available in33. Furthermore, a deep explanation about how the dataset has been generated as well as the format of each instances is provided in34.

In our specific use case, the preferences in relative positioning (see real-world BPP restrictions) are tested as HC for load bearing. Accounting fragility issues, one could apply the rule of choosing pairs of packages to decide on what height to place each of them based on a mass ratio \(\eta\) (assuming that weight is related to fragility). Thus, defining \(P_3^{-}=\{(i,k)\in I^2\text { }|\text { }i<k\text { and }\mu _k/\mu _i>\eta \}\) (so \(b_{i,k,3}=0\text { }\forall (i,k)\in P_3^{-}\)) and \(P^{-}_6=\{(i,k)\in I^2\text { }|\text { }i<k,\text { and }\mu _i/\mu _k>\eta \}\) (so \(b_{i,k,6}=0\text { }\forall (i,k)\in P_6^{-}\)), this instantiation avoid configurations where items whose mass are more than \(\eta\) times the mass of other ones are placed above of them.

Figure 4 represents the results provided by Q4RealBPP for each of the instances described in Table 5. Regarding the running time, we have empirically determined the time it takes for the LeapCQMHybrid to resolve these instances to be \({30}\,{\textrm{s}}\), presenting a maximum Quantum Processing Unit (QPU) access time of \({0.032}\,{\textrm{s}}\) per execution. Lastly, for interested readers, all obtained results are freely available33.

(a) Colour palette used in the solved instances. (b)–(m) Brief description of instances given in Table 5 and solutions provided by Q4RealBPP. Red lines show the bin boundaries. The activated restrictions work as expected.

Besides that, we have conducted additional experimentation with the goal of further understanding the performance of Q4RealBPP. For this purpose, we have solved all the instances described in Table 5 under different time limits. Thus, 10 copies of each instance were executed independently with time limits set at 5, 10, 30, and 60 s. In the top of Fig. 5, the obtained results are shown using the mean \(\mu\) and standard deviation \(\sigma\) of the energy value \(\{e_i\}_{i=1}^{10}\) (where energy represents the sum of the objective values to optimize), being \(e_i\) the i-th energy returned by the solver upon the assigned time limit for each instance. Moreover, the mean QPU access time in nanoseconds is also attached. As a complementary analysis, in the botton part of Fig. 5, since the returned energies vary considerably depending on the nature of the instance, we have computed the deviation around the mean energies in terms of

for illustrating more clearly the stability of the solution. This additional analysis is depicted in the bottom part of Fig. 5.

Three main conclusions can be drawn from Fig. 5: (1) generally, the longer the time limit given, the lower the energy returned (thus the better solution quality); (2) the deviation around the mean values of the objective function remains stable against the different time limits given as well as it does not show a remarkable dependency with the nature of the instance studied; and (3) although different time limits have been given to the solver, the QPU access time did not vary significantly for each one, indicating that the optimization process on the LeapCQMHybrid workflow mainly relies on the heuristic module of the solver. Despite the clear behaviour exhibited by our results, further work should be done for having a deeper understanding of how the presented framework performs.

Top: mean energy values with their corresponding standard deviation for the 10 runs belonging to each instance. From left to right on each instance, the time limits given to the solver are \({5}\,{\textrm{s}}\), \({10}\,{\textrm{s}}\), \({30}\,{\textrm{s}}\) and \({60}\,{\textrm{s}}\). Numbers placed above and below the shaded areas show the mean QPU access time for every time limit within each instance (in units of nanoseconds). Bottom: using (28), deviation around the mean energy of the results depicted above. For both plots, shaded area shows the region where the minimum and maximum values fell during the study.

In this work we have presented Q4RealBPP, a quantum-classical framework for solving real-world instances of the 3 dBPP. This software can be easily used for both end-users and practitioners for dealing with 3 dBPP instances considering constraints such as the weight, load bearing, package categories and load balancing.

To prove the applicability of Q4RealBPP, we have tested it over 12 instances of different nature, with the main intention of showcasing the capacity of the method to encompass real-world constraints. As depicted in Fig. 4, Q4RealBPP has successfully tackled all the generated instances, contemplating different real-world situations. Particularly noteworthy are the last two instances, 3dBPP_11 and 3dBPP_12 (Fig. 4l,m, respectively), where all the constraints are activated.

The future work comprises the following interests: first, we have planned to develop a more advanced version of the Q4RealBPP to generalize the framework to other BPP variants, and consider further features such as multi-class categorization of items. Also, we have the intention of exploiting this framework in conjunction with complementary Artificial Intelligence algorithms to enhance its potential real-world applications. Finally, a thorough comparison among Q4RealBPP and any traditional artificial intelligence method would contribute to a deeper analysis of our framework in terms of robustness of results and execution times. Anyway, this valuable comparison would inevitably entail the implementation of a classical technique completely adapted to the 3 dBPP problem described in this paper. For this reason, we have settled this action as future work. As a final conclusion, authors consider that further work is needed in this regard, so we encourage researchers in this field to use and adapt our benchmarking instances33 to test and compare already existing and novel frameworks.

The code is available from the corresponding author (E.O.) upon reasonable request. The data used, as well as Q4RealBPP-DataGen and all the results discussed in this work, are available at http://dx.doi.org/10.17632/y258s6d939.1.

Garey, M. R. & Johnson, D. S. Approximation algorithms for bin packing problems: A survey. In Analysis and Design of Algorithms in Combinatorial Optimization 147–172 (Springer, 1981).

Chapter Google Scholar

Munien, C. & Ezugwu, A. E. Metaheuristic algorithms for one-dimensional bin-packing problems: A survey of recent advances and applications. J. Intell. Syst. 30, 636–663 (2021).

Google Scholar

Delorme, M., Iori, M. & Martello, S. Bin packing and cutting stock problems: Mathematical models and exact algorithms. Eur. J. Oper. Res. 255, 1–20 (2016).

Article MathSciNet MATH Google Scholar

Martello, S., Pisinger, D. & Vigo, D. The three-dimensional bin packing problem. Oper. Res. 48, 256–267 (2000).

Article MathSciNet MATH Google Scholar

Lodi, A., Martello, S. & Vigo, D. Heuristic algorithms for the three-dimensional bin packing problem. Eur. J. Oper. Res. 141, 410–420 (2002).

Article MathSciNet MATH Google Scholar

Yang, H. & Shi, J. A hybrid cd/vnd algorithm for three-dimensional bin packing. In 2010 Second International Conference on Computer Modeling and Simulation, vol. 3, 430–434 (IEEE, 2010).

Parreño, F., Alvarez-Valdés, R., Oliveira, J. F. & Tamarit, J. M. A hybrid grasp/vnd algorithm for two-and three-dimensional bin packing. Ann. Oper. Res. 179, 203–220 (2010).

Article MathSciNet MATH Google Scholar

Elhedhli, S., Gzara, F. & Yildiz, B. Three-dimensional bin packing and mixed-case palletization. Informs J. Optim. 1, 323–352 (2019).

Article MathSciNet Google Scholar

Ramos, A. G., Silva, E. & Oliveira, J. F. A new load balance methodology for container loading problem in road transportation. Eur. J. Oper. Res. 266, 1140–1152 (2018).

Article MathSciNet MATH Google Scholar

Paquay, C., Schyns, M. & Limbourg, S. A mixed integer programming formulation for the three-dimensional bin packing problem deriving from an air cargo application. Int. Trans. Oper. Res. 23, 187–213 (2016).

Article MathSciNet MATH Google Scholar

Paquay, C., Limbourg, S., Schyns, M. & Oliveira, J. F. Mip-based constructive heuristics for the three-dimensional bin packing problem with transportation constraints. Int. J. Prod. Res. 56, 1581–1592 (2018).

Article MATH Google Scholar

Silva, E. F., Machado Toffolo, T. A. & Wauters, T. Exact methods for three-dimensional cutting and packing: A comparative study concerning single container problems. Comput. Oper. Res. 109, 12–27 (2019).

Article MathSciNet MATH Google Scholar

Lucas, A. Ising formulations of many np problems. Front. Phys. 2, 25 (2014).

Article Google Scholar

Gill, S. S. et al. Quantum computing: A taxonomy, systematic review and future directions. Softw. Pract. Exp. 52, 66–114 (2022).

Article Google Scholar

Chandarana, P. et al. Meta-learning digitized-counterdiabatic quantum optimization. arXiv:2206.09966 (arXiv preprint) (2022).

Huang, T. et al. Time-optimal quantum driving by variational circuit learning. arXiv:2211.00405 (arXiv preprint) (2022).

Luckow, A., Klepsch, J. & Pichlmeier, J. Quantum computing: Towards industry reference problems. Digitale Welt 5, 38–45 (2021).

Article Google Scholar

Osaba, E., Villar-Rodriguez, E. & Oregi, I. A systematic literature review of quantum computing for routing problems. IEEE Access 20, 20 (2022).

Google Scholar

Orús, R., Mugel, S. & Lizaso, E. Quantum computing for finance: Overview and prospects. Rev. Phys. 4, 100028 (2019).

Article Google Scholar

Garcia-de Andoin, M., Osaba, E., Oregi, I., Villar-Rodriguez, E. & Sanz, M. Hybrid quantum-classical heuristic for the bin packing problem. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, 2214–2222 (Association for Computing Machinery, 2022).

De Andoin, M. G., Oregi, I., Villar-Rodriguez, E., Osaba, E. & Sanz, M. Comparative benchmark of a quantum algorithm for the bin packing problem. In 2022 IEEE Symposium Series on Computational Intelligence (SSCI), 930–937 (2022).

Bozhedarov, A. et al. Quantum and quantum-inspired optimization for solving the minimum bin packing problem. arXiv:2301.11265 (arXiv preprint) (2023).

Layeb, A. & Boussalia, S. R. A novel quantum inspired cuckoo search algorithm for bin packing problem. Int. J. Inf. Technol. Comput. Sci. 4, 58–67 (2012).

Google Scholar

Zendaoui, Z. & Layeb, A. Adaptive cuckoo search algorithm for the bin packing problem. In Modelling and Implementation of Complex Systems 107–120 (Springer, 2016).

Chapter Google Scholar

Layeb, A. & Boussalia, S. R. A novel greedy quantum inspired cuckoo search algorithm for variable sized bin packing problem. Int. J. Math. Oper. Res. 6, 732–751 (2014).

Article MathSciNet Google Scholar

Zhang, G. Quantum-inspired evolutionary algorithms: A survey and empirical study. J. Heurist. 17, 303–351 (2011).

Article MATH Google Scholar

D-Wave Developers. Measuring Performance of the Leap Constrained Quadratic Model Solver. Tech. Rep. 14-1065A-A, D-Wave Systems Inc. (2022).

D-Wave Ocean Developers Team. 3d-bin-packing (GitHub repository) (2022). Last retrieved 2023/02/27.

Preskill, J. Quantum computing in the NISQ era and beyond. Quantum 2, 79 (2018).

Article Google Scholar

Dahmani, N. & Krichen, S. Solving a load balancing problem with a multi-objective particle swarm optimisation approach: Application to aircraft cargo transportation. Int. J. Oper. Res. 27, 62–84 (2016).

Article MathSciNet MATH Google Scholar

Zhu, R. & Wang, L. Research on real-time channel optimization of ship based on load balancing algorithm. In The 29th International Ocean and Polar Engineering Conference (OnePetro, 2019).

D-Wave Developers. Hybrid solver for constrained quadratic models. Tech. Rep. 14-1055A-A, D-Wave Systems Inc. (2021).

Osaba, E., Villar, E. & V. Romero, S. Benchmark dataset and instance generator for real-world 3dbpp. https://doi.org/10.17632/y258s6d939.1 (2023). Online at Mendeley Data.

Osaba, E., Villar-Rodriguez, E. & Romero, V. S. Benchmark dataset and instance generator for real-world three-dimensional bin packing problems. Data Brief 20, 109309 (2023).

Article Google Scholar

Download references

This work was supported by the Basque Government through HAZITEK program (Q4_Real project, ZE-2022/00033), and by the Spanish CDTI through Proyectos I+D Cervera 2021 Program (QOptimiza project, 095359) and Misiones Ciencia e Innovación Program (CUCO) under Grant MIG-20211005.

TECNALIA, Basque Research and Technology Alliance (BRTA), 48160, Derio, Spain

Sebastián V. Romero, Eneko Osaba, Esther Villar-Rodriguez, Izaskun Oregi & Yue Ban

EUNEIZ, 01013, Vitoria-Gasteiz, Spain

Izaskun Oregi

You can also search for this author in PubMed Google Scholar

You can also search for this author in PubMed Google Scholar

You can also search for this author in PubMed Google Scholar

You can also search for this author in PubMed Google Scholar

You can also search for this author in PubMed Google Scholar

All authors conceived the research. S.V.R. formulated the problem and developed the code. E.V.R. formulated and developed the instance generator. S.V.R. and E.O. conceived and conducted the experiments. All authors wrote the manuscript. All authors reviewed the manuscript.

Correspondence to Eneko Osaba.

The authors declare no competing interests.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Reprints and Permissions

V. Romero, S., Osaba, E., Villar-Rodriguez, E. et al. Hybrid approach for solving real-world bin packing problem instances using quantum annealers. Sci Rep 13, 11777 (2023). https://doi.org/10.1038/s41598-023-39013-9

Download citation

Received: 06 March 2023

Accepted: 18 July 2023

Published: 21 July 2023

DOI: https://doi.org/10.1038/s41598-023-39013-9

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

By submitting a comment you agree to abide by our Terms and Community Guidelines. If you find something abusive or that does not comply with our terms or guidelines please flag it as inappropriate.