## 3 Proposed Method
### Route Generation
#### 3.5.3 Improved Genetic Algorithm  
The genetic algorithm (GA) was designed according to the evolution law of organisms in nature. It is a computational model of the biological evolution process that simulates the natural selection and genetic mechanism of Darwinian biological evolution. It thus searches for the optimal solution by simulating the natural evolution process [27; 28; 29; 30]. In this study, an improved GA was used to search effective edges, and travel routes satisfying constraint conditions and scenic features conforming to user preferences were planned according to different urgencies. The algorithm flow chart is shown in Figure 2. In the figure, the gene splicing operator and the gene replacement operator are two new operators compared with the traditional genetic operator, and the gene splicing operator is used to solve the problem of discontinuity of actual paths corresponding to chromosomes. The gene replacement operator is an improved part of the traditional GA according to the problem requirements. The purpose of adding this operator is to make a local optimization adjustment of all the current chromosomes before each iteration generates a new population to improve the performance of the final search results. \(b\) is the travel time budget, and \(C\) is the maximum number of replacements. 1. Selection. This paper uses roulette to select offspring, that is, the probability of each chromosome being selected is proportional to its fitness value. This method may not ensure the best individual inherits the next generation, but it can avoid the impact of super chromosomes on the overall evolution. At the same time, it is possible to pass on the worst chromosome to the next generation. 2. Crossover. In this paper, the method of single point crossing is used to cross chromosomes, that is, randomly select two chromosomes and determine the same edge of the path to cross that can ensure the continuity of the path. If two chromosomes have multiple identical edges, one of the same edges is randomly selected for crossing. If two chromosomes do not have the same edge of the path, then randomly select one edge to cross, and the continuity of the path is guaranteed by the gene splicing operator. The schematic diagram of the crossover operation is shown in Figure 3a, in which the corresponding paths of the two chromosomes intersect at the edge \(f\), so the chromosomes are crossed at a single point at \(f\) to form two new chromosomes. 3. Mutation. The mutation operation randomly selects an edge in a chromosome, randomly selects another effective edge in the effective region, and then replaces the selected edge on the chromosome with the effective edge. The variation here is adjusted with only a small probability. After the above crossover and mutation operators have been executed, the problem of gene duplication in chromosomes may arise. In practice, the user's route from the starting point to the end point should be unidirectional, and the user is not allowed to walk back and forth on a certain section of road repeatedly. This situation will also increase the cost of useless paths. Therefore, it is necessary to check the chromosomes and delete repeated edges. The schematic diagram of the mutation operation is shown in Figure 3b, in which the gene \(f\) of the chromosome mutates into gene \(g\), resulting in the continuous occurrence of two gene \(g\) in the chromosome. At this time, a duplicate gene \(g\) is deleted through the deletion operation to form a new chromosome. 4. Gene Splicing. Gene splicing is mainly used to solve the problem of discontinuous paths corresponding to chromosomes. In the operation of chromosome coding and  
Figure 3: Schematic diagram of crossover and mutation operation. (**a**) Crossover; (**b**) Mutation. Figure 2: Flow chart of improved GA.  
cross mutation, the corresponding path of chromosome will be discontinuous, so this paper uses the shortest path to fill the gap between edges.