## 4 The Packing Problem  
In Section 3, we introduced different in-store routing methodologies that can optimize the picking process. With the implementation of a'scan-as-you-pick device' that is gradually becoming popular in stores, the employees performing the picking operation are able to scan and pack the products during the picking process without the need of a cashier later on to produce the bill. In such a context, employees could, however, have difficulty distributing evenly and safely all the products into the shopping bags, in order to avoid too heavy/full or light/empty imbalance issues.  
To solve this problem and make the packing operation more efficient, a two-step optimization is developed, as described in [29], that first calculates the minimum number of bags needed for a given shopping list and balances the content of the bags by minimizing the differences of weight and volume of the products contained in each pair of bags. The first step is to determine the minimum number of bags required \(b_{min}\) for a given shopping list. The following formulation is based on a classic Bin Packing problem [21]. We define \(P=\{1,2,\ldots,m\}\) as the set of products and \(B=\{1,2,\ldots,n\}\) as the set of available shopping bags. The volume and weight of each product \(i\in P\) are represented as \(v_{i}\) and \(w_{i}\), respectively. The content of each shopping bag cannot exceed a maximum volume \(V_{max}\) and a maximum weight \(W_{max}\). Two binary variables are also defined: \(x_{ij}\) takes the value 1 if product \(i\) is in packed bag \(j\), 0 otherwise, and \(y_{j}=1\) if bag \(j\) is used, 0 otherwise. The problem can be then written in the following way:  
\[b_{min}=\min \sum_{j\in B}y_{j} \tag{1}\] \[s.t \sum_{i\in P}w_{i}x_{ij}\leq W_{max}y_{j} j\in B\] (2) \[\sum_{i\in P}v_{i}x_{ij}\leq V_{max}y_{j} j\in B\] (3) \[\sum_{j\in B}x_{ij}=1 i\in P\] (4) \[x_{ij}\in\{0,1\} i\in P,j\in B\] (5) \[y_{j}\in\{0,1\} j\in B \tag{6}\]  
The constraints (2) and (3) restrict the articles in each bag from exceeding the maximum weight and volume. Constraint (4) enforces each article to be in one and only one bag.  
When there is more than one bag required for the shopping list, the second optimization step is to balance the contents of the bags as evenly as possible. This is realized by solving a Min-Max problem [30]. We define \(B_{m}=\{1,\ldots,b_{min}\}\) as the set of bags to be used, \(z\) as the minmax variable. \(d_{w}^{+}d_{w}^{-}d_{w}^{+}\) and \(d_{w}^{-}\) are technical variables required to minimize the difference between the volume and weight of each pair of bags. The problem can be written as follows:  
\[\min z \tag{7}\] \[s.t (2)-(6)\] \[\sum_{i\in P}w_{i}x_{ij}-\sum_{i\in P}w_{i}x_{ik}-d_{w}^{+}+d_{w} ^{-}=0 j,k\in B_{m},j<k\] (8) \[\sum_{i\in P}v_{i}x_{ij}-\sum_{i\in P}v_{i}x_{ik}-d_{v}^{+}+d_{v} ^{-}=0 j,k\in B_{m},j<k\] (9) \[z\geq d_{w}^{+}+d_{w}^{-}\] (10) \[z\geq d_{v}^{+}+d_{v}^{-}\] (11) \[d_{w}^{+}d_{w}^{-}d_{w}^{+},d_{v}^{-}\geq 0 \tag{12}\]With constraint (8) and (9), each shopping bag contains products that sum up to a similar volume and weight. The minmax constraints for the distance variables are shown in (10) and (11). The distance variables \(d_{w}^{+}d_{w}^{-}d_{w}^{+}\) and \(d_{w}^{-}\) are nonnegative.  
In practice, different types of bags may be required for different products. In such a case, the products should first be classified according to the type of bag required, then the algorithm can be applied to each subgroup. As minimizing the number of bags is an environmental friendly intention, customers can also choose to use paper bags, reusable plastic boxes, or their own bags for the same purpose. Correspondingly, the classification of the products based on the bags can be customized. The model itself is adaptable to these changes.