Sage Journals: Discover world-class research

Abstract

Last train timetable plays an important role in actual operation of metro systems, especially in big cities. Appreciable transfer passengers rely on last train connections to reach their destinations, which requires a coordinated last train timetable. This study is devoted to dealing with the last train timetabling problem in metro networks, and proposes an integer linear programing model to coordinate last train connections at transfer stations to improve the transfer accessibility in terms of served transfer passengers and effective last train connections. Several measures at the planning level are used to guarantee feasibility of the optimized last train timetable when applied in practice. Then, the schedule-based transfer network and pre-process method are presented to shrink the scale of binary variables, which can expedite the solution process when solving problems in large-scale networks. Finally, some experiments based on the Qingdao metro network are carried out to verify the effectiveness of the timetabling method, and results show that dwell time and service ending time have direct influence on network accessibility. Comparison analyses show that the proposed model is able to generate a coordinated enough last train timetable with higher transfer accessibility and better practicality, which can provide support for operators to improve the last train service in a metro network.

Keywords

Metro network last train timetabling transfer accessibility integer linear programing schedule-based transfer network

Introduction

With the sustained construction and development, many metro systems in big cities have entered the period of networking operation. In a metro network, a number of lines are connected by transfer stations, which greatly improves the network accessibility. Meanwhile, many passengers have to transfer between lines to reach their destinations, and transfer passengers become an important element that is able to influence the daily operation. As a result, transfer passenger demand must be taken into account in train timetabling problems from the network level, and train connections determined in the timetable will greatly affect travel experience of transfer passengers via the network.

During the daily operation, there is a specific train service among hundreds of train services on a metro line, namely last train, which signals the ending of operation on the line. Correspondingly, among all train connections, there is a specific connection that is the last chance for a transfer passenger to achieve his/ her transfer, namely last train connection. The last train timetable will define all last train connections in a network, which determines the transfer accessibility during the end-of-service period. However, there is still an awkward situation often happening in practice that many transfer passengers may miss their last connecting trains, which reflects the existing last train timetable cannot fit the actual demand of transfer passengers.

In practice, there are appreciable transfer passengers traveling during the end-of-service period, especially in big cities.¹ Considering the inconvenience if a transfer passenger misses the last connecting train, for example, more time or more expenses to get to the destination, it is a consensus that a last train timetable should be coordinated to satisfy transfer passenger demand as much as possible, as well as improving the transfer service level of the network. Meanwhile, the operation costs should be taken into account as well when scheduling a last train timetable, because prolonging the service time is not an economical and sustainable method.

Therefore, this work contributes to the last train timetabling problem with transfer accessibility. First, an integer linear programing model is proposed to coordinate last train connections in the network, and to generate an optimized last train timetable considering transfer passenger demand. On the one hand, the model expects the optimized last train timetable is able to serve more transfer passengers and to provide effective last train connections as many as possible. On the other hand, the model also seeks to restrict the operation costs so that the ending time of last train service as the most important factor to reflect operation costs is formulated to be a constraint in the model.

Second, the last train timetabling is derived from the planning stage at network level. However, most existing studies preferred to change section running times to extend coordinating space, leading to modification in train speed profile, which will increase the complexity of actual operation. To state clearly the difference between this study and existing literatures, this study tends to keep train speed profile as usual to improve the feasibility when applied in practice. Third, in order to expedite the solution process, a schedule-based transfer network and pre-process method are presented to improve accuracy and to lower computational complexity. Finally, some numerical experiments based on the Qingdao metro network with given transfer passenger demand are carried out to validate the effectiveness of the proposed method. The results show that the pre-process method is able to increase computational efficiency and the optimized last train timetable can improve transfer accessibility significantly.

The rest of this work is organized as follows. “Literature review” section presents a brief review of related works about train timetable coordination and last train timetabling. The integer linear programing model for last train timetabling is proposed in “Last train timetabling model” section. “Schedule-based transfer network and pre-process method” section presents the schedule-based transfer network and pre-process method. “Case study and discussion” section reports the obtained computational results about the Qingdao metro network, and “Conclusions” section draws some conclusions in brief.

Literature review

In this section, a brief review of related literature is presented from two aspects: train timetable coordination and last train timetabling.

Train timetable coordination

The train timetabling problem has always been a hot topic over the years because the train timetable plays an important role in operation and management of rail transit systems.^2,3 At first, most studies contributed to dealing with the problem of line level.^4–8 However, when the scale shifting from line level to network level, the train timetabling problem evolves into train timetable coordination problem.

Most related studies are devoted to optimize the timetable principally by improving the transfer waiting time or maximizing the transfer coordination events. Wong et al. presented a mixed integer programing model for planning coordinated timetables with minimizing the transfer waiting time of all passengers.⁹ Wu et al.¹⁰ and Liu et al.¹¹ also proposed timetable coordination optimization models to optimize transfer waiting time. However, Wu et al. aimed at improving the worst transfer with a min-max objective function based on equity.¹⁰ Liu et al. sought to optimize train departure times from terminals with fixed headway.¹¹

Guo et al.¹² focused on the train timetable coordination in the transitional period during which train headway changes and passenger demand varies significantly. They proposed a mixed integer non-linear programing model to maximize the transfer coordination events. Cao et al.¹³ studied the coordination by determining the departure time under even headway to maximize the number of smooth transfers. However, the optimization is based on the priority of transfer stations and lines.

Shang et al.,¹⁴ Wang et al.¹⁵ and Yin et al.¹⁶ studied the problem by proposing a mixed integer programing model under time-dependent passenger demand. Shang et al. presented the objective with minimizing passenger total travel time.¹⁴ Wang et al. was devoted to minimizing total waiting time of all passengers and the number of passengers who fail to transfer.¹⁵ However, Yin et al. focused on minimizing the crowdedness of stations during peak hours.¹⁶

Overall, the studies reviewed above contributed to the train timetable coordination in the regular period of the daily operation, which is pretty different from last train timetabling problem. Due to the peculiarity of last trains and huge inconvenience if missing the last connecting train, last train timetabling in a network should be more considerate and transfer-passenger-oriented when coordinating last train connections.

Last train timetabling

Recently, there has been a series of studies focusing on the last train timetabling problem in metro networks. Kang et al. modeled the problem as a mean-variance formulation in terms of transfer redundant time and transfer binary variables to improve the efficiency of transfer passengers, and designed a genetic simulated annealing algorithm.¹⁷ Kang et al. proposed an indicator of passenger transfer connection headways to reflect last train connections and transfer waiting time, which is maximized by a genetic algorithm to reduce the number of missed connections.¹⁸ Further extension are made in solution method.^19,20

Li et al.²¹ and Wang et al.²² focused on optimizing the latest time that passengers can reach their destinations which may guide passengers clearer. Yang et al. presented a model under transfer demand uncertainty in mean-variance formulation.²³ Chen et al. considered the heterogeneity of transfer walking time as the log-normal distribution.²⁴ Zhang et al. paid more attention to passengers’ effective travel routes and all transportation activities were effectively described.²⁵ Zhang et al. proposed an optimization model for minimizing the total passenger transfer failures with an ABC algorithm.²⁶

Guo et al. proposed a trade-off approach that passengers with maximizing the transfer synchronization events, and operators with minimizing the worst big diﬀerence between last trains to cancel redundant trains.¹ However, canceling services may be not reasonable in practice. The operation costs can be controlled in terms of operation ending time^27,28 and energy consumption.²⁹

Furthermore, as a twin problem to the last train timetabling problem, Kang et al.,³⁰ Xu et al.,³¹ Xu et al.³² studied the last train timetable rescheduling problem form the view of coordination to serve more transfer passengers after disturbances.

In summary, these related works studied the last train timetabling problem with different mathematical formulations in objectives and constraints. Whereas, scheduling measures are roughly analogous, such as adjusting departure times from initial stations, section running times and dwell times within a min-max range of time, which seems like a rescheduling measure to take full advantage of buffer times.

However, the last train timetabling, after all, is at the planning stage. The difference from existing studies is presented here. First, there is no need to modify section running times so that train speed profile can keep unchanged to avoid increasing the complexity in actual operation. Second, the service time can’t be extended without limit so that the ending time of last train service should be restricted to control operation costs. This work intends to propose a last train timetabling model enabling these improvements. Third, a schedule-based transfer network and pre-process method are novelly proposed to speed up the model solution, which will be further illustrated in “Schedule-based transfer network and pre-process method” section.

Last train timetabling model

In order to generate a better last train timetable with given demand of transfer passengers in a metro network, an integer linear programing model is presented to coordinate the operation of last trains among different lines.

Model notations

For modeling convenience, some necessary symbols and parameters are defined as follows.

$L$ : the set of all lines in a metro network, $L = {l | l = 1, 2, . . ., \bar{L}}$ , where $\bar{L}$ is the total number of lines in the network. To be precise, a double-track metro line is regarded as two one-way lines.³³

$S_{l}$ : the set of all stations on line $l$ , $S_{l} = {s_{l} | s_{l} = 1, 2, . . ., {\bar{S}}_{l}}$ , where ${\bar{S}}_{l}$ is the total number of stations on line $l$ .

${\bar{T}}_{l, s}^{a r r}$ : the arrival time of last train at station $s$ on line $l$ in the existing last train timetable.

${\bar{T}}_{l, s}^{d e p}$ : the departure time of last train from station $s$ on line $l$ in the existing last train timetable.

${\bar{t}}_{l, s}^{r}$ : the section running time for last train from station $s$ to station $s + 1$ on line $l$ in the existing last train timetable.

${\bar{t}}_{l, s}^{d}$ : the dwell time for last train stopping at station $s$ on line $l$ in the existing last train timetable.

$C$ : the set of all transfer directions in a metro network, $C = {c (l s \to l' s')}$ , where $c (l s \to l' s')$ denotes the transfer direction from station $s$ on line $l$ to station $s'$ on line $l'$ . In the real world, station $s$ and station $s'$ are the same transfer station with different serial numbers on different lines.

$t_{c}^{w a l k}$ : the time for transfer passengers in $c (l s \to l' s')$ walking from the platform at station $s$ on line $l$ to the platform at station $s'$ on line $l'$ . Obviously, the time is deeply affected by walking speed of different persons. However, at the planning stage, the time is set constant and a bit longer than the average time obtained by a field survey, which can serve most passengers.²⁷

$P_{c}$ : the demand of transfer passengers in $c (l s \to l' s')$ , which can be derived approximately from the historical automated fare collection data.

The decision variables used in the model are presented as follows.

$T_{l, s}^{a r r}$ : the arrival time of last train at station $s$ on line $l$ in the optimized last train timetable.

$T_{l, s}^{d e p}$ : the departure time of last train from station $s$ on line $l$ in the optimized last train timetable.

Last train connections

In a transfer station, there are several transfer directions that depends on the number of linked lines and station type, that is, initial, intermediate, or terminal station, on each line. Figure 1 is an illustration of eight transfer directions in a common transfer station as an intermediate station on two double-track lines.

Figure 1.

Illustration of transfer directions in a common transfer station.

For each transfer direction $c (l s \to l' s')$ , whether passengers can achieve the transfer or not, it is determined by the temporal relation between the time when transfer passengers reach the platform of the connecting line and the departure time of the last train on the connecting line, leading to effective or ineffective last train connections.

For example, the time gap $T_{l', s'}^{d e p} - T_{l, s}^{a r r}$ is 4 min in a transfer direction $c (l s \to l' s')$ . If the transfer walking time $t_{c}^{w a l k}$ (e.g. 2 min) is within the gap, then transfer passengers will have a waiting time of 2 min, and the connection is an effective last train connection, as shown in Figure 2(a). However, if the transfer walking time $t_{c}^{w a l k}$ is longer than the gap (e.g. 5 min), then the connection is an ineffective last train connection, as shown in Figure 2(b).

Figure 2.

Illustration of effective or ineffective last train connections: (a) effective last train connection and (b) ineffective last train connection.

Thus, a binary variable $x_{c}$ is introduced to present the connection relationship between two last trains of the transfer direction $c (l s \to l' s')$ . If transfer passengers on last train of line $l$ can reach the platform of station $s'$ on line $l'$ no later than the departure time $T_{l', s'}^{d e p}$ , then $x_{c} = 1$ which denotes an effective last train connection. If not, then $x_{c} = 0$ which denotes an ineffective last train connection.

As a result, the binary variable $x_{c}$ is determined by

x_{c} = {\begin{matrix} 1, if T_{l', s'}^{d e p} - T_{l, s}^{a r r} - t_{c}^{w a l k} \geq 0, \\ 0, else . \end{matrix}

(1)

However, the binary expression is a non-linear mathematical expression. For the convenience of model solution, equation (1) can be replaced equally by two linear formulas, see

T_{l', s'}^{d e p} - T_{l, s}^{a r r} - t_{c}^{w a l k} \geq M \times (x_{c} - 1),

(2)

T_{l', s'}^{d e p} - T_{l, s}^{a r r} - t_{c}^{w a l k} < M \times x_{c},

(3)

where $M$ is a positive integer with big enough value.

Model constraints

In order to improve the feasibility of the optimized last train timetable when applied in practice, some measures at a planning level will be adopted to modify the existing one.

Departure time from initial station

For each last train, the departure time from its initial station is allowed to be advanced only by a short time in case some passengers can’t catch the last train as well as violating the headway away the penultimate train, see

T_{l, 1}^{d e p} \geq {\bar{T}}_{l, 1}^{d e p} - t_{a d v},

(4)

where $t_{a d v}$ denotes the maximum time that the departure can be advanced.

Meanwhile, the departure time from initial station can be postponed within a given time period, see

T_{l, 1}^{d e p} \leq {\bar{T}}_{l, 1}^{d e p} + Δ T_{l, 1}^{d e p},

(5)

where $Δ T_{l, 1}^{d e p}$ denotes the maximum time that the departure of last train from its initial station on line $l$ can be postponed.

Section running time

From the planning level, it is a common measure to keep the train speed profile same as usual in metro systems. Thus, the time for last train of line $l$ running from station $s$ to station $s + 1$ is equal to the section running time in the existing timetable, see

T_{l, s + 1}^{a r r} - T_{l, s}^{d e p} = {\bar{t}}_{l, s}^{r} .

(6)

Dwell time

Last train with longer dwell time may serve more passengers. Thus, the dwell time is extended within a reasonable range of time compared with the existing timetable, see

T_{l, s}^{d e p} - T_{l, s}^{a r r} \geq {\bar{t}}_{l, s}^{d},

(7)

T_{l, s}^{d e p} - T_{l, s}^{a r r} \leq t_{l, s}^{d \max},

(8)

where $t_{l, s}^{d \max}$ denotes the maximum dwell time for last train at station $s$ on line $l$ .

Arrival time at terminal station

Considering the operation costs and system maintenance requirement, the ending time of last train service cannot be postponed without restriction. In other words, the arrival time at terminal station is allowed to be postponed within a finite time period compared to the existing timetable, see

T_{l, {\bar{S}}_{l}}^{a r r} \leq {\bar{T}}_{l, {\bar{S}}_{l}}^{a r r} + Δ T_{l, {\bar{S}}_{l}}^{a r r},

(9)

where $Δ T_{l, {\bar{S}}_{l}}^{a r r}$ denotes the maximum time that the arrival of last train at its terminal station on line $l$ can be postponed.

Optimization objective

At the planning stage, considering appreciable transfer passengers and great inconvenience of missing the last connecting train, a good last train timetable should achieve more effective last train connections to improve the transfer accessibility, see

\max \sum_{c \in C} x_{c} .

(10)

However, incorporating the transfer passenger demand, the number of served transfer passengers will be more persuasive to illustrate the transfer accessibility. As a result, the objective is presented to maximize the number of served transfer passengers, see

\max \sum_{c \in C} (P_{c} \times x_{c}) .

(11)

In brief, the last train timetabling model is formulated as an integer linear programing model with the objective (11), and constraints (2–9). Correspondingly, formula (10) can be reformulated to calculate the number of effective last train connections as a performance index used in case study.

Schedule-based transfer network and pre-process method

As mentioned in “Last train connections” section, there are several transfer directions in a transfer station. However, connections in physical network can’t guarantee that passengers can transfer successfully during the end-of-service period, which is deeply affected by the last train timetable. In order to better depict transfer directions, a schedule-based transfer network is proposed in this work to combine the physical network and the last train timetable. Similarly, a typical transfer station of two double-track lines is as an example to illustrate the original schedule-based transfer network, see Figure 3.

Figure 3.

Illustration of the original schedule-based transfer network.

In the schedule-based transfer network, a station in real world is regarded as two stations for each direction of a double-track line, respectively. Solid lines with arrows represent last train running activities, and dotted lines with arrows represent latent transfer activities.

In order to improve accuracy and computational complexity,^34,35 a pre-process method is proposed based on the existing last train timetable to figure out transfer activities that may be achieved after the last-train timetable optimization, and to shrink the scale of non-deterministic binary variables during the solution process. A new time index $t_{c u t}$ is introduced to represent the transfer time gap, which can be determined by the actual operation. Then, each dotted line in the original schedule-based transfer network can be further revised by

x_{c} = 0, if T_{l', s'}^{d e p} - T_{l, s}^{a r r} - t_{c}^{w a l k} \leq - t_{c u t} .

(12)

Assuming that the existing last train timetable of Line A and Line B is listed in Table 1, and setting $t_{c}^{w a l k}$ by 120 s and $t_{c u t}$ by 600 s. Then, applying the pre-process method to the original schedule-based transfer network. First, calculating $x_{c}$ of each dotted line in Figure 3 by formula (12). Second, cutting all dotted lines with $x_{c} = 0$ . Then, the pre-processed schedule-based transfer network is obtained, see Figure 4 as an example.

Table 1.

A sample of the existing last train timetable of line A and line B.

Station	The existing last train timetable
Station	Arrival Time	Departure Time
S_AW	23:00:00	23:00:30
S_AE	22:40:00	22:40:30
S_BS	22:30:00	22:30:30
S_BN	22:50:00	22:50:30

Figure 4.

Illustration of the pre-processed schedule-based transfer network.

Comparing Figures 3 and 4, four dotted lines are deleted by applying the pre-process method, which means the method is able to scale down the non-deterministic binary variables obviously. Adding formula (12) to the last train timetabling model in “Last train timetabling model” section, then, the model can be solved by some commercial solvers, for example, CPLEX, efficiently.

Case study and discussion

In order to validate the effectiveness of the proposed model, some numerical experiments are carried out based on the Qingdao metro network. By the end of July 2022, the Qingdao metro network is composed of six double-track lines and reaches a total length of 284.3 km. Six lines have 138 stations in total, seven of which are transfer stations from all, as illustrated in Figure 5. Words with all letters in upper case are acronyms of key stations’ names.

Figure 5.

The diagram of Qingdao metro network.

There are total 46 transfer directions in the network. The daily operation of the system starts from 5:45 am, and lasts until 23:39 pm. The existing last train timetable can be obtained from the official website of Qingdao Metro. Next, the proposed model is applied to optimize the last train timetable, and some numerical results are reported to evaluate the performance by tests with adjusting several key parameters.

Last train timetable optimization

From the view of the planning stage, some necessary parameters are given with reasonable values according to operation practice, see Table 2. Then, the problem with transfer demand is carried out by the pre-process method and is solved by CPLEX 12.6.2 on a laptop computer with quad-core i7-7700HQ CPU @ 2.8 GHz and 16 GB RAM. The optimized timetable is obtained within 10 s, which shows the efficiency of the proposed method.

Table 2.

Parameters in optimization.

Parameter	$t_{a d v}$	$Δ T_{l, 1}^{d e p}$	$t_{l, s}^{d \max}$	$Δ T_{l, {\bar{S}}_{l}}^{a r r}$	$t_{c u t}$
Value	120 s	300 s	180 s	600 s	600 s

The optimized last train timetable is compared with the existing one in terms of transfer accessibility. Two indicators are presented to evaluate the performance, the number of effective last train connections and the number of served transfer passengers, as shown in Table 3.

Table 3.

Optimization results.

Indicator	Effective last train connections	Served transfer passengers
Existing timetable	18	1950
Optimized timetable	21	2217
Improvement	+3 (+16.7%)	+267 (+13.7%)

The results show measurable improvement of transfer accessibility in the optimized timetable. According to the transfer demand, the model recalculates the arrival and departure times for all last trains at each station, and restructure the connection relationships at transfer stations, leading to the number of effective last train connections increasing from 18 to 21, and the number of served transfer passengers increasing by 13.7%.

To figure out the changes in operation costs corresponding to the improvement, two time indicators are proposed to mainly reflect the changes in operation costs. $Δ t_{d e p}$ is the total deviation of departure time between the optimized and existing last train timetables for all last trains from initial and intermediate stations, see equation (13). $Δ t_{a r r}$ is the total deviation of arrival time between the optimized and existing last train timetables for all last trains at terminal stations, see equation (14).

Δ t_{d e p} = \sum_{l \in L} \sum_{s = 1}^{{\bar{S}}_{l} - 1} (T_{l, s}^{d e p} - {\bar{T}}_{l, s}^{d e p})

(13)

Δ t_{a r r} = \sum_{l \in L} (T_{l, {\bar{S}}_{l}}^{a r r} - {\bar{T}}_{l, {\bar{S}}_{l}}^{a r r})

(14)

Calculations show that, to enable the improvement in Table 3, $Δ t_{d e p}$ is only 1450 seconds and $Δ t_{a r r}$ is only 400 s, which means the improvement just requires minor extension in operation time for the whole network. In other words, the increase of operation costs is slight and acceptable. Therefore, the optimized method is practical and is able to generate a good last train timetable, which can offer better last train services than the existing one for transfer passengers during the end-of-service period.

Impact of dwell time

Dwell time has an important impact on transfer accessibility. However, the dwell time for a last train at a station is not allowed to be extended infinitely. In the optimized timetable, the total time $Δ t_{l}$ that can be assigned to the extension of dwell time on line $l$ is calculated by $(T_{l, {\bar{S}}_{l}}^{a r r} - T_{l, 1}^{d e p}) - ({\bar{T}}_{l, {\bar{S}}_{l}}^{a r r} - {\bar{T}}_{l, 1_{l}}^{d e p})$ . If slacking the constraint of maximum dwell time, i.e. $t_{l, s}^{d \max}$ , $Δ t_{l}$ will be freely assigned to dwell times at transfer stations to find the optimal solution. Performance is tested with increasing $t_{l, s}^{d \max}$ from 30 to 300 s, divided by 30 s respectively, and without the limit of $t_{l, s}^{d \max}$ . Figure 6 shows the upward trend both in effective last train connections and served transfer passengers.

Figure 6.

The impact of dwell time on transfer accessibility.

As shown in Figure 6, $t_{l, s}^{d \max} = 30$ seconds means that there is no change in dwell times as well as section running times, which indicates just modifying the departure time from initial station is also able to improve the transfer accessibility.

Generally, transfer accessibility is improved with the increasing of $t_{l, s}^{d \max}$ , because long dwell time will improve the chances of last train coordination. However, since $t_{l, s}^{d \max} \geq 210$ seconds, the improvement becomes limited in this case. As a result, whether setting a longer dwell time should be further discussed according to situations in practice. After all, long dwell time may provoke the dissatisfaction of non-transfer passengers.

Impact of arrival time at terminal station

Arrival time at terminal station plays an important role in both transfer accessibility and operation costs. In order to control operation costs, the arrival at terminal station is not allowed to be postponed without limit for economical purposes. Thus, it is necessary to figure out an reasonable $Δ T_{l, {\bar{S}}_{l}}^{a r r}$ . Some experiments are conducted with varying $Δ T_{l, {\bar{S}}_{l}}^{a r r}$ from 2 to 16 min, divided by 2 min respectively. Other parameters are same as values in Table 2. Solution results are displayed in Figure 7.

Figure 7.

The impact of arrival time at terminal station on transfer accessibility.

As shown in Figure 7, transfer accessibility is basically improved with the increasing of $Δ T_{l, {\bar{S}}_{l}}^{a r r}$ . However, when $Δ T_{l, {\bar{S}}_{l}}^{a r r}$ exceeds a specific value (10 min in this case), there will be no further improvement, which reflects the restricted effect of postponing the ending time of service. Similar results are also found with other combinations of $Δ T_{l, {\bar{S}}_{l}}^{a r r}$ and $t_{l, s}^{d \max}$ .

As a result, the postponement of arrival at terminal station should be also determined by the actual situations in practice, and appropriate postponed time will benefit both transfer accessibility and controlling operation costs. In general, operators can choose plans of switching points, for example, points with circles in Figure 7, as priority.

Conclusions

In order to generate a more coordinated last train timetable to provide a better service for transfer passengers during the end-of-service period, this work proposes a practical method from the view of the planning stage for last train timetabling in the metro network. An integer linear programing model is presented to improve transfer accessibility in terms of served transfer passengers and effective last train connections. Different from existing studies, the model doesn’t change section running time to keep train speed profile as usual for practical purposes. To improve the model solution efficiency, the schedule-based transfer network and a pre-process method are novelly presented to scale down the non-deterministic binary variables.

The last train timetabling method is validated by a case study derived from the Qingdao metro network, and results show that extending dwell times and postponing arrival times at terminal stations within reasonable time range will improve transfer accessibility effectively with minor extension in operation time. In conclusion, the method is able to generate a coordinated last train timetable with good transfer accessibility and acceptable increase in operation costs, which can benefit the actual last train operation, and offer better service for transfer passengers during the end-of-service period.

Footnotes

Declaration of conflicting interests

The author declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is supported by the Scientific Research Foundation of Shandong University of Science and Technology for Recruited Talents (0104060511715).

ORCID iD

Wenkai Xu

References

Guo

Sun

, et al. Scheduling synchronization in urban rail transit networks: trade-offs between transfer passenger and last train operation. Transp Res A-Pol 2020; 138: 463–490.

Cacchiani

Toth

Nominal and robust train timetabling problems. Eur J Oper Res 2012; 219(3): 727–737.

Parbo

Nielsen

Prato

CG.

Passenger perspectives in railway timetabling: a literature review. Transp Rev 2016; 36(4): 500–526.

Caprara

Fischetti

Toth

Modeling and solving the train timetabling problem. Oper Res 2002; 50(5): 851–861.

Niu

Zhou

Optimizing urban rail timetable under time-dependent demand and oversaturated conditions. Transp Res C-Emer 2013; 36: 212–230.

Barrena

Canca

Coelho

, et al. Exact formulations and algorithm for the train timetabling problem with dynamic demand. Comput Oper Res 2014; 44: 66–74.

Barrena

Canca

Coelho

, et al. Single-line rail rapid transit timetabling under dynamic passenger demand. Transp Res B-Meth 2014; 70: 134–150.

Shi

Yang

, et al. Service-oriented train timetabling with collaborative passenger flow control on an oversaturated metro line an integer linear optimization approach. Transp Res B-Meth 2018; 110: 26–59.

Wong

RCW

Yuen

TWY

Fung

, et al. Optimizing timetable synchronization for rail mass transit. Transp Sci 2008; 42(1): 57–69.

10.

Liu

Sun

, et al. Equity-based timetable synchronization optimization in urban subway network. Transp Res C-Emer 2015; 51: 1–18.

11.

Liu

Huang

, et al. Minimizing metro transfer waiting time with AFCS data using simulated annealing with parallel computing. J Adv Transport 2018; 2018: 1–17.

12.

Guo

Sun

, et al. Multiperiod-based timetable optimization for metro transit networks. Transp Res B-Meth 2017; 96: 46–67.

13.

Cao

Ceder

, et al. Optimal synchronization and coordination of actual passenger-rail timetables. J Intell Transp Syst 2019; 23(3): 231–249.

14.

Shang

Liu

, et al. Timetable synchronization and optimization considering time-dependent passenger demand in an urban subway network. Transp Res Rec 2018; 2672(8): 243–254.

15.

Wang

Cao

Integrated timetable synchronization optimization with capacity constraint under time-dependent demand for a rail transit network. Comput Ind Eng 2020; 142: 106374.

16.

Yin

D’Ariano

Wang

, et al. Timetable coordination in a rail transit network with time-dependent passenger demand. Eur J Oper Res 2021; 295(1): 183–202.

17.

Kang

Zhu

, et al. Departure time optimization of last trains in subway networks: Mean-variance model and GSA algorithm. J Comput Civ Eng 2015; 29(6): 04014081.

18.

Kang

Sun

, et al. A case study on the coordination of last trains for the Beijing subway network. Transp Res B-Meth 2015; 72: 112–127.

19.

Kang

Zhu

Strategic timetable scheduling for last trains in urban railway transit networks. Appl Math Model 2017; 45: 209–225.

20.

Kang

Meng

Two-phase decomposition method for the last train departure time choice in subway networks. Transp Res B-Meth 2017; 104: 568–582.

21.

Luo

, et al. Coordination of last train transfers using automated fare collection (AFC) system data. J Adv Transport 2016; 50(8): 2209–2225.

22.

Wang

Song

, et al. Collaborative optimization of last-train timetables for metro network to increase service time for passengers. Comput Oper Res 2023; 151: 106091.

23.

Yang

Gao

, et al. Last-train timetabling under transfer demand uncertainty mean-variance model and heuristic solution. J Adv Transport 2017; 2017: 1–13.

24.

Chen

Mao

Bai

, et al. Optimal coordination of last trains for maximum transfer accessibility with heterogeneous walking time. J Adv Transport 2019; 2019: 1–13.

25.

Zhang

, et al. Last Train rapid synchronizing approach for maximum OD accessibility with passengers’ effective travel route. J Transp Eng A-Syst 2023; 149(1): 04022119.

26.

Zhang

Yan

, et al. Last train timetabling optimization for minimizing passenger transfer failures in urban rail transit networks: A time period based approach. Phys 2022; 605: 128071.

27.

Chen

Mao

Bai

, et al. Timetable synchronization of last trains for urban rail networks with maximum accessibility. Transp Res C-Emer 2019; 99: 110–129.

28.

Yao

Zhu

Shi

, et al. Last train timetable optimization considering detour routing strategy in an urban rail transit network. Meas Control 2019; 52(9–10): 1461–1479.

29.

Wang

Meng

Guo

, et al. An integrated energy-efficient and transfer-accessible model for the last train timetabling problem. Phys 2022; 588: 126575.

30.

Kang

Sun

, et al. A practical model for last train rescheduling with train delay in urban railway transit networks. Omega 2015; 50: 29–42.

31.

Zhao

Ning

Last train delay management in urban rail transit network Bi-objective MIP model and genetic algorithm. KSCE J Civil Eng 2018; 22(4): 1436–1445.

32.

Zhao

Ning

A practical method for timetable rescheduling in subway networks during the end-of-service period. J Adv Transport 2018; 2018: 1–9.

33.

Xie

Ning

A trade-off method for timetable rescheduling considering transfer connections in subway networks. Mod Phys Lett B 2020; 34(24): 2050253.

34.

Yağ

Altan

. Artificial intelligence-based robust hybrid algorithm design and implementation for real-time detection of plant diseases in agricultural environments. Biology 2022; 11(12): 1732.

35.

Altan

. Performance of Metaheuristic Optimization Algorithms based on Swarm Intelligence in Attitude and Altitude Control of Unmanned Aerial Vehicle for Path Following. In: 2020 4th international symposium on multidisciplinary studies and innovative technologies (ISMSIT), Istanbul, Turkey, 22–24 October 2020, pp.1–6. New York, NY: IEEE.

Last train timetabling with transfer accessibility in metro networks: integer linear programing model and schedule-based transfer network

Abstract

Keywords

Introduction

Literature review

Train timetable coordination

Last train timetabling

Last train timetabling model

Model notations

Last train connections

Model constraints

Departure time from initial station

Section running time

Dwell time

Arrival time at terminal station

Optimization objective

Schedule-based transfer network and pre-process method

Case study and discussion

Last train timetable optimization

Impact of dwell time

Impact of arrival time at terminal station

Conclusions

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References