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 inTable1.
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}^3omega _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=1text { }forall i).
The first and main objective minimizes the total amount of bins used to locate the packages. This can be achieved by minimizing
$$begin{aligned} o_1 = sum _{j=1}^nv_j. end{aligned}$$
(1)
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
$$begin{aligned} o_2 = frac{1}{mH}sum _{i=1}^mleft( z_i + z'_iright) . end{aligned}$$
(2)
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
$$begin{aligned} o_3 = frac{1}{m}left( frac{1}{L}sum _{i=1}^m {tilde{x}}_i + frac{1}{W}sum _{i=1}^m {tilde{y}}_iright) , end{aligned}$$
(3)
with
$$begin{aligned} {tilde{x}}_i {:}{=}left| left( x_i + frac{x_i'}{2}right) !text { mod } L -{tilde{L}} right| quad text {and}quad {tilde{y}}_i {:}{=}left| y_i + frac{y_i'}{2} -{tilde{W}} right| quad forall iin I, end{aligned}$$
(4)
where (0le x_i< nL) (bins stacked horizontally) and (0le y_i< W) (forall iin 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
$$begin{aligned} sum _{kin K_i}r_{i,k}=1quad forall iin I. end{aligned}$$
(5)
Set of possible orientations (kin 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). SeeTable2.
Orientations give rise to the effective length, width, and height of the items along x, y and z axes
$$begin{aligned} x'_i&= l_ir_{i,1} + l_ir_{i,2} + w_ir_{i,3} + w_ir_{i,4} + h_ir_{i,5} + h_ir_{i,6} quad forall iin I, end{aligned}$$
(6)
$$begin{aligned} y'_i&= w_ir_{i,1} + h_ir_{i,2} + l_ir_{i,3} + h_ir_{i,4} + l_ir_{i,5} + w_ir_{i,6} quad forall iin I, end{aligned}$$
(7)
$$begin{aligned} z'_i&= h_ir_{i,1} + w_ir_{i,2} + h_ir_{i,3} + l_ir_{i,4} + w_ir_{i,5} + l_ir_{i,6} quad forall iin I, end{aligned}$$
(8)
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 (iin I_text {c}) with (I_text {c}{:}{=}{iin I,|,l_i=w_i=h_i}) (cubic items), we can set (r_{i,1}=1) and 0 otherwise, thus satisfying(5) in advance. InTable2, 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 (seeFig.2)
$$begin{aligned} text {Item }itext { is at the left of item }k, (q=1)text {:}{} & {} -(2 - u_{i,j}u_{k,j}-b_{i,k,1})nL+x_i+x'_i-x_kle 0{} & {} forall i,kin I,text { }forall jin J, end{aligned}$$
(9)
$$begin{aligned} text {Item }itext { is behind item }k, (q=2)text {:}{} & {} -(2 - u_{i,j}u_{k,j}-b_{i,k,2})W+y_i+y'_i-y_kle 0{} & {} forall i,kin I,text { }forall jin J, end{aligned}$$
(10)
$$begin{aligned} text {Item }itext { is below item }k, (q=3)text {:}{} & {} -(2 - u_{i,j}u_{k,j}-b_{i,k,3})H+z_i+z'_i-z_kle 0{} & {} forall i,kin I,text { }forall jin J, end{aligned}$$
(11)
$$begin{aligned} text {Item }itext { is at the right of item }k, (q=4)text {:}{} & {} -(2 - u_{i,j}u_{k,j}-b_{i,k,4})nL+x_k+x'_k-x_ile 0{} & {} forall i,kin I,text { }forall jin J,end{aligned}$$
(12)
$$begin{aligned} text {Item }itext { is in front of item }k, (q=5)text {:}{} & {} -(2 - u_{i,j}u_{k,j}-b_{i,k,5})W+y_k+y'_k-y_ile 0{} & {} forall i,kin I,text { }forall jin J, end{aligned}$$
(13)
$$begin{aligned} text {Item }itext { is above item }k, (q=6)text {:}{} & {} -(2 - u_{i,j}u_{k,j}-b_{i,k,6})H+z_k+z'_k-z_ile 0{} & {} forall i,kin I,text { }forall jin J. end{aligned}$$
(14)
As discussed with the orientation variable (r_{i,k}) in(5), the relative position between items i and k must be unique, so
$$begin{aligned} sum _{qin Q}b_{i,k,q}=1quad forall i,kin I. end{aligned}$$
(15)
Representation of (b_{i,k,q}) activated for all relative positions (qin 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
$$begin{aligned} sum _{j=1}^n u_{i,j}=1quad forall iin I. end{aligned}$$
(16)
The following formula verifies if items are being packed inside bins that are already in use
$$begin{aligned} sum _{i=1}^m(1-v_j)u_{i,j}le 0quad forall jin J, end{aligned}$$
(17)
so it activates (v_j) if needed during packaging. Bins can be activated sequentially to avoid duplicated solutions ensuring that
$$begin{aligned} v_jge v_{j+1}quad forall jin Jtext { } | text { }jne n. end{aligned}$$
(18)
Bin boundary constraints: in order to contemplate bin boundaries, the following set of restrictions must be met
$$begin{aligned}{} & {} x_i+x'_i-jL le (1-u_{i,j})nL quad forall iin I,text { }forall jin J, end{aligned}$$
(19)
$$begin{aligned}{} & {} x_i-(j-1)Lu_{i,j} ge 0 quad forall iin I,text { }forall jin Jtext { }|text { }j>1, end{aligned}$$
(20)
$$begin{aligned}{} & {} y_i+y'_i-W le (1-u_{i,j})W quad forall iin I,text { }forall jin J, end{aligned}$$
(21)
$$begin{aligned}{} & {} z_i+z'_i-H le (1-u_{i,j})H quad forall iin I,text { }forall jin J, end{aligned}$$
(22)
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
$$begin{aligned} sum _{i=1}^mmu _iu_{i,j}le Mquad forall jin J. end{aligned}$$
(23)
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 {:}{=}{iin Itext { }|text { }{} texttt {id}text { of }itext { 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
$$begin{aligned} sum _{(alpha ,beta )in A^text {neg}},sum _{(i_alpha ,i_beta )in I_alpha times I_beta },sum _{j=1}^nu_{i_alpha ,j}u_{i_beta ,j}=0, end{aligned}$$
(24)
To activate this restriction, a set of incompatibilities must be given. Moreover, we can satisfy in advance (nu {:}{=}6nsum _{(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
$$begin{aligned} sum _{(alpha ,beta )in A^text {pos}},sum _{(i_alpha ,i_beta )in I_alpha times I_beta },sum _{j=1}^nleft( 1-u_{i_alpha ,j}u_{i_beta ,j}right) =0, end{aligned}$$
(25)
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 (qin 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
$$begin{aligned} P_q^{-}{:}{=}{(i,k)in I^2text { }|text { }i
(26)
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 _{qin Q}|P_q^{-}|}) and (smash [t]{p^{+}=sum _{qin Q}|P_q^{+}|}) with (smash [t]{P^{-}_qcap 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
$$begin{aligned} pm frac{1}{n}sum _{j=1}^nleft[ x_i+frac{x_i'}{2} - n(j-1)u_{i,j}L -{tilde{L}}right] le {tilde{x}}_i quad text {and}quad pm left( y_i+frac{y_i'}{2} -{tilde{W}}right) le {tilde{y}}_i quad forall iin I. end{aligned}$$
(27)
This feature is represented inFig.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 inTable3, where our formulation scales as ({mathscr {O}}[m^2+nm]) in terms of variables. Additionally, the total amount of constraints required is provided inTable4, whose quantity grows quadratically as ({mathscr {O}}[m^2+nm]).
Go here to read the rest:
Hybrid approach for solving real-world bin packing problem ... - Nature.com