## 2 Related Works
Consequently, we propose a time-based service regularity model and integrate it with service capability to further enhance the rescheduling model. The rescheduling problem is a long-term decision-making problem. An intuitive idea to achieve comprehensive optimization is to perform rescheduling on the whole schedule directly, but this requires significant computational support. By decomposing complicated problems into several sub-stages and constructing correlations among them, dynamic programming can help efficiently obtain long-term beneficial solutions [30]. Moreover, the scheduling model based on dynamic programming can adeptly take into account time-based variations, which help improve resource utilization efficiency and achieve robust schemes [31]. Therefore, dynamic programming has attracted considerable interest in operational optimization and may be more practical for performing rescheduling. Considering service capability, the rescheduling problem is described as a binary linear programming model. Many deterministic algorithms can solve this problem and obtain analytical solutions, such as column generation [14], and branch-and-bound [6; 32] algorithms. However, the problem becomes nonlinear when service regularity is integrated because trips can be canceled or retimed, which complicates the solution. As the problem has been proven to be NP-hard [3; 4; 5; 6; 7], several approximation algorithms have been applied to effectively address the problem. In [8], the auction algorithm was used to solve the model pseudo-polynomially. Lagrangian relaxation [4; 9] can help reduce the complexity by decomposing the problem into multiple sub-problems. Nevertheless, the computational cost still explodes with the number of remaining trips. Thus, researchers have designed many heuristic-based algorithms to reduce the solution space. For example, the greedy heuristic algorithm [11], insertion heuristic algorithm [4], variable neighborhood search heuristic algorithm [33], tabu search algorithm [34], neighborhood search algorithm [35], simulated-annealing algorithm [28], and genetic algorithm [36] have been applied to gradually modify initial solutions by performing local adjustments. Heuristic algorithms are highly effective for solving combinatorial optimization problems and obtaining approximate optimal solutions. Local search (LS) is a prevalent heuristic algorithm employed for combinatorial optimization problems. Typically, the algorithm preserves a feasible solution and iteratively replaces the solution with its neighbor of higher quality until a locally optimal solution is achieved [37]. The large neighborhood search (LNS) algorithm was developed based on the principle of local search, where the neighborhood is defined by recombination methods (often heuristics) that are used to destroy and repair a current solution [38]. Through the use of heuristics, LNS is capable of exploring complex neighborhoods efficiently and finding better candidate solutions in each iteration, making it one of the most successful paradigms for solving various transportation and scheduling problems [37]. The recombination methods function by strategically destroying the solution at specific positions and subsequently repairing it using predefined rules. Various destroy methods are utilized in bus operation research, including random removal [39], worst removal [40], and neighborhood-based removal [41]. Common repair methods involve additions and shifts, such as stop insertion for bus routes [42], trip insertion for bus schedules [40], or timetable shifts [43]. The flexible nature of these configurations makes LNS a powerful tool for solving bus operation problems. Through the improvement of LNS with appropriately designed recombination rules,the aim of ensuring service capability and regularity can be effectively achieved in the bus rescheduling problem.