## 3 Problem Description
### Passenger Travel Path Selection  
Passengers have multiple spatial-temporal paths in the STN, usually described by the link sequence, due to the diversified train services. Figure 6 shows three exemplary paths of passengers, marked \(q_{1,6,4}\), who arrive at station 1 before the arrival of train 4 and go to station 6. The path \(p_{1}\) contains 12 links and represents taking train 4 at station 1,  
Figure 5: The space–time network design problem. Figure 6: STN of the time–distance diagram in Figure 4b. transferring to train 2 at station 4, and going to station 6. Considering the characteristic of rail transit that passengers actually choose trains rather than links, these passengers' choice elements are recorded as a path strategy. A path strategy comprises a set of train types that enable passengers to reach their destinations. If multiple train types are involved in a path strategy, passengers will transfer at the appropriate stations. Path \(p_{1}\) is an instance of the path strategy defined by \"boarding train type 2 and transferring to train type 1\". A path strategy may have multiple path instances, but not all paths will be chosen when passengers are familiar with the timetable. For example, if passengers \(q_{1,A3}\) choose the path strategy \"boarding train type 2\", they will choose path \(p_{4}\) instead of \(p_{6}\) because of the evident additional waiting time. Similarly, it is unreasonable to transfer to subsequent trains of the same type, such as \(p_{5}\). Note that this is similar to some assumptions of timetabling optimization problems without considering passenger detention (i.e., only taking the current train). In addition, path \(p_{1}\) has the same travel time as path \(p_{2}\), but a shorter in-vehicle time and longer transfer and waiting times. This means that the chosen probabilities of these two paths are not equal because of the different perceptions of waiting, transfer, and travel times [10]. Some comfort indicators have similar phenomena, such as vehicle congestion [33]. Therefore, we use non-dominated paths to describe the partial-order relationship. The definitions of the related concepts are provided below. Definition 1 (Domination): Let vectors \(\mathbf{f}_{1},\mathbf{f}_{2}\in R^{n}\), \(\mathbf{f}_{1}=(f_{11},f_{12},\ldots,f_{1n})^{T}\), \(\mathbf{f}_{2}=(f_{21},f_{22},\ldots,f_{2n})^{T}\). \(\mathbf{f}_{1}\) dominates \(\mathbf{f}_{2}\) if and only if \(\forall\ i:f_{1i}\leq f_{2i},\exists j:f_{1j}<f_{2j}\), written as \(\mathbf{f}_{1}\prec\mathbf{f}_{2}\). Definition 2 (Pareto front): Let vectors \(\mathbf{f}_{1},\mathbf{f}_{2},\ldots,\mathbf{f}_{m}\in R^{n}\), where \(\mathbf{f}_{i}=(f_{i1},f_{i2},\ldots,f_{in})^{T}\), \(i\in I\subseteq M\), and \(M=\{1,2,\ldots,m\}\). \(\mathbf{f}_{i}\) is called the Pareto front if and only if \(\exists j\in M-I:f_{jk}\leq f_{ik}\),\(\forall k\leq n\)  
Definition 3 (Path domination): Let \(P\) denote the set of all paths of an OD pair with path cost function \(\mathbf{c}(\cdot):R^{n}_{+}\to R^{m}_{+}\). Path \(p_{1}\in P\) dominates \(p_{2}\in P\) if and only if \(\mathbf{c}(p_{1})\prec\mathbf{c}(p_{2})\), written as \(p_{1}\prec p_{2}\)  
Definition 4 (Non-dominated path): Let set \(\mathcal{W}\) denote all OD pairs and \(P_{w}\) denote the set of all paths between \(w\in\mathcal{W}\) in a STN. Path \(p_{1}\in P_{w}\) is called a non-dominated path if and only if \(\exists p_{2}\in P_{w}:p_{2}\prec p_{1}\). The set of all non-dominated paths \(p_{i}\in P_{w}\) is called the non-dominated path set \(\mathcal{P}_{w}\) of OD pair \(w\in\mathcal{W}\), and \(\mathcal{P}=\cup_{w\in\mathcal{W}}\mathcal{P}_{w}\) is called the non-dominated path set of the STN. To simplify the description, the waiting time at station \(r\) and transfer time at the intermediate station \(r^{\prime}\) of passengers \(q_{rsi}\) are collectively called the passenger waiting time in this paper.