# An Integrated Optimization Method of High-Speed Railway Rescheduling Problem at the Network Level
## 4 NSGA-III Algorithm
### Initial Populations and Infeasible Solution Adjustment
After the initialization of the solutions, there may be some discontinuous sequence value in a section, such as 0, 1, 3, 4, 5, 0, which should be adjusted to 0, 1, 2, 3, 4, 0. Algorithm 4 shows the process. ### Decoding

The chromosomes are made of four gene fragments, which represent the operating scheme of the standby train sets, the cancellation scheme of the trains, the sequence of the trains, and the coupling scheme of the trains, respectively. Thus, the chromosomes have to be decoded to derive the train timetable, the train set circulation plan, and the passenger demand flow plan. Therefore, the decoding process is divided into three main steps. #### 4.4.1 Calculating and Obtaining Train Timetable

The four gene fragments above can be expressed by the decision variables \(h_{b}\), \(can^{c,t}\), \(tos_{s}^{ct}\) and \(wtc_{c,t}^{c^{\prime},t^{\prime}}\), respectively (as mentioned in Section 3.1). We stipulation the direction of the interruption direction 1 and the opposite direction is direction 2. We design a sub-model to calculate the timetable of the trains whose direction is direction 1, with the objective of rescheduling the trains of direction 1 in the shortest possible time:

\[\text{min}\text{$\sum$}_{c\in C}\sum\
olimits_{t\in T^{dret}}{{a}at_{TMS^{c,t} }^{c,t}}\forall c\in C,t\in T^{dret} \tag{41}\]

\[s.t. \tag{42}\]

The used sets, symbols and variables are defined in Section 3.1. The model is solved with CPLEX and a group of values of variables. After this part, \(h_{b}\), \(can^{c,t}\), \(tos_{s}^{c,t}\), \(wtc_{c,t}^{c^{\prime},t^{\prime}}\), \(aws_{j}^{c,t}\), \(adt_{j}^{c,t}\) and \(aaf_{j}^{c,t}\) can be determined. #### 4.4.2 Rescheduling Train Sets Circulation Plan

After calculating and obtaining the timetable of direction 1-trains, we get the arrival time of these trains at their destination stations. And some train sets of them should continue executing the trains in direction 2 according to their original circulation plan. These trains in direction 2 can be executed by their original train sets, the train sets in otheraffected circulations, and the standby train sets. The rescheduling algorithm is shown as Algorithm 5:

```
Step 1. Find all the trains of direction 2 which should be executed by train-sets according to the original trains-sets circulation plan. Create set \(ET\) and add them to set \(ET\). Step 2. For each train \(t\in ET\) Find out whether train \(t\) can be executed by its original train-set. If yes  Train \(t\) will be executed by its original train-set Remove Train \(t\) from set \(ET\). Step 3. Sort the trains according to the departure time at the start station. (from early to late) For each train \(t\in ET\) Find out if train \(t\) can be executed by the train-sets in other affected circulations. If yes  Let the earliest train-sets execute train \(t\) and remove train \(t\) from set \(ET\). Step 4. Sort the trains according to the departure time at the start station. (from early to late) For each train \(t\in ET\) Find out if train \(t\) can be executed by the standby train-sets. If yes  Let the standby train-sets execute train \(t\) and remove train \(t\) from set \(ET\). Step 5. Find out if there are trains in set \(ET\). If yes  Cancel these trains. ```

**Algorithm 5** Rescheduling train sets circulation plan

In this part, the variables \(a_{i}^{c,t}\), \(h_{b}^{c,t}\), \(aat_{j}^{b}\), \(adt_{j}^{b}\), \(to_{j,j+1}^{c,t^{\prime},t^{\prime}}\) and \(tr_{c^{\prime},t^{\prime}}^{c,t}\) can be determined, and the train-sets circulation plan is rescheduled. #### 4.4.3 Rescheduling Passenger Demand Flow Plan

In this part, we design a method to reschedule passenger demands. The passenger demands that need to be served consist of the passenger demands of interrupted trains and the passenger demands of canceled trains. The standby train sets and other affected trains can serve these passenger demands. Considering the distance and delay time, this method gives the cross-line passenger demands the priority of being served.