# A Network-Based Method for the EMU Train High-Level Maintenance Planning Problem
## 3 Methodology
### Time-State Network  
A time-state network is designed based on graph theory to analyze HMP. In China high speed railway, train-sets operate the timetable during the daytime and get rest or lower level maintenance during the night. Furthermore, the working time of the maintenance workshop is also during the daytime. Therefore, we constructed a time-state network by setting the night as a node, and regarded the duration of daytime as an arc that connects adjacent nodes (see Figure 3). The horizontal direction represents the elapse of time, and the vertical direction shows different states of train-sets. Figure 2: The HM cyclic graph. Directed graph \(G\) consists of the node set \(V\) and the arc set \(A\), \(G=(V,A)\). The last column denotes virtual hyper-nodes in the planning horizon. The notations, including the indices, parameters, and sets, are listed in Table 2.  
A dashed line presents the time arc \(a_{ik}\) in Figure 3. There are four kinds of time arcs that exist in the time-state network (distinguished by different color), which represent the available state, and third-level, fourth-level and fifth-level maintenance state, respectively. Then, we explain the \begin{table}
\begin{tabular}{c l} \hline \hline
**Notation** & **Description** \\ \hline _Indices_ & \\ \hline \(i,j\) & The state of the train-set: \(i\), \(j=1\), \(2\), \(3\), \(4\), denote available state, the third-, fourth- and fifth-level maintenance state, respectively \\ \(k,h\) & The ordinal number of the column (day): \(k\), \(h=1\), \(2\), \(3\), \(\ldots,T\) \\ \(e\) & The train-set: \(e\in E\) \\ \hline _Parameters_ & \\ \hline \(v_{ik}\) & The node locates in the i-th row and the k-th column: \(v_{ik}\in V\) \\ \(a\) & The arc: \(a\in A\) \\ \(a_{ik}\) & The time arc following the node \(v_{ik}\): \(a_{ik}\in A_{i}\) \\ \(a_{ij}^{k}\) & The connection arc from \(v_{ik}\) to \(v_{jk}\): \(i\
eq j\) \\ \(a_{ij}^{k}\) & The available/maintenance arc from \(v_{ik}\) to \(v_{ik}\) \\ \(w_{ik}\) & The volume value of time arc \\ \(b_{1}(a_{ik})\) & The minimum value of \(w_{ik}\) for arc \(a_{ik,k}\): \(i=2\), \(3\), \(4\) \\ \(b_{i}\) & The maximum value of \(w_{ik}\) for arc \(a_{ik}\): \(i=2\), \(3\), \(4\) \\ \(T\) & The length of planning horizon \\ \(r\) & The path on the time-state network: \(r\in R\) \\ \(t\) & The time point from the available state converted to the maintenance state \\ \(g\) & The level of maintenance \\ \(\mu\) & The length of maintenance service time \\ \hline _Sets_ & \\ \hline \(E\) & Set of train-sets \\ \(A\) & Set of all arcs \\ \(V\) & Set of all nodes \\ \(A_{i}\) & Set of time arcs: \(A_{i}\subset A\), \(i=1\), \(2\), \(3\), \(4\) \\ \(R\) & Set of all path \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Notation of indices, sets, and parameters. Figure 3: Schematic diagram of connection relationship between available and HM states for EMU. weight of these time arcs as follows. Let \(w_{ik}\) denote the number of train-sets on the \(k\)-th day and in the \(i\)-th state. To successfully undertake the transportation tasks on the \(k\)-th day, the \(w_{1,k}\) must greater than or equal to \(b_{1}(a_{1,k})\), i.e., \(w_{1,k}\geq b_{1}(a_{1,k})\). Note that the value of \(b_{1}(a_{1,k})\) is the least demand for available states, and it is variable according to travel demand on the \(k\)-th day. Let \(w_{2,k}\) denote the number of train-sets in third-level maintenance state on the \(k\)-th day. Due to the limited service capacity of the workshop, \(w_{2,k}\) has its maximum value \(b_{2}\). Similarly, \(w_{3,k}\leq b_{3}\) and \(w_{4,k}\leq b_{4}\). Note that \(b_{2}\), \(b_{3}\), \(b_{4}\) is fixed, but \(b_{1}(a_{1,k})\) is variable. The process of train-sets entering or leaving workshop are relatively stochastic in practical, so we did not take time consumption into consideration for this.