# Genetic Algorithm for the Retailers' Shelf Space Allocation Profit Maximization Problem
## 3 Problem Definition
There are some binary parameters that reflect additional properties of the product:  
* \(p_{j}^{pl}\) denotes if the product must be put on a pallet (the products in big packs are placed on the lowest shelf because of their weight),
* \(p_{j}^{r}\) shows if the product must be put at eye level (which will increase its selling),
* \(p_{j}^{\prime\prime\prime}\) indicates if the product must be put at a lower level (the cheapest products with high rotation),
* \(p_{j}^{\prime\prime}\) and \(p_{j}^{\prime\prime}\) show if the product must be placed near the first or last aisle (first-aid products),
* \(p_{j}^{r}\) means that the product must be allocated in the rest part of the shelf (but not near the aisle), i.e., in the centre of the shelf (expensive, new, brand products),
* \(p_{j}^{r}\) means that the product must be put in the virtual segment for convenience products,
* \(p_{j}^{c}\) indicates whether the product must be placed in the virtual segment dedicated to local products. In this research, we use SVS to refer to the Special Virtual Segment of any local, convenience, centre, or aisle virtual segments. The product \(j\) is unique if it is marked at least by one of the product properties: \(p_{j}^{lc}\), \(p_{j}^{r}\), \(p_{j}^{c}\), \(p_{j}^{aff}\), \(p_{j}^{\prime\prime}\). To solve task of the correct product placement into the SVS, we define the type \(m\) (\(m=1,\ldots,5\)) for every kind of virtual segment constraint according to the horizontal position on the shelf. There are five possible product types on the shelves: local product (\(m=1\)), convenience product (\(m=2\)), shelf centre product (\(m=3\)), first aisle product (\(m=4\)), and last aisle product (\(m=5\)). On each type \(m\), we divide the number of products \(P\) into three subsets on each shelf: subset A is before the SVS, subset C is inside the SVS, subset B is after the SVS. For example, C is a subset for the products allocated in the first or last aisle SVS and marked as special products. Other products (not special ones) may be allocated to the subsets \(A,B\) with no restrictions. Thus, binary decision variable \(y_{mijr}^{ABC}\) indicates if the product \(j\) belongs to the appropriate type \(m\) (\(m=1,\ldots,5\)) of the subset \(r\) (\(r=1,\ldots,3\)) on the shelf \(i\). Figure 3 shows the general allocation of the virtual segments on a planogram. Based on the given SVS numbers, we calculate \(z_{mn}\) (\(n=1,\ldots,2\)), which defines the left (\(n=1\)) and right (\(n=2\)) horizontal coordinates of the virtual segment. The size of the  
Figure 3: Virtual segments on a planogram. special virtual segments is flexible. This means that the virtual segment may be reduced, extended or moved left or right, but the centre of each special product must be placed inside the original left and right borders of the SVS. Figure 4 demonstrates the possible sizes of the virtual segments on a planogram. On the first (lowest) shelf, the first aisle virtual segment is extended, and the space for the centre virtual segment is reduced. On the second shelf, the last aisle virtual segment is reduced, and the space for the centre virtual segments is extended. On this shelf, the convenience virtual segment is also extended. On the third shelf, the local virtual segment is reduced, the centre virtual segments are extended. On the fourth (highest) shelf, there are no changes in segments sizes. The left and right coordinates of the SVS are calculated as follows:  
\(z_{11}=(v^{lc}-1)\cdot v_{i}^{w},\ z_{12}=v^{lc}\cdot v_{i}^{w}\)--for local virtual segment;  
\(z_{21}=(v^{p}-1)\cdot v_{i}^{w},\ z_{22}=v^{p}\cdot v_{i}^{w}\)--for convenience virtual segment;  
\(z_{31}=v_{i}^{w},\)\(z_{32}=s_{i}^{l}-v_{i}^{w}\)--for shelf center;  
\(z_{41}=0,\)\(z_{42}=v_{i}^{w}\)--for first aisle;  
\(z_{51}=s_{i}^{l}-v_{i}^{w},\)\(z_{52}=s_{i}^{l}\)--for last aisle. Figure 5 presents the possibilities for the extension and reduction of the SVS.