# Optimization Strategies for In-Store Order Picking in Omnichannel Retailing

Xiaochen Chou, Nicola Ognibene Pietri, Dominic Loske, Matthias Klumpp, Roberto Montemanni

► To cite this version:

Xiaochen Chou, Nicola Ognibene Pietri, Dominic Loske, Matthias Klumpp, Roberto Montemanni. Optimization Strategies for In-Store Order Picking in Omnichannel Retailing. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2021, Nantes, France. pp.603-611, 10.1007/978-3-030-85902-2_64. hal-04117698

HAL Id: hal-04117698

https://inria.hal.science/hal-04117698

Submitted on 5 Jun 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# Optimization Strategies for In-Store Order Picking in Omnichannel Retailing

Xiaochen Chou<sup>1,2</sup>, Nicola Ognibene Pietri<sup>2</sup>, Dominic Loske<sup>3,5</sup>, Matthias Klumpp<sup>4,5,6</sup>, and Roberto Montemanni<sup>2</sup>

<sup>1</sup> Dalle Molle Institute for Artificial Intelligence, Switzerland

<sup>2</sup> University of Modena and Reggio Emilia, Italy

<sup>3</sup> University of Murcia, Spain

<sup>4</sup> Georg-August-University of Göttingen, Germany

<sup>5</sup> FOM University of Applied Sciences Essen, Germany

<sup>6</sup> Fraunhofer IML Dortmund, Germany

**Abstract.** The COVID-19 pandemic is changing consumer behavior and accelerating the interest for online grocery purchases. Hence, traditional brick-and-mortar retailers are developing omnichannel solutions enabling online purchases in parallel to normal activities. Buy-Online-Pick-up-in-Store concepts are flourishing in this context, and they are the topic of this work.

In this paper we propose a novel application of the sequential ordering problem to model products picking throughout the store shelves. The result is an optimized picking sequence that however takes also into account the characteristics of the goods (fragility, weight, etc). The aim is to preserve goods integrity while allowing the pickers to optimize their route through the shop. The approach is exemplified on historical online orders of a real German shop.

**Keywords:** In-Store Order Picking · Omnichannel Grocery Retailing · Sequential Ordering Problem.

## 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 on-line 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 in-vestigates 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 ex-isting 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. Characteris-tics 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 Section 3.1 in detail and explain how to solve the in-store picking problem as an SOP in Section 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 = \begin{cases} 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{cases}$$

$$HeavSC = \begin{cases} 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{cases}$$

$$DensSC = 2 + 2 \cdot [Density/0.30]$$

$$PackSC = \text{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:

$$ Score = SizeSC \cdot 0.15 + HeavSC \cdot 0.15 + DensSC \cdot 0.30 + PackSC \cdot 0.40 $$

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><caption>**Table 1.** An example of an order with the scores attributed to the articles</caption><thead><tr><th>Product</th><th>Volume</th><th>Mass</th><th>Density</th><th>Packaging</th><th>Score</th></tr></thead><tbody><tr><td>1L Bottle</td><td>1.00</td><td>1.02</td><td>1.02</td><td>Bottle</td><td>13.24</td></tr><tr><td>2L Bottle</td><td>2.00</td><td>2.05</td><td>1.03</td><td>Bottle</td><td>15.86</td></tr><tr><td>Energy Drink</td><td>0.50</td><td>0.52</td><td>1.04</td><td>Can</td><td>10.02</td></tr><tr><td>Chips</td><td>1.00</td><td>0.13</td><td>0.13</td><td>Bag</td><td>3.73</td></tr><tr><td>Eggs</td><td>0.90</td><td>0.38</td><td>0.42</td><td>Carton</td><td>6.54</td></tr><tr><td>Milk</td><td>1.00</td><td>1.05</td><td>1.05</td><td>Carton</td><td>8.94</td></tr><tr><td>Instant Noodles</td><td>0.40</td><td>0.12</td><td>0.30</td><td>Package</td><td>4.61</td></tr><tr><td>Pasta</td><td>1.40</td><td>0.50</td><td>0.36</td><td>Package</td><td>6.95</td></tr><tr><td>Jam</td><td>0.20</td><td>0.37</td><td>1.85</td><td>Glass</td><td>9.38</td></tr><tr><td>Wine Bottle</td><td>0.75</td><td>1.20</td><td>1.60</td><td>Bottle</td><td>14.09</td></tr></tbody></table>

## 3.2 The Route Planner

With the scoring model described in Section 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
<figure><img src="image_3.png" /><figcaption>**Fig. 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.</figcaption></figure>

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.

# 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.85m/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
<figure><img src="image_4.png" /><figcaption>**Fig. 2.** Simulation of travel times for 10 representative online orders in four different scenarios.</figcaption></figure>

dimensions issues). The third list considered is ordered according to the opti-
mal 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 (Section 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.

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 seconds 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 seconds 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 seconds 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 seconds 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.

References

1. Hübner, A., Kuhn, H., Sternbeck, M.G.: Demand and supply chain planning in grocery retail: an operations planning framework. International Journal of Retail & Distribution Management 41(7), 512-530 (2013).
2. Pires, M., Camanho, A., Amorim, P.: Solving the grocery backroom sizing problem. International Journal of Production Research 58(18), 5707-5720 (2020).

3. Reiner, G., Teller, C., Kotzab, H.: Analyzing the efficient execution of in-store logistics processes in grocery retailing. The case of dairy products. Production and Operations Management 22, 924-939 (2013).

4. Hübner, A., Kuhn, H., Wollenburg, J.: Last mile fulfilment and distribution in omni-channel grocery retailing. International Journal of Retail & Distribution Management 44(3), 228-247 (2016).

5. Wang, Y., Xu, R., Schwartz, M., Chen, X.: COVID-19 and Retail Grocery Management: Insights from a Broad-Based Consumer Survey. IEEE Engineering Management Review 48(3), 202-211 (2020).

6. Boysen, N., Koster, R. de, Füßler. D.: The forgotten sons. Warehousing systems for brick-and-mortar retail chains. European Journal of Operational Research 288(2), 361-381 (2021).

7. Wollenburg, J., Hübner, A., Kuhn, H., Trautrimms, A.: From bricks-and-mortar to bricks-and-clicks. International Journal of Physical Distribution & Logistics Management 48(4), 415-438 (2018).

8. Li, Z., Yang, W., Jin, H.S., Wang, D.: Omnichannel retailing operations with coupon promotions. Journal of Retailing and Consumer Services 58, 102324 (2021).

9. Kim, K., Han, S.-L., Jang, Y.-Y., Shin, Y.-C.: The effects of the antecedents of "Buy-Online-Pick-up-In-Store" service on consumer's BOPIS choice behaviour. Sustainability 12(23), 9989 (2020).

10. Kong, R., Luo, L., Chen, L., Keblis, M.F.: The effects of BOPS implementation under different pricing strategies in omnichannel retailing. Transportation Research Part E: Logistics and Transportation Review 141, 102014 (2020).

11. Chou, X., Loske, D., Klumpp, M., Gambardella, L.M., Montemanni, R.: In-Store Picking Strategies for Online Orders in Grocery Retail Logistics. Submitted for publication (2021).

12. Matusiak, M., Koster, R. de, Saarinen, J.: Utilizing individual picker skills to improve order batching in a warehouse. European Journal of Operational Research 263(3), 888-899 (2017).

13. Ogasawara, A., Ishigaki, A., Yasui, S.: Adaptive storage reassignment in order picking systems to picker learning and change of demand. Procedia Manufacturing 39, 1623-1632 (2019).

14. Grosse, E.H., Calzavara, M., Glock, C.H., Sgarbosssa, F.: Incorporating human factors into decision support models for production and logistics. Current state of research. IFAC-PapersOnLine 50(1), 6900-6905 (2017).

15. Pardines, I., Lopez, V.: Shop&Go: TSP heuristics for an optimal shopping with smartphones. Science China Information Sciences 56, 1-12 (2013).

16. Liebmann, H.P., Zentes, J.: Handelsmanagement. Vahlen, Munich (2001).

17. Ozgormusa, E., Smith, A.E.: A data-driven approach to grocery store block layout. Computers & Industrial Engineering 139, 105562 (2020).

18. Filipe, S., Henriques Marques, S., Fátima Salgueiro. M. de: Customers' relationship with their grocery store: Direct and moderating effects from store format and loyalty programs. Journal of Retailing and Consumer Services 37, 7888 (2017).

19. Mojana, M., Montemanni, R., Di Caro, G., Gambardella, L.M.: A branch and bound approach for the sequential ordering problem. Lecture Notes in Management Science 4(1), 266-27 (2012).

20. Montemanni, R., Smith, D.H., Rizzoli, A.E., Gambardella, L.M.: Sequential ordering problems for crane scheduling in port terminals. International Journal of Simulation and Process Modelling 5(4), 348-361 (2009).