# A Practical Method for Timetable Rescheduling in Subway Networks during the End-of-Service Period

Authors: Wenkai Xu; Peng Zhao; Liqiao Ning
Journal: Journal of Advanced Transportation
 (2018)

---

## Abstract

This study proposes a biobjective optimization method for timetable rescheduling during the end-of-service period of a subway network, taking all stakeholders’ interests into consideration. We seek to minimize the total transfer waiting time for all transfer passengers, meanwhile minimizing the deviation to the scheduled timetable. Theε-constraint method and linearization techniques are utilized to obtain the approximate Pareto optimal solutions within limited seconds, allowing for figuring out the trade-off between the two objectives. The method is validated by numerical experiments for different delay scenarios based on a real-world case: the Beijing subway network.


---

## Body

## 1. Introduction

Recently, there are several contributions to the last-train timetabling problem of a subway system, which focused only on the last train of each line in the network and expected to generate a more efficiently scheduled timetable for all last trains [1–4]. However, it is very common that the scheduled timetable cannot be implemented because of unavoidable delays that occur at an operational level [5]. As a result, this study is devoted to the timetable rescheduling problem during a specific period: the end-of-service period.Typically, most subway systems will be closed to the public at midnight or thereabouts for maintenance. Owing to the differences in passenger flow characteristics between different lines in a subway network, the operational time frames vary considerably among different lines. To be specific, the end-of-service period in this study is defined as a period of time from the scheduled departure time of the earliest last train from its originating station (among all last trains of all lines) to the time when all trains finish their jobs.Because of unavoidable disturbances in the daily operation, a lot of contributions have been made to the timetable rescheduling problem during other periods (e.g., peak hours) [6]. But there is a considerable difference between the end-of-service period and other periods. For example, if a transfer passenger misses a connecting train due to a disturbance before the end-of-service period, there is always a next connecting train which the transfer passenger can board. But during the end-of-service period, the missed connecting train may be the last train of the connecting line; if so, the transfer passenger cannot finish his/ her trip via the subway system, which will bring a lot of inconvenience to the transfer passenger.As a result, in order to deal with the disturbances occurring during the end-of-service period, the first contribution of this study is that a timetable rescheduling model is proposed from a stakeholder-oriented perspective with the consideration of benefits of both passengers and operating agencies. On the one hand, we seek to minimize the total transfer waiting time (TTWT) of all transfer passengers, and a penalty time is adopted if transfer passengers miss their last connecting trains, which benefits improving the level of service (LOS) after disturbances. On the other hand, we try to minimize the deviation between the rescheduled timetable and the scheduled timetable, which also benefits passengers who do not need to transfer.In addition, in contrast to previous studies that focused only on the last train of each line, there are multiple trains running on each line during the end-of-service period, which means that the train connection relationship in transfer stations becomes much more complicated. But, the timetable rescheduling is carried out through real-time adjustment of an existing schedule, with a consequent need for fast computation. In order to solve the practical problem of a large-scale and complex network efficiently, we utilize theε-constraint method and some linearization techniques to convert the proposed model into an integer linear programming (ILP) model that can be solved by Cplex speedily, which constitutes the second contribution of this study.The third contribution of this study is that a real-world case study of the Beijing subway network is presented to validate the effectiveness of the proposed method. Historical automatic fare collection (AFC) data of the Beijing subway system is available to obtain the number of transfer passengers of each connection, as an important input of our model. The approximate Pareto frontier is obtained by calculating the approximate Pareto optimal solutions, which helps us understand the trade-off of the two objectives.The rest of this study is organized as follows. Section2 reviews some recent studies about timetable rescheduling and last-train timetabling. The stakeholder-oriented model for timetable rescheduling during the end-of-service period is proposed in Section 3. Section 4 presents the model conversion and the solution strategy. Some experiments based on a real-world case, the Beijing subway network, are carried out in Section 5. Section 6 draws some conclusions and future directions in brief.


## 2. Literature Review

The literature review presented in this section focuses on two aspects: timetable rescheduling and last-train timetabling. Some recent publications are reviewed below in detail.


### 2.1. Timetable Rescheduling

There are a lot of studies focusing on timetable rescheduling, which can be classified by disturbance or disruption, microscopic or macroscopic, and passenger-oriented or train-oriented [6]. Various approaches have been developed in these previous studies.From a train-oriented perspective, D’Ariano et al. [7] regarded the timetable rescheduling problem as a huge job shop scheduling problem with no-store constraints and modeled the problem with an alternative graph formulation to minimize the deviation from the scheduled timetable. They proposed a branch and bound algorithm with implication rules enabling the speed up of the computation. Törnquist and Persson [8] presented a MIP model to minimize a cost function based on train delays considering reordering and rerouting of trains. But for certain scenarios, it is difficult to find good solutions within seconds. Therefore, Krasemann [9] designed a greedy algorithm to quickly find a good solution by performing a depth-first search. Dündar and Șahin [10] developed a genetic algorithm to minimize the total weighted delay. The algorithm could reduce total delay time by around half in comparison to an artificial neural network method developed to mimic the decision behavior of dispatchers.From a passenger-oriented perspective, since Schöbel [11] proposed the first MIP model for the delay management problem to minimize the total delay time of all passengers, the model has been further extended in Schöbel [12], Schachtebeck and Schöbel [13], and Dollevoet et al. [14, 15] by considering limited capacity of tracks, priority decisions, rerouting passengers, and limited capacity of stations. Binder et al. [16] proposed an ILP model with three objectives: the passenger satisfaction, the operational costs, and the deviation from the scheduled timetable. Strategies include canceling, delaying, rerouting the trains, and scheduling emergency trains.More recently, there are several publications focusing on timetable rescheduling of a subway system. However, methods were mostly proposed at a single-line level. Xu et al. [17] modeled the problem as a discrete event model considering service balance performance of both directions on a double-track subway line. The model is expected to minimize the total delay time of all trains rather than all passengers. Gao et al. [18] integrated the skip-stop pattern into the rescheduling model for a double-track subway line. An iterative algorithm was proposed to solve the model based on the model decomposition. Xu et al. [19] proposed a passenger-oriented model for rescheduling on a subway line considering the limited train capacity. The delay time of alighting passengers and the penalty time of stranded passengers constitute the generalized delay time, which is expected to be minimized.


### 2.2. Last-Train Timetabling

An enormous amount of literatures contribute to the timetabling problem, like Caprara et al. [20], Zhou and Zhong [21], Lee and Chen [22], Cacchiani and Toth [5], and Yang et al. [23]. However, the last-train timetabling problem of a subway system is an emerging issue in recent years. However, all related publications focused only on the last train of each line. Zhou et al. [1] developed an optimization model to reduce passengers’ transfer waiting time for last trains and inaccessible passenger volume of all origin-destination pairs. Coordinated departure times for all last trains are determined by the model. Kang et al. [2] established a programing model with adjustable running times and dwell times to obtain coordinated arrival and departure times of last trains at transfer stations. A genetic algorithm was designed to solve the model. Kang et al. [3] modeled the problem as a mean-variance model to improve the efficiency of transfer passengers. The model was solved by a genetic simulated annealing algorithm. Kang and Zhu [4] studied the same problem in Kang et al. [2] and designed a new heuristic algorithm outperforming both genetic algorithms and simulated annealing algorithms.Based on all publications reviewed above, we present the focus of this study here. In case there is a disturbance occurring in a subway network during the end-of-service period, this study is working to offer a practical method for timetable rescheduling from the stakeholder-oriented perspective, at a macroscopic level. Disturbances (i.e., delays of 3 to 10 minutes) will not make passengers change their predetermined origin and destination stations and paths. To the best of our knowledge, this study is the first attempt on timetable rescheduling during the end-of-service period in a subway network and real data from the AFC system is used as the model input. We want to figure out the trade-off between different objectives and provide a method of decision support to dispatchers.


## 2.1. Timetable Rescheduling

There are a lot of studies focusing on timetable rescheduling, which can be classified by disturbance or disruption, microscopic or macroscopic, and passenger-oriented or train-oriented [6]. Various approaches have been developed in these previous studies.From a train-oriented perspective, D’Ariano et al. [7] regarded the timetable rescheduling problem as a huge job shop scheduling problem with no-store constraints and modeled the problem with an alternative graph formulation to minimize the deviation from the scheduled timetable. They proposed a branch and bound algorithm with implication rules enabling the speed up of the computation. Törnquist and Persson [8] presented a MIP model to minimize a cost function based on train delays considering reordering and rerouting of trains. But for certain scenarios, it is difficult to find good solutions within seconds. Therefore, Krasemann [9] designed a greedy algorithm to quickly find a good solution by performing a depth-first search. Dündar and Șahin [10] developed a genetic algorithm to minimize the total weighted delay. The algorithm could reduce total delay time by around half in comparison to an artificial neural network method developed to mimic the decision behavior of dispatchers.From a passenger-oriented perspective, since Schöbel [11] proposed the first MIP model for the delay management problem to minimize the total delay time of all passengers, the model has been further extended in Schöbel [12], Schachtebeck and Schöbel [13], and Dollevoet et al. [14, 15] by considering limited capacity of tracks, priority decisions, rerouting passengers, and limited capacity of stations. Binder et al. [16] proposed an ILP model with three objectives: the passenger satisfaction, the operational costs, and the deviation from the scheduled timetable. Strategies include canceling, delaying, rerouting the trains, and scheduling emergency trains.More recently, there are several publications focusing on timetable rescheduling of a subway system. However, methods were mostly proposed at a single-line level. Xu et al. [17] modeled the problem as a discrete event model considering service balance performance of both directions on a double-track subway line. The model is expected to minimize the total delay time of all trains rather than all passengers. Gao et al. [18] integrated the skip-stop pattern into the rescheduling model for a double-track subway line. An iterative algorithm was proposed to solve the model based on the model decomposition. Xu et al. [19] proposed a passenger-oriented model for rescheduling on a subway line considering the limited train capacity. The delay time of alighting passengers and the penalty time of stranded passengers constitute the generalized delay time, which is expected to be minimized.


## 2.2. Last-Train Timetabling

An enormous amount of literatures contribute to the timetabling problem, like Caprara et al. [20], Zhou and Zhong [21], Lee and Chen [22], Cacchiani and Toth [5], and Yang et al. [23]. However, the last-train timetabling problem of a subway system is an emerging issue in recent years. However, all related publications focused only on the last train of each line. Zhou et al. [1] developed an optimization model to reduce passengers’ transfer waiting time for last trains and inaccessible passenger volume of all origin-destination pairs. Coordinated departure times for all last trains are determined by the model. Kang et al. [2] established a programing model with adjustable running times and dwell times to obtain coordinated arrival and departure times of last trains at transfer stations. A genetic algorithm was designed to solve the model. Kang et al. [3] modeled the problem as a mean-variance model to improve the efficiency of transfer passengers. The model was solved by a genetic simulated annealing algorithm. Kang and Zhu [4] studied the same problem in Kang et al. [2] and designed a new heuristic algorithm outperforming both genetic algorithms and simulated annealing algorithms.Based on all publications reviewed above, we present the focus of this study here. In case there is a disturbance occurring in a subway network during the end-of-service period, this study is working to offer a practical method for timetable rescheduling from the stakeholder-oriented perspective, at a macroscopic level. Disturbances (i.e., delays of 3 to 10 minutes) will not make passengers change their predetermined origin and destination stations and paths. To the best of our knowledge, this study is the first attempt on timetable rescheduling during the end-of-service period in a subway network and real data from the AFC system is used as the model input. We want to figure out the trade-off between different objectives and provide a method of decision support to dispatchers.


## 3. Model Formulation

### 3.1. Notations

Some necessary parameters are defined as follows:L: the set of subway lines in a network, L=l∣l=1,2,...,L-, where L- is the total number of lines. Specifically, a double-track subway line in practice is considered as two one-way lines.S l: the set of all stations on line l, Sl=s∣s=1,2,...,S-l, where S-l is the total number of stations on line l.V l: the set of trains still in operation on line l during the end-of-service period, Vl=v∣v=1,2,...,V-l, where V-l is the last train of line l.h l: the minimum headway of line l during the end-of-service period.t l , s r: the minimum running time for trains running from station s to s+1 on line l, including additional time of train starting and braking at stations.t l , s d: the minimum dwell time for trains stopping at station s on line l.T - l , s , v a r r: the planned arrival time for train v at station s on line l.T - l , s , v d e p: the planned departure time for train v from station s on line l.P s , s ′ v: the number of transfer passengers on train v, who need to transfer from station s on line l to station s′ on line l′. In reality, station s and station s′ are the same station with different serial numbers on different lines.t s , s ′ w a l k: the average time for transfer passengers walking from the platform of station s on line l to the platform of station s′ on line l′. It is obvious that different people have different walking speed. For model simplification, the transfer walking time is assumed to be constant for passengers of the same transfer direction in this study.The decision variables are presented as follows:T l , s , v a r r: the actual arrival time for train v at station s on line l.T l , s , v d e p: the actual departure time for train v from station s on line l.t v , v ′ w a i t: the waiting time of transfer passengers who are from train v and transfer to station s′ on line l′. This is a period of time from passengers reaching the platform of station s′ to the actual departure time of train v′ from station s′.


### 3.2. Train Connection Relationship

During the end-of-service period, once a delay occurs in the network, train connections determined in the scheduled timetable might change. To describe connections between trains of different lines, the binary variablexv,v′ is introduced. xv,v′=1 indicates that transfer passengers on feeder train v can transfer from station s on line l to station s′ on line l′ and board the connecting train v′ successfully. Figures 1 and 2 depict the successful and failed transfer connections, respectively.Figure 1
The successful transfer connection.Figure 2
The failed transfer connection.As a result,xv,v′ can be determined by the following formula:(1)xv,v′=1,ifTl′,s′,v′dep-Tl,s,varr-ts,s′walk≥00,else


### 3.3. Transfer Waiting Time and Penalty

In normal daytime operation, travelers waiting at a given station may be unable to take the first available train, e.g., if that train has no spare capacity for additional passengers (Schmöcker et al., 2011). However, it seems reasonable to suppose that demand during the end-of-service period is generally low enough to permit the assumption that capacity is always available. As a result, all passengers are assumed to board the first arriving train after they reach the platform in this study. When there is a successful transfer connection,tv,v′wait can be determined by the following formula:(2)tv,v′wait=Tl′,s′,v′dep-Tl,s,varr-ts,s′walk,ifv′=1&xv,v′=1Tl′,s′,v′dep-Tl,s,varr-ts,s′walk,ifv′>1,xv,v′-1=0&xv,v′=1But for transfer passengers, the last train of the connecting line is the last chance to finish their trips. If the connection to the last connecting train is broken, it will bring a lot of inconvenience to transfer passengers. To avoid this undesired phenomenon as much as possible, a penalty timetp is introduced in this study. If the missed connecting train is the last train of the connecting line, the transfer waiting time of these transfer passengers (i.e., failed transfer passengers, FTP) equals the penalty time; see the following formula:(3)tv,v′wait=tp,ifv′=V-l′&xv,v′=0In summary, the completetv,v′wait can be determined by the following formula:(4)tv,v′wait=Tl′,s′,v′dep-Tl,s,varr-ts,s′walk,ifv′=1&xv,v′=1Tl′,s′,v′dep-Tl,s,varr-ts,s′walk,ifv′>1,xv,v′-1=0&xv,v′=1tp,ifv′=V-l′&xv,v′=00,else


### 3.4. Model Constraints

The rescheduling model is mainly subject to some operational requirements to ensure the safety of the operation and the feasibility of the rescheduled timetable.


#### 3.4.1. Initial Delay

This constraint is to input the delay information (e.g., the delayed train, delay time, and position) to the model; see the following formula:(5)Tl∗,s∗,v∗dep≥T-l∗,s∗,v∗dep+tdorTl∗,s∗,v∗arr≥T-l∗,s∗,v∗arr+tdwhere v∗ indicates the delayed train running on line l∗. s∗ represents the station, where train v∗ is located when the disturbance occurs or the first station that is going to be visited by train v∗ after the disturbance occurs. td represents the delay time.


#### 3.4.2. Actual Arrival and Departure Time

During the process of rescheduling, the actual arrival and departure times of trains at stations cannot be earlier than the scheduled times; see the following formulas:(6)Tl,s,varr≥T-l,s,varr(7)Tl,s,vdep≥T-l,s,vdep


#### 3.4.3. Section Running Time

Under the limitations of the traction and brake performance of trains, the length of each section, safety requirements, and the actual running times of trains in sections must be longer than the minimum running times [24]; see the following formula:(8)Tl,s+1,varr-Tl,s,vdep≥tl,sr


#### 3.4.4. Dwell Time

Adjusting the dwell time is an important measure for dispatchers to control subway trains. Similar to the section running time, the actual dwell times of trains at stations must be longer than the minimum dwell times [24]; see the following formula:(9)Tl,s,vdep-Tl,s,varr≥tl,sd


#### 3.4.5. Headway

As we mentioned above, there is more than one train still running on each line during the end-of-service period. Thus, all trains running on each line should meet the requirements of minimum headway during the end-of-service period; see the following formulas:(10)Tl,s,v+1arr-Tl,s,varr≥hl(11)Tl,s,v+1dep-Tl,s,vdep≥hl


### 3.5. Optimization Objectives

We present two objectives to be optimized here. First, we try to minimize the total transfer waiting time (TTWT) for all transfer passengers, which helps to improve the LOS of the system after disturbances; see formula (12). The first objective also benefits increasing the number of successful transfer passengers after disturbances because of the penalty time set for failed transfer passengers (FTP) who miss their last connecting trains. Second, we seek to minimize the deviation between the rescheduled timetable and the scheduled timetable, which is usually dispatchers’ first goal in practice; see formula (13). Passengers who do not need to transfer after disturbances also benefit from the second objective.(12)min∑l∈L∑l′∈L∑s∈Sl∑s′∈Sl′∑v∈Vl∑v′∈Vl′Ps,s′v×tv,v′wait(13)min∑l∈L∑s∈Sl∑v∈VlTl,s,varr-T-l,s,varr+Tl,s,vdep-T-l,s,vdepThe two objectives and constraints (1) and ((4)-(11)) above consist of the complete rescheduling model during the end-of-service period. The model is called a stakeholder-oriented model because interests of both operation and passengers (transfer and nontransfer) are considered in the two objectives. The trade-off between the two objectives may help dispatchers make decisions.


## 3.1. Notations

Some necessary parameters are defined as follows:L: the set of subway lines in a network, L=l∣l=1,2,...,L-, where L- is the total number of lines. Specifically, a double-track subway line in practice is considered as two one-way lines.S l: the set of all stations on line l, Sl=s∣s=1,2,...,S-l, where S-l is the total number of stations on line l.V l: the set of trains still in operation on line l during the end-of-service period, Vl=v∣v=1,2,...,V-l, where V-l is the last train of line l.h l: the minimum headway of line l during the end-of-service period.t l , s r: the minimum running time for trains running from station s to s+1 on line l, including additional time of train starting and braking at stations.t l , s d: the minimum dwell time for trains stopping at station s on line l.T - l , s , v a r r: the planned arrival time for train v at station s on line l.T - l , s , v d e p: the planned departure time for train v from station s on line l.P s , s ′ v: the number of transfer passengers on train v, who need to transfer from station s on line l to station s′ on line l′. In reality, station s and station s′ are the same station with different serial numbers on different lines.t s , s ′ w a l k: the average time for transfer passengers walking from the platform of station s on line l to the platform of station s′ on line l′. It is obvious that different people have different walking speed. For model simplification, the transfer walking time is assumed to be constant for passengers of the same transfer direction in this study.The decision variables are presented as follows:T l , s , v a r r: the actual arrival time for train v at station s on line l.T l , s , v d e p: the actual departure time for train v from station s on line l.t v , v ′ w a i t: the waiting time of transfer passengers who are from train v and transfer to station s′ on line l′. This is a period of time from passengers reaching the platform of station s′ to the actual departure time of train v′ from station s′.


## 3.2. Train Connection Relationship

During the end-of-service period, once a delay occurs in the network, train connections determined in the scheduled timetable might change. To describe connections between trains of different lines, the binary variablexv,v′ is introduced. xv,v′=1 indicates that transfer passengers on feeder train v can transfer from station s on line l to station s′ on line l′ and board the connecting train v′ successfully. Figures 1 and 2 depict the successful and failed transfer connections, respectively.Figure 1
The successful transfer connection.Figure 2
The failed transfer connection.As a result,xv,v′ can be determined by the following formula:(1)xv,v′=1,ifTl′,s′,v′dep-Tl,s,varr-ts,s′walk≥00,else


## 3.3. Transfer Waiting Time and Penalty

In normal daytime operation, travelers waiting at a given station may be unable to take the first available train, e.g., if that train has no spare capacity for additional passengers (Schmöcker et al., 2011). However, it seems reasonable to suppose that demand during the end-of-service period is generally low enough to permit the assumption that capacity is always available. As a result, all passengers are assumed to board the first arriving train after they reach the platform in this study. When there is a successful transfer connection,tv,v′wait can be determined by the following formula:(2)tv,v′wait=Tl′,s′,v′dep-Tl,s,varr-ts,s′walk,ifv′=1&xv,v′=1Tl′,s′,v′dep-Tl,s,varr-ts,s′walk,ifv′>1,xv,v′-1=0&xv,v′=1But for transfer passengers, the last train of the connecting line is the last chance to finish their trips. If the connection to the last connecting train is broken, it will bring a lot of inconvenience to transfer passengers. To avoid this undesired phenomenon as much as possible, a penalty timetp is introduced in this study. If the missed connecting train is the last train of the connecting line, the transfer waiting time of these transfer passengers (i.e., failed transfer passengers, FTP) equals the penalty time; see the following formula:(3)tv,v′wait=tp,ifv′=V-l′&xv,v′=0In summary, the completetv,v′wait can be determined by the following formula:(4)tv,v′wait=Tl′,s′,v′dep-Tl,s,varr-ts,s′walk,ifv′=1&xv,v′=1Tl′,s′,v′dep-Tl,s,varr-ts,s′walk,ifv′>1,xv,v′-1=0&xv,v′=1tp,ifv′=V-l′&xv,v′=00,else


## 3.4. Model Constraints

The rescheduling model is mainly subject to some operational requirements to ensure the safety of the operation and the feasibility of the rescheduled timetable.


### 3.4.1. Initial Delay

This constraint is to input the delay information (e.g., the delayed train, delay time, and position) to the model; see the following formula:(5)Tl∗,s∗,v∗dep≥T-l∗,s∗,v∗dep+tdorTl∗,s∗,v∗arr≥T-l∗,s∗,v∗arr+tdwhere v∗ indicates the delayed train running on line l∗. s∗ represents the station, where train v∗ is located when the disturbance occurs or the first station that is going to be visited by train v∗ after the disturbance occurs. td represents the delay time.


### 3.4.2. Actual Arrival and Departure Time

During the process of rescheduling, the actual arrival and departure times of trains at stations cannot be earlier than the scheduled times; see the following formulas:(6)Tl,s,varr≥T-l,s,varr(7)Tl,s,vdep≥T-l,s,vdep


### 3.4.3. Section Running Time

Under the limitations of the traction and brake performance of trains, the length of each section, safety requirements, and the actual running times of trains in sections must be longer than the minimum running times [24]; see the following formula:(8)Tl,s+1,varr-Tl,s,vdep≥tl,sr


### 3.4.4. Dwell Time

Adjusting the dwell time is an important measure for dispatchers to control subway trains. Similar to the section running time, the actual dwell times of trains at stations must be longer than the minimum dwell times [24]; see the following formula:(9)Tl,s,vdep-Tl,s,varr≥tl,sd


### 3.4.5. Headway

As we mentioned above, there is more than one train still running on each line during the end-of-service period. Thus, all trains running on each line should meet the requirements of minimum headway during the end-of-service period; see the following formulas:(10)Tl,s,v+1arr-Tl,s,varr≥hl(11)Tl,s,v+1dep-Tl,s,vdep≥hl


## 3.4.1. Initial Delay

This constraint is to input the delay information (e.g., the delayed train, delay time, and position) to the model; see the following formula:(5)Tl∗,s∗,v∗dep≥T-l∗,s∗,v∗dep+tdorTl∗,s∗,v∗arr≥T-l∗,s∗,v∗arr+tdwhere v∗ indicates the delayed train running on line l∗. s∗ represents the station, where train v∗ is located when the disturbance occurs or the first station that is going to be visited by train v∗ after the disturbance occurs. td represents the delay time.


## 3.4.2. Actual Arrival and Departure Time

During the process of rescheduling, the actual arrival and departure times of trains at stations cannot be earlier than the scheduled times; see the following formulas:(6)Tl,s,varr≥T-l,s,varr(7)Tl,s,vdep≥T-l,s,vdep


## 3.4.3. Section Running Time

Under the limitations of the traction and brake performance of trains, the length of each section, safety requirements, and the actual running times of trains in sections must be longer than the minimum running times [24]; see the following formula:(8)Tl,s+1,varr-Tl,s,vdep≥tl,sr


## 3.4.4. Dwell Time

Adjusting the dwell time is an important measure for dispatchers to control subway trains. Similar to the section running time, the actual dwell times of trains at stations must be longer than the minimum dwell times [24]; see the following formula:(9)Tl,s,vdep-Tl,s,varr≥tl,sd


## 3.4.5. Headway

As we mentioned above, there is more than one train still running on each line during the end-of-service period. Thus, all trains running on each line should meet the requirements of minimum headway during the end-of-service period; see the following formulas:(10)Tl,s,v+1arr-Tl,s,varr≥hl(11)Tl,s,v+1dep-Tl,s,vdep≥hl


## 3.5. Optimization Objectives

We present two objectives to be optimized here. First, we try to minimize the total transfer waiting time (TTWT) for all transfer passengers, which helps to improve the LOS of the system after disturbances; see formula (12). The first objective also benefits increasing the number of successful transfer passengers after disturbances because of the penalty time set for failed transfer passengers (FTP) who miss their last connecting trains. Second, we seek to minimize the deviation between the rescheduled timetable and the scheduled timetable, which is usually dispatchers’ first goal in practice; see formula (13). Passengers who do not need to transfer after disturbances also benefit from the second objective.(12)min∑l∈L∑l′∈L∑s∈Sl∑s′∈Sl′∑v∈Vl∑v′∈Vl′Ps,s′v×tv,v′wait(13)min∑l∈L∑s∈Sl∑v∈VlTl,s,varr-T-l,s,varr+Tl,s,vdep-T-l,s,vdepThe two objectives and constraints (1) and ((4)-(11)) above consist of the complete rescheduling model during the end-of-service period. The model is called a stakeholder-oriented model because interests of both operation and passengers (transfer and nontransfer) are considered in the two objectives. The trade-off between the two objectives may help dispatchers make decisions.


## 4. Model Solution

Owing to the huge complexity of the timetable rescheduling problem, especially when solving a real-world case of a large-scale and complex network, many heuristic algorithms have been proposed to speed solving this problem. Examples include greedy algorithm [9], particle swarm algorithm [25], and genetic algorithm [10]. However, in this study, we utilize the ε-constraint method [26] to convert the model into a single-objective model, and some linearization techniques are adopted to reformulate all nonlinear constraints into linear constraints. Then, the original model is converted to a single-objective ILP model, which can be solved by Cplex rapidly. By solving the problem for different values of ε, the approximate Pareto frontier can be shown to understand the trade-off between the two objectives.


### 4.1. Theε-Constraint Method

Theε-constraint method is good at solving multiobjective models to obtain a set of approximate Pareto optimal solutions. During the end-of-service period, we should put transfer passengers on the first place because they may miss their last connecting trains due to delayed feeder trains. As a result, the objective function (13) is chosen as the ε-constraint and reformulated by the following formula:(14)∑l∈L∑s∈Sl∑v∈VlTl,s,varr-T-l,s,varr+Tl,s,vdep-T-l,s,vdep≤F∗×1+εwhere F∗ indicates the optimal objective value when only objective function (13) is considered in the model. ε is a coefficient representing dispatchers’ tolerability to the deviation between the rescheduled and scheduled timetables, ε≥0.By theε-constraint method, the original model is converted into a single-objective model with the objective function (12) and constraints (1), ((4)-(11)), and (14).


### 4.2. Linearization

Among all constraints, constraints (1) and (4) are nonlinear constraints. In order to speed the process of model solution, constraints (1) and (4) need to be reformulated into linear constraints.M is introduced to represent a big enough positive integer; then formula (1) can be easily replaced by the following linear formulas:(15)Tl′,s′,v′dep-Tl,s,varr-ts,s′walk<M×xv,v′(16)Tl′,s′,v′dep-Tl,s,varr-ts,s′walk≥M×xv,v′-1On the premise of the objective to minimize the total transfer waiting time of all transfer passengers, formula (4) can be relaxed into formula (17). Then formula (17) can be replaced by linear formulas ((18)-(21)).(17)tv,v′wait≥Tl′,s′,v′dep-Tl,s,varr-ts,s′walk,ifv′=1&xv,v′=1Tl′,s′,v′dep-Tl,s,varr-ts,s′walk,ifv′>1,xv,v′-1=0&xv,v′=1tp,ifv′=V-l′&xv,v′=00,else(18)tv,v′wait≥Tl′,s′,v′dep-Tl,s,varr-ts,s′walk-M×1-xv,v′,ifv′=1(19)tv,v′wait≥Tl′,s′,v′dep-Tl,s,varr-ts,s′walk-M×xv,v′-1,ifv′>1(20)tv,v′wait≥tp×1-xv,v′,ifv′=V-l′(21)tv,v′wait≥0,∀v∈Vl,v′∈Vl′Finally, the single-objective model obtained in Section4.1 is converted into a single-objective ILP model with objective function (12) and linear constraints ((5)-(11)), ((14)-(16)), and ((18)-(21)), which can be solved by Cplex within limited seconds.


## 4.1. Theε-Constraint Method

Theε-constraint method is good at solving multiobjective models to obtain a set of approximate Pareto optimal solutions. During the end-of-service period, we should put transfer passengers on the first place because they may miss their last connecting trains due to delayed feeder trains. As a result, the objective function (13) is chosen as the ε-constraint and reformulated by the following formula:(14)∑l∈L∑s∈Sl∑v∈VlTl,s,varr-T-l,s,varr+Tl,s,vdep-T-l,s,vdep≤F∗×1+εwhere F∗ indicates the optimal objective value when only objective function (13) is considered in the model. ε is a coefficient representing dispatchers’ tolerability to the deviation between the rescheduled and scheduled timetables, ε≥0.By theε-constraint method, the original model is converted into a single-objective model with the objective function (12) and constraints (1), ((4)-(11)), and (14).


## 4.2. Linearization

Among all constraints, constraints (1) and (4) are nonlinear constraints. In order to speed the process of model solution, constraints (1) and (4) need to be reformulated into linear constraints.M is introduced to represent a big enough positive integer; then formula (1) can be easily replaced by the following linear formulas:(15)Tl′,s′,v′dep-Tl,s,varr-ts,s′walk<M×xv,v′(16)Tl′,s′,v′dep-Tl,s,varr-ts,s′walk≥M×xv,v′-1On the premise of the objective to minimize the total transfer waiting time of all transfer passengers, formula (4) can be relaxed into formula (17). Then formula (17) can be replaced by linear formulas ((18)-(21)).(17)tv,v′wait≥Tl′,s′,v′dep-Tl,s,varr-ts,s′walk,ifv′=1&xv,v′=1Tl′,s′,v′dep-Tl,s,varr-ts,s′walk,ifv′>1,xv,v′-1=0&xv,v′=1tp,ifv′=V-l′&xv,v′=00,else(18)tv,v′wait≥Tl′,s′,v′dep-Tl,s,varr-ts,s′walk-M×1-xv,v′,ifv′=1(19)tv,v′wait≥Tl′,s′,v′dep-Tl,s,varr-ts,s′walk-M×xv,v′-1,ifv′>1(20)tv,v′wait≥tp×1-xv,v′,ifv′=V-l′(21)tv,v′wait≥0,∀v∈Vl,v′∈Vl′Finally, the single-objective model obtained in Section4.1 is converted into a single-objective ILP model with objective function (12) and linear constraints ((5)-(11)), ((14)-(16)), and ((18)-(21)), which can be solved by Cplex within limited seconds.


## 5. Case Study

To validate the method proposed in this study, the Beijing subway network is used as a real-world case study. By the end of 2016, the Beijing subway network consisted of 18 double-track lines (i.e., 36 one-way lines), 53 transfer stations, and 225 ordinary stations with an average daily ridership of 9.998 million passengers. A sketch map of the Beijing subway network without Airport Express is shown in Figure3. Words with all letters in uppercase are acronyms of stations’ names.Figure 3
Sketch map of the Beijing subway network without Airport Express.Owing to the difference in passenger flow characteristics, different lines have different operational time frames. Among all last trains of all lines in Beijing subway network, the earliest one is the last train of Fangshan Line from SZ to GGZ, starting at 22:00. According to the definition in this study, the end-of-service period of the Beijing subway case is from 22:00 to the time when all trains finish their jobs, a period of time about 2.5 hours. In addition, the starting time is (22:00) reset to 0 and then all times are changed according to the time lag and the minimum time unit is second.Table1 shows a sample of the real AFC data with key information of the Beijing subway system. The number of transfer passengers is the key to deciding whether a connecting train should wait for a delayed feeder train or depart on time. From the real data recorded in the AFC system, we can obtain the approximate number of transfer passengers during the end-of-service period by a “Passenger-to-Train” assignment method [27]. The AFC data, the data of average transfer walking time in all transfer stations, and the data of the scheduled timetable are all provided by the Beijing Rail Transit Control Center.Table 1
A sample of the AFC data with key information.
Smart card ID Station_In Time_In Station_Out Time_Out 20714652 Beijingxizhan 22:00:13 Xizhimen 22:49:24 79292837 Lishuiqiao 22:04:35 Beijingzhan 22:53:42 50124710 Dawanglu 22:25:29 Chaoyangmen 22:47:07 78241891 Jinsong 23:02:28 Wukesong 23:55:02 22069171 Zhichunlu 23:30:51 Longze 23:57:49 ⋮ ⋮ ⋮ ⋮ ⋮


### 5.1. Scenario-Based Experiments

In order to prove that the proposed method is effective, various delay scenarios are generated randomly in terms of delayed train, delay position, and delay time. Numerical experiments based on these delay scenarios are carried out. Detailed information about these delay scenarios is listed in Table2.Table 2
Delay scenarios in detail.
ID Line Scenario Delay time 1 Line 1 from SHD to PGY The1st train departs late at Guomao. 9 min 2 Line 2 outer loop The1st train arrives late at Yhgong. 10 min 3 Line 4 from TGY to AB The2nd train departs late at Xizhimen. 8 min 4 Line 5 from TB to SJZ The2nd train departs late at Dongdan. 6 min 5 Line 6 from LC to HW The1st train arrives late at Bsqnan. 8 min 6 Line 7 from BX to JHC The2nd train arrives late at Ciqikou. 7 min 7 Line 8 from NG to ZXZ The2nd train departs late at Huoying. 9 min 8 Line 9 from GT to GGZ The3rd train arrives late at Bsqnan. 10 min 9 Line 10 outer loop The3rd train departs late at Shaoyaoju. 5 min 10 Line 15 from QX to BB The1st train arrives late at Wangjingxi. 7 minWe test these delay scenarios withε=0.25, hl=2 minutes, and tp=1 hour (i.e., 3600 seconds). All corresponding problems are solved within 2 seconds by Cplex 12.6.2 on a laptop computer with Intel Core i7-7700HQ CPU @ 2.8 GHz, 8 GB RAM. For benchmarking, we also test these delay scenarios with ε=0, which is similar to actual behaviors of dispatchers to minimize the deviation. Table 3 reports the solution results in detail.Table 3
Solution results of different scenarios.
Scenario TTWT/s Decrement Number of FTP Decrement ε = 0 ε = 0.25 ε = 0 ε = 0.25 1 11418266 8879746 22.23% 1304 734 43.71% 2 11623197 9064789 22.01% 1372 796 41.98% 3 11312422 8956396 20.83% 1307 745 43.00% 4 11720791 9337384 20.33% 1408 868 38.35% 5 11632670 9345290 19.66% 1402 849 39.44% 6 11400663 9220033 19.13% 1317 811 38.42% 7 11387058 9532154 16.29% 1340 888 33.73% 8 11474331 8422855 26.59% 1331 604 54.62% 9 11374509 9196693 19.15% 1325 810 38.87% 10 11398591 9237736 18.96% 1346 816 39.38%The TTWT includes the transfer waiting time of all successful transfer passengers and the penalty time of failed transfer passengers. For most scenarios, there is a considerable decrease of about 20% in the TTWT as well as a big decline in the number of FTP, about 40% compared to those of the rescheduled timetable withε=0, which is used to mimic dispatchers’ behaviors. These numerical results show that the LOS of subway systems after disturbances can be improved obviously by our method.


### 5.2. Delay Time Analysis

During the daily operation, different disturbances may lead to different delay times. In this experiment, we focus on Scenario 1 and set delay time changing from 5 to 10 minutes to test the effect of the method on different delay times. Similarly, all corresponding problems are solved within 2 seconds by Cplex 12.6.2 on the same computer. Table4 shows the solution results in detail.Table 4
Solution results of Scenario 1 with different delay times.
TTWT/s Delay time/s 300 360 420 480 540 600 ε = 0 11417881 11388673 11389273 11379193 11418266 11421626 ε = 0.25 9373458 9227160 9132110 8998431 8879746 8743882 Decrement 17.91% 18.98% 19.82% 20.92% 22.23% 23.44%With the delay time increasing from 5 to 10 minutes, our method can reduce the TTWT by 17.91% to 23.44% compared with that of the rescheduled timetable withε=0. In other words, the gap in TTWT between the rescheduled timetables by dispatchers and by our method is becoming bigger with the increasing delay time. As a result, with the improving requirements for LOS from passengers, our method is much better than dispatchers when tackling a disturbance which leads to a long delay time.


### 5.3. Trade-Off between Objectives

Our proposed biobjective model for timetable rescheduling during the end-of-service period aims to minimize the TTWT for all transfer passengers, meanwhile minimizing the deviation to the scheduled timetable. However, in the actual process of decision-making, it is difficult for dispatchers to obtain the optimal solution for multiple criteria. As a result, we are interested in the trade-off between objectives and adopt theε-constraint method to obtain a set of approximate Pareto optimal solutions, allowing dispatchers to choose one solution simply.Scenario 1 is still an example to obtain approximate Pareto optimal solutions by changing the value ofε from 0 to 0.5. The numerical results are shown in the left part of Figure 4. With ε rising from 0 to 0.5, the TTWT decreases rapidly; however, the deviation increases steadily. The right part of Figure 4 shows us the approximate Pareto frontier, which can demonstrate the trade-off between the two objectives. There is an obvious trend between the two objectives: a decrease in the TTWT corresponding to an increase in the deviation. Dispatchers should weigh up interests of all stakeholders and make decisions with the best solution in their minds according to the actual situation.Figure 4
Numerical results with changingε and the approximate Pareto frontier.In addition, for each approximate Pareto optimal solution, we calculate the TTWT, the number of FTP, and the total travel time (TT) of all trains involved in the end-of-service period by∑l∈L∑v∈Vl(Tl,S-l,varr-Tl,1,vdep), as shown in Table 5. According to the numerical results we can conclude that a high tolerability to the deviation only causes a rather small extension in the total TT of all involved trains. For example, among all rescheduled timetables, the biggest increment in total TT is only 132 seconds (ε=0.45), but there is a 27.82% decrement in the TTWT and a 58.13% decrement in the number of FTP compared to those of the rescheduled timetable with ε=0.Table 5
A comparison between total TT, TTWT, and the number of FTP.
RescheduledTimetable Total TT/s Increment TTWT/s Decrement FTP Decrement ε = 0.00 661345 ---- 11418266 ---- 1304 ---- ε = 0.05 661345 0 9800056 14.17% 932 28.53% ε = 0.10 661345 0 9452463 17.22% 857 34.28% ε = 0.15 661381 36 9223486 19.22% 810 37.88% ε = 0.20 661382 37 9034198 20.88% 751 42.41% ε = 0.25 661351 6 8879746 22.23% 734 43.71% ε = 0.30 661477 132 8726061 23.58% 686 47.39% ε = 0.35 661447 102 8589964 24.77% 669 48.70% ε = 0.40 661351 6 8396420 26.47% 594 54.45% ε = 0.45 661477 132 8241846 27.82% 546 58.13% ε = 0.50 661447 102 8102096 29.04% 529 59.43%During the end-of-service period, a passenger who does not need to transfer can catch his or her train definitely even if the train is late, but a transfer passenger may miss the last connecting train because of the late feeder train. As a result, based on all our numerical results in Section5.3, Figure 4, and Table 5 in particular, we strongly suggest that dispatchers should take more interests from transfer passengers into consideration when rescheduling timetable after disturbances during the end-of-service period.


## 5.1. Scenario-Based Experiments

In order to prove that the proposed method is effective, various delay scenarios are generated randomly in terms of delayed train, delay position, and delay time. Numerical experiments based on these delay scenarios are carried out. Detailed information about these delay scenarios is listed in Table2.Table 2
Delay scenarios in detail.
ID Line Scenario Delay time 1 Line 1 from SHD to PGY The1st train departs late at Guomao. 9 min 2 Line 2 outer loop The1st train arrives late at Yhgong. 10 min 3 Line 4 from TGY to AB The2nd train departs late at Xizhimen. 8 min 4 Line 5 from TB to SJZ The2nd train departs late at Dongdan. 6 min 5 Line 6 from LC to HW The1st train arrives late at Bsqnan. 8 min 6 Line 7 from BX to JHC The2nd train arrives late at Ciqikou. 7 min 7 Line 8 from NG to ZXZ The2nd train departs late at Huoying. 9 min 8 Line 9 from GT to GGZ The3rd train arrives late at Bsqnan. 10 min 9 Line 10 outer loop The3rd train departs late at Shaoyaoju. 5 min 10 Line 15 from QX to BB The1st train arrives late at Wangjingxi. 7 minWe test these delay scenarios withε=0.25, hl=2 minutes, and tp=1 hour (i.e., 3600 seconds). All corresponding problems are solved within 2 seconds by Cplex 12.6.2 on a laptop computer with Intel Core i7-7700HQ CPU @ 2.8 GHz, 8 GB RAM. For benchmarking, we also test these delay scenarios with ε=0, which is similar to actual behaviors of dispatchers to minimize the deviation. Table 3 reports the solution results in detail.Table 3
Solution results of different scenarios.
Scenario TTWT/s Decrement Number of FTP Decrement ε = 0 ε = 0.25 ε = 0 ε = 0.25 1 11418266 8879746 22.23% 1304 734 43.71% 2 11623197 9064789 22.01% 1372 796 41.98% 3 11312422 8956396 20.83% 1307 745 43.00% 4 11720791 9337384 20.33% 1408 868 38.35% 5 11632670 9345290 19.66% 1402 849 39.44% 6 11400663 9220033 19.13% 1317 811 38.42% 7 11387058 9532154 16.29% 1340 888 33.73% 8 11474331 8422855 26.59% 1331 604 54.62% 9 11374509 9196693 19.15% 1325 810 38.87% 10 11398591 9237736 18.96% 1346 816 39.38%The TTWT includes the transfer waiting time of all successful transfer passengers and the penalty time of failed transfer passengers. For most scenarios, there is a considerable decrease of about 20% in the TTWT as well as a big decline in the number of FTP, about 40% compared to those of the rescheduled timetable withε=0, which is used to mimic dispatchers’ behaviors. These numerical results show that the LOS of subway systems after disturbances can be improved obviously by our method.


## 5.2. Delay Time Analysis

During the daily operation, different disturbances may lead to different delay times. In this experiment, we focus on Scenario 1 and set delay time changing from 5 to 10 minutes to test the effect of the method on different delay times. Similarly, all corresponding problems are solved within 2 seconds by Cplex 12.6.2 on the same computer. Table4 shows the solution results in detail.Table 4
Solution results of Scenario 1 with different delay times.
TTWT/s Delay time/s 300 360 420 480 540 600 ε = 0 11417881 11388673 11389273 11379193 11418266 11421626 ε = 0.25 9373458 9227160 9132110 8998431 8879746 8743882 Decrement 17.91% 18.98% 19.82% 20.92% 22.23% 23.44%With the delay time increasing from 5 to 10 minutes, our method can reduce the TTWT by 17.91% to 23.44% compared with that of the rescheduled timetable withε=0. In other words, the gap in TTWT between the rescheduled timetables by dispatchers and by our method is becoming bigger with the increasing delay time. As a result, with the improving requirements for LOS from passengers, our method is much better than dispatchers when tackling a disturbance which leads to a long delay time.


## 5.3. Trade-Off between Objectives

Our proposed biobjective model for timetable rescheduling during the end-of-service period aims to minimize the TTWT for all transfer passengers, meanwhile minimizing the deviation to the scheduled timetable. However, in the actual process of decision-making, it is difficult for dispatchers to obtain the optimal solution for multiple criteria. As a result, we are interested in the trade-off between objectives and adopt theε-constraint method to obtain a set of approximate Pareto optimal solutions, allowing dispatchers to choose one solution simply.Scenario 1 is still an example to obtain approximate Pareto optimal solutions by changing the value ofε from 0 to 0.5. The numerical results are shown in the left part of Figure 4. With ε rising from 0 to 0.5, the TTWT decreases rapidly; however, the deviation increases steadily. The right part of Figure 4 shows us the approximate Pareto frontier, which can demonstrate the trade-off between the two objectives. There is an obvious trend between the two objectives: a decrease in the TTWT corresponding to an increase in the deviation. Dispatchers should weigh up interests of all stakeholders and make decisions with the best solution in their minds according to the actual situation.Figure 4
Numerical results with changingε and the approximate Pareto frontier.In addition, for each approximate Pareto optimal solution, we calculate the TTWT, the number of FTP, and the total travel time (TT) of all trains involved in the end-of-service period by∑l∈L∑v∈Vl(Tl,S-l,varr-Tl,1,vdep), as shown in Table 5. According to the numerical results we can conclude that a high tolerability to the deviation only causes a rather small extension in the total TT of all involved trains. For example, among all rescheduled timetables, the biggest increment in total TT is only 132 seconds (ε=0.45), but there is a 27.82% decrement in the TTWT and a 58.13% decrement in the number of FTP compared to those of the rescheduled timetable with ε=0.Table 5
A comparison between total TT, TTWT, and the number of FTP.
RescheduledTimetable Total TT/s Increment TTWT/s Decrement FTP Decrement ε = 0.00 661345 ---- 11418266 ---- 1304 ---- ε = 0.05 661345 0 9800056 14.17% 932 28.53% ε = 0.10 661345 0 9452463 17.22% 857 34.28% ε = 0.15 661381 36 9223486 19.22% 810 37.88% ε = 0.20 661382 37 9034198 20.88% 751 42.41% ε = 0.25 661351 6 8879746 22.23% 734 43.71% ε = 0.30 661477 132 8726061 23.58% 686 47.39% ε = 0.35 661447 102 8589964 24.77% 669 48.70% ε = 0.40 661351 6 8396420 26.47% 594 54.45% ε = 0.45 661477 132 8241846 27.82% 546 58.13% ε = 0.50 661447 102 8102096 29.04% 529 59.43%During the end-of-service period, a passenger who does not need to transfer can catch his or her train definitely even if the train is late, but a transfer passenger may miss the last connecting train because of the late feeder train. As a result, based on all our numerical results in Section5.3, Figure 4, and Table 5 in particular, we strongly suggest that dispatchers should take more interests from transfer passengers into consideration when rescheduling timetable after disturbances during the end-of-service period.


## 6. Conclusions

The timetable rescheduling problem can be optimized by many objectives because of its inherently multicriterion nature. It is difficult to tell which solution is the optimal solution. But in terms of some specific criteria, we can figure out that a solution is better or worse than others. As a result, one of the major contributions of this study is that a biobjective optimization method is proposed from the stakeholder-oriented perspective to tackle the timetable rescheduling problem during the end-of-service period of a subway network, which allows us to figure out the trade-off between the LOS (in terms of the TTWT and the number of FTP) and the operation (in terms of the deviation to the scheduled timetable). We utilize theε-constraint method to obtain approximate Pareto optimal solutions within limited seconds for different delay scenarios based on a real-world case, the Beijing subway network, which can help dispatchers to make decisions during the process of rescheduling.In addition, given the actual characteristics of the end-of-service period as well as the fact that a high tolerability to the deviation will not lead to a big extension in the total travel time, we think that dispatchers should put transfer passengers’ interests in the first place when rescheduling during the end-of-service period, which will benefit the overall LOS after disturbances.For future extension, the timetable rescheduling problem during the end-of-service period can take passengers rerouting into consideration, especially when the delay time is long. However, train rerouting seems an unreasonable option because in most subway systems, trains belonging to a line cannot run on other lines. Anyway, contributions should be devoted to improving the LOS of subway systems after disturbances.



---

*Source: 5914276-2018-06-27.xml*