# Optimization of Multi-Day Flexible EMU Routing Plan for High-Speed Rail Networks
## 3 Solution Algorithm  
The multi-day flexible EMU routing plan for railway networks must be generated based on train timetables and connection rules. Subsequently, EMUs are assigned according to the initial train in each circulation. Given the complexity of decision variables and the abundance of constraints, directly solving the model is computationally challenging. Therefore, in this paper, we propose a heuristic decomposition algorithm based on the model structure, enabling efficient solution acquisition within a reasonable time.  
The algorithm decomposes the original problem in three main phases. Firstly, it focuses on minimizing the total connection time for daily EMU routing planning, considering intra-day connection rules. Secondly, it constructs an assignment network based on task chains, network layout, and maintenance resources. Lastly, it solves a multi-day integrated circulation plan with flexible inspection requirements and connection constraints. The detailed steps are as follows:  
**Step 1: Generation of Daily Train Service Task Chains using Gurobi**  
Each EMU is required to perform a sequence of train services on a given day, which collectively form a daily task chain. In generating these chains, the model does not consider first-level maintenance capacity constraints. Instead, it focuses exclusively on intra-day train connection constraints. This simplification is intended to ensure feasibility in later stages by avoiding infeasibility caused by the number of task chains exceeding the available storage or inspection capacity at intermediate stations or depots.  
Moreover, the inter-day continuity between task chains on day \(k\) and day \(k+1\) is not considered in this stage. The primary objective of this subproblem is to minimize the total connection time of EMUs on each day. The constraints include only same-day connection feasibility rules, excluding multi-day dependencies and maintenance requirements. The detailed procedure is illustrated in Figure 5, and we solve this subproblem using Gurobi [27]. The output of this stage provides the foundation for subsequent EMU assignment and routing decisions.  
**Step 2: Construction of EMU Assignment Network**  
Using the daily train task chains from Step 1, a bipartite network is constructed to assign rolling stock to each task chain. Each task chain is treated as a demand node with attributes such as origin, destination, operation time, and mileage, while supply nodes represent available depot and yard resources. Feasible arcs between demand and supply nodes are defined based on network layout, the initial departure station and time, and depot-station connectivity (see Figure 6).  
**Step 3: Generation of Multi-day EMU Routing Plan**  
Finally, based on the assignment network, the EMU routing plan is optimized over the entire planning horizon. The objective is to minimize total deadhead mileage, while satisfying cross-day connection continuity and inspection constraints. This final stage is modeled similarly to the mathematical formulation in Section 2, with task chains replacing individual train services as basic planning units (see Figure 7).  
Based on the above three-step decomposition, the proposed heuristic algorithm transforms the complex multi-day EMU routing optimization problem into a tractable solution framework. Through first determining feasible task chains for each day and then constructing a structured assignment network to match available EMUs with task chains, the method  
Figure 5: Daily train connection tasks.  
Figure 6: Multi-day EMU dispatching network.  
Figure 7: Multi-day EMU routing plan.  
integrates operational logic and maintenance feasibility. The final routing plan is generated through global coordination, ensuring consistency across days.