# First-Train Timetable Synchronization in Metro Networks under Origin-Destination Demand Conditions

Authors: Hetian Chai; Xiaopeng Tian; Huimin Niu
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

This paper focuses on how to synchronize network-wide timetables of first trains in an urban metro system, in which the train-connection-based route can be exactly determined for each first-train-attached origin-destination (OD) demand pair. With the help of even headway scheduling on each line, the problem is actually to adjust the departure times of first trains and connecting trains from their origin stations and the departure interval on each line. Subjected to train operation and connection constraints, a biobjective nonlinear integer programming model is formulated to minimize the total travel time of OD-dependent passenger demands and the deviation between the known and expected schedules. Then, the Nondominated Sorted Genetic Algorithm-II (NSGA-II) is adopted to solve the proposed model, and an improved technique is elaborated to reduce the alternative route choices. Finally, numerical experiments are conducted to demonstrate the effectiveness and availability of the proposed model and methods.


---

## Body

## 1. Introduction

As one of the network-wide train timetabling problems, the first train timetabling problem seeks to determine the departure times of the first trains in metro networks, to improve the connection efficiency of these first trains at transfer stations. Compared with the non-first train timetable synchronization problem, the first train timetabling problem is characterized by a longer train connection time between the first trains, which typically exceeds the maximum headway on lines. Such excessive passenger transfer waiting time can seriously decrease the travel quality of the passengers taking the first trains. It is necessary to design a high-level first-train timetable for these passengers. Furthermore, a well-designed first train synchronization timetable, which can provide high-quality transfer services to attract more passengers, is a matter of significant importance for operators.The first train timetabling problem is known to be very complicated, so the existing literature has proposed some simplistic measures to address this problem. First, transfer direction-based passenger demand, which is actually the number of passengers from the feeder line to the connecting line at transfer stations, is considered to facilitate modeling and solving [1]. It is undeniable that such a passenger demand pattern is capable of representing passenger transfer behaviors when passenger travel routes are unique. However, in large-scale metro networks, passengers typically have several alternative transfer routes from the origin stations to designation stations, which means that passengers can flexibly select the transfer direction. That is, the transfer-direction-based demand may be a rough estimate of passenger transfer because it lacks a description of passenger choice behaviors. Second, the simplistic measures are from the identification of train connections. Based on the given train timetable, a typical approach is to optimize only the train connections between the first trains, ignoring the connections from the first trains to non-first connecting trains [2]. Although a standard mixed-integer linear programming model can be established by the above simplification, the corresponding first train synchronization efficiency is bound to be affected by the simplified connections and the given train timetable.Therefore, this paper addresses passenger demand and train connection identification to improve the first train transfer efficiency. Specifically, we consider transfer passenger origin-destination (OD) demand that takes the first trains in the metro network and allows them to select flexible travel routes. Furthermore, all the connections from the first trains to the corresponding connecting trains are identified, and the variable headway on each line is considered. Thus, a biobjective optimization model is established to minimize the passenger travel times and the deviation times from the actual schedules. Meanwhile, the Nondominated Sorted Genetic Algorithm-II (NSGA-II) is designed to generate Pareto solutions for the problem under consideration.


### 1.1. Literature Review

The network-wide train timetabling problem has attracted extensive attention from the public transportation field, and the objective functions of the problem are diverse. First, much research has focused on single-objective functions for train timetable synchronization. Fleurent et al. [3] established a network flow model to reduce the deviation between the actual departure interval and the ideal interval. Cevallos and Zhao [4] presented a system-wide approach to minimize the total transfer times by shifting existing timetables. Considering heterogeneous transfer walking times, Chen et al. [5] proposed a mixed-integer quadratic programming model to maximize the number of transfer passengers for last train services on metro networks. A mixed-integer programming model was established by Chen et al. [6] to improve passenger accessibility. As for the first train timetabling problem, Guo et al. [2] proposed a first train timetable optimization model based on the importance of lines and transfer stations, which can minimize the total connection time at transfer stations coupled with the degree of importance of the station. Li et al. [7] proposed a reference-based piecewise function to maximize the satisfaction of passengers’ transfer waiting times.Second, multiple objective functions are often used to optimize the train transfer optimization problem. Chung Min Kwan and Chang [8] proposed a biobjective programming model to minimize the total passenger dissatisfaction index and total deviation index and employed the Nondominated Sorted Genetic Algorithm-II to generate Pareto solutions. Tian and Niu [9] considered a biobjective function with the maximum number of train connections and the minimum passenger waiting times for the network-wide train timetable problem. From the perspective of passengers and operators, Guo et al. [10] developed a multiobjective optimization model to determine optimal train service schedules with the maximum transfer events and the minimum transfer synchronization time. Kang et al. [11] simultaneously minimized passenger transfer waiting times, total train running times, and train energy consumption for the last train station-skipping problem. Furthermore, Nie et al. [12] established the last-shift schedule model to minimize the transfer waiting times and maximize the network connectivity. Obviously, it is more comprehensive to use multiple evaluation criteria to measure the complicated network-wide train timetabling problems. Note that, however, the studies associated with first train synchronization mainly focus on a single objective function with train connection efficiency.In the design of train timetables, passenger demand plays an important role, such as Niu and Zhou [13], Barrena et al. [14], Niu et al. [15], Tian and Niu [16], and Shang et al. [17]. Due to the inherent complexity of train synchronization, transfer-direction-based passenger demand is usually considered to optimize network-wide train timetables. Given the number of passengers between each transfer direction, Wong et al. [18] presented a mixed integer programming optimization model to minimize the interchange waiting times of all passengers for this schedule synchronization problem with nonperiodic timetables. Similar to transfer-direction-based demand, Wang et al. [19] adopted arrival-rate-based passenger demand to establish a nonlinear integer programming model for the train transfer problem. Shafahi and Khani [20] formulated a mixed integer programming model to minimize the waiting time of station-based passenger demand for the transit network scheduling problem. For the first train synchronization problem, Kang et al. [1] established an optimization model by using the transfer-direction-based demand and analyzed the connectional regulation of first trains at transfer stations on each line. Indeed, such passenger demand patterns can effectively facilitate modeling and computation, but they cannot capture the travel choice behavior of passengers.More recently, the passenger OD demand has also been applied to the network-wide train timetabling problem. For two interconnected high-speed rail lines, Niu et al. [21] proposed a nonlinear programming model based on the time-dependent OD demand to minimize passenger waiting times at stations and crowding disutility in trains. Li et al. [22] maximized the total number of passengers reaching their destinations in a network by using the OD demand. Zhou et al. [23] paid close attention to the entire travel process, including multiple transfer behaviors of passengers and loaded static OD passenger demand on the traveling path. For the last-train timetable problem, Yang et al. [24] expected to find a feasible train space-time path with accessibility for the OD passenger demand. Furthermore, Yin et al. [25] utilized the time-dependent OD demand pattern to construct a mixed-integer nonlinear programming model for the train timetabling problem with the transfer. Although the OD passenger demand has been considered for some train transfer problems, the first train timetable problem still lacks the application of the OD passenger demand.


### 1.2. Focus of This Study

To highlight the contributions of our proposed approach, Table1 provides a systematic comparison with the most relevant literature. Specifically, we collaboratively optimize the train timetabling and the passenger routing by using the OD passenger demand instead of the transfer-direction-based passenger demand. Then, a biobjective function is proposed to more comprehensive formulate this problem. Furthermore, the NSGA-II algorithm is designed to solve the proposed biobjective optimization model. Note that, similar to the existing literature, this paper ignores the train capacity constraints to simplify this problem.Table 1
Comparison between this paper and the most relevant literature.
PublicationProblem typeTrain capacityPassenger demandObjective functionPassenger travel routeAlgorithmWong et al. [18]All trainsNoTransfer-direction-based demandMinimize waiting timeNoCPLEX-based heuristicShafahi and Khani [20]All trainsNoStation-based demandMinimize waiting timeNoGAZhou et al. [23]Last trainNoStatic OD demandMaximize OD accessibilityYesCPLEXChen et al. [5]Last trainNoStation-based demandMaximize the number of transfer passengersNoCPLEXChen et al. [6]Last trainNoStatic OD demandMaximize percentage of accessible OD pairsYesGAYang et al. [24]Last trainNoTime-dependent OD demandMaximize space-time accessibilityYesLRGuo et al. [2]First trainNoTransfer-direction-based demandMinimize connection timeNoCPLEXKang et al. [1]First trainNoTransfer-direction-based demandMinimize waiting timeNoHeuristicThis paperFirst trainNoStatic OD demandMinimize travel timeMinimize schedule deviationYesNSGA-IICompared with the existing research, the main contributions of this paper are summarized as follows:(1)
We consider the transfer OD passenger demand in the first train timetabling problem. Based on this OD demand, transfer passenger travel behaviors can be easily formulated during the modeling process, which is beneficial for designing passenger-oriented train timetables.(2)
To trade off transfer passenger travel efficiency and nontransfer passenger service quality, a biobjective nonlinear programming model is then established to minimize the transfer waiting times and the deviations between the actual schedule and the expected schedule on each line. In addition, a train connection-based route is introduced to calculate the total travel time of transfer passengers.(3)
An NSGA-II with customized acceleration strategies is proposed to effectively solve large-scale instances. These strategies are able to generate promising passenger travel routes and accelerate computational times by reducing the repetitive calculation of transfer times for different OD demands.The remainder of this paper is organized as follows: the problem is described in detail in Section2. In Section 3, a mixed integer programming model is established to describe the interest in the problem. Then, in Section 4, the method of determining the effective route alternative set and the OD demand classification method are introduced, and the implementation principle of the NSGA-II algorithm is also introduced. Section 5 conducts several numerical examples with different scales, and the authors conclude this study and provide further research directions in the last section.


## 1.1. Literature Review

The network-wide train timetabling problem has attracted extensive attention from the public transportation field, and the objective functions of the problem are diverse. First, much research has focused on single-objective functions for train timetable synchronization. Fleurent et al. [3] established a network flow model to reduce the deviation between the actual departure interval and the ideal interval. Cevallos and Zhao [4] presented a system-wide approach to minimize the total transfer times by shifting existing timetables. Considering heterogeneous transfer walking times, Chen et al. [5] proposed a mixed-integer quadratic programming model to maximize the number of transfer passengers for last train services on metro networks. A mixed-integer programming model was established by Chen et al. [6] to improve passenger accessibility. As for the first train timetabling problem, Guo et al. [2] proposed a first train timetable optimization model based on the importance of lines and transfer stations, which can minimize the total connection time at transfer stations coupled with the degree of importance of the station. Li et al. [7] proposed a reference-based piecewise function to maximize the satisfaction of passengers’ transfer waiting times.Second, multiple objective functions are often used to optimize the train transfer optimization problem. Chung Min Kwan and Chang [8] proposed a biobjective programming model to minimize the total passenger dissatisfaction index and total deviation index and employed the Nondominated Sorted Genetic Algorithm-II to generate Pareto solutions. Tian and Niu [9] considered a biobjective function with the maximum number of train connections and the minimum passenger waiting times for the network-wide train timetable problem. From the perspective of passengers and operators, Guo et al. [10] developed a multiobjective optimization model to determine optimal train service schedules with the maximum transfer events and the minimum transfer synchronization time. Kang et al. [11] simultaneously minimized passenger transfer waiting times, total train running times, and train energy consumption for the last train station-skipping problem. Furthermore, Nie et al. [12] established the last-shift schedule model to minimize the transfer waiting times and maximize the network connectivity. Obviously, it is more comprehensive to use multiple evaluation criteria to measure the complicated network-wide train timetabling problems. Note that, however, the studies associated with first train synchronization mainly focus on a single objective function with train connection efficiency.In the design of train timetables, passenger demand plays an important role, such as Niu and Zhou [13], Barrena et al. [14], Niu et al. [15], Tian and Niu [16], and Shang et al. [17]. Due to the inherent complexity of train synchronization, transfer-direction-based passenger demand is usually considered to optimize network-wide train timetables. Given the number of passengers between each transfer direction, Wong et al. [18] presented a mixed integer programming optimization model to minimize the interchange waiting times of all passengers for this schedule synchronization problem with nonperiodic timetables. Similar to transfer-direction-based demand, Wang et al. [19] adopted arrival-rate-based passenger demand to establish a nonlinear integer programming model for the train transfer problem. Shafahi and Khani [20] formulated a mixed integer programming model to minimize the waiting time of station-based passenger demand for the transit network scheduling problem. For the first train synchronization problem, Kang et al. [1] established an optimization model by using the transfer-direction-based demand and analyzed the connectional regulation of first trains at transfer stations on each line. Indeed, such passenger demand patterns can effectively facilitate modeling and computation, but they cannot capture the travel choice behavior of passengers.More recently, the passenger OD demand has also been applied to the network-wide train timetabling problem. For two interconnected high-speed rail lines, Niu et al. [21] proposed a nonlinear programming model based on the time-dependent OD demand to minimize passenger waiting times at stations and crowding disutility in trains. Li et al. [22] maximized the total number of passengers reaching their destinations in a network by using the OD demand. Zhou et al. [23] paid close attention to the entire travel process, including multiple transfer behaviors of passengers and loaded static OD passenger demand on the traveling path. For the last-train timetable problem, Yang et al. [24] expected to find a feasible train space-time path with accessibility for the OD passenger demand. Furthermore, Yin et al. [25] utilized the time-dependent OD demand pattern to construct a mixed-integer nonlinear programming model for the train timetabling problem with the transfer. Although the OD passenger demand has been considered for some train transfer problems, the first train timetable problem still lacks the application of the OD passenger demand.


## 1.2. Focus of This Study

To highlight the contributions of our proposed approach, Table1 provides a systematic comparison with the most relevant literature. Specifically, we collaboratively optimize the train timetabling and the passenger routing by using the OD passenger demand instead of the transfer-direction-based passenger demand. Then, a biobjective function is proposed to more comprehensive formulate this problem. Furthermore, the NSGA-II algorithm is designed to solve the proposed biobjective optimization model. Note that, similar to the existing literature, this paper ignores the train capacity constraints to simplify this problem.Table 1
Comparison between this paper and the most relevant literature.
PublicationProblem typeTrain capacityPassenger demandObjective functionPassenger travel routeAlgorithmWong et al. [18]All trainsNoTransfer-direction-based demandMinimize waiting timeNoCPLEX-based heuristicShafahi and Khani [20]All trainsNoStation-based demandMinimize waiting timeNoGAZhou et al. [23]Last trainNoStatic OD demandMaximize OD accessibilityYesCPLEXChen et al. [5]Last trainNoStation-based demandMaximize the number of transfer passengersNoCPLEXChen et al. [6]Last trainNoStatic OD demandMaximize percentage of accessible OD pairsYesGAYang et al. [24]Last trainNoTime-dependent OD demandMaximize space-time accessibilityYesLRGuo et al. [2]First trainNoTransfer-direction-based demandMinimize connection timeNoCPLEXKang et al. [1]First trainNoTransfer-direction-based demandMinimize waiting timeNoHeuristicThis paperFirst trainNoStatic OD demandMinimize travel timeMinimize schedule deviationYesNSGA-IICompared with the existing research, the main contributions of this paper are summarized as follows:(1)
We consider the transfer OD passenger demand in the first train timetabling problem. Based on this OD demand, transfer passenger travel behaviors can be easily formulated during the modeling process, which is beneficial for designing passenger-oriented train timetables.(2)
To trade off transfer passenger travel efficiency and nontransfer passenger service quality, a biobjective nonlinear programming model is then established to minimize the transfer waiting times and the deviations between the actual schedule and the expected schedule on each line. In addition, a train connection-based route is introduced to calculate the total travel time of transfer passengers.(3)
An NSGA-II with customized acceleration strategies is proposed to effectively solve large-scale instances. These strategies are able to generate promising passenger travel routes and accelerate computational times by reducing the repetitive calculation of transfer times for different OD demands.The remainder of this paper is organized as follows: the problem is described in detail in Section2. In Section 3, a mixed integer programming model is established to describe the interest in the problem. Then, in Section 4, the method of determining the effective route alternative set and the OD demand classification method are introduced, and the implementation principle of the NSGA-II algorithm is also introduced. Section 5 conducts several numerical examples with different scales, and the authors conclude this study and provide further research directions in the last section.


## 2. Problem Statement and Passenger Travel Times

### 2.1. Problem Statement

This paper focuses on a directed urban metro network, where the set of lines is denoted byL, l∈L, the set of stations on line l is indicated as Sl, s∈Sl, and the set of trains scheduled on line l is represented by Il, i∈Il. Considering that the same-speed trains are scheduled in most metro systems, we assume that both the running times on each segment and dwelling times at each station for all trains are given.In the metro network, letK be the set of all transfer OD demands that need to take the first trains at their origin stations. For OD demand k∈K, let k=ok,dk,qk, where ok, dk, and qk represent the origin station, the destination station, and the number of passengers from ok to dk, respectively. The purpose of this paper is to generate high-quality network-wide train timetables for serving the considered transfer OD demand.To facilitate modeling, we do not consider passenger waiting times at the origin stations and instead pay more attention to the passenger travel times. Such consideration is the same as in the existing literature [2], mainly for the following reasons. Specifically, in practice, the obtained first-train timetable is usually publicly announced, especially in China, which means that the passengers taking the first trains can select a reasonable time to arrive at the origin stations according to the published first-train timetables, thereby avoiding long waiting times. Additionally, the passengers taking the first trains may face a special transfer time exceeding the maximum headway of all lines due to the uncoordinated first-train timetables [1]. Thus, these passengers are typically more concerned about their travel times than waiting times at the origin stations. Furthermore, we specify in advance an actual timetable that can provide high-level service quality for the nontransfer passengers. By minimizing the deviation time between the optimized timetable and the actual timetable, we can indirectly guarantee the service quality of the nontransfer passengers.In practice, the majority of the OD demands have multiple physical routes from the origin stations to the destination stations in metro networks. These physical routes are actually represented by a sequence of stations on different lines. In this paper, letRk denote all routes of demand k (r∈Rk), and let S¯r be all transfer stations in route r. At transfer station s∈S¯r, the corresponding feeder and connecting lines are indicated by lr,sfeeder and lr,sconnect, respectively. As shown in Figure 1, the OD demand from stations 2 to 9 has two routes, i.e., Rk = {r1, r2}, and the sets of stations of the two routes are S¯r1=3,7 and S¯r2=4,8, respectively. At transfer station 3 in route r1, we can obtain lr1,3feeder  = 1D and lr1,3connect  = 3U.Figure 1
Illustration of the metro network and passenger transfer route.To model and solve the first-train timetable synchronization problem as described previously, we integrate nonlinear modeling techniques, multiobjective optimization methods, and intelligent evolutionary algorithms. Specifically, the passenger travel times are used to measure the level-of-service of train timetables. However, the calculation of passenger travel times involves inherent nonlinear relationships caused by train connections between different lines. The nonlinear modeling technique is thus employed to represent the complicated calculation process of passenger travel times. Then, we systematically consider four kinds of constraints and two objective functions to build a biobjective first-train timetable synchronization model. Based on the multiobjective optimization method, an intelligent evolutionary algorithm (i.e., NSAG-II) is finally designed to solve the proposed biobjective optimization model. An illustrative description of the research process is shown in Figure2.Figure 2
Illustration of the research process outline.


### 2.2. Passenger Travel Times

Passenger travel times are often used as an important evaluator for passenger-oriented train timetabling problems. Generally, the travel times are composed of train running times, transfer waiting times, and transfer times. The train running times can be easily obtained according to the train operating process. The passenger transfer waiting times need to identify the effective connections between different trains at transfer stations, which is a more complicated task. Furthermore, the key to calculating travel times is determining the connection times between different trains at transfer stations.For simplicity, we adopt two common assumptions: (1) the walking times of all passengers at transfer stations are fixed [18] and (2) the train capacity is not considered so that passengers can board the first arriving train [26]. That is, a successful train connection must satisfy the requirements that the difference between the departure time of the connecting train and the arrival time of the feeder train is minimal and not less than the transfer time. As shown in Figure 3, the connecting train of train 1 on line 1D is only train 2 on line 3U at transfer station 3.Figure 3
Train-connection-based route.From the two above-given assumptions, we can obtain that a feeder train corresponds to the unique connecting train at the transfer station. Meanwhile, it has been mentioned that the transfer OD demand only takes the first train at the origin station. Thus, the passengers along a given physical route definitely have unique train trajectories when the network-wide train timetable is known. In this paper, the train trajectory is called a train-connection-based route. In terms of a single passenger, his or her travel time along the given route is actually the duration of the corresponding train-connection-based route, which is equal to the difference between the arrival time of the train serving him or her at the destination station and the departure time of the first train from the origin station. For clarity, letTAl,is and TDl,is denote the arrival and departure times of train i at station s on line l, respectively.Taking router1 in Figure 1 as an illustrative example, the given train timetables on the lines involved in route r1 are shown in Figure 2. Clearly, for the OD demand k from stations 2 to 9, Figure 2 shows that their travel route along r1 is unique. Specifically, they take the first train at station 2 on line 1D, then transfer to train 2 on line 3U at station 3, and finally transfer to train 4 on line 2D at station 7. Furthermore, the travel time is the arrival time of train 4 at station 9 on line 2D minus the departure time of train 1 at station 2 on line 1D, i.e., TA2D,49−TD1D,12.As mentioned previouly, many passengers need to transfer multiple times from their origin stations to the destination stations. To model the passenger travel process, it is necessary to record the trains involved in the passenger travel process. To this end, we introduce the symbolαr,l,s to indicate the corresponding connecting train on line l at transfer station s in route r. In fact, the identification of connecting trains at transfer stations is a recursive iterative process. For example, at transfer station 3 in Figure 2, the feeder train must be the first train on line 1D; thus, we easily obtain that train 2 on line 3U is its connecting train because this train satisfies minTD3U,23−TA1D,13|TD3U,23−TA1D,13≥t1D,3U3,2∈I3U. Furthermore, at the next transfer station 7, train 2 on line 3U can be used as the feeder train, so its connecting train (i.e., train 4 on line 2D) can be recursively obtained by the same method. By analogy, we can identify the associated trains on the route. Thus, the symbol αr,l,s can be represented as follows:(1)αr,l,s=argmini∈IlTDl,is−TAl′,αr,l′,s−s|TDl,is−TAl′,αr,l′,s−s≥tl′,ls,l′=lr,sfeederl=lr,sconnect,s∈S¯r,r∈Rk,where tl′,ls is the fixed transfer time from lines l′ to l at transfer station s and αr,l′,s− is the connecting train at the previous transfer station (denoted by s−) of station s on line l′ in route r. Furthermore, the passenger travel time of OD demand k along route r, denoted by Tkr, can be easily formulated as follows:(2)Tkr=qk⋅TAl,αr,l,r+dk−TDl′,1okl=lr,r+connect,l′=lr,r−feeder,r∈Rk,k∈K.where r− and r+ are the first and last transfer stations in route r, respectively.From the above-given analysis, it can be seen that the calculation of passenger travel time is a very complicated process, which involves the passenger in-train travel times and the transfer waiting times. The passenger in-train travel times depend utterly on the train running time on each segment. In the metro network, though the train running time is fixed, the passenger in-train travel times of different travel routes are distinguishable. Also, the passenger transfer waiting times can be determined by the corresponding train connections between the feeder trains and the connecting trains. To exactly calculate the passenger travel time, the passenger route selection and the train connection identification must be combined. Note that, such a combination greatly increases the complexity of this problem so that we need to explore a very large solution space for finding the optimal solution.


## 2.1. Problem Statement

This paper focuses on a directed urban metro network, where the set of lines is denoted byL, l∈L, the set of stations on line l is indicated as Sl, s∈Sl, and the set of trains scheduled on line l is represented by Il, i∈Il. Considering that the same-speed trains are scheduled in most metro systems, we assume that both the running times on each segment and dwelling times at each station for all trains are given.In the metro network, letK be the set of all transfer OD demands that need to take the first trains at their origin stations. For OD demand k∈K, let k=ok,dk,qk, where ok, dk, and qk represent the origin station, the destination station, and the number of passengers from ok to dk, respectively. The purpose of this paper is to generate high-quality network-wide train timetables for serving the considered transfer OD demand.To facilitate modeling, we do not consider passenger waiting times at the origin stations and instead pay more attention to the passenger travel times. Such consideration is the same as in the existing literature [2], mainly for the following reasons. Specifically, in practice, the obtained first-train timetable is usually publicly announced, especially in China, which means that the passengers taking the first trains can select a reasonable time to arrive at the origin stations according to the published first-train timetables, thereby avoiding long waiting times. Additionally, the passengers taking the first trains may face a special transfer time exceeding the maximum headway of all lines due to the uncoordinated first-train timetables [1]. Thus, these passengers are typically more concerned about their travel times than waiting times at the origin stations. Furthermore, we specify in advance an actual timetable that can provide high-level service quality for the nontransfer passengers. By minimizing the deviation time between the optimized timetable and the actual timetable, we can indirectly guarantee the service quality of the nontransfer passengers.In practice, the majority of the OD demands have multiple physical routes from the origin stations to the destination stations in metro networks. These physical routes are actually represented by a sequence of stations on different lines. In this paper, letRk denote all routes of demand k (r∈Rk), and let S¯r be all transfer stations in route r. At transfer station s∈S¯r, the corresponding feeder and connecting lines are indicated by lr,sfeeder and lr,sconnect, respectively. As shown in Figure 1, the OD demand from stations 2 to 9 has two routes, i.e., Rk = {r1, r2}, and the sets of stations of the two routes are S¯r1=3,7 and S¯r2=4,8, respectively. At transfer station 3 in route r1, we can obtain lr1,3feeder  = 1D and lr1,3connect  = 3U.Figure 1
Illustration of the metro network and passenger transfer route.To model and solve the first-train timetable synchronization problem as described previously, we integrate nonlinear modeling techniques, multiobjective optimization methods, and intelligent evolutionary algorithms. Specifically, the passenger travel times are used to measure the level-of-service of train timetables. However, the calculation of passenger travel times involves inherent nonlinear relationships caused by train connections between different lines. The nonlinear modeling technique is thus employed to represent the complicated calculation process of passenger travel times. Then, we systematically consider four kinds of constraints and two objective functions to build a biobjective first-train timetable synchronization model. Based on the multiobjective optimization method, an intelligent evolutionary algorithm (i.e., NSAG-II) is finally designed to solve the proposed biobjective optimization model. An illustrative description of the research process is shown in Figure2.Figure 2
Illustration of the research process outline.


## 2.2. Passenger Travel Times

Passenger travel times are often used as an important evaluator for passenger-oriented train timetabling problems. Generally, the travel times are composed of train running times, transfer waiting times, and transfer times. The train running times can be easily obtained according to the train operating process. The passenger transfer waiting times need to identify the effective connections between different trains at transfer stations, which is a more complicated task. Furthermore, the key to calculating travel times is determining the connection times between different trains at transfer stations.For simplicity, we adopt two common assumptions: (1) the walking times of all passengers at transfer stations are fixed [18] and (2) the train capacity is not considered so that passengers can board the first arriving train [26]. That is, a successful train connection must satisfy the requirements that the difference between the departure time of the connecting train and the arrival time of the feeder train is minimal and not less than the transfer time. As shown in Figure 3, the connecting train of train 1 on line 1D is only train 2 on line 3U at transfer station 3.Figure 3
Train-connection-based route.From the two above-given assumptions, we can obtain that a feeder train corresponds to the unique connecting train at the transfer station. Meanwhile, it has been mentioned that the transfer OD demand only takes the first train at the origin station. Thus, the passengers along a given physical route definitely have unique train trajectories when the network-wide train timetable is known. In this paper, the train trajectory is called a train-connection-based route. In terms of a single passenger, his or her travel time along the given route is actually the duration of the corresponding train-connection-based route, which is equal to the difference between the arrival time of the train serving him or her at the destination station and the departure time of the first train from the origin station. For clarity, letTAl,is and TDl,is denote the arrival and departure times of train i at station s on line l, respectively.Taking router1 in Figure 1 as an illustrative example, the given train timetables on the lines involved in route r1 are shown in Figure 2. Clearly, for the OD demand k from stations 2 to 9, Figure 2 shows that their travel route along r1 is unique. Specifically, they take the first train at station 2 on line 1D, then transfer to train 2 on line 3U at station 3, and finally transfer to train 4 on line 2D at station 7. Furthermore, the travel time is the arrival time of train 4 at station 9 on line 2D minus the departure time of train 1 at station 2 on line 1D, i.e., TA2D,49−TD1D,12.As mentioned previouly, many passengers need to transfer multiple times from their origin stations to the destination stations. To model the passenger travel process, it is necessary to record the trains involved in the passenger travel process. To this end, we introduce the symbolαr,l,s to indicate the corresponding connecting train on line l at transfer station s in route r. In fact, the identification of connecting trains at transfer stations is a recursive iterative process. For example, at transfer station 3 in Figure 2, the feeder train must be the first train on line 1D; thus, we easily obtain that train 2 on line 3U is its connecting train because this train satisfies minTD3U,23−TA1D,13|TD3U,23−TA1D,13≥t1D,3U3,2∈I3U. Furthermore, at the next transfer station 7, train 2 on line 3U can be used as the feeder train, so its connecting train (i.e., train 4 on line 2D) can be recursively obtained by the same method. By analogy, we can identify the associated trains on the route. Thus, the symbol αr,l,s can be represented as follows:(1)αr,l,s=argmini∈IlTDl,is−TAl′,αr,l′,s−s|TDl,is−TAl′,αr,l′,s−s≥tl′,ls,l′=lr,sfeederl=lr,sconnect,s∈S¯r,r∈Rk,where tl′,ls is the fixed transfer time from lines l′ to l at transfer station s and αr,l′,s− is the connecting train at the previous transfer station (denoted by s−) of station s on line l′ in route r. Furthermore, the passenger travel time of OD demand k along route r, denoted by Tkr, can be easily formulated as follows:(2)Tkr=qk⋅TAl,αr,l,r+dk−TDl′,1okl=lr,r+connect,l′=lr,r−feeder,r∈Rk,k∈K.where r− and r+ are the first and last transfer stations in route r, respectively.From the above-given analysis, it can be seen that the calculation of passenger travel time is a very complicated process, which involves the passenger in-train travel times and the transfer waiting times. The passenger in-train travel times depend utterly on the train running time on each segment. In the metro network, though the train running time is fixed, the passenger in-train travel times of different travel routes are distinguishable. Also, the passenger transfer waiting times can be determined by the corresponding train connections between the feeder trains and the connecting trains. To exactly calculate the passenger travel time, the passenger route selection and the train connection identification must be combined. Note that, such a combination greatly increases the complexity of this problem so that we need to explore a very large solution space for finding the optimal solution.


## 3. First-Train Timetable Synchronization Model

### 3.1. Notations

In this study, we introduce the following two types of decision variables:TDl,1sl: departure time of the first train on line l at its starting station s(l)Hl: headway of two adjacent trains on the line lFor the convenience of readers, the notations used in the formulation of our problem are listed in Table2.Table 2
Sets, indices, parameters, and variables.
SetsDefinitionLSet of lines in the urban rail transit networkSlSet of stations on linelIlSet of trains scheduled on linelKSet of OD demand in the urban rail transit networkRkSet of transfer routes of OD demandkS¯rSet of transfer stations in routerIndicesl,l′Index of lines,l,l′∈LiIndex of trains,i∈Il,l∈LsIndex of stations,s∈Sl,l∈LkIndex of OD demand,k ∈ KrIndex of transfer route of OD demandk, r∈Rk,k∈KParameterss(l)Starting station on linele(l)Terminal station on linelokOrigin station of OD demandkdkDestination station of OD demandkqkNumber of passengers for OD demandkr−The first transfer station in router of OD demand kr+The last transfer station in router of OD demand klr,sfeederFeeder line at stations in route rlr,sconnectConnecting line at stations in route rtlearlyEarliest departure time of the first train from the starting station onlineltllateLatest departure time of the first train from the starting station onlinelhlmaxMaximum departure interval of two adjacent trains on linelhlminMinimum departure interval of two adjacent trains on lineltl,srunTrain running time from stationss − 1 to s on line ltl,sdwellTrain dwell time at stations on line ltl′,lsTransfer time from linesl′ to l at transfer station sVariablesTAl,isArrival time of traini at station s on line lTDl,isDeparture time of traini at station s on line lαr,l,sConnecting train on linel at transfer station s in route rTkrTravel time of router of OD demand kTkMinimum travel time of OD demandk


### 3.2. Constraints

#### 3.2.1. Headway Constraints

(3)Hl=TDl,i+1sl−TDl,isli,i+1∈Il,l∈L,(4)hlmin≤Hl≤hlmaxl∈L.Constraint (3) can ensure that the time interval of two adjacent trains is equal to headway Hl. That is, using the decision variables TDl,1sl and Hl, we can easily obtain the departure times of nonfirst trains at the corresponding starting stations. Constraint (4) requires that the decision variable Hl satisfy the minimum and maximum restrictions [27].


#### 3.2.2. Train Operation Constraints

(5)TAl,is=TDl,is−1+tl,srun,s∈Sl\sl,i∈Il,l∈L,(6)TDl,is=TAl,is+tl,sdwell,s∈Sl\sl,el,i∈Il,l∈L.These constraints can determine the arrival and departure times of all trains at each station according to the given running times and dwell times.


#### 3.2.3. First Train Departure Time Constraints

(7)tlearly≤TDl,1sl≤tllatel∈L.In a metro network, the departure time of the first train at the starting station on each line is required to satisfy the earliest and latest departure times. In this paper, the earliest departure times are equal to the prespecified starting operation times, which can be comprehensively determined by many factors, such as passenger demand, maintenance constraints, and station management.


#### 3.2.4. Passenger Travel Time Constraints

(8)Tk=minr∈RkTkr.Here,Tk denotes the shortest travel time of demand k. As mentioned previously, OD demand k in the metro network usually corresponds to several travel routes Rk. Thus, the travel time of demand k is equal to the minimum travel time in Rk, namely, minr∈RkTkr. Note that, the travel time of each route Tkr can be determined by (2), which is associated with the decision variables.


### 3.3. Objective Functions

In this paper, the optimization objectives of the first train timetable synchronization problem are considered from the following two aspects.First, the minimum total transfer passenger travel time is regarded as one optimization objective. As mentioned previously, any OD demandk corresponds to several travel routes. In general, passengers expect to select the shortest route for their journey. We use Tk to denote the shortest travel time of demand k, i.e., Tk=minp∈PkTkp. Therefore, the minimum total transfer passenger travel time, denoted by Z1, can be represented as follows:(9)minZ1=∑k∈KTk.Second, the minimum deviation between the actual schedule and the optimized schedule, denoted byZ2, is used as the other objective function. Similar to Kwan et al. [8], this paper introduces the actual schedule to guarantee the service level for nontransfer passengers. Let H¯l indicate the actual headway of trains on line l, and D¯l indicate the actual departure time of the first train at the origin station on line l. Furthermore, it is required that the optimized schedule is as close as possible to the actual schedule. The corresponding objective function can be written as follows:(10)minZ2=∑l∈LTDl,1sl−D¯l+Hl−H¯l.


### 3.4. Model Analysis

Furthermore, the above first-train timetable synchronization model (FTSM) can be summarized as follows:Model FTSM. Objective function (9) and (10) Constraints (1)–(8)The above-given model FTSM is a typical biobjective nonlinear optimization model. Between the two objective functions (9) and (10), there exists a conflicting relationship that the deviation times may not be optimal if the passenger travel times are minimized and vice versa. Such a conflicting relationship easily causes severe solving difficulty to simultaneously minimize these two objectives. Additionally, the objective function (10) with the absolute value and the constraints (1), (2), and (8) are nonlinear, which further increases the complexity of the model FTSM.For the multiobjective optimization problem, nondominated sorting is a necessary step in the solution process. To represent the complexity of nondominated sorting in our proposed model, letNDl denote the set of departure times of the first train at the starting station on line l, NDl=tlearly,tlearly+1,…,tllate, and NHl indicate the set of accessible headways on line l, NHl=hlmin,hlmin+1,…,hlmax. Furthermore, the number of feasible solutions, denoted by N, for the proposed model can be obtained, namely, N=∏l=1LNDl⋅NHl. Similar to the discussion of Wu et al. [28], the computational complexity of nondominated sorting in our problem can be expressed as O(2N2). For the rail network with 4 lines shown in Figure 1, when assuming NDl=5 and NHl=5 for all lines, the number of feasible solutions is N = 390,625, and then the computational complexity of nondominated sorting is 305,175,781,250. Obviously, the computational complexity of nondominated sorting greatly increases the difficulty of solving this problem.Based on the above analysis, the considered problem is very complex. Actually, the train synchronization optimization problem is known to be NP-hard [18]. It is difficult to find the optimal solutions in large-scale and complex instances. Thus, using multiobjective evolutionary algorithms (e.g., NSGA-II) is a good choice to overcome the difficulties mentioned previously.


## 3.1. Notations

In this study, we introduce the following two types of decision variables:TDl,1sl: departure time of the first train on line l at its starting station s(l)Hl: headway of two adjacent trains on the line lFor the convenience of readers, the notations used in the formulation of our problem are listed in Table2.Table 2
Sets, indices, parameters, and variables.
SetsDefinitionLSet of lines in the urban rail transit networkSlSet of stations on linelIlSet of trains scheduled on linelKSet of OD demand in the urban rail transit networkRkSet of transfer routes of OD demandkS¯rSet of transfer stations in routerIndicesl,l′Index of lines,l,l′∈LiIndex of trains,i∈Il,l∈LsIndex of stations,s∈Sl,l∈LkIndex of OD demand,k ∈ KrIndex of transfer route of OD demandk, r∈Rk,k∈KParameterss(l)Starting station on linele(l)Terminal station on linelokOrigin station of OD demandkdkDestination station of OD demandkqkNumber of passengers for OD demandkr−The first transfer station in router of OD demand kr+The last transfer station in router of OD demand klr,sfeederFeeder line at stations in route rlr,sconnectConnecting line at stations in route rtlearlyEarliest departure time of the first train from the starting station onlineltllateLatest departure time of the first train from the starting station onlinelhlmaxMaximum departure interval of two adjacent trains on linelhlminMinimum departure interval of two adjacent trains on lineltl,srunTrain running time from stationss − 1 to s on line ltl,sdwellTrain dwell time at stations on line ltl′,lsTransfer time from linesl′ to l at transfer station sVariablesTAl,isArrival time of traini at station s on line lTDl,isDeparture time of traini at station s on line lαr,l,sConnecting train on linel at transfer station s in route rTkrTravel time of router of OD demand kTkMinimum travel time of OD demandk


## 3.2. Constraints

### 3.2.1. Headway Constraints

(3)Hl=TDl,i+1sl−TDl,isli,i+1∈Il,l∈L,(4)hlmin≤Hl≤hlmaxl∈L.Constraint (3) can ensure that the time interval of two adjacent trains is equal to headway Hl. That is, using the decision variables TDl,1sl and Hl, we can easily obtain the departure times of nonfirst trains at the corresponding starting stations. Constraint (4) requires that the decision variable Hl satisfy the minimum and maximum restrictions [27].


### 3.2.2. Train Operation Constraints

(5)TAl,is=TDl,is−1+tl,srun,s∈Sl\sl,i∈Il,l∈L,(6)TDl,is=TAl,is+tl,sdwell,s∈Sl\sl,el,i∈Il,l∈L.These constraints can determine the arrival and departure times of all trains at each station according to the given running times and dwell times.


### 3.2.3. First Train Departure Time Constraints

(7)tlearly≤TDl,1sl≤tllatel∈L.In a metro network, the departure time of the first train at the starting station on each line is required to satisfy the earliest and latest departure times. In this paper, the earliest departure times are equal to the prespecified starting operation times, which can be comprehensively determined by many factors, such as passenger demand, maintenance constraints, and station management.


### 3.2.4. Passenger Travel Time Constraints

(8)Tk=minr∈RkTkr.Here,Tk denotes the shortest travel time of demand k. As mentioned previously, OD demand k in the metro network usually corresponds to several travel routes Rk. Thus, the travel time of demand k is equal to the minimum travel time in Rk, namely, minr∈RkTkr. Note that, the travel time of each route Tkr can be determined by (2), which is associated with the decision variables.


## 3.2.1. Headway Constraints

(3)Hl=TDl,i+1sl−TDl,isli,i+1∈Il,l∈L,(4)hlmin≤Hl≤hlmaxl∈L.Constraint (3) can ensure that the time interval of two adjacent trains is equal to headway Hl. That is, using the decision variables TDl,1sl and Hl, we can easily obtain the departure times of nonfirst trains at the corresponding starting stations. Constraint (4) requires that the decision variable Hl satisfy the minimum and maximum restrictions [27].


## 3.2.2. Train Operation Constraints

(5)TAl,is=TDl,is−1+tl,srun,s∈Sl\sl,i∈Il,l∈L,(6)TDl,is=TAl,is+tl,sdwell,s∈Sl\sl,el,i∈Il,l∈L.These constraints can determine the arrival and departure times of all trains at each station according to the given running times and dwell times.


## 3.2.3. First Train Departure Time Constraints

(7)tlearly≤TDl,1sl≤tllatel∈L.In a metro network, the departure time of the first train at the starting station on each line is required to satisfy the earliest and latest departure times. In this paper, the earliest departure times are equal to the prespecified starting operation times, which can be comprehensively determined by many factors, such as passenger demand, maintenance constraints, and station management.


## 3.2.4. Passenger Travel Time Constraints

(8)Tk=minr∈RkTkr.Here,Tk denotes the shortest travel time of demand k. As mentioned previously, OD demand k in the metro network usually corresponds to several travel routes Rk. Thus, the travel time of demand k is equal to the minimum travel time in Rk, namely, minr∈RkTkr. Note that, the travel time of each route Tkr can be determined by (2), which is associated with the decision variables.


## 3.3. Objective Functions

In this paper, the optimization objectives of the first train timetable synchronization problem are considered from the following two aspects.First, the minimum total transfer passenger travel time is regarded as one optimization objective. As mentioned previously, any OD demandk corresponds to several travel routes. In general, passengers expect to select the shortest route for their journey. We use Tk to denote the shortest travel time of demand k, i.e., Tk=minp∈PkTkp. Therefore, the minimum total transfer passenger travel time, denoted by Z1, can be represented as follows:(9)minZ1=∑k∈KTk.Second, the minimum deviation between the actual schedule and the optimized schedule, denoted byZ2, is used as the other objective function. Similar to Kwan et al. [8], this paper introduces the actual schedule to guarantee the service level for nontransfer passengers. Let H¯l indicate the actual headway of trains on line l, and D¯l indicate the actual departure time of the first train at the origin station on line l. Furthermore, it is required that the optimized schedule is as close as possible to the actual schedule. The corresponding objective function can be written as follows:(10)minZ2=∑l∈LTDl,1sl−D¯l+Hl−H¯l.


## 3.4. Model Analysis

Furthermore, the above first-train timetable synchronization model (FTSM) can be summarized as follows:Model FTSM. Objective function (9) and (10) Constraints (1)–(8)The above-given model FTSM is a typical biobjective nonlinear optimization model. Between the two objective functions (9) and (10), there exists a conflicting relationship that the deviation times may not be optimal if the passenger travel times are minimized and vice versa. Such a conflicting relationship easily causes severe solving difficulty to simultaneously minimize these two objectives. Additionally, the objective function (10) with the absolute value and the constraints (1), (2), and (8) are nonlinear, which further increases the complexity of the model FTSM.For the multiobjective optimization problem, nondominated sorting is a necessary step in the solution process. To represent the complexity of nondominated sorting in our proposed model, letNDl denote the set of departure times of the first train at the starting station on line l, NDl=tlearly,tlearly+1,…,tllate, and NHl indicate the set of accessible headways on line l, NHl=hlmin,hlmin+1,…,hlmax. Furthermore, the number of feasible solutions, denoted by N, for the proposed model can be obtained, namely, N=∏l=1LNDl⋅NHl. Similar to the discussion of Wu et al. [28], the computational complexity of nondominated sorting in our problem can be expressed as O(2N2). For the rail network with 4 lines shown in Figure 1, when assuming NDl=5 and NHl=5 for all lines, the number of feasible solutions is N = 390,625, and then the computational complexity of nondominated sorting is 305,175,781,250. Obviously, the computational complexity of nondominated sorting greatly increases the difficulty of solving this problem.Based on the above analysis, the considered problem is very complex. Actually, the train synchronization optimization problem is known to be NP-hard [18]. It is difficult to find the optimal solutions in large-scale and complex instances. Thus, using multiobjective evolutionary algorithms (e.g., NSGA-II) is a good choice to overcome the difficulties mentioned previously.


## 4. Solution Algorithm

### 4.1. Algorithm Framework

For the above biobjective optimization model, we employ the NSGA-II to generate its Pareto solutions. During the solution process, the calculation of objective functionZ1 (i.e., minimizing the total travel time) is more complicated. Specifically, we need to search all the routes of each OD demand and calculate the corresponding travel times. However, in large-scale urban rail networks, there are thousands of OD demands, and each OD demand has a large number of routes. Obviously, the calculation of the travel times in the objective function is a very time-consuming process. Therefore, a preprocessing method (see Section 4.2) is embedded in the NSGA-II to speed up the travel time calculation.Furthermore, the overall algorithm framework is shown in Figure4. First, we need to input the associated information, such as the network topology, OD demand, actual schedule, and algorithm parameters, in the initialization stage. Second, we implement the preprocessing method and randomly generate several feasible solutions to activate the NSGA-II algorithm. Then, the key steps and basic genetic operations of the NSGA-II are executed. Finally, a new population is generated, and the corresponding objective value of each chromosome can be rapidly calculated by using the preprocessing method.Figure 4
Algorithm framework.


### 4.2. Preprocessing Method for Accelerating the Travel Time Calculation

As mentioned previously, each OD demand corresponds to numerous physical routes in large-scale metro networks. In practice, many of these routes may be unfavorable for passenger travel because of their longer travel times [29]. To save computational time, we select some promising routes instead of all routes to calculate the objective function. Specifically, according to the departure time windows of the first trains at the starting stations and the actual schedule of each line, we estimate the minimum and maximum travel times of each physical route using the enumerate method. Then, given any two routes r and r', we will take route r as the promising route if the maximum travel of route r is less than the minimum travel time of route r'.We continue to take the small-scale metro network shown in Figure1 as an example. The running time on each segment is shown in Figure 5. The transfer times at all transfer stations are set as 3 min, the dwelling times of all trains at each station are 1 min, and the actual headway of each line is 7 min. Furthermore, the departure time windows of lines 1D, 2D, 3U, and 4U are [5:50, 6:10], [5:55, 6:15], [5:55, 6:15], and [6:00, 6:20], respectively. For the OD demand from stations 1 to 10 in this network, there are two routes, i.e., r1 = (1 ⟶ 2 ⟶ 3 ⟶ 7 ⟶ 8 ⟶ 9 ⟶ 10) and r2 = (1 ⟶ 2 ⟶ 3 ⟶ 4 ⟶ 8 ⟶ 9 ⟶ 10). Using the enumeration method, we estimate the minimum and maximum travel times of the two routes, as shown in Table 3. Obviously, since the maximum travel time of route r1 is less than that of route r2, we select route r1 as the promising route.Figure 5
Illustration of the running time on each segment.Table 3
Feasible route of OD demand from stations 1 to 10.
Departure times and travel timeRouter1Router2Minimum caseMaximum caseMinimum caseMaximum caseDeparture time of the first train at thestarting station on each line1D5:505:505:505:502D5:565:595:556:003U5:576:15——4U——6:006:06Travel time33576072In addition, we mentioned previously that the key to the travel time calculation is to determine the train connection time at transfer stations. In practice, the routes of many OD demands have common transfer directions. That is, the travel times of these routes include the same train connection times. The OD demands (1, 9), (2, 9), (1, 10), and (2, 10) shown in Figure4 can complete their journeys along route r1 (i.e., 1 ⟶ 2 ⟶ 3 ⟶ 7 ⟶ 8 ⟶ 9 ⟶ 10). Obviously, these OD demands have the same train connections at transfer stations 3 and 7. Thus, it is necessary to avoid repeatedly calculating train connection times to accelerate the computational time. To this end, we first determine the train connection times of each first train at transfer stations from the given network-wide timetables and then save the values of these train connection times to a data pool. Subsequently, the travel time calculation of each OD demand directly uses the associated connection times from the data pool.


### 4.3. NSGA-II

In order to clearly describe the NSGA-II algorithm, letpop_size denotes the population size, Gen_ max indicates the maximum number of iterations, and l_num denotes the number of lines in the network. An integer coding chromosome with a length of 2∗l_num is employed in the genetic operation. The first l_num genes express the departure times of the first trains on each line, and the last l_num genes indicate the headways on each line.Figure6 uses a chromosome with 8 genes to denote the corresponding solution to the problem illustrated in Figure 1. Specifically, the first four genes represent the departure times of the first trains on four lines, and the remaining genes denote the headways on all lines. Furthermore, if we assume that the starting timestamp of the study period is 6:00, then the departure times of the first trains on lines lD, 2D, 3U, and 4U are 6:10, 6:15, 6:21, and 6:08, respectively; and the corresponding headways are 8 min, 7 min, 6 min, and 4 min on the four lines, respectively.Figure 6
Chromosome structure for four lines.The crossover and mutation operations in this paper are similar to Li et al. [30]. In the crossover operation, two crossover points are randomly generated in the range of [1, l_num] and [l_num +  1, 2∗l_num], respectively. In addition, the crossover operation is performed with the given crossover probability. In the mutation process, two feasible values are randomly generated for the departure times and headways, respectively. Likewise, if the randomly generated floating-point number is less than the mutation probability, the mutation operation is conducted.To calculate the crowding distance of different objectives, the following equation is established:(11)Dwi=fwi+1−fwi−1/fwmax−fwmin.Here,fwmax and fwmin represent the maximum and minimum values of the wth objective function at this level, respectively, and fwi+1 and fwi−1 represent the wth objective function values corresponding to the i + 1th and i − 1th individuals at this level, respectively.In the process of generating a new parent population, individuals with higher levels are selected from the combined population to enter the new parent population. If the total number of individuals in the same level exceeds the population size of the new parent population, the individuals with a large crowding distance in the level are selected to enter until the number of individuals reaches the population size. The detailed procedure is represented in Algorithm 1.Algorithm 1: NSGA-II.
Step 1: (Initialization)Step 1.1: Input the number and index of the lines in the network and the number and index of the intermediate stations and transfer stations on each line;Step 1.2: Input OD demand setK and promising routes;Step 1.3: Input the actual schedule of each line in the network and other parameters;Step 1.4: Input algorithm parameters, such as the population sizepop_size, maximum number of iterations Gen_max, crossover probability, and mutation probability;Step 2: (Initial population)Fori = 1 to pop_sizedoGeneratel_num departure times of first trains and headways of each individual randomly;Endfor//iGenerate the parent population;Gen = 1;Step 3: (Sorting)Step 3.1:Forj = 1 to pop_sizedoCalculate the nondominated sorting rank of each individual;Endfor//jStep 3.2:Calculate the crowded distance of each individual in the same rank;Step 4: (Genetic operation)According to the binary tournament selection rules,pop_size/2 individuals are selected from the parent population and the pop_size/2 individuals are genetically operated according to the randomly generated crossover probability and mutation probability until other pop_size/2 individuals are generated;Step 5: (Offspring population)Thesepop_size individuals generated in Step 4 compose the offspring population;Step 6: (Combined population)The parent population generated in Step 7 (ifGen = 1, generated in Step 2) and offspring population generated in Step 5 compose the combined population (2∗pop_size);Step 7: (New population)Calculate the nondominated sorting rank of each individual in the combined population and calculate the crowded distance of each individual in the same rank;Selectpop_size new individuals from the combined population to compose the new parent population;Step 8: (Solution)IfGen < Gen_max, thenGo to step 4;ElseOutput final solutions, such as the Pareto front, synchronized timetable, and train connection sequence.Endif


## 4.1. Algorithm Framework

For the above biobjective optimization model, we employ the NSGA-II to generate its Pareto solutions. During the solution process, the calculation of objective functionZ1 (i.e., minimizing the total travel time) is more complicated. Specifically, we need to search all the routes of each OD demand and calculate the corresponding travel times. However, in large-scale urban rail networks, there are thousands of OD demands, and each OD demand has a large number of routes. Obviously, the calculation of the travel times in the objective function is a very time-consuming process. Therefore, a preprocessing method (see Section 4.2) is embedded in the NSGA-II to speed up the travel time calculation.Furthermore, the overall algorithm framework is shown in Figure4. First, we need to input the associated information, such as the network topology, OD demand, actual schedule, and algorithm parameters, in the initialization stage. Second, we implement the preprocessing method and randomly generate several feasible solutions to activate the NSGA-II algorithm. Then, the key steps and basic genetic operations of the NSGA-II are executed. Finally, a new population is generated, and the corresponding objective value of each chromosome can be rapidly calculated by using the preprocessing method.Figure 4
Algorithm framework.


## 4.2. Preprocessing Method for Accelerating the Travel Time Calculation

As mentioned previously, each OD demand corresponds to numerous physical routes in large-scale metro networks. In practice, many of these routes may be unfavorable for passenger travel because of their longer travel times [29]. To save computational time, we select some promising routes instead of all routes to calculate the objective function. Specifically, according to the departure time windows of the first trains at the starting stations and the actual schedule of each line, we estimate the minimum and maximum travel times of each physical route using the enumerate method. Then, given any two routes r and r', we will take route r as the promising route if the maximum travel of route r is less than the minimum travel time of route r'.We continue to take the small-scale metro network shown in Figure1 as an example. The running time on each segment is shown in Figure 5. The transfer times at all transfer stations are set as 3 min, the dwelling times of all trains at each station are 1 min, and the actual headway of each line is 7 min. Furthermore, the departure time windows of lines 1D, 2D, 3U, and 4U are [5:50, 6:10], [5:55, 6:15], [5:55, 6:15], and [6:00, 6:20], respectively. For the OD demand from stations 1 to 10 in this network, there are two routes, i.e., r1 = (1 ⟶ 2 ⟶ 3 ⟶ 7 ⟶ 8 ⟶ 9 ⟶ 10) and r2 = (1 ⟶ 2 ⟶ 3 ⟶ 4 ⟶ 8 ⟶ 9 ⟶ 10). Using the enumeration method, we estimate the minimum and maximum travel times of the two routes, as shown in Table 3. Obviously, since the maximum travel time of route r1 is less than that of route r2, we select route r1 as the promising route.Figure 5
Illustration of the running time on each segment.Table 3
Feasible route of OD demand from stations 1 to 10.
Departure times and travel timeRouter1Router2Minimum caseMaximum caseMinimum caseMaximum caseDeparture time of the first train at thestarting station on each line1D5:505:505:505:502D5:565:595:556:003U5:576:15——4U——6:006:06Travel time33576072In addition, we mentioned previously that the key to the travel time calculation is to determine the train connection time at transfer stations. In practice, the routes of many OD demands have common transfer directions. That is, the travel times of these routes include the same train connection times. The OD demands (1, 9), (2, 9), (1, 10), and (2, 10) shown in Figure4 can complete their journeys along route r1 (i.e., 1 ⟶ 2 ⟶ 3 ⟶ 7 ⟶ 8 ⟶ 9 ⟶ 10). Obviously, these OD demands have the same train connections at transfer stations 3 and 7. Thus, it is necessary to avoid repeatedly calculating train connection times to accelerate the computational time. To this end, we first determine the train connection times of each first train at transfer stations from the given network-wide timetables and then save the values of these train connection times to a data pool. Subsequently, the travel time calculation of each OD demand directly uses the associated connection times from the data pool.


## 4.3. NSGA-II

In order to clearly describe the NSGA-II algorithm, letpop_size denotes the population size, Gen_ max indicates the maximum number of iterations, and l_num denotes the number of lines in the network. An integer coding chromosome with a length of 2∗l_num is employed in the genetic operation. The first l_num genes express the departure times of the first trains on each line, and the last l_num genes indicate the headways on each line.Figure6 uses a chromosome with 8 genes to denote the corresponding solution to the problem illustrated in Figure 1. Specifically, the first four genes represent the departure times of the first trains on four lines, and the remaining genes denote the headways on all lines. Furthermore, if we assume that the starting timestamp of the study period is 6:00, then the departure times of the first trains on lines lD, 2D, 3U, and 4U are 6:10, 6:15, 6:21, and 6:08, respectively; and the corresponding headways are 8 min, 7 min, 6 min, and 4 min on the four lines, respectively.Figure 6
Chromosome structure for four lines.The crossover and mutation operations in this paper are similar to Li et al. [30]. In the crossover operation, two crossover points are randomly generated in the range of [1, l_num] and [l_num +  1, 2∗l_num], respectively. In addition, the crossover operation is performed with the given crossover probability. In the mutation process, two feasible values are randomly generated for the departure times and headways, respectively. Likewise, if the randomly generated floating-point number is less than the mutation probability, the mutation operation is conducted.To calculate the crowding distance of different objectives, the following equation is established:(11)Dwi=fwi+1−fwi−1/fwmax−fwmin.Here,fwmax and fwmin represent the maximum and minimum values of the wth objective function at this level, respectively, and fwi+1 and fwi−1 represent the wth objective function values corresponding to the i + 1th and i − 1th individuals at this level, respectively.In the process of generating a new parent population, individuals with higher levels are selected from the combined population to enter the new parent population. If the total number of individuals in the same level exceeds the population size of the new parent population, the individuals with a large crowding distance in the level are selected to enter until the number of individuals reaches the population size. The detailed procedure is represented in Algorithm 1.Algorithm 1: NSGA-II.
Step 1: (Initialization)Step 1.1: Input the number and index of the lines in the network and the number and index of the intermediate stations and transfer stations on each line;Step 1.2: Input OD demand setK and promising routes;Step 1.3: Input the actual schedule of each line in the network and other parameters;Step 1.4: Input algorithm parameters, such as the population sizepop_size, maximum number of iterations Gen_max, crossover probability, and mutation probability;Step 2: (Initial population)Fori = 1 to pop_sizedoGeneratel_num departure times of first trains and headways of each individual randomly;Endfor//iGenerate the parent population;Gen = 1;Step 3: (Sorting)Step 3.1:Forj = 1 to pop_sizedoCalculate the nondominated sorting rank of each individual;Endfor//jStep 3.2:Calculate the crowded distance of each individual in the same rank;Step 4: (Genetic operation)According to the binary tournament selection rules,pop_size/2 individuals are selected from the parent population and the pop_size/2 individuals are genetically operated according to the randomly generated crossover probability and mutation probability until other pop_size/2 individuals are generated;Step 5: (Offspring population)Thesepop_size individuals generated in Step 4 compose the offspring population;Step 6: (Combined population)The parent population generated in Step 7 (ifGen = 1, generated in Step 2) and offspring population generated in Step 5 compose the combined population (2∗pop_size);Step 7: (New population)Calculate the nondominated sorting rank of each individual in the combined population and calculate the crowded distance of each individual in the same rank;Selectpop_size new individuals from the combined population to compose the new parent population;Step 8: (Solution)IfGen < Gen_max, thenGo to step 4;ElseOutput final solutions, such as the Pareto front, synchronized timetable, and train connection sequence.Endif


## 5. Numerical Experiments

In this section, different-scale experiments regarding the Xi’an metro network are conducted to verify the correctness and effectiveness of the above model and algorithm. All experiments are implemented by C++ on a PC with an i5-4590s 3.00 GHz CPU and 4 GB RAM.


### 5.1. Large-Sized Numerical Experiment

We take the Xi’an urban rail transit network, which includes 16 lines (8 bidirectional lines) and 153 stations, as the large-sized numerical experiment. In this experiment, each bidirectional line is used as two unidirectional lines. For example, line 1 represents the up-train and down-train directions as lines 1U and 1D, respectively. The lines and stations are renumbered as shown in Figure7. The running times on each segment and the OD demands are listed at https://github.com/xpTianLZJT/TTP/blob/main/JAT2021/FurtherExperiments.zip. The dwell times of all trains at each station are 1 min, the passenger transfer walking times at each transfer station are 3 min, and the actual headway of each line is 7 min. In addition, according to the actual operation requirements of the Xi’an metro, we set the minimum headway and the maximum headway to 2 minutes and 10 minutes, respectively. Table 4 shows the earliest and latest departure times of the first trains on all lines.Figure 7
Map of the Xi’an metro network.Table 4
The earliest and latest departure times of the first trains.
LineEarliest departure timeLatest departure time1D5:506:101U5:506:102D5:506:102U5:506:103D5:506:103U5:506:104D5:506:104U5:506:105D5:506:105U5:506:106D5:506:106U6:056:257D6:206:407U6:206:408D5:506:108U5:506:10We set the size of the population to 200, the crossover probability to 0.9, the mutation probability to 0.2, and the maximum number of iterations to 500. To reduce the influence of randomness in the NSGA-II algorithm, we repeatedly perform the NSGA-II algorithm 50 times for the large-scale experiment. Furthermore, we select the most typical 5 groups of Pareto solutions from multiple calculations, which are shown in Figure8. For convenience, each solution is denoted by the corresponding coordinate of the objective value, i.e., (value of passenger travel time, value of schedule deviation time). For example, the first solution with a travel time of 5648027 min and a deviation time of 36 min is represented by (5648027, 36).Figure 8
Pareto solutions of the large-scale experiment.To compare the difference between the optimized timetable and the actual timetable, Table5 lists the departure times of the first trains at the starting stations in the actual timetable, and the actual headways of all lines are equal to 7 min. The total travel time of transfer passengers is 5729497 min.Table 5
Departure times of the first trains in the actual timetable.
LineDeparture time1D6:001U6:002D6:002U6:003D6:003U6:004D6:004U6:005D6:005U6:006D6:006U6:157D6:307U6:308D6:008U6:00From the solutions in Figure8, we can find that the passenger travel time of the solution (5236686, 99) is the smallest, which is 8.6% less than that of the actual schedule. The corresponding headways, the departure times of the first trains, and the deviations from the actual timetable are shown in Table 6, where the deviation is represented by the optimized headway (departure time) minus the actual headway (departure time). For example, the deviation headway of line 1D is −2 (i.e., −2 = 5–7). In addition, for the solution (5648027, 36) with the minimum deviation, the total passenger travel time is also the largest, which is reduced by 1.4% compared with the actual schedule. In practice, operators can select a suitable solution according to practical requirements.Table 6
Optimized headways and departure times of the first trains for solution (5236686, 99).
LineOptimized headwayDeviation from the actual headway (min)The optimized departure time of the first trainDeviation from the actual departure time of the first train (min)1D5−25:53−71U6−16:04+42D3−46:02+22U6−16:02+23D6−16:0003U4−35:51−94D2−55:56−44U2−55:53−75D6−15:51−95U3−46:03+36D10+35:58−26U2−56:20+57D5−26:29−17U8+16:29−18D705:58−28U8+16:02+2Table7 lists some train connection relationships from the possible feeder lines to the connecting lines 1U and 1D in solution (5236686, 99). At transfer station 14, (1, 2D)⟶(1, 1D) represents the first train on line 2D is connected by the first train on line 1D. Similarly, the passengers on the first train of line 3D can transfer to the third train on line 1U at transfer station 18. Note that there is a unique transfer direction at station 23. Among the optimized connection in Table 7, the “first train-first train” connection occurs six times, accounting for 46.2%. From the above-given results, we can further verify that not all passengers taking the first trains transfer to the first train on the connecting line. Also, compared with the actual train timetable, the connection efficiency and transfer waiting time of the optimized train timetable are improved.Table 7
Connection relationships for the connecting lines 1U and 1D in solution (5236686, 99).
Transfer stationOptimized connection relationshipTransfer waiting time (min)Actual connection relationshipTransfer waiting time (min)14(1, 2D) ⟶ (1, 1D)0(1, 2D) ⟶ (1, 1D)10(1, 2D) ⟶ (1, 1U)0(1, 2D) ⟶ (2, 1U)3(1, 2U) ⟶ (2, 1D)0(1, 2U) ⟶ (1, 1D)5(1, 2U) ⟶ (2, 1U)1(1, 2U) ⟶ (3, 1U)515(1, 4D) ⟶ (1, 1D)0(1, 4D) ⟶ (1, 1D)3(1, 4D) ⟶ (2, 1U)0(1, 4D) ⟶ (3, 1U)0(1, 4U) ⟶ (1, 1D)1(1, 4U) ⟶ (1, 1D)2(1, 4U) ⟶ (2, 1U)1(1, 4U) ⟶ (4, 1U)618(1, 3D) ⟶ (1, 1D)1(1, 3D) ⟶ (1, 1D)9(1, 3D) ⟶ (4, 1U)0(1, 3D) ⟶ (5, 1U)3(1, 3U) ⟶ (1, 1D)13(1, 3U) ⟶ (1, 1D)12(1, 3U) ⟶ (2, 1U)0(1, 3U) ⟶ (5, 1U)623(1, 7U) ⟶ (12, 1U)0(1, 7U) ⟶ (12, 1U)6


### 5.2. Further Experiments

#### 5.2.1. Comparison of Different-Sized Experiment Instances

By using different-sized networks, we further compare the efficiency of the proposed algorithm with the NSGA-II without the preprocessing method. These different-sized networks are constructed based on the above-mentioned Xi’an metro network, which is shown in Table8. The detailed information of these instances is available at https://github.com/xpTianLZJT/TTP/blob/main/JAT2021/FurtherExperiments.zip. Among the algorithm parameters, we set the population size to 50, the number of iterations to 50, the crossover probability to 0.9, and the mutation probability to 0.2.Table 8
Instance information.
Instance IDNetworkNumber of linesNumber of stationsNumber of transfer stations1Origin network16153132Except 6U and 6D14142113Except 6U, 6D, 8U, and 8D12134104Except 6U, 6D, 8U, 8D, 7U, and 7D1012095Except 6U, 6D, 8U, 8D, 7U, 7D, 3U, and 3D8985In general, the physical lines in metro networks are decreasing, and the corresponding transfer passenger demand is also decreasing. The opposite also holds. Table9 lists the calculation time of solving the model with or without the preprocessing method. The scale of the problem always affects the calculation speed, and the preprocessing method can effectively reduce the computation time.Table 9
Comparison of the computational efficiency under different network sizes.
Instance IDNumber of OD pairsComputational times of the proposed algorithm without the preprocessing method (min)Computational times of the proposed algorithm with the preprocessing method (min)1195592.980.2122164812.200.1533143531.630.1384110210.9920.078568860.5360.034To validate the effectiveness of the proposed approach, we use statistical analysis to assess the results of different-scale experiments obtained by the NSGA-II with and without the preprocessing method. Taking the computation times in Table9 as two related samples, we then perform the Wilcoxon test on the SPSS software to verify the two methods. The verification results are shown in Table 10. Specifically, the value of normalized Wilcoxon statistics (denoted by Z) is −2.023, and the asymptotic 2-sided significance (denoted by P) is 0.043. Due to P=0.043<0.05, the computation times with and without preprocessing method are completely different, and the NSGA-II with the preprocessing method is conducive to improving the solution efficiency.Table 10
Wilcoxon test results.
With the preprocessing method − without the preprocessing methodZ−2.023P0.043To further demonstrate the advantage of our proposed approach, we compare the difference between transfer OD passenger demand and transfer-direction-based demand. First, we convert the OD demand to the transfer-direction-based demand. Similar to Wong et al. [18], we assume that the path choices of passengers are fixed, and passengers choose a path with as few interchanges as possible. This assumption allows us to obtain transfer-direction-based demand by assigning OD demand. Second, we replace minimizing passenger travel time with minimizing passenger transfer waiting time. The revised approach is capable of solving instances with the transfer-direction-based demand. Then, we use the two approaches (i.e., the proposed approach for OD demand and the revised approach for transfer-direction-based demand) to solve five groups of instances with different-sized networks. For each instance, we select solutions with the same deviation from the Pareto solutions obtained by the two approaches, respectively. The comparison results of the two cases are shown in Table 11.Table 11
Comparison of the two approaches with different demand patterns.
Instance IDOur proposed approachApproach for transfer-direction-based demandPassenger waiting time for the first transferPassenger waiting time for the second transferPassenger waiting time for the third transferComputational times (min)Passenger waiting time for the first transferPassenger waiting time for the second transferPassenger waiting time for the third transferComputational times (min)1367538122574747680.212371544——0.052231396483143448130.153338915——0.033327508934666152270.138289690——0.03042119252718800.078211315——0.02651001212361800.034102418——0.015It is well known that a transfer passenger may need to transfer multiple times to reach his/her destination in a complex metro network, which can be found in Table11. Specifically, the passenger waiting time for the first, second, and third transfers can be obtained in our proposed approach, but the approach for the transfer-direction-based demand only can retrieve the waiting time for the first transfer.In other words, the approach for transfer-direction-based demand cannot measure the multiple transfers of passengers. As shown in Figure9, in the solution obtained by our proposed approach in the instance 1, OD (12, 79) passenger demand is to transfer from train 1 on line 1D to train 2 online 2D at station 14, from train 2 on line 2D to train 2 on line 3U at station 60, and from train 2 on line 3U to train 3 on line 6U. When using the approach for transfer-direction-based demand, however, the transfer processes of OD (12, 79) demand at stations 60 and 57 cannot be considered.Figure 9
Transfer process for OD (12, 79) passenger demand.


#### 5.2.2. Analysis of the Actual HeadwayH¯l and the Maximum Headway hlmax

To analyze the influence of the actual headwaysH¯l and maximum headways hlmax on the optimized solutions, we consider five instances by setting different H¯l and hlmax on the basis of the above lager-sized example regarding the Xi’an metro network. Furthermore, we set the population size to 50, the number of iterations to 50, the crossover probability to 0.9, and the mutation probability to 0.2. The obtained results are shown in Table 12, where we calculate the average travel time, deviation time, and average headway for all the obtained Pareto solutions. Obviously, both the average travel time and average headway increase with both the maximum and actual headways.Table 12
Analysis of different maximum headways and actual headways.
InstanceAverage travel time (min)Average deviationtime (min)Average headway (min)Computationaltimes (min)Maximum headway (hlmax)Actual headwayH¯l12754570969060.225149552575881100.21716115566354113100.22318135694798108140.28420155747981110140.325In addition, we select three solutions (i.e., (5974021, 75), (5669964, 108), and (5492363, 147)) from Pareto solutions of the instance withhlmax=18 and H¯l=13. We count the number of optimized headways and the number of connections of the first trains, which are shown in Table 13. It can be found that the average headway of the solution (5974021, 75) is greater than the actual headway, but the average headways of the other two solutions are less than the actual headway. That is, the optimized Pareto solutions provide different train schedules such that operators can choose the preferred solutions according to their preferences. Also, although we have optimized the connection times of the first trains, the connection times of many first trains are still longer than the headway. Actually, this result is also the most distinctive feature of the first train timetabling problem.Table 13
Analysis of optimized headway and connection of the first train.
SolutionOptimized headwayConnection of the first trainNumber of optimized headways (>13 min)Number of optimized headways (=13 min)Number of optimized headways (<13 min)Average headway (min)Number of connection times for first trains (>18 min)Number of connection times for first trains (≤18 min)Average connection time (min)(5974021, 75)65514196938(5669964, 108)231110187036(5492363, 147)31128196937


#### 5.2.3. Analysis of Different Departure Time Ranges of the First Trains at the Starting Stations

To analyze the influence of different departure time ranges of the first trains at the starting stations on the optimized solution, we further solve the 6 groups of instances with the different lengths of departure time ranges. Specifically, the Xi’an metro network is also used as input, and the length of the departure time ranges of the first trains are set to 10, 12, 14, 16, 18, and 20 minutes, respectively. The other parameters in the algorithm are the same as the setting of the above section, and Table14 lists the optimized results. One of the most notable features is that as the length of the departure time range is increased, the average deviation time increases because the longer departure time range inevitably causes a larger solution space.Table 14
Analysis of the different departure time ranges of the first trains at starting stations.
The length of the departure timerange for each instance (min)Number of Pareto solutionsAverage travel time (min)Average deviation time (min)1024136964712181296662142213878141622167888818241758897202721211133


#### 5.2.4. Analysis of Different Decision Variables

To analyze the influence of different decision variables, we propose the following three approaches: (i) optimizing departure times of first trains with fixed headways, denoted as FH-ODT for short, (ii) optimizing headways with fixed departure times of first trains, denoted as FDT-OH, and (iii) optimizing headways and departure times of first trains (i.e., our proposed approach). Based on the aforementioned large-sized instance in Section5.1, we construct five instances by setting different headways and departure times of first trains. For simplicity, we assume that the headways of all lines are the same and the departure times of first trains are uniformly increased or decreased on the basis of Table 5. Thus, each instance is identified by the headways and the increment of the departure times of the first trains. For example, instance (5, −5) is that the headways of all lines are 5 minutes, and the departure times of the first trains are the departure times in Table 5 minus 5 minutes. Then, we employ the three approaches to solve each instance. The computational results are shown in Table 15. Compared with approaches FH-ODT and FDT-OH, our proposed approach can significantly improve passenger travel time while maintaining small changes in deviation times.Table 15
Influence of decision variables on results.
Instance IDApproach FH-ODTApproach FDT-OHOur proposed approachAverage travel timeAverage deviation time of departure times of first trainsAverage travel timeAverage deviation time of headwayAverage travel timeAverage deviation time of departure times of first trainsAverage deviation time of headway(5, −5)53384224454776212853280606228(6, −3)54633064754769313054413264534(7, 0)55289834254773913154533574632(8, 3)55904694455071522754852734629(9, 5)56209824155064953154959595642


## 5.1. Large-Sized Numerical Experiment

We take the Xi’an urban rail transit network, which includes 16 lines (8 bidirectional lines) and 153 stations, as the large-sized numerical experiment. In this experiment, each bidirectional line is used as two unidirectional lines. For example, line 1 represents the up-train and down-train directions as lines 1U and 1D, respectively. The lines and stations are renumbered as shown in Figure7. The running times on each segment and the OD demands are listed at https://github.com/xpTianLZJT/TTP/blob/main/JAT2021/FurtherExperiments.zip. The dwell times of all trains at each station are 1 min, the passenger transfer walking times at each transfer station are 3 min, and the actual headway of each line is 7 min. In addition, according to the actual operation requirements of the Xi’an metro, we set the minimum headway and the maximum headway to 2 minutes and 10 minutes, respectively. Table 4 shows the earliest and latest departure times of the first trains on all lines.Figure 7
Map of the Xi’an metro network.Table 4
The earliest and latest departure times of the first trains.
LineEarliest departure timeLatest departure time1D5:506:101U5:506:102D5:506:102U5:506:103D5:506:103U5:506:104D5:506:104U5:506:105D5:506:105U5:506:106D5:506:106U6:056:257D6:206:407U6:206:408D5:506:108U5:506:10We set the size of the population to 200, the crossover probability to 0.9, the mutation probability to 0.2, and the maximum number of iterations to 500. To reduce the influence of randomness in the NSGA-II algorithm, we repeatedly perform the NSGA-II algorithm 50 times for the large-scale experiment. Furthermore, we select the most typical 5 groups of Pareto solutions from multiple calculations, which are shown in Figure8. For convenience, each solution is denoted by the corresponding coordinate of the objective value, i.e., (value of passenger travel time, value of schedule deviation time). For example, the first solution with a travel time of 5648027 min and a deviation time of 36 min is represented by (5648027, 36).Figure 8
Pareto solutions of the large-scale experiment.To compare the difference between the optimized timetable and the actual timetable, Table5 lists the departure times of the first trains at the starting stations in the actual timetable, and the actual headways of all lines are equal to 7 min. The total travel time of transfer passengers is 5729497 min.Table 5
Departure times of the first trains in the actual timetable.
LineDeparture time1D6:001U6:002D6:002U6:003D6:003U6:004D6:004U6:005D6:005U6:006D6:006U6:157D6:307U6:308D6:008U6:00From the solutions in Figure8, we can find that the passenger travel time of the solution (5236686, 99) is the smallest, which is 8.6% less than that of the actual schedule. The corresponding headways, the departure times of the first trains, and the deviations from the actual timetable are shown in Table 6, where the deviation is represented by the optimized headway (departure time) minus the actual headway (departure time). For example, the deviation headway of line 1D is −2 (i.e., −2 = 5–7). In addition, for the solution (5648027, 36) with the minimum deviation, the total passenger travel time is also the largest, which is reduced by 1.4% compared with the actual schedule. In practice, operators can select a suitable solution according to practical requirements.Table 6
Optimized headways and departure times of the first trains for solution (5236686, 99).
LineOptimized headwayDeviation from the actual headway (min)The optimized departure time of the first trainDeviation from the actual departure time of the first train (min)1D5−25:53−71U6−16:04+42D3−46:02+22U6−16:02+23D6−16:0003U4−35:51−94D2−55:56−44U2−55:53−75D6−15:51−95U3−46:03+36D10+35:58−26U2−56:20+57D5−26:29−17U8+16:29−18D705:58−28U8+16:02+2Table7 lists some train connection relationships from the possible feeder lines to the connecting lines 1U and 1D in solution (5236686, 99). At transfer station 14, (1, 2D)⟶(1, 1D) represents the first train on line 2D is connected by the first train on line 1D. Similarly, the passengers on the first train of line 3D can transfer to the third train on line 1U at transfer station 18. Note that there is a unique transfer direction at station 23. Among the optimized connection in Table 7, the “first train-first train” connection occurs six times, accounting for 46.2%. From the above-given results, we can further verify that not all passengers taking the first trains transfer to the first train on the connecting line. Also, compared with the actual train timetable, the connection efficiency and transfer waiting time of the optimized train timetable are improved.Table 7
Connection relationships for the connecting lines 1U and 1D in solution (5236686, 99).
Transfer stationOptimized connection relationshipTransfer waiting time (min)Actual connection relationshipTransfer waiting time (min)14(1, 2D) ⟶ (1, 1D)0(1, 2D) ⟶ (1, 1D)10(1, 2D) ⟶ (1, 1U)0(1, 2D) ⟶ (2, 1U)3(1, 2U) ⟶ (2, 1D)0(1, 2U) ⟶ (1, 1D)5(1, 2U) ⟶ (2, 1U)1(1, 2U) ⟶ (3, 1U)515(1, 4D) ⟶ (1, 1D)0(1, 4D) ⟶ (1, 1D)3(1, 4D) ⟶ (2, 1U)0(1, 4D) ⟶ (3, 1U)0(1, 4U) ⟶ (1, 1D)1(1, 4U) ⟶ (1, 1D)2(1, 4U) ⟶ (2, 1U)1(1, 4U) ⟶ (4, 1U)618(1, 3D) ⟶ (1, 1D)1(1, 3D) ⟶ (1, 1D)9(1, 3D) ⟶ (4, 1U)0(1, 3D) ⟶ (5, 1U)3(1, 3U) ⟶ (1, 1D)13(1, 3U) ⟶ (1, 1D)12(1, 3U) ⟶ (2, 1U)0(1, 3U) ⟶ (5, 1U)623(1, 7U) ⟶ (12, 1U)0(1, 7U) ⟶ (12, 1U)6


## 5.2. Further Experiments

### 5.2.1. Comparison of Different-Sized Experiment Instances

By using different-sized networks, we further compare the efficiency of the proposed algorithm with the NSGA-II without the preprocessing method. These different-sized networks are constructed based on the above-mentioned Xi’an metro network, which is shown in Table8. The detailed information of these instances is available at https://github.com/xpTianLZJT/TTP/blob/main/JAT2021/FurtherExperiments.zip. Among the algorithm parameters, we set the population size to 50, the number of iterations to 50, the crossover probability to 0.9, and the mutation probability to 0.2.Table 8
Instance information.
Instance IDNetworkNumber of linesNumber of stationsNumber of transfer stations1Origin network16153132Except 6U and 6D14142113Except 6U, 6D, 8U, and 8D12134104Except 6U, 6D, 8U, 8D, 7U, and 7D1012095Except 6U, 6D, 8U, 8D, 7U, 7D, 3U, and 3D8985In general, the physical lines in metro networks are decreasing, and the corresponding transfer passenger demand is also decreasing. The opposite also holds. Table9 lists the calculation time of solving the model with or without the preprocessing method. The scale of the problem always affects the calculation speed, and the preprocessing method can effectively reduce the computation time.Table 9
Comparison of the computational efficiency under different network sizes.
Instance IDNumber of OD pairsComputational times of the proposed algorithm without the preprocessing method (min)Computational times of the proposed algorithm with the preprocessing method (min)1195592.980.2122164812.200.1533143531.630.1384110210.9920.078568860.5360.034To validate the effectiveness of the proposed approach, we use statistical analysis to assess the results of different-scale experiments obtained by the NSGA-II with and without the preprocessing method. Taking the computation times in Table9 as two related samples, we then perform the Wilcoxon test on the SPSS software to verify the two methods. The verification results are shown in Table 10. Specifically, the value of normalized Wilcoxon statistics (denoted by Z) is −2.023, and the asymptotic 2-sided significance (denoted by P) is 0.043. Due to P=0.043<0.05, the computation times with and without preprocessing method are completely different, and the NSGA-II with the preprocessing method is conducive to improving the solution efficiency.Table 10
Wilcoxon test results.
With the preprocessing method − without the preprocessing methodZ−2.023P0.043To further demonstrate the advantage of our proposed approach, we compare the difference between transfer OD passenger demand and transfer-direction-based demand. First, we convert the OD demand to the transfer-direction-based demand. Similar to Wong et al. [18], we assume that the path choices of passengers are fixed, and passengers choose a path with as few interchanges as possible. This assumption allows us to obtain transfer-direction-based demand by assigning OD demand. Second, we replace minimizing passenger travel time with minimizing passenger transfer waiting time. The revised approach is capable of solving instances with the transfer-direction-based demand. Then, we use the two approaches (i.e., the proposed approach for OD demand and the revised approach for transfer-direction-based demand) to solve five groups of instances with different-sized networks. For each instance, we select solutions with the same deviation from the Pareto solutions obtained by the two approaches, respectively. The comparison results of the two cases are shown in Table 11.Table 11
Comparison of the two approaches with different demand patterns.
Instance IDOur proposed approachApproach for transfer-direction-based demandPassenger waiting time for the first transferPassenger waiting time for the second transferPassenger waiting time for the third transferComputational times (min)Passenger waiting time for the first transferPassenger waiting time for the second transferPassenger waiting time for the third transferComputational times (min)1367538122574747680.212371544——0.052231396483143448130.153338915——0.033327508934666152270.138289690——0.03042119252718800.078211315——0.02651001212361800.034102418——0.015It is well known that a transfer passenger may need to transfer multiple times to reach his/her destination in a complex metro network, which can be found in Table11. Specifically, the passenger waiting time for the first, second, and third transfers can be obtained in our proposed approach, but the approach for the transfer-direction-based demand only can retrieve the waiting time for the first transfer.In other words, the approach for transfer-direction-based demand cannot measure the multiple transfers of passengers. As shown in Figure9, in the solution obtained by our proposed approach in the instance 1, OD (12, 79) passenger demand is to transfer from train 1 on line 1D to train 2 online 2D at station 14, from train 2 on line 2D to train 2 on line 3U at station 60, and from train 2 on line 3U to train 3 on line 6U. When using the approach for transfer-direction-based demand, however, the transfer processes of OD (12, 79) demand at stations 60 and 57 cannot be considered.Figure 9
Transfer process for OD (12, 79) passenger demand.


### 5.2.2. Analysis of the Actual HeadwayH¯l and the Maximum Headway hlmax

To analyze the influence of the actual headwaysH¯l and maximum headways hlmax on the optimized solutions, we consider five instances by setting different H¯l and hlmax on the basis of the above lager-sized example regarding the Xi’an metro network. Furthermore, we set the population size to 50, the number of iterations to 50, the crossover probability to 0.9, and the mutation probability to 0.2. The obtained results are shown in Table 12, where we calculate the average travel time, deviation time, and average headway for all the obtained Pareto solutions. Obviously, both the average travel time and average headway increase with both the maximum and actual headways.Table 12
Analysis of different maximum headways and actual headways.
InstanceAverage travel time (min)Average deviationtime (min)Average headway (min)Computationaltimes (min)Maximum headway (hlmax)Actual headwayH¯l12754570969060.225149552575881100.21716115566354113100.22318135694798108140.28420155747981110140.325In addition, we select three solutions (i.e., (5974021, 75), (5669964, 108), and (5492363, 147)) from Pareto solutions of the instance withhlmax=18 and H¯l=13. We count the number of optimized headways and the number of connections of the first trains, which are shown in Table 13. It can be found that the average headway of the solution (5974021, 75) is greater than the actual headway, but the average headways of the other two solutions are less than the actual headway. That is, the optimized Pareto solutions provide different train schedules such that operators can choose the preferred solutions according to their preferences. Also, although we have optimized the connection times of the first trains, the connection times of many first trains are still longer than the headway. Actually, this result is also the most distinctive feature of the first train timetabling problem.Table 13
Analysis of optimized headway and connection of the first train.
SolutionOptimized headwayConnection of the first trainNumber of optimized headways (>13 min)Number of optimized headways (=13 min)Number of optimized headways (<13 min)Average headway (min)Number of connection times for first trains (>18 min)Number of connection times for first trains (≤18 min)Average connection time (min)(5974021, 75)65514196938(5669964, 108)231110187036(5492363, 147)31128196937


### 5.2.3. Analysis of Different Departure Time Ranges of the First Trains at the Starting Stations

To analyze the influence of different departure time ranges of the first trains at the starting stations on the optimized solution, we further solve the 6 groups of instances with the different lengths of departure time ranges. Specifically, the Xi’an metro network is also used as input, and the length of the departure time ranges of the first trains are set to 10, 12, 14, 16, 18, and 20 minutes, respectively. The other parameters in the algorithm are the same as the setting of the above section, and Table14 lists the optimized results. One of the most notable features is that as the length of the departure time range is increased, the average deviation time increases because the longer departure time range inevitably causes a larger solution space.Table 14
Analysis of the different departure time ranges of the first trains at starting stations.
The length of the departure timerange for each instance (min)Number of Pareto solutionsAverage travel time (min)Average deviation time (min)1024136964712181296662142213878141622167888818241758897202721211133


### 5.2.4. Analysis of Different Decision Variables

To analyze the influence of different decision variables, we propose the following three approaches: (i) optimizing departure times of first trains with fixed headways, denoted as FH-ODT for short, (ii) optimizing headways with fixed departure times of first trains, denoted as FDT-OH, and (iii) optimizing headways and departure times of first trains (i.e., our proposed approach). Based on the aforementioned large-sized instance in Section5.1, we construct five instances by setting different headways and departure times of first trains. For simplicity, we assume that the headways of all lines are the same and the departure times of first trains are uniformly increased or decreased on the basis of Table 5. Thus, each instance is identified by the headways and the increment of the departure times of the first trains. For example, instance (5, −5) is that the headways of all lines are 5 minutes, and the departure times of the first trains are the departure times in Table 5 minus 5 minutes. Then, we employ the three approaches to solve each instance. The computational results are shown in Table 15. Compared with approaches FH-ODT and FDT-OH, our proposed approach can significantly improve passenger travel time while maintaining small changes in deviation times.Table 15
Influence of decision variables on results.
Instance IDApproach FH-ODTApproach FDT-OHOur proposed approachAverage travel timeAverage deviation time of departure times of first trainsAverage travel timeAverage deviation time of headwayAverage travel timeAverage deviation time of departure times of first trainsAverage deviation time of headway(5, −5)53384224454776212853280606228(6, −3)54633064754769313054413264534(7, 0)55289834254773913154533574632(8, 3)55904694455071522754852734629(9, 5)56209824155064953154959595642


## 5.2.1. Comparison of Different-Sized Experiment Instances

By using different-sized networks, we further compare the efficiency of the proposed algorithm with the NSGA-II without the preprocessing method. These different-sized networks are constructed based on the above-mentioned Xi’an metro network, which is shown in Table8. The detailed information of these instances is available at https://github.com/xpTianLZJT/TTP/blob/main/JAT2021/FurtherExperiments.zip. Among the algorithm parameters, we set the population size to 50, the number of iterations to 50, the crossover probability to 0.9, and the mutation probability to 0.2.Table 8
Instance information.
Instance IDNetworkNumber of linesNumber of stationsNumber of transfer stations1Origin network16153132Except 6U and 6D14142113Except 6U, 6D, 8U, and 8D12134104Except 6U, 6D, 8U, 8D, 7U, and 7D1012095Except 6U, 6D, 8U, 8D, 7U, 7D, 3U, and 3D8985In general, the physical lines in metro networks are decreasing, and the corresponding transfer passenger demand is also decreasing. The opposite also holds. Table9 lists the calculation time of solving the model with or without the preprocessing method. The scale of the problem always affects the calculation speed, and the preprocessing method can effectively reduce the computation time.Table 9
Comparison of the computational efficiency under different network sizes.
Instance IDNumber of OD pairsComputational times of the proposed algorithm without the preprocessing method (min)Computational times of the proposed algorithm with the preprocessing method (min)1195592.980.2122164812.200.1533143531.630.1384110210.9920.078568860.5360.034To validate the effectiveness of the proposed approach, we use statistical analysis to assess the results of different-scale experiments obtained by the NSGA-II with and without the preprocessing method. Taking the computation times in Table9 as two related samples, we then perform the Wilcoxon test on the SPSS software to verify the two methods. The verification results are shown in Table 10. Specifically, the value of normalized Wilcoxon statistics (denoted by Z) is −2.023, and the asymptotic 2-sided significance (denoted by P) is 0.043. Due to P=0.043<0.05, the computation times with and without preprocessing method are completely different, and the NSGA-II with the preprocessing method is conducive to improving the solution efficiency.Table 10
Wilcoxon test results.
With the preprocessing method − without the preprocessing methodZ−2.023P0.043To further demonstrate the advantage of our proposed approach, we compare the difference between transfer OD passenger demand and transfer-direction-based demand. First, we convert the OD demand to the transfer-direction-based demand. Similar to Wong et al. [18], we assume that the path choices of passengers are fixed, and passengers choose a path with as few interchanges as possible. This assumption allows us to obtain transfer-direction-based demand by assigning OD demand. Second, we replace minimizing passenger travel time with minimizing passenger transfer waiting time. The revised approach is capable of solving instances with the transfer-direction-based demand. Then, we use the two approaches (i.e., the proposed approach for OD demand and the revised approach for transfer-direction-based demand) to solve five groups of instances with different-sized networks. For each instance, we select solutions with the same deviation from the Pareto solutions obtained by the two approaches, respectively. The comparison results of the two cases are shown in Table 11.Table 11
Comparison of the two approaches with different demand patterns.
Instance IDOur proposed approachApproach for transfer-direction-based demandPassenger waiting time for the first transferPassenger waiting time for the second transferPassenger waiting time for the third transferComputational times (min)Passenger waiting time for the first transferPassenger waiting time for the second transferPassenger waiting time for the third transferComputational times (min)1367538122574747680.212371544——0.052231396483143448130.153338915——0.033327508934666152270.138289690——0.03042119252718800.078211315——0.02651001212361800.034102418——0.015It is well known that a transfer passenger may need to transfer multiple times to reach his/her destination in a complex metro network, which can be found in Table11. Specifically, the passenger waiting time for the first, second, and third transfers can be obtained in our proposed approach, but the approach for the transfer-direction-based demand only can retrieve the waiting time for the first transfer.In other words, the approach for transfer-direction-based demand cannot measure the multiple transfers of passengers. As shown in Figure9, in the solution obtained by our proposed approach in the instance 1, OD (12, 79) passenger demand is to transfer from train 1 on line 1D to train 2 online 2D at station 14, from train 2 on line 2D to train 2 on line 3U at station 60, and from train 2 on line 3U to train 3 on line 6U. When using the approach for transfer-direction-based demand, however, the transfer processes of OD (12, 79) demand at stations 60 and 57 cannot be considered.Figure 9
Transfer process for OD (12, 79) passenger demand.


## 5.2.2. Analysis of the Actual HeadwayH¯l and the Maximum Headway hlmax

To analyze the influence of the actual headwaysH¯l and maximum headways hlmax on the optimized solutions, we consider five instances by setting different H¯l and hlmax on the basis of the above lager-sized example regarding the Xi’an metro network. Furthermore, we set the population size to 50, the number of iterations to 50, the crossover probability to 0.9, and the mutation probability to 0.2. The obtained results are shown in Table 12, where we calculate the average travel time, deviation time, and average headway for all the obtained Pareto solutions. Obviously, both the average travel time and average headway increase with both the maximum and actual headways.Table 12
Analysis of different maximum headways and actual headways.
InstanceAverage travel time (min)Average deviationtime (min)Average headway (min)Computationaltimes (min)Maximum headway (hlmax)Actual headwayH¯l12754570969060.225149552575881100.21716115566354113100.22318135694798108140.28420155747981110140.325In addition, we select three solutions (i.e., (5974021, 75), (5669964, 108), and (5492363, 147)) from Pareto solutions of the instance withhlmax=18 and H¯l=13. We count the number of optimized headways and the number of connections of the first trains, which are shown in Table 13. It can be found that the average headway of the solution (5974021, 75) is greater than the actual headway, but the average headways of the other two solutions are less than the actual headway. That is, the optimized Pareto solutions provide different train schedules such that operators can choose the preferred solutions according to their preferences. Also, although we have optimized the connection times of the first trains, the connection times of many first trains are still longer than the headway. Actually, this result is also the most distinctive feature of the first train timetabling problem.Table 13
Analysis of optimized headway and connection of the first train.
SolutionOptimized headwayConnection of the first trainNumber of optimized headways (>13 min)Number of optimized headways (=13 min)Number of optimized headways (<13 min)Average headway (min)Number of connection times for first trains (>18 min)Number of connection times for first trains (≤18 min)Average connection time (min)(5974021, 75)65514196938(5669964, 108)231110187036(5492363, 147)31128196937


## 5.2.3. Analysis of Different Departure Time Ranges of the First Trains at the Starting Stations

To analyze the influence of different departure time ranges of the first trains at the starting stations on the optimized solution, we further solve the 6 groups of instances with the different lengths of departure time ranges. Specifically, the Xi’an metro network is also used as input, and the length of the departure time ranges of the first trains are set to 10, 12, 14, 16, 18, and 20 minutes, respectively. The other parameters in the algorithm are the same as the setting of the above section, and Table14 lists the optimized results. One of the most notable features is that as the length of the departure time range is increased, the average deviation time increases because the longer departure time range inevitably causes a larger solution space.Table 14
Analysis of the different departure time ranges of the first trains at starting stations.
The length of the departure timerange for each instance (min)Number of Pareto solutionsAverage travel time (min)Average deviation time (min)1024136964712181296662142213878141622167888818241758897202721211133


## 5.2.4. Analysis of Different Decision Variables

To analyze the influence of different decision variables, we propose the following three approaches: (i) optimizing departure times of first trains with fixed headways, denoted as FH-ODT for short, (ii) optimizing headways with fixed departure times of first trains, denoted as FDT-OH, and (iii) optimizing headways and departure times of first trains (i.e., our proposed approach). Based on the aforementioned large-sized instance in Section5.1, we construct five instances by setting different headways and departure times of first trains. For simplicity, we assume that the headways of all lines are the same and the departure times of first trains are uniformly increased or decreased on the basis of Table 5. Thus, each instance is identified by the headways and the increment of the departure times of the first trains. For example, instance (5, −5) is that the headways of all lines are 5 minutes, and the departure times of the first trains are the departure times in Table 5 minus 5 minutes. Then, we employ the three approaches to solve each instance. The computational results are shown in Table 15. Compared with approaches FH-ODT and FDT-OH, our proposed approach can significantly improve passenger travel time while maintaining small changes in deviation times.Table 15
Influence of decision variables on results.
Instance IDApproach FH-ODTApproach FDT-OHOur proposed approachAverage travel timeAverage deviation time of departure times of first trainsAverage travel timeAverage deviation time of headwayAverage travel timeAverage deviation time of departure times of first trainsAverage deviation time of headway(5, −5)53384224454776212853280606228(6, −3)54633064754769313054413264534(7, 0)55289834254773913154533574632(8, 3)55904694455071522754852734629(9, 5)56209824155064953154959595642


## 6. Conclusions

This paper studies first-train timetable synchronization in metro networks under passenger OD demand conditions. These passengers only take the first train on each line and expect to complete their journeys in the minimum travel times. To minimize the passenger travel times, the flexible selection of travel routes in the network is permitted for passengers. Furthermore, the train-connection-based route is introduced to calculate the passenger travel times. In addition, to guarantee the service quality of nontransfer passengers, we minimize the deviation between the actual schedule and the optimized schedule on each line. Thus, a biobjective nonlinear integer programming model, which is subjected to train operation and connection constraints, is established. Then, NSGA-II is used to solve the proposed model, and an effective preprocessing method is proposed to speed up the computational times. Taking the Xi’an metro network as the background, several experiments are implemented to demonstrate the effectiveness and efficiency of the model and algorithm.As for this complex first-train timetable synchronization problem, our future studies will focus on the following aspects. First, a strict train capacity will be considered to model passenger travel behaviors. Second, it is necessary to establish some tractable linear optimization models and develop high-performance solution algorithms, as well as mathematical models under uncertain train operation and passenger travel conditions. Finally, it may be a better research direction to expand the research object from partial trains to all trains for the construction of full-day network-wide train timetables.



---

*Source: 8579354-2022-06-03.xml*