# Optimization of Warehouse Operations with Genetic Algorithms
## 5 The Proposed Method
### Data Format and Problem Encoding
Further refining of the mutation scheme, together with the mutation--crossover interactions is quite a complex issue and it will be one of our future research topics, when we will attempt to find optimal schemes for different situations. ### Optimization of Order Picking Routes

As previously discussed, the task of optimization of order picking routes is a part of the optimization of product placement in the warehouse. The sum of the lengths of the order picking routes for a given product placement is its cost \(costPP\)--the lower the better (see Equation (1)). The process is presented in the pseudo-code in Algorithm 2 and in the diagram in Figure 4.

During the order picking route optimization the locations of products are constant. The product locations are changed by Algorithm 1 only before each round of order picking route optimization. As discussed in Section 5.1, the order picking route starts from the entrance, then visits all locations of products listed in the current order and returns to the warehouse entrance. The task is to optimize the sequence of visiting the locations to obtain the shortest route. There are two main families of approaches to finding the shortest routes connecting a list of locations--the local search methods (e.g., nearest neighbor or k-opt [28]) and population methods (e.g., genetic algorithms or ant colony optimization [28]). In the Nearest Neighbor Algorithm, we always go from the current location to the nearest yet not visited location. In this way the algorithm implements local search. The local search guaranties finding the nearest location to the current location with 100% probability. However, the drawback of the local search approaches is that they do not include the global view of the situation. Although there was some research to improve these methods, the population methods still have the advantage of applying the global search. A sample route determined with the nearest neighbor, which shows the problems of this method, is shown in Figure 5.

Figure 1:0 Order picking route optimization. As will be shown in the experimental evaluations in Section 6 and as it is also known from previous studies [29], when the Nearest Neighbor Algorithm is used instead of genetic algorithms for that kind of problems, the calculation time can be dramatically reduced, however at the cost of worse results (on average 10% longer routes). To determine the shortest route for completing each order, our method can use three different algorithms:

* Iterating through half of the possible permutations (as the transition cost matrix is symmetric--we can start the order completion from the end or from the beginning of the determined route, so we do not need to check all permutations, but only half of them). This method is 100% accurate, but is the slowest one expect for very short orders. As its complexity is \(O(n! )\), it is impractical for orders above 10 positions and technically impossible to use for orders over 15 positions. * Genetic algorithm with the multi-parent HGreX crossover operator. This method is faster than iterating over permutations, but does not guarantee finding the best solution, but only the solution close to the best one. (The basic version of the HGreX crossover is presented in Section 4.3 and the multi-parent extension in Section 5.4.1.) The fitness of the \(i\)-th order picking route is given by Equation (5). \(fitnessR(i)\) takes larger values for better individuals to ensure that they have higher probability of being selected as parents, while \(lengthR\) take smaller values for better individuals, as this value expresses the route length. Figure 1:1 (5) where \(c_{2}\) is a coefficient, which determined the strength of the selection (the lower \(c_{2}\), the stronger preference for the individuals representing shorter routes) \(lengthR_{max}\) is the maximal and \(lengthR_{min}\) is the minimal length of the order picking route in the population.