# Optimization Model of Express-Local Train Schedules Under Cross-Line Operation of Suburban Railway
## 6 Algorithmic Design  
The extended adaptive large neighborhood search (E-ALNS) algorithm is used to solve the train timetable model. E-ALNS uses different destruction and repair operators to find the current solution neighborhood, evaluates the operators, and then selects them with a roulette strategy, which prevents the algorithm from falling into the local optimum too early, improves the global search ability, and is highly efficient in dealing with large-scale combinatorial optimization problems. This paper follows this classical algorithm, and the algorithm design covers the design of destruction and repair operators, operator selection, weight update rules, and termination conditions. The purpose of the destruction operators is to perturb the current solution by deleting or modifying the existing train operation arrangements, thereby encouraging the exploration of new solution spaces. In this study, two categories of destruction operators are designed:  
1. Train Removal-Based Destruction Operators: 1. Randomly select a train from the current timetable and remove it. 2. Calculate the departure intervals between neighboring trains at each station, and remove the train whose deletion results in the smallest overall interval during operating hours. 3. For each train with service plan \(p\) and first-station departure time \(t\), evaluate the number of passenger boardings at each station \(s\). Remove the train with the lowest total number of passenger boardings. 2. Service Plan-Based Destruction Operators: 1. Randomly change a train's service pattern from a local train to an express train. 2. For each express train, count the total number of boardings at small stations. Identify the local train with the lowest small-station boardings and change it to an express train. 3. Randomly change a cross-line train into a non-cross-line train. 4. Identify the cross-line train with the lowest number of passengers traveling to segments shared with urban rail lines and convert it into a non-cross-line train. The purpose of the repair operators is to restore feasibility by reinserting or adjusting trains within the solution to compensate for missing or unreasonable configurations caused by the destruction phase. Two categories of repair operators are developed:  
1. Train Reinsertion-Based Repair Operators: 1. Randomly select a train and reinsert it into the current timetable. 2. Compute the departure intervals at each station, identify the time slot with the largest interval across all stations, and insert a train at that point. * Identify stations with high passenger backlogs and insert a train into the timetable, with the specific train selected randomly. * Service Plan-Based Repair Operators:
* Randomly convert an express train back to a local train. * For each local train, identify small stations with severe passenger backlogs, and convert the associated train to an express train if appropriate. * Randomly convert a non-cross-line train into a cross-line train. * Identify the non-cross-line train with the highest passenger flow destined for segments shared with urban rail lines and convert it into a cross-line train. In each iteration, a roulette selection mechanism is adopted to select the currently applied operator from the set of destruction and repair operators. To measure the contribution of each operator \(\varphi\) in the search process, a score \(\pi_{\varphi}\) is used to evaluate its performance in successive iterations, i.e., after each selection of operators, the corresponding score is increased according to the quality of the obtained solution \(S\). The logical framework of the E-ALNS algorithm is schematized as shown in the following Algorithm 1.