# Minimizing Metro Transfer Waiting Time with AFCS Data Using Simulated Annealing with Parallel Computing

Authors: Xiaobo Liu; Minghua Huang; Hezhou Qu; Steven Chien
Journal: Journal of Advanced Transportation
 (2018)

---

## Abstract

Coordinating train arrivals at transfer stations by altering their departure times can reduce transfer waiting time (TWT) and improve level of service. This paper develops a method to optimize train departure times from terminals that minimizes total TWT for an urban rail network with many transfer stations. To maintain service capacity and avoid operational complexity, dispatching headway is fixed. An integrated Simulated Annealing with parallel computing approach is applied to perform the optimization. To demonstrate model applicability and performance, the Shenzhen metro network is applied, where passenger flows (i.e., entry, transfer, and exit) at stations are approximated with the automatic fare collection system (AFCS) data. Results show that the total TWT can be significantly reduced.


---

## Body

## 1. Introduction

For large-scale metro networks, large numbers of passengers arrive simultaneously at transfer stations, especially during peak periods. Transfer time incurred by passengers has been considered as an index of service quality. Synchronizing vehicle arrival times to facilitate effective timed transfer is desirable.Transfer time is defined in this study as the elapsed time between a passenger alighting from a “delivery” train to boarding a “pickup” train, which consists of walking time between platforms and transfer waiting time (TWT) for the “pickup” train. Walking time is dependent on the layout of the station and walking speed, while TWT is affected by the arrival/departure times of the trains and walking time. To minimize TWT for a large metro network, the relationship between demand (i.e., spatiotemporal transfer passenger distribution) and supply (i.e., network configuration, service frequency, and departure time) must be carefully formulated.Automatic fare collection systems (AFCS) have been applied in many metro systems (i.e., Metro Card in New York, Oyster Card in London, etc.). With the AFCS data in this study, the temporal and spatial passenger entry/exit distributions and transfer volumes at stations can be determined. We aim to seek a quick and easy-to-implement method to effectively reduce TWT without increasing operator’s cost and operational complexity. To this end, we alter the train departure times from terminals but fix the dispatching headways. The research problem is combinatorial, which is difficult to solve with classic optimization methods. An integrated Simulated Annealing (SA) with parallel computing (PC) approach is developed to search for the solution that minimizes TWT.The remainder of this paper is structured as follows. Section2 describes previous research and practices related to this study. The development of the proposed model and solution method to solve the study problem are discussed in Sections 3 and 4, respectively. In Section 5, the Shenzhen Metro in China is employed as a case study to demonstrate the effectiveness of the solution algorithm and the benefits of the optimized solution. Finally, the paper concludes with a summary of findings and future research needs.


## 2. Literature Review

Coordinating train arrivals to facilitate transfer activities in a transit network offers an effective way to reduce transfer time. Transfer time is an important indicator representing the service quality and the efficiency of public transit systems [1–3]. Previous studies have focused on minimizing total waiting time [4–8] or maximizing the number of synchronized vehicle arrivals [9, 10] at transfer nodes. Recently, several studies focused on the first and last trains timetabling optimization, with objectives such as maximizing passenger transfer connection headways [11], minimizing the connection time between first trains [12], incorporating bilevel objectives in which the upper level maximizes social benefit (the number of passengers transferring to the last trains successfully) with minimum total subsidy and the lower level minimizes revenue loss for the operating companies [13], and maximizing the total number of successful transfer passengers and minimizing waiting times for rail-to-bus passengers [14].Several studies optimized coordination of transfers at a single hub station. Feng et al. [15] developed an optimization model for the arrival and departure times of connecting trains, which minimized average waiting time. Liu et al. [16] developed a multiobjective optimization model to minimize the total transfer waiting time, train operating cost, and fluctuation of departure interval with given transfer volumes. The optimized results were found using a genetic algorithm (GA). Chen and Wang [17] minimized passenger waiting time via synchronizing train arrivals and departures and revealed the relationships between three influencing factors (transfer forms, walking distance in the station, and congestion degree of passenger flow) and transfer time.Optimizing coordination among multiple transfer stations was conducted by previous studies. Assuming uniform passenger arrivals, Wong et al. [18] presented a mix-integer programming model to optimize nonperiodic timetable. A heuristic approach was employed to minimize the waiting time by justifying the train running time between stations, dwell times at stations, and departure and turnaround times at terminals. Fang et al. [19] minimized total waiting time yielded by the optimized vehicle arrival and departure times at transfer stations. Aksu and Akyol [20] optimized integer-ratio headways to minimize total cost. Considering random passenger arrivals, Liu et al. [21] minimized total waiting time by altering the train departure times found by SA. To improve transfer efficiency, Wu et al. [22] optimized vehicle departure time, headway, running time, and dwell time using GA.Considering probabilistic vehicle travel time, Chowdhury and Chien [23, 24] synchronized vehicle arrivals for an intermodal transit network to minimize total cost. The study network consisted of a train line with multiple transfer stations and multiple feeder bus routes connecting at the station. Shrivastava and Dhingra [25, 26] used GA to coordinate an integrated bus-train service which minimized total cost consisting of user and vehicle operating costs. Li et al. [27] optimized bus timetables for a feeder route which minimized total transfer wait time. Using GA and the Frank-Wolfe algorithm, Xiong et al. [28] synchronized arrivals of community shuttles linking with a metro service, which yielded the minimum total cost. Due to the absence of the AFCS data, the distribution of passenger arrivals at stations in most previous studies discussed above was either simplified or assumed. Few studies have applied the AFCS data for analyzing passenger demand and route choices [29–31] and optimizing timetable [32].The primary contribution of this study is to collect, process, and generate the spatiotemporal origin-destination (OD) demand with the AFCS data, approximate transfer volumes at stations, and apply that to minimize total TWT for a large metro network with many transfer stations. Optimizing such a coordinated transfer problem is challenging because it is combinatorial and difficult to solve with classic optimization methods. A method that integrates SA with PC (SAPC) is developed and implemented to search for the optimal solution.


## 3. Methodology

The mathematical model is formulated and discussed in this section, and the objective is to minimize total TWT. To maintain service capacity and avoid operational complexity, the preplanned dispatching headways are fixed. The decision variables therefore consist of train departure times from the beginning terminals of all lines in the study network. The development of the proposed model is discussed next, and the variables used to formulate the model are summarized in Table1.Table 1
Notations.
Variables Units Description A m i l / D m i l - Arrival / Departure time of trainm at station i of line l F l trains/hour Train frequency of linel h l min Headway of linel i / j / k - Index of stations (i,j,k∈N) l / l ′ - Index of lines (l,l′∈LT and l,l′=1,2,…,L) L T - The set of lines m / m ′ - Index of pick-up/delivery trains (m=1,2,…,Fl, and m′=1,2,…,Fl′) N - The set of stations q t i j s pass/s Number of passengers from stationsi to j via transfer station s at t r - Index of routes (r∈RT, and r=1,2,…,Ro) r m ′ l ′ , m l , s pass Number of transfer pass from trainm′ line l′ to train mline l at s r m ′ l ′ i , m l j , s pass Number of pass from sta.ito j on train m′ line l′ via train m line l at s r s / r l / r r min/pass Average TWT at transfer stations/ on line l/ on route r R min Total TWT R s / R l / R r min TWT at transfer stations/ on line l/ on route r R T - The set of routes s - Index of transfer stations (s∈ST, and s=1,2,…,S) S T - The set of transfer stations t - Index of time t m ′ l ′ , m l , s min TWT from trainm′ of line l′ to train m of line l at station s t l ′ l s min Walking time from linel′ to l at transfer station s t i j s min Passenger travel time from stationsi to jvia transfer station s t V i j s min In-vehicle time from stationsi to j via transfer station s v l min Adjustment of schedule departure time for trains on linel w i min Initial waiting time at stationi λ m ′ l ′ , m l , s - Binary var., 1 as passengers from trainm′ line l′ to train m line l via s; otherwise, 0 γ l s - Binary var., 1 as transfer stations is on line l; otherwise, 0 η r l - Binary var., 1 as linel belongs to route r; otherwise, 0


### 3.1. A General Metro Network

A general metro network consists of many routes defined asRT and a set of stations defined as N. A route is represented by two unidirectional lines (i.e., outbound and inbound). Line l belongs to a set of lines denoted as LT. Each line consists of a set of stations Nl, and Nl∈N. Each station is given a unique station ID. For example, station ID of line 1 begins with 1 and ends at N1, and then the IDs of stations on line 2 start from N1+1 and end at N2. Thus, stations of linel(l=2,3,…,L) are labeled from Nl-1+1 through Nl. For linel, the hourly service frequency is denoted as Fl, and a train is indexed bym (m=1,2,…,Fl). To formulate TWT incurred by passengers at a transfer station, a link-node diagram is shown in Figure 1 where transfer station s is also labelled as ul for line l as well as ul′ for line l′ (ul,ul′∈N). Transfer station s has four IDs associated with four connecting lines.Figure 1
Configuration of a general transfer station.To formulate the proposed model, the following assumptions are made and subsequently explained:(1)
The platform-to-platform walking time at a transfer station is given (obtainable from a survey or field observations), which may vary among stations(2)
Passenger arrival distributions at stations will not be affected by the change of train departure time(3)
The choice of transfer location(s) is determined based on the shortest travel time, which is the sum of initial waiting time, in-vehicle time, and TWT(4)
The number of passengers making more than two transfers to reach their destination is negligible(5)
Train running times between stations and dwell times at stations are deterministic within a period; however, they may vary over different periods


### 3.2. Demand Characteristics

In this study, the passenger OD demand distribution can be derived from the AFCS records. Passengers who access stationi are classified into two types, direct (without transfer) and indirect (with transfer), and they must swipe the card when entering and exiting a station. Note that indirect passengers do not need to swipe cards at transfer stations.


#### 3.2.1. Indirect Passenger Arrival Distribution

With the AFCS data, the temporal passenger arrival distribution at any stationi and their destination (stationj) can be determined; however, the transfer location is not available. As discussed in assumption (3), passengers would use the shortest travel time paths to reach their destinations. Since passenger arrival time at station i and posted train schedule are known, the travel path and transfer location(s) for each passenger can be determined by employing a time-dependent shortest path algorithm which will be discussed later in Section 3.2.2. Once the transfer location(s) is determined, the passengers who enter station i at time t and exit station j via transfer station s denoted as qtijs (see Figure 2) can be approximated.Figure 2
Temporal distribution of transfer passenger arrivals at origin stationi.Considering required platform-to-platform walking time, passengers can take trainm′ of line l′ to transfer station s and wait for train m of line l. For example, as train m′-1 of line l′ departs from station i at time Dm′-1,i,l′ and the following train m′ of line l′ departure time is Dm′il′, the number of indirect passengers (i.e., the shaded area in Figure 2) from station i to station j via transfer stations (denoted as rm′l′i,mlj,s) can be determined by time interval [Dm′-1,i,l′, Dm′il′), qtijs and transfer connection availability λm′l′,ml,s. Thus,(1)rm′l′i,mlj,s=∑t=Dm′-1,i,l′Dm′il′-1qijstλm′l′,ml,s,∀i,j,s,m′,l′,m,lNote thatλm′l′,ml,s is a binary variable. It is equal to 1 indicating that train m′ of line l′ arrives early, so that successful transfer can be made to train m line l ats; otherwise, it is 0. Thus,(2)λm′l′,ml,s=1;Dmsl>Am′sl′+tl′lsTrainsm′andmare connected0;Dmsl≤Am′sl′+tl′lsOtherwise


#### 3.2.2. Enhanced Dijkstra Algorithm (EDA)

The shortest path of a network where the travel time is not time-dependent can be found by applying the Dijkstra algorithm (DA) [33]. Otherwise, an enhanced Dijkstra algorithm (EDA) shall be developed for dealing with the time-dependent travel time. The train arrival and departure time at various stations will be recorded using actual time schedule, which is different from starting at zero time used in DA. A brief discussion of the proposed EDA is summarized below.The travel time of a path is dependent on the passengers’ arrival time at the origin station. To determine the shortest in-vehicle time from stationi to stationk, all links which have their start station ID equal to station i and end station ID equal to station k can be searched through the network layout (note that the metro network has specific direction of operation for each line). For each of these links, the first train departure time at station i which is greater than the passenger arrival time at station i can be obtained by the timetables. The train and passenger arrival time at station k when traveling by this link is equal to the corresponding departure time of the start station i plus the travel time from the start station i to the end station k of the link which can be extracted by the timetables, too.If a transfer is needed at a station, transfer time must be included in the travel time of the appropriate link. Note that transfer times vary with different transfer stations. The link which gets the shortest travel time (including the passenger initial waiting time at origin station, in-vehicle time, and transfer waiting time) from stationsi to k is chosen as the shortest path. The proposed algorithm will find the shortest paths for all passengers from the origin station to destination station.Transfer passengersqtijs will select the best transfer location s to minimize their travel time denoted as tijs. Thus,(3)min⁡tijs,∀i,j,sNote that tijs is the sum of initial waiting time, in-vehicle time, and TWT. Thus,(4)tijs=wi+tVijs+tm′l′,ml,swhere the initial waiting time, wi, is the time for passengers who wait for boarding on train m′ of line l′ at stationi, which is the elapsed time from passenger arrival time t to the train departure time Dm′il′. Thus,(5)wi=Dm′il′-tThe in-vehicle time, denoted astVijs, includes the in-vehicle time from station i of line l′ to transfer station s and then to station j of line l. Thus,(6)tVijs=Am′sl′-Dm′il′+Amjl-Dmslwhere Amil and Dmil represent the arrival and departure times of train m on line l at stationi, respectively. Finally, tm′l′,ml,s can be calculated by (7).


#### 3.2.3. Transfer Passengers

As discussed earlier, we assume that passengers would use transfer station(s), if necessary, which minimizes their travel time. For passengers who expect to transfer from trainm′ of line l′ to train m of line l ats, the TWT denoted as tm′l′,ml,s is determined by the departure time of pickup train m denoted as Dmsl and the arrival time of delivery train m′ denoted as Am′sl′, the platform-to-platform walking time is tl′ls, and transfer connection availability is λm′l′,ml,s. Thus,(7)tm′l′,ml,s=Dmsl-Am′sl′-tl′lsλm′l′,mls,∀m′,l′,m,l,sIn the interest of simplicity, the average walking time is distance divided by walking speed. Since each “route” is split into two unidirectional lines, there are eight transfer flows at a general stations. The number of transfer passengers from train m′ of line l′ to train m of line l at s is denoted as rm′l′,ml,s, which can be calculated by(8)rm′l′,ml,s=∑i=Nl′-1+1ul′-1∑j=ul+1Nlrm′l′i,mlj,s,∀m′,l′,m,l,sNote that rm′l′i,mlj,s can be determined by (1).


### 3.3. Objective Function

It is worth noting that the average access time for passengers swiping metro cards, entering the station, and walking to the boarding area is given, which will not affect the optimized solution and thus can be omitted. The objective total TWT denoted asR is the sum of TWT incurred by all transfer passengers. Thus,(9)R=∑s=1S∑l=1L∑m=1Fl∑l′=1L∑m′=1Fl′rm′l′,ml,stm′l′,ml,swhere tm′l′,ml,s is affected by the justification of train departure times at the beginning terminal of linel (i.e., the decision variable, denoted as vl). The objective is to minimizeR; therefore, the objective function is(10)min⁡R


### 3.4. Constraints

To maintain service capacity without increasing the operation cost, the service headway of each line is not varied. Therefore, the constraints considered in most previous studies, such as capacity and fleet size constraints, will not be our concerns. The relation among the “delivering” train arrival time, walking time, and “pickup” train departure time will be employed to minimize total TWT. When the departure time of trainm of line l at stations(Dmsl) is greater than the arrival time of train m′ line l′ (Am′sl′) plus walking time (tl′ls), transfers can be successfully made and λm′l′,ml,s is equal to 1. Thus,(11)Dmsl>Am′sl′+tl′ls,∀m,l,sNote that only one pickup train m of line l has connectivity with delivery train m′ of line l′. Thus,(12)∑m=1Flλm′l′,ml,s=1,∀m′,l′,m,l,swhere Fl represents the service frequency on linel.


### 3.5. Performance Analysis

To evaluate the effectiveness of the optimized solution on system operation, we propose to investigate total and average TWT at different level of detail. Equations to assess system performance are formulated and discussed below.


#### 3.5.1. Transfer Waiting Time (TWT)

The station-based total TWT, denoted asRs, is the sum of TWT incurred by transfer passengers at transfer stations s. Thus,(13)Rs=∑l=1L∑m=1Fl∑l′=1L∑m′=1Fl′rm′l′,ml,stm′l′,ml,s,∀sThe line-based total TWT, denoted asRl, is the sum of TWT incurred by transfer passengers at all transfer stations from other lines to line l. Thus,(14)Rl=∑s=1S∑m=1Fl∑l′=1L∑m′=1Fl′rm′l′,ml,stm′l′,ml,sγls,∀lwhere γls equal to 1 means that station s is on linel; otherwise, it is 0. Thus,(15)γls=1;Transfer stationson linel0;OtherwiseThe route-based total TWT, denoted asRr, is the sum of TWT consumed on the two lines associated with route r. Thus,(16)Rr=∑l=1LRlηrl,∀rwhere ηrl equal to 1 means that line l is associated with route r. Otherwise, it is 0. Thus,(17)ηrl=1;Linelbelongs to Router0;Otherwise


#### 3.5.2. Average Transfer Waiting Time

The average TWT ats, denoted as rs, is total TWT divided by the number of transfer passengers. Thus,(18)rs=Rs∑l=1L∑m=1Fl∑l′=1L∑m′=1Fl′rm′l′,ml,s,∀sThe average TWT of linel, denoted as rl, is Rl divided by the number of transfer passengers of line l. Thus,(19)rl=Rl∑s=1S∑m=1Fl∑l′=1L∑m′=1Fl′rm′l′,ml,sγls,∀lSimilarly, the average TWT of router, denoted as rr, is Rr divided by the number of transfer passengers of route r. Thus,(20)rr=Rr∑l=1Lrlηl,∀r


## 3.1. A General Metro Network

A general metro network consists of many routes defined asRT and a set of stations defined as N. A route is represented by two unidirectional lines (i.e., outbound and inbound). Line l belongs to a set of lines denoted as LT. Each line consists of a set of stations Nl, and Nl∈N. Each station is given a unique station ID. For example, station ID of line 1 begins with 1 and ends at N1, and then the IDs of stations on line 2 start from N1+1 and end at N2. Thus, stations of linel(l=2,3,…,L) are labeled from Nl-1+1 through Nl. For linel, the hourly service frequency is denoted as Fl, and a train is indexed bym (m=1,2,…,Fl). To formulate TWT incurred by passengers at a transfer station, a link-node diagram is shown in Figure 1 where transfer station s is also labelled as ul for line l as well as ul′ for line l′ (ul,ul′∈N). Transfer station s has four IDs associated with four connecting lines.Figure 1
Configuration of a general transfer station.To formulate the proposed model, the following assumptions are made and subsequently explained:(1)
The platform-to-platform walking time at a transfer station is given (obtainable from a survey or field observations), which may vary among stations(2)
Passenger arrival distributions at stations will not be affected by the change of train departure time(3)
The choice of transfer location(s) is determined based on the shortest travel time, which is the sum of initial waiting time, in-vehicle time, and TWT(4)
The number of passengers making more than two transfers to reach their destination is negligible(5)
Train running times between stations and dwell times at stations are deterministic within a period; however, they may vary over different periods


## 3.2. Demand Characteristics

In this study, the passenger OD demand distribution can be derived from the AFCS records. Passengers who access stationi are classified into two types, direct (without transfer) and indirect (with transfer), and they must swipe the card when entering and exiting a station. Note that indirect passengers do not need to swipe cards at transfer stations.


### 3.2.1. Indirect Passenger Arrival Distribution

With the AFCS data, the temporal passenger arrival distribution at any stationi and their destination (stationj) can be determined; however, the transfer location is not available. As discussed in assumption (3), passengers would use the shortest travel time paths to reach their destinations. Since passenger arrival time at station i and posted train schedule are known, the travel path and transfer location(s) for each passenger can be determined by employing a time-dependent shortest path algorithm which will be discussed later in Section 3.2.2. Once the transfer location(s) is determined, the passengers who enter station i at time t and exit station j via transfer station s denoted as qtijs (see Figure 2) can be approximated.Figure 2
Temporal distribution of transfer passenger arrivals at origin stationi.Considering required platform-to-platform walking time, passengers can take trainm′ of line l′ to transfer station s and wait for train m of line l. For example, as train m′-1 of line l′ departs from station i at time Dm′-1,i,l′ and the following train m′ of line l′ departure time is Dm′il′, the number of indirect passengers (i.e., the shaded area in Figure 2) from station i to station j via transfer stations (denoted as rm′l′i,mlj,s) can be determined by time interval [Dm′-1,i,l′, Dm′il′), qtijs and transfer connection availability λm′l′,ml,s. Thus,(1)rm′l′i,mlj,s=∑t=Dm′-1,i,l′Dm′il′-1qijstλm′l′,ml,s,∀i,j,s,m′,l′,m,lNote thatλm′l′,ml,s is a binary variable. It is equal to 1 indicating that train m′ of line l′ arrives early, so that successful transfer can be made to train m line l ats; otherwise, it is 0. Thus,(2)λm′l′,ml,s=1;Dmsl>Am′sl′+tl′lsTrainsm′andmare connected0;Dmsl≤Am′sl′+tl′lsOtherwise


### 3.2.2. Enhanced Dijkstra Algorithm (EDA)

The shortest path of a network where the travel time is not time-dependent can be found by applying the Dijkstra algorithm (DA) [33]. Otherwise, an enhanced Dijkstra algorithm (EDA) shall be developed for dealing with the time-dependent travel time. The train arrival and departure time at various stations will be recorded using actual time schedule, which is different from starting at zero time used in DA. A brief discussion of the proposed EDA is summarized below.The travel time of a path is dependent on the passengers’ arrival time at the origin station. To determine the shortest in-vehicle time from stationi to stationk, all links which have their start station ID equal to station i and end station ID equal to station k can be searched through the network layout (note that the metro network has specific direction of operation for each line). For each of these links, the first train departure time at station i which is greater than the passenger arrival time at station i can be obtained by the timetables. The train and passenger arrival time at station k when traveling by this link is equal to the corresponding departure time of the start station i plus the travel time from the start station i to the end station k of the link which can be extracted by the timetables, too.If a transfer is needed at a station, transfer time must be included in the travel time of the appropriate link. Note that transfer times vary with different transfer stations. The link which gets the shortest travel time (including the passenger initial waiting time at origin station, in-vehicle time, and transfer waiting time) from stationsi to k is chosen as the shortest path. The proposed algorithm will find the shortest paths for all passengers from the origin station to destination station.Transfer passengersqtijs will select the best transfer location s to minimize their travel time denoted as tijs. Thus,(3)min⁡tijs,∀i,j,sNote that tijs is the sum of initial waiting time, in-vehicle time, and TWT. Thus,(4)tijs=wi+tVijs+tm′l′,ml,swhere the initial waiting time, wi, is the time for passengers who wait for boarding on train m′ of line l′ at stationi, which is the elapsed time from passenger arrival time t to the train departure time Dm′il′. Thus,(5)wi=Dm′il′-tThe in-vehicle time, denoted astVijs, includes the in-vehicle time from station i of line l′ to transfer station s and then to station j of line l. Thus,(6)tVijs=Am′sl′-Dm′il′+Amjl-Dmslwhere Amil and Dmil represent the arrival and departure times of train m on line l at stationi, respectively. Finally, tm′l′,ml,s can be calculated by (7).


### 3.2.3. Transfer Passengers

As discussed earlier, we assume that passengers would use transfer station(s), if necessary, which minimizes their travel time. For passengers who expect to transfer from trainm′ of line l′ to train m of line l ats, the TWT denoted as tm′l′,ml,s is determined by the departure time of pickup train m denoted as Dmsl and the arrival time of delivery train m′ denoted as Am′sl′, the platform-to-platform walking time is tl′ls, and transfer connection availability is λm′l′,ml,s. Thus,(7)tm′l′,ml,s=Dmsl-Am′sl′-tl′lsλm′l′,mls,∀m′,l′,m,l,sIn the interest of simplicity, the average walking time is distance divided by walking speed. Since each “route” is split into two unidirectional lines, there are eight transfer flows at a general stations. The number of transfer passengers from train m′ of line l′ to train m of line l at s is denoted as rm′l′,ml,s, which can be calculated by(8)rm′l′,ml,s=∑i=Nl′-1+1ul′-1∑j=ul+1Nlrm′l′i,mlj,s,∀m′,l′,m,l,sNote that rm′l′i,mlj,s can be determined by (1).


## 3.2.1. Indirect Passenger Arrival Distribution

With the AFCS data, the temporal passenger arrival distribution at any stationi and their destination (stationj) can be determined; however, the transfer location is not available. As discussed in assumption (3), passengers would use the shortest travel time paths to reach their destinations. Since passenger arrival time at station i and posted train schedule are known, the travel path and transfer location(s) for each passenger can be determined by employing a time-dependent shortest path algorithm which will be discussed later in Section 3.2.2. Once the transfer location(s) is determined, the passengers who enter station i at time t and exit station j via transfer station s denoted as qtijs (see Figure 2) can be approximated.Figure 2
Temporal distribution of transfer passenger arrivals at origin stationi.Considering required platform-to-platform walking time, passengers can take trainm′ of line l′ to transfer station s and wait for train m of line l. For example, as train m′-1 of line l′ departs from station i at time Dm′-1,i,l′ and the following train m′ of line l′ departure time is Dm′il′, the number of indirect passengers (i.e., the shaded area in Figure 2) from station i to station j via transfer stations (denoted as rm′l′i,mlj,s) can be determined by time interval [Dm′-1,i,l′, Dm′il′), qtijs and transfer connection availability λm′l′,ml,s. Thus,(1)rm′l′i,mlj,s=∑t=Dm′-1,i,l′Dm′il′-1qijstλm′l′,ml,s,∀i,j,s,m′,l′,m,lNote thatλm′l′,ml,s is a binary variable. It is equal to 1 indicating that train m′ of line l′ arrives early, so that successful transfer can be made to train m line l ats; otherwise, it is 0. Thus,(2)λm′l′,ml,s=1;Dmsl>Am′sl′+tl′lsTrainsm′andmare connected0;Dmsl≤Am′sl′+tl′lsOtherwise


## 3.2.2. Enhanced Dijkstra Algorithm (EDA)

The shortest path of a network where the travel time is not time-dependent can be found by applying the Dijkstra algorithm (DA) [33]. Otherwise, an enhanced Dijkstra algorithm (EDA) shall be developed for dealing with the time-dependent travel time. The train arrival and departure time at various stations will be recorded using actual time schedule, which is different from starting at zero time used in DA. A brief discussion of the proposed EDA is summarized below.The travel time of a path is dependent on the passengers’ arrival time at the origin station. To determine the shortest in-vehicle time from stationi to stationk, all links which have their start station ID equal to station i and end station ID equal to station k can be searched through the network layout (note that the metro network has specific direction of operation for each line). For each of these links, the first train departure time at station i which is greater than the passenger arrival time at station i can be obtained by the timetables. The train and passenger arrival time at station k when traveling by this link is equal to the corresponding departure time of the start station i plus the travel time from the start station i to the end station k of the link which can be extracted by the timetables, too.If a transfer is needed at a station, transfer time must be included in the travel time of the appropriate link. Note that transfer times vary with different transfer stations. The link which gets the shortest travel time (including the passenger initial waiting time at origin station, in-vehicle time, and transfer waiting time) from stationsi to k is chosen as the shortest path. The proposed algorithm will find the shortest paths for all passengers from the origin station to destination station.Transfer passengersqtijs will select the best transfer location s to minimize their travel time denoted as tijs. Thus,(3)min⁡tijs,∀i,j,sNote that tijs is the sum of initial waiting time, in-vehicle time, and TWT. Thus,(4)tijs=wi+tVijs+tm′l′,ml,swhere the initial waiting time, wi, is the time for passengers who wait for boarding on train m′ of line l′ at stationi, which is the elapsed time from passenger arrival time t to the train departure time Dm′il′. Thus,(5)wi=Dm′il′-tThe in-vehicle time, denoted astVijs, includes the in-vehicle time from station i of line l′ to transfer station s and then to station j of line l. Thus,(6)tVijs=Am′sl′-Dm′il′+Amjl-Dmslwhere Amil and Dmil represent the arrival and departure times of train m on line l at stationi, respectively. Finally, tm′l′,ml,s can be calculated by (7).


## 3.2.3. Transfer Passengers

As discussed earlier, we assume that passengers would use transfer station(s), if necessary, which minimizes their travel time. For passengers who expect to transfer from trainm′ of line l′ to train m of line l ats, the TWT denoted as tm′l′,ml,s is determined by the departure time of pickup train m denoted as Dmsl and the arrival time of delivery train m′ denoted as Am′sl′, the platform-to-platform walking time is tl′ls, and transfer connection availability is λm′l′,ml,s. Thus,(7)tm′l′,ml,s=Dmsl-Am′sl′-tl′lsλm′l′,mls,∀m′,l′,m,l,sIn the interest of simplicity, the average walking time is distance divided by walking speed. Since each “route” is split into two unidirectional lines, there are eight transfer flows at a general stations. The number of transfer passengers from train m′ of line l′ to train m of line l at s is denoted as rm′l′,ml,s, which can be calculated by(8)rm′l′,ml,s=∑i=Nl′-1+1ul′-1∑j=ul+1Nlrm′l′i,mlj,s,∀m′,l′,m,l,sNote that rm′l′i,mlj,s can be determined by (1).


## 3.3. Objective Function

It is worth noting that the average access time for passengers swiping metro cards, entering the station, and walking to the boarding area is given, which will not affect the optimized solution and thus can be omitted. The objective total TWT denoted asR is the sum of TWT incurred by all transfer passengers. Thus,(9)R=∑s=1S∑l=1L∑m=1Fl∑l′=1L∑m′=1Fl′rm′l′,ml,stm′l′,ml,swhere tm′l′,ml,s is affected by the justification of train departure times at the beginning terminal of linel (i.e., the decision variable, denoted as vl). The objective is to minimizeR; therefore, the objective function is(10)min⁡R


## 3.4. Constraints

To maintain service capacity without increasing the operation cost, the service headway of each line is not varied. Therefore, the constraints considered in most previous studies, such as capacity and fleet size constraints, will not be our concerns. The relation among the “delivering” train arrival time, walking time, and “pickup” train departure time will be employed to minimize total TWT. When the departure time of trainm of line l at stations(Dmsl) is greater than the arrival time of train m′ line l′ (Am′sl′) plus walking time (tl′ls), transfers can be successfully made and λm′l′,ml,s is equal to 1. Thus,(11)Dmsl>Am′sl′+tl′ls,∀m,l,sNote that only one pickup train m of line l has connectivity with delivery train m′ of line l′. Thus,(12)∑m=1Flλm′l′,ml,s=1,∀m′,l′,m,l,swhere Fl represents the service frequency on linel.


## 3.5. Performance Analysis

To evaluate the effectiveness of the optimized solution on system operation, we propose to investigate total and average TWT at different level of detail. Equations to assess system performance are formulated and discussed below.


### 3.5.1. Transfer Waiting Time (TWT)

The station-based total TWT, denoted asRs, is the sum of TWT incurred by transfer passengers at transfer stations s. Thus,(13)Rs=∑l=1L∑m=1Fl∑l′=1L∑m′=1Fl′rm′l′,ml,stm′l′,ml,s,∀sThe line-based total TWT, denoted asRl, is the sum of TWT incurred by transfer passengers at all transfer stations from other lines to line l. Thus,(14)Rl=∑s=1S∑m=1Fl∑l′=1L∑m′=1Fl′rm′l′,ml,stm′l′,ml,sγls,∀lwhere γls equal to 1 means that station s is on linel; otherwise, it is 0. Thus,(15)γls=1;Transfer stationson linel0;OtherwiseThe route-based total TWT, denoted asRr, is the sum of TWT consumed on the two lines associated with route r. Thus,(16)Rr=∑l=1LRlηrl,∀rwhere ηrl equal to 1 means that line l is associated with route r. Otherwise, it is 0. Thus,(17)ηrl=1;Linelbelongs to Router0;Otherwise


### 3.5.2. Average Transfer Waiting Time

The average TWT ats, denoted as rs, is total TWT divided by the number of transfer passengers. Thus,(18)rs=Rs∑l=1L∑m=1Fl∑l′=1L∑m′=1Fl′rm′l′,ml,s,∀sThe average TWT of linel, denoted as rl, is Rl divided by the number of transfer passengers of line l. Thus,(19)rl=Rl∑s=1S∑m=1Fl∑l′=1L∑m′=1Fl′rm′l′,ml,sγls,∀lSimilarly, the average TWT of router, denoted as rr, is Rr divided by the number of transfer passengers of route r. Thus,(20)rr=Rr∑l=1Lrlηl,∀r


## 3.5.1. Transfer Waiting Time (TWT)

The station-based total TWT, denoted asRs, is the sum of TWT incurred by transfer passengers at transfer stations s. Thus,(13)Rs=∑l=1L∑m=1Fl∑l′=1L∑m′=1Fl′rm′l′,ml,stm′l′,ml,s,∀sThe line-based total TWT, denoted asRl, is the sum of TWT incurred by transfer passengers at all transfer stations from other lines to line l. Thus,(14)Rl=∑s=1S∑m=1Fl∑l′=1L∑m′=1Fl′rm′l′,ml,stm′l′,ml,sγls,∀lwhere γls equal to 1 means that station s is on linel; otherwise, it is 0. Thus,(15)γls=1;Transfer stationson linel0;OtherwiseThe route-based total TWT, denoted asRr, is the sum of TWT consumed on the two lines associated with route r. Thus,(16)Rr=∑l=1LRlηrl,∀rwhere ηrl equal to 1 means that line l is associated with route r. Otherwise, it is 0. Thus,(17)ηrl=1;Linelbelongs to Router0;Otherwise


## 3.5.2. Average Transfer Waiting Time

The average TWT ats, denoted as rs, is total TWT divided by the number of transfer passengers. Thus,(18)rs=Rs∑l=1L∑m=1Fl∑l′=1L∑m′=1Fl′rm′l′,ml,s,∀sThe average TWT of linel, denoted as rl, is Rl divided by the number of transfer passengers of line l. Thus,(19)rl=Rl∑s=1S∑m=1Fl∑l′=1L∑m′=1Fl′rm′l′,ml,sγls,∀lSimilarly, the average TWT of router, denoted as rr, is Rr divided by the number of transfer passengers of route r. Thus,(20)rr=Rr∑l=1Lrlηl,∀r


## 4. Solution Algorithm

To minimize total TWT for a large metro network consisting of multiple lines intersecting at many stations, the study problem is combinatorial with large feasible solution spaces. The developed model is therefore difficult to solve with classic optimization methods. With SA, the computation time could be long due to large passenger demand, number of running trains, and the size of the study network. The primary reasons for using PC (splitting large problems into smaller ones that are solved simultaneously) are to save time, to solve larger problems, and to provide concurrency [34].We thus apply an integrated SA with PC (using MATLAB software) to search for the optimized solution and compute the objective total TWT. The procedure is discussed below and illustrated in Figure3.Figure 3
Step procedure of the proposed SAPC.Step 1 (initialization).
Input SA parameters (i.e., initial solution, temperature, upper and lower bounds, etc.) and baseline model parameter values (i.e., train arrival and departure times of the existing timetable.Step 2.
With initialized information, open the parallel pool and calculate total TWT denoted asR0 (see (9)) with PC (split the execution of calculation in serial over the workers in a parallel pool). Let Rx=R0. Set the index of SA temperature iterationz = 0.Step 3.
Search for a provisionalvl with SA, determine Dm1l, and calculate total TWT denoted as Ry with PC. Let u=u+1. Note that Dm1l is updated based on vl, which must be satisfied with(21)Dm1l=Dm1l0+vl,Dm1l∈0,Twhere the planning time horizon of departure time is denoted as [0,T]. Therefore, the adjusted departure time Dmil and arrival time Amil at each station can be derived accordingly based on the existing departure time D0mil and arrival time A0mil. Thus,(22)Dmil=Dmil0+vl(23)Amil=Amil0+vlwhere the allowable adjustment range of vl is deviating within the dispatching headway of linel, denoted as hl. Thus,(24)-hl2<vl<hl2Step 4.
CompareRx and Ry. If Ry⩾Rx, go to Step 5; otherwise, let Rx=Ry and denote the current solution as the provisional solution; then go to Step 6.Step 5.
Verify the Metropolis criterion. Calculate∆Rxy=Ry-Rx. If exp⁡-∆Rxy/tz>ε (ε is a random number), ε∈(0,1), let Rx=Ry; otherwise, go to Step 6.Step 6.
Reduction criteria of temperature: ifu>U,tz+1=αtz, repetition counteru= 0, go to Step 7; otherwise, go to Step 3. Setz =z+1.Step 7.
Check if the stop criteria (e.g., maximum iterationZ) are satisfied. If positive, go to Step 8; otherwise, go to Step 3.Step 8.
Terminate SA search and output the optimized solutionsv∗l, D∗m1l, D∗mil, A∗mil, and R∗. Update train arrival and departure times at each station based on the results from(25)Dmil∗=Dmil0+vl∗(26)Amil∗=Amil0+vl∗


## 5. Case Study

### 5.1. Study Metro Network and Associated Data

The case study employs the year 2013 metro network in Shenzhen, China, consisting of 5 routes intersecting at 13 transfer stations. Considering inbound and outbound traffic, the network is represented by 10 directional lines with 262 stations as shown in Figure4. The baseline model parameter values were provided by the operating agency, including a spatiotemporal passenger OD demand matrix, timetables, and average passenger walking time from one line to another at each transfer station.Figure 4
The studied Shenzhen metro network.The ridership distribution over time on a typical weekday is shown in Figure5. In addition to minimizing total TWT, the benefit before and after the implementation of the optimized solution will be assessed.Figure 5
Temporal distribution of ridership.To demonstrate the model performance applied in different levels of congestion for the metro network, we apply the AFCS data collected in the AM peak (i.e., 8:00 am ~ 9:00 am) and off-peak (i.e., 12:00 pm ~ 1:00 pm). There are 111,887 and 17,984 transfer passengers in AM peak and off-peak, respectively, which resulted in transfer volumes of 138,702 and 22,107 because some passengers need more than one transfer. The input data include train departure and arrival times, transfer walking time, and other operator parameters, which are summarized in AppendicesA and B.


### 5.2. Passenger Demand

When a passenger either enters or exits a station, the time is reported and archived in AFCS. Thus, the passenger in- and out-flow distributions can be accurately derived. Table2 illustrates the sample data extracted from the AFCS database, which include passenger ID, transaction time (entering and exiting a station), line/station ID where a transaction occurred, and transaction type. The sample data represent trips initiated by two passengers (i.e., ID 32286198 and ID 322357672). Passenger 32286198 began his/her journey from Station 218 and ended at Station 230 on line 9, who traveled without transfer. The same passenger initiated the 2nd trip in the afternoon on the same day. On the other hand, passenger 322357672 began his/her trip from Station 33 of line 2, transfer at station s2, and then ended that trip at Station 86 of line 3.Table 2
Sample data from AFCS.
PassengerNo. Card ID Transaction time stamp Line ID Station ID Transaction type 1 322861698 2013-10-16 08:26:18 9 218 Entry 322861698 2013-10-16 09:00:35 9 230 Exit 322861698 2013-10-16 13:31:17 10 241 Entry 322861698 2013-10-16 14:07:50 10 253 Exit  2 322357672 2013-10-16 07:54:19 2 33 Entry 322357672 2013-10-16 08:50:52 3 86 Exit 322357672 2013-10-16 11:40:27 4 93 Entry 322357672 2013-10-16 12:57:47 1 28 ExitAs shown in Table3, the transfer demand matrix at a transfer station s1 records transfer volume at each of 8 transfer directions (see Figure 1).Table 3
Train-to-train transfer demand at stations1.
Line ID 1 2 3 4 1 - - r m ’ 1 , m 3 , s 1 r m ’ 1 , m 4 , s 1 2 - - r m ’ 2 , m 3 , s 1 r m ’ 2 , m 4 , s 1 3 r m ’ 3 , m 1 , s 1 r m ’ 3 , m 2 , s 1 - - 4 r m ’ 4 , m 1 , s 1 r m ’ 4 , m 2 , s 1 - -


### 5.3. Optimized Results

The SA parameter values include initial temperaturet0=10,000, reduction parameter of temperature α=0.9, number of temperature iterationsZ= 1,000, and number of iterations at current temperatureU=100.For the AM peak, the computation time to search for the optimized solution using SA requires 85.7 hours to yield the minimum total cost (Intel(R) Xeon(R) CPU E5-1620 v4 @3.50 GHz 3.50 GHz with 32.0 GB RAM and 64-bit Operating System). However, SAPC requires 8.5 hours to yield the optimized result.For the off-peak, the computation time with SA only was 8.5 hours, which is significantly less than that for the AM peak because of less transfer demand and reduced service frequency. It was found in Table4 that as the transfer demand is reduced (i.e., off-peak) using SAPC seems inefficient (i.e., 9.5 hours) which costs more computation time to find the optimized solution than that of solely using SA (i.e., 8.5 hours). This computing in serial loops generally does not benefit from conversion into PC method for a relatively simple computational task in off-peak. Because the time needed for data transfer is significant compared with the time needed for computation, therefore, the results show that the PC method can be useful for some loop iterations that require long times to execute with big data.Table 4
Results from different solution algorithms.
AM peak (Off Peak) Solution algorithm Computation time(hr) Minimized TWT(min) Reduced TWT(min) SAPC 8.5 (9.5) 276,194.1 (65,464.7) 41,851.9 (9,822.8) SA 85.7 (8.5) 283,626.3 (65,481.1) 34,419.7 (9,806.4)The total TWT of the studied AM peak and off-peak were significantly reduced by 41,851.9 minutes and 9,822.8 minutes, respectively, after implementing the adjusted train departure times at the beginning stations. The yielded minimum total TWT by the solutions found using SA and SAPC are fairly close, which indicates that SAPC is very efficient.Figure6 shows the relationship between total TWT and the number of iterations using SAPC. It is notable that total TWT was reduced quickly at the first 200 iterations and then stably converged to a constant after the 500th iteration.Figure 6
Total TWT vs. iteration with SAPC (AM and off-peak).Results under existing operation (EO) and optimized operation (OO) are compared in this section. EO refers to train departures following the existing timetable, while OO refers to the fact that trains will be dispatched based on the optimized departure times. The difference between the departure times at the beginning terminal with EO and OO of linel denoted as vl is shown in Figure 7. It was found that the trains of lines 1, 4, 5, 8, and 10 should be dispatched later than the existing schedule (i.e., 32, 150, 14, 29, and 43 seconds, respectively), while trains operating on lines 2, 3, 6, 7, and 9 should be dispatched earlier (i.e., -2, -104, -50, -72, and -45 seconds) in the AM peak. However, in the off-peak hour all the trains’ departure times should be dispatched earlier than the existing schedule (i.e., negative values: -179, -174, -103, -55, -209, -142, -38, -82, -46, and -112 sec).Figure 7
Optimized adjustment of departure times with SAPC (AM and off-peak).


### 5.4. Before and after Analysis

With SAPC, the proposed model is applied to optimize train departure times from the terminals in the studied time periods. There are 148 trains dispatched during the AM peak and 85 trains dispatched in the off-peak.


#### 5.4.1. TWT at Transfer Stations

As indicated in Table5 and Figure 8, total TWT was reduced by 13.2% (i.e., 41,851.9 minutes) after adjusting the departure times within the AM peak. The greatest TWT saving occurred at station s10, whereas increased TWT was found at s6, s8, and s13 with relatively low transfer volumes.Table 5
Comparison of station-based TWT.
Transfer station Transfer volume(pass) Total TWT(min) Average TWT (min/pass) Difference (min) Percentagechange ID EO OO EO OO EO OO AM peak  s 1 6,432 6,440 10,852.2 9,737.8 1.69 1.51 -1,114.4 -10.3% s 2 10,619 10,611 21,509.3 21,461.3 2.03 2.02 -48.0 -0.2% s 3 23,724 23,821 43,244.5 28,801.8 1.82 1.21 -14,442.7 -33.4% s 4 13,454 13,357 24,206.6 21,443.3 1.80 1.61 -2,763.3 -11.4% s 5 8,833 8,833 15,655.4 14,805.4 1.77 1.68 -850.0 -5.4% s 6 537 507 1,877.2 1,951.4 3.50 3.85 74.2 +4.0% s 7 12,126 12,156 31,194.6 27,383.0 2.57 2.25 -3,811.6 -12.2% s 8 3,350 3,339 10,062.2 11,165.9 3.00 3.34 1,103.7 +11.0% s 9 7,163 7,163 21,913.5 20,286.9 3.06 2.83 -1,626.6 -7.4% s 10 10,381 10,381 27,064.7 13,294.9 2.61 1.28 -13,769.8 -50.9% s 11 17,579 17,590 56,087.6 51,749.4 3.19 2.94 -4,338.2 -7.7% s 12 10,327 10,327 25,926.3 24,517.6 2.51 2.37 -1,408.7 -5.4% s 13 14,177 14,177 28,451.9 29,595.4 2.01 2.09 1,143.5 +4.0% Total 138,702 138,702 318,046.0 276,194.1 2.29 1.99 -41,851.9 -13.2%  Off-peak  s 1 1,240 1,247 4,095.7 3,987.4 3.30 3.20 -108.3 -2.6% s 2 1,425 1,452 4,744.4 4,717.0 3.33 3.25 -27.4 -0.6% s 3 3,632 3,655 11,915.3 10,400.0 3.28 2.85 -1,515.3 -12.7% s 4 1,331 1,229 4,010.4 3,770.0 3.01 3.07 -240.4 -6.0% s 5 2,595 2,466 9,256.5 5,325.8 3.57 2.16 -3,930.7 -42.5% s 6 50 51 173.8 200.0 3.48 3.92 26.2 +15.1% s 7 1,718 1,726 6,000.5 5,270.3 3.49 3.05 -730.2 -12.2% s 8 610 603 2,318.5 2,091.2 3.80 3.47 -227.3 -9.8% s 9 1,464 1,528 5,441.7 5,260.4 3.72 3.44 -181.3 -3.3% s 10 1,022 1,065 2,853.1 1,629.9 2.79 1.53 -1,223.2 -42.9% s 11 2,199 2,210 7,709.3 7,099.0 3.51 3.21 -610.3 -7.9% s 12 2,100 2,052 7,731.3 6,372.1 3.68 3.11 -1,359.2 -17.6% s 13 2,721 2,823 9,037.0 9,341.6 3.32 3.31 304.6 +3.4% Total 22,107 22,107 75,287.5 65,464.7 3.41 2.96 -9,822.8 -13.0%Figure 8
Total TWT with EO and OO at various transfer stations.In the off-peak period (see Table5), total TWT was reduced by 13.0% (9,822.8 minutes) compared to that with EO. The greatest saving was found at s5 and the least average TWT was found at s10. It is worth noting that the choice of transfer location(s) is based on the shortest travel time, which has been discussed in the assumptions. The transfer volumes before and after optimization at transfer stations have changed because passengers selected different locations to make transfer, since the justified train departure times have altered their shortest paths.


#### 5.4.2. TWT by Lines

The comparison of TWT by lines is shown in Table6. For the AM peak on line 1 (outbound direction of route A, Figure 9), there is a transfer volume of 33,183 passengers who transfer from lines 3 through 10, which accounts for 23.9% of the total transfer demand. After adjusting the train departure times from the beginning terminal, the TWT consumed on line 1 was reduced by 21,778.2 minutes, thus yielding the greatest saving of any line. However, for line 2 (the opposite direction of line 1), only 2,069.1 minutes were reduced, even though there is a transfer volume of 20,023 passengers. Since the average TWT of line 2 is the shortest (1.39 min) among all lines at EO, the room to reduce average TWT was limited.Table 6
Comparison of line-based TWT with EO and OO.
Line ID Transfer volume(pass) Total TWT(min) Average TWT (min/pass) Difference(min) Percentagechange EO OO EO OO EO OO AM peak  1 33,183 33,218 57,844.5 36,066.3 1.74 1.09 -21,778.2 -37.6% 2 20,023 20,007 27,737.9 25,668.8 1.39 1.28 -2,069.1 -7.5% 3 15,448 15,434 40,463.5 29,568.4 2.62 1.92 -10,895.1 -26.9% 4 9,908 9,903 30,699.8 27,868.9 3.10 2.81 -2,830.9 -9.2% 5 11,657 11,641 31,205.3 29,627.7 2.68 2.55 -1,577.6 -5.1% 6 18,228 18,201 54,038.5 48,111.4 2.96 2.64 -5,927.1 -11.0% 7 4,754 4,771 11,834.6 11,703.4 2.49 2.45 -131.2 -1.1% 8 10,736 10,751 15,356.8 15,885.2 1.43 1.48 528.4 +3.4% 9 6,698 6,707 23,113.8 23,516.4 3.45 3.51 402.6 +1.7% 10 8,067 8,069 25,751.3 28,177.6 3.19 3.49 2,426.3 +9.4% Total 138,702 138,702 318,046.0 276,194.1 2.29 1.99 -41,851.9 -13.2%  Off-peak  1 3,525 3,471 11,206.2 8,977.6 3.18 2.59 -2,228.6 -19.9% 2 3,234 3,151 9,881.6 7,352.6 3.06 2.33 -2,529.0 -25.6% 3 1,814 1,823 6,370.0 4,759.7 3.51 2.61 -1,610.3 -25.3% 4 1,332 1,419 5,188.3 5,182.3 3.90 3.65 -6.0 -0.1% 5 2,720 2,667 9,325.9 8,620.9 3.43 3.23 -705.0 -7.6% 6 1,916 1,880 6,537.5 6,511.0 3.41 3.46 -26.5 -0.4% 7 2,311 2,395 7,259.9 7,001.7 3.14 2.92 -258.2 -3.6% 8 1,802 1,872 5,630.8 5,193.2 3.12 2.77 -437.6 -7.8% 9 1,991 2,017 8,077.3 7,026.3 4.06 3.48 -1,051.0 -13.0% 10 1,462 1,412 5,810.0 4,839.4 3.97 3.43 -970.6 -16.7% Total 22,107 22,107 75,287.5 65,464.7 3.41 2.96 -9,822.8 -13.0%Figure 9
Total TWT with EO and OO at transfer stations on line 1.On the other hand, in the off-peak, there is a transfer volume of 3,525 passengers who transfer from lines 3 through 10 to line 1, which accounts for 15.9% of total transfer demand. Under OO, the TWT reduced by 2,228.6 minutes and 2,529.0 minutes on lines 1 and 2, respectively. The average TWT in the AM peak is less than that in the off-peak because of shorter headways. However, the reduction of average TWT in the off-peak is greater than that of the AM peak. It appears that longer headway in the off-peak offers more flexibility to justify the departure times at the beginning terminals.


#### 5.4.3. TWT by Routes

The comparison of TWT on a route basis with EO and OO is conducted and the results are summarized in Table7. It seems that routes with heavy demand experience the greatest reductions in TWT; however, it increases at some light-demand routes.Table 7
Comparison of route-based total TWT with EO and OO.
Route ID Transfer volume(pass) Total TWT(min) Average TWT (min/pass) Difference (min) Percentagechange EO OO EO OO EO OO AM peak  A 53,206 53,226 85,582.4 61,735.1 1.61 1.16 -23,847.3 -27.9% B 25,356 25,337 71,163.3 57,437.3 2.81 2.27 -13,726.0 -19.3% C 29,885 29,842 85,243.8 77,739.1 2.85 2.61 -7,504.7 -8.8% D 15,490 15,522 27,191.4 27,588.6 1.76 1.78 397.2 +1.5% E 14,765 14,775 48,865.1 51,694.0 3.31 3.50 2,828.9 +5.8% Total 138,702 138,702 318,046.0 276,194.1 2.29 1.99 -41,851.9 -13.2%  Off-peak  A 6,759 6,621 21,087.8 16,330.2 3.12 2.47 -4,757.6 -22.6% B 3,146 3,242 11,558.3 9,942.0 3.67 3.07 -1,616.3 -14.0% C 4,636 4,548 15,863.4 15,131.9 3.42 3.33 -731.5 -4.6% D 4,113 4,267 12,890.7 12,194.9 3.13 2.86 -695.8 -5.4% E 3,453 3,429 13,887.3 11,865.7 4.02 3.46 -2,021.6 -14.6% Total 22,107 22,107 75,287.5 65,464.7 3.41 2.96 -9,822.8 -13.0%For route A in the AM peak, there is a transfer volume of 53,206 passengers from routes B through E, which accounts for 38.4% of the total transfer demand. After implementing the adjusted departure times, TWT reduced by 23,847.3 minutes (57.0% of the total reduced TWT). However, for route E with a transfer volume of 14,765 passengers (the least transfer volume among the 5 routes), TWT increased by 2,828.9 minutes (5.8%).


## 5.1. Study Metro Network and Associated Data

The case study employs the year 2013 metro network in Shenzhen, China, consisting of 5 routes intersecting at 13 transfer stations. Considering inbound and outbound traffic, the network is represented by 10 directional lines with 262 stations as shown in Figure4. The baseline model parameter values were provided by the operating agency, including a spatiotemporal passenger OD demand matrix, timetables, and average passenger walking time from one line to another at each transfer station.Figure 4
The studied Shenzhen metro network.The ridership distribution over time on a typical weekday is shown in Figure5. In addition to minimizing total TWT, the benefit before and after the implementation of the optimized solution will be assessed.Figure 5
Temporal distribution of ridership.To demonstrate the model performance applied in different levels of congestion for the metro network, we apply the AFCS data collected in the AM peak (i.e., 8:00 am ~ 9:00 am) and off-peak (i.e., 12:00 pm ~ 1:00 pm). There are 111,887 and 17,984 transfer passengers in AM peak and off-peak, respectively, which resulted in transfer volumes of 138,702 and 22,107 because some passengers need more than one transfer. The input data include train departure and arrival times, transfer walking time, and other operator parameters, which are summarized in AppendicesA and B.


## 5.2. Passenger Demand

When a passenger either enters or exits a station, the time is reported and archived in AFCS. Thus, the passenger in- and out-flow distributions can be accurately derived. Table2 illustrates the sample data extracted from the AFCS database, which include passenger ID, transaction time (entering and exiting a station), line/station ID where a transaction occurred, and transaction type. The sample data represent trips initiated by two passengers (i.e., ID 32286198 and ID 322357672). Passenger 32286198 began his/her journey from Station 218 and ended at Station 230 on line 9, who traveled without transfer. The same passenger initiated the 2nd trip in the afternoon on the same day. On the other hand, passenger 322357672 began his/her trip from Station 33 of line 2, transfer at station s2, and then ended that trip at Station 86 of line 3.Table 2
Sample data from AFCS.
PassengerNo. Card ID Transaction time stamp Line ID Station ID Transaction type 1 322861698 2013-10-16 08:26:18 9 218 Entry 322861698 2013-10-16 09:00:35 9 230 Exit 322861698 2013-10-16 13:31:17 10 241 Entry 322861698 2013-10-16 14:07:50 10 253 Exit  2 322357672 2013-10-16 07:54:19 2 33 Entry 322357672 2013-10-16 08:50:52 3 86 Exit 322357672 2013-10-16 11:40:27 4 93 Entry 322357672 2013-10-16 12:57:47 1 28 ExitAs shown in Table3, the transfer demand matrix at a transfer station s1 records transfer volume at each of 8 transfer directions (see Figure 1).Table 3
Train-to-train transfer demand at stations1.
Line ID 1 2 3 4 1 - - r m ’ 1 , m 3 , s 1 r m ’ 1 , m 4 , s 1 2 - - r m ’ 2 , m 3 , s 1 r m ’ 2 , m 4 , s 1 3 r m ’ 3 , m 1 , s 1 r m ’ 3 , m 2 , s 1 - - 4 r m ’ 4 , m 1 , s 1 r m ’ 4 , m 2 , s 1 - -


## 5.3. Optimized Results

The SA parameter values include initial temperaturet0=10,000, reduction parameter of temperature α=0.9, number of temperature iterationsZ= 1,000, and number of iterations at current temperatureU=100.For the AM peak, the computation time to search for the optimized solution using SA requires 85.7 hours to yield the minimum total cost (Intel(R) Xeon(R) CPU E5-1620 v4 @3.50 GHz 3.50 GHz with 32.0 GB RAM and 64-bit Operating System). However, SAPC requires 8.5 hours to yield the optimized result.For the off-peak, the computation time with SA only was 8.5 hours, which is significantly less than that for the AM peak because of less transfer demand and reduced service frequency. It was found in Table4 that as the transfer demand is reduced (i.e., off-peak) using SAPC seems inefficient (i.e., 9.5 hours) which costs more computation time to find the optimized solution than that of solely using SA (i.e., 8.5 hours). This computing in serial loops generally does not benefit from conversion into PC method for a relatively simple computational task in off-peak. Because the time needed for data transfer is significant compared with the time needed for computation, therefore, the results show that the PC method can be useful for some loop iterations that require long times to execute with big data.Table 4
Results from different solution algorithms.
AM peak (Off Peak) Solution algorithm Computation time(hr) Minimized TWT(min) Reduced TWT(min) SAPC 8.5 (9.5) 276,194.1 (65,464.7) 41,851.9 (9,822.8) SA 85.7 (8.5) 283,626.3 (65,481.1) 34,419.7 (9,806.4)The total TWT of the studied AM peak and off-peak were significantly reduced by 41,851.9 minutes and 9,822.8 minutes, respectively, after implementing the adjusted train departure times at the beginning stations. The yielded minimum total TWT by the solutions found using SA and SAPC are fairly close, which indicates that SAPC is very efficient.Figure6 shows the relationship between total TWT and the number of iterations using SAPC. It is notable that total TWT was reduced quickly at the first 200 iterations and then stably converged to a constant after the 500th iteration.Figure 6
Total TWT vs. iteration with SAPC (AM and off-peak).Results under existing operation (EO) and optimized operation (OO) are compared in this section. EO refers to train departures following the existing timetable, while OO refers to the fact that trains will be dispatched based on the optimized departure times. The difference between the departure times at the beginning terminal with EO and OO of linel denoted as vl is shown in Figure 7. It was found that the trains of lines 1, 4, 5, 8, and 10 should be dispatched later than the existing schedule (i.e., 32, 150, 14, 29, and 43 seconds, respectively), while trains operating on lines 2, 3, 6, 7, and 9 should be dispatched earlier (i.e., -2, -104, -50, -72, and -45 seconds) in the AM peak. However, in the off-peak hour all the trains’ departure times should be dispatched earlier than the existing schedule (i.e., negative values: -179, -174, -103, -55, -209, -142, -38, -82, -46, and -112 sec).Figure 7
Optimized adjustment of departure times with SAPC (AM and off-peak).


## 5.4. Before and after Analysis

With SAPC, the proposed model is applied to optimize train departure times from the terminals in the studied time periods. There are 148 trains dispatched during the AM peak and 85 trains dispatched in the off-peak.


### 5.4.1. TWT at Transfer Stations

As indicated in Table5 and Figure 8, total TWT was reduced by 13.2% (i.e., 41,851.9 minutes) after adjusting the departure times within the AM peak. The greatest TWT saving occurred at station s10, whereas increased TWT was found at s6, s8, and s13 with relatively low transfer volumes.Table 5
Comparison of station-based TWT.
Transfer station Transfer volume(pass) Total TWT(min) Average TWT (min/pass) Difference (min) Percentagechange ID EO OO EO OO EO OO AM peak  s 1 6,432 6,440 10,852.2 9,737.8 1.69 1.51 -1,114.4 -10.3% s 2 10,619 10,611 21,509.3 21,461.3 2.03 2.02 -48.0 -0.2% s 3 23,724 23,821 43,244.5 28,801.8 1.82 1.21 -14,442.7 -33.4% s 4 13,454 13,357 24,206.6 21,443.3 1.80 1.61 -2,763.3 -11.4% s 5 8,833 8,833 15,655.4 14,805.4 1.77 1.68 -850.0 -5.4% s 6 537 507 1,877.2 1,951.4 3.50 3.85 74.2 +4.0% s 7 12,126 12,156 31,194.6 27,383.0 2.57 2.25 -3,811.6 -12.2% s 8 3,350 3,339 10,062.2 11,165.9 3.00 3.34 1,103.7 +11.0% s 9 7,163 7,163 21,913.5 20,286.9 3.06 2.83 -1,626.6 -7.4% s 10 10,381 10,381 27,064.7 13,294.9 2.61 1.28 -13,769.8 -50.9% s 11 17,579 17,590 56,087.6 51,749.4 3.19 2.94 -4,338.2 -7.7% s 12 10,327 10,327 25,926.3 24,517.6 2.51 2.37 -1,408.7 -5.4% s 13 14,177 14,177 28,451.9 29,595.4 2.01 2.09 1,143.5 +4.0% Total 138,702 138,702 318,046.0 276,194.1 2.29 1.99 -41,851.9 -13.2%  Off-peak  s 1 1,240 1,247 4,095.7 3,987.4 3.30 3.20 -108.3 -2.6% s 2 1,425 1,452 4,744.4 4,717.0 3.33 3.25 -27.4 -0.6% s 3 3,632 3,655 11,915.3 10,400.0 3.28 2.85 -1,515.3 -12.7% s 4 1,331 1,229 4,010.4 3,770.0 3.01 3.07 -240.4 -6.0% s 5 2,595 2,466 9,256.5 5,325.8 3.57 2.16 -3,930.7 -42.5% s 6 50 51 173.8 200.0 3.48 3.92 26.2 +15.1% s 7 1,718 1,726 6,000.5 5,270.3 3.49 3.05 -730.2 -12.2% s 8 610 603 2,318.5 2,091.2 3.80 3.47 -227.3 -9.8% s 9 1,464 1,528 5,441.7 5,260.4 3.72 3.44 -181.3 -3.3% s 10 1,022 1,065 2,853.1 1,629.9 2.79 1.53 -1,223.2 -42.9% s 11 2,199 2,210 7,709.3 7,099.0 3.51 3.21 -610.3 -7.9% s 12 2,100 2,052 7,731.3 6,372.1 3.68 3.11 -1,359.2 -17.6% s 13 2,721 2,823 9,037.0 9,341.6 3.32 3.31 304.6 +3.4% Total 22,107 22,107 75,287.5 65,464.7 3.41 2.96 -9,822.8 -13.0%Figure 8
Total TWT with EO and OO at various transfer stations.In the off-peak period (see Table5), total TWT was reduced by 13.0% (9,822.8 minutes) compared to that with EO. The greatest saving was found at s5 and the least average TWT was found at s10. It is worth noting that the choice of transfer location(s) is based on the shortest travel time, which has been discussed in the assumptions. The transfer volumes before and after optimization at transfer stations have changed because passengers selected different locations to make transfer, since the justified train departure times have altered their shortest paths.


### 5.4.2. TWT by Lines

The comparison of TWT by lines is shown in Table6. For the AM peak on line 1 (outbound direction of route A, Figure 9), there is a transfer volume of 33,183 passengers who transfer from lines 3 through 10, which accounts for 23.9% of the total transfer demand. After adjusting the train departure times from the beginning terminal, the TWT consumed on line 1 was reduced by 21,778.2 minutes, thus yielding the greatest saving of any line. However, for line 2 (the opposite direction of line 1), only 2,069.1 minutes were reduced, even though there is a transfer volume of 20,023 passengers. Since the average TWT of line 2 is the shortest (1.39 min) among all lines at EO, the room to reduce average TWT was limited.Table 6
Comparison of line-based TWT with EO and OO.
Line ID Transfer volume(pass) Total TWT(min) Average TWT (min/pass) Difference(min) Percentagechange EO OO EO OO EO OO AM peak  1 33,183 33,218 57,844.5 36,066.3 1.74 1.09 -21,778.2 -37.6% 2 20,023 20,007 27,737.9 25,668.8 1.39 1.28 -2,069.1 -7.5% 3 15,448 15,434 40,463.5 29,568.4 2.62 1.92 -10,895.1 -26.9% 4 9,908 9,903 30,699.8 27,868.9 3.10 2.81 -2,830.9 -9.2% 5 11,657 11,641 31,205.3 29,627.7 2.68 2.55 -1,577.6 -5.1% 6 18,228 18,201 54,038.5 48,111.4 2.96 2.64 -5,927.1 -11.0% 7 4,754 4,771 11,834.6 11,703.4 2.49 2.45 -131.2 -1.1% 8 10,736 10,751 15,356.8 15,885.2 1.43 1.48 528.4 +3.4% 9 6,698 6,707 23,113.8 23,516.4 3.45 3.51 402.6 +1.7% 10 8,067 8,069 25,751.3 28,177.6 3.19 3.49 2,426.3 +9.4% Total 138,702 138,702 318,046.0 276,194.1 2.29 1.99 -41,851.9 -13.2%  Off-peak  1 3,525 3,471 11,206.2 8,977.6 3.18 2.59 -2,228.6 -19.9% 2 3,234 3,151 9,881.6 7,352.6 3.06 2.33 -2,529.0 -25.6% 3 1,814 1,823 6,370.0 4,759.7 3.51 2.61 -1,610.3 -25.3% 4 1,332 1,419 5,188.3 5,182.3 3.90 3.65 -6.0 -0.1% 5 2,720 2,667 9,325.9 8,620.9 3.43 3.23 -705.0 -7.6% 6 1,916 1,880 6,537.5 6,511.0 3.41 3.46 -26.5 -0.4% 7 2,311 2,395 7,259.9 7,001.7 3.14 2.92 -258.2 -3.6% 8 1,802 1,872 5,630.8 5,193.2 3.12 2.77 -437.6 -7.8% 9 1,991 2,017 8,077.3 7,026.3 4.06 3.48 -1,051.0 -13.0% 10 1,462 1,412 5,810.0 4,839.4 3.97 3.43 -970.6 -16.7% Total 22,107 22,107 75,287.5 65,464.7 3.41 2.96 -9,822.8 -13.0%Figure 9
Total TWT with EO and OO at transfer stations on line 1.On the other hand, in the off-peak, there is a transfer volume of 3,525 passengers who transfer from lines 3 through 10 to line 1, which accounts for 15.9% of total transfer demand. Under OO, the TWT reduced by 2,228.6 minutes and 2,529.0 minutes on lines 1 and 2, respectively. The average TWT in the AM peak is less than that in the off-peak because of shorter headways. However, the reduction of average TWT in the off-peak is greater than that of the AM peak. It appears that longer headway in the off-peak offers more flexibility to justify the departure times at the beginning terminals.


### 5.4.3. TWT by Routes

The comparison of TWT on a route basis with EO and OO is conducted and the results are summarized in Table7. It seems that routes with heavy demand experience the greatest reductions in TWT; however, it increases at some light-demand routes.Table 7
Comparison of route-based total TWT with EO and OO.
Route ID Transfer volume(pass) Total TWT(min) Average TWT (min/pass) Difference (min) Percentagechange EO OO EO OO EO OO AM peak  A 53,206 53,226 85,582.4 61,735.1 1.61 1.16 -23,847.3 -27.9% B 25,356 25,337 71,163.3 57,437.3 2.81 2.27 -13,726.0 -19.3% C 29,885 29,842 85,243.8 77,739.1 2.85 2.61 -7,504.7 -8.8% D 15,490 15,522 27,191.4 27,588.6 1.76 1.78 397.2 +1.5% E 14,765 14,775 48,865.1 51,694.0 3.31 3.50 2,828.9 +5.8% Total 138,702 138,702 318,046.0 276,194.1 2.29 1.99 -41,851.9 -13.2%  Off-peak  A 6,759 6,621 21,087.8 16,330.2 3.12 2.47 -4,757.6 -22.6% B 3,146 3,242 11,558.3 9,942.0 3.67 3.07 -1,616.3 -14.0% C 4,636 4,548 15,863.4 15,131.9 3.42 3.33 -731.5 -4.6% D 4,113 4,267 12,890.7 12,194.9 3.13 2.86 -695.8 -5.4% E 3,453 3,429 13,887.3 11,865.7 4.02 3.46 -2,021.6 -14.6% Total 22,107 22,107 75,287.5 65,464.7 3.41 2.96 -9,822.8 -13.0%For route A in the AM peak, there is a transfer volume of 53,206 passengers from routes B through E, which accounts for 38.4% of the total transfer demand. After implementing the adjusted departure times, TWT reduced by 23,847.3 minutes (57.0% of the total reduced TWT). However, for route E with a transfer volume of 14,765 passengers (the least transfer volume among the 5 routes), TWT increased by 2,828.9 minutes (5.8%).


## 5.4.1. TWT at Transfer Stations

As indicated in Table5 and Figure 8, total TWT was reduced by 13.2% (i.e., 41,851.9 minutes) after adjusting the departure times within the AM peak. The greatest TWT saving occurred at station s10, whereas increased TWT was found at s6, s8, and s13 with relatively low transfer volumes.Table 5
Comparison of station-based TWT.
Transfer station Transfer volume(pass) Total TWT(min) Average TWT (min/pass) Difference (min) Percentagechange ID EO OO EO OO EO OO AM peak  s 1 6,432 6,440 10,852.2 9,737.8 1.69 1.51 -1,114.4 -10.3% s 2 10,619 10,611 21,509.3 21,461.3 2.03 2.02 -48.0 -0.2% s 3 23,724 23,821 43,244.5 28,801.8 1.82 1.21 -14,442.7 -33.4% s 4 13,454 13,357 24,206.6 21,443.3 1.80 1.61 -2,763.3 -11.4% s 5 8,833 8,833 15,655.4 14,805.4 1.77 1.68 -850.0 -5.4% s 6 537 507 1,877.2 1,951.4 3.50 3.85 74.2 +4.0% s 7 12,126 12,156 31,194.6 27,383.0 2.57 2.25 -3,811.6 -12.2% s 8 3,350 3,339 10,062.2 11,165.9 3.00 3.34 1,103.7 +11.0% s 9 7,163 7,163 21,913.5 20,286.9 3.06 2.83 -1,626.6 -7.4% s 10 10,381 10,381 27,064.7 13,294.9 2.61 1.28 -13,769.8 -50.9% s 11 17,579 17,590 56,087.6 51,749.4 3.19 2.94 -4,338.2 -7.7% s 12 10,327 10,327 25,926.3 24,517.6 2.51 2.37 -1,408.7 -5.4% s 13 14,177 14,177 28,451.9 29,595.4 2.01 2.09 1,143.5 +4.0% Total 138,702 138,702 318,046.0 276,194.1 2.29 1.99 -41,851.9 -13.2%  Off-peak  s 1 1,240 1,247 4,095.7 3,987.4 3.30 3.20 -108.3 -2.6% s 2 1,425 1,452 4,744.4 4,717.0 3.33 3.25 -27.4 -0.6% s 3 3,632 3,655 11,915.3 10,400.0 3.28 2.85 -1,515.3 -12.7% s 4 1,331 1,229 4,010.4 3,770.0 3.01 3.07 -240.4 -6.0% s 5 2,595 2,466 9,256.5 5,325.8 3.57 2.16 -3,930.7 -42.5% s 6 50 51 173.8 200.0 3.48 3.92 26.2 +15.1% s 7 1,718 1,726 6,000.5 5,270.3 3.49 3.05 -730.2 -12.2% s 8 610 603 2,318.5 2,091.2 3.80 3.47 -227.3 -9.8% s 9 1,464 1,528 5,441.7 5,260.4 3.72 3.44 -181.3 -3.3% s 10 1,022 1,065 2,853.1 1,629.9 2.79 1.53 -1,223.2 -42.9% s 11 2,199 2,210 7,709.3 7,099.0 3.51 3.21 -610.3 -7.9% s 12 2,100 2,052 7,731.3 6,372.1 3.68 3.11 -1,359.2 -17.6% s 13 2,721 2,823 9,037.0 9,341.6 3.32 3.31 304.6 +3.4% Total 22,107 22,107 75,287.5 65,464.7 3.41 2.96 -9,822.8 -13.0%Figure 8
Total TWT with EO and OO at various transfer stations.In the off-peak period (see Table5), total TWT was reduced by 13.0% (9,822.8 minutes) compared to that with EO. The greatest saving was found at s5 and the least average TWT was found at s10. It is worth noting that the choice of transfer location(s) is based on the shortest travel time, which has been discussed in the assumptions. The transfer volumes before and after optimization at transfer stations have changed because passengers selected different locations to make transfer, since the justified train departure times have altered their shortest paths.


## 5.4.2. TWT by Lines

The comparison of TWT by lines is shown in Table6. For the AM peak on line 1 (outbound direction of route A, Figure 9), there is a transfer volume of 33,183 passengers who transfer from lines 3 through 10, which accounts for 23.9% of the total transfer demand. After adjusting the train departure times from the beginning terminal, the TWT consumed on line 1 was reduced by 21,778.2 minutes, thus yielding the greatest saving of any line. However, for line 2 (the opposite direction of line 1), only 2,069.1 minutes were reduced, even though there is a transfer volume of 20,023 passengers. Since the average TWT of line 2 is the shortest (1.39 min) among all lines at EO, the room to reduce average TWT was limited.Table 6
Comparison of line-based TWT with EO and OO.
Line ID Transfer volume(pass) Total TWT(min) Average TWT (min/pass) Difference(min) Percentagechange EO OO EO OO EO OO AM peak  1 33,183 33,218 57,844.5 36,066.3 1.74 1.09 -21,778.2 -37.6% 2 20,023 20,007 27,737.9 25,668.8 1.39 1.28 -2,069.1 -7.5% 3 15,448 15,434 40,463.5 29,568.4 2.62 1.92 -10,895.1 -26.9% 4 9,908 9,903 30,699.8 27,868.9 3.10 2.81 -2,830.9 -9.2% 5 11,657 11,641 31,205.3 29,627.7 2.68 2.55 -1,577.6 -5.1% 6 18,228 18,201 54,038.5 48,111.4 2.96 2.64 -5,927.1 -11.0% 7 4,754 4,771 11,834.6 11,703.4 2.49 2.45 -131.2 -1.1% 8 10,736 10,751 15,356.8 15,885.2 1.43 1.48 528.4 +3.4% 9 6,698 6,707 23,113.8 23,516.4 3.45 3.51 402.6 +1.7% 10 8,067 8,069 25,751.3 28,177.6 3.19 3.49 2,426.3 +9.4% Total 138,702 138,702 318,046.0 276,194.1 2.29 1.99 -41,851.9 -13.2%  Off-peak  1 3,525 3,471 11,206.2 8,977.6 3.18 2.59 -2,228.6 -19.9% 2 3,234 3,151 9,881.6 7,352.6 3.06 2.33 -2,529.0 -25.6% 3 1,814 1,823 6,370.0 4,759.7 3.51 2.61 -1,610.3 -25.3% 4 1,332 1,419 5,188.3 5,182.3 3.90 3.65 -6.0 -0.1% 5 2,720 2,667 9,325.9 8,620.9 3.43 3.23 -705.0 -7.6% 6 1,916 1,880 6,537.5 6,511.0 3.41 3.46 -26.5 -0.4% 7 2,311 2,395 7,259.9 7,001.7 3.14 2.92 -258.2 -3.6% 8 1,802 1,872 5,630.8 5,193.2 3.12 2.77 -437.6 -7.8% 9 1,991 2,017 8,077.3 7,026.3 4.06 3.48 -1,051.0 -13.0% 10 1,462 1,412 5,810.0 4,839.4 3.97 3.43 -970.6 -16.7% Total 22,107 22,107 75,287.5 65,464.7 3.41 2.96 -9,822.8 -13.0%Figure 9
Total TWT with EO and OO at transfer stations on line 1.On the other hand, in the off-peak, there is a transfer volume of 3,525 passengers who transfer from lines 3 through 10 to line 1, which accounts for 15.9% of total transfer demand. Under OO, the TWT reduced by 2,228.6 minutes and 2,529.0 minutes on lines 1 and 2, respectively. The average TWT in the AM peak is less than that in the off-peak because of shorter headways. However, the reduction of average TWT in the off-peak is greater than that of the AM peak. It appears that longer headway in the off-peak offers more flexibility to justify the departure times at the beginning terminals.


## 5.4.3. TWT by Routes

The comparison of TWT on a route basis with EO and OO is conducted and the results are summarized in Table7. It seems that routes with heavy demand experience the greatest reductions in TWT; however, it increases at some light-demand routes.Table 7
Comparison of route-based total TWT with EO and OO.
Route ID Transfer volume(pass) Total TWT(min) Average TWT (min/pass) Difference (min) Percentagechange EO OO EO OO EO OO AM peak  A 53,206 53,226 85,582.4 61,735.1 1.61 1.16 -23,847.3 -27.9% B 25,356 25,337 71,163.3 57,437.3 2.81 2.27 -13,726.0 -19.3% C 29,885 29,842 85,243.8 77,739.1 2.85 2.61 -7,504.7 -8.8% D 15,490 15,522 27,191.4 27,588.6 1.76 1.78 397.2 +1.5% E 14,765 14,775 48,865.1 51,694.0 3.31 3.50 2,828.9 +5.8% Total 138,702 138,702 318,046.0 276,194.1 2.29 1.99 -41,851.9 -13.2%  Off-peak  A 6,759 6,621 21,087.8 16,330.2 3.12 2.47 -4,757.6 -22.6% B 3,146 3,242 11,558.3 9,942.0 3.67 3.07 -1,616.3 -14.0% C 4,636 4,548 15,863.4 15,131.9 3.42 3.33 -731.5 -4.6% D 4,113 4,267 12,890.7 12,194.9 3.13 2.86 -695.8 -5.4% E 3,453 3,429 13,887.3 11,865.7 4.02 3.46 -2,021.6 -14.6% Total 22,107 22,107 75,287.5 65,464.7 3.41 2.96 -9,822.8 -13.0%For route A in the AM peak, there is a transfer volume of 53,206 passengers from routes B through E, which accounts for 38.4% of the total transfer demand. After implementing the adjusted departure times, TWT reduced by 23,847.3 minutes (57.0% of the total reduced TWT). However, for route E with a transfer volume of 14,765 passengers (the least transfer volume among the 5 routes), TWT increased by 2,828.9 minutes (5.8%).


## 6. Conclusions

This study develops a quick and easy-to-implement method to minimize total TWT with the AFCS data provided by Shenzhen Metro in China in which the train departure times from the beginning terminals were optimized. The metro users can gain substantial benefit (reduced TWT) without bearing additional operator’s cost.Since the transfer information is not available in AFCS, an enhanced Dijkstra algorithm (EDA) was developed to search for transfer station(s) for each indirect passenger based on their arrival time at station and posted train schedule. With that, the transfer volume at each station can be estimated.The average TWT was found to be reduced more in the off-peak period than the AM peak period because longer headway offers more flexibility to justify the train departure time. The average and total TWT based on station, line, and route were assessed. In general, more TWT can be saved at stations with greater transfer volume, albeit increasing at stations with light transfer volume.In addition, the developed SAPC is fairly efficient in searching for the solution. It significantly outperforms SA, especially in the peak period when the transfer demand is large. As would be expected, the computational efficiency is highly dependent on the size of solution spaces.As an immediate extension of this study, we intend to enhance the developed model by considering realistic train operational issues (i.e., probabilistic train travel time between stations and dwell time at stations), probabilistic passenger walking time [35] within the transfer station, and passengers making more than two transfers to reach their destination. This enhancement would permit the developed model to better optimize dynamic train departure times at the beginning station and holding times at intermediate stations.



---

*Source: 4218625-2018-10-04.xml*