Keywords

1 Introduction

In the past decade we have witnessed a rapid increase of digitization, that has also been transforming our behaviour as consumers. Online grocery purchases have gradually entered our lives as a convenient option for shopping. This process has been further accelerated by the restrictions and desire for contactless shopping during the COVID-19 pandemic. In such a scenario, traditional brick-and-mortar (B &M) retailers have been greatly incentivized to develop omnichannel solutions [1]. Among the three classical ways for the design of an omnichannel model [2], we are interested in the mode of grocery retailers using their existing B &M structures to fulfill both online and offline demands. The corresponding Buy-Online-Pick-up-in-Store concept (BOPS) is the focus of the remainder of this paper.

The BOPS model has been extensively studied in terms of market strategies [3, 4], but approaches for operations management of in-store order picking are scarce. In the BOPS model, a picker travels through the store to pick all the items on a given shopping list and checks out at the cashier like a regular customer. From the information made available by retailers, these picking operations are commonly not optimized. Employees who are not (yet) familiar with the store may need to go back and forth for a picking task. Even skilled pickers may return to the previously visited shelves, as a consequence of lack of correlation between the articles’ order given on a shopping list and the layout of the supermarket.

Since human workforce is considered a major cost-driver in omnichannel retailing, optimizing the picking and packing process is crucial in cost reduction. An effective way to improve the efficiency of the picking would be reordering the articles in the shopping list by a simple shortest route analysis [5]. The problem is treated as a Travelling Salesman Problem (TSP): the picker follows the shortest route to visit each zone of the store only once, and picks up all the articles on the list at each zone. This is a very effective way to reduce the operating time. However, the B &M stores layout are commonly designed to maximize revenue [2, 6] and customer satisfaction [7], and the main product attributes being considered are visibility, variety, availability and position to maximize impulsive purchases. Product attributes such as size and fragility are less considered, thus picking the articles following the shortest path may lead to potential product damaging and a substantial rearrangement overhead at the cashier. Since manpower is consumed in the packing process as well, determining a good packaging during the picking process would be a great benefit, especially in presence of portable devices that can be used by the employees to produce the bill already while picking. In a previous work [8], a scoring model that gives each product a priority value defined by its characteristics has been proposed. By adding precedence constraints on top of the shortest route analysis, the model is solved as a Sequential Ordering Problem (SOP) [9]. In this paper, the solutions are devised by the heuristic algorithms described in [10]. The picking route is then optimized to reduce the time of moving back and forth in the store while not damaging the articles due to the order in which they are placed. Such an approach provides a good trade-off between efficiency and customer satisfaction. Nevertheless, this model has a drawback considering actual situations. When more than one bag is required for a given shopping list, there is a high probability that we will get one full bag of heavy stuffs (e.g. beverages) and another bag full of light products (e.g. potato chips), since packing in multiple bags is not considered by the optimizer.

To close the gap, in this work we propose a two-step process that estimates the number of bags required for a given shopping list and prepares for the picker an ordered list with each article associated with a certain bag. The articles are conveniently arranged in bags concurrently. In such a way, multiple packages are ready for the customers at the end of each picking task, that further improves the overall efficiency of the BOPS model.

2 Problem Statement

The purpose of this paper is to expand and complete the research conducted in a previous work [8], in which the in-store picking problem was optimized as a SOP to find a trade-off between shorter route and safe pickings that avoid damages to the articles.

In this work, we further optimize the picking and packing process when multiple shopping bags are considered. When the picker uses an ordered list with the previous solving method, it is impossible to put the articles in a reasonable and even manner simultaneously in each bag, as it is difficult for a picker to directly estimate the exact number of shopping bags needed by taking a look at a list of products. To solve this issue, we further optimize the shopping list with a mathematical model that estimates the minimum number of bags required for a given shopping list, and assigns each article in a shopping list to a certain bag in order to have also a balanced packing.

3 Methodology

First of all, we consider the basic problem (BASE) to determine the minimum number of bags required \(b_{min}\) for a given shopping list.

BASE. We define \(P = \{1,2...,m\}\) as the set of products and \(B = \{1,2...,n\}\) as the set of available homogeneous bags. \(v_i\) is the volume of product \(i \in P\), \(w_i\) is the weight of product \(i \in P\). The maximum volume of a bag is \(V_{max}\) and the maximum weight of a bag is \(W_{max}\). In the model we define two binary variables: \(x_{ij}\) and \(y_j\). If product i is in bag j, \(x_{ij}\) takes the value 1, otherwise \(x_{ij} =0\). Similarly, \(y_j = 1\) if bag j is used, 0 otherwise. The basic problem can be written as the following binary linear programming problem:

$$\begin{aligned} b_{min} = \min \quad&\sum _{j \in B} y_{j} \end{aligned}$$
(1)
$$\begin{aligned} s.t \quad&\sum _{i \in P} w_{i} x_{ij} \le W_{max} y_j&j \in B \end{aligned}$$
(2)
$$\begin{aligned}&\sum _{i \in P} v_{i} x_{ij} \le V_{max} y_j&j \in B \end{aligned}$$
(3)
$$\begin{aligned}&\sum _{j \in B} x_{ij} =1&i \in P \end{aligned}$$
(4)
$$\begin{aligned}&x_{ij} \in \{0, 1\}&i \in P, j \in B \end{aligned}$$
(5)
$$\begin{aligned}&y_{j} \in \{0, 1\}&j \in B \end{aligned}$$
(6)

The objective function (1) is to minimize the total number of bags. The constraints (2) and (3) restricts the articles in each bag from exceeding the maximum weight and volume. Constraints (4) enforce each article to be in one and only one bag. The optimal solution to the base problem is the minimum number of bags required \(b_{min}\). If \(b_{min}=1\), the solution is equivalent to the SOP solution discussed in [8] and no further optimization is required. When \(b_{min}>1\), the next step is to look for the optimal solution that assign each product into a shopping bag, based on some heuristically approximated characteristics of the good, with the aim of having a balanced packing. To achieve this, we solve a Min-Max problem that ensures that the total volume and weight of the contents in each shopping bag are almost identical.

MIN-MAX. With respect to the basic problem, we define \(B_m = \{1,...,b_{min}\}\) as the set of bags, as calculated with problem BASE, z as the minmax variable, \(d_w^+\), \(d_w^-\), \(d_v^+\) and \(d_v^-\) as the distance variables that are dummy variables required to minimize the difference between the volume and weight of a pair of bags. The problem can be written as follows:

$$\begin{aligned} \min \quad&z \end{aligned}$$
(7)
$$\begin{aligned} s.t \quad&((2))-((6)) \nonumber \\&\sum _{i \in P}w_i x_{ij} -\sum _{i \in P}v_i x_{ik} - d_w^+ + d_w^- = 0&j,k \in B_m, j<k \end{aligned}$$
(8)
$$\begin{aligned}&\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 \end{aligned}$$
(9)
$$\begin{aligned}&0 \le d_w^+, d_w^-, d_v^+, d_v^-\le z&\end{aligned}$$
(10)

With constraint (8) and (9), each shopping bag contains products that sum up to a similar volume and weight. The distance variables \(d_w^+\),\(d_w^-\),\(d_v^+\) and \(d_v^-\) are non negative, and the minmax constraints for the distance variables are shown in (10). An example of an optimized shopping list by the two-step model is shown in Fig. 1. Volumes are expressed in litres (l) and weights in kilograms (kg).

Fig. 1.
figure 1

Example of a shopping list optimized by the two-step model

Full size image

4 Experimental Simulation

In this section we present the experimental results based on layout and orders made available by a German retailer. Simulation experiments are conducted on 10 real historical BOPS orders that contains 48 items on average with a standard deviation of 5. All models were solved with the Excel Solver performed on a Windows 10 virtual machine with dual-core Intel core i5 processor 2.3 GHz and 4GB of RAM.

By adopting the two-step model proposed in this work, the space of each packaging bag should be used to the greatest extent and the articles are reasonably stacked and will not be damaged. Therefore the articles can be directly scanned during the picking process as they are ready-to-go at the end of a picking trip. Consider that the reality picking is fast but rearranging and repacking articles at the cashier is time consuming. We conducted a simulation for a comprehensive understanding on the total manpower required by the picking, scanning, and packing processes: the travel time for moving between the shelves are derived from [8]. During the picking task, the time to pick up an item is estimated as 7 s if the optimization methods we propose, that adapt to the scan-as-you-pick model is applied, and 5 s otherwise. At the cashier, the time to scan and place the products in the final bag is estimated as 8 s per product when the scan-as-you-pick protocol is not applied, of which 5 for the picker and 3 for the cashier [11] (the picker loads the article and packs, the cashier scans).

The result shows a remarkable difference: an average time of 177 s is saved when the optimization methods that adapt to the scan-as-you-pick model is applied, that roughly equals to 23% of the total time required. Such an improvement can be achieved only when the picker is completely free of distractions. Deviations could exist in actual operation due to the number of articles, the pickers’ experience, and even the articles’ attributes, therefore the estimation is only marginal. Nevertheless, the optimization method proposed in this work reduces the complexity of the task, thereby reduces the pressure on employees.

The solutions of the model are reported in Fig. 2. For each of the 10 orders, we show the estimated number of bags and the total volume and weight of the articles in each shopping bag. The maximum volume and weight of a shopping bag are set to 12 l and 9 kg respectively.

Fig. 2.
figure 2

Simulation results for 10 order picking and packing tasks. For each bag used, the volume (blue) and weight (red) are reported

Full size image

In Fig. 2 we can observe that the articles are divided evenly in each shopping bag (each pair of blue/red columns in the chart represents a bag). The maximum difference in terms of volume and weight between all the shopping bags for a certain shopping list is 0.363 l and 0.315 kg. We can conclude that the model estimates the number of shopping bags required correctly and allocates the articles in each bag with respect to the attributes reasonably. In general, an significant advantage of the optimization model in terms of manpower saving can be observed.

5 Conclusion

In this work we propose a two-step optimization approach to increase the overall efficiency of the in-store picking and packing problem in BOPS retailing. Articles are assigned into balanced shopping bags according to its characteristics. Such an approach prevents the products from being damaged during the picking process, and makes the packing task easier for pickers. It also reduces the time required to process an order when packaging time is also considered.