# Genetic Algorithm for the Retailers' Shelf Space Allocation Profit Maximization Problem
## 3 Problem Definition  
The problem concerns constructing a planogram, i.e., allocating \(P\) products on \(S\) shelves, where shelves are divided into \(V_{i}\)\((i=1,\dots,S)\) virtual segments, to maximize the predicted profit from selling these products. In this research, we define the term virtual segment, which means visual shelf dividing into the parts for correct products allocation based on their types. There are no physical borders between the segments on the shelf, and the division is only virtual and used only by space planners. Clients see visual groups of product allocation, e.g., by category. Such allocation of products on the shelves helps the clients examine and compare the products along the shelves. Each shelf \(i\) is described by the shelf length \(s_{i}^{l}\), the shelf height \(s_{i}^{h}\), and the product's weight limit \(s_{i}^{h}\). Moreover, depending on the vertical shelf position, the types of shelf can be specified and described by the binary parameters:  
* the shelf is a pallet (which is located on the floor and used for big heavy products), \(s_{i}^{pl}\);
* the shelf is at eye level (used for expensive products or VIP products), \(s_{i}^{e}\);
* the shelf is at a lower level (used, for example, to display children's products), \(s_{i}^{lw}\). A shelf \(i\) is divided into \(V_{i}\) virtual segments for correct product allocation based on their position constraints. It is supposed that all virtual segments have equal width on the shelf. The width of the virtual segment is \(v_{i}^{w}=s_{i}^{l}\):\(V_{i}\), i.e., it is possible to divide the shelf length \(s_{i}^{l}\) into the number of virtual segments \(V_{i}\) on this shelf without a remainder. Depending on the horizontal position of the shelves and the customers' traffic direction, there are several types of a virtual segment \(g\)\((g=1,\dots,V_{i})\):  
* the virtual segment is used for local products, \(v^{lc}\);
* the virtual segment is used for convenience products, \(v^{v}\);
* the virtual segment is situated in the central part of the shelf;
* the virtual segment is situated near the first aise;
* the virtual segment is situated near the last aise. The shelf index describes virtual segments \(s^{lc}\)\((s^{lc}=\{1,\dots,S\})\), \(s^{v}\)\((s^{v}=\{1,\dots,S\})\) and the index of the virtual segment on this shelf is \(v^{lc}\)\((v^{lc}=\{1,\dots,V_{i}\})\)), \(v^{v}\)\((v^{v}\)\(=\{1,\dots,V_{i}\})\) consequently, i.e., local and virtual convenience segments are defined by the index of row and index of the column on a planogram. Each product \(j\) is characterized by its width \(w_{j}\), height \(h_{j}\), and weight \(b_{j}\). The supply limit of the product \(t_{j}\) restricts the maximum availability of the product, which can be  
number of facings to support the cappings above is \(\left\lceil\frac{h_{j}}{w_{j}}\right\rceil\), i.e., the necessary number of facings in one capped group. The minimum \(n_{j}^{\min}\) and maximum \(n_{j}^{\max}\) side nestings per position may be also restricted for each product. \(n_{j}^{\max}\) is the maximum number of nestings that can be physically placed above one facing without destroying it. In order to limit the number of shelves where the product can be placed, the minimum \(s_{j}^{\min}\) and maximum \(s_{j}^{\max}\) number of such shelves on which it can be allocated are defined. The total number of facings of the product is equal to the sum of facings \(f_{ij}\), cappings \(c_{ij}\) and nestings numbers \(n_{ij}\) of a product.