Joint Shelf Design and Space Planning Problem With Placement Options

Abstract

This article introduces the first joint shelf design and space planning problem that considers two placement options for items—hanging and shelving—on flexible shelves. These types of shelves are used in sectors such as do-it-yourself and toy retail, and for household goods in grocery stores. However, they have received limited attention in the literature, which typically focuses on regular shelves with a single placement option: placing items on shelf panels. The problem requires three interdependent decisions: (1) the placement option for each item (shelving or hanging), (2) the shelf design (number and vertical positioning of shelf panels), and (3) the shelf space planning (assignment of facings as well as the vertical and horizontal positioning of items). We formalize this problem as a mixed-integer linear program (MILP) and develop a greedy multi-start matheuristic to efficiently solve practical instances. Computational experiments demonstrate that our algorithm outperforms both a commercial solver and a benchmark method for two-dimensional shelf space planning in terms of runtime and solution quality. A comprehensive analysis of synthetic instances and a real-world case study provides several managerial insights. First, hanging items enables more flexible use of shelf space, which is especially beneficial when item variety is high. However, when large vertical grabbing gaps must be considered, stacking items on shelf panels may be more advantageous. In turn, there is a risk of wasted space due to height or width mismatches. Second, the number and size of the segments on the shelf significantly influence layout profitability, highlighting the need to jointly optimize shelf design and space allocation. Third, it is common practice to arrange hanging items in horizontal rows, which can be facilitated by segmenting the shelf space. While this improves visual appeal, increasing the number of segments tends to reduce overall space utilization and profitability. Finally, a real-world case study involving 237 products across six categories from a European grocery retailer confirms the practical applicability of our approach. It demonstrates significant potential for improving space utilization and layout efficiency.

1. Introduction

In retail, shelf space is the most valuable asset that must be managed effectively (Irion et al., 2012). Since the 1970s, scientists have developed optimization models to support the decision maker in allocating scarce shelf space to products (items) to be displayed. Given a predefined space for the considered product category as well as a fixed assortment, the objective is to generate a profit maximizing shelf layout. The layout is illustrated in a planogram, that shows for each item (a) the number of horizontal and vertical facings (space assignment), (b) the vertical position of shelf panels and items (vertical allocation), and (c) the horizontal position of items (horizontal location) (Bianchi-Aguiar et al., 2021). Retailers use different software providers to create such planograms which often use simplified rules of thumb (Hübner and Kuhn, 2012).

Although the literature on shelf space planning is vast, there remain discrepancies that prevent or limit the practical implementation of these approaches (Düsterhöft and Hübner, 2023). Particularly, literature focuses on shelf space problems in which items are placed on shelf panels (Bianchi-Aguiar et al., 2021; Hübner et al., 2020). However, there are many other shelf types in practice that are more suitable for certain categories but have received limited attention so far (Düsterhöft and Hübner, 2023). Note that we refer to a single board of a shelf as a “shelf panel” to distinguish this term from the entire shelf.

This contribution studies shelf space planning on flexible shelves that allow items to be either hung or shelved. One example of such a shelf type are pegboards which are shelves with a perforated back wall. Flexible shelves are used in a variety of retail environments. In supermarkets, they are commonly found in the non-food section (e.g., kitchen supplies and stationery; see top left of Figure 1) and in the cleaning supplies aisle (bottom left of Figure 1). In hardware stores, they can be found in the pet supplies section (top right of Figure 1) and in displays of paint tools such as paint rollers (bottom right of Figure 1).

Figure 1.

Examples of flexible shelves in various retail contexts.

Despite their practical relevance, flexible shelves are rarely discussed in the literature, which focuses primarily on the placement and sizing of shelf segments under the assumption that every item must be placed on a shelf panel. This can have a negative impact on space utilization and visibility of an item, resulting in reduced consumer satisfaction and loss of sales. Other contributions consider the two-dimensional placement of items, for example, in the context of freezer boxes or cabinets (Geismar et al., 2015; Hübner et al., 2020). These approaches can also be applied to a shelf planning problem with only hanging items. However, it then ignores the possibility that some items of the same category need to be placed on a shelf panel, for example because they are too heavy or do not have suitable packaging for hanging.

There is no article in which both items that are hung and items that are placed on a shelf panel are considered together. Moreover, some items may have both placement options. By changing the shelf design, more space can be created for hanging and placement on a shelf panel, respectively. Therefore, jointly deciding on the shelf design and space planning is beneficial. The problem investigated in this article builds on the contributions published so far in the field of shelf space planning and extends them substantially. In particular, we make the following contributions to close the research gap:

We present a first mixed-integer linear program for this novel problem that determines the shelf design and, for each item, the placement option, number and arrangement of facings, and location on the shelf.

A greedy multi-start matheuristic is proposed for addressing practical problem sizes, and its performance is evaluated using a simulated data set.

We show that our solution approach achieves competitive results compared to an approach from literature that considers a special case of our problem.

Lastly, we give important managerial insights based on an extensive sensitivity analysis and a practical case study with a major European grocery retailer.

The remainder of this study is organized as follows: Section 2 describes the problem setting and Section 3 reviews related literature. Section 4 presents a novel mixed-integer linear program that formulates the decision problem considered. Section 5 develops a greedy multi-start matheuristic for solving problem instances of practical size. Section 6 then demonstrates the performance of the heuristic developed and analyzes the influence of specific problem features on the results achieved. Afterwards, Section 7 provides a practical case study. The study concludes in Section 8 with a summary of the managerial insights and an outlook for future research.

2. Problem Description

The decision problem at hand addresses a joint shelf design and shelf space planning problem in which a given set of items is to be placed with at least one facing on a shelf with a given width and height—thus, the assortment is assumed given. The flexible shelf offers two options for placing the items: an upper part (hanging area), in which items can be hung, and a lower part (shelving area), which consists of shelf panels for shelved items. However, the shelf can also be exclusively configured for hanging items or the shelf can be completely equipped with shelf panels for shelved items. In practice, those shelves are typically 100 cm wide and between 140 cm and 180 cm high. However, not all items offer both placement options. Flexible items can either be hung or placed on a shelf panel, while only-shelved and only-hanging items are limited to their respective placement option. Examples of flexible items are food storage containers and baking tins, whereas measuring or thermal cups are examples for only-shelved items since they may not have suitable packaging or may be too heavy to hang.

Figure 2 (left image) shows a pack of knives hanging. This item can easily fall over and create a messy shelf appearance if it is placed on a shelf panel in the same display orientation as in the hanging area (middle image of Figure 2). To prevent this, the item must be laid down, changing its display orientation (right image of Figure 2). As a result, this knife would have low visibility on a shelf panel and may therefore be categorized as an only-hanging item. Other examples of this type of item are cake toppers and toothpicks. The example of Figure 2, however, shows that the space occupied by a certain number of facings in the hanging or shelving area could be different.

Figure 2.

Item requiring hanging placement (left) due to low stability (middle) or low visibility (right) on a shelf panel.

Figure 3 shows an example of food storage containers, which belong to the category of flexible items. A specific rectangle is defined by the item’s horizontal and vertical number of facings, as well as its placement option, hanging in the shelf or placed on a shelf panel. For visual appeal, only rectangular arrangements are allowed. Figure 3 provides an overview of possible rectangles of this flexible item with a maximum of three facings. The number of facings assigned to an item defines the number of front-most units that are directly visible to the customer. The more facings are assigned to an item, the more likely it is that it will be seen by customers and therefore purchased more often. Grabbing gaps must also be considered below each of the hanging units of an item, which increases the height of the rectangle. It is worth noting that in the example shown in Figure 3, the orientation of the item changes between hanging and shelved items. However, it is also possible that the display orientation does not change or that several different display orientations are possible for each of the placement options.

Figure 3.

Example of possible rectangles of a flexible item with maximum three facings.

The number of assignable facings is usually limited, for example, due to marketing restrictions. The maximum number may depend on the selected placement option, as some items cannot be stacked because of their shape or can only be stacked up to a certain level. Non-stackable items are, for example, thermal cups or meat tenderizers. Multiple facings of this item type can only be arranged horizontally.

The problem description so far illustrates the two interlinked decision problems, namely the shelf design problem and the shelf space problem. The shelf design problem refers to the problem of how the given shelf is divided into the hanging and shelving area and how many shelf panels are set up in the shelving area, which in turn define the respective shelf segments. We assume that each shelf panel extends across the entire width of the shelf. The shelf space problem, on the other hand, defines how the available space in the hanging area and on the shelf panels is utilized by the selected facings and their arrangement, placement options and orientations of the shelved items. In this context, the necessary grabbing gaps must also be considered.

Figure 4 illustrates a feasible solution of the defined decision problem in which 50 items with various placement options have been positioned on a shelf 100 cm wide and 160 cm high. The layout uses two shelf segments and one mixed segment that contains items that are hung or placed on the upmost shelf panel. For easy removal of the items, two major kinds of vertical grabbing gaps must be considered when placing the items, a vertical grabbing gap below each hanging unit of an item and below each shelf panel.

Figure 4.

Example of a feasible shelf layout with 50 items.

The objective of the planning problem is to maximize total profit as the sum of margin multiplied by realized demand. A space-elastic demand is assumed, which depends on how many facings are assigned to each item, whether the item is hanging on the shelf or placed on a shelf panel, and, in addition, which display orientation is chosen. We denote the entire planning problem as the Joint Shelf Design and Space Planning Problem with Placement Options (JSDSPP-PO), which decides on the following interlinked decisions:

Which items should be placed on a shelf panel and which should be hung?

How many shelf panels are required and on which vertical level should they be positioned?

How many facings should be assigned to each item and how should they be arranged?

1. —

On which vertical and horizontal position should hanging items be placed?

—

On which shelf panel and on which horizontal position should shelved items be placed?

Note that each shelf space planning problem involves elements of the knapsack problem at its core. The JSDSPP-PO incorporates multiple-choice aspects by selecting from a set of possible arrangements for each item, a two-dimensional component by considering both width and height constraints, and multi-knapsack features through the assignment of items to distinct segments with varying capacities. The classification of cutting and packing problems developed by Wäscher et al. (2007) treats the problem as a two-dimensional rectangular multiple heterogeneous knapsack problem. For fixed facings and placement options, strip packing algorithms can be used to pack the resulting rectangles into a fixed-width shelf and verify whether the height constraint is satisfied. However, unlike classical strip packing, the JSDSPP-PO also optimizes these facing and placement decisions. Additionally, it resembles class-constrained two-dimensional packing, as placement options can only be assigned to specific segments and spatial feasibility must be ensured. However, shelf space planning introduces unique elements such as capacity restrictions and positioning requirements, which distinguish it from traditional knapsack formulations and cutting and packing problems. The shelf design and shelf space problem considered in the JSDSPP-PO has not yet been addressed in the literature so far. This will be discussed in the next section.

3. Literature Review

JSDSPP-PO has three distinctive characteristics: shelf design, placement options and display orientation. The related literature was scanned focusing on these aspects. In particular, we included contributions that either (a) incorporate flexible shelf designs or more realistic shelf designs with heterogeneous segment heights, (b) consider display orientation decisions, or (c) study placement options other than placing items on shelf panels. An overview of the most relevant contributions with the assumed demand factors is shown in Table 1. These works are categorized using the classification scheme proposed by Bianchi-Aguiar et al. (2021), which distinguishes shelf space planning problems based on integrated decisions (i.e., space assignment (S), vertical allocation (A), and horizontal location (L)) and other planning aspects such as assortment, pricing, or replenishment. Our problem is accordingly classified as SAL. In addition, we distinguish between regular shelves, where the shelf panels cover the entire length of the shelf, limiting vertical placement but allowing free horizontal placement, and non-regular shelves.

Table 1.

Related shelf space planning literature.

		Demand factors
Contribution	Decisions1	Space	Horizontal	Vertical	Stochastic	# segments	Shelf design	Item positioning	Display orientation
Regular shelves
Hübner and Schaal (2017)	R-S	✓				single	fixed	on shelf panels	decision
									(2 DOs2)
Murray et al. (2010)	P-SA	✓	✓	✓		multiple	fixed	on shelf panels	decision
									(3 DOs2)
Bai et al. (2013)	SA	✓	✓	✓		multiple	fixed	on shelf panels	fixed
Düsterhöft et al. (2020)	R-SA	✓	✓	✓		multiple	fixed	on shelf panels	fixed
Rabbani et al. (2018)	SA	✓	✓	✓		fixed number	variable vertical position of shelf panels	on shelf panels	decision
									(2 DOs2)
Hübner et al. (2021)	R-SA	✓	✓	✓		variable	variable vertical position of shelf panels	on shelf panels	fixed
Non-regular shelves
Hübner et al. (2020)	A-SAL	✓			✓	single	fixed	on a 2d area	fixed
Geismar et al. (2015)	SAL	✓(linear)		✓		multiple	fixed	on a row in a column	unspecified
Gecili and Parikh (2022)	SAL	✓(linear)				variable	variable horizontal & vertical positions of shelf panels	on shelf panels	fixed
This study	SAL	✓				variable	variable vertical position of shelf panels	on shelf panels or on a 2d area	decision (max. 2 DOs2)

¹Refer to Bianchi-Aguiar et al. (2021): S = Space assignment; A = Vertical allocation; L = Horizontal location; A- = Assortment; P- = Pricing; R- = Replenishment.

²DO = Display Orientation.

Subsection 3.1 reviews the key demand factors commonly considered in shelf space problems and provides a rationale for the assumed demand function. Subsection 3.2 then reviews problem settings related to the JSDSPP-PO. Finally, Subsection 3.3 identifies the research gap addressed.

3.1. Demand Factors

In the literature, usually a profit function is maximized that contains a non-linear demand function. Demand is typically assumed deterministic and stationary (Bianchi-Aguiar et al., 2021), which we also consider in this study. Empirical studies have demonstrated the impact of various aspects of a shelf layout on stimulating consumer demand. According to a recent literature overview on shelf space planning, the most important demand factors are space and cross-space elasticity, out-of-stock substitution, positioning, and arrangement effects (Bianchi-Aguiar et al., 2021). Curhan (1972) defines space-elastic demand as “the ratio of relative change in unit sales to relative change in shelf space.” The higher the space allocated to an item, the more visible it is, which stimulates impulse buying. This phenomenon has been extensively studied in various empirical studies (Curhan, 1972; Dréze et al., 1994; Eisend, 2014). In a meta-analysis conducted by Eisend (2014), an average space elasticity of 17% was determined, indicating that demand typically increases at a diminishing rate as more facings are allocated. However, Yang and Chen (1999) argue that within a small range of possible facings per item, a linear relationship can serve as a reasonable approximation—an approach followed by some studies (Gecili and Parikh, 2022; Geismar et al., 2015). Cross-space elasticity, where the allocated space for an item affects the demand of its substitutes and complements, is less frequently considered. There are two main reasons for this. First, it is challenging to obtain reliable cross-elasticity estimates, primarily due to data limitations. Second, the influence of cross-space elasticity on item demand is very limited, even if the elasticities are significantly higher than the typically determined empirical values (Schaal and Hübner, 2018). We therefore neglect cross-space elasticity in our decision model. Additionally, the space assignment and the associated shelf quantity impact the availability of an item and may lead to out-of-stock substitution demand. In case of deterministic demand, researchers often assume that supply chain processes can be aligned accordingly so that no out-of-stock situation arises. Another commonly integrated demand effect is position-dependent demand. Studies have shown that items placed on top- and middle-shelf positions and positioned in the center of a shelf tend to generate higher demand (Chandon et al., 2009; Dréze et al., 1994). In the literature, a multiplicative factor is often introduced, which reflects the attractiveness of the allocation of items to a particular shelf (Düsterhöft et al., 2020; Geismar et al., 2015). Lastly, arrangement-dependent demand describes the effect of specific ways of item grouping on the customer attention and thus demand. Pieters et al. (2010) show a positive effect on viewer attention if a display is carefully organized in product families, but a negative effect in case of excessive complexity. This effect experienced little attention in the literature so far.

In this article, we assume a space-elastic demand function. In the JSDSPP-PO, it would also be reasonable to integrate a vertical location effect, but its integration presents significant challenges. In traditional shelf space planning problems, items are assigned to a shelf panel from a predefined set of shelf panels, with each shelf associated with an effectiveness factor that influences demand. However, this approach does not naturally extend to the JSDSPP-PO because shelf panels and items can be freely placed on the shelf, that is, there is no finite set of predefined vertical positions. One possible way to integrate this factor would be a grid-based mathematical model. However, preliminary analysis showed that such an approach performed worse than the formulation proposed in Section 4. Nevertheless, this remains an interesting direction for future research.

3.2. Related Problem Settings

The examination of different placement options is an unexplored aspect in shelf space planning. Traditionally, research has centered on shelves with fixed shelf panels on which items are placed, as these are commonly used in various industries. Hanging items is not an option in this setup. In addition, traditional models do not integrate multiple display orientations, varying shelf segment sizes, or adjustable shelf design (especially the vertical position of shelf panels). Integrating these aspects can enhance the effectiveness of shelf space planning. First, item packaging sometimes allows for multiple acceptable display orientations. The decision on a display orientation affects customer demand not only because of potentially different display areas but also due to esthetic elements of its display such as visibility of the item label (Dréze et al., 1994; Murray et al., 2010). Additionally, it can free up space for high-profit items or increase their visibility. Only a few studies consider display orientation decisions during shelf space planning (Hübner and Schaal, 2017; Murray et al., 2010; Rabbani et al., 2018). Second, adapting the shelf design enables more efficient shelf space utilization. Traditionally, literature interprets shelf space as a one-dimensional value (Borin et al., 1994; Corstjens and Doyle, 1981; Hansen and Heinsbroek, 1979; Hübner and Schaal, 2017; Irion et al., 2012). However, the assumption that the resulting solution can be transformed into a feasible one is only valid in around $10\mathrm{\%}$ of the time without modifications (Düsterhöft et al., 2020). Acknowledging this, some researchers focus on shelves with a fixed shelf design where segments between adjacent shelf panels can vary (Bai et al., 2013; Düsterhöft et al., 2020; Geismar et al., 2015; Murray et al., 2010). Assigning an item to a segment affects the number of units that fit on top or behind the first unit, which in turn influences expected demand and shelf stock. More recent approaches examine the potential of the joint determination of shelf design and item allocation (Gecili and Parikh, 2022; Hübner et al., 2021; Rabbani et al., 2018). However, these studies only analyze setups where items are placed on shelf panels within regular shelves.

Other shelf types are often used for specific item categories. These settings require a two-dimensional perspective since shelf capacity utilization in horizontal and vertical direction is relevant, either due to the possibility of free placement of items on a shelf space area or arrangement rules like placing items in contiguous rectangles. Such two-dimensional shelf space models are rarely studied. Geismar et al. (2015) examine shelf space planning in a DVD store with cabinets with a specified number of rows and columns, where unit sizes match slot sizes. Each of the slots must have one item assigned to it and each item must be assigned to a single cabinet. The facings of an item must form a contiguous rectangle. The objective is to maximize total revenue while considering vertical demand effects but neglecting shelf space elasticity. Hübner et al. (2020) expand the model of Geismar et al. (2015). They deal with items placed on tilted shelves where customers have a total perspective instead of a frontal one. Exemplary categories include meat or book displays as well as pizza shelves. The problem is modeled as a newsvendor problem with stochastic demand, where assortment and shelf space planning are addressed. Sales can be lost if the shelf inventory is too low to meet demand. On the other hand, additional costs can arise if the supply is too high. This is a particularly valid assumption in the case of perishable goods. Gecili and Parikh (2022) optimize shelf design, assortment, and space planning on flexible shelves, including gondola and pegboards, while taking multiple practical constraints into account. Shelf panels of varying lengths can be placed anywhere within the available shelf space. Stacking decisions are made a priori for each item and determine the total height of the rectangles.

3.3. Research Gap

The joint consideration of both placement options (hanging and shelving) has not been studied so far. Although there is one study that also considers flexible shelves (Gecili and Parikh, 2022)—which are the focus of this study—the authors only consider shelving. This is surprising, considering that these flexible shelf types are used for joint hanging and shelving in various industries and product groups in practice, as demonstrated in Figure 1. Moreover, in contrast to Gecili and Parikh (2022), the JSDSPP-PO fixes the length of a shelf panel to the length of the shelf, and the decisions on stacking and the facing arrangement are made jointly with the shelf design.

Only Geismar et al. (2015) and Hübner et al. (2020) consider a two-dimensional display on non-regular shelves, which is a key aspect in the JSDSPP-PO. The JSDSPP-PO extends the problems to varying item sizes, multiple display orientations and a variable shelf design with multiple segments of potentially varying size and an additional placement option. However, compared to Geismar et al. (2015), a single cabinet and shelf space elasticity effect are assumed, vertical location effects are not studied and empty slots (thus unoccupied shelf space) are allowed as a shelf space utilization of $100\mathrm{\%}$ is typically not possible due to varying item sizes. Compared to Hübner et al. (2020), the assortment is assumed fixed and demand deterministic. Thus, approaches for the JSDSPP-PO can be applied to certain variants of the problems described by Geismar et al. (2015) and Hübner et al. (2020), but not to all of them, so it is not a straightforward extension.

In summary, this article introduces the JSDSPP-PO, a novel shelf space planning problem of high practical relevance. It addresses a notable research gap by considering (a) placement options previously unstudied in the literature, as well as decisions related to (b) display orientation, and (c) shelf design, which have received limited attention so far.

4. Decision Model

In this section, we elaborate on the shelf layout evaluation in Subsection 4.1 and present an efficient mathematical model formulation in Subsection 4.2.

4.1. Evaluation and Demand Function

The task is to find a feasible shelf layout as described in Section 2 so that total profit is maximized which depends on the demand realized. As is common in the literature, we assume a space-elastic demand function. For each item $i$ , chosen rectangle $r$ , and placement option $p$ , the profit ${\pi }_{irp}$ is computed based on margin $m_i$ and demand realized ${\lambda }_{irp}$ as follows:

$${\pi }_{irp}=m_i\cdot {\lambda }_{irp}$$

(1)

To reflect a space-elastic demand, a non-linear demand function as proposed in Corstjens and Doyle (1981) is used. The demand depends on the total number of facings of the selected rectangle $r$ , which is defined by its number of horizontal and vertical facings $f_r^{\mathrm{horiz}}$ and $f_r^{\mathrm{vert}}$ , respectively (cf. Figure 3). Let ${\beta }_i$ be the space elasticity factor, that is the diminishing rate of demand. Then, the realized demand ${\lambda }_{irp}$ is computed as the basic demand ${\alpha }_{ip}$ of placing exactly one facing of item $i$ in placement option $p$ multiplied by the number of facings ( $f_r^{\mathrm{horiz}}\cdot f_r^{\mathrm{vert}}$ ) of rectangle $r$ to the power of the space elasticity factor ${\beta }_i$ :

$${\lambda }_{irp}={\alpha }_{ip}\cdot (f_r^{\mathrm{horiz}}\cdot f_r^{\mathrm{vert}}{)}^{{\beta }_i}$$

(2)

The displayed area depends on the selected display orientation and influences the basic demand. In this article, each placement option is assumed to be associated with a fixed display orientation. Let $p=0$ indicate a hanging placement and $p=1$ a shelving placement. Let flexible item $i$ further have height $h_{ip}$ if placement option $p$ is selected. For simplicity, we then assume following relation for flexible items:

$${\alpha }_{i1}=\frac{h_{i1}}{h_{i0}}\cdot {\alpha }_{i0}$$

(3)

Given that the displayed area significantly drives demand in shelf space problems, this assumption is valid. However, it can be omitted if the actual basic demand for each placement option is known. As the maximum facings are known for each item, the profit ${\pi }_{irp}$ can be calculated for each item $i$ , for each possible rectangle $r$ and placement option $p$ in advance, resulting in a linear formulation as described in the next subsection.

4.2. Mathematical Formulation

In this subsection, a mathematical model for the described problem is presented. Note that this decision model does not incorporate guillotine cutting constraints, which are common in packing and cutting literature and can potentially reduce the solution space by limiting combinatorial options. Guillotine cuts can be applied horizontally or vertically, spanning the entire width or height of the shelf, with each item belonging to only one such section. However, these constraints are not suitable for the JSDSPP-PO, as they would restrict the degrees of freedom in selecting facings and arrangement options. Additionally, the variable dimensions of item rectangles would prevent meaningful cuts (Hübner et al., 2020).

Table 2 provides an overview of the parameters and variables used. The model aims to maximize the total profit as follows:

$$max\sum _{i\in \mathcal{N}}\sum _{p\in \mathcal{P}}\sum _{r\in {\mathcal{R}}_{ip}}\sum _{k\in \mathcal{K}}{\pi }_{irp}{u}_{irpk}$$

(4)

The assignment variable $u_{irpk}$ specifies the selected rectangle $r$ and placement option $p$ for item $i$ and the segment $k$ to which it is assigned. For a given item $i$ , the profit ${\pi }_{irp}$ depends both on the facings of its selected rectangle $r$ and on its visible area that is subject to the selected placement option $p$ .

Table 2.

Notation.

Indices and sets
$\mathcal{N}$	Set of items with $i,j\in \mathcal{N}$ consisting of pairwise disjoint sets ${\mathcal{N}}^{\text{Shelf}}$ , ${\mathcal{N}}^{\text{Hanging}}$ and ${\mathcal{N}}^{\text{Flexible}}$
	with ${\mathcal{N}}^{\text{Shelf}}\cup {\mathcal{N}}^{\text{Hanging}}\cup {\mathcal{N}}^{\text{Flexible}}=\mathcal{N}$
${\mathcal{N}}^{\text{Shelf}}$	Set of items that have to be shelved
${\mathcal{N}}^{\text{Hanging}}$	Set of items that have to be hung
${\mathcal{N}}^{\text{Flexible}}$	Set of items that can be either hung or shelved
$\mathcal{P}$	Set of placement options with $p\in P$ ( $p=0\Rightarrow$ hanging, $p=1\Rightarrow$ shelving)
${\mathcal{R}}_{ip}$	Set of possible rectangles of item $i$ in placement option $p$ with $r\in {\mathcal{R}}_{ip}$ , where a rectangle is defined by its number of horizontal and vertical facings
$\mathcal{K}$	Set of possible segments with $k\in \mathcal{K}$ and $\mathcal{K}={\mathcal{K}}^{\text{Shelf}}\cup \{0\}$
Parameters
${\pi }_{irp}$	Profit of choosing rectangle $r$ of item $i$ in placement option $p$
$w_i$	Width of item $i$
$W_{ir}$	Width of item $i$ for rectangle $r$
$h_{ip}$	Height of item $i$ in placement option $p$
$H_{irp}$	Height of item $i$ for rectangle $r$ in placement option $p$ , considering grabbing gaps
$S^W$ ( $S^H$ )	Total width (height) of the shelf (available shelf space)
$\nu$	Vertical grabbing distance
$H^{SP}$	Height of a shelf
Decision variables
$u_{irpk}$	1 if rectangle $r$ is chosen for item $i$ in placement option $p$ and allocated to segment $k$ , else 0
$l_{ij}(b_{ij})$	$1$ if item $i$ is arranged left (below) of item $j$ , else 0
${\mathrm{coor}}_i^x$ ( ${\mathrm{coor}}_i^y$ )	Location coordinate of item $i$ in the x-dimension (y-dimension)
$a_k$	1 if segment $k$ is used, else 0
${\mathrm{coor}}_k^{SP}$	Location coordinate of the $k$ -th segment in the y-dimension

The solution has to adhere to a set of constraints. Equations (5)–(8) concern the assignment variable $u_{irpk}$ .

$$\begin{array}{rlr}s.t.& \sum _{p\in \mathcal{P}}\sum _{r\in {\mathcal{R}}_{ip}}\sum _{k\in \mathcal{K}}{u}_{irpk}=1& \mathrm{\forall }i\in \mathcal{N}\end{array}$$

(5)

$$\begin{array}{rlr}& \sum _{r\in {\mathcal{R}}_{i0}}{u}_{ir00}=1& \mathrm{\forall }i\in {\mathcal{N}}^{\text{Hanging}}\end{array}$$

(6)

$$\begin{array}{rlr}& \sum _{r\in {\mathcal{R}}_{i1}}\sum _{k\in \mathcal{K}}{u}_{ir1k}=1& \mathrm{\forall }i\in {\mathcal{N}}^{\text{Shelf}}\end{array}$$

(7)

$$\begin{array}{rlr}& u_{ir0k}=0& \mathrm{\forall }i\in \mathcal{N},r\in {\mathcal{R}}_{i0},k\in {\mathcal{K}}^{\text{Shelf}}\end{array}$$

(8)

Constraints (5) demand to select exactly one placement option $p$ , one rectangle $r$ and one segment $k$ per item. If the item has to be hung ( $i\in {\mathcal{N}}^{\text{Hanging}}$ ), Constraints (6) ensure that the corresponding placement option $p=0$ is selected and the item is assigned to segment $0$ , that is the mixed segment. If the item must be shelved ( $i\in {\mathcal{N}}^{\text{Shelf}}$ ), Constraints (7) require choosing placement option $p=1$ , respectively. Lastly, any item that is hung cannot be placed in shelf segment $k\in {\mathcal{K}}^{\text{Shelf}}$ (Constraints (8)).

The following Constraints (9)-(14) relate to item placement.

$$\begin{array}{rlr}& l_{ij}+l_{ji}+b_{ij}+b_{ji}\ge 1& \mathrm{\forall }i,j(i<j)\in \mathcal{N}\end{array}$$

(9)

$$\begin{array}{rl}& {\mathrm{coor}}_i^x+\sum _{p\in \mathcal{P}}\sum _{r\in {\mathcal{R}}_{ip}}{W}_{ir}{u}_{irp0}\\ & \le {\mathrm{coor}}_j^x+S^W(1-l_{ij})& \mathrm{\forall }i,j(i\ne j)\in \mathcal{N}\end{array}$$

(10)

$$\begin{array}{rl}& {\mathrm{coor}}_i^y+\sum _{p\in \mathcal{P}}\sum _{r\in {\mathcal{R}}_{ip}}{H}_{irp}{u}_{irp0}\\ & \le {\mathrm{coor}}_j^y+S^H(1-b_{ij})& \mathrm{\forall }i,j(i\ne j)\in \mathcal{N}\end{array}$$

(11)

$$\begin{array}{rlr}& {\mathrm{coor}}_i^x+\sum _{p\in \mathcal{P}}\sum _{r\in {\mathcal{R}}_{ip}}{W}_{ir}{u}_{irp0}\le S^W& \mathrm{\forall }i\in \mathcal{N}\end{array}$$

(12)

$$\begin{array}{rlr}& {\mathrm{coor}}_i^y+\sum _{p\in \mathcal{P}}\sum _{r\in {\mathcal{R}}_{ip}}{H}_{irp}{u}_{irp0}\le S^H& \mathrm{\forall }i\in \mathcal{N}\end{array}$$

(13)

$$\begin{array}{rlr}& \sum _{i\in \mathcal{N}}\sum _{r\in {\mathcal{R}}_{i1}}{W}_{ir}{u}_{ir1k}\le S^W& \mathrm{\forall }k\in {\mathcal{K}}^{\text{Shelf}}\end{array}$$

(14)

As in Hübner et al. (2020), we use the formulation of Pisinger and Sigurd (2007) to model the overlap constraints. Constraints (9) set each item $i$ in a relative position to every other item $j$ by setting the variables $l_{ij}$ and $b_{ij}$ accordingly. These variables are required in the next two constraints that forbid overlaps between each item pair $(i,j)$ in both x and y dimensions. The variables ${\mathrm{coor}}_i^x$ and ${\mathrm{coor}}_i^y$ reflect the coordinates of the item in the respective dimension. If item $i$ is placed left of item $j$ ( $l_{ij}=1$ ), Constraints (10) demand the right edge of the rectangle of item $i$ (left term) to be smaller or equal to the left edge of the rectangle of item $j$ . Analogously, if item $i$ is positioned below item $j$ ( $b_{ij}=1$ ), Constraints (11) guarantee the top edge of the rectangle of item $i$ to be below the bottom edge of the rectangle of item $j$ . Additionally, Constraints (12)-(13) limit the right and upper edge of the rectangles in the mixed segment to shelf width and height.

Note that Constraints (10)-(13) are only imposed on the mixed segment with $k=0$ to reduce the number of constraints. For pure shelf segments $k\in {\mathcal{K}}^{\text{Shelf}}$ , the total width of the selected rectangles must be less than or equal to the shelf width $S^W$ (Constraints (14)). The coordinates of items assigned to shelf segments are easily obtained in a post-processing based on the widths of their selected rectangles.

The next two sets of restrictions concern the shelf design. First, we need to define when a shelf panel is in use, and under what circumstances it might be in use.

$$\begin{array}{rlr}& a_0=1& \end{array}$$

(15)

$$\begin{array}{rlr}& a_k-a_{k-1}\le 0& \mathrm{\forall }k\in {\mathcal{K}}^{\text{Shelf}}\setminus \{1\}\end{array}$$

(16)

$$\begin{array}{rlr}& \sum _{i\in \mathcal{N}}\sum _{p\in P}\sum _{r\in R_{ip}}{u}_{irpk}\le |\mathcal{N}|\cdot a_k& \mathrm{\forall }k\in \mathcal{K}\end{array}$$

(17)

$$\begin{array}{rlr}& \sum _{i\in \mathcal{N}}\sum _{p\in P}\sum _{r\in R_{ip}}{u}_{irpk}\ge a_k& \mathrm{\forall }k\in \mathcal{K}\end{array}$$

(18)

The variable $a_k$ indicates if shelf panel $k$ has been used in the layout. Constraint (15) ensures that the mixed segment is always used. A large number of equivalent layouts that yield the same total profit exist, making it difficult to find an optimal solution. For example, the same result is obtained regardless of whether shelf panel 1, 2, or 3 is used in the layout. To reduce the symmetry of the solution and make the solution more distinct, Constraints (16) guarantee that shelf panels are used consecutively by allowing shelf panel $k$ to be used ( $a_k=1$ ) only if shelf panel $k-1$ has been used ( $a_{k-1}=1$ ). If at least one item is assigned to a shelf panel, it is considered used and vice versa (Constraints (17) to (18)).

Second, Restrictions (19)-(24) define the positions of shelf panels and of items on the mixed segment.

$$\begin{array}{rl}& {\mathrm{coor}}_0^{SP}-{\mathrm{coor}}_i^y\le S^H(1-\sum _{r\in R_{i1}}{u}_{ir10})\mathrm{\forall }i\in \mathcal{N}\end{array}$$

(19)

$$\begin{array}{rl}& {\mathrm{coor}}_0^{SP}-{\mathrm{coor}}_i^y\ge -S^H(1-\sum _{r\in R_{i1}}{u}_{ir10})\mathrm{\forall }i\in \mathcal{N}\end{array}$$

(20)

$$\begin{array}{rl}& {\mathrm{coor}}_k^{SP}-{\mathrm{coor}}_{k-1}^{SP}\ge \sum _{r\in {\mathcal{R}}_{i1}}{H}_{ir1}{u}_{i,r,1,k-1}+(H^{SP}+\nu )a_{k-1}\\ & -S^H(3-a_k-a_{k-1}-\sum _{r\in {\mathcal{R}}_{i1}}{u}_{i,r,1,k-1})\\ & \mathrm{\forall }i\in \mathcal{N},k\in {\mathcal{K}}^{\text{Shelf}}\setminus \{1\}\end{array}$$

(21)

$$\begin{array}{rl}& {\mathrm{coor}}_0^{SP}-{\mathrm{coor}}_k^{SP}\ge \sum _{r\in {\mathcal{R}}_{i1}}{H}_{ir1}{u}_{i,r,1,k}+(H^{SP}+\nu )a_k\\ & -S^H(2-a_k-\sum _{r\in {\mathcal{R}}_{i1}}{u}_{i,r,1,k})\\ & \mathrm{\forall }i\in \mathcal{N},k\in {\mathcal{K}}^{\text{Shelf}}\end{array}$$

(22)

$$\begin{array}{rl}& {\mathrm{coor}}_i^y\ge {\mathrm{coor}}_0^{SP}-S^H(1-\sum _{r\in {\mathcal{R}}_{i0}}{u}_{ir00})\mathrm{\forall }i\in \mathcal{N}\end{array}$$

(23)

$$\begin{array}{rl}& {\mathrm{coor}}_0^{SP}\ge {\mathrm{coor}}_k^{SP}\mathrm{\forall }k\in {\mathcal{K}}^{\text{Shelf}}\end{array}$$

(24)

Constraints (19)-(20) ensure that assigning an item to the shelf panel in the mixed segment involves matching their vertical levels. The shelf segment defined between two active shelf panels $k$ and $k-1$ has to be at least as high as the largest item placed on shelf panel $k-1$ plus the height of shelf panel $k$ and a grabbing gap (Constraints (21)). The same applies for the mixed segment and all shelf segments (Constraints (22)). Constraints (23)-(24) demand that items can only hang above the level of the mixed segment and that the mixed segment is located above all shelf segments.

At last, Constraints (25)–(31) define the domain of the decision variables.

$$\begin{array}{rlr}& u_{irpk}\in \{0,1\}& \mathrm{\forall }i\in \mathcal{N},p\in \mathcal{P},r\in {\mathcal{R}}_{ip},k\in \mathcal{K}\end{array}$$

(25)

$$\begin{array}{rlr}& l_{ij},b_{ij}\in \{0,1\}& \mathrm{\forall }i,j(i\ne j)\in \mathcal{N}\end{array}$$

(26)

$$\begin{array}{rlr}& 0\le {\mathrm{coor}}_i^x\le S^W-w_i& \mathrm{\forall }i\in \mathcal{N}\end{array}$$

(27)

$$\begin{array}{rlr}& 0\le {\mathrm{coor}}_i^y\le S^H-h_{i0}& \mathrm{\forall }i\in {\mathcal{N}}^{\text{Hanging}}\end{array}$$

(28)

$$\begin{array}{rlr}& 0\le {\mathrm{coor}}_i^y\le S^H-h_{i1}& \mathrm{\forall }i\in {\mathcal{N}}^{\text{Shelf}}\cup {\mathcal{N}}^{\text{Flexible}}\end{array}$$

(29)

$$\begin{array}{rlr}& a_k\in \{0,1\}& \mathrm{\forall }k\in \mathcal{K}\end{array}$$

(30)

$$\begin{array}{rlr}& {\mathrm{coor}}_k^{SP}\ge 0& \mathrm{\forall }k\in \mathcal{K}\end{array}$$

(31)

5. Greedy Multi-Start Matheuristic

To solve problems of realistic size efficiently, a greedy multi-start matheuristic is developed. Algorithm 1 gives an overview.

In line 1, the start layout $L$ , the potentially improved layout $L^{\mathrm{\prime }}$ and the best-known layout $L^{*}$ are initialized. While a predefined termination criterion is not met, a start layout is obtained in line 3 and, if feasible, improved by a greedy search and perturbations in line 5. If applicable, the best-known solution is then updated in line 6. In Subsection 5.1, we explain how a start solution is generated by solving a capacity assignment model with a time limit and a greedy reduction procedure. Subsection 5.2 then elaborates on how a given layout is improved by using a greedy increase and perturbation procedure.

5.1. Obtaining a Start Solution

Algorithm 2 shows how a start layout is generated. The procedure initially solves a capacity model with a given time limit in line 1. Essentially, the capacity model is a relaxed version of the decision model in Subsection 4.2 and, as a result, does not necessarily yield a feasible packing solution. It does not include the computationally expensive positioning variables $l_{ij}$ , $b_{ij}$ , ${\mathrm{coor}}_i^x$ and ${\mathrm{coor}}_i^y$ as well as related constraints. Instead, the following capacity constraints are taken into account:

$$\begin{array}{rl}& \sum _{i\in \mathcal{N}}\sum _{p\in \mathcal{P}}\sum _{r\in {\mathcal{R}}_{ip}}\sum _{k\in \mathcal{K}}{W}_{ir}\cdot H_{irp}\cdot u_{irpk}\\ & +(\sum _{k\in \mathcal{K}}{a}_k-1)\cdot (H^{SP}+\nu )\le S^W\cdot S^H\end{array}$$

(32)

$$\begin{array}{rl}& \sum _{i\in \mathcal{N}}\sum _{p\in \mathcal{P}}\sum _{r\in {\mathcal{R}}_{ip}}{W}_{ir}\cdot H_{irp}\cdot u_{irp0}\le S^W\cdot (S^H-{\mathrm{coor}}_0^{SP})\end{array}$$

(33)

$$\begin{array}{rl}& \sum _{i\in \mathcal{N}}\sum _{r\in {\mathcal{R}}_{ip}}{W}_{ir}\cdot u_{ir1k}\le S^W\mathrm{\forall }k\in \mathcal{K}\end{array}$$

(34)

Constraint (32) requires that the total space utilized by the selected rectangles and used shelf panels is smaller than the available shelf space. Particularly, if a shelf panel is used, the height of the panel and the grabbing distance to the items placed below it have to be considered. Ideally, items are positioned directly on the bottom of the shelf. In this case, a shelf segment is created without requiring a specific shelf panel and we deduct this in the first bracket. Analogously, the total space consumed by items assigned to the mixed segment has to be smaller than the available space in it (Constraint (33)). Constraints (34) ensure that the total width of the selected rectangles is smaller than the shelf width on each segment $k$ .

To increase the space assigned to the mixed segment, the objective function (4) is modified as follows:

$$\begin{array}{rl}& max\sum _{i\in \mathcal{N}}\sum _{p\in \mathcal{P}}\sum _{r\in {\mathcal{R}}_{ip}}\sum _{k\in \mathcal{K}}{\pi }_{irp}{u}_{irpk}\\ & +\epsilon (\sum _{k\in \mathcal{K}}-{\mathrm{coor}}_k^{SP}\cdot (k+1)+\sum _{i\in \mathcal{N}}\sum _{p\in \mathcal{P}}\sum _{r\in {\mathcal{R}}_{ip}}\sum _{k\in {\mathcal{K}}^{Shelf}}{u}_{irpk})\end{array}$$

(35)

This formulation favors assignments with shelf panels positioned on the lower part of the shelf and a higher number of items assigned to shelf segments. Note that $\epsilon$ is chosen sufficiently small so that a lexicographical order of the two terms is achieved. Adding this $\epsilon$ -term in the heuristic gave an advantage, whereas this was generally not the case with the mathematical model of Section 4.

The capacity model (CP) solved in line 1 in Algorithm 2 is thus given as:

$$\begin{array}{c}max(35)\\ \text{s.t.}(5)-(8),(15)-(18),(21),(22),(24),(32)-(34)\\ (25),(30),(31)\end{array}$$

For a complete overview of the capacity planning model, please refer to Section 1 of the E-Companion. The capacity plan assigns a placement option, facings and a segment to each item. It further fixes the levels of the shelf panels. The following steps are repeated until a feasible solution $L$ is obtained. First, each segment is considered separately in the procedure placeItemsOnShelfSegments and the coordinates for the assigned shelved items are extracted based on the selected rectangles and shelf levels. In line (5), the procedure packMixedSegment tries to find a feasible packing for the mixed segment. It sorts shelved and hanging items by height and width and applies a bottom-left heuristic to place rectangles at the lowest, leftmost position. If packing fails, hanging items are randomly perturbed and re-sorted while keeping the allocated facings. This repeats until a feasible layout is found or a stopping criterion is reached (for more details see Section 2 of the E-Companion). If this is not possible, a certain number of facings is reduced in a greedy manner based on the currently assigned number of facings (lines 7–8). For each item candidate $i\in \mathcal{C}$ whose facings can be reduced, a ratio ${\varphi }_i^{\text{decr}}$ between reduction in profit and freed up space is computed. An item is randomly selected from the candidates satisfying the following requirement:

$${\varphi }_i^{\text{decr}}\le \underset{i\in \mathcal{C}}{min}{\varphi }_i^{\text{decr}}+\gamma \cdot (\underset{i\in \mathcal{C}}{max}{\varphi }_i^{\text{decr}}-\underset{i\in \mathcal{C}}{min}{\varphi }_i^{\text{decr}})$$

(36)

The lower $\gamma$ is set, the greedier the selection becomes. The facings of the selected item are reduced by one. Every ${\mathrm{Iter}}^{\text{CPupdate}}$ iteration, the algorithm continues with the removal of rectangles for the previously selected items that have a higher number of facings than currently set, as well as an update of the capacity plan (lines 9–11). Otherwise, the code in lines 12–16 is executed. For each selected item, the algorithm tries to set a new rectangle with the given number of facings, while particularly taking into account the space constraints of the currently assigned segment. As long as this is not possible, the facings of the item are again reduced by one. The process of finding a feasible packing, greedily reducing the number of facings, updating the capacity plan (or redefining rectangles) repeats until a feasible start layout is found or no further reduction of the number of facings is possible. In the latter case, the algorithm terminates.

5.2. Improve and Perturb

Algorithm 3 improves on the start solution with greedy search and perturbation moves. Initially, the algorithm tries to increase the number of facings in a greedy way in the procedure improveNbFacings. To free up space in shelf segments, we first switch to the rectangle with the same number of facings for each item, which still fits into the shelf segment in terms of height and has the smallest width. Analogously to the described procedure greedyReduceAndReturnOfItem in Algorithm 2, we determine a ratio ${\varphi }^{\text{incr}}$ between increase in profit and additionally occupied space for each item candidate $i\in \mathcal{C}$ whose facings can be increased. An item is randomly selected from the set of candidates satisfying the following constraint:

$${\varphi }_i^{\text{incr}}\ge \underset{i\in \mathcal{C}}{max}{\varphi }_i^{\text{incr}}-\gamma \cdot (\underset{i\in \mathcal{C}}{max}{\varphi }_i^{\text{incr}}-\underset{i\in \mathcal{C}}{min}{\varphi }_i^{\text{incr}})$$

(37)

This continues until no further increase in the facings of any item on the shelf segments is possible. In the mixed segment, we again determine ${\varphi }_i^{\text{incr}}$ and randomly select an item whose facings should be increased. As we do not fixate on a specific rectangle, we possibly ignore additionally required area in terms of grabbing gaps. Algorithm 1 is used to retrieve a solution, if possible. The procedure terminates if we cannot increase facings for $Ite{r}^{\text{NoImprovGreedyIncr}}$ times.

Line 2 updates the improved layout $L^{\mathrm{\prime }}$ . The algorithm then perturbs the layout in line 5 using a destroy and shuffle operation followed by a perturbation move. First, with probability destroyProb, the facings of toBeDestroyed percent of randomly selected items are reduced to one and segment assignments are shuffled with probability destroyShuffleProb over ${\mathrm{Iter}}^{\text{FindPackingShuffle}}$ iterations. Second, one of three perturbation moves is applied: (a) Increase/Decrease Facings in Same Segment, which aims to increase the facings of one randomly selected item by reducing the facings of other ones allocated to the same segment; (b) Switch Segment Assignment of Two Shelved Items, which swaps the segment allocation of two items if compatibility conditions are met; and (c) Switch Placement Option, which changes a flexible item’s placement between shelving and hanging. To ensure feasibility of the perturbed solution, a greedy reduction procedure may be applied. The reader is referred to Section 3 of the E-Companion for more details. The algorithm then improves its facings (line 6) and updates the best found layout in lines 7–11, if applicable. It returns layout $L^{\mathrm{\prime }}$ once ${\mathrm{Iter}}^{\text{NoImprov}}$ consecutive moves without improvement were observed.

6. Numerical Results Based on Simulated Data

In this section, we first show the necessity and performance advantage of the matheuristic over solving the decision model directly with Gurobi (Subsection 6.1). We then compare the matheuristic with a benchmark from the literature on JSDSPP-PO instances that satisfy certain conditions (Subsection 6.2). Finally, a sensitivity analysis examines the impact of problem characteristics on solution quality (Subsection 6.3).

For parameter tuning, a test set with two instances each with 10, 50, and 70 items was created. The algorithmic parameters were tuned iteratively based on the trade-off between obtained profit and runtime averaged over 5 runs and for maximum 5 restarts without improvement. Moreover, the contributions of the destroy operator and all three perturbation neighborhoods were verified. The interested reader is referred to Section 4 of the E-Companion for details of the algorithmic parameter values used.

All experiments were conducted on a Microsoft Windows 10 Enterprise Version 22H2 64-bit with an AMD Ryzen 9 3 $,$ 900X 12-Core Processor and 32-GB memory. The tests are implemented in Python 3.10.14 (Spyder IDE 5.5.1) and Gurobi Optimizer 10.0.2. For the BL heuristic, the pack algorithm MaxRectsBl provided by the open-source library rectpack was utilized (see https://github.com/secnot/rectpack). For a description of MaxRectsBl, please refer to Jylänki (2010).

6.1. Performance Comparison of Gurobi and the Matheuristic

In this section, the matheuristic is benchmarked against Gurobi on instances for the JSDSPP-PO of varying sizes. Due to the combinatorial nature of the problem, proven optimal solutions could only be obtained for very small instances within a reasonable computing time. To demonstrate the high efficiency of the heuristic, the heuristic is compared to the (near-)optimal solutions of instances with $n=10$ items to be placed on a shelf with 75 cm width and 160 cm height. More realistic instances are simulated by assuming $n=50$ , $n=70$ , and $n=100$ items to be placed on a shelf with 100 cm width and 160 cm height. An overview of the parameters used in the base test setting analyzed below is provided in Section 5 of the E-Companion. In each of the four instance groups in the base test setting, 10 instances were generated and the average results of 5 runs of the heuristic are reported.

Table 3 demonstrates the computational efficiency of the algorithm based on the evaluation of a number of simulated problem instances in the base test setting. For Gurobi, the table reports the average profit over all 10 instances with the same number of items, total runtime (RT), time to reach the best solution (RT Best), MIP gap, and relative space utilization (i.e., the ratio of displayed item area to shelf space). For the heuristic, it presents the average across all instances and runs, total runtime, the gap of the heuristic (computed using Gurobi’s best upper bound as a reference), its variation over runs, and relative space utilization. To compare the approaches, the relative runtime difference of the heuristic (compared to both the total runtime and time to best solution of Gurobi) is shown, along with differences in gaps and utilized space.

Table 3.

Results for instances in the base test setting (time limit of 1,200s for Gurobi, average over 5 runs for matheuristic).

	Gurobi					Heuristic					Solution quality & performance
	Profit	RT	RT Best	Gap	Space Util.	Profit	RT	Gap	$\mathrm{\Delta }$ Gap	Space Util.	$\mathrm{\Delta }$ RT	$\mathrm{\Delta }$ RT Best	$\mathrm{\Delta }$ Gap	$\mathrm{\Delta }$ Space Util.
n		[s]	[s]	[%]	[%]		[s]	[%]	[pp.] (runs)	[%]	[%]	[%]	[pp.]	[pp.]
10	103.5	186.4	31.3	0.2	82.8	102.8	6.2	0.9	0.1	77.9	96.7	80.1	0.6	−4.9
50	510.6	1200.5	967.5	5.1	71.7	523.1	114.5	2.6	0.2	74.7	90.5	88.2	−2.5	2.9
70	630.3	1201.2	831.5	12.4	71.0	657.0	157.3	7.9	0.2	73.6	86.9	81.1	−4.6	2.6
100	946.5	1201.5	1099.7	13.1	67.5	1003.9	297.9	6.6	0.2	70.3	75.2	72.9	−6.5	2.8

First, it shows that the heuristic obtains solutions close to the (near-)optimal ones based on 10 test instances with 10 items. On average, the heuristic generated a solution within 6 seconds, saving $96.7$ % of the total runtime and $80.1$ % of Gurobi’s time to reach the best solution. However, Gurobi’s runtimes across instances for this problem size vary widely between less than $1$ and $\mathrm{1,200}$ seconds. Therefore, these average savings should be treated with caution. This also means that the number of items alone does not determine the difficulty of an instance. The computational experiments also showed that when the optimal layout can place the maximum number of facings for each item, the selection pressure is low and both approaches find the optimal solution quickly. Second, the matheuristic outperforms Gurobi in larger, more realistic problem instances with 50, 70 and 100 items, respectively. In contrast to the actual runtime of Gurobi, which is around the time limit of $\mathrm{1,200}$ seconds, it saves between $90.5$ %, $86.9$ % and $75.2$ % of runtime on average. Relative to Gurobi’s time to reach the best solution, it still saves a substantial $88.2$ %, $81.1$ %. and $72.9$ %, respectively. Compared to the upper bound of Gurobi, the heuristic also generates layouts with a gap that is on average $2.5$ , $4.6$ and $6.5$ percentage points lower, respectively. The column $\mathrm{\Delta }$ Space Util. [pp.] shows that higher-quality solutions typically coincide with a higher shelf space utilization. For larger problem sizes (70 and 100 items), however, the additional space used is usually smaller than the additional profit achieved.

Table 4 compares the structural differences between the heuristic and Gurobi solutions. We report variations in selected facings and placement options. Between $22.6$ % and $34.8$ % of the items change their facings between the two approaches, with the share of items showing an increase in facings compared to Gurobi that fluctuates between $40.3$ % and $52.1$ % for $n>10$ . On average, the matheuristic assigned 0.14 facings less to 0.03 facings more to an item compared to Gurobi. These results suggest that the overall improvement in solution quality (cf. Table 3) is not due to a general increase in placed facings, but rather to a balanced redistribution of shelf space. Placement differences become more apparent as the number of items increases, with up to $17.9$ % of items receiving a different placement option for $n=100$ . The matheuristic decides to hang a significant majority of these items (up to $98.5$ % on average for $n>10$ ), rather than shelving them. Since the heuristic generally achieves higher profits, this shift toward hanging placements likely contributes to a higher solution quality.

Table 4.

Analysis of changes in solution structures from Gurobi to the matheuristic.

	Share of items with	Among these: % with	$\mathrm{\Delta }$ facings	Share of items with	Among these: % with
n	$\mathrm{\Delta }$ facings [%]	higher facings	per item	$\mathrm{\Delta }$ placement option [%]	hanging placement
10	22.6	15.9	−0.14	0.0	0.0
50	34.8	52.1	0.03	7.6	90.0
70	32.9	44.2	−0.04	16.3	98.5
100	31.7	40.3	−0.11	17.9	98.4

6.2. Performance Comparison to a 2D Shelf Space Planning Approach in the Literature

This section aims to show the competitiveness of our matheuristic by comparing it to an approach from the literature. We focus on two-dimensional shelf space planning problems, as they play an important role in the JSDSPP-PO. As discussed in Section 3, the JSDSPP-PO can be seen as an extension of special cases presented in Hübner et al. (2020) and Geismar et al. (2015), both of which study two-dimensional shelf space problems. Since Hübner et al. (2020) assume stochastic demand and also decide on the assortment, we believe that a more appropriate comparison can be made with Geismar et al. (2015).

To enable a fair comparison with the shelf space planning problem studied in Geismar et al. (2015), we generated a set of test instances that can be solved by both our approach and their decomposition-based method. A detailed description of their problem setting, algorithm, and instance generation is provided in Section 6 of the E-Companion.

Table 5 shows the relative profit improvements of the matheuristic (based on five runs per instance) compared to the decomposition approach of Geismar et al. (2015). Although the matheuristic underperforms in certain cases, it outperforms the decomposition approach on average. Note that in around $17\mathrm{\%}$ of the runs, the fallback solution was used, as not all items were placed when solving the maximum weighted independent set problem. In some rare cases for instances with 5 items, the matheuristic was not able to obtain a feasible solution. However, this instance size is atypical in JSDSPP-PO, and only $0.8\mathrm{\%}$ of the runs for 5 item instances were affected. Table 6 shows acceptable runtimes for each heuristic with the matheuristic outperforming the decomposition approach on average for instances with 10 and 15 items.

Table 5.

Relative profit improvements of the matheuristic compared to the decomposition approach of Geismar et al. (2015).

		ln nrm	ln nrm	neg bin	neg bin	normal	normal	normal	unifm	unifm
n		(3,2)	(8,10)	(20,0.8)	(10,0.4)	(12,4)	(12,8)	(3,8)	[2,20]	[2,36]	Average
5	Profit improvement [%]	0.68	0.54	0.82	0.28	0.11	0.38	0.40	1.03	0.90	0.57
	$\mathrm{\Delta }$ profit improvement [pp.] (runs)	0.16	0.25	0.23	0.43	0.51	0.24	0.09	0.28	0.39	0.29
10	Profit improvement [%]	0.12	−0.16	0.35	1.48	1.91	0.86	0.12	0.89	1.08	0.74
	$\mathrm{\Delta }$ profit improvement [pp.] (runs)	0.32	0.36	0.33	0.34	0.25	0.33	0.31	0.27	0.19	0.30
15	Profit improvement [%]	0.00	0.00	0.07	0.04	0.05	0.06	0.01	0.07	0.04	0.04
	$\mathrm{\Delta }$ profit improvement [pp.] (runs)	0.03	0.02	0.02	0.00	0.00	0.00	0.00	0.00	0.00	0.01

Table 6.

Runtimes in seconds of the matheuristic and the decomposition approach of Geismar et al. (2015).

		ln nrm	ln nrm	neg bin	neg bin	normal	normal	normal	unifm	unifm
	n	(3,2)	(8,10)	(20,0.8)	(10,0.4)	(12,4)	(12,8)	(3,8)	[2,20]	[2,36]	Average
Matheuristic	5	7	5	6	5	5	6	6	6	6	6
Decomp. appr.		4	4	4	4	3	4	4	3	4	4
Matheuristic	10	8	7	6	6	7	6	7	6	6	7
Decomp. appr.		25	28	31	31	35	29	28	29	29	29
Matheuristic	15	4	4	4	4	4	4	4	4	4	4
Decomp. appr.		68	58	70	70	74	70	71	70	73	69

Finally, we evaluate both approaches for solving realistic instances of the JSDSPP-PO with 50 and 70 items. We generated 10 instances for each of the three distributions for which the decomposition approach previously performed best: lognormal ( $\mu =3,\sigma =2$ ), lognormal ( $\mu =8,\sigma =10$ ), and normal ( $\mu =3,\sigma =8$ ). In each case, a maximum of 6 facings per item is allowed on a cabinet with 12 rows and 8 columns, and a 6-hour time limit was imposed for solving the maximum weight independent set problem in the decomposition approach. Table 7 summarizes the results. The matheuristic clearly outperforms the decomposition approach in profit and runtime over all distributions and problem sizes. It achieves a relative profit improvement of up to $47.6$ %, which is consistent over five runs as indicated by the zero variance in $\mathrm{\Delta }$ profit improvement [pp.] (runs), while requiring at most $0.25$ % of the runtime. Most of the runtime of the decomposition method was spent solving the maximum weighted independent set problem, but its solution was always infeasible (not all items were placed), requiring the fallback heuristic. In terms of solution structure, only a small fraction of items experienced a change in facings ( $11.2$ %- $11.8$ % for $n=50$ and about $4$ % for $n=70$ ), with less than half of these changes being an increase. Finally, the total number of allocated slots is identical in both approaches, since every slot is used.

Table 7.

Metrics for performance and change of solution structures for larger instances.

	$n=50$			$n=70$
Metric	ln nrm (3,2)	ln nrm (8,10)	normal (3,8)	ln nrm (3,2)	ln nrm (8,10)	normal (3,8)
Relative profit improvement [%]	33.1	47.6	5.0	12.8	2.5	1.7
$\mathrm{\Delta }$ relative profit improvement [pp.] (runs)	0.0	0.0	0.0	0.0	0.0	0.0
Runtime decomp. appr. [s]	6447.0	21963.5	7836.1	7634.5	22210.6	6864.1
Runtime mathheuristic [s]	16.4	23.7	18.3	13.1	14.5	13.0
Share of items with $\mathrm{\Delta }$ facings	11.2	11.6	11.8	3.7	3.9	4.1
Among these: % with higher facings	48.3	43.1	38.6	40.0	39.1	35.0
$\mathrm{\Delta }$ # assigned slots	0.0	0.0	0.0	0.0	0.0	0.0

Overall, the matheuristic distributes facings more effectively and outperforms the decomposition approach for both smaller and larger instances, demonstrating its high computational efficiency.

6.3. Sensitivity Analysis

To analyze the problem in detail, we focus on the introduced 10 instances for the JSDSPP-PO with 50 items. This is a typical problem size when considering a single shelf in practical applications. Starting from the base test setting, selected problem characteristics are varied and the results obtained by the matheuristic are compared. Subsection 6.3.1 analyzes the value of flexible item placement. Subsection 6.3.2 examines the profit impact of integrating the shelf design and the shelf space problem, while Subsection 6.3.3 evaluates the cost of arranging hanging items in visually appealing rows, a common practice in retail.

6.3.1. The Value of Flexible Item Placement

This section evaluates the value of flexible placement by investigating how different proportions of flexible, shelved and hanging items affect overall performance. In particular, we explore whether allowing more items to be either hung or shelved improves profitability, efficiency and space utilization. We study six settings: (1) Flexible, (2) Shelving, (3) Hanging, (4) Shelving & Flexible, (5) Hanging & Flexible, and (6) Shelving, Hanging, & Flexible (see Table 8). Each configuration was tested on 10 instances of the base test setup, assuming no changes in display orientation for ease of comparison. The instances remained identical in all settings, differing only in the placement options available.

Table 8.

Improved profit, decreased runtime and increased space utilization in case of flexible item placement.

	Probability						Selected placement [%]
				Relative profit	Runtime	Space utilization
Setting	Only-shelved	Only-hanging	Flexible	improvement [%]	decrease [s]	increase [%]	Shelving	Hanging
Flexible	0%	0%	100%	–	–	–	41.0	59.0
Shelving	100%	0%	0%	2.4	221.6	14.7	100.0	0.0
Hanging	0%	100%	0%	1.0	46.2	11.0	0.0	100.0
Shelving & Flexible	67%	0%	33%	0.7	8.4	5.9	77.8	22.2
Hanging & Flexible	0%	67%	33%	0.5	78.8	5.7	19.4	80.6
Shelving, Hanging
& Flexible	33%	33%	33%	0.6	20.4	5.7	47.0	53.0

In the Flexible setting, profit improves by $0.5$ % to $2.4$ % and space utilization increases by $5.7$ % to $14.7$ %, while runtime is reduced by $8$ to $222$ seconds. The Shelving setting resulted in the lowest profits and the highest, most volatile runtime. It often required the maximum number of shelf segments and had the lowest space utilization. The shelf panel may not be fully utilized, resulting in wasted space, either horizontally or vertically. Vertical inefficiencies occur especially when the heights of the items assigned to the same shelf panel are not approximately multiples of each other. However, stacking items on a shelf panel with a grabbing gap of zero improves space utilization to some extent. When some items must be hung while others are flexible, shelving a flexible item may require an additional shelf panel which prevents hanging items below it. This reduces the available space for hanging items, as they need to be hung above all shelf panels.

The Hanging setting performed better, yielding higher profits and lower, more stable runtimes. Hanging the items allows for a better space utilization, but can also be disadvantageous. Additional grabbing gaps must be considered if the facings of a hanging item are placed one above the other. However, the combinatorial nature of the problem can make side-by-side placement of all facings infeasible.

Overall, the highest profit and shelf space utilization can be seen in the setting Flexible. The shelf space occupied by shelved items is over 50%, while the number of shelved items is only around 41% on average. A similar trend is observed in the Shelving, Hanging, and Flexible setting, where flexible items were less frequently shelved. This may reflect the fact that, in an ideal layout, fewer items are shelved, but when they are, they tend to be stacked as high as possible. Section 7 of the E-companion provides example layouts for all six settings.

6.3.2. The Value of Integrating the Shelf Design and the Shelf Space Problem

This section analyzes the advantage of a joint solution to the shelf design and shelf space problem compared to an isolated solution of the shelf space problem that proceeds from a predefined shelf design. We examine five shelf designs (see Table 9). We compare the results with the solution of a previously unspecified design in an integrated shelf design and shelf space problem assuming the ten instances of the basic setting with 50 items, which consist of one third each of only-shelved, only-hanging, and flexible items. Instances where the predefined shelf designs proved infeasible have been excluded from this analysis.

Table 9.

Improved profit, increased runtime and space utilization of an integrated solution to the shelf design and space problem.

		Share
					Relative profit	Runtime	Space utilization
Design	# segments	Mixed segment	Shelf segment 1	Shelf segment 2	improvement [%]	increase [s]	increase [%]
2 sgm. (50/50)	2	50%	50%	–	5.3	0.5	44.5
2 sgm. (67/33)	2	67%	33%	–	1.4	24.8	12.2
2 sgm. (75/25)	2	75%	25%	–	0.7	17.6	6.1
3 sgm. (33/33/33)	3	33%	33%	33%	9.7	31.7	67.8
3 sgm. (50/25/25)	3	50%	25%	25%	3.4	37.7	25.8

Results reveal that an integrated solution to both decision problems may lead to a significant improvement in profit. Compared to each of the five predefined shelf designs, the profit increases by $0.7$ % to $9.7$ % and space utilization by $6.1$ % to $67.8$ %, while requiring only up to 38 seconds more runtime on average. In the case of shelf design “3 sgm. (33/33/33),” profit increases most by $9.7$ % and shelf space utilization increases by $67.8$ %, while in shelf design “3 sgm. (50/25/25)” the increases are only $3.4$ % and $25.8$ %, respectively. In the latter case, more space was allocated to the mixed segment in advance, which in this case turned out to be favorable. Profit and space utilization increase as more space is assigned to the mixed segment. It is worth noting that shelf design “3 sgm. (50/25/25)” outperforms shelf design “2 sgm. (50/50)” in terms of profit, although in both settings the mixed segment was allocated $50$ % of the available shelf space. This also shows that the number of shelf segments cannot be determined independently of the space planning.

To sum up, the number and level of the shelf segments considerably influence the achievable results. Shelf design “2 sgm. (75/25)” achieves results that are closest to an integrated solution. However, this design cannot be known in advance as this depends largely on the mixture of products to be assigned and their respective characteristics. Shelf design and space planning should therefore be solved simultaneously as far as possible. Examples of layouts for predefined and optimized shelf designs are given in Section 8 of the E-Companion.

6.3.3. The Cost of Visually Appealing Layouts

In practice, items are often hung in rows for visual appeal. However, this practice restricts the flexibility of space assignments, leading to unused gaps and negatively affecting profit. In this section, we quantify the effect of enforcing structured, row-based layouts for hanging items and measure the resulting profit loss. We assume equally sized segments on a shelf with a height of 160 cm. We test five configurations (1, 2, 4, 5, and 8 segments), making sure that the segment heights are integer values that add up to the total height of the shelf. As the number of segments increases, the row-based hanging concept is applied more heavily. Items are randomly assigned to each segment, and the matheuristic is used to determine a layout for each segment individually. The total profit across all segments is then determined. One run of the heuristic reports the best profit across 10 random item assignments, and we analyze the average profit over 5 runs.

Table 10 shows that imposing row-based hanging layouts leads to no or only an insignificant reduction in profit and space utilization when the number of segments is small, but this loss increases as the number of segments grows. For items of uniform size, profit loss compared to the single segment case remains negligible up to four segments but rises to $6.6$ % at eight segments, accompanied by a significant drop in space utilization from $75$ % to $50$ %. Note that in this setting, hanging items in rows should be both simple and space-efficient. However, segmenting the shelf without considering item dimensions, grabbing gaps, and shelf height results in inefficient layouts. Given a uniform item height and width of 10 cm, a vertical grabbing gap of 3 cm, and a shelf height of 160 cm, it is possible to fit 12 rows with 1, 2, and 4 segments, but only 10 rows with 5 segments and just 8 rows with 8 segments. This reduction in the number of rows directly contributes to the observed profit loss.

Table 10.

Results for imposing row-based hanging to increase visual appeal (average over 5 runs and 10 random item assignments).

	#Segments
Item sizes	1	2	4	5	8
Uniform sizes
Profit reduction [%]	–	0.0	0.1	3.1	6.6
Runtime [s]	50.4	350.9	191.5	382.1	180.5
Utilized space [%]	75.0	75.0	75.0	62.5	50.0
Moderate variability
Profit reduction [%]	–	0.0	0.6	1.4	3.8
Runtime [s]	129.7	1008.2	575.2	438.8	190.7
Utilized space [%]	72.7	72.7	70.6	68.1	58.0
High variability
Profit reduction [%]	–	0.0	0.5	1.1	–
Runtime [s]	234.4	1134.9	513.6	397.2	–
Utilized space [%]	71.5	71.7	69.8	67.5	–

For items with moderate or high size variability, the performance drop is less steep but still notable — reaching up to $3.8$ % and $1.1$ %, respectively. Note that for highly variable item sizes, no feasible solution could be found with eight segments. Runtime increases from one to two segments significantly and then decreases as the number of segments grows, with an outlier at five segments in the case of uniform item sizes. This pattern arises because, for a single segment, no item assignment step is needed and the layout is optimized in a single run. With more segments, the individual subproblems become smaller as fewer items need to be arranged on smaller shelf areas. As a result, computational effort is reduced despite the need for repeated item assignments.

Overall, the results show a clear trade-off between visual appeal and layout efficiency: the stricter the row-based structure, the greater the loss in expected profit. However, these profit losses could potentially be reduced with a more strategic segmentation, careful selection of segment sizes and the number of segments, as well as a more intelligent item assignment strategy. Examples of shelf layouts with different numbers of segments are shown in Section 9 of the E-Companion.

7. Case Study

This section presents a case study in cooperation with a major European grocery retailer. The company provided data on $|\mathcal{N}|=237$ items that are regularly listed in the stores which have in total six shelves with a shelf space of 100 cm width and 140 cm height dedicated to the non-food segment. Company software is used to create a planogram for each shelf combination, ignoring store-specifics due to the high computational and organizational effort. In contrast, the software also decides on the product range, for example, and takes product groups into account. To ensure a fair comparison, each of the six product categories is analyzed separately. Each product group was assigned the same shelf space as in the business software solution. Table 11 provides an overview of the category names and abbreviations as well as the number of items, the item mix and the allocated shelf width per category. Note that in category bbq all items must be hung while none of the items in the category p&p need to be hung.

Table 11.

Number of items, item mix, and allocated shelf space per category in the case study.

	Baking	Barbecue	Breakfast	Kitchen gadgets	Party&decoration	Pots&pans
Category	(bak)	(bbq)	(bf)	(kit)	(p&d)	(p&p)	Avg.
# items	41	10	24	106	36	20	39.5
# only-shelved	10	0	14	10	5	8	7.8
# only-hanging	24	10	8	81	31	0	25.7
# flexible	7	0	2	15	0	12	6.0
Shelf width	127	26	60	229	68	90	100.0

Access was granted to item master data (sizes, available placement options, maximum number of facings) and to the shelf layout generated by the company (selected placement options, facings and shelf design). The item-specific parameters are subject to a non-disclosure agreement. Stacking an item is not permitted if stability cannot be guaranteed or the individual pieces interlock considerably, so that an increased likelihood of impulse purchases cannot be assumed. This is the case, for example, with measuring cups or salad bowls. The gross profit was calculated as the product of the sales price and a randomly drawn margin. The price class of the item determines the level of the lower and upper limits of the assumed uniform distribution as well as the interval range. We further simulate the sales for five different instances (=stores). Between each item, a vertical grabbing gap of 1cm has to be respected and a maximum of six shelf segments can be formed.

Subsection 7.1 compares the heuristic solution with the company layout for each category. For marketing reasons, a maximum of three facings is assumed for each item. Then, Subsection 7.2 evaluates and discusses potential benefits of generating store-specific layouts in contrast to a “one layout fits all” solution based on average sales data.

Table 12.

Case study results: average profit increase compared to company layout over 5 runs.

Category	bak	bbq	bf	kit	p&d	p&p	Average
Store 1	+3.4	+7.4	+0.8	+5.8	+4.4	+4.4	+4.4
Store 2	+3.1	+6.2	+1.0	+5.2	+2.3	+4.8	+3.8
Store 3	+2.9	+5.1	+1.6	+6.6	+2.8	+3.3	+3.7
Store 4	+4.6	+5.2	+0.5	+6.0	+3.6	+4.8	+4.1
Store 5	+3.6	+6.6	+0.4	+4.9	+4.0	+4.4	+4.0
Average	+3.5	+6.1	+0.9	+5.7	+3.4	+4.3	+4.0

7.1. Performance Comparison to the Company Layout

Each store-category problem instance is solved with the matheuristic over five runs and the results are compared to the company layout. Table 12 shows that the heuristic produces layouts with an average $4.0$ % higher profit. The average runtime varies from 7 seconds for category bbq to 810 seconds for category kit. In each store and category, the expected profit can be improved by increasing the item visibility and thus impulse purchases. One reason for the increase in profit are the additional facings for some items, see left chart in Figure 5. In total over all items in one category, the number of facings in the individual categories and stores increased between one and twelve. As a result, the total utilized space rises by $5\mathrm{\%}$ to $85\mathrm{\%}$ .

Figure 5.

Change in the total facings & number of items with different facings and placement option cf. company layout.

Comparing the increase in the number of facings (left chart of Figure 5) with the number of items affected by a facing change (middle chart of Figure 5), it can be seen that the latter value often exceeds the former. The facings of some items are therefore increased and those of some other items reduced.

In addition, placement options could also be changed for flexible items (see right-hand figure). In the two categories with the highest number of flexible items, kit and p&p, around one third of the flexible items are assigned a different placement option. Only about one of seven flexible items change their placement option in the bak category. Otherwise, either there are no flexible items (categories bbq and p&d) or the placement option assignments are not different (category bf).

To summarize, with the help of our solution approach, the shelf space layout of six categories can be noticeably improved at our case company, and thus the expected profit for all categories and stores can be considerably increased. The expected increase in profit stems from an increased total number of facings as well as an improved facing and/or placement option allocation. Additionally, a larger number of facings also allows for more on-shelf inventory. This reduces the refilling frequency and therefore replenishment costs and out-of-shelf risk while rising inventory holding costs (Hübner and Schaal, 2017). This is significant as in-store operational costs account for $45\mathrm{\%}$ of total operational costs in retail (Kuhn and Sternbeck, 2013; van Zelst et al., 2009). Finally, the free space can also be used to expand the product range. Once a feasible layout was determined for a core assortment, our solution approach developed could be solved iteratively with more and more optional items, possibly while fixing the number of facings of the core assortment by setting the rectangle set accordingly.

7.2. Store-Individual Shelf Layouts Versus One Layout Fits All

Our case company simply creates a unique shelf layout for all stores of a certain size class, which is then used in all stores of this class. This approach reduces the organizational effort but ignores regionally specific features. The case company therefore assumes that the product range and margins are the same across the stores and that sales can be well represented by average sales. However, regional preferences may increase sales of some items and decrease sales of others. Examples include spaetzle presses in southwestern Germany and cast iron pans for poffertjes in northern Germany. As a result, the relations between the basic demand for items and placement options can vary from store to store, and so can the optimal facing and placement options allocation. The benefit of using store-specific layouts is particularly high when the sales volume of items differ greatly between stores.

In our case study, sales of an item differ substantially from store to store. To find out the concrete benefit of store-specific layouts, we compare them to a one layout fits all solution that uses average sales data from the five stores. Interestingly, store-specific solutions improve overall profit by only $0.6$ % on average. One reason for this is that 80% to 92% of all items are placed with just one facing. On average, merely $1.2$ facings are used for each item. This indicates a severely limited space and only little leeway for increasing facings of the given assortment. It can be assumed that a significantly higher available shelf space will have a noticeable influence on the advantage of store-specific layouts in our case study. Since shelf space is a scarce resource, this result also underlines the importance of including assortment planning in the generation of non-food shelf layouts in the future.

8. Conclusion and Outlook

8.1. Summary

This article introduces the novel joint shelf design and shelf space planning problem with placement options, which occur on flexible shelves that allow items to be either hung or shelved. In contrast, the literature on shelf space planning focuses solely on regular shelves with only one placement option, namely the placement of items on a shelf panel. In our case, however, the following interrelated decisions must be made simultaneously: (a) Which item should be placed on a shelf panel (shelved items) and which should be hung (hanging items)? (b) How many shelf panels are required for shelved items? (c) On which vertical level should the individual shelf panels be positioned? (d) How many facings should be assigned to each item? (e) How should the number of intended facings of an item be arranged horizontally and vertically? (f) On which vertical and horizontal position should hanging items be placed? (g) And finally, on which shelf panel and on which horizontal position should shelved items be located?

We formulate the decision problem at hand as a mixed-integer linear program and develop a greedy multi-start matheuristic for solving problem instances of realistic size. The high performance of the algorithm is first demonstrated by comparing the matheuristic with Gurobi on generated test instances, showing that the matheuristic is preferable for realistic problem sizes. Then, it is benchmarked against a method from the literature that solves the two-dimensional shelf space problem, which represents a special case of our problem. Our approach also achieves competitive results in this setting, especially for realistic instance sizes. Furthermore, the problem is analyzed by systematically varying key characteristics. Finally, we show the practical applicability of the developed algorithm by analyzing a case study with 237 items across six categories of a major European grocery retailer. The numerical analyses performed and the case study conducted provide a wide range of managerial insights:

Hanging an item achieves higher space utilization than placing it on a shelf panel, which may require an additional shelf panel or can create an unused space between two shelf panels. In addition, the orientation of an item placed on a shelf panel may need to change to one that restricts the visibility of the item for stability reasons. This in turn reduces customer satisfaction and the item’s revenue. On the other hand, hanging the items can also be less favorable than placing them on a shelf panel if the respective facings of the hanging item must be arranged one above the other. In this case, additional grabbing gaps become necessary, which take up additional space on the shelf. However, this issue does not arise when items are stacked on shelf panels, which is again an advantage of shelving items.

Determining the appropriate number of segments for hanging and shelved items as well as the positioning of the shelf panels has a noticeable influence on the results. Shelf design and space planning should therefore be planned together whenever possible.

Row-based layouts improve visual appeal but can come at the expense of space efficiency and profit, especially when item sizes and grabbing gaps do not fit well with the predefined segment heights. Managers should balance esthetics and performance when planning shelf layouts. Profit loss can be reduced by intelligently selecting segment sizes, number of segments, and item assignments.

For our case company, the developed modeling and solution approach can significantly improve space utilization and thus increase the visibility of the items and the retailer’s sales.

Store-specific layouts can improve the retailer’s profitability, but this depends largely on the degree to which the number of facings of each item can be modified and the ability to customize the shelf design.

8.2. Limitations and Future Areas of Research

Although we have proposed a novel modeling and solution approach to a previously unaddressed shelf design and shelf space planning problem, our study offers several opportunities for improvements and extensions that lead to new perspectives for further research. Possible extensions could be made in the following directions: (1) demand effects and marketing measures, (2) demand volatility, (3) assortment impacts, (4) replenishment effects, and (5) store-wide planning concepts.

1. (1)

Our approach focuses on the effects of space-elastic demand. It ignores, though, the effects of cross-space elasticity, which seems to be less relevant in retail practice. However, future studies should consider incorporating positioning effects to account for the varying demand for an item depending on its vertical position, as demand tends to be highest at “eye level.” Furthermore, price effects with price and cross-price elasticity, as well as additional marketing activities that influence customer demand could be investigated.

(2)

Our model assumes deterministic and stationary demand, whereas in practice demand usually depends on numerous external factors such as the time of year, public holidays or the day of the week. The inclusion of seasonal and stochastic effects as well as out-of-stock substitution would make the modeling approach considerably more relevant in practice. For perishable goods, a stochastic model should balance between understocking and overstocking. This would reflect the trade-off between service level and food waste.

(3)

The assortment decision could also be integrated into the modeling and solution approach presented. This should then also reflect the situation that unlisted items can be at least partially substituted by listed items, that is, effects on out-of-assortment substitution.

(4)

Our model determines the number of assigned facings and selects a placement option, which in turn quantifies the available stock throughout the shelf for each item. However, the available stock specifies how often the stock on the shelf must be replenished from the warehouse or from the store’s backroom area to meet customer demand. The decision on the number of facings must therefore be aligned with the store’s delivery patterns and the in-store replenishment cycles. Extending the model to the entire supply chain will certainly provide additional managerial insights.

(5)

The planning problem being considered could also be extended in the direction of store-wide space planning approaches. These approaches select the categories offered by the retailer, determine the store-specific role of each category, allocate the total shelf space of the store to each category, and group the categories to allocate them to specific store and shelf space areas.

More broadly, future research may also examine how the proposed solution approach can be transferred to related problem settings. While we have demonstrated that our method also works in simplified settings with only one placement option (either hanging or shelving), real-world scenarios sometimes involve more than two. For example, in promotional displays for baking utensils, some items are hung (e.g., cookie cutters or icing tips), others are stacked on shelf panels (e.g., baking mixes), and irregular, non-stackable items are loosely placed in bins (e.g., silicone molds or muffin cups). Each placement option imposes different spatial constraints and affects visibility and accessibility in distinct ways. In the current model, two placement options are handled by horizontally partitioning the shelf into two areas. With three or more placement options, more flexible segmentation and additional placement rules may be required. A promising direction for future research is therefore to investigate how the model and matheuristic can be generalized to multi-option settings.

This underlying structure—assigning items to placement options and allocating limited space accordingly—is not unique to brick-and-mortar retail. Similar allocation problems arise in other domains where content or products must be assigned to distinct formats with different spatial characteristics. In online advertising, for instance, placement options may correspond to different content formats, such as static product tiles, sponsored listings labeled as ads, or dynamic pop-up banners. These formats vary in visibility, user engagement, and spatial requirements. Similarly, in warehouse management, placement options may represent different storage formats, such as pallet stacking, shelving, or hanging storage for certain items. In each case, space must be allocated strategically across competing formats, and items using the same placement option may need to be grouped together to enhance efficiency or consistency. Transferring the principles of joint design and space allocation to these contexts could open new avenues for research and broaden the applicability of the proposed approach.

Supplemental Material

sj-pdf-1-pao-10.1177_10591478251359808 - Supplemental material for Joint Shelf Design and Space Planning Problem With Placement Options

Supplemental material, sj-pdf-1-pao-10.1177_10591478251359808 for Joint Shelf Design and Space Planning Problem With Placement Options by Sandra Zajac and Heinrich Kuhn in Production and Operations Management