## 4 Adaptive Hybrid GA-SAA Algorithm
### Genetic Operators
#### 4.4.2 Crossover Operator  
The crossover operator mixes the genetic materials from the selected parent chromosomes to produce child chromosomes in the successor population with a certain crossover rate [39]. In this paper, we propose an adaptive crossover rate based on the fitness performance of selected parent chromosomes: the individual with higher fitness has a lower crossover rate, which can benefit the reproduction of good solutions and the improvement of bad solutions. As for the source population, we sort the fitness values of the chromosomes. Since we need to consider the fitness performance of the pair of selected parent chromosomes, we calculate the average fitness of each two chromosomes in the source population. Let the average fitness of the two chromosomes with the highest and lowest fitness be \(\overline{f}_{\text{max}}\) and \(\overline{f}_{\text{min}}\), and the highest and lowest crossover rate be \(p_{c-\text{max}}\) and \(p_{c-\text{min}}\). As for a pair of selected parent chromosomes, if the average fitness is \(\overline{f}\), then the crossover rate for this parent chromosome pair is  
\[p_{c}=p_{c-\text{max}}-(p_{c-\text{max}}-p_{c-\text{min}})\frac{\overline{f}- \overline{f}_{\text{min}}}{\overline{f}_{\text{max}}-\overline{f}_{\text{min}}} \tag{19}\]  
When the selected pair is the best, it has a high probability to be preserved and the crossover rate would be the lowest \(p_{c-\text{min}}\), while the selected pair with the worst two individuals would be recombined with the highest crossover rate \(p_{c-\text{max}}\). If the crossover rate is satisfied, then we execute the crossover operators. In this paper, we propose three crossover operators, involving internal crossover and external crossover. Internal crossover operators exchange the alleles or segments of a single chromosome. We propose two internal crossover operators: allele crossover and segment crossover. The allele crossover operator randomly exchanges the codes that represent the reverse stop labels at the same station with a certain proportion, while the segment crossover operator randomly exchanges the code segments that represent the stop labels of two trains along the same route. External crossover operator  
Since the train travel time (especially stop time) is the measurement of stop distribution imbalance, the stop number is a critical impact element. This means that the imbalance index would change when the stop number changes. Thus, to ensure diversity in the  
Figure 3: Illustration of Tournament Selection. crossover process, we think it is significant to exchange the segments with different stop numbers. Next, we extend the crossover strategy in [PERSON] et al. [51] to the K-point crossover process. The crossover point choosing strategy is extended by a bidirectional search along the selected chromosome pair. This strategy searches crossover points from the two ends of the pair and executes the K-point crossover, which is beneficial to a stable descent gradient. Figure 4 illustrates the crossover process. First, we adopt a bidirectional search to determine the crossover points. In Figure 4, each double-coupled chromosome has 40 alleles, where each part has 20 alleles. As for each part, we first choose the candidate left crossover points from the first allele where the two chromosomes have the same stop number, which are represented by the red dots in Figure 4, and it is only needed to exchange the subsequent alleles of these points; then, we choose the candidate right crossover points from the last allele where the two chromosomes have the same stop number, which are represented by the blue dots in Figure 4, and it is only needed to exchange the preceding alleles of these points. Then, we randomly choose a left crossover point and a right crossover point, of which the sequence numbers are \(i_{t},i_{r}\), respectively. The K-point crossover is executed as follows:  
1. If \(i_{l}+2\leq i_{r}\), then the alleles numbered by \(i_{l}+1\) to \(i_{r}-1\) would be exchanged between the two chromosomes. 2.