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

Sebastián V. Romero¹, Eneko Osaba^1†, Esther Villar-Rodriguez¹ and Antón Asla² 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).^†Corresponding Author.¹Sebastián V. Romero, Eneko Osaba, and Esther Villar-Rodriguez are with TECNALIA, Basque Research and Technology Alliance (BRTA), 48160 Derio, Spain. Contact email: [email protected].²Antón Asla is in Serikat - Consultoría y Servicios Tecnológicos, 48009 Bilbao, Spain.© 2023 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

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.

Index Terms:

Bin Packing Problem, Logistics, Optimization, Quantum Computing, Quantum Annealer, D-Wave.

I Introduction

The Bin Packing Problem (BPP) is a combinatorial optimization problem that consists of packing a group of items, or packages, into a set of bins or containers without any kind of overlap. Usually, the main objective of the BPP is i) to store all items in a single bin as densely as possible or ii) to distribute the complete set of packages into as few containers as possible.

The BPP is a classical problem in artificial intelligence and operations research, and it has wide industrial applicability. The BPP has been applied to problems ranging from origami design [1], steel production [2], or placement of advertisements [3], among many others. Furthermore, transportation and logistics are application fields that have benefited from the advancements made regarding the BPP.

In fact, one of the toughest challenges for logistic corporations is related to bin packing, which is a critical issue for reducing storage costs or improving vehicle space allocation [4]. Among general applications, we can highlight pallet loading [5], automatic depot management [6], or optimizing shared parking resources [7] to name a few examples.

Due to their remarkable scientific and business interest, BPP variants have been widely addressed in the literature by different solving approaches. In this paper, we explore the BPP from a perspective still scarcely studied in the literature: Quantum Computing (QC, [8]). Nowadays, QC is attracting a lot of attention from researchers and practitioners, and the related community is working to discern the contributions that this revolutionary technology can offer to many application sectors. Transportation and logistics are fields in which QC has already demonstrated promising performance [9], for instance, tackling problems related to routing [10] or traffic management [11]. In spite of this blossoming scientific activity, BPP is still few dealt from QC perspective.

Thus, our main objective is to take a step forward with respect to our previous study presented in [12]. In that work, we proposed a QC-based framework for dealing with real-word three dimensional BPPs (3dBPP, [13]). We coined this framework Quantum Framework for Real Bin Packing Problems (Q4RealBPP). In this manuscript, we further elaborate on the formulation and findings presented in [12] by considering the following aspects:

•

Contemplate having heterogeneous bins in the same instance, with different sizes and capacities.
•

Extend the applicability of Q4RealBPP for solving both one-dimensional (1dBPP, [14]) and two-dimensional (2dBPP, [15]) instances. To the best of our knowledge, this feature becomes Q4RealBPP in the first QC-based framework in the literature for dealing with not only real-world oriented 3dBPP problems but also with 2dBPP instances.
•

Allow the user to impose requirements for item-bin associations. In other words, each item must be assigned to a specific set of bins.
•

Embrace the relative positioning feature introduced in [12] (and later detailed), exploring the application of delivery priorities to store items. This way, the user defines which packages will be delivered first, so that they are placed closer to the trunk’s door or bin boundaries.

All these new features enable to outline more realistic BPP instances with a more accurate applicability to the field of logistics. Therefore, in this paper, we describe how these features have been implemented into Q4RealBPP. Also, we conduct experiments for solving real-oriented instances over new scenarios not contemplated at all in the original formulation, proving the flexibility of our methodology.

It is interesting to mention that all the advances detailed in this research have been defined involving a national company specialized in transport and logistics, named Ertransit¹¹1https://www.ertransit.com.cn/ertransit-espana/. After conducting several meetings among Ertransit and the research team, a set of real needs were established, which have guided the developments detailed in this paper.

The rest of the article is organized as follows: in Section II, we provide the background of this research. Then, in Section III we describe Q4RealBPP and all the newly implemented aspects. Section IV is devoted to demonstrating the applicability of the new version of Q4RealBPP. Finally, we conclude this article by summarizing the work done and proposing possible future research in Section V.

II Background

The BPP, in any of its variants, has been extensively studied over the last decades. In fact, interest is so strong that significant research is still being done on even the most basic version, the 1dBPP [14]. Furthermore, the 2dBPP is also widely studied, having practical applications in the sheet metal, leather, clothing, and glass industries [16]. In these cases, the 2dBPP is employed to lay out some pieces on a surface minimizing waste of material. The 2dBPP has also demonstrated applicability in business transportation, giving rise to the well-known vehicle routing problem with two-dimensional loading constraints (2L-CVRP, [17]).

So far, the 3dBPP is the BPP version that has been explored the most. Highlighted in studies such as [18], the 3dBPP has relevance in many industrial settings. Also, thanks to its complexity, the 3dBPP is also employed as a benchmarking problem to test new techniques and procedures [19]. In any case, it is hard to find 3dBPP instances that can really handle the size and requirements expected by industry [5]. For this reason, even though the most basic formulation does not faithfully respond to the demands of real-world scenarios, the 3dBPP is also used as a subproblem of more complex and larger problems [20]. Additionally, a wide variety of practical constraints have been included to model more realistic 3dBPP variants [21], such as load balancing, uncertainty, overweight restrictions, priority, or load bearing, among many others.

Regarding its solving, BPP-related variants have been approached using different techniques, such as exact methods [22], classical local-search heuristics [23], nature-inspired metaheuristics [24] and more advanced paradigms, such as reinforcement learning [25]. Anyway, if we pay attention to the QC field, BPPs have drawn scant attention so far.

In a nutshell, QC is a revolutionary computing paradigm that leverages quantum phenomena to find competent solutions in a more efficient way. For doing that, specific processing units called Quantum Processing Units (QPU) are used. Up until now, the potential of QC has been explored in research areas such as simulation, machine learning, cryptography, or optimization. The rapid evolution of related technology and the advances made in its democratization [26] have contributed to the growth of QC community, especially in the optimization field, in which areas as transportation [27], energy [28] or finance [29] have already benefited from this avant-garde computing paradigm.

At the confluence between QC and BPP, as mentioned, only a few dedicated papers can be found in the literature to date. It was not until 2022 that the pioneering works focused on 1dBPP were published [30, 31]. Besides those studies, in [32] the problem of filling spent nuclear fuel in deep-repository canisters is addressed by a 1dBPP approach. Authors solve the problem using the D-Wave quantum annealer.

Lastly, the authors of this paper presented a framework for solving real-world oriented 3dBPP instances in 2023 [12]. This framework, named Q4RealBPP, and built upon an existing code [33], allows the consideration of features such as i) dimensions of items and containers, ii) overweight restrictions, iii) affinities among items, iv) relative positioning of items and v) load balancing. In addition, the authors developed a Python script for the generation of synthetic datasets. We refer interested readers to [34].

As mentioned before, this research improves significantly this previous work adding further features and novel procedures to deal with even more realistic and varying scenarios.

III Quantum Framework for Real Bin Packing Problems - Q4RealBPP

Q4RealBPP is a quantum-based framework making use of Leap Constrained Quadratic Model (CQM) Hybrid Solver (LeapCQMHybrid, [35]) as its quantum engine. As mentioned, five different features were taken into account in Q4RealBPP: i) dimensions, ii) maximum weight allowed per bin, iii) affinities among packages, iv) relative positioning of items, and v) the establishment of a center of mass. Lastly, we finish this section by implementing an additional mechanism with the aim of optimizing the inner space between items for reaching better results.

In this article, we add a new functionality layer on top of Q4RealBPP, seeking to tackle a broader spectrum of realistic scenarios, especially focused on logistics environments. This section describes the new contributions. The parameters and variables used in our formulation are shown in Table I.

TABLE I: Parameters and variables used in this manuscript.

Parameters
$I,J,K_{i},Q$	sets of items, bins, orientations of $i$ -th item and relative positions between items.
$m,n$	number of items and bins.
$l_{i},w_{i},h_{i},\mu_{i}$	length, width, height and weight of item $i\in I$ .
$L_{j},W_{j},H_{j},M_{j}$	length, width, height and maximum capacity (optional) of bin $j\in J$ .
$P^{+}_{q}$	set of relative positionings $q\in Q$ between pairs of items $i,k\in I$ to satisfy (optional).
$(\tilde{L},\tilde{W})$	target center of mass of the resultant packings (optional).
Variables
$v_{j}$	binary variable that represents if bin $j\in J$ is used.
$u_{i,j}$	binary variable that represents if item $i$ is added to bin $j$ .
$r_{i,k}$	binary variable that shows if orientation $k\in K_{i}$ is applied to item $i$ . Used to compute effective length, width and height $(x^{\prime}_{i},y^{\prime}_{i},z^{\prime}_{i})$ .
$x_{i},y_{i},z_{i}$	real variables that return the location of the back lower left corner of item $i$ along $x$ , $y$ and $z$ axes.
$b_{i,k,q}$	binary variable that returns the relative position $q\in Q$ between items $i,k\in I$ .

Heterogeneous bins: as can be read in papers such as [13, 15], canonical BPPs count with a set of unlimited bins with the same size and capacity. Arguably, this is the most frequent trend in the literature, which is far away from real-world settings. This is particularly acute in road transport, where vehicle fleets are usually heterogeneous. In our previous formulation, every bin has the same dimensions [12]. Here, we extend its capabilities by considering $n$ bins of heterogeneous dimensions $\{(L_{j},W_{j},H_{j})\}_{j=1}^{n}$ . This feature is added within bin boundary constraints $\forall i\in I,\text{ }\forall j\in J$ as

		$\displaystyle x_{i}+x_{i}^{\prime}-\sum\nolimits_{p=1}^{j}L_{p}\leq(1-u_{i,j})\sum\nolimits_{p=1}^{n}L_{p},$		(1)
		$\displaystyle x_{i}-u_{i,j}\sum\nolimits_{p=1}^{j-1}L_{p}\geq 0\quad(j>1),$		(2)
		$\displaystyle y_{i}+y_{i}^{\prime}-W_{j}\leq(1-u_{i,j})W_{\text{max}},$		(3)
		$\displaystyle z_{i}+z_{i}^{\prime}-H_{j}\leq(1-u_{i,j})H_{\text{max}}.$		(4)

with $W_{\text{max}}=\max\{W_{i}\}_{i=1}^{n}$ and $H_{\text{max}}=\max\{H_{i}\}_{i=1}^{n}$ . For 2dBPP, just consider (1)-(3) and for 1dBPP (1) and (2).

Similarly, instead of only having the same maximum capacity for all bins, it is possible to set one for each bin as $\{M_{j}\}_{j=1}^{n}$ and modify the overweight restriction as

\sum\nolimits_{i=1}^{m}\mu_{i}u_{i,j}\leq M_{j}\quad\forall j\in J.

(5)

1dBPP/2dBPP compatibility: being the most complete variant of the BPP family, the 3dBPP is more conducive to solving transportation-related problems. However, 2dBPP and 1dBPP have also proven to be effective formulations for modeling real-world scenarios. The former is a key component of the aforementioned 2L-CVRP, while the 1dBPP has also been embraced for routing environments [36]. With the principal motivation of extending the applicability of the framework, we have generalized Q4RealBPP to cover 1dBPP and 2dBPP problems, letting the user codify the problem in as many spatial dimensions as the problem demands. This new functionality has augmented the capabilities of the framework presented in [12].

For 1dBPP, where items are represented just by their $l_{i}$ , orientations are ignored. The effective lengths are $x_{i}^{\prime}=l_{i}$ $\forall i\in I$ . This is not the case of 2dBPP, in which items are described by their $l_{i}$ and $w_{i}$ , and where one rotation can be applied to each of them. The set of non-redundant orientations $K_{i}$ for each item $i$ is $\varnothing$ if $l_{i}=w_{i}$ (square items) and $\{1,3\}$ otherwise (see Figure 1), needing $\kappa=\sum_{i=1}^{m}|K_{i}|$ orientation variables $r_{i,k}$ . For $i\in I_{\text{s}}$ with $I_{\text{s}}=\{i\in I\,|\,l_{i}=w_{i}\}$ , we can set in advance $r_{i,1}=1$ and $r_{i,3}=0$ . Their effective lengths and widths are $x_{i}^{\prime}=l_{i}r_{i,1}+w_{i}r_{i,3}$ and $y_{i}^{\prime}=w_{i}r_{i,1}+l_{i}r_{i,3}$ $\forall i\in I$ .

Since the dimensionality of the problem changes, some restrictions of [12] must be accordingly modified. For 2dBPP, non-overlapping constraints are given by $\forall i,k\in I,\,\forall j\in J$ ,

		$\displaystyle(u_{i,j}u_{k,j}+b_{i,k,1}-2)\!\sum\nolimits_{p=1}^{n}L_{p}+x_{i}+x^{\prime}_{i}-x_{k}\leq 0,$		(6)
		$\displaystyle(u_{i,j}u_{k,j}+b_{i,k,2}-2)W_{\text{max}}+y_{i}+y^{\prime}_{i}-y_{k}\leq 0,$		(7)
		$\displaystyle(u_{i,j}u_{k,j}+b_{i,k,4}-2)\!\sum\nolimits_{p=1}^{n}L_{p}+x_{k}+x^{\prime}_{k}-x_{i}\leq 0,$		(8)
		$\displaystyle(u_{i,j}u_{k,j}+b_{i,k,5}-2)W_{\text{max}}+y_{k}+y^{\prime}_{k}-y_{i}\leq 0,$		(9)

where (6) considers item $i$ at the left of item $k$ ( $q=1$ ), (7) that $i$ is behind $k$ ( $q=2$ ), (8) that $i$ is at the right of $k$ ( $q=4$ ) and (9) that $i$ is in front of $k$ ( $q=5$ ). Similarly, for 1dBPP, we just need to consider (6) and (8). Figure 2 depicts the set of relative positions among items.

(a)

k=1

(b)

k=3

Figure 1: Orientations

k\in K_{i}

for an item

i

of dimensions

(l_{i},w_{i})

(a)

b_{{\color[rgb]{1,0,0}i},{\color[rgb]{0,0,1}k},1}=1

(b)

b_{{\color[rgb]{1,0,0}i},{\color[rgb]{0,0,1}k},2}=1

(c)

b_{{\color[rgb]{1,0,0}i},{\color[rgb]{0,0,1}k},3}=1

(d)

b_{{\color[rgb]{1,0,0}i},{\color[rgb]{0,0,1}k},4}=1

(e)

b_{{\color[rgb]{1,0,0}i},{\color[rgb]{0,0,1}k},5}=1

(f)

b_{{\color[rgb]{1,0,0}i},{\color[rgb]{0,0,1}k},6}=1

Figure 2: Scheme of

b_{i,k,q}

activated for relative positions

q\in Q

among items

i,k\in I

. Both are in contact but it is not mandatory.

Requirements for item-bin association: with this new functionality, the user is able to assign a set of eligible bins for each item. This way, the solution is considered feasible if all items are allocated to an admissible container. This feature is especially interesting in environments in which bins are heterogeneous and of different characteristics. We can easily think of a scenario with a mixture of refrigerated and non-refrigerated containers. In these cases, it is common to have certain products that need to be kept cold, whereas others may not tolerate low temperatures.

This new feature adds for each item category $\alpha$ a list, $J_{\alpha}$ , of available bins as input, i.e. a set of bins where $\alpha$ -items must be placed. Defining $I_{\alpha}=\{i\in I\,|\,\texttt{id}\text{ of }i\text{ is }\alpha\}$ , there are three possible scenarios depending on the length of $J_{\alpha}$ :

1.

$|J_{\alpha}|=1$ : then $\alpha$ -items must be placed in only one bin. Thus, we can set in advance $u_{i,j}=1$ $\forall i\in I_{\alpha},\text{ }j\in J_{\alpha}$ and $u_{i,j}=0$ $\forall i\in I_{\alpha},\text{ }\forall j\notin J_{\alpha}$ .
2.

$1<|J_{\alpha}|<n$ : then $\alpha$ -items must be placed in certain bins, so some of them are excluded. So, we can set in advance $u_{i,j}=0$ $\forall i\in I_{\alpha},\text{ }\forall j\notin J_{\alpha}$ .
3.

$|J_{\alpha}|=n$ : $\alpha$ -items can be placed in any bin. That is, no requirement for item-bin association is applied. Hence, we follow the same procedure as in [12].

Taking this into account, $\sum_{\alpha}(n-|J_{\alpha}|)|I_{\alpha}|$ variables can be set in advance, leading to a formulation where fewer variables (thus qubits) are needed (suitable for NISQ era [37]).

Delivery priorities: in academia, BPP and routing problems are usually treated separately. In contrast, in a real logistics environment, these two problems are interrelated in such a way that the global solution satisfies all the requirements coherently. Thus, optimality in terms of time would involve taking into account the delivery ordering of the customers assigned to each vehicle in such a way that items to be delivered first are placed closest to the unloading door. It is easy to imagine a scenario in which the items to be delivered first are placed closest to the bin boundaries.

We have materialized these scenarios by using the functionality, described in [12], named relative positioning among items. In our previous work, we employed it for load-bearing purposes, considering the weight of items as a reference for fragility. In that case, heavy packages should be placed beneath the lightest ones, eventually controlling $b_{i,k,q}$ variables, specifically in this example with $q=3$ and $q=6$ (see Figure 2). Therefore, similarly to [12], delivery priorities are specified to influence the values to some $b_{i,k,q}$ variables, we define delivery priorities as:

	$\displaystyle P^{+}_{q}$	$\displaystyle=\{(i,k)\in I^{2}\,\|\,i<k\text{ and }i\text{ delivered before }k\},$		(10)
	$\displaystyle P^{+}_{q^{\prime}}$	$\displaystyle=\{(i,k)\in I^{2}\,\|\,i<k\text{ and }k\text{ delivered before }i\},$		(10)

being $q=1$ and $q^{\prime}=4$ in the case of 3dBPP. So, we set $b_{i,k,1}=1$ and $0$ otherwise for $(i,k)\in P^{+}_{1}$ and $b_{i,k,4}=1$ and $0$ otherwise for $(i,k)\in P^{+}_{4}$ . For 2dBPP, the same procedure is followed, but using $q=2$ and $q^{\prime}=5$ .

Note that this constraint, and all of those relating relative positions, could be easily adapted to any other scenario via $b_{i,k,q}$ . For example, to problems with bins that are accessed from the top ( $z$ axis) or from their laterals ( $y$ axis), such as with tarpaulin trailers.

Reduce inner space between items: 2dBPP has well-known significance where cutting rectangular items from raw material sheets, such as steel or wood, is required minimizing the amount of left-overs [38]. Also, for the 3dBPP, a user may prefer to have all items stacked, with the intention of reducing the space between packages. For materializing this requirement, one key constraint consists on pushing items to boundaries, which can be introduced using

o_{x}=\frac{1}{mL}\sum\nolimits_{i=1}^{m}(x_{i}+x_{i}^{\prime})\,\text{ }o_{y}=\frac{1}{mW}\sum\nolimits_{i=1}^{m}(y_{i}+y_{i}^{\prime}),

(11)

which extends the second objective of [12].

IV Demonstration

In this section, we demonstrate the applicability of our developed Q4RealBPP with a focus on the new functionalities and features described in this study. In order for the problem to be solved, it must first be modeled as a CQM and then sent to the LeapCQMHybrid provided by D-Wave. This solver is part of D-Wave’s hybrid solver service (HSS, [39]), which is a portfolio of methods developed by D-Wave. These hybrid techniques balance classical and quantum computation for addressing optimization problems unable to be directly faced by purely quantum processors [35]. At the time of this writing, the portfolio of hybrid methods available in HSS permits the solving of Binary Quadratic Models, Discrete Quadratic Models and, lastly, CQMs, such as the one formulated in this research.

Having said this, the rest of this section is devoted to showcasing how Q4RealBPP deals with new realistic industrial contexts. These scenarios relate with heterogeneous bins, item-bin associations and delivery priorities, respectively, using 3dBPP and 2dBPP instances. Also, we demonstrate the resolution of two different 1dBPP cases. Finally, for the sake of completeness, we test Q4RealBPP in two real-world oriented 3dBPP instances, considering not only the features described here but also further ones detailed in our previous work [12]. Aiming to enhance the replicability of this work, the ten instances used and the results are openly available in [40]. The format of these instances is based on the one provided in [33], and further described in [34].

IV-A Heterogeneous Bins

On the one hand, we depict in Figure 3(a) the result provided by Q4RealBPP for the instance coined 3dBPP_het_bins. This instance is composed of $m$ =51 items distributed among 10 categories and $n$ =2 bins of $L_{0}$ = $W_{0}$ = $H_{0}$ =1200 and $L_{1}$ = $W_{1}$ = $H_{1}$ =900 dimensions. On the other hand, in Figure 3(b) we represent the solution offered for the instance 2dBPP_het_bins, with $m$ =35 distributed among 10 categories and $n$ =2 bins of $L_{0}$ = $W_{0}$ =120 and $L_{1}$ = $W_{1}$ =170 dimensions, respectively. Note that bin boundaries are represented by straight red lines in all figures shown in this manuscript.

Refer to caption — (a) Solution to 3dBPP_het_bins.

IV-B Requirements for item-bin association

Table II summarizes the requirements for item-bin association built for the two instances generated for this use case, named 3dBPP_item_bins and 2dBPP_item_bins. For each one, we represent the id of every item category and the bins allowed for each of these categories. Both instances count with $n$ =3 bins, and $m$ =57 items for the 3dBPP and $m$ =40 for the 2dBPP. Solutions to these instances are shown in Figure 4.

TABLE II: Summary of the item-bin associations for 3dBPP_item_bins and 2dBPP_item_bins. Each item category is represented by the number of items to store and the ids of the bins allowed. Both instances count with a pool of 3 bins with ids {0,1,2}.

Item ID	3dBPP		2dBPP
	Amount	Bins	Amount	Bins
0	5	2	4	0
1	6	0,1,2	2	0
2	3	0,1,2	5	0,1,2
3	6	0,1,2	5	0,1,2
4	8	1	2	0,1,2
5	6	0,2	6	0,2
6	5	0,1	3	1,2
7	3	0	4	0,2
8	7	1,2	5	2
9	8	0,2	4	1

IV-C Delivery Priorities

For both instances, named as 3dBPP_del_prior and 2dBPP_del_prior, the item category that should be prioritized is the id=9 ( ), meaning that all packages of this class must be placed near an imaginary door for the 3dBPP ( $y$ axis) and on the bottom of the bin for the 2dBPP ( $x$ axis). In 3dBPP_del_prior $m$ is equal to 42, while 2dBPP_del_prior is composed of $m$ =44 items. We represent the solutions given by Q4RealBPP for this use case in Figure 5.

IV-D Solving 1dBPP instances

Regarding the 1dBPP, we demonstrate the application of Q4RealBPP using two different instances. On the one hand, 1dBPP_1 contains $m$ =51 items, and $n$ =2 bins, with $M_{0}$ =80 and $M_{1}$ =60. On the other hand, in 1dBPP_2, $m$ =59, $n$ =2 and $M_{0}$ = $M_{1}$ =85. We have also taken delivery priorities into account, storing items with id=9 ( ) at the top of the bin. Figure 6 shows the solutions to both instances.

IV-E Solving Real-World instances

Finally, and for the sake of completeness, we demonstrate in this subsection how Q4RealBPP can deal with two real-world oriented instances, which include not only the characteristics described in Section III but also the ones shown in our previous work [12]. Thus, the following two use cases have been built by combining multiple features developed in Q4RealBPP:

•

3dBPP_real_world_1: $m$ =41 distributed in 7 categories; $n$ =1 with dimensions $L_{0}$ = $W_{0}$ = $H_{0}$ =1600; a center of mass $(\tilde{L},\tilde{W})$ = $(800,800)$ ; items with id=5 ( ) are so heavy that must not be placed beneath any package of other category; and delivery priority for items with id=6 ( ).
•

3dBPP_real_world_2: $m$ =55 items distributed among 10 categories; $n$ =3 with $L_{0}$ = $W_{0}$ = $H_{0}$ =750, $L_{1}$ = $W_{1}$ = $H_{1}$ =800 and $L_{2}$ = $W_{2}$ = $H_{2}$ =900; items with the id=1 ( ) must not be stored in the same bin as id=2 ( ) and id=3 ( ); item-bin associations equal to what detailed in Table II for the 3dBPP instance; items with id=9 ( ) are so heavy that they must not be placed beneath any package of another category; and delivery priority for items with id=8 ( ).

V Conclusions and further work

This paper has enriched our previous work [12] with new industrial applications. Thanks to the work detailed in this manuscript, our tool is able to deal with more realistic and logistics oriented BPP scenarios. More specifically, we have described and tested four different features: i) the generalization to 1dBPP and 2dBPP, ii) the possibility of having heterogeneous bins, iii) requirements for item-bin associations, and iv) the introduction of delivery priorities. We have planned for future research to develop additional functionalities, such as deeming two centers of mass in the same bin or the consideration of constraints as soft restrictions, and test additional realistic scenarios, such as ones considering delivery priorities in both $y$ and $z$ axes. Also, we will work on improving the overall quality of the solutions provided by Q4RealBPP. Finally, we also contemplate as further work the introduction of advanced paradigms such as transfer optimization.

References

[1] J. T. Bruton, T. G. Nelson, T. K. Zimmerman, J. D. Fernelius, S. P. Magleby, and L. L. Howell, “Packing and deploying soft origami to and from cylindrical volumes with application to automotive airbags,” Royal Society open science, vol. 3, no. 9, p. 160429, 2016.
[2] A. Maddaloni, V. Colla, G. Nastasi, M. Del Seppia, and V. Iannino, “A bin packing algorithm for steel production,” in 2016 European Modelling Symposium (EMS). IEEE, 2016, pp. 19–24.
[3] G. Kim and I. Moon, “Online banner advertisement scheduling for advertising effectiveness,” Computers & Industrial Engineering, vol. 140, p. 106226, 2020.
[4] R. Tian, C. Kang, J. Bi, Z. Ma, Y. Liu, S. Yang, and F. Li, “Learning to multi-vehicle cooperative bin packing problem via sequence-to-sequence policy network with deep reinforcement learning model,” Computers & Industrial Engineering, p. 108998, 2023.
[5] F. Gzara, S. Elhedhli, and B. C. Yildiz, “The pallet loading problem: Three-dimensional bin packing with practical constraints,” European Journal of Operational Research, vol. 287, no. 3, pp. 1062–1074, 2020.
[6] S. You and S. Ji, “Design of a multi-robot bin packing system in an automatic warehouse,” in 2014 11th International Conference on Informatics in Control, Automation and Robotics (ICINCO), vol. 2. IEEE, 2014, pp. 533–538.
[7] P. Zhao, H. Guan, H. Wei, and S. Liu, “Mathematical modeling and heuristic approaches to optimize shared parking resources: A case study of beijing, china,” Transportation Research Interdisciplinary Perspectives, vol. 9, p. 100317, 2021.
[8] L. Gyongyosi and S. Imre, “A survey on quantum computing technology,” Computer Science Review, vol. 31, pp. 51–71, 2019.
[9] S. Wang, Z. Pei, C. Wang, and J. Wu, “Shaping the future of the application of quantum computing in intelligent transportation system,” Intelligent and Converged Networks, vol. 2, no. 4, pp. 259–276, 2021.
[10] E. Osaba, E. Villar-Rodriguez, and I. Oregi, “A systematic literature review of quantum computing for routing problems,” IEEE Access, 2022.
[11] S. Boyapati, S. R. Swarna, and A. Kumar, “Quantum neural networks for dynamic route identification to avoid traffic,” in 2020 Fourth International Conference on I-SMAC (IoT in Social, Mobile, Analytics and Cloud)(I-SMAC). IEEE, 2020, pp. 1018–1022.
[12] S. V. Romero, E. Osaba, E. Villar-Rodriguez, I. Oregi, and Y. Ban, “Hybrid approach for solving real-world bin packing problem instances using quantum annealers,” Scientific Reports, vol. 13, no. 1, p. 11777, 2023.
[13] S. Martello, D. Pisinger, and D. Vigo, “The three-dimensional bin packing problem,” Operations research, vol. 48, no. 2, pp. 256–267, 2000.
[14] C. Munien and A. E. Ezugwu, “Metaheuristic algorithms for one-dimensional bin-packing problems: A survey of recent advances and applications,” Journal of Intelligent Systems, vol. 30, no. 1, pp. 636–663, 2021.
[15] A. Lodi, S. Martello, and D. Vigo, “Recent advances on two-dimensional bin packing problems,” Discrete Applied Mathematics, vol. 123, no. 1-3, pp. 379–396, 2002.
[16] X. Hu, J. Li, and J. Cui, “Greedy adaptive search: A new approach for large-scale irregular packing problems in the fabric industry,” IEEE Access, vol. 8, pp. 91 476–91 487, 2020.
[17] S. C. Leung, X. Zhou, D. Zhang, and J. Zheng, “Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem,” Computers & Operations Research, vol. 38, no. 1, pp. 205–215, 2011, project Management and Scheduling.
[18] A. Lodi, S. Martello, and D. Vigo, “Heuristic algorithms for the three-dimensional bin packing problem,” European Journal of Operational Research, vol. 141, no. 2, pp. 410–420, 2002.
[19] C. Paquay, S. Limbourg, M. Schyns, and J. F. Oliveira, “Mip-based constructive heuristics for the three-dimensional bin packing problem with transportation constraints,” International Journal of Production Research, vol. 56, no. 4, pp. 1581–1592, 2018.
[20] F. Parreño, R. Alvarez-Valdés, J. F. Oliveira, and J. M. Tamarit, “A hybrid grasp/vnd algorithm for two-and three-dimensional bin packing,” Annals of Operations Research, vol. 179, no. 1, pp. 203–220, 2010.
[21] O. X. do Nascimento, T. A. de Queiroz, and L. Junqueira, “Practical constraints in the container loading problem: Comprehensive formulations and exact algorithm,” Computers & Operations Research, vol. 128, p. 105186, 2021.
[22] E. F. Silva, T. Wauters et al., “Exact methods for three-dimensional cutting and packing: A comparative study concerning single container problems,” Computers & Operations Research, vol. 109, pp. 12–27, 2019.
[23] J. Jiang and L. Cao, “A hybrid simulated annealing algorithm for three-dimensional multi-bin packing problems,” in 2012 International Conference on Systems and Informatics (ICSAI2012). IEEE, 2012, pp. 1078–1082.
[24] M. Weiss Cohen, “Solving a profited 3d bin packing problem using a hybrid genetic algorithm,” in ASME International Mechanical Engineering Congress and Exposition, vol. 85604. American Society of Mechanical Engineers, 2021, p. V006T06A001.
[25] H. Hu, X. Zhang, X. Yan, L. Wang, and Y. Xu, “Solving a new 3d bin packing problem with deep reinforcement learning method,” arXiv preprint arXiv:1708.05930, 2017.
[26] Z. C. Seskir, S. Umbrello, C. Coenen, and P. E. Vermaas, “Democratization of quantum technologies,” Quantum Science and Technology, vol. 8, no. 2, p. 024005, 2023.
[27] S. Harwood, C. Gambella, D. Trenev, A. Simonetto, D. Bernal, and D. Greenberg, “Formulating and solving routing problems on quantum computers,” IEEE Transactions on Quantum Engineering, vol. 2, pp. 1–17, 2021.
[28] A. Ajagekar and F. You, “Quantum computing for energy systems optimization: Challenges and opportunities,” Energy, vol. 179, pp. 76–89, 2019.
[29] R. Orús, S. Mugel, and E. Lizaso, “Quantum computing for finance: Overview and prospects,” Reviews in Physics, vol. 4, p. 100028, 2019.
[30] M. G. de Andoin, E. Osaba, I. Oregi, E. Villar-Rodriguez, and M. Sanz, “Hybrid quantum-classical heuristic for the bin packing problem,” in Proceedings of the Genetic and Evolutionary Computation Conference Companion, 2022, pp. 2214–2222.
[31] M. G. De Andoin, I. Oregi, E. Villar-Rodriguez, E. Osaba, and M. Sanz, “Comparative benchmark of a quantum algorithm for the bin packing problem,” in 2022 IEEE Symposium Series on Computational Intelligence (SSCI), 2022, pp. 930–937.
[32] A. Bozhedarov, A. Boev, S. Usmanov, G. Salahov, E. Kiktenko, and A. Fedorov, “Quantum and quantum-inspired optimization for solving the minimum bin packing problem,” arXiv preprint arXiv:2301.11265, 2023.
[33] D-Wave Ocean Developers Team, “3d-bin-packing (GitHub repository),” 6 2022, Last retrieved . [Online]. Available: https://github.com/dwave-examples/3d-bin-packing
[34] E. Osaba, E. Villar-Rodriguez, and S. V. Romero, “Benchmark dataset and instance generator for real-world three-dimensional bin packing problems,” Data in Brief, p. 109309, 2023.
[35] D-Wave Developers, “Measuring Performance of the Leap Constrained Quadratic Model Solver,” D-Wave Systems Inc., Tech. Rep. 14-1065A-A, 11 2022.
[36] S. Anand and S. Guericke, “A bin packing problem with mixing constraints for containerizing items for logistics service providers,” in Computational Logistics: 11th International Conference, ICCL 2020, Enschede, The Netherlands, September 28–30, 2020, Proceedings. Springer, 2020, pp. 342–355.
[37] J. Preskill, “Quantum Computing in the NISQ era and beyond,” Quantum, vol. 2, p. 79, Aug. 2018.
[38] N. M. Cid-Garcia and Y. A. Rios-Solis, “Positions and covering: A two-stage methodology to obtain optimal solutions for the 2d-bin packing problem,” PLOS ONE, vol. 15, no. 4, p. e0229358, Apr 2020.
[39] D-Wave Developers, “D-Wave Hybrid Solver Service: An Overview,” D-Wave Systems Inc., Tech. Rep. 14-1039A-B, 05 2020.
[40] E. Osaba, S. V. Romero, and E. Villar-Rodriguez, “Benchmark dataset for logistic-oriented bin packing problems,” http://dx.doi.org/10.17632/9ts4rvkc5s.1, 2023, online at Mendeley Data.