# A Novel Multi-Agent-Based Approach for Train Rescheduling in Large-Scale Railway Networks
## 5 Case Study
### Computational Complexity Analysis  
In the following tables, Tables 1 and 2 illustrate the computational complexity in a train rescheduling problem and that in a junction agent in the proposed MAS. The computational complexity analysis includes the total number of continuous variables \(t_{\text{res}}^{I_{\text{res}}}\), binary variables \(i_{\text{res}}^{I_{\text{res}}}\), railway operational constraints, and timetable coupling constraints. And the second table illustrates the exact number of variables and constraints in this case study. In this study, we use asymptotic complexity, indicating the worst case counts in terms of optimization. Figure 3: Network of Derby station and its surrounding area and the definition of each junction in the case study. From the complexity analysis presented earlier, it is evident that the train rescheduling problem in the case study involves a vast number of variables that must be optimized under a substantial set of constraints. Solving this mixed-integer linear programming (MILP) problem with conventional tools like CPLEX typically requires around two hours of computation time. Furthermore, the authors' experimentation has shown that centralized solution approaches--such as genetic algorithms (GAs) using parameter configurations identical to this study--often encounter excessively large search spaces. In some cases, this can even yield inferior solutions compared to simple first-come-first-served (FCFS) dispatching rules. The multi-agent system (MAS) approach offers a crucial advantage for train rescheduling problems through its distributed optimization framework. By decomposing the overall problem and assigning specific optimization tasks to individual junction agents, the MAS approach achieves three key benefits:  
1. It dramatically reduces the problem's search space to computationally tractable levels. 2. It enables truly real-time operation for traffic control applications. 3. It facilitates parallel computation through distributed junction agents, yielding significantly faster solutions than centralized methods. While the junction agents' localized optimization might appear more limited in scope compared to global optimization approaches, the integrated Condorcet voting mechanism effectively resolves any resulting infeasibilities, ensuring system-wide solution quality. Furthermore, timetable coupling constraints, which ensure the synchronization of train schedules across different junctions, are managed by the collaborative agent. Although the voting process may require adjustments to the train sequence variables \(i_{\text{tr}_{\text{tr}},\tau_{\text{tr}}}^{l_{\text{tr}}}\) and the corresponding indicators \(i_{\text{tr}_{\text{tr}},\tau_{\text{tr}}}^{l_{\text{tr}},l_{\text{tr}}}\), not all decisions made by the junction agents will conflict with one another. As a result, the number of timetable coupling constraints may be significantly smaller than initially anticipated, depending on the test scenario. This reduction is supported by the classification operator within the proposed GA in the MAS. In contrast, a centralized system must account for all timetable coupling constraints, which further extend the computational time. Therefore, solving large-scale railway network train rescheduling