# A Novel Multi-Agent-Based Approach for Train Rescheduling in Large-Scale Railway Networks
## 1 Introduction  
The rapidly increasing demand for railway transport has led to the intensive use of railway infrastructure. As more services are added to already busy networks, trains must operate at higher speeds and with shorter headways. Consequently, even a small initial delay can cascade into a series of knock-on delays affecting trains across the entire network due to interconnected schedules and network conflicts [1]. Traditionally, train monitoring and real-time rescheduling are traditionally performed by local dispatchers and real-time rescheduling decisions are made when significant delays occur, often using rule-based approaches such as  
* Timetable Order Enforced (TTOE): Dispatch trains in the same sequence as their operational timetables. * First Come First Served (FCFS): Prioritize the first train arriving at the last signal before a junction. * Fast Line First (FLF): Prioritize trains on the fast line over those on the local line. Busy Line First (BLF): Dispatch trains from the line with a higher volume of traffic. Once a dispatching decision is made, the signaling and interlocking systems translate it into future actions. The primary goal of generating a train rescheduling solution is to minimize knock-on delays among conflicting trains within the local area. However, dispatchers may not always find the optimal solution for the problem at hand [2]. Consequently, a series of studies have introduced advanced algorithms and decision-support systems to address train rescheduling challenges. Typically, these problems are modeled as mixed-integer linear programming (MILP) problems, allowing for the generation of optimal solutions within a reasonable computation time. However, these algorithms face computational bottlenecks when dealing with highly complex problems. As the controlled network expands, search algorithms may struggle to find promising solutions, sometimes even performing less efficiently than traditional rule-based strategies. Additionally, the search process can become extremely time-consuming, making it unsuitable for the real-time demands of dispatching systems [3]. Moreover, because train timetables are strongly interdependent, adjusting the timetable for a single train can trigger a domino effect across the entire network, which local dispatchers cannot anticipate. As a result, a solution that appears optimal for a local network may not be globally feasible. In the context of railway networks, each local area is highly self-governing and aims to solve its traffic management problems independently. However, these local issues are often interconnected with other areas. Therefore, the train rescheduling problem should be approached from a global perspective, but in a decentralized manner. This paper presents a novel multi-agent-based approach to solving the train rescheduling problem. The primary advantages of applying a multi-agent system (MAS) to railway traffic management are its inherently decentralized architecture and its ability to handle complex, large-scale problems. The proposed MAS generates real-time train rescheduling solutions by adjusting train passing sequences and times at junctions and stations, thereby minimizing knock-on delays caused by conflicts with the original timetable and ultimately improving rail service across the entire network. The key contributions of this paper are as follows:  
1. **Hierarchical Multi-Agent System for Large-Scale Networks**: We apply a hierarchical MAS to address train rescheduling challenges in large-scale railway networks. This includes detailed descriptions of the methods for network decomposition and the allocation of optimization tasks across the entire MAS. 2. **Enhancements in the Searching Algorithm**: We introduce two additional operators in the searching algorithm: **modification** and **classification**. The modification operator acts as a post-correction mechanism to ensure the feasibility of solutions under local operational constraints.