Keywords

1 Introduction

Traditional factors such as a growing range of products, volatile demand behavior, or scarce logistics and sales space have been affecting grocery retailing for years. Thus, research has predominantly focused on demand and supply chain planning [1], the in-store backroom sizing problem [2], efficient in-store processes [3], as well as last-mile distribution [4]. Along with the COVID-19 pandemic, existing parameters were ex-tended through changing consumer behavior, switching from offline to online purchases [5]. As a consequence, the design of efficient operations to fulfill this online demand is a recent challenge for traditional brick-and-mortar (B&M) retailers that focused on offline sales during the last decades [6]. For the design of these omnichannel operations, [7] differ between three typologies: (1) An integrated distribution center for online and offline orders that enable bulk and single unit picking and delivery, (2) distribution centers exclusively utilized to fulfill online orders, and (3) grocery retailers using their B&M structures for online order fulfillment, especially on the store-level to fulfill online and offline demands. These stores are named Buy-Online-Pick-up-in-Store concepts (BOPS) and are the argument of the remainder of this paper. We position our research at the interface of BOPS together with the optimization of operational efficiency in in-store order picking.

Observing the existing literature, BOPS and order picking are well-examined fields of research in marketing and operations management. Form a marketing perspective, focusing on, e.g., coupon promotions [8], customer behavior [9], or pricing strategies [10]. Regarding order picking, an extensive body of research investigates the human factor [11], batch assignment [12], and storage assignment [13] with the aim of optimizing these laborious and costly operations. However, approaches optimizing in-store order picking operations are scarce. In the existing literature, the grocery store order picking problem is treated as an open Traveling Salesman Problem (TSP) [14] on an underlying graph representing the location of the items within the shop. Therefore, the obtained solutions are the shortest tours from the store entrance to the cashiers going through all the nodes associated with goods of a given shopping list [15]. In a BOPS context, this approach makes sense since in-store logistics is performed for the most part by human operators and is considered a major cost-driver. It can account for up to 40% of all the activities executed during working hours [16]. Hence, a solution minimizing the time required for order picking can reduce the impact of BOPS-related movements on the overall logistics. However, when designing the layout of a store, the factors considered are normally revenue maximization [7, 17] and customer satisfaction [18]. Thus, the product attributes analyzed are visibility, position to maximize impulsive purchases, variety, and availability. Characteristics like fragility or dimensions are simply left out of the equation when articles are located within a shop. As a consequence, operating according to shortest tours among the locations of the items without considering their characteristics might lead to product damaging (e.g., storing bottles ending on top of fresh fruit) or to a situation where the products can be placed into the final bags only after the whole tour is finished, causing a rearranging over-head.

The objective of this study is to explore how adding precedence constraints among the products to avoid the aforementioned issues alters the performance of the TSP solver. The resulting optimization model to represent the order picking is then a Sequential Ordering Problem (SOP) [19, 20]. We will investigate the time overhead associated with the (more realistic) SOP solutions with respect to TSP solutions.

2 Problem Description

The idea behind the operational problem treated in this paper can be outlined as follows: in order to implement efficient in-store picking operations for online orders, the shortest path analysis is required for a given set of articles to be picked, given the store layout settings (topology of the shop and positioning of the products in the shelves). This operation has been proven effective in improving the pickers’ efficiency in the BOPS model. However, a rearrangement of the articles is often required at the cashier to reposition fragile articles and/or to save final packaging space. Therefore, we propose to score the articles by characteristics and divide them into several sub-groups with different priorities. By adding these precedence constraints, the in-store picking problem can be solved as an SOP. In the following section, we discuss the scoring model in Sect. 3.1 in detail and explain how to solve the in-store picking problem as an SOP in Sect. 3.2.

3 Methodology

3.1 The Scoring Model

An order usually contains the following information for each of its articles: name of and producer, quantity, volume/weight, and the type of packaging. In order to have a complete set of data with normalized units of measurement, we select size, heaviness, and resistance (internal and external) as the main characteristics to be considered during an in-store picking tour. Size and heaviness are represented by the volume and mass of a product, that are the characteristics usually considered in determining the picking order for items. Another important characteristic is fragility, which is influenced by the internal and external resistance to pressure. Therefore, density and packaging type are considered as further attributes. All the attributes contribute to a weighted sum, and to have a reliable result, it is important to normalize the different attributes in the scoring system.

The scores for the packaging type are assigned based on estimated sturdiness. The scores for mass, volume, and density are defined by ad-hoc piecewise functions to take into account that the impact of these attributes varies based on their value. For example, when the volume of an article is small, it will not affect the picking order significantly. Hence, the associated coefficient is expected to be extremely value. On the contrary, when the volume of an article exceeds a certain threshold, people tend to collect it first, as it is a large item. In this case, the coefficient of volume should amplify its magnitude. The scoring function of the attributes we have derived by simulating real-world scenarios in common sense, are defined as follows:

  • \(SizeSC = {\left\{ \begin{array}{ll} 1, &{} \text {if } Volume \le 0.15L\\ 1+[(Volume - 0.05)/0.10], &{}\text {if } 0.15L< Volume \le 0.85L\\ 3+[(Volume - 0.15)/0.10], &{}\text {if } 0.85L < Volume \le 1.50L\\ 11+2\cdot [Volume/0.50], &{}\text {if } Volume > 1.50L \end{array}\right. }\)

  • \(HeavSC = {\left\{ \begin{array}{ll} 1+[Mass/0.10], &{}\text {if } Mass \le 1Kg\\ 3+2\cdot [Mass/0.25], &{}\text {if } 1Kg < Mass \le 2Kg\\ 5\cdot [Mass/0.25]-20, &{}\text {if } Mass > 2Kg\\ \end{array}\right. }\)

  • DensSC = \(2+2\cdot [Density/0.30]\)

  • PackSC = bag 2; tube 4; pack 6; carton 7; glass 10; can 14; bottle 18

With the scores defined in the same standard unit, the attributes are then combined in a weighted sum model. The priority of an article increases as the result of the weighted sum increases (e.g., the article with the highest output value has to be collected first). To achieve the proper model, the coefficients (weights) of the attributes have manually adjusted based on real-world simulations until satisfying picking lists were obtained. The resulting coefficients are incorporated in the following formula, which implement our scoring system:

$$\begin{aligned} \begin{aligned} Score = SizeSC \cdot 0.15 + HeavSC\cdot 0.15 + DensSC\cdot 0.30 + PackSC\cdot 0.40 \end{aligned} \end{aligned}$$

An example of a random order and the attributes associated with its articles is presented in Table 1. The attributes of each article are shown together with the score received by the article according to the scoring system.

Table 1. An example of an order with the scores attributed to the articles
Full size table

3.2 The Route Planner

With the scoring model described in Sect. 3.1, articles in the shopping list have different priorities to be picked. The in-store order picking problem formalized in this work can therefore be modelled as a Sequential Ordering Problem. Given a weighted graph, the SOP is a TSP with precedence constraints between pairs of vertices. The objective is to find a Hamiltonian Path with minimum cost that satisfies the precedence constraints.

An instance of the SOP is represented by two graphs: a cost graph and a precedence graph. The cost graph is a weighted directed graph \(G = (V, E)\) where V is the set of vertices (corresponding to articles in our case), \(E =\{(i, j) | i,j \in V\}\) is the set of edges, and each edge \((i, j) \in E\) has a cost \(t_{ij}\). The precedence graph is a directed graph \(H = (V, P)\) where V is the same set of vertices. When an edge \((i, j) \in P\), vertex \(v_i\) must precede vertex \(v_j\) in any feasible solution. A Hamiltonian Path is a permutation of the full set of vertices that each vertex appears exactly once in the given graph. For a solution S, the cost is defined as \(\sum _{(i,j) \in S} t_{ij}\). Given a start and a final vertex, the objective of the SOP is to find the Hamiltonian path with minimum cost that satisfies all the precedence constraints. It corresponds to the picking order in our application. However, if we strictly follow the precedence constraints, a lot of back-and-forth movements are expected, and a long time might be required to complete the task. This inefficiency is not the original aim of using the SOP model, but rather a side effect to the benefits of a SOP solution. Therefore, we propose also a relaxed SOP model to have a trade-off between priorities and total picking time. We define a limited number of precedence classes based on the scores. Precedences among articles in a same class are relaxed, assuming they are basically equivalent in terms of score. The number of classes can be adjusted according to the actual situation. In this work, we divide the articles into four precedence classes, in such a way that class 1 contains articles with a score up to 5.00; class 2 the articles with a score between 5.00 and 8.50; class 3 the articles with a score between 8.50 and 12.00; class 4 the articles with a score higher than 12.00.

Fig. 1.
figure 1

Layout of a real store with numbers corresponding to zones containing products of different categories and a path indicating the optimal relaxed SOP solution of a given shopping list.

Full size image

4 Experimental Simulation

In this section, we present methods and results for an experimental simulation of a real store in German. The layout of the store is presented in Fig. 1, with the numbers corresponding to areas/zones containing products of different categories. A path representing the optimal relaxed SOP tour for a given shopping list, is also depicted. Zone 1 includes the entrance and Zone 15 includes the cashier desks, they are the fixed starting and ending points in our model. Each article is associated with the zone containing it, and zones are used to estimate travel times. The travel time \(t_{ij}\) from zone i to zone j is calculated assuming a walking speed of 0.85 m/s and considering the shortest path. The travel time between two articles in the same zone is set to zero. The time to pick up articles is not considered, since it has no influence on the total time spent moving in the shop. In the simulation, we compare the time required to pick all the articles on the shopping lists when the given lists are ordered in different ways. Ten representative online orders, consisting of 36.6 items on average and with a standard deviation of 6.12, are considered. The original shopping lists received are in random order (no optimization solution). The second picking sequence is calculated as the optimal TSP solution [14] (this solution ignores fragility and dimensions issues). The third list considered is ordered according to the optimal SOP solution, strictly following precedence constraint. For example, in the shopping list presented in Table 1, we follow the descending order of the Score value to pick the corresponding item, with 2L bottle being the first and chips being the last to be picked. This solution only optimizes the articles’ sequence but not the picking path. The fourth list is ordered according to the relaxed SOP solution (Sect. 3.2, see also Fig. 1), which optimizes a trade-off between the characteristics of the articles and the total travel time. The SOP optimal solutions can be obtained by the algorithm described in [19]. To summarize, four scenarios are analyzed: (1) no optimization; (2) articles ordered according to the TSP solution; (3) articles ordered according to the SOP solution; (4) articles ordered according to the relaxed SOP solution.

The simulation results are reported in Fig. 2. We can observe that TSP solutions performs the best in terms of travel time, as expected. Knowing the disadvantages of TSP solutions in terms of sequencing of the articles, our main interest is to estimate the extra time required by the SOP solutions, which takes into account mainly the correct sequencing of the articles. The results from Fig. 2 shows that with the optimal SOP solutions increase the time by 150% on average compared to TSP solutions, while relaxed SOP solutions increase the time by only 71%, while retaining an operationally acceptable sequencing of the article. This indicates that relaxed SOP solutions are considerable choice for this problem.

Fig. 2.
figure 2

Simulation of travel times for 10 representative online orders in four different scenarios.

Full size image

Let us consider order 3 as an example to understand the characteristics of the different solutions. The order contains 46 different articles from four different zones. The articles are mainly located in Zones 10, 11, and 12, but one is in Zone 3 (Fig. 1). The list is ordered as the customer added the articles to the shopping cart. Therefore, when no optimization is considered, the picker first heads to Zone 11, then travels back and forth among Zones 11, 12, and 10 and finally goes to Zone 3 to pick the last item before going to the cashier at Zone 15. It takes 349 s travel time to finish the task, and yet more time is required to sort out the messy shopping cart at the cashier (there is also a risk of damaging the goods, if the picker is not careful enough). When the TSP solution is considered, the picker visits Zones 3, 10, 11, 12 in this order. It takes only 145 s travel time to finish the task, but some more time is required to reorder the items for the subsequent packing process, and extra care had to be taken by the picker not to damage any product. When the list is ordered according to the SOP solution, heavy and non-fragile articles are picked first, leaving light, small and fragile articles for the end. The picker travels back and forth among Zones 11, 10 and 12, and goes to zone 3 at a certain point in the middle of the process. It takes 367 s travel time to complete the task (even more than the unsorted list), but in this case no extra time is needed to rearrange the articles, since packing is already sorted. When the list is ordered according to the relaxed SOP solution, the has considerably fewer moves back and forth among the zones. It takes only 231 s travel time, and there is no need to rearrange the articles for a final packing.

In conclusion, the relaxed SOP solution shows a good compromise between being very fast with unsorted (and potentially damaged) goods and producing a ready-to-go package already while picking articles. Furthermore, it is worth to mention that “scan as you pick” devices are becoming popular in grocery stores. The receipts are ready at the end of the tour and the articles can be directly packed in bags during picking. In this case, the benefit of SOP-based model is even more straightforward.

5 Conclusions

The research on the optimization strategies for in-store order picking presented in this paper aspires to contribute to the improvement of omnichannel in-store logistics operations for brick-and-mortar grocery retails. We proposed an optimization approach for the in-store order picking problem in the context of a Buy-Online-Pick-up-in-Store system relying on human workforce. We discussed the benefit of reordering shopping lists according to an ad-hoc precedence model instead, which prevents potential dam-ages to the goods during the in-store picking phase and also makes the packaging task trivial, with benefit also for customers, that have articles sorted in a correct order inside their bags. Experimental simulations on a real-world store have been per-formed, demonstrating the practicality and applicability of the approach, which has been shown to provide a good trade-off between efficiency and customer satisfaction. With the increasing popularity of co-called “scan as you pick” devices, even further benefits from this model can be foreseen.