# Transfer Coordination for Metro Networks during the Start- or End-of-Service Period

Authors: Liqiao Ning; Peng Zhao; Wenkai Xu; Ke Qiao
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

When travelling via metro networks during the start- or end-of-service period, transferring passengers may suffer a transfer failure. Accordingly, the synchronization timetabling problem necessitates consideration of transfer waiting time and transfer availability with respect to the first or last train. Hence, transfer train index (TTI) is formulated to identify the transfer train and calculate the transfer waiting time. Furthermore, two types of connection indexes, the last connection train index (LCTI) and the first connection train index (FCTI), are devised to distinguish transfer failure from transfer success, and the penalty constraints are implemented together to reflect the adverse effects of transfer failure. Then, a mixed integer programming model is developed to concurrently reduce transfer waiting time and improve transfer availability, which can be solved by CPLEX. Finally, a case study on Beijing metro network is made to verify the method. Experimental results show that our proposed model can yield synchronization solutions with significant reductions in both the average transfer waiting time and the proportion of transfer failure passengers.


---

## Body

## 1. Introduction

With the expansion of metro network in large cities, transfer efficiency at transfer stations is of vital importance. To improve transfer efficiency, operators need to coordinate the arrival and departure time of trains at transfer stations to implement smoothly transferring as much as possible. In other words, it requires of synchronization timetabling to acquire a short transfer waiting time.Specially, during the end-of-service period denoted as the end of the operation period (for example, the last half hour) in a day on lines, transferring passengers may miss the last connection train, which is known as a “transfer failure”. Certainly, it would cause an extreme inconvenience and produce a strong dissatisfaction when passengers experience a transfer failure. Also, it is not easy to hunt for an alternative mode since the availability of bus, taxis, or other traffic modes is at a low level during this period. Due to the adverse effects of transfer failure, coordinating the network timetable during the end-of-service period has become a hot issue in research and practice. Similarly, during the start-of-service period denoted as the start of the operation period (for example, the first half hour) in a day on lines, a phenomenon that transferring passengers might have to wait for a long and unbearable time and they would abandon the transfer within the metro network for the sake of a short travelling time actually exists; in this case, we regard it as a transfer failure as well. Although transfer failure during the start-of-service period does have a less impact on passenger trips compared with that during the end-of-service period, it still is a noticeable problem and should not be neglected.Transfer failure has the direct bearing on transfer availability, and a poor transfer availability network will lower the level of service of metro system. However, it is hard to ensure the transfer availability for all transfer connections within a network. Thus, it is necessary to take the passenger transfer demands into account to seek for the global and systematic optimal scheme. Generally, transfer demands are distributed on several trains on each line during the start- or end-of-service period, rather than primarily on the first train during the start-of-service period or the last train during the end-of-service period, whereas foci of interest in current researches on the sort of timetabling problem are merely relevant to the first or last train on each line within a network and are thus exclusive of other trains during the start- or end-of-service period. Therefore, even though passengers on the subsequent trains (after the first train) during the start-of-service period or the previous trains (before the last train) during the end-of-service period are likely to experience a transfer failure as well, the part of transfer availability has been overlooked.Figure1 is an illustration of one-platform-transfer during the end-of-service period. Current researches mainly focus on the transfer of transfer passengers TP4. However, TP3 also miss the last connection train and the part of transfer availability has been overlooked. Furthermore, because the headways between trains on suburban rail transit lines are typically longer during this period, the transfer waiting time of TP1 and TP2 is worthy noted. Implementing the synchronization timetabling from the perspective of the start- or end-of-service period yields the following three advantages: (1) more catering to the actual transfer demand; (2) concurrently reducing the transfer waiting time and improving the transfer availability; (3) incorporating the generated timetables during the start- or end-of-service period into the timetables during other periods more easily and reasonably.Figure 1
Illustration of synchronization timetabling during the end-of-service period.The remainder of this paper is organized as follows: Section2 provides literature review; Section 3 provides a transfer description by means of establishing the transfer train index (TTI) to identify the transfer train and calculate the relevant transfer waiting time and of devising the last connection train index (LCTI) and the first connection train index (FCTI) to distinguish transfer failure from transfer success. Section 4 proposes a timetable synchronization optimization (TSO) model to concurrently reduce transfer waiting time and improve transfer availability, which can be solved by CPLEX; Section 5 implements a case study on Beijing metro network, sensitivity analysis of which demonstrates the different effects of the ranger of headways, dwell times, and running times. Section 6 provides the conclusions.


## 2. Literature Review

Transfer efficiency is a crucial measure in the evaluation of network timetable performance. There is a wealth of literature on transfer optimization via timetabling. The timetabling problem itself has diverse variants, such as cyclic (periodic) or noncyclic versions, network or single one-way line (corridor) versions, and various versions with different objective functions [1]. Thus, the transfer synchronization problem can be implemented via a variety of different timetabling models.There are several researches based on even headways. Bookbinder and Desilets [2] employed a simulation procedure combined with an optimization model in consideration of the stochastic travel times of buses. Daduna and Voß [3], Jansen et al. [4], Cevallos and Zhao [5], and Shafahi and Khani [6] established the synchronization optimization models to minimize the transfer waiting time and presented the genetic algorithms to solve them.As for unevenly spaced departure times, the timetabling problem becomes complex and intractable, because the numbers of binary variables increase sharply, and thus the connection pairs have vast combination schemes. For this reason, the sort of timetabling problem is always accompanied with associated exact or heuristic algorithms. Ceder and Tal [7, 8] defined synchronization as the simultaneous arrival of two buses and proposed a mixed integer linear programming model to maximize the number of simultaneous arrivals. Meanwhile, efficient procedures are presented as a useful tool for the scheduler in generating timetables. Based on this, Eranki [9] redefined synchronization as the simultaneous arrival of two buses within a time window and devised the corresponding heuristic approach. Ibarra-Rojas et al. [10, 11] also applied the concept of synchronization and developed different metaheuristic solving frameworks (iterated located search, variable neighborhood search, and evolutionary algorithm), whereas Fouilhoux et al. [12] devised four classed of valid inequalities to cut fractional solutions of the linear relaxations of integer programs and nonoptimal feasible solutions, thereby yielding a shrink in the feasible space. Consequently, a promotion in solving efficiency is acquired when implementing the exact branch-and-cut algorithm in CPLEX. Wong Rachel [13] proposed a synchronization optimized timetable model to minimize the total transfer waiting time in a network and designed an optimization-based heuristic method by means of the LP-relaxation solutions. Kwan and Chang [14] built a multiobjective model to minimize the passenger dissatisfaction and the degree of the deviation from the original timetable and developed the multiobjective evolutionary approach.Typically, during the start- or end-of-service period, the problem with respect to transfer availability arises. Due to the adverse effects of transfer failure, many researchers are dedicated to improving the transfer availability, but all focused on the first or last train on each line in a network. Zhou et al. [15] proposed a first and last train coordination optimization model considering transfer waiting time for the first and last train based on passengers route choice behaviors and designed the genetic algorithm. Kang et al. [16] and Kang et al. [17] established a first train coordination model and a last train mean-variance model; and both were solved via simulated annealing algorithm. Kang et al. [18] developed a last train network transfer model to maximize the passenger transfer connection headways. Furthermore, in actual operation, a train delay can break the fine transfer and transfer success is likely to deteriorate into transfer failure. In this regard, a high-efficiency algorithm is worthy of studying to solve this rescheduling problem. Kang et al. [19] and Xu, Zhao, and Ning [20] proposed a last train rescheduling model allowing for a last train delay and developed the genetic algorithm which can generate the last train timetable quickly.The literature review presented different characteristics of the timetabling problem. However, to the best of our knowledge, there is no optimization model devoted to coordinating the train timetables during the start- or end-of-service period that is capable of simultaneously reducing transfer waiting time (from the general synchronization version) and improving transfer availability (from the first or last train coordination version).


## 3. Transfer Description

Coordinating arrival and departure time of trains at transfer stations in a network can yield improvements in the efficiency of the train timetabling problem with respect to transfer connection. Generally, transfer patterns can be fixed and unfixed. The fixed transfer patterns imply that all the transfer pairs for feeder trains and connection trains are predetermined and inflexible. However, in this case, the generated timetables are usually not the optimal solution. Alternatively, in our model, transfer patterns are unfixed and flexible; and it is part of the optimization problem. In this consideration, the trains can arrive and depart in transfer station within a certain period of time, and the transfer connection trains are undetermined.In the paper, we aim to yield the synchronization timetable with consideration of the phenomena of missing transfer in metro network during the start- or end-of-service period. However, it is a difficult task when connection patterns are not predetermined. More specifically, there are four major challenges, which need to overcome in this paper.(1)
How to distinguish transfer failure from transfer success during the start- or end-of-service period?(2)
When it is a transfer success, how to identify the transfer train and calculate the transfer waiting time while the arrival time of feeder trains and the departure time of connection trains at transfer station are not predetermined?(3)
When it is a transfer failure, how to quantify and measure the adverse effects of transfer failure and then reflect it in the optimization model?(4)
How to simultaneously reduce transfer waiting time with respect to transfer success and improve transfer availability with respect to transfer failure?


### 3.1. Nomenclature

Model parameters are defined as follows:S is the set of lines in the network, S=s∣s=1,2,⋯,U, where U is the total number of lines.Is is the set of stations on line s, Is=i∣i=1,2,⋯,Gs, where Gs is the total number of stations on line s.Qs is the set of trains on line s, Qs=q∣q=1,2,⋯,Ns, where Ns is the total number of trains on line s during the start- or end-of-service period.K is the set of transfer arcs in a network, K=k∣k=s,i→s′,i′, where s,i→s′,i′ denotes station i on line s and station i′ on line s′ which are the same transfer station.ckq is the number of transferring passengers on transfer arc k who transfer from the q-th train on feeder line s to connection line s′at transfer station.ek is passengers walking time on transfer arc k.hmins, hmaxs are the minimum and maximum headway of line s, respectively.Model variables are defined as follows:Aisq is arrival time of the q-th train on line s at transfer station i.Lisq is departure time of the q-th train on line s at transfer station i.Disq is dwell time of the q-th train on line s at station i.Risq is running time of the q-th train on line s from station i-1 to station i.wkqq′ is transfer waiting time for passengers who transfer from the q-th train on feeder line s to the q′-th train on connection line s′ at transfer station.


### 3.2. Transfer Index

#### 3.2.1. The Transfer Train Index (TTI)

Modelling transfer requires consideration of the arrival time of the corresponding feeder train, transferring passenger walking time at transfer station, transferring passenger waiting time, and departure time of the connecting train. An essential criterion for a possible connection at transfer station is that the departure time of the connection train should be later than the time of transferring passengers reaching the connection platform after getting off a feeder train. Accordingly, a train connection time (TCT) is defined as the difference between the departure time of theq′-th connection train and the sum of the arrival time of the q-th feeder train and transfer walking time ek, which can be denoted as Li′s′q′-(Aisq+ek).In accordance with the criteria, the transfer train index (TTI) denoted as a binary variableαkqq′ is introduced to identify whether it is a possible connection and the constraint defined via (1) is a linearization of the definition to activate the TTI. If the TCT is nonnegative, αkqq′ is equal to 1; otherwise it is equal to 0.(1)Mαkqq′-1≤Li′s′q′-Aisq+ek≤Mαkqq′where M is a large positive integer.


#### 3.2.2. The Last Connection Train Index (LCTI)

Typically, during the end-of-service period, passengers may miss the last connection trainNs′, which leads to a transfer failure. Accordingly, to identify whether it is a transfer failure or transfer success, we introduce a last connection train index (LCTI) to set up the relationship between each feeder train and the last connection train, as demonstrated via (2). Interestingly, the LCTI is in effect a component of TTI and can be expressed as αkqNs′.(2)MαkqNs′-1≤Li′s′Ns′′-Aisq+ek≤MαkqNs′IfAisq+ek≤Li′s′Ns′, there will always be connection trains at transfer station for transferring passengers to board and it is a transfer success, and the LCTI is equal to 1; otherwise transferring passengers will miss the last connection train, and the LCTI is equal to 0.


#### 3.2.3. The First Connection Train Index (FCTI)

While trains operate during the end-of-service period, passengers travelling via a network are always able to board the connection trains during the start-of-service period, whereas it is unreasonable and unrealistic for transferring passengers to waiting for a long time. Accordingly, based on the differences, the circumstance that the train connection time TCT is larger than a tolerable time is here regarded as a transfer failure; otherwise it is a transfer success, and in this case the relevant transfer waiting time is equal to the TCT.Similarly, a first connection train index (FCTI) denoted as a binary variableσkq is introduced to distinguish transfer failure from transfer success during the start-of-service period. The constraint defined via (3) is the linearization of the FCTI. When Li′s′1-(Aisq+ek)>BTk, the first connection train cannot arrive at transfer station within the maximum tolerable transfer waiting time; in this case, the FCTI is equal to 1, and it is a transfer failure; otherwise transfer passengers can catch the connection trains in the tolerable waiting time, and the FCTI is equal to 0.(3)Mσkq-1≤Li′s′1-Aisq+ek-BTk≤Mσkqwhere BTk is the maximum tolerable transfer waiting time.


### 3.3. Transfer Waiting Time

#### 3.3.1. Transfer Success

Under transfer success circumstances, transferring passenger can board the connection trains. Nonetheless, we still cannot decide which connection train is the transfer train and calculate the relevant transfer waiting time. Here, we assume that train person capacity is sufficient during the start- and end-of-service period and passengers will always board the first arriving train after they reach the platform for purpose of a short waiting time, which implies that only the first arriving train can be the transfer train.Thus, the transfer waiting time can be modelled via (4) which delimits the fact that if and only if αkq(q′-1)=0, αkqq′=1, the transfer waiting time can be positive.(4)Li′s′q′-Aisq+ek-Mαkqq′-1≤wkqq′,q′≠1When TCT is nonnegative andαkq(q′-1)=0, the connection train q′ is the transfer train of the feeder train q, and the transfer waiting time wkqq′ is equal to the TCT, as illustrated in Figure 2. When the TCT is nonnegative and αkq(q′-1)=1, the left side of constraint (4) is negative due to the large positive number M, and the constrain (4) equates the pointless constraint wkqq′≥0. When the TCT is negative, the constraint (4) makes no sense likewise.Figure 2
Connection relationships between feeder trains and connection trains.During the end-of-service period, ifLi′s′1≤Aisq+ek≤Li′s′1+hmaxs′, the transfer train of the feeder train q should be one of the previous trains of the 1-th connection train (the first train we consider during the end-of-service period). Since the timetables of the previous periods are unknown, this part of waiting time is not taken into account. We assume that, for the feeder train q, if Li′s′1-Aisq+ek is nonnegative and less than half of the sum of the minimum and maximum headway of connection line s′, the transfer train is the 1-th train on line s′; otherwise it is one of the previous trains. Accordingly, we introduce binary variable γkq and the transfer waiting time between the feeder train q and the 1-th connection train wkq1q′=1, which are not be allowed for in constraint (4), can be counted via (6).(5)Mγkq-1≤Li′s′1-Aisq+ek-hmins′+hmaxs′2≤Mγkq(6)Li′s′1-Aisq+ek-Mγkq≤wkq1Analogously, as to the start-of-service period, via incorporating the constraint (7) into (3), the transfer waiting time wkq1q′=1 can be modelled.(7)Li′s′1-Aisq+ek-Mσkq≤wkq1


#### 3.3.2. Transfer Failure

As mentioned above, passengers suffering a transfer failure will experience an extremely bad travel. It does not mean that the part of passengers certainly cannot reach the destination, because they may choose other traffic modes to complete the rest travel. Here, we introduce penalty coefficients to quantify and measure the adverse effects of transfer failure. Moreover, they can be set based on the operation situation of all the other traffic modes during the start- and end-of-service period to cater to the reality.Noted that the penalty coefficients are utilized to impose some penalty time on transfer waiting time when it is a transfer failure. Thus, they should have no effects under transfer success circumstances. Accordingly, penalty constraints are jointly established to cope with both cases concurrently via incorporating the LCTI and the FCTI, as demonstrated via (8) and (9).During the end-of-service period, whenAisq+ek>Li′s′Ns′, passengers fail to catch the last connection trains, and the LCTI is equal to 0 according to constraint (2). In this case, penalty coefficients CkL are utilized to impose some penalty time on transfer failure. More importantly, it makes no sense to the transfer waiting time of transfer success.(8)CkL1-αkqNs′≤wkqNs′Analogously, during the start-of-service period, whenLi′s′1-(Aisq+ek)>BTk, it is a transfer failure, and the FCTI is equal to 1 according to constraint (3). In this case, the transfer waiting time is equal to penalty coefficients CkF, as demonstrated in Figure 3. In the case of transfer success, the penalty constraint has no effects.(9)CkFσkq≤wkq1Figure 3
Transfer waiting time during the start-of-service period.In summary, the transfer waiting time is determined by combining all the joint constraints (1)~(9) and implies twofold meanings: (1) the actual waiting time when it is a transfer success; (2) the penalty waiting time when it is a transfer failure.


## 3.1. Nomenclature

Model parameters are defined as follows:S is the set of lines in the network, S=s∣s=1,2,⋯,U, where U is the total number of lines.Is is the set of stations on line s, Is=i∣i=1,2,⋯,Gs, where Gs is the total number of stations on line s.Qs is the set of trains on line s, Qs=q∣q=1,2,⋯,Ns, where Ns is the total number of trains on line s during the start- or end-of-service period.K is the set of transfer arcs in a network, K=k∣k=s,i→s′,i′, where s,i→s′,i′ denotes station i on line s and station i′ on line s′ which are the same transfer station.ckq is the number of transferring passengers on transfer arc k who transfer from the q-th train on feeder line s to connection line s′at transfer station.ek is passengers walking time on transfer arc k.hmins, hmaxs are the minimum and maximum headway of line s, respectively.Model variables are defined as follows:Aisq is arrival time of the q-th train on line s at transfer station i.Lisq is departure time of the q-th train on line s at transfer station i.Disq is dwell time of the q-th train on line s at station i.Risq is running time of the q-th train on line s from station i-1 to station i.wkqq′ is transfer waiting time for passengers who transfer from the q-th train on feeder line s to the q′-th train on connection line s′ at transfer station.


## 3.2. Transfer Index

### 3.2.1. The Transfer Train Index (TTI)

Modelling transfer requires consideration of the arrival time of the corresponding feeder train, transferring passenger walking time at transfer station, transferring passenger waiting time, and departure time of the connecting train. An essential criterion for a possible connection at transfer station is that the departure time of the connection train should be later than the time of transferring passengers reaching the connection platform after getting off a feeder train. Accordingly, a train connection time (TCT) is defined as the difference between the departure time of theq′-th connection train and the sum of the arrival time of the q-th feeder train and transfer walking time ek, which can be denoted as Li′s′q′-(Aisq+ek).In accordance with the criteria, the transfer train index (TTI) denoted as a binary variableαkqq′ is introduced to identify whether it is a possible connection and the constraint defined via (1) is a linearization of the definition to activate the TTI. If the TCT is nonnegative, αkqq′ is equal to 1; otherwise it is equal to 0.(1)Mαkqq′-1≤Li′s′q′-Aisq+ek≤Mαkqq′where M is a large positive integer.


### 3.2.2. The Last Connection Train Index (LCTI)

Typically, during the end-of-service period, passengers may miss the last connection trainNs′, which leads to a transfer failure. Accordingly, to identify whether it is a transfer failure or transfer success, we introduce a last connection train index (LCTI) to set up the relationship between each feeder train and the last connection train, as demonstrated via (2). Interestingly, the LCTI is in effect a component of TTI and can be expressed as αkqNs′.(2)MαkqNs′-1≤Li′s′Ns′′-Aisq+ek≤MαkqNs′IfAisq+ek≤Li′s′Ns′, there will always be connection trains at transfer station for transferring passengers to board and it is a transfer success, and the LCTI is equal to 1; otherwise transferring passengers will miss the last connection train, and the LCTI is equal to 0.


### 3.2.3. The First Connection Train Index (FCTI)

While trains operate during the end-of-service period, passengers travelling via a network are always able to board the connection trains during the start-of-service period, whereas it is unreasonable and unrealistic for transferring passengers to waiting for a long time. Accordingly, based on the differences, the circumstance that the train connection time TCT is larger than a tolerable time is here regarded as a transfer failure; otherwise it is a transfer success, and in this case the relevant transfer waiting time is equal to the TCT.Similarly, a first connection train index (FCTI) denoted as a binary variableσkq is introduced to distinguish transfer failure from transfer success during the start-of-service period. The constraint defined via (3) is the linearization of the FCTI. When Li′s′1-(Aisq+ek)>BTk, the first connection train cannot arrive at transfer station within the maximum tolerable transfer waiting time; in this case, the FCTI is equal to 1, and it is a transfer failure; otherwise transfer passengers can catch the connection trains in the tolerable waiting time, and the FCTI is equal to 0.(3)Mσkq-1≤Li′s′1-Aisq+ek-BTk≤Mσkqwhere BTk is the maximum tolerable transfer waiting time.


## 3.2.1. The Transfer Train Index (TTI)

Modelling transfer requires consideration of the arrival time of the corresponding feeder train, transferring passenger walking time at transfer station, transferring passenger waiting time, and departure time of the connecting train. An essential criterion for a possible connection at transfer station is that the departure time of the connection train should be later than the time of transferring passengers reaching the connection platform after getting off a feeder train. Accordingly, a train connection time (TCT) is defined as the difference between the departure time of theq′-th connection train and the sum of the arrival time of the q-th feeder train and transfer walking time ek, which can be denoted as Li′s′q′-(Aisq+ek).In accordance with the criteria, the transfer train index (TTI) denoted as a binary variableαkqq′ is introduced to identify whether it is a possible connection and the constraint defined via (1) is a linearization of the definition to activate the TTI. If the TCT is nonnegative, αkqq′ is equal to 1; otherwise it is equal to 0.(1)Mαkqq′-1≤Li′s′q′-Aisq+ek≤Mαkqq′where M is a large positive integer.


## 3.2.2. The Last Connection Train Index (LCTI)

Typically, during the end-of-service period, passengers may miss the last connection trainNs′, which leads to a transfer failure. Accordingly, to identify whether it is a transfer failure or transfer success, we introduce a last connection train index (LCTI) to set up the relationship between each feeder train and the last connection train, as demonstrated via (2). Interestingly, the LCTI is in effect a component of TTI and can be expressed as αkqNs′.(2)MαkqNs′-1≤Li′s′Ns′′-Aisq+ek≤MαkqNs′IfAisq+ek≤Li′s′Ns′, there will always be connection trains at transfer station for transferring passengers to board and it is a transfer success, and the LCTI is equal to 1; otherwise transferring passengers will miss the last connection train, and the LCTI is equal to 0.


## 3.2.3. The First Connection Train Index (FCTI)

While trains operate during the end-of-service period, passengers travelling via a network are always able to board the connection trains during the start-of-service period, whereas it is unreasonable and unrealistic for transferring passengers to waiting for a long time. Accordingly, based on the differences, the circumstance that the train connection time TCT is larger than a tolerable time is here regarded as a transfer failure; otherwise it is a transfer success, and in this case the relevant transfer waiting time is equal to the TCT.Similarly, a first connection train index (FCTI) denoted as a binary variableσkq is introduced to distinguish transfer failure from transfer success during the start-of-service period. The constraint defined via (3) is the linearization of the FCTI. When Li′s′1-(Aisq+ek)>BTk, the first connection train cannot arrive at transfer station within the maximum tolerable transfer waiting time; in this case, the FCTI is equal to 1, and it is a transfer failure; otherwise transfer passengers can catch the connection trains in the tolerable waiting time, and the FCTI is equal to 0.(3)Mσkq-1≤Li′s′1-Aisq+ek-BTk≤Mσkqwhere BTk is the maximum tolerable transfer waiting time.


## 3.3. Transfer Waiting Time

### 3.3.1. Transfer Success

Under transfer success circumstances, transferring passenger can board the connection trains. Nonetheless, we still cannot decide which connection train is the transfer train and calculate the relevant transfer waiting time. Here, we assume that train person capacity is sufficient during the start- and end-of-service period and passengers will always board the first arriving train after they reach the platform for purpose of a short waiting time, which implies that only the first arriving train can be the transfer train.Thus, the transfer waiting time can be modelled via (4) which delimits the fact that if and only if αkq(q′-1)=0, αkqq′=1, the transfer waiting time can be positive.(4)Li′s′q′-Aisq+ek-Mαkqq′-1≤wkqq′,q′≠1When TCT is nonnegative andαkq(q′-1)=0, the connection train q′ is the transfer train of the feeder train q, and the transfer waiting time wkqq′ is equal to the TCT, as illustrated in Figure 2. When the TCT is nonnegative and αkq(q′-1)=1, the left side of constraint (4) is negative due to the large positive number M, and the constrain (4) equates the pointless constraint wkqq′≥0. When the TCT is negative, the constraint (4) makes no sense likewise.Figure 2
Connection relationships between feeder trains and connection trains.During the end-of-service period, ifLi′s′1≤Aisq+ek≤Li′s′1+hmaxs′, the transfer train of the feeder train q should be one of the previous trains of the 1-th connection train (the first train we consider during the end-of-service period). Since the timetables of the previous periods are unknown, this part of waiting time is not taken into account. We assume that, for the feeder train q, if Li′s′1-Aisq+ek is nonnegative and less than half of the sum of the minimum and maximum headway of connection line s′, the transfer train is the 1-th train on line s′; otherwise it is one of the previous trains. Accordingly, we introduce binary variable γkq and the transfer waiting time between the feeder train q and the 1-th connection train wkq1q′=1, which are not be allowed for in constraint (4), can be counted via (6).(5)Mγkq-1≤Li′s′1-Aisq+ek-hmins′+hmaxs′2≤Mγkq(6)Li′s′1-Aisq+ek-Mγkq≤wkq1Analogously, as to the start-of-service period, via incorporating the constraint (7) into (3), the transfer waiting time wkq1q′=1 can be modelled.(7)Li′s′1-Aisq+ek-Mσkq≤wkq1


### 3.3.2. Transfer Failure

As mentioned above, passengers suffering a transfer failure will experience an extremely bad travel. It does not mean that the part of passengers certainly cannot reach the destination, because they may choose other traffic modes to complete the rest travel. Here, we introduce penalty coefficients to quantify and measure the adverse effects of transfer failure. Moreover, they can be set based on the operation situation of all the other traffic modes during the start- and end-of-service period to cater to the reality.Noted that the penalty coefficients are utilized to impose some penalty time on transfer waiting time when it is a transfer failure. Thus, they should have no effects under transfer success circumstances. Accordingly, penalty constraints are jointly established to cope with both cases concurrently via incorporating the LCTI and the FCTI, as demonstrated via (8) and (9).During the end-of-service period, whenAisq+ek>Li′s′Ns′, passengers fail to catch the last connection trains, and the LCTI is equal to 0 according to constraint (2). In this case, penalty coefficients CkL are utilized to impose some penalty time on transfer failure. More importantly, it makes no sense to the transfer waiting time of transfer success.(8)CkL1-αkqNs′≤wkqNs′Analogously, during the start-of-service period, whenLi′s′1-(Aisq+ek)>BTk, it is a transfer failure, and the FCTI is equal to 1 according to constraint (3). In this case, the transfer waiting time is equal to penalty coefficients CkF, as demonstrated in Figure 3. In the case of transfer success, the penalty constraint has no effects.(9)CkFσkq≤wkq1Figure 3
Transfer waiting time during the start-of-service period.In summary, the transfer waiting time is determined by combining all the joint constraints (1)~(9) and implies twofold meanings: (1) the actual waiting time when it is a transfer success; (2) the penalty waiting time when it is a transfer failure.


## 3.3.1. Transfer Success

Under transfer success circumstances, transferring passenger can board the connection trains. Nonetheless, we still cannot decide which connection train is the transfer train and calculate the relevant transfer waiting time. Here, we assume that train person capacity is sufficient during the start- and end-of-service period and passengers will always board the first arriving train after they reach the platform for purpose of a short waiting time, which implies that only the first arriving train can be the transfer train.Thus, the transfer waiting time can be modelled via (4) which delimits the fact that if and only if αkq(q′-1)=0, αkqq′=1, the transfer waiting time can be positive.(4)Li′s′q′-Aisq+ek-Mαkqq′-1≤wkqq′,q′≠1When TCT is nonnegative andαkq(q′-1)=0, the connection train q′ is the transfer train of the feeder train q, and the transfer waiting time wkqq′ is equal to the TCT, as illustrated in Figure 2. When the TCT is nonnegative and αkq(q′-1)=1, the left side of constraint (4) is negative due to the large positive number M, and the constrain (4) equates the pointless constraint wkqq′≥0. When the TCT is negative, the constraint (4) makes no sense likewise.Figure 2
Connection relationships between feeder trains and connection trains.During the end-of-service period, ifLi′s′1≤Aisq+ek≤Li′s′1+hmaxs′, the transfer train of the feeder train q should be one of the previous trains of the 1-th connection train (the first train we consider during the end-of-service period). Since the timetables of the previous periods are unknown, this part of waiting time is not taken into account. We assume that, for the feeder train q, if Li′s′1-Aisq+ek is nonnegative and less than half of the sum of the minimum and maximum headway of connection line s′, the transfer train is the 1-th train on line s′; otherwise it is one of the previous trains. Accordingly, we introduce binary variable γkq and the transfer waiting time between the feeder train q and the 1-th connection train wkq1q′=1, which are not be allowed for in constraint (4), can be counted via (6).(5)Mγkq-1≤Li′s′1-Aisq+ek-hmins′+hmaxs′2≤Mγkq(6)Li′s′1-Aisq+ek-Mγkq≤wkq1Analogously, as to the start-of-service period, via incorporating the constraint (7) into (3), the transfer waiting time wkq1q′=1 can be modelled.(7)Li′s′1-Aisq+ek-Mσkq≤wkq1


## 3.3.2. Transfer Failure

As mentioned above, passengers suffering a transfer failure will experience an extremely bad travel. It does not mean that the part of passengers certainly cannot reach the destination, because they may choose other traffic modes to complete the rest travel. Here, we introduce penalty coefficients to quantify and measure the adverse effects of transfer failure. Moreover, they can be set based on the operation situation of all the other traffic modes during the start- and end-of-service period to cater to the reality.Noted that the penalty coefficients are utilized to impose some penalty time on transfer waiting time when it is a transfer failure. Thus, they should have no effects under transfer success circumstances. Accordingly, penalty constraints are jointly established to cope with both cases concurrently via incorporating the LCTI and the FCTI, as demonstrated via (8) and (9).During the end-of-service period, whenAisq+ek>Li′s′Ns′, passengers fail to catch the last connection trains, and the LCTI is equal to 0 according to constraint (2). In this case, penalty coefficients CkL are utilized to impose some penalty time on transfer failure. More importantly, it makes no sense to the transfer waiting time of transfer success.(8)CkL1-αkqNs′≤wkqNs′Analogously, during the start-of-service period, whenLi′s′1-(Aisq+ek)>BTk, it is a transfer failure, and the FCTI is equal to 1 according to constraint (3). In this case, the transfer waiting time is equal to penalty coefficients CkF, as demonstrated in Figure 3. In the case of transfer success, the penalty constraint has no effects.(9)CkFσkq≤wkq1Figure 3
Transfer waiting time during the start-of-service period.In summary, the transfer waiting time is determined by combining all the joint constraints (1)~(9) and implies twofold meanings: (1) the actual waiting time when it is a transfer success; (2) the penalty waiting time when it is a transfer failure.


## 4. Synchronization Timetabling during the Start- and End-of-Service Period

Synchronization timetabling focuses on reducing transfer waiting time. Typically, when it comes to the start- and end-of-service period, passengers travelling within a network may encounter a transfer failure. Thus, synchronization necessitate consideration of transfer availability concurrently. In the section, a timetable synchronization optimization (TSO) model during the start- and end-of-service period is developed via coordinating the arrival and departure time of trains at transfer stations in a network.


### 4.1. Assumptions

Here, several assumptions are made throughout the paper for simplicity in the model formulation.Assumption 1.
The transfer walking time is assumed constant and fixed for all transferring passengers without allowing for the difference of passengers’ age, gender, packages, etc. The average values are usually used and obtained based on actual surveys and the fluctuations have insignificant effect on the coordinated schemes.Assumption 2.
The path choices of passengers are known and fixed without considering the slight adjustment of the timetable plan, which are generally explained by simulation. Although there may be alternative lines in the system to complete the travel, we do not consider it in this paper.Assumption 3.
The passenger flows are evenly distributed within a short time period. It is rather difficult to count the exact number of passengers getting on a train due to the randomness of the arrival time of passenger and the differences of headway between trains.Assumption 4.
The train person capacity is sufficient to accommodate all passengers who want to ride the train during the start- and end-of-service period, and passengers will always ride the first arriving train after reaching the connection platform.


### 4.2. TSO Model during the Start- and End-of-Service Period

Synchronization timetabling problem during the start- and end-of-service period necessitates consideration of both transfer waiting time with respect to transfer success and transfer availability with respect to transfer failure. As mentioned in Section3.3.2, the adverse effects of a transfer failure are converted to a penalty time on transfer waiting time. Hence, in views of both transfer success and transfer failure circumstances, we implement the total transfer waiting time within a network as the objective to construct the TSO model, as demonstrated via (10). Therefore, the model is given as follows:(10)Min∑k∑q=1Ns∑q′=1Ns′ckqwkqq′(11)Lisq=Aisq+Disq(12)Aisq=L0sq+∑j=1iRjsq+∑j=1i-1Djsq(13)hmins≤Lisq-Lisq-1≤hmaxs(14)ymins≤Amssq-L0sq≤ymins(15)Mαkqq′-1≤Li′s′q′-Aisq+ek≤Mαkqq′(16)Li′s′q′-Aisq+ek-Mαkqq′-1≤wkqq′,q≠1(17)Lasttrains:Mγkq-1≤Li′s′1-Aisq+ek-hmins′+hmaxs′2≤MγkqLi′s′1-Aisq+ek-Mγkq≤wkq1CkL1-αkqNs′≤wkqNs′(18)Firsttrains:Mσkq-1≤Li′s′q′-Aisq+ek-BTk≤MσkqLi′s′1-Aisq+ek-Mσkq≤wkq1CkFσkq≤wkq1(19)ri,mins≤Risq≤ri,maxs,di,mins≤Disq≤di,maxs,zi,mins≤Lis1≤zi,maxs(20)Aisq,Lisq,Risq,Disq∈N,s=1,2,⋯,U,q=1,2,⋯,Ns,i=0,1,⋯,Gs(21)αkqq′,γkq,σkq=0,1,wkqq′≥0,k=1,2,⋯,KGenerally, train operation follows a cyclic pattern of events: departure, running, arrival, and dwelling. Because of the continuity of these events, the departure time of a train at a station is the sum of the arrival time and dwell time at this station, as modelled via (11); meanwhile, the arrival time of a train at a station is the sum of the departure time at the first station, the total running time of the train, and the dwell time at all the previous stations, as modelled via (12). The constraint defined via (13) imposes a minimum headway between departures of consecutive trains to guarantee operational safety and a maximum headway to maintain the standard level of service. Moreover, the constraint presented via (14) limits the total travel time of a train, which is defined as the time travelling from the originating terminal station to the destination terminal station. The constraints defined via (15)-(18) are consistent with constraints (1)-(8). Meanwhile, the acceptable ranges for running time, dwell time, and departure time at the first station on each line are delimited in (19); in addition, the constraint presented via (20)-(21) requires that the timetable variables should be a nonnegative integer and delimits the fact that binary variables must be 0 or 1.Furthermore, solutions of TSO model have an interesting characteristic: there are a herein correlation between the TTIs for each transfer arc. To be specific, since the departure time of the subsequent connection trains at a station will increase over time, the TCT for a certain feeder trainq will increase together. Consequently, according to constraints (1), the TTIs would not reduce, as illustrated via (22). Analogously, since the arrival time of the subsequent feeder trains at a station will increase over time, the TCT for a certain connection train q′ will decrease. In the same way, the TTIs would not be larger than the previous, as illustrated via (23).(22)αkq1≤αkq2≤⋯≤αkqNs′(23)αk1q′≥αk2q′≥⋯≥αkNsq′Figure4 shows a typical structure of the matrix formed by the TTIs for each transfer arc k. By adding the two constraints (22)-(23) to the TSO model before solving it, the search space of algorithm can be shrunk and the solution efficiency can be improved.Figure 4
Typical structure of the matrix formed by the TTIs for each transfer arck.It is worth mentioning that whenNs=1,∀s=1,2,⋯,U, the synchronization timetabling problem merely focuses on the first one train during the start-of-service period or the last one train during the end-of-service period on each line within a network; in this case, the TSO model could be a first or last train timetable coordination model. Furthermore, we can fix the arrival and departure time of some trains, for example, the last train during the start-of-service period or the first train during the end-of-service period, to smoothly incorporate the generated synchronization timetables during the start- and end-of-service period into the timetables during other periods.The model we proposed is a mixed integer linear programming model with a large number of binary variables. ILOG CPLEX (CPLEX for short), as a top software package to deal with the linear programming problem and the mixed integer programming problem, is powerful and has excellent properties, which is used rather extensively. Hence, we solve the model by CPLEX, and the model is built and compiled via C# on a desktop computer.


## 4.1. Assumptions

Here, several assumptions are made throughout the paper for simplicity in the model formulation.Assumption 1.
The transfer walking time is assumed constant and fixed for all transferring passengers without allowing for the difference of passengers’ age, gender, packages, etc. The average values are usually used and obtained based on actual surveys and the fluctuations have insignificant effect on the coordinated schemes.Assumption 2.
The path choices of passengers are known and fixed without considering the slight adjustment of the timetable plan, which are generally explained by simulation. Although there may be alternative lines in the system to complete the travel, we do not consider it in this paper.Assumption 3.
The passenger flows are evenly distributed within a short time period. It is rather difficult to count the exact number of passengers getting on a train due to the randomness of the arrival time of passenger and the differences of headway between trains.Assumption 4.
The train person capacity is sufficient to accommodate all passengers who want to ride the train during the start- and end-of-service period, and passengers will always ride the first arriving train after reaching the connection platform.


## 4.2. TSO Model during the Start- and End-of-Service Period

Synchronization timetabling problem during the start- and end-of-service period necessitates consideration of both transfer waiting time with respect to transfer success and transfer availability with respect to transfer failure. As mentioned in Section3.3.2, the adverse effects of a transfer failure are converted to a penalty time on transfer waiting time. Hence, in views of both transfer success and transfer failure circumstances, we implement the total transfer waiting time within a network as the objective to construct the TSO model, as demonstrated via (10). Therefore, the model is given as follows:(10)Min∑k∑q=1Ns∑q′=1Ns′ckqwkqq′(11)Lisq=Aisq+Disq(12)Aisq=L0sq+∑j=1iRjsq+∑j=1i-1Djsq(13)hmins≤Lisq-Lisq-1≤hmaxs(14)ymins≤Amssq-L0sq≤ymins(15)Mαkqq′-1≤Li′s′q′-Aisq+ek≤Mαkqq′(16)Li′s′q′-Aisq+ek-Mαkqq′-1≤wkqq′,q≠1(17)Lasttrains:Mγkq-1≤Li′s′1-Aisq+ek-hmins′+hmaxs′2≤MγkqLi′s′1-Aisq+ek-Mγkq≤wkq1CkL1-αkqNs′≤wkqNs′(18)Firsttrains:Mσkq-1≤Li′s′q′-Aisq+ek-BTk≤MσkqLi′s′1-Aisq+ek-Mσkq≤wkq1CkFσkq≤wkq1(19)ri,mins≤Risq≤ri,maxs,di,mins≤Disq≤di,maxs,zi,mins≤Lis1≤zi,maxs(20)Aisq,Lisq,Risq,Disq∈N,s=1,2,⋯,U,q=1,2,⋯,Ns,i=0,1,⋯,Gs(21)αkqq′,γkq,σkq=0,1,wkqq′≥0,k=1,2,⋯,KGenerally, train operation follows a cyclic pattern of events: departure, running, arrival, and dwelling. Because of the continuity of these events, the departure time of a train at a station is the sum of the arrival time and dwell time at this station, as modelled via (11); meanwhile, the arrival time of a train at a station is the sum of the departure time at the first station, the total running time of the train, and the dwell time at all the previous stations, as modelled via (12). The constraint defined via (13) imposes a minimum headway between departures of consecutive trains to guarantee operational safety and a maximum headway to maintain the standard level of service. Moreover, the constraint presented via (14) limits the total travel time of a train, which is defined as the time travelling from the originating terminal station to the destination terminal station. The constraints defined via (15)-(18) are consistent with constraints (1)-(8). Meanwhile, the acceptable ranges for running time, dwell time, and departure time at the first station on each line are delimited in (19); in addition, the constraint presented via (20)-(21) requires that the timetable variables should be a nonnegative integer and delimits the fact that binary variables must be 0 or 1.Furthermore, solutions of TSO model have an interesting characteristic: there are a herein correlation between the TTIs for each transfer arc. To be specific, since the departure time of the subsequent connection trains at a station will increase over time, the TCT for a certain feeder trainq will increase together. Consequently, according to constraints (1), the TTIs would not reduce, as illustrated via (22). Analogously, since the arrival time of the subsequent feeder trains at a station will increase over time, the TCT for a certain connection train q′ will decrease. In the same way, the TTIs would not be larger than the previous, as illustrated via (23).(22)αkq1≤αkq2≤⋯≤αkqNs′(23)αk1q′≥αk2q′≥⋯≥αkNsq′Figure4 shows a typical structure of the matrix formed by the TTIs for each transfer arc k. By adding the two constraints (22)-(23) to the TSO model before solving it, the search space of algorithm can be shrunk and the solution efficiency can be improved.Figure 4
Typical structure of the matrix formed by the TTIs for each transfer arck.It is worth mentioning that whenNs=1,∀s=1,2,⋯,U, the synchronization timetabling problem merely focuses on the first one train during the start-of-service period or the last one train during the end-of-service period on each line within a network; in this case, the TSO model could be a first or last train timetable coordination model. Furthermore, we can fix the arrival and departure time of some trains, for example, the last train during the start-of-service period or the first train during the end-of-service period, to smoothly incorporate the generated synchronization timetables during the start- and end-of-service period into the timetables during other periods.The model we proposed is a mixed integer linear programming model with a large number of binary variables. ILOG CPLEX (CPLEX for short), as a top software package to deal with the linear programming problem and the mixed integer programming problem, is powerful and has excellent properties, which is used rather extensively. Hence, we solve the model by CPLEX, and the model is built and compiled via C# on a desktop computer.


## 5. Case Study

### 5.1. Description

To verify the performance of the model, a case study on the Beijing metro network is implemented. Figure5 is the topology map of Beijing metro network without the airport line by the end of 2016, which comprises 18 bidirectional metro lines (36 unidirectional metro lines) and 53 transfer stations. Due to the similarity of the coordination and optimization mechanism for the start-of-service period and the end-of-service period, the case study here is merely concerned with the end-of-service period, and we take about the last half hour as the end-of-service period of each line.Figure 5
Topology map of Beijing metro network.


### 5.2. Comparison Cases and Optimized Results

In order to demonstrate the advantages of the proposed model, three cases are presented for purpose of comparison. Besides, the penalty times on transfer failure for every transfer arc are all set as 30 minutes for simplicity.Case 1. The operational parameters are identical with the original timetable plan.Case 2. Only the departure time of the 1-th train at originating terminal station during the end-of-service period can be adjusted; and other operational parameters are consistent with the original timetable plan.Case 3. The headways can be adjusted ±60 seconds based on the average headways, the dwell times can be adjusted ±5 seconds based on the original planned dwell times, and the running times are identical with the original.The optimized results are all generated via C#, and computational results are presented by using the integer linear solver CPLEX 12.5 within a time limit of two hours on a desktop computer (Intel Pentium CPU G3240 3.1 GHz, 8 GB RAM), as shown in Table1. The ATWT is the average transfer waiting time of all transferring passengers (including transfer success passengers and transfer failure passengers). The PTFP is the proportion of transfer failure passengers. The ATWT_TSP is the average transfer waiting time of transfer success passengers, which can be roughly deduced by the formula ATWT-1800×PTFP/(1-PTFP). The solution time is the average computational time in seconds exclusive of the preprocessing time.Table 1
Optimized results.
Case ATWT PTFP ATWT_TSP Solution time Case 1 915 s 41.3 % 292 s -- Case 2 791 s 36.6 % 209 s 108.43 s Case 3 633 s 29.4 % 147 s 4591.52 sCompared to original timetable plan Case 1, Case 2, and Case 3 are more efficient and available in terms of transfer, as they yield a less ATWT and a smaller PTFP. Moreover, Case 3 exhibits better performance with respect to both ATWT and PTFP; this indicates that unfixed headway and dwell time can increase the possibilities of synchronizing and coordinating the transfer during the end-of-service period; and thus the solution time grows sharply to seek for the optimal solutions due to the increase of binary variables and the connection schemes. Furthermore, the general notion of synchronization merely shows solicitude for transfer success passengers; thus, the ATWT_TSP are discussed here. The reduction in ATWT_TSP exhibits the properties of synchronization of our optimized model.In summary, our developed model synthesizes the general notion of transfer synchronization and the concept of transfer availability during the start- and end-of-service period and can concurrently reduce transfer waiting time and improve transfer availably.


### 5.3. Sensitivity Analysis

To provide guidance on adjustment tactic for metro operators, sensitivity analysis of headway, dwell time, and running time is implemented to expound which operational parameters in the inputs to the model will produce the greatest effects on optimized results.


#### 5.3.1. The Headway

The adjustment of headway is more flexible and can be conducted easily, so it is the most common strategy used in research and practice for timetabling problems. In order to analyze the sensitivity of the headway, we design four different cases, in which the headways are the variable parameters and the dwell time and running time are fixed and identical with the planned timetable.The optimized results are shown in Table2. As can be seen, the PTFP yields a significance reduction. This is because the range of headways provides great flexibility of the arrival and departure time of trains and thus obtained a significant sensitivity on the PTFP. On the other hand, the ATWT_TSP does not always go down but the ATWT are indeed improved, which implies that the optimized model does not necessarily reduce the transfer waiting time of transfer success passengers to optimize the timetable. In other words, the optimal timetable is a systematic optimal scheme for all transferring passengers. Besides, the solution time grows due to an improvement in the flexibility of the timetable.Table 2
Headway sensitivity analysis and optimized results.
Optimized results The headways± 0 s The headways± 30 s The headways± 60 s The headways± 120 s ATWT 791 s 764 s 735 s 693 s PTFP 36.6 % 35.1 % 33.5 % 30.6 % ATWT_TSP 209 s 204 s 198 s 205 s Solution time 108.43 s 189.57 s 306.89 s 602.91 s


#### 5.3.2. The Dwell Time

Similarly, for purpose of the sensitivity analysis of dwell time, six cases are designed that the dwell time can be adjusted in the case of average headways and unfixed headways with±60 s. The optimized results are shown in Table 3. Among these cases, the case with the most flexible headways and dwell time performs best. Compared to Table 1, the ATWT_TSP exhibits a remarkable sensitivity of dwell time. This differences is because the complex properties of network structure makes it hard to coordinate all transfer arcs in a network, and the flexibility of dwell times enhances the elasticity in timetabling and can be used to coordinate some conflicts herein which is not easy by adjusting the headways. In this way, the solution time will grow sharply due to the more candidate solutions in the branch-and-bound tree. And as to the case with the most flexible headways and dwell times, it cannot find the optimal solution within a time limit of two hours; this is an indicative of a huge search space. In addition, as compared to the ATWT_TSP, the sensitivity on PTFP is not significant.Table 3
Dwell time sensitivity analysis and optimized results.
Optimized results The headways: ±0 s The headways: ±60 s Dwell time±0 s Dwell time±5 s Dwell time±10 s Dwell time±0 s Dwell time±5 s Dwell time±10 s ATWT 791 s 751 s 704 s 735 s 633 s 596 s PTFP 36.6 % 35.4 % 33.1 % 33.5 % 29.4 % 28.3 % ATWT_TSP 209 s 176 s 162 s 198 s 147 s 121 s Solution time 108.43 s 915.03 s 4678.84 s 306.89 s 4591.52 s 7200 s∗ The symbol “∗” means that the case is not solved to optimality within a time limit of two hours.


#### 5.3.3. The Running Time

In the same way, six cases are designed to analyze the sensitivity of running time. In consideration of the energy cost of train in actual operation, the range of running time is set as0, +2, or +5 s. (Generally, it is not impractical to coordinate the timetable plan by cutting down the running time.) The optimized results are shown in Table 4. As we can see, the effects of adjusting the running times are not remarkable in ATWT, PTFP, and ATWT_TSP. Since it cannot achieve a worthy profit, the adjustment of the running time is not recommended.Table 4
Running time sensitivity analysis and optimized results.
Optimized results The headways: ±0 s The headways: ±60 s Running time: +0 s Running time: +2 s Running time: +5 s Running time: +0 s Running time: +2 s Running time: +5 s ATWT 791 s 772 s 759 s 735 s 721 s 708 s PTFP 36.6 % 36.2 % 35.7 % 33.5 % 32.5 % 31.6 % ATWT_TSP 209 s 189 s 181 s 198 s 201 s 203 s Solution time 108.43 s 343.28 s 1312.57 s 306.89 s 2197.54 s 2879.02 s


## 5.1. Description

To verify the performance of the model, a case study on the Beijing metro network is implemented. Figure5 is the topology map of Beijing metro network without the airport line by the end of 2016, which comprises 18 bidirectional metro lines (36 unidirectional metro lines) and 53 transfer stations. Due to the similarity of the coordination and optimization mechanism for the start-of-service period and the end-of-service period, the case study here is merely concerned with the end-of-service period, and we take about the last half hour as the end-of-service period of each line.Figure 5
Topology map of Beijing metro network.


## 5.2. Comparison Cases and Optimized Results

In order to demonstrate the advantages of the proposed model, three cases are presented for purpose of comparison. Besides, the penalty times on transfer failure for every transfer arc are all set as 30 minutes for simplicity.Case 1. The operational parameters are identical with the original timetable plan.Case 2. Only the departure time of the 1-th train at originating terminal station during the end-of-service period can be adjusted; and other operational parameters are consistent with the original timetable plan.Case 3. The headways can be adjusted ±60 seconds based on the average headways, the dwell times can be adjusted ±5 seconds based on the original planned dwell times, and the running times are identical with the original.The optimized results are all generated via C#, and computational results are presented by using the integer linear solver CPLEX 12.5 within a time limit of two hours on a desktop computer (Intel Pentium CPU G3240 3.1 GHz, 8 GB RAM), as shown in Table1. The ATWT is the average transfer waiting time of all transferring passengers (including transfer success passengers and transfer failure passengers). The PTFP is the proportion of transfer failure passengers. The ATWT_TSP is the average transfer waiting time of transfer success passengers, which can be roughly deduced by the formula ATWT-1800×PTFP/(1-PTFP). The solution time is the average computational time in seconds exclusive of the preprocessing time.Table 1
Optimized results.
Case ATWT PTFP ATWT_TSP Solution time Case 1 915 s 41.3 % 292 s -- Case 2 791 s 36.6 % 209 s 108.43 s Case 3 633 s 29.4 % 147 s 4591.52 sCompared to original timetable plan Case 1, Case 2, and Case 3 are more efficient and available in terms of transfer, as they yield a less ATWT and a smaller PTFP. Moreover, Case 3 exhibits better performance with respect to both ATWT and PTFP; this indicates that unfixed headway and dwell time can increase the possibilities of synchronizing and coordinating the transfer during the end-of-service period; and thus the solution time grows sharply to seek for the optimal solutions due to the increase of binary variables and the connection schemes. Furthermore, the general notion of synchronization merely shows solicitude for transfer success passengers; thus, the ATWT_TSP are discussed here. The reduction in ATWT_TSP exhibits the properties of synchronization of our optimized model.In summary, our developed model synthesizes the general notion of transfer synchronization and the concept of transfer availability during the start- and end-of-service period and can concurrently reduce transfer waiting time and improve transfer availably.


## 5.3. Sensitivity Analysis

To provide guidance on adjustment tactic for metro operators, sensitivity analysis of headway, dwell time, and running time is implemented to expound which operational parameters in the inputs to the model will produce the greatest effects on optimized results.


### 5.3.1. The Headway

The adjustment of headway is more flexible and can be conducted easily, so it is the most common strategy used in research and practice for timetabling problems. In order to analyze the sensitivity of the headway, we design four different cases, in which the headways are the variable parameters and the dwell time and running time are fixed and identical with the planned timetable.The optimized results are shown in Table2. As can be seen, the PTFP yields a significance reduction. This is because the range of headways provides great flexibility of the arrival and departure time of trains and thus obtained a significant sensitivity on the PTFP. On the other hand, the ATWT_TSP does not always go down but the ATWT are indeed improved, which implies that the optimized model does not necessarily reduce the transfer waiting time of transfer success passengers to optimize the timetable. In other words, the optimal timetable is a systematic optimal scheme for all transferring passengers. Besides, the solution time grows due to an improvement in the flexibility of the timetable.Table 2
Headway sensitivity analysis and optimized results.
Optimized results The headways± 0 s The headways± 30 s The headways± 60 s The headways± 120 s ATWT 791 s 764 s 735 s 693 s PTFP 36.6 % 35.1 % 33.5 % 30.6 % ATWT_TSP 209 s 204 s 198 s 205 s Solution time 108.43 s 189.57 s 306.89 s 602.91 s


### 5.3.2. The Dwell Time

Similarly, for purpose of the sensitivity analysis of dwell time, six cases are designed that the dwell time can be adjusted in the case of average headways and unfixed headways with±60 s. The optimized results are shown in Table 3. Among these cases, the case with the most flexible headways and dwell time performs best. Compared to Table 1, the ATWT_TSP exhibits a remarkable sensitivity of dwell time. This differences is because the complex properties of network structure makes it hard to coordinate all transfer arcs in a network, and the flexibility of dwell times enhances the elasticity in timetabling and can be used to coordinate some conflicts herein which is not easy by adjusting the headways. In this way, the solution time will grow sharply due to the more candidate solutions in the branch-and-bound tree. And as to the case with the most flexible headways and dwell times, it cannot find the optimal solution within a time limit of two hours; this is an indicative of a huge search space. In addition, as compared to the ATWT_TSP, the sensitivity on PTFP is not significant.Table 3
Dwell time sensitivity analysis and optimized results.
Optimized results The headways: ±0 s The headways: ±60 s Dwell time±0 s Dwell time±5 s Dwell time±10 s Dwell time±0 s Dwell time±5 s Dwell time±10 s ATWT 791 s 751 s 704 s 735 s 633 s 596 s PTFP 36.6 % 35.4 % 33.1 % 33.5 % 29.4 % 28.3 % ATWT_TSP 209 s 176 s 162 s 198 s 147 s 121 s Solution time 108.43 s 915.03 s 4678.84 s 306.89 s 4591.52 s 7200 s∗ The symbol “∗” means that the case is not solved to optimality within a time limit of two hours.


### 5.3.3. The Running Time

In the same way, six cases are designed to analyze the sensitivity of running time. In consideration of the energy cost of train in actual operation, the range of running time is set as0, +2, or +5 s. (Generally, it is not impractical to coordinate the timetable plan by cutting down the running time.) The optimized results are shown in Table 4. As we can see, the effects of adjusting the running times are not remarkable in ATWT, PTFP, and ATWT_TSP. Since it cannot achieve a worthy profit, the adjustment of the running time is not recommended.Table 4
Running time sensitivity analysis and optimized results.
Optimized results The headways: ±0 s The headways: ±60 s Running time: +0 s Running time: +2 s Running time: +5 s Running time: +0 s Running time: +2 s Running time: +5 s ATWT 791 s 772 s 759 s 735 s 721 s 708 s PTFP 36.6 % 36.2 % 35.7 % 33.5 % 32.5 % 31.6 % ATWT_TSP 209 s 189 s 181 s 198 s 201 s 203 s Solution time 108.43 s 343.28 s 1312.57 s 306.89 s 2197.54 s 2879.02 s


## 5.3.1. The Headway

The adjustment of headway is more flexible and can be conducted easily, so it is the most common strategy used in research and practice for timetabling problems. In order to analyze the sensitivity of the headway, we design four different cases, in which the headways are the variable parameters and the dwell time and running time are fixed and identical with the planned timetable.The optimized results are shown in Table2. As can be seen, the PTFP yields a significance reduction. This is because the range of headways provides great flexibility of the arrival and departure time of trains and thus obtained a significant sensitivity on the PTFP. On the other hand, the ATWT_TSP does not always go down but the ATWT are indeed improved, which implies that the optimized model does not necessarily reduce the transfer waiting time of transfer success passengers to optimize the timetable. In other words, the optimal timetable is a systematic optimal scheme for all transferring passengers. Besides, the solution time grows due to an improvement in the flexibility of the timetable.Table 2
Headway sensitivity analysis and optimized results.
Optimized results The headways± 0 s The headways± 30 s The headways± 60 s The headways± 120 s ATWT 791 s 764 s 735 s 693 s PTFP 36.6 % 35.1 % 33.5 % 30.6 % ATWT_TSP 209 s 204 s 198 s 205 s Solution time 108.43 s 189.57 s 306.89 s 602.91 s


## 5.3.2. The Dwell Time

Similarly, for purpose of the sensitivity analysis of dwell time, six cases are designed that the dwell time can be adjusted in the case of average headways and unfixed headways with±60 s. The optimized results are shown in Table 3. Among these cases, the case with the most flexible headways and dwell time performs best. Compared to Table 1, the ATWT_TSP exhibits a remarkable sensitivity of dwell time. This differences is because the complex properties of network structure makes it hard to coordinate all transfer arcs in a network, and the flexibility of dwell times enhances the elasticity in timetabling and can be used to coordinate some conflicts herein which is not easy by adjusting the headways. In this way, the solution time will grow sharply due to the more candidate solutions in the branch-and-bound tree. And as to the case with the most flexible headways and dwell times, it cannot find the optimal solution within a time limit of two hours; this is an indicative of a huge search space. In addition, as compared to the ATWT_TSP, the sensitivity on PTFP is not significant.Table 3
Dwell time sensitivity analysis and optimized results.
Optimized results The headways: ±0 s The headways: ±60 s Dwell time±0 s Dwell time±5 s Dwell time±10 s Dwell time±0 s Dwell time±5 s Dwell time±10 s ATWT 791 s 751 s 704 s 735 s 633 s 596 s PTFP 36.6 % 35.4 % 33.1 % 33.5 % 29.4 % 28.3 % ATWT_TSP 209 s 176 s 162 s 198 s 147 s 121 s Solution time 108.43 s 915.03 s 4678.84 s 306.89 s 4591.52 s 7200 s∗ The symbol “∗” means that the case is not solved to optimality within a time limit of two hours.


## 5.3.3. The Running Time

In the same way, six cases are designed to analyze the sensitivity of running time. In consideration of the energy cost of train in actual operation, the range of running time is set as0, +2, or +5 s. (Generally, it is not impractical to coordinate the timetable plan by cutting down the running time.) The optimized results are shown in Table 4. As we can see, the effects of adjusting the running times are not remarkable in ATWT, PTFP, and ATWT_TSP. Since it cannot achieve a worthy profit, the adjustment of the running time is not recommended.Table 4
Running time sensitivity analysis and optimized results.
Optimized results The headways: ±0 s The headways: ±60 s Running time: +0 s Running time: +2 s Running time: +5 s Running time: +0 s Running time: +2 s Running time: +5 s ATWT 791 s 772 s 759 s 735 s 721 s 708 s PTFP 36.6 % 36.2 % 35.7 % 33.5 % 32.5 % 31.6 % ATWT_TSP 209 s 189 s 181 s 198 s 201 s 203 s Solution time 108.43 s 343.28 s 1312.57 s 306.89 s 2197.54 s 2879.02 s


## 6. Conclusions

To date, foci of interest on the timetabling problem with respect to transfer failure during the start- or end-of-service period are merely relevant to the first or last train on each line within a network and are thus exclusive of other trains, even though transferring passengers on these trains are likely to experience a transfer failure as well. Alternatively, in this paper, we implement the synchronization timetabling in consideration of all train during the start- and end-of-service period. The main contributions of this paper can be summarized as follows:(1)
Through analysis of the train connection time (TCT), the transfer train index (TTI) is formulated to identify the transfer train and calculated the relevant transfer waiting time with respect to a transfer success.(2)
This paper devises the last connection train index (LCTI) and the first connection train index (FCTI) to distinguish transfer failure from transfer success by building the relation between the feeder train and the first or last connection train.(3)
This paper established the penalty constraint to measure the adverse effects of transfer failure. Thereby, by implementing the transfer waiting time of all transferring passengers (transfer success passengers and transfer failure passengers), the timetable synchronization optimization (TSO) model can concurrently reduce transfer waiting time and improve transfer availability.Lastly, a case study on Beijing metro network is conducted to demonstrate that our developed model can generate synchronization solutions with respect to both transfer efficiency and transfer availability. Furthermore, the sensitivity analysis shows that the range of headways can provide great flexibility of the arrival and departure time of trains and has a significant effects on the proportion of transfer failure passengers (PTFP); and the flexibility of dwell times enhances the elasticity in timetabling that can be used to coordinate some conflicts herein effectively, thereby leading to a remarkable reduction in transfer waiting time of transfer success passengers (ATWT_TSP); but the running time has low sensitivities in the optimized results and the adjustment of that is not recommended.



---

*Source: 3835270-2018-07-03.xml*