## 4 Solution Approach
### Dynamic Programming  
The public transit rescheduling problem exhibits several significant characteristics: (a) the initial schedule is phased; (b) disruptions have a backward propagating impact along schedules, which represents a long-term decision challenge; and (c) the computational complexity increases with the number of buses and trips. Therefore, the application of staged decision making over time becomes practical. Drawing inspiration from this concept, we introduce dynamic programming to break down the problem and facilitate state transitions across stages. This approach allows us to derive a suitable response to disruptions and address a smaller-scale problem with LNS in each stage, consequently reducing the solution space in a rational manner and efficiently obtaining a long-term optimal solution. According to the typical scheduling phase, we divide the rescheduling problem into hourly stages. Each sub-stage, denoted as \(stage_{k}\), is defined by a start time \(T_{min}^{k}\) and an end time \(T_{max}^{k}\), spanning one hour. These stages are guided by the objective presented in Formula (8), and the allocation of buses \(\mathbf{B}_{k}\) and trips \(\mathbf{R}_{k}\) is determined as follows:  
\[\mathbf{B}_{k}=\{b|T_{st}^{b}\leq T_{max}^{k}\quad\&\quad T_{min}^{k}<T_{ed}^ {b}\} \tag{16}\]  
\[\mathbf{R}_{k}=\{i|T_{min}^{k}\leq T_{i}<T_{max}^{k},i\in\mathbf{V}\} \tag{17}\]  
where \(T_{st}^{b}\) and \(T_{ed}^{b}\) represent the start and end times of bus \(b\)'s daily working schedule. In each stage, we input the initial spatiotemporal information of the arranged buses and scheduled trips for that period and employ LNS to generate the schedule for that specific time frame. A bus \(b\) becomes available for dispatch after completing its previous trip. Thus, the input state for sub-stage \(stage_{k}\) can be represented as \(\mathbf{ST}_{al}^{k}=\{(s_{al}^{b,k},T_{al}^{b,k})|b\in\mathbf{B}_{k}\}\), where \(T_{al}^{b,k}\) signifies the time when the bus completes its last trip in the previous stage, and \(s_{al}^{b,k}\) corresponds to the arrival stop. With specific values of \((\mathbf{B}_{k},\mathbf{ST}_{al}^{k},\mathbf{R}_{k})\), we construct the connection network and ultimately produce the solution for \(stage_{k}\), denoted as \(f_{k}=\{(e_{i,j}^{b},T_{j})|b\in\mathbf{B}_{k},i,j\in\mathbf{R}_{k}\}\). The corresponding cost \(z_{k}\) can be calculated using (8). Between stages, the states of buses undergo transitions, allowing us to consider the propagation of disruptions. Buses are scheduled to perform trips in \(stage_{k+1}\) upon the completion of the \(stage_{k}\) schedule. Consequently, the input state for \(stage_{k+1}\) is exclusively determined by the input state and decisions made in \(stage_{k}\). We denote \(g_{k}\) as the process governing the state's evolution from \(stage_{k}\) to \(stage_{k+1}\), and the transition function is defined in Formula (18). \[\mathbf{ST}_{al}^{k+1}=g_{k}(\mathbf{ST}_{al}^{k},f_{k}) \tag{18}\]  
With the state representation of each stage and the transition function, we can formalize the problem's optimization. Given the initial state \(\mathbf{ST}_{al}^{1}\) when disruptions occur and \(K\) sub-stage solutions \(\{f_{1},f_{2},\ldots,f_{K}\}\), the total cost of the optimization scheme is represented by Formula (19). Finally, to minimize the total cost, the optimal value of an initial state is given by function (20) [30]. \[J(\mathbf{ST}_{al}^{1};f_{1},f_{2},\ldots,f_{K})=\sum_{k=1}^{K}z_{k} \tag{19}\]  
\[J^{*}(\mathbf{ST}_{al}^{1})=\min J(\mathbf{ST}_{al}^{1};f_{1},f_{2},\ldots,f_{K}) \tag{20}\]  
Let \(J_{k}^{*}(\mathbf{ST}_{al}^{k})\), as shown in (21), denote the optimal value of the tail sub-problem that starts from \(stage_{k}\), i.e., the minimal rescheduling cost from \(stage_{k}\) to \(stage_{K}\). Then, dynamic programming solves Function (21) by considering all possible states \(\mathbf{ST}_{al}^{k}\) and then proceeds with Formula (22).