Last train timetable optimization for metro network to maximize the passenger accessibility over the end-of-service period

Abstract

Purpose

This study aims to improve the passenger accessibility of passenger demands in the end-of-operation period.

Design/methodology/approach

A mixed integer nonlinear programming model for last train timetable optimization of the metro was proposed considering the constraints such as the maximum headway, the minimum headway and the latest end-of-operation time. The objective of the model is to maximize the number of reachable passengers in the end-of-operation period. A solution method based on a preset train service is proposed, which significantly reduces the variables of deciding train services in the original model and reformulates it into a mixed integer linear programming model.

Findings

The results of the case study of Wuhan Metro show that the solution method can obtain high-quality solutions in a shorter time; and the shorter the time interval of passenger flow data, the more obvious the advantage of solution speed; after optimization, the number of passengers reaching the destination among the passengers who need to take the last train during the end-of-operation period can be increased by 10%.

Originality/value

Existing research results only consider the passengers who take the last train. Compared with previous research, considering the overall passenger demand during the end-of-operation period can make more passengers arrive at their destination. Appropriately delaying the end-of-operation time can increase the proportion of passengers who can reach the destination in the metro network, but due to the decrease in passenger demand, postponing the end-of-operation time has a bottleneck in increasing the proportion of passengers who can reach the destination.

Citation

Wen, F., Bai, Y., Zhang, X., Chen, Y. and Li, N. (2023), "Last train timetable optimization for metro network to maximize the passenger accessibility over the end-of-service period", Railway Sciences, Vol. 2 No. 2, pp. 273-288. https://doi.org/10.1108/RS-03-2023-0012

1. Introduction

Optimization of metro timetable refers to determining the arrival and departure times of trains on different lines in the network at transfer stations, so as to improve the transfer efficiency of passengers. In off-peak and peak hours, the optimization of the timetable focuses on reducing the waiting time for passenger transfer to improve the service level of the network (Yu, Han, Dong, Li, & Yao, 2015). Whereas at the end-of-operation period, a train transfer failure between lines will cause a decrease in passenger accessibility of the network service, thus passengers would not be able to reach their destination by taking the metro (Guo, Jia, & Qin, 2015). Therefore, it is necessary to study the optimization of the last train timetable from the perspective of service passenger accessibility, so that boosting passenger accessibility as far as possible of the metro.

Existing studies on the optimization for the timetable of the last train of the metro can be mainly divided into two categories: the first category focuses on improving the number of successful transfer connections at the transfer station and the second category optimizes the passenger accessibility of passengers in the network. For the first category, references (Xu, Zhang, & Jiang, 2008; Kang, Wu, Sun, Zhu, & Gao, 2015; Kang & Meng, 2017; Chen, Bai, Feng, & Li, 2017, Chen, Mao, Bai, Ho, & Li, 2019a, Chen, Mao, Bai, Ho, & Li, 2019b; Guo et al., 2020) optimized the timetable of the last train, to improve the number of passengers transferring successfully among the last train and reduce the waiting time for the transfer; Ning, Zhao, Xu, Qiao, and Yao (2016) formulated an optimization model of train timetable in the end-of-operation period to minimize the waiting time for transfer and the number of failed transfer passengers, considering all trains in the period. However, in the metro network, optimizing train transfers merely does not guarantee the largest number of passengers reaching their destinations.

The second category of study optimizes the last train timetable from the perspective of OD (origin-destination) reachability. Chen et al. (2019a, b) further considered the transfer of passengers between the last train and the non-last train on different metro lines and optimized the timetable of the last train with the objective of maximizing the number of passengers who can reach their destination among the passengers taking the last train at the origin station (passengers departing by the last train). Considering the demand of passengers departing by the last train, Zhou, Wang, Yang, and Yan (2019) proposed an MILP (mixed integer linear program) model for the last train timetable optimization, which can be solved by Cplex. In the end-of-operation period, not only the passengers departing by the last train may not be able to reach their destination but passengers taking the non-last train at the origin station of the travel may also be unreachable to their destination. Yao, Liu, Liu, and Yang (2018) optimized OD reachability of the network considering passengers taking the last train in the entire travel. Yang, Di, Dessouky, Gao, and Shi (2020) proposed an MILP model based on a space-time network with the consideration of the passenger demand departing by the non-last train, and designed a Lagrange relaxation algorithm to solve the model. This study considers all passenger demands at the end-of-operation period, which may lead to a large scale of problems and difficulty in achieving efficient solutions. Wen et al. (2019) proposed a mathematical model aiming at the maximum total number of reachable OD pairs at each time during the end-of-operation period, but the model did not consider the difference in passenger demand with different departure times. In the existing studies, only part of the passenger demand (such as the passengers departing by the last train) in the end-of-operation period is taken into consideration to optimize the last train timetable, while all OD passenger demands in the period are not considered in detail (passengers departing by the non-last train are overlooked), so it is difficult to ensure the maximum reachability of the network service.

Tackling the issues raised above, this paper, oriented toward all passenger demands in the end-of-operation period, proposes an optimization model of the last train timetable to maximize the number of reachable passengers of the metro network in the end-of-operation period; in view of the characteristics of various departure times and great difficulty in model solution during the period, a solution method based on preset train services is designed to solve the optimized last train timetables.

2. Illustrating existing problems

2.1 Definition of parameters

The metro network consists of lines and stations, and the up and down directions are considered as two lines. Definition of parameters: nl is the number of lines; L is the set of lines, L={li,i=1,2,…,nl}; ns is the number of stations on the metro network; S is the set of stations, S={se,e=1,2,…,ns}; nsi is the number of stations on the line li; Sli is the set of stations of the line li, Sli={se,e=ei,1,ei,2,…,ei,nsi}, where ei,1,ei,2,…,ei,nsi corresponds to the number of each station of the line in the set S of stations of the metro network.

t₀ is defined as the start time of the end-of-operation period, and the end-of-operation period is divided into several time points with an interval of δ. The end-of-operation period is denoted by a set T={t0+δ,t0+2δ,…,t0+nδδ}, where nδ is the number of intervals in the period. Since the passenger accessibility of passengers with the same departing time is the same between the same OD, it can be regarded as one group of passenger flow; and the OD pair, composed of the origin station sp∈S and the destination station sq∈S, is recorded as g_pq; bγ is the passenger group with the departure time t between OD, bγ=(sp,sq,t); the demand of all passenger groups in the end-of-operation period can be expressed as a set B={bγ,γ=1,2,…,nb}, where nb is the number of passenger groups; uγ is the number of passengers in the passenger group bγ.

For the passenger group bγ=(sp,sq,t), the effective path set between the OD pair g_pq can be expressed as Rγ={rγ,k,k=1,2,…,nrγ}, where nrγ is the number of effective paths of the passenger group bγ. In the effective path set Rγ, each effective path rγ,k is composed of several ride sections v, i.e. rγ,k={vγ,k,m,m=1,2,…,nvγ,k}, the ride section vγ,k,m=(li,se,se′) represents the passenger group taking the train at the station se of the line li and alighting from the train se′ at the station; where nvγ,k is the number of ride sections in the path rγ,k; t̑γ,k,mA and t˘γ,k,mA are, respectively, the time when the passenger group bγ reaches the origin station and the destination station of the ride section vγ,k,m. The schematic diagram of the effective path between an OD pair g_pq is shown in Figure 1. As can be seen from Figure 1, the effective path set Rγ of the passenger group bγ=(sp,sq,t) includes two paths, namely rγ,1 and rγ,2, which are, respectively, rγ,1={(l1,sp,s2),(l4,s2,sq)} and rγ,2={(l1,sp,s1),(l2,s1,s3),(l3,s3,sq)}.

In the end-of-operation period, the train services on the line li can be expressed as a set Hi={hi,j,j=1,2,…,nhi}, where nhi is the number of train services on the line li (the train services are sorted in reverse order to departure time); ti,j,eD and ti,j,eA are, respectively, the departure and arrival times of the train hi,j on the line li at the station se along the line; se is a transfer station, and te,i,i′w is the time of transfer by foot of the passenger group from the line li to the line li′.

2.2 Analysis of passenger accessibility

Passenger accessibility varies along with departure time and is directly related to the connectivity of effective paths between ODs. At a certain moment, if there is at least one connected path between ODs, OD is considered as reachable (Xu, Zhang, Guo, & Du, 2014; Chen, Mao, Bai, Li, & Tang, 2020). Taking the passenger group bγ=(sp,sq,t) in Figure 1 as an example, if the paths rγ,1={(l1,sp,s2),(l4,s2,sq)} or rγ,2={(l1,sp,s1),(l2,s1,s3),(l3,s3,sq)} are connected, the OD pair is reachable for g_pq, and the passenger group bγ=(sp,sq,t) can reach its destination. Sufficient and necessary conditions for path connectivity entail that the passenger group can board the train in each ride section of the path. This depends on the passenger’s surplus time for riding at the origin station of the ride section, which is equal to the difference between the departure time of the train on the ride section and the time when the passenger group arrives at the platform.

Taking the path rγ,1={(l1,sp,s2),(l4,s2,sq)} as an example, the travel path for transfer at the station s2 is shown in Figure 2. For the ride section vγ,1,1=(l1,sp,s2), if the time t̑γ,1,1A when the passenger group bγ=(sp,sq,t) arrives at the platform of the station, sp is earlier than the departure time of the train h1,1 and the train h1,2 at the station sp of the line l1; then the surplus time of the passenger group bγ for the train h1,1 and the train h1,2 is greater than 0, and the passenger group will take the train h1,2 arriving earlier, and the time of reaching the station s2 is t1,2,2A; for the ride section vγ,1,2=(l4,s2,sq), the time t̑γ,1,2A when the passenger group bγ arrives at the platform of the origin station s2 of the ride section is equal to the sum of t1,2,2A and the time t2,1,4w of transfer by foot between the two lines, and then combined with the departure times of each train of the line l4, it can be estimated whether the passenger group can get on the train promptly in the ride section vγ,1,2=(l4,s2,sq) and the train it takes; thus, the riding behaviors of the passenger group in all the ride sections can be calculated in turn, thereby judging whether the paths are connected.

3. Optimization model of last train timetable

3.1 Model assumptions

1. It is assumed that the passenger heterogeneity is low and the fluctuation of the time of transfer by foot is small at the end-of-operation period, which indicates the passengers in the same transfer direction at the transfer station have the same time of transfer by foot.

2. The effective path between OD takes the K short physical path before loop-free.

3. Assuming that the train capacity is sufficient and there is no passenger stranded, passengers always choose to take the train arriving first.

3.2 Modeling

3.2.1 Decision variables

In this paper, to improve the OD reachability of the network during the end-of-operation period, the arrival and departure times (ti,1,eA,ti,1,eD ∀li∈L,se∈Sli) of the last train of each line at each station are taken as the decision variable in the model.

3.2.2 Constraints

1. Constraints on the adjustment range of section operation and dwell times of the last train

Let t_Δ1 and t_Δ2 be the maximum and minimum values of section operation time adjustment, t_Δ3 and t_Δ4 the maximum and minimum values of dwell time adjustment, and the time adjustment should meet the actual operation requirements, so the arrival and departure times of the last train at each station should be within the adjustment range, i.e.

(1)tΔ1≤ti,1,eA−ti,1,e′D≤tΔ2 ∀e=ei,β,e′=ei,β−1,li∈L

(2)tΔ3≤ti,1,eD−ti,1,eA≤tΔ4 ∀se∈Sli,li∈L

1. Constraint of maximum headway

To ensure the level of passenger service, the headway between the last train and the penultimate train at the first station should not be greater than the maximum headway Iimax, i.e.

(3)ti,1,eD−ti,2,eD≤Iimax ∀e=ei,1,li∈L

1. Constraint of minimum headway

To ensure train operation safety in the section, the headway between the last train and the penultimate train should not be less than the minimum headway Iidd, i.e.

(4)ti,1,eD−ti,2,eD≥Iidd ∀se∈Sli,li∈L

To ensure the safety of station operation, at the same station, the headway between the arrival time of the last train and the departure time of the penultimate train should not be less than the minimum headway Iida, i.e.

(5)ti,1,eA−ti,2,eD≥Iida ∀se∈Sli,li∈L

1. Constraint on the latest end-of-operation time

To avoid interference with night maintenance, the end-of-operation time of the terminal station ei,nsi of each line should not be later than the latest end-of-operation time timax, i.e.

(6)ti,1,eA≤timax ∀e=ei,nsi,li∈L

3.2.3 Objective function

Defined xγ as a 0-1 variable, indicating the OD reachability of the passenger group bγ. When the passenger group bγ can reach the destination, xγ=1; otherwise, xγ=0. The objective function of the model is the maximization of the total number of passengers who can reach their destinations in the passenger group set B={bγ,γ=1,2,…,nb} in the end-of-operation period, i.e.

(7)Q=max∑bγ∈Buγxγ

3.2.4 Evaluation of passenger accessibility

1. Evaluation of passenger accessibility

Defined yγ,k as a 0-1 variable, indicating whether the path rγ,k of the passenger group bγ is connected. When the path rγ,k is connected, rγ,k=1; otherwise, rγ,k=0. If there is a connected effective path between ODs, then OD can be reached, and the constraint condition for OD to be reached can be expressed as

(8)xγ≤∑rγ,k∈Rγyγ,k ∀bγ∈B

1. Evaluation of path connectivity

Defined zγ,k,m as a 0-1 variable, indicating whether the passenger group bγ can successfully board the train in the ride section vγ,k,m of the path rγ,k. When the passenger group successfully can board the train, it is taken as zγ,k,m=1; otherwise, zγ,k,m=0; M1 is a sufficiently large positive integer. If the passenger group can board the train in all ride sections of the path, then the path rγ,k is connected, and the constraint for path connectivity is as follows:

(9)M1(yγ,k−1)≤∑v∈rzγ,k,m−nvγ,k<M1yγ,k∀rγ,k∈Rγ,bγ∈B

1. Evaluate whether the passenger can take the train in the ride section

Defined αγ,k,m,j as a 0-1 variable, indicating whether the passenger group bγ takes the train hi,j in the ride section vγ,k,m (within the line li) of the path rγ,k. If the passenger group takes a train hi,j of the line li, then αγ,k,m,j=1 and zγ,k,m=1. If the passenger group cannot take any train, then ∑j∈Hliαγ,k,m,j=0 and zγ,k,m=0. When there is more than one train available, the passenger group can only select one of them. In order to maximize the passenger accessibility for passengers, the value αγ,k,m,j of the first train arriving should be 1, so the constraint conditions for whether the train can travel in the ride section are as follows:

(10)zγ,k,m≤∑j∈Hliαγ,k,m,j ∀vγ,k,m=(li,se,se′)∈rγ,k,rγ,k∈Rγ,bγ∈B

(11)∑j∈Hliαγ,k,m,j≤1 ∀vγ,k,m=(li,se,se′)∈rγ,k,rγ,k∈Rγ,bγ∈B

1. Evaluation of the train service in the ride section

The value of the variable αγ,k,m,j is related to the surplus time of the train service hi,j taken by the passenger group. For the ride section vγ,k,m=(li,se,se′), the surplus time of the passenger group bγ for the train service hi,j is equal to the difference between the departure time ti,j,eD of the train service hi,j at the station se and the time t̑γ,k,mA, when the passenger group bγ arrives at the origin station se of the ride section. If the surplus time is less than 0, then αγ,k,m,j=0; otherwise, αγ,k,m,j>0, indicating that the passenger group can choose to take the train service hi,j, and the constraint condition for the passenger group to take a certain train in the ride section is

(12)M1(αγ,k,m,j−1)≤ti,j,eD−t̑γ,k,mA ∀hi,j∈Hi,vγ,k,m=(li,se,se′)∈rγ,k,rγ,k∈Rγ,bγ∈B

1. Evaluation of the arrival time of the passenger group at the origin station of the ride section

In Equation (12), if vγ,k,m is the first ride section of the path (m = 1), the time t̑γ,k,1A when the passenger group bγ arrives at the platform at the origin station of the ride section is equal to the departure time t of the passenger group bγ=(spsqt); if vγ,k,m=(li,se,se″) is the subsequent ride section (m > 1), the time t̑γ,k,mA when the passenger group arrives at the platform at the origin station se of the ride section vγ,k,m is the sum of the arrival time t˘γ,k,m−1A of the passenger group at the destination station se of the previous ride section vγ,k,m−1=(li′,se′,se) and the time of transfer by foot te,i′,iw. Therefore, the evaluation formula for the arrival time of the passenger group at the origin station of the ride section is as follows:

(13)t̑γ,k,mA={tm=1t˘γ,k,m−1A+te,i′,iwm>1∀vγ,k,m−1=(li′,se′,se),vγ,k,m=(li,se,se″)∈rγ,k,rγ,k∈Rγ,bγ∈B

1. Evaluation of the arrival time of the passenger group at the destination station of the ride section

In Equation (13), the arrival time t˘γ,k,m−1A of the passenger group at the destination station se of the ride section vγ,k,m−1=(li′,se′,se) is determined by the train service (Chen et al., 2019a, b). If the train is taken by the passenger group in the ride section vγ,k,m−1=(li′,se′,se) is hi′,j, i.e. αγ,k,m−1,j=1, then t˘γ,k,m−1A=ti′,j,eA; if the passenger group cannot take any train on the line li′, i.e. ∑j∈Hli′αγ,k,m−1,j=0, the arrival time is set to a large positive integer M2 (M2≪M1). Therefore, the evaluation formula for the arrival time of the passenger group at the destination station of the ride section is as follows:

(14)t˘γ,k,m−1A=∑j∈Hli′αγ,k,m−1,jti,j,eA+(1−∑j∈Hli′αγ,k,m−1,j)M2 ∀vγ,k,m−1=(li,se′,se)∈rγ,k,rγ,k∈Rγ,bγ∈B

4. Solution method

The optimization model of the last train timetable is a mixed integer nonlinear programming model. Its number of decision variables and constraints are mainly affected by the number of passenger groups and the size of the train set Hli on each line. In order to evaluate the train service of the passenger group, for any valid path rγ,k of the passenger group bγ, the variable αγ,k,m,j with a quantity of |Hli| should be considered for each ride section vγ,k,m, which leads to a large number of 0-1 variables in the model, and the solving time with a commercial solver is too long.

To reduce the number of variables, a solution method based on a preset train service is proposed. The preset train service refers to the earliest train service that the passenger group can board in the travel path according to the departure time of the passenger group, the timetable information of the non-last train and the adjustment range of the timetable of the last train. If the passenger group does not need to take the last train in the travel path, the passenger group can still reach the destination after optimization, and this part of the passenger group is eliminated by the algorithm; if the optional train of the passenger group is the last train, the OD reachability of the passenger group can be determined by estimating whether the passenger group can get on the last train. Thus, the model is linearized to an MILP model and the timetable optimization model can be quickly solved by the commercial solver.

4.1 Preset method of train service in ride section

The preset train service of the ride section is related to the timetable of the line corresponding to the ride section and the time when the passenger group arrives at the origin station of the ride section. For the passenger group bγ=(sp,sq,t), the preset train service jγ,k,m of the passenger group in each ride section vγ,k,m of the path rγ,k is estimated in turn with the non-last train timetable, the last train timetable constraints, and the path as inputs.

1. Step 1

Given the ride section vγ,k,m=(li,se,se′) in the path rγ,k and the time t̑γ,k,mA when the passenger group arrives at the station se of line li, estimate the preset train service jγ,k,m of the ride section: if the arrival time t̑γ,k,mA of the passenger group is earlier than the departure time of the non-last train at the station se of line li, that is, there is a train hi,j={j | t̑γ,k,mA≤ti,j,eD,j≥2}, the passenger group takes the non-last train that arrives the earliest, and the preset train is jγ,k,m=max{j | t̑γ,k,mA≤ti,j,eD}; otherwise, the passenger group can only select the last train in the ride section, and the preset train is the last train jγ,k,m=1. For the first ride section vγ,k,1 of rγ,k, t̑γ,k,1A is equal to the departure time t of the passenger group; for the subsequent ride section, t̑γ,k,mA is equal to the sum of the arrival time of the passenger group at the destination station of the previous ride section and the time of transfer by foot.

1. Step 2

Based on the preset train service jγ,k,m of the ride section vγ,k,m=(li,se,se′), estimate the time t˘γ,k,mA when the passenger group arrives at the destination station se′ of the ride section: if the passenger group takes a non-last train (jγ,k,m≥2), then the time when the passenger group arrives at the station se′ is the arrival time of the train, i.e. t˘γ,k,mA=ti,j(v),se′A; if the passenger group takes the last train (jγ,k,m=1), since the arrival and departure times of the last train at each station are decision variables and non-fixed values, the feasible latest arrival time of the last train at the station is taken as the estimated arrival time of the passenger group.

1. Step 3

Determine whether vγ,k,m is the last ride section in rγ,k, i.e. whether there is m=nvγ,k. If yes, the preset train service jγ,k,m of each ride section in rγ,k will be output, and the evaluation of the preset train service of the current path is over; otherwise, the preset train service of the next ride section vγ,k,m+1 will be evaluated, and go to Step 1.

4.2 Reformulated model based on preset train service

With the preset train service of each ride section, it is assumed that the passenger group only selects the preset train in the travel path, and a reformulated model of the coordination optimization model of the last train timetable (hereinafter referred to as the original model) is proposed.

Since the reformulated model only considers whether the passenger group bγ can board the preset train of the ride section, the constraint formula Equation (10) can be reformulated as follows without considering the constraint formula Equation (11).

(15)zγ,k,m≤αγ,k,m,jγ,k,m ∀vγ,k,m∈rγ,k,rγ,k∈Rγ,bγ∈B′

For the constraint formula Equation (12), the constraint of the surplus time of the passenger group bγ for the preset train service jγ,k,m can be reformulated as follows:

(16)M1(αγ,k,m,jγ,k,m−1)≤ti,jγ,k,m,eD−t̑γ,k,mA ∀vγ,k,m=(li,se,se′)∈rγ,k,rγ,k∈Rγ,bγ∈B′

Similar to the original model, for the first ride section in the path rγ,k, t̑γ,k,1A is equal to the departure time t of the passenger group; for the subsequent ride section vγ,k,m=(li,se,se″), t̑γ,k,mA is equal to the sum of the arrival time t˘γ,k,m−1A of the passenger group at the station se in the previous ride section vγ,k,m−1=(li′,se′,se) and the time of transfer by foot te,i′,iw; and t˘γ,k,m−1A is the arrival time ti,jγ,k,m−1,eA of the preset train service j(vγ,k,m−1) of line li′ at the station se. The evaluation formula of the arrival time of the passenger group at the origin station and the destination station of the ride section can be expressed as a linear common constraint, see Equations (17) and (18), that is, the conditional formulae, Equations (13) and (14), of the original model constraint are reformulated as follows:

(17)t̑γ,k,mA={tm=1t˘γ,k,m−1A+te,i′,iwm>1∀vγ,k,m−1=(li′,se′,se),vγ,k,m=(li,se,se″)∈rγ,k,rγ,k∈Rγ,bγ∈B′

(18)t˘γ,k,m−1A=ti,jγ,k,m−1,eA ∀vγ,k,m−1=(li′,se′,se),rγ,k∈Rγ,bγ∈B′

The rest constraints remain unchanged, and the reformulated model is obtained as follows:

(19)Q=max∑bγ∈B′uγxγ

s.t.

Eqs. (1)–(6), Eqs. (8)–(9), Eqs. (15)–(18)

Compared with the original model, the decision variables and constraint scale of train service evaluation in the reformulated model are significantly reduced; and the reformulated model is a linear model, which can be quickly solved by Cplex software.

As the model only optimizes the timetable of the last train on each line, passenger groups who can arrive at the destination station by taking a non-last train during the trip will still reach the destination station after optimization. For the passenger groups that need to take the last train during their trip, their passenger accessibility is affected by the last train timetable. In order to improve the solution efficiency, the preset method is first used to estimate the preset train service of each path of all passenger groups in the ride section during the end-of-operation period. According to the preset train service, the passenger groups that must take the last train during the trip are eliminated from passenger demand B during the end-of-operation period, and their set is represented by B′, i.e. bγ∈B′, where there exists a ride section jγ,k,m=1 for rγ,k∈Rγ. The reformulated model only takes the passenger flow set B′ as the input, which can not only ensure that the demands of all passengers who need to take the last train during the end-of-operation period are considered but also reduce the scale of problem-solving.

5. Case study

Taking Wuhan Metro as the background, the up-direction and down-direction lines in the metro network are regarded as two lines. There are 48 key stations, including transfer stations, origin and terminal stations of the line, and stations with the largest passenger flow between two adjacent transfer stations. The simplified network diagram is shown in Figure 3. The green and blue arrows indicate the up direction and down direction of the line, respectively; dots indicate key stations in the network. Two key stations constitute the key OD (2,256 pairs in total). Three valid paths are considered between each OD. Parameter setting: the end-of-operation period is 21:30 to 24:00; the dwell time of each station in the initial timetable is 30–60 s. The running time in sections is within 1–4 minutes; the minimum headway and the minimum departure–arrival headway at stations are both 2 minutes. The maximum headway between the last train and the penultimate train at the origin station of the line is 10 minutes. The end-of-operation time of the line can be delayed by 10 minutes.

5.1 Comparison of solving efficiency between reformulated model and original model

The end-of-operation period is divided by intervals δ of 1, 5 and 10 minutes, respectively, and the set B′ of passenger groups that must take the last train during the trip is taken as the input. Cplex is used to test the solution effect of the original model and the reformulated model under the passenger demand at different intervals. The results are shown in Table 1, where “the preset number of people who can reach the destination” refers to the number of passengers who can reach the destination by the preset trains under the optimized timetable, that is, the objective function value of the reformulated model (the original model has no such result); “the accurate number of people who can reach the destination” includes the passengers who actually arrived at the destination without choosing the preset train (evaluated with Equations (7)–(14) in the original model with the optimized timetable as input); “upper limit” refers to the upper limit value of Cplex solution; “gap” refers to the percentage of the difference between the accurate number of people who can reach the destination and the upper limit.

Table 1 shows that in the reformulated model, the difference between the preset and the accurate number of people who can reach the destination is only 44. The reason is that the preset method assumes that passengers only choose the preset train in their travel path, but passengers may not choose the preset train. The small difference indicates that the preset method has high accuracy in estimating the train taken by passengers in the ride section and that the evaluation error of the model is small. With the decrease of interval, the problem scale and the computation challenge increase, the relative difference between the two models increases and the computation time becomes longer. The smaller the interval of passenger demand is, the more obvious the advantage of the fast-solving speed of the reformulated model is. Therefore, the reformulated model can get the approximate optimal solution in a relatively short time compared with the original model.

5.2 Optimization results

With the set B′ of passenger groups who need to take the last train during the trip and the time interval is 1 minute, the reformulated model is solved by Cplex. The proportion of reachable OD in the network varying with time before and after optimization is shown in Figure 4; the number of destination-reachable passengers of all passenger demand B during the end-of-operation period is shown in Figure 5 and the change of average travel time of passengers is shown in Table 2. For some OD, passengers cannot reach the destination station, thus the travel time penalty for the passengers who cannot reach their destination is set to be 100 minutes.

It can be seen from Figures 4 and 5 that compared with the original, the optimized reachable OD percentage and the number of destination-reachable passengers in the end-of-operation period are increased to a certain extent; the reachable OD percentage increases significantly during the period 22:31–22:56 and increases by 15.6% at 22:32.

It can be seen from Table 2 that within the passenger flow B′, for passengers who need to take the last train during the end-of-operation period, the percentage of destination-reachable passengers increased by 10% from 32.3% to 42.3%. The average travel time of destination-reachable passengers increased by 5.2 minutes, mainly because the departure time of the last train on some lines was delayed. It indicates that the optimization of the last train timetable can help some destination-unreachable passengers reach their destination, but the travel time of some passengers also increased slightly. Considering all passengers in B′, the average total travel time after optimization has decreased from the initial 79.2 minutes to 76.7 minutes, which means that the overall service level of passengers has been improved.

Although the optimized timetable slightly increases the travel time of some passengers who can reach their destination before optimization, it effectively improves the percentage of reachable OD and the number of destination-reachable passengers of the whole network during the end-of-operation period and improves the overall service level of the network.

5.3 Verification of the necessity of considering the overall passenger demand in the end-of-operation period

In existing studies, only the passenger groups departing by the last train are considered to optimize the last train timetable. In order to verify the necessity of considering the overall passenger demand during the end-of-operation period, a comparative case is set up, where set B″ of passenger groups departing by the last train is taken as the input passenger flow.

The time interval of passenger flow data is 1 minute. The optimization results are shown in Table 3. It can be seen that in the compared case and the case in this study, the percentages of reachable passengers in passenger flow B″ increased by 24.9% and 24.1%, respectively, and that of flow B′ increased by 28.0% and 31.0%, respectively. Compared with the compared case, the case in this study has a slight improvement in the number of destination-reachable passengers in passenger flow B″, but the increase of the number of destination-reachable passengers in the passenger flow B′ is 3.0% higher, so that more passengers can take the last train to their destination. Therefore, it is necessary to consider all the passenger demands in the end-of-operation period in the study on optimization of the last train time.

5.4 Sensitivity analysis of the latest end-of-operation time

The latest end-of-operation time of each line restricts the adjustment range of the arrival and departure times of the last train at each station, thus having a great impact on the service passenger accessibility in the network. In this paper, the latest end-of-operation time timax of each line is set to be 0, 5, 10 and 15 minutes later than the original end-of-operation time, and the time interval of passenger flow data is taken as 1 minute, so as to optimize the percentage of destination-reachable passengers in the passenger flow B′ and analyze the influence of the latest end-of-operation time timax on the effect of the optimization of passenger accessibility. The results are shown in Figure 6.

As can be seen from Figure 6, without the delay of the end-of-operation time of each line, the percentage of destination-reachable passengers increases by 6.5%; with the delay of the latest end-of-operation time, the percentage of destination-reachable passengers in the passenger flow B′ who need to take the last train gradually increases, and it increases by 3.4% with a time delay of 5 minutes; when the end-of-operation time can be delayed by 10 and 15 minutes, the percentage of destination-reachable passengers hardly increases. This shows that the percentage of destination-reachable passengers in the network can be increased by appropriately delaying the end-of-operation time of the line; due to the reduction of passenger demand, the delay of end-of-operation time has a bottleneck in improving the percentage of destination-reachable passengers. Therefore, the operating companies can determine a reasonable end-of-operation time through sensitivity analysis to maximize service passenger accessibility and avoid late end-of-operation time.

6. Conclusions

1. From the perspective of improving the passenger accessibility during the end-of-operation period, a last train timetable optimization model is proposed. Considering the model is difficult to be solved due to the large number of passenger groups and train services during the end-of-operation period, this study proposes a solution method based on preset trains, which reformulates the original model into a mixed integer linear programming model with fewer decision variables and can achieve a fast solution.

2. Compared with the original model, the reformulated model and the solution method can get a high-quality solution in a relatively short time with a small error. The smaller the interval of passenger flow data, the more significant the advantage of the fast solution. After optimization, the percentage of passengers who can reach their destination successfully by last train during the end-of-operation period increases by 10%, which verifies the effectiveness of this model. Compared with the previous studies that only consider the passengers who take the last train, the number of passengers who take the last train and can reach the destination in the end-of-operation period increased by 3.0%, which indicates that it is necessary to consider the overall passenger demand in the end-of-operation period for the study on the optimization of the last train schedule.

3. In this paper, the passenger accessibility of the network is optimized by adjusting the last train timetable. In future research, it can be considered to coordinate and optimize all train timetables in the end-of-operation period, expand the model solution space and achieve a better optimization effect.

Figures

Figure 1

Schematic diagram of effective paths between OD pair gpq

Figure 2

Schematic diagram of travel path

Figure 3

Schematic diagram of the network and key stations

Figure 4

Reachable OD percentage of network before and after optimization

Figure 5

Number of destination-reachable passengers in the network

Figure 6

Influence of delay in latest end-of-operation time on the percentage of destination-reachable passengers

Table 1

Solution results of the original model and reformulated model under passenger flow data with different intervals

Interval/min	Model	The preset number of people who can reach the destination/pax	The accurate number of people who can reach the destination/pax	Upper limit/pax	Gap/%	Computation time/min
10	Original	23,745	23,789	23,792	0.01	11
	Reformulated		23,789		0.01	3
5	Original	27,816	27,458	27,923	1.69	60
	Reformulated		27 860		0.23	11
1	Original	29,108	28,579	29,391	2.84	780
	Reformulated		29,152		0.82	65

Source(s): Authors’ own work

Table 2

Percentage of destination-reachable passengers and average travel time before and after optimization

Timetable	Percentage of destination-reachable passengers in passenger flow, B′/%	Average travel time of destination-reachable passengers/min	Average travel time of all passengers/min
Original	32.3	39.8	79.2
Optimized	42.3	45.0	76.7

Source(s): Authors’ own work

Table 3

Comparison of the number of destination-reachable passengers and increase after optimization

Timetable		Passenger flow departing by the last train B″		Passenger flow needing the last train during travel B′
		Number of destination-reachable passengers/pax	Increase in destination-reachable passengers/%	Number of destination-reachable passengers/pax	Increase in destination-reachable passengers/%
Original		9,959		22,249
Optimized	Comparative case	12,443	24.9	28,477	28.0
	Case of this study	12,360	24.1	29,152	31.0

Source(s): Authors’ own work