# Optimization of Warehouse Operations with Genetic Algorithms
## 5 The Proposed Method
### Data Format and Problem Encoding
For a graph of \(v\) vertices (locations) and \(e\) connecting edges (transition costs), calculating all the distances with Dijkstra Algorithm with a priority queue has the complexity \(O(v(e+vlogv))\), while the complexity of the two other algorithms is \(O(v^{3})\) and \(O(ev^{2})\). Calculating the cost matrix with the Dijkstra Algorithm takes only a very small, practically negligible, fraction of the time of the whole optimization of the product locations. Moreover, once calculated, the cost matrix can be re-used for other product placement as long as the physical layout of the warehouse does not change. The A\({}^{\star}\) Algorithm [23] can be faster than Dijkstra only when the approximate cost from the current to the target node can be assessed. However, in this problem, we are not able to assess the approximate cost, because we do not know the coordinates of particular locations, but only the transition cost between neighboring locations. Considering these two factors it is not justified to demand from the user preparing additional data with coordinates of each location in order to use the A* Algorithm, as in this case the gain of the CPU time (usually less than a second) would not compensate the lost of the user's time (usually several hours) spent on preparing the additional data. ### Product Placement Optimization

In this subsection we present the algorithm used to optimize the placement of particular products in the warehouse in order to minimize the total time of completing the orders from the order list. The main optimization process is shown in pseudo-code in Algorithm 1 and as diagrams in Figures 2 and 3. The sub-process, which determines the shortest order picking routes is discussed in the next section. Figure 2: Product Placement Optimization (main process). Now will explain the base version of the algorithm with \(numberOfProcessRestarts=1\) (line 2 in Algorithm 1) and in Section 5.4.3 we will explain the use and purpose of multiple process restarts (\(numberOfProcessRestarts>1\)). The process starts in line 1, where the Dijkstra algorithm calculates the full matrix \(\mathbf{D}\) of transition costs (or distances) between product locations (see Section 5.1 for details). In line 3 the initial random population of product placements (PP) is generated. In line 7 the genetic algorithm starts the optimization. In line 10 the algorithm checks if any of the current individuals existed previously in current or any past epoch. If so the fitness of such an individual is not calculated but retrieved from the cache. In line 15 the shortest route for completing each different order for the current PP is calculated with Algorithm 2. Since we need to minimize the sum of order completion times, for each considered placement of products in the warehouse we need to calculate the time of each order completion and then add the times. To minimize the computational complexity of this step we group orders consisting of the same products together and assign to such an aggregated order a higher weight, which equals the number of single orders of which the aggregate order is composed. In line 18 the cost of the current PP is calculated, next the fitness is calculated from the cost and the cache is updated. In line 25 the parents for each child are selected and in the next line the child is created with the AEX crossover operator. If the fitness of the best PP has not improved for \(NBI_{PP}\) iterations (line 28) then the optimization is finished. In line 32 the promotion of children and best parents to the next generation takes place. In the next line the mutation is applied and the cache is updated. Finally in the last line the algorithm returns the best product placement and the corresponding set of the shortest order picking routes.