# Research on O2O Takeout Delivery Route Optimization Problem Based on Improved Genetic Algorithm
## 4 Improved Genetic Algorithm  
In this paper, an improved genetic algorithm incorporating a local search method is used to solve the model. According to the characteristics of the takeout delivery problem, where pickup precedes delivery, during the construction of the initial solution, as well as in the crossover and mutation stages of the algorithm, the allocation of the merchant points to riders and the service sequence for the corresponding orders were determined first. Then, customer points were inserted into this sequence in a certain way to generate a feasible solution to the original problem. In addition, after each generation of genetic operations, two local search operators were applied to enhance the local search ability of the algorithm. The framework of the algorithm is illustrated in Figure 4.  
The main steps of the improved genetic algorithm proposed in this paper are as follows:  
1. Chromosome encoding. Integer encoding is used, with a length of \(2n+m-1\). The merchant genes and customer genes each have \(n\) positions, and the allocation of all orders to \(m\) riders is determined by the \(m-1\) zero genes as separators. 2. Population initialization. Traditional population initialization generally adopts a random initial population approach. However, considering the characteristics of the O2O takeout delivery problem, where pickup precedes delivery, the random initialization approach tends to generate many infeasible solutions, thereby reducing the quality of the initial population. Therefore, first, the \(n\) merchant points were assigned to \(m\) riders, forming a permutation of length \(n+m-1\), denoted as \(\pi\). During the population initialization phase, the orders assigned to each rider were ensured to satisfy the vehicle capacity constraint and were as balanced as possible. Finally, using equal probability, the random insertion and shortest distance insertion methods  
Figure 4: Flowchart of the improved genetic algorithm. were employed to insert all customer points after the corresponding merchant points, while ensuring that each order's merchant and customer points are assigned to the same rider's delivery route. Compared to the randomly generated initial population, this method provides the algorithm with a set of better initial feasible solutions, thus improving the convergence speed of the algorithm. Figure 5 shows a diagram of a chromosome encoding. Here, the number of orders is 9, the merchant points are represented by genes 1-9, the customer points are represented by genes 11-19 (which correspond to the values of the merchant point genes plus 10), and the zero genes represent rider separations. Rider 1 serves 3 orders, and the service route is as follows: \[2\to 9\to 19\to 12\to 5\to 15\] The service routes for rider 2 and rider 3 can be derived similarly. 3. Fitness calculation. In order to avoid negative fitness values during the calculation process, the objective function is normalized: \[Z^{\prime}=\omega_{1}\frac{Z_{1}-\min\{Z_{1}\}}{\max\{Z_{1}\}-\min\{Z_{1}\}}+ \omega_{2}\frac{\max\{Z_{2}\}-Z_{2}}{\max\{Z_{2}\}-\min\{Z_{2}\}}\] (16) The fitness function is then selected as the reciprocal of \(Z^{\prime}\). 4. Selection operation. The selection operator in the algorithm uses a roulette wheel selection strategy. 5. Crossover and mutation operators. Since directly performing crossover and mutation operations on the chromosomes may lead to situations such as the customer points of the same order appearing before the merchant points or different riders delivering the same order, the proposed algorithm first performs the crossover and mutation operations on the permutation \(\pi\) that only contains the merchant points and zero genes. After each crossover and mutation operation, any solution that does not satisfy the vehicle capacity constraint must be repaired. The specific repair rule is as follows: first, check whether the capacity of each vehicle exceeds its capacity limit. If a vehicle's capacity exceeds the limit, identify the vehicle with the largest capacity violation.