# Train Service Design for Rail Transit Cross-Line Operation Applying Virtual Coupling
## 4 Adaptive Simulated Annealing Genetic Algorithm (ASA-GA)  
As the optimization model of the train service scheme established in this study is a nonlinear integer programming model, it is mostly solved by a heuristic algorithm. The genetic algorithm (GA) is widely used in URT system optimization problems, such as the study of integrated optimization of express trains and cross-line trains by [PERSON] et al. [28] and the study of energy consumption and timetable operation of trains by [PERSON] et al. [29]. Although the GA has a strong global search ability and is suitable for large-scale optimization problems, it is prone to fall into local optimality, while the simulated annealing algorithm (SAA) simulates the cooling process and continuously adds disturbance to the generated solution to find the optimal solution, which has a strong local search ability. Combined with GA, it can effectively avoid falling into the local optimal situation and achieve the purpose of complementary advantages. Moreover, to improve the search performance of SA-GA, an adaptive selection mechanism, namely, an adaptive simulated annealing genetic algorithm (ASA-GA), is designed to solve the proposed model in this study, and its main steps are as follows. (1) Population Initialization  
Train frequency, train composition, and turn-back stations are selected as genes on each chromosome. In this study, we use decimal coding, and one chromosome represents one train service scheme. As shown in Figure 7, a chromosome is divided into three parts, where part A indicates the train frequency of three types of trains (including train 1, train 2, and train 3), part B indicates the train composition of three types of trains, and part C indicates the turn-back stations of the cross-line. Step 1: Set the initial value parameters of GA and SA, including the population size, initial generation, initial temperature, final temperature, cooling coefficient, maximum number of generations, and number of cycles per temperature level. Step 2: Input boundaries of genes in parts A, B, and C of chromosomes, which facilitates the generation of feasible solutions and faster convergence. Step 3: Perform random generation of parental chromosome genes: this includes the three parts. Step 4: Check the viability of chromosomes. If this is not feasible, return to step 2 until feasible populations are obtained. (2) Adaptive crossover and mutation operator  
Crossover is one of the main operations of GA, and the process is shown in Figure 8. To avoid that, a large crossover probability will destroy the optimal solution, and a small crossover probability will affect the diversity of individuals. In this study, the adaptive annealing temperature crossover probability \(p_{c}\) is expressed as in Equation (48):  
\[p_{c}= \begin{cases}\frac{p_{c1}+p_{c2}}{2}\cdot\frac{f_{\max}-f^{\prime}}{f_{ \max}-f_{\text{avg}}}-\frac{\beta N}{f_{\text{max}}},&f\geq f_{avg},\\ \frac{p_{c1}+p_{c2}}{2}-\frac{\beta N}{f_{\text{avg}}},&f\leq f_{avg}.\end{cases}  \tag{48}\]  
Figure 7: Illustration of the composition of chromosome. where \(p_{c1}\) and \(p_{c2}\) are the maximum and minimum values of crossover probability, respectively. \(f_{max}\) and \(f_{avg}\) are the highest adaptation values and the average adaptation values, respectively. \(f^{\prime\prime}\) is the larger adaptation value of the two crossed chromosomes. Mutation operation is the replacement of a specific gene in an individual's chromosome with an allele to form a new individual. Some chromosomes are randomly selected to be the parents of mutation. The adaptive annealing temperature mutation probability \(p_{m}\) is shown in Equation (49):  
\[p_{m}= \begin{cases}\frac{p_{m1}+p_{m2}}{2}\cdot\frac{f_{max}-f}{f_{max}-f_{avg }}-\frac{\beta N}{f_{now}},&f\geq f_{avg},\\ \frac{p_{m1}+p_{m2}}{2}-\frac{\beta N}{f_{now}}\,&f\leq f_{avg}.\end{cases}  \tag{49}\]  
where \(p_{m1}\) and \(p_{m2}\) are the maximum and minimum values of mutation probability, respectively.