Sage Journals: Discover world-class research

Abstract

In most urban subway networks, passengers may make a transfer at night or in the early morning to arrive at their destinations. Given that passengers may confronted with transfer failure at night or long waiting in the morning, scheduling overnight trains is beneficial to both the last and first train services in the urban metro network, in particular, to minimize the number of failed transfer passengers in the last train service and the transfer waiting time for the first train service. Then, we formulate the overnight train scheduling problem as a mixed integer linear programming model based on a well-designed time-discretized space–time network. To handle large-scale applications, we decompose the proposed model into two space–time path-searching sub-problems and a semi-assignment problem through Lagrangian relaxation–based decomposition and solution framework. Finally, we adopt Beijing Subway Network as a practical case study. The results show that both the number of failed transfer passengers for last train service and the passenger transfer waiting time for first train service decrease significantly if the operators can schedule the overnight trains in Beijing Subway Network according to the optimization results of the proposed model.

Keywords

Overnight train space–time network the first and last train services urban subway network

Introduction

Motivation

The development of the urban subway system has been thriving over the last decade, and many urban subway networks have become the most important transportation mode in cities¹ due to its security, wide accessibility, high-energy performance, reliable service, convenience, and low-carbon consumption.^2,3 Most subway systems are usually not operating for 24 h. For example, in the Beijing Subway Network, trains are running from about 5:00 to 24:00 continuously. However, passengers may suffer inconvenience at night or in the early morning when the trains in the urban subway network nearly end or just start for operation. Figure 1(a) shows the situation of failed transfer for last train service, and Figure 1(b) shows the situation of long transfer waiting time for first train service. In response to this situation, the solution presented in this article is “overnight trains”: an overnight train is arranged by the operators to provide a transfer service for passengers who failed to transfer after the last train at night and passengers who waited for the first train in the morning for a long time, and stops at a specific non-service station during this period. Therefore, scheduling overnight train can be an efficient method for improving service levels for both last and first train services in an urban subway network.

Figure 1.

(a) Situation of failed transfers at night; (b) situation of long waiting time in the early morning.

Figure 2 shows an example in the Beijing Subway network for the failed transfer and the long-time transfer latency existing in the last and first train timetables. Both XiErQi and GongZhufen are transfer stations. The former connects the Line CP and Line 13, and the latter connects the Line 10 and Line 1. Figure 2(a) shows that the last train on Line ChangPing arrives at XiErQi station at 23:26; then there are no trains on Line ChangPing when passengers from Line 13 go to Line ChangPing at XiErQi station, which leads to a failed transfer. Figure 2(b) shows the train timetable of GongZhuFen station. The first feeder train on Line 1 arrives at GongZhuFen station at 5:18, and the first connection train on Line 10 arrives at GongZhufen at 6:27; passengers must wait more than 1 h to board the first train on Line 10.

Figure 2.

The example of long transfer waiting time and failed transfer in Beijing subway: (a) train timetable for XiErQi station at night; (b) train timetable for GongZhuFen station in the morning.

According to the existing timetable in Beijing subway network, there are more than 108 failed transfer directions for last train service and the total waiting time for the first train service is more than 2600 min.⁴ The reason can be explained that there are operation time and maintenance time window constraints for each line considering passenger demand, train and track maintenance requirement, and also working time for crew. Therefore, this study takes the actual passenger demand at night and in the early morning into consideration and aims to minimize the number of failed transfer passengers at night and the total transfer waiting time in the early morning by scheduling overnight trains in the subway network. Figure 3 shows the flow chart of this study. First, the physical urban subway network, the existing train timetables at night and in the early morning, and the corresponding passenger demand are the inputs of the model. Then, we propose a MILP model to optimize the overnight train schedule and simultaneously assign passengers into the subway network to evaluate the overnight train schedule in a space–time network. The proposed model can be solved by a Lagrangian relaxation (LR) decomposition and solution framework, which is tested on a large-scale case of Beijing Subway Network.

Figure 3.

The flow chart of solving the problem.

Literature review

Several scholars have provided excellent surveys of the inherent connections among different optimization problems in the field of rail transit routing and scheduling.^5,6 In an urban subway network, timetable synchronization problem has been widely studied from different perspective. Wong et al.⁷ proposed a mixed integer programming optimization model to minimize the passengers transfer waiting time in railway network for the timetable synchronization problem. Shafahi and Khani⁸ established a mixed integer programming model to minimize the waiting time considering the extra stopping time of vehicles at transfer stations. Niu et al.⁹ proposed a non-linear optimization model to minimize passenger waiting time at station and crowding disutility in the trains when passengers have a transfer between two interconnected high-speed rail lines. Tian and Niu¹⁰ proposed a bi-objective integer programming model integrated with irregular headways to optimize the train timetables for transfer synchronization, in order to minimize the total waiting time and maximize the number of connections. Shang et al.¹¹ formulated a demand-driven timetable synchronization and optimization model to minimize passenger total travel time, the model aimed to adjust the departure time, running time, stopping time, and headway of all trains on each line which can be computed by the genetic algorithm.

With the development of smart card automatic fare collection (AFC) systems, more detailed data of passenger demand and characteristic can be obtained, including passenger origin and destination stations and corresponding departure times and arrival times. A trend toward demand-driven transit rail timetable optimization has emerged.^12,13 For instance, Niu and Zhou¹⁴ constructed a binary integer programming model to optimize a passenger train timetable when the passengers cannot board the trains because of the maximum loading capacity of previous trains. Niu et al.¹⁵ formulated a mathematically rigorous and algorithmically tractable non-linear mixed integer programming model for both real-time scheduling and medium-term planning applications to minimize the total waiting time of passengers at stations. Canca et al.¹⁶ formulated a non-linear integer programming model, which fits the arrival and departure time of trains for a dynamic behavior of demand to solve the problem of timetable determination. Canca et al.¹⁷ focused on the design and optimization of train timetables to minimize the average passenger waiting time at the stations with two mathematical programming formulations which adapt the non-periodic train timetabling problem on a single line under a dynamic demand pattern. Yin et al.^18,19 proposed models for rescheduling and scheduling trains considering energy-efficiency and time-dependent passenger demand. Shi et al.²⁰ established an integrated integer linear programming model to optimize the train timetable and accurate passenger flow control strategies on an oversaturated metro line, aimed to minimize the total passengers waiting time. Shang et al.²¹ formulated a space–time–state network based on multi-commodity flow formulation to solve an equity-oriented skip-stopping schedule problem in an oversaturated urban rail transit network. Then the linear programming model can be effectively decomposed to a least-cost sub-problem with positive arc costs for each individual passenger and a least-cost sub-problem with negative arc costs under LR framework. Shang et al.²² proposed a model which aimed to minimize the total passenger travel time with the dynamic passenger demand. Shang et al.²³ formulated an approach to estimate the passengers flow state based on the space–time–state network by integrating Lagrangian and Eulerian observations.

Timetable optimization for the last and first train services are two important problems, and several optimization models are proposed to offer optimized timetables in previous studies. For the last train problem, Kang et al.²⁴ focused on the last train transfer problem in the urban subway network; they formulated a last-train network transfer model to maximize passengers transfer connection headway, which can decrease the number of passengers failed transfer. Kang et al.²⁵ established a rescheduling model for last trains, which focused on the train delays because of incidents that occurred in train operations; the model was to minimize the dwell time and the running time, and to maximize the average transfer redundant time and the network accessibility. Yin et al.²⁶ focused on the last-train timetabling problem and proposed a bi-level programming model to maximize the social service efficiency and minimize the revenue loss for the operating companies by a genetic algorithm. Kang et al.²⁷ connected the last and bus bridging service problem in the urban railway transit networks; they proposed a last and bus bridging coordination mixed integer linear programming (MILP) model to maximize the last train connections and minimize waiting time for rail-to-bus passengers. For the first train problem, Kang et al.⁴ optimized the first-train timetable with a mixed integer programming model to minimize the arrival time difference of trains and the number of missed trains. Guo et al.²⁸ proposed a model to coordinate first-train timetable in the urban railway network with a sub-network connection method. Kang and Zhu²⁹ used the mixed integer variables to calculate the waiting time for the “first available” train correctly, which can minimize the passengers transfer waiting time. Kang and Zhu³⁰ presented two practical optimization models to minimize the standard deviation of transfer redundant times and to balance the last train transfers in subway networks, which can be solved by a new heuristic algorithm.

Table 1 shows the comparisons of previous last-train, first-train studies, and the overnight train problem in this study.

Table 1.

The comparisons of the previous last/first-train studies, and the overnight train problem in this study.

Study	Problem	Objective function	Passenger demand	Solution algorithm
Kang et al.²⁴	Last train timetable	Maximize connection headway	Considered by key directions	Genetic algorithm
Kang et al.⁴	First train timetable	Minimize the arrival time difference	Transfer passenger demand	A local search algorithm
Guo et al.²⁸	First train timetable	Minimize the cost-importance measure of the whole network	–	CPLEX
Kang and Zhu²⁹	First train timetable	Minimize the passengers transfer waiting time	–	Simulated annealing algorithm
Kang and Zhu³⁰	Last train timetable	Minimize the standard deviation of transfer redundant times and balance the last train transfers	–	A new heuristic algorithm
Kang et al.²⁵	Last train rescheduling	Minimize the running time and the dwell time, maximize the average transfer redundant time and the network accessibility, minimize the difference between the original timetable and the rescheduled one	–	Genetic algorithm
Kang et al.²⁷	Last train timetableand bus bridging service	Maximize the last train connections and minimize waiting time for rail-to-bus passengers	Transfer passenger demand	A decomposition approach
Yin et al.²⁶	Last train timetable with social welfare	Maximize the social service efficiency and minimize the revenue loss for the operating companies	Probability density of transfer passenger	Genetic algorithm
This study	Overnight train schedule	Minimize the number of failed passengers for last train service and the transfer waiting time for first train service	Passenger origin–destination (OD) demand in the network	Lagrangian relaxation (LR)-based decomposition and solution framework

Contribution

Based on the literature review above, the last and first train problems are studied independently with different objectives. This study proposes a novel strategy, which schedules overnight trains as a bridge to coordinately minimize the number of transfer failed passengers for last train service and the transfer waiting time for first train service. The contribution of this study can be summed in the following.

We propose a solution to improve service levels for both last and first train services, which schedules overnight train on each line in the urban subway network that departs its depot after the last train to serve some failed transfer directions, and stays at a station during non-service hours, finally continues to finish the remaining trip before the first train.

We propose a space–time network to formulate the overnight train schedule and passenger assignment. In the proposed space–time network, candidate overnight train traveling and stopping arcs are built to represent the possible overnight train schedule, including the departure time from the depot at night, overnight stopping station, and another departure time from the stopping station in the early morning.

A MILP model is proposed to optimize the overnight train schedule and simultaneously assign passengers to evaluate the overnight train schedule. The proposed MILP model can be directly solved by CPLEX for simple case. To handle large-scale case, for example, Beijing Subway Network, we propose a Lagrangian-based decomposition and solution framework, within which the original model can be decomposed into two space–time path-searching sub-problems and a semi-assignment problem, which can be efficiently solved for large-scale cases.

The remainder of this article is organized as follows. The “Key concepts for model formulation” section presents some key concepts for model formulation, including the problem statement, construction of the space–time network for existing timetables, and possible overnight train schedule. The “Model formulation and solution approach” section formally proposes the MILP model for the overnight train scheduling problem and a LR decomposition and solution framework to decompose the MILP model into sub-problems. The proposed MILP model and solution algorithm are demonstrated through a simple case and a real-world case based on Beijing Subway Network in the “Numerical examples” section. The “Conclusions” section summaries the findings.

Key concepts for model formulation

Notations

The notations used in this article are listed in Table 2.

Table 2.

Indices, sets, parameters, and variables.

Notations	Definition
Indices
$i, j$	Index of stations in the physical network, $i, j \in N$
$(i, j)$	Index of links in the physical network, $(i, j) \in L$
$t, s, τ$	Index of time intervals, $t, s, τ \in T$
a	Index of passengers group at night, $a \in A$
$a'$	Index of passengers group in the early morning, $a' \in A'$
q	Index of trains, $q \in Q$
$q'$	Index of overnight trains, $q' \in Q'$
$(i, t), (j, s)$	Index of vertices in the space–time network, $(i, t), (j, s) \in V$
$(i, j, t, s)$	Index of space–time arcs, $(i, j, t, s) \in E$
Sets
N	Set of stations in the physical urban subway network
L	Set of links in the physical urban subway network
T	Set of time intervals in the study time horizon
A	Set of passengers at night
$A'$	Set of passengers in the early morning
Q	Set of trains
$Q'$	Set of overnight trains $Q' \subset Q$
V	Set of vertices in the space–time network
E	Set of arcs in the space–time network, $E = E_{e} \cup E_{p} \cup E_{t} \cup E_{s}$
$E_{e}$	Set of arcs in the space–time network, including waiting arcs, existing traveling arcs, transfer arcs, and dummy arcs
$E_{p}$	Set of penalty arcs for passengers who cannot arrive at their destinations in the space–time network
$E_{t}$	Set of candidate overnight train traveling arcs in the space–time network
$E_{s}$	Set of candidate overnight train stopping arcs in the space–time network
Parameters
$o (a / a')$	Origin station of passenger $a / a'$
$d (a / a')$	Destination station of passenger $a / a'$
$DT (a / a')$	Departure time of passenger $a / a'$
$o (q)$	Origin station of train q
$d (q)$	Destination of train q
$DT (q)$	Scheduled depart time at its origin station of train q
$AT (q)$	Scheduled arrival time at its destination station of train q
$c_{i, j, t, s}$	Travel time of space–time arc $(i, j, t, s)$
$α$	The weight of the transfer failed problem
$β$	The weight of the long waiting time problem
Variables
$x_{i, j, t, s}^{a}$	= 1 if passenger a selects space–time arc $(i, j, t, s)$ , = 0 otherwise
$x_{i, j, t, s}^{a'}$	= 1 if passenger $a'$ selects space–time arc $(i, j, t, s)$ , = 0 otherwise
$y_{i, j, t, s}^{q'}$	= 1 if overnight train $q'$ selects space–time arc $(i, j, t, s)$ , = 0 otherwise

Problem statement

We propose a novel strategy to improve service levels for both last and first train services, which schedules overnight train on each line that departs a depot after the last and stays at a station for non-service period and continues to finish the remaining trip before the first train. Therefore, the study problem in this article is stated formally in the following. Given (a) physical urban subway network, (b) current timetables at night before (including) the last and in the early morning after (including) the first train, and (c) according to the passengers demand at night and in the early morning, we aim to determine the overnight train schedule, including departure time from the depot at night, overnight stopping station, and another departure time from the stopping station in the early morning, to minimize the number of failed transfer passengers for last train service and the transfer waiting time for first train service in an urban subway network.

Space–time network construction based on the current first and last train services

A space–time network representation has been widely used in transportation route optimization, various scheduling applications, and general dynamic network flow modeling.^21,31 Considering a physical urban rail transit network with a set of nodes (stations) N and a set of links L (segments between adjacent stations) shown in Figure 4, each link can be denoted as a directed link $(i, j)$ from upstream station i to downstream station j, with a deterministic scheduled travel time. We then construct the space–time network $(V, E)$ , where V is the set of vertices and E is the set of arcs. Station i is extended to a set of vertices $(i, t)$ at each time interval t in the study time horizon, $t \in T$ . To consider current first and last train services, we build four types of arcs stated in the following.

Waiting arcs $(i, i, t, t + 1)$ are built from $(i, t)$ to $(i, t + 1)$ at any station i having waiting time as one time interval, where $(i, i, t, t + 1) \in E_{e}$ .

Existing traveling arcs $(i, j, t, s)$ are extended from a link $(i, j)$ and each arc traverses from vertex $(i, t)$ to vertex $(j, s)$ based on the given timetables at night before (including) the last and in the early morning after (including) the first train, where $(s - t)$ is the scheduled traveling time for link $(i, j)$ plus dwell time at station j . The capacity is defined as train carrying capacity, where $(i, j, t, s) \in E_{e}$ .

Transfer arcs $(i, j, t, s)$ are constructed based on a transfer link $(i, j)$ from time t to time s, where $(s - t)$ is the passenger transfer time from station i to station j, where $(i, j, t, s) \in E_{e}$ .

Dummy arcs $(i, i, t, T)$ are constructed at each station i from time t to time T to represent the arrival event for passengers arriving at their destination station i at time t, where $(i, i, t, T) \in E_{e}$ , for example, the solid line in Figure 5 is one of the dummy arcs in station 5, every node in station 5 will connect the dummy node in station 5 as the dummy arcs.

Penalty arcs $(i, j, t, T)$ are constructed at each station i from time t for passengers who cannot arrive at their destinations j due to failed transfers, where $(i, j, t, T) \in E_{p}$ , for example, the dotted line in Figure 5 are two of the penalty arcs; all the nodes in station 5 serving for last trains will connect the dummy nodes in station 8 and station 3 as the penalty arcs.

Figure 4.

Physical urban subway network.

Figure 5.

Space–time network construction.

In the proposed space–time network, the cost of waiting, traveling, and transfer arcs are set as the actual time cost. The costs of dummy arcs are set as minimum values, that is, 0.01. And the costs of penalty arcs are set as very large values, that is, 10000. Therefore, passengers will choose the shortest feasible path in the space–time network, when the total traveling cost of all passengers is minimized in the objective function.

For illustration purpose, we offer a timetable (Table 3) for last and first train services based on the given physical urban subway network (Figure 4), and corresponding space–time network can be built as shown in Figure 5. All the travel times of all links are set to be one-time unit. Dummy arcs and penalty arcs are also shown partially in Figure 5.

Table 3.

The timetable of current last and first train services.

Service	Line	Train	Station sequence	Departure timefrom origin station
Last train service	1	1	1-7-8-3	1
	2	1	2-5	1
		2	2-5	2
		3	2-5	3
	3	1	4-6	1
		2	4-6	2
		3	4-6	3
First trainservice	1	1	1-7-8-3	12
	2	1	2-5	11
		2	2-5	12
		3	2-5	13
	3	1	4-6	11
		2	4-6	12
		3	4-6	13

Constructing candidate arcs in the space–time network for scheduling overnight trains

To schedule overnight trains in an urban subway network, candidate overnight train operations arcs need to be further built into the space–time network. We construct the candidate overnight operations arcs into the set E. Two types of overnight train operation arcs should be built.

Candidate traveling arcs $(i, j, t, s)$ are constructed if an overnight train can depart from station i at time t and arrive at station j at time s, where $(i, j, t, s) \in E_{t}$ . In order to ensure that the departure time and arrive time of the overnight trains fall into the reasonable operation time window, the candidate traveling arcs generated after the last and before the first train should be not too late in the night and not too early in the morning, respectively.

Candidate stopping arcs $(i, i, t, s)$ are constructed for overnight stopping operation at station i, where $(i, i, t, s) \in E_{s}$ .

Figure 6 shows the construction for candidate overnight train operation arcs on Line 1.

Figure 6.

Space–time network with candidate overnight-train operation arcs.

Benefit analysis based on the illustrated example

As stated above, Figure 4 depicts a simple physical urban subway network with eight stations and three lines, and Figure 5 shows the space–time networks constructed based on given timetables of last and first train services listed in Table 3. We assume an overnight train schedule plan on Line 1 as shown in Table 4.

Table 4.

An overnight train schedule plan on Line 1.

Link	Departure time	Arrival time	Operation
(1,7)	3	4	Running
(7,8)	4	5	Running
(8,8)	5	13	Overnight stopping
(8,3)	13	14	Running

Figure 7 shows the space–time network with an illustrated overnight train service plan. To demonstrate the benefits of scheduling the overnight train, we load three passenger groups into the space–time network with specific volume, origin–destination (OD) pair, and departure time (Table 5). For last train service, passenger groups 1 and 2 can arrive at their destinations only when the overnight train is scheduled on Line 1. For first train service, the total waiting time can decrease from $3 \times 1 = 3$ to $0$ due to the additional overnight train.

Figure 7.

Space–time network with an illustrated overnight train service plan.

Table 5.

The comparison of travel time between two situations.

Group	OD	Volume	Departure time	Without overnight train		With overnight train
Group	OD	Volume	Departure time	Waiting time	Transfer	Waiting time	Transfer
1	2-8	3	1	–	Failed	0	Successful
2	2-8	2	2	–	Failed	0	Successful
3	4-3	3	11	1	Successful	0	Successful

OD: origin–destination.

Model formulation and solution approach

In this section, we formally propose the optimization model for the overnight train scheduling problem in an urban subway network and its solution approach.

Model formulation

We aim to minimize the number of failed transfer passengers for last train service and minimize the transfer waiting time for first train service by adopting the strategy of scheduling the overnight train on each line in an urban subway network. Two sets of passengers are taken into consideration: one set denotes passengers departing their origins at night, who concern that whether they can arrive at their destinations successfully; another set denotes passengers departing their origins in the early morning, who concern that whether they can avoid long transfer waiting time and arrive at their destinations as fast as possible. Typically, we adopt the linear weight method to handle these two sets of problems, and introduce $α$ and $β$ as the weight of transfer failed problem and long waiting time problem, respectively. We try to improve service levels for these two sets of passengers by optimally determining the overnight train schedule using our proposed model as follows.

Objective function

\begin{matrix} \min α \times [\sum_{a \in A} \sum_{(i, j, t, s) \in E_{e} \cup^{E_{t}}} c_{i, j, t, s} \times x_{i, j . t, s}^{a} + \sum_{a \in A} \sum_{(i, j, t, s) \in E_{p}} c_{i, j, t, s} \times x_{i, j . t, s}^{a}] + β \\ \times \sum_{a' \in A'} \sum_{(i, j, t, s) \in E_{e} \cup^{E_{t}}} c_{i, j, t, s} \times x_{i, j . t, s}^{a'} \end{matrix}

(1)

Subject to,

Passenger flow balance constraints

\begin{matrix} \sum_{i, t : (i, j, t, s) \in E_{e} \cup^{E_{t}}} x_{i, j, t, s}^{a} - \sum_{i, t : (j, i, s, t) \in E_{e} \cup^{E_{t}}} x_{j, i, s, t}^{a} \\ = {\begin{matrix} - 1 \\ 1 \\ 0 \end{matrix} \begin{matrix} j = o (a), s = DT (a) \\ j = d (a), s = T \\ otherwise \end{matrix} \forall a \in A \end{matrix}

(2)

\begin{matrix} \sum_{i, t : (i, j, t, s) \in E_{e} \cup^{E_{t}}} x_{i, j, t, s}^{a'} - \sum_{i, t : (j, i, s, t) \in E_{e} \cup^{E_{t}}} x_{j, i, s, t}^{a'} \\ = {\begin{matrix} - 1 \\ 1 \\ 0 \end{matrix} \begin{matrix} j = o (a'), s = DT (a') \\ j = d (a'), s = T \\ otherwise \end{matrix} \forall a' \in A' \end{matrix}

(3)

Overnight train flow balance constraint

\begin{matrix} \sum_{i, t : (i, j, t, s) \in E_{t} \cup^{E_{s}}} y_{i, j, t, s}^{q'} - \sum_{i, t : (j, i, s, t) \in E_{t} \cup^{E_{s}}} y_{j, i, s, t}^{q'} \\ = {\begin{matrix} - 1 \\ 1 \\ 0 \end{matrix} \begin{matrix} j = o (q'), s = DT (q') \\ j = d (q'), s = AT (q') \\ otherwise \end{matrix} \forall q' \in Q' \end{matrix}

(4)

Passenger flow and overnight train flow coupling constraints

\sum_{a} x_{i, j, t, s}^{a} \leq \sum_{q'} y_{i, j, t, s}^{q'} \times Ca p_{i, j, t, s} \forall (i, j, t, s) \in E_{t}

(5)

\sum_{a'} x_{i, j, t, s}^{a'} \leq \sum_{q'} y_{i, j, t, s}^{q'} \times Ca p_{i, j, t, s} \forall (i, j, t, s) \in E_{t}

(6)

Binary variable constraints

x_{i, j, t, s}^{a} \in {0, 1}

(7)

x_{i, j, t, s}^{a'} \in {0, 1}

(8)

y_{i, j, t, s}^{q'} \in {0, 1}

(9)

The first part of the objective function (equation (1)) aims to minimize the total travel time of passengers at night. The second part of the objective function gives penalties to passengers who cannot arrive at their destinations due to failed transfers. The third part of the objective function aims to minimize the total travel time of passengers in the early morning. Equations (2) and (3) give the standard passenger flow balance constraints. Overnight train flow balance constraint is formulated in equation (4). Equations (5) and (6) define the coupling relationship between passengers and overnight trains. Equations (7)–(9) define the binary variables for the model formulation.

Considering about the maintenance time window

Considering that the maintenance operations at certain stations during the night would affect the service of the overnight train. Therefore, we further consider the maintenance time window constraint in our proposed model. In previous, many researchers studied the problem of connection between train dispatching and maintenance operations. Zhang et al.³² formulated an MILP model to select the time window of the regular maintenance on high-speed railway; the objective of the model is to minimize the total travel time of sunset-departure and sunrise-arrival trains (SDSA-trains). Aken et al.³³ proposed an MILP model to solve the Timetable Adjustment Problem, which can get an alternative timetable with re-timing, re-ordering, short-turning, and cancelation under the condition of maintenance. Lidén et al.³⁴ proposed a mixed integer programming model to minimize the total cost of maintenance and train operations which coordinate the railway maintenance and train traffic.

In this article, we schedule the overnight trains to minimize the number of failed transfer passengers for the last train service and minimize the transfer waiting time for the first train service; therefore, the overnight train must stay in a station for a whole night. In actual, not all stations can offer the stopping operation because of the maintenance operation. In order to avoid the conflict between the train schedule and maintenance time window, the maintenance constraint can be further formulated into the proposed model as follow

\sum_{t_{i}^{start} \leq t, s \leq t_{i}^{end} : (i, i, t, s) \in E_{s}} y_{i, i, t, s}^{q'} = 0 \forall i \in N', q'

(10)

In this equation, $(t_{i}^{start}, t_{i}^{end})$ is the maintenance time window in the station i, and the $N'$ is the set of stations which has maintenance operations.

Problem decomposition

In this section, we propose an LR framework to solve the model. We set up a multiplier $λ_{i, j, t, s}^{last}$ and $λ_{i, j, t, s}^{first}$ to dualize passenger flow and train flow coupling constraints (equations (5) and (6)) into the objective function to generate lower bounds. After implementing the LR, the objective function is transformed to equation (11) as follows.

Objective function

\begin{matrix} \min α \times \sum_{a \in A} \sum_{(i, j, t, s) \in E_{e} \cup E_{t} \cup E_{p}} c_{i, j, t, s} \times x_{i, j . t, s}^{a} + β \\ \times \sum_{a' \in A'} \sum_{(i, j, t, s) \in E_{e} \cup E_{t}} c_{i, j, t, s} \times x_{i, j . t, s}^{a'} + \sum_{(i, j, t, s) \in E_{t}} λ_{i, j, t, s}^{last} \\ \times [\sum_{a} x_{i, j, t, s}^{a} - \sum_{q'} y_{i, j, t, s}^{q'} \times Ca p_{i, j, t, s}] + \sum_{(i, j, t, s) \in E_{t}} λ_{i, j, t, s}^{first} \\ \times [\sum_{a'} x_{i, j, t, s}^{a'} - \sum_{q'} y_{i, j, t, s}^{q'} \times Ca p_{i, j, t, s}] \end{matrix}

(11)

Subject to constraints (2)–(4) and (7)–(10).

The above problem can be decomposed into three sub-problems $P_{last, x}$ , $P_{first, x}$ , and $P_{y}$ due to the decision variables $x_{i, j, t, s}^{a}$ , $x_{i, j, t, s}^{a'}$ and $y_{i, j, t, s}^{q'}$ . The sub-problems $P_{last, x}$ and $P_{first, x}$ are standard time-dependent shortest path problems, and sub-problem $P_{y}$ is a semi-assignment problem.

Sub-problem $P_{last, x}$

Objective function

\begin{matrix} \min α \times \sum_{a \in A} \sum_{(i, j, t, s) \in E_{e} \cup E_{p}} c_{i, j, t, s} \times x_{i, j . t, s}^{a} + α \\ \times \sum_{a \in A} \sum_{(i, j, t, s) \in E_{t}} (c_{i, j, t, s} + λ_{i, j, t, s}^{last}) \times x_{i, j . t, s}^{a} \end{matrix}

(12)

Subject to constraints (2) and (7).

Sub-problem $P_{first, x}$

Objective function

\begin{matrix} \min β \times \sum_{a' \in A'} \sum_{(i, j, t, s) \in E_{e} \cup E_{p}} c_{i, j, t, s} \times x_{i, j . t, s}^{a'} + β \\ \times \sum_{a' \in A'} \sum_{(i, j, t, s) \in E_{t}} (c_{i, j, t, s} + λ_{i, j, t, s}^{first}) \times x_{i, j . t, s}^{a'} \end{matrix}

(13)

Subject to constraints (3) and (8).

Sub-problem $P_{y}$

Objective function

\begin{matrix} \max \sum_{(i, j, t, s) \in E_{t}} λ_{i, j, t, s}^{last} \times \sum_{q'} y_{i, j, t, s}^{q'} \times Ca p_{i, j, t, s} \\ + \sum_{(i, j, t, s) \in E_{t}} λ_{i, j, t, s}^{first} \times \sum_{q'} y_{i, j, t, s}^{q'} \times Ca p_{i, j, t, s} \end{matrix}

(14)

Subject to constraints (4), (9) and (10).

Solution process

Based on the model decomposition, we propose a LR-based solution framework to solve the proposed model iteratively. The specific procedure is described as follows:

Step 1: Initialization. Initialize iteration number

g = 0

; Construct the space–time network; Input passenger demand; Initialize the Lagrangian multipliers

λ_{i, j, t, s}^{last}

and

λ_{i, j, t, s}^{first}

as positive values;Step 2: Solve the sub-problems

P_{last, x}

and

P_{first, x}

to obtain variables

x_{i, j, t, s}^{a}

and

x_{i, j, t, s}^{a'}

;Step 3: Solve the sub-problem

P_{y}

to obtain variable

y_{i, j, t, s}^{q'}

Step 4: Update Lagrangian multipliers: Step 4.1: Calculate the sub-gradient: Sub-gradient of passenger flow and train flow coupling constraint:

\nabla λ_{i, j, t, s}^{last} = \sum_{a} x_{i, j, t, s}^{a} - \sum_{q'} y_{i, j, t, s}^{q'} \times Ca p_{i, j, t, s}

for any

(i, j, t, s) \in E_{t}

;

\nabla λ_{i, j, t, s}^{first} = \sum_{a'} x_{i, j, t, s}^{a'} - \sum_{q'} y_{i, j, t, s}^{q'} \times Ca p_{i, j, t, s}

for any

(i, j, t, s) \in E_{t}

; Step 4.2: Update Lagrangian multiplier: Multiplier of passenger flow and train flow coupling constraint:

λ_{i, j, t, s}^{l a s t, g + 1} = m a x {0, λ_{i, j, t, s}^{l a s t, g} + α^{g} \times \nabla λ_{i, j, t, s}^{l a s t}}

;

λ_{i, j, t, s}^{f i r s t, g + 1} = m a x {0, λ_{i, j, t, s}^{f i r s t, g} + α^{g} \times \nabla λ_{i, j, t, s}^{f i r s t}}

;Step 5: Termination condition test If g is equal to the predetermined maximum iteration number G, terminate the algorithm; otherwise,

g = g + 1

and turn back to step 2.

In the LR framework, sub-problems $P_{last, x}$ and $P_{first, x}$ can be solved by standard shortest path finding package,³⁵ and sub-problem $P_{y}$ is a semi-assignment problem which can be solved easily. The LR solution framework is shown in Figure 8. The three sub-problems are independent, which can be parallel computed in each iteration to improve the computing efficiency for large-scale network.

Figure 8.

The solution framework based on Lagrangian decomposition.

Numerical examples

In this section, we construct a simple network and solve it by the proposed optimization model with both CPLEX solver and the LR-based solution approach. To demonstrate the advantages of the LR-based solution approach, we compare the computing time and gap between these two approaches.

A simple case

In this section, we initially test our proposed model and solution approach in a simple case. As shown in Figure 9, the test network contains 4 bi-direction lines and 16 stations. The minimum time interval is 1 min in the simple case; and the study time horizon is 60 min. The train capacity is set to be 1000 (because the train capacity is enough at night and in the early morning), and two sets of input passenger demand are listed in Tables 6 and 7. The timetables of existing trains for the last and first train services are listed in Table 8.

Figure 9.

The physical urban subway network.

Table 6.

The demand of the last train service passengers.

Passenger	OD	Departure time	Passenger	OD	Departuretime	Passenger	OD	Departure time	Passenger	OD	Departuretime	Passenger	OD	Departure time
1	(1,8)	31	2	(1,8)	39	3	(1,8)	47	4	(1,7)	31	5	(1,7)	39
6	(1,7)	47	7	(1,6)	31	8	(1,6)	39	9	(1,6)	47	10	(6,1)	31
11	(6,1)	39	12	(6,1)	47	13	(6,7)	31	14	(6,7)	39	15	(6,7)	47
16	(6,8)	31	17	(6,8)	39	18	(6,8)	47	19	(2,3)	31	20	(2,3)	39
21	(2,3)	47	22	(2,4)	31	23	(2,4)	39	24	(2,4)	47	25	(2,5)	31
26	(2,5)	39	27	(2,5)	47	25	(5,4)	31	29	(5,4)	39	30	(5,4)	47
31	(5,3)	31	32	(5,3)	39	33	(5,3)	47	34	(5,2)	31	35	(5,2)	39
36	(5,2)	47

OD: origin–destination.

Table 7.

The demand of the first train service passengers.

Passenger	OD	Departuretime	Passenger	OD	Departuretime	Passenger	OD	Departuretime	Passenger	OD	Departuretime	Passenger	OD	Departuretime
37	(1,8)	7	38	(1,8)	15	39	(1,8)	23	40	(1,7)	7	41	(1,7)	15
42	(1,7)	23	43	(1,6)	7	44	(1,6)	15	45	(1,6)	23	46	(6,1)	7
47	(6,1)	15	48	(6,1)	23	49	(6,7)	7	50	(6,7)	15	51	(6,7)	23
52	(6,8)	7	53	(6,8)	15	54	(6,8)	23	55	(2,3)	7	56	(2,3)	15
57	(2,3)	23	58	(2,4)	7	59	(2,4)	15	60	(2,4)	23	61	(2,5)	7
62	(2,5)	15	63	(2,5)	23	64	(5,4)	7	65	(5,4)	15	66	(5,4)	23
67	(5,3)	7	68	(5,3)	15	69	(5,3)	23	70	(5,2)	7	71	(5,2)	15
72	(5,2)	23

OD: origin–destination.

Table 8.

The timetable of existing trains.

Line	Train	Station sequence	Time sequence	Line	Train	Station sequence	Time sequence
Line 1 up	1	$1 \to 10 \to 12 \to 6$	$8 \to 9 \to 10 \to 11$	Line 1 up	4	$1 \to 10 \to 12 \to 6$	$32 \to 33 \to 34 \to 35$
Line 1 up	2	$1 \to 10 \to 12 \to 6$	$16 \to 17 \to 18 \to 19$	Line 1 up	5	$1 \to 10 \to 12 \to 6$	$40 \to 41 \to 42 \to 43$
Line 1 up	3	$1 \to 10 \to 12 \to 6$	$22 \to 23 \to 24 \to 25$	Line 1 up	6	$1 \to 10 \to 12 \to 6$	$48 \to 49 \to 50 \to 51$
Line 1 down	1	$6 \to 12 \to 10 \to 1$	$8 \to 9 \to 10 \to 11$	Line 1 down	4	$6 \to 12 \to 10 \to 1$	$32 \to 33 \to 34 \to 35$
Line 1 down	2	$6 \to 12 \to 10 \to 1$	$16 \to 17 \to 18 \to 19$	Line 1 down	5	$6 \to 12 \to 10 \to 1$	$40 \to 41 \to 42 \to 43$
Line 1 down	3	$6 \to 12 \to 10 \to 1$	$22 \to 23 \to 24 \to 25$	Line 1 down	6	$6 \to 12 \to 10 \to 1$	$48 \to 49 \to 50 \to 51$
Line 2 up	1	$2 \to 14 \to 16 \to 5$	$12 \to 13 \to 14 \to 15$	Line 2 up	4	$2 \to 14 \to 16 \to 5$	$36 \to 37 \to 38 \to 39$
Line 2 up	2	$2 \to 14 \to 16 \to 5$	$20 \to 21 \to 22 \to 23$	Line 2 up	5	$2 \to 14 \to 16 \to 5$	$44 \to 45 \to 46 \to 47$
Line 2 up	3	$2 \to 14 \to 16 \to 5$	$26 \to 27 \to 28 \to 29$	Line 2 up	6	$2 \to 14 \to 16 \to 5$	$52 \to 53 \to 54 \to 55$
Line 2 down	1	$5 \to 16 \to 14 \to 2$	$12 \to 13 \to 14 \to 15$	Line 2 down	4	$5 \to 16 \to 14 \to 2$	$36 \to 37 \to 38 \to 39$
Line 2 down	2	$5 \to 16 \to 14 \to 2$	$20 \to 21 \to 22 \to 23$	Line 2 down	5	$5 \to 16 \to 14 \to 2$	$44 \to 45 \to 46 \to 47$
Line 2 down	3	$5 \to 16 \to 14 \to 2$	$26 \to 27 \to 28 \to 29$	Line 2 down	6	$5 \to 16 \to 14 \to 2$	$52 \to 53 \to 54 \to 55$
Line 3 up	1	$8 \to 9 \to 13 \to 3$	$10 \to 11 \to 12 \to 13$	Line 3 up	2	$8 \to 9 \to 13 \to 3$	$53 \to 54 \to 55 \to 56$
Line 3 down	1	$3 \to 13 \to 9 \to 8$	$10 \to 11 \to 12 \to 13$	Line 3 down	2	$3 \to 13 \to 9 \to 8$	$53 \to 54 \to 55 \to 56$
Line 4 up	1	$7 \to 11 \to 15 \to 4$	$14 \to 15 \to 16 \to 17$	Line 4 up	2	$7 \to 11 \to 15 \to 4$	$50 \to 51 \to 52 \to 53$
Line 4 down	1	$4 \to 15 \to 11 \to 7$	$14 \to 15 \to 16 \to 17$	Line 4 down	2	$4 \to 15 \to 11 \to 7$	$50 \to 51 \to 52 \to 53$

In the simple case, we input a set of 72 passengers and 32 current trains. Four overnight trains are to be scheduled in four lines (Line 3 up direction, Line 3 down direction, Line 4 up direction, and Line 4 down direction). The simple case can be directly solved by CPLEX solver, from which the optimal schedules of the four overnight trains can be obtained are shown in Table 9. Figure 10 shows the space–time network, including space–time arcs of existing first and last and overnight trains.

Table 9.

The results of overnight trains.

Line	Segment	Departure time	Arrival time	Operation
Line 3 up	$8 \to 13$	14	16	Running
	$13 \to 13$	16	35	Stopping
	$13 \to 3$	35	36	Running
Line 3 down	$3 \to 9$	14	16	Running
	$9 \to 9$	16	35	Stopping
	$9 \to 8$	35	36	Running
Line 4 up	$7 \to 15$	17	19	Running
	$15 \to 15$	19	38	Stopping
	$15 \to 4$	38	39	Running
Line 4 down	$4 \to 11$	17	19	Running
	$11 \to 11$	19	38	Stopping
	$11 \to 7$	38	39	Running

Figure 10.

The corresponding space–time network of the simple case (only train service arcs are shown).

We compare four indicators between the timetables with and without overnight trains, based on the same input demand, as shown in Table 10 and Figure 11. For the last train services, all eight passengers who cannot arrive at their destinations due to failed transfers can successfully complete their trips if the overnight trains are scheduled. For the first train services, the total travel time and waiting time of all passengers in the early morning can be decreased by 28.7% and 38.6%, respectively.

Table 10.

The comparison results of the simple case.

Indicator	Without overnight train	With overnight train
Number of passengers who suffer failed transfers	8	0
Number of passengers who can arrive at their destinations	28	36
Total travel time of passengers in the early morning	558	398
Total waiting time of passenger in the early morning	414	254

Figure 11.

The comparison results of the simple case.

Then, we use the proposed LR-based solution framework to solve the same case for 100 iterations, from which the lower bound values can be obtained as approximate solutions. Figure 12 shows the optimal lower bound values for 100 iterations, from which a small gap 1.49% is reached between the optimal value and the lower bound value after 100 iterations. Therefore, the proposed LR-based solution framework can obtain the approximate optimal value compared with the optimal value obtained by CPLEX solver with a large amount of computing time saved, especially for more large-scale case. Table 11 compares the efficiency between CPLEX and Lagrangian-based decomposition method.

Figure 12.

Lower bounds and optimal value for each iteration.

Table 11.

The methods efficiency comparison.

Method	CPLEX	Lagrangian-based decomposition method
Time	10.6 min	5 s per iteration

Considering the trade-off between the cost of the overnight trains and value of the objective, we do a test to analyze the relation between them. In the test, we remove different numbers of overnight trains to find the changes of the objective value. The cost of the overnight trains can be defined as a linear function (equation (15)) depending on their operational time, including traveling time between stations

c_{overnight train} = γ \times \sum_{q'} \sum_{(i, j, t, s) \in E_{t}} y_{i, j, t, s}^{q'}

(15)

Table 12 presents the value of the objective when some overnight trains are removed, and we set $γ = 1$ in our test. Because the passengers demand and physical network are symmetric, the situations we set are only “No overnight train,”“Cancel three overnight trains,”“Cancel two overnight trains,”“Cancel one overnight train,” and “No cancellation.” We can find that although the cost of the overnight trains increases, the total cost has a decreasing trend.

Table 12.

The comparisons in five situations.

Situations	Objective value	Cost of the overnight trains	Total
No overnight train	3219.12	0	3219.12
Cancel three overnight trains	3040.08	22	3062.08
Cancel two overnight trains	2927.62	44	2971.62
Cancel one overnight train	2856.18	66	2922.18
No cancelation	2810.56	88	2898.56

A real-world case

In this section, we apply the proposed model and LR-based solution approach into the Beijing Subway Network. The structure of Beijing Subway Network is shown in Figure 13, which includes 17 lines, 343 stations, and 3168 links in the physical network. The first train usually begins after 5:30 and the last train stops before 24:00 on each line. Therefore, we select the passengers who depart their origins after 22:00 as input passenger demand for last train service, and passengers who depart their origins before 6:00 as input passenger demand for the first train service. We assume that two overnight trains can be scheduled on each line, in the up and down direction, respectively, and the overnight trains can choose to stop at the stations which have no maintenance operation along the line during non-service period. In actual application, operators can determine some candidate stations to offer the opportunity for the overnight stopping operation of the overnight trains, which can be carried out by constructing candidate stopping arcs at allowable stations.

Figure 13.

The Beijing subway network (17 bi-direction lines, 343 stations, 52 transfer stations).

The passenger demand data are obtained from the smart card AFC system, and the total number of passenger demand in this case study is more than 30,000. Therefore, we group passengers according to their OD pairs and departure times. The capacity of each train is set to 1500. On account of the large number of vertices and arcs built in the space–time network, the scale of the Beijing Subway Network case is more extensive than the simple case tested in the section “A simple case.” It is impossible to solve the Beijing Subway Network case with CPLEX, so we use LR-based solution approach to solve it. We code the algorithm in Matlab platform with a PC (CPU: i7-7700HQ 2.80 GHZ with eight threads, 16 GB RAM) and run it for 20 iterations within about 5 h. We depict the schedule overnight trains in Figure 14 using the red and green triangles to denote the overnight stopping stations, and the two times near each triangle denote the starting and ending times of the overnight stopping operation for each overnight train. For example, the schedule of the overnight train in the up direction on Line 6 can be explained as follows: (1) the overnight train departs from Haidianwuluju Station (depot of Line 6) after the last and arrives at Beihaibei (BHB) station at 23:44; (2) the overnight train stops at BHB station from 23:44 to 5:12 for the non-service period; (3) the overnight train departs BHB station at 5:12 before the first train and finishes the remaining trip on Line 6.

Figure 14.

Optimized overnight train schedule plan.

The comparison results are shown in Table 13 and Figure 15. In the Beijing Subway Network case, we can increase additional 8091 passengers (increased by 92.2%) to arrive at their destinations by scheduling overnight trains on each line for the last train service. The total travel time and total waiting time of passenger in the early morning can be decreased by 7.8% and 13.4%, respectively.

Table 13.

The comparison results of the Beijing subway case.

Indicator	Original	Scheduling
Number of passengers who suffer failed transfers	10,479	2388
Number of passengers who can arrive at their destinations	8771	16,862
Total travel time of passengers in theearly morning	683,195	629,681
Total waiting time of passenger in the early morning	399,526	346,012

Figure 15.

The comparison results of the Beijing subway case.

Conclusions

In this article, we propose a novel optimization model to schedule the overnight trains in an urban subway network. Compared with the last and first train problems,^4,24 this study introduces the concept of the overnight train that departs the depot after the last and stops at the station for non-service period and continues to finish the remaining trip before the first train, which can benefit both first and last train services in the subway network, specifically, to minimize the number of failed transfer passengers for last train service and the transfer waiting time for first train service. Then, we formulate the overnight train scheduling problem as a MILP model based on a well-designed time-discretized space–time network, which can be directly solved by CPLEX for small cases. To handle large-scale applications, we propose a LR-based decomposition and solution framework, which decomposes the original model into three sub-problems and solve them parallelly. The proposed model and algorithm are evaluated by a small case and a large-scale case based on the Beijing Subway Network. Results show that the proposed model can improve service levels for both last and first train services. For example, we can increase additional 8091 passengers (increased by 92.2%) to arrive at their destinations by scheduling overnight train on each line for the last train service. The total travel time and total waiting time of passengers in the early morning can be decreased by 7.8% and 13.4%, respectively. In future research, we will consider multimodal public transport cooperation and integrate regular trains, night trains, and buses to study a large network to meet the growing needs of passengers.

Footnotes

Acknowledgements

The fourth author would like to thank the support from the China Scholarship Council and the Innovative Practice Program for Graduate Students of Tsinghua University, China.

Handling Editor: James Baldwin

Declaration of conflicting interests

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

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research is support by the project “Improving the technology of railway passenger and freight transport efficiency and service level” (Number: 2018YFB1201402).

ORCID iD

Pan Shang

References

Wen

Gui

Tian

et al . Subway opening, traffic accessibility, and housing prices: a quantile hedonic analysis in Hangzhou, China. Sustainability 2018; 10: 2254.

Chen

Shen

Wang

et al . An evaluation of the low-carbon effects of urban rail based on mode shifts. Sustainability 2017; 9: 401.

Jiao

Chen

et al . An innovative approach to determining high-risk nodes in a complex urban rail transit station: a perspective of promoting urban sustainability. Sustainability 2018; 10: 2456.

Kang

Zhu

Sun

et al . Modeling the first train timetabling problem with minimal missed trains and synchronization time differences in subway networks. Transport Res B: Meth 2016; 93: 17–36.

Cordeau

J-F

Toth

Vigo

A survey of optimization models for train routing and scheduling. Transport Sci 1998; 32: 380–404.

Ibarra-Rojas

Delgado

Giesen

et al . Planning, operation, and control of bus transport systems: a literature review. Transport Res B: Meth 2015; 77: 38–75.

Wong

Yuen

Fung

et al . Optimizing timetable synchronization for rail mass transit. Transport Sci 2008; 42: 57–69.

Shafahi

Khani

A practical model for transfer optimization in a transit network: model formulations and solutions. Transport Res A: Pol 2010; 44: 377–389.

Niu

Tian

Zhou

Demand-driven train schedule synchronization for high-speed rail lines. IEEE T Intell Transp 2015; 16: 2642–2652.

10.

Tian

Niu

A bi-objective model with sequential search algorithm for optimizing network-wide train timetables. Comput Ind Eng 2019; 127: 1259–1272.

11.

Shang

Liu

et al . Timetable synchronization and optimization considering time-dependent passenger demand in an urban subway network. Transp Res Record. Epub ahead of print 14 May 2018. DOI: 10.1177/0361198118772958

12.

Pelletier

M-P

Trépanier

Morency

Smart card data use in public transit: a literature review. Transport Res C: Emer 2011; 19: 557–568.

13.

Han

Zhou

Smart urban transit systems: from integrated framework to interdisciplinary perspective. Urban Rail Transit 2018; 4: 49–67.

14.

Niu

Zhou

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

15.

Niu

Zhou

Gao

Train scheduling for minimizing passenger waiting time with time-dependent demand and skip-stop patterns: nonlinear integer programming models with linear constraints. Transport Res B: Meth 2015; 76: 117–135.

16.

Canca

Barrena

Algaba

et al . Design and analysis of demand-adapted railway timetables. J Adv Transport 2014; 48: 119–137.

17.

Canca

Barrena

De-Los-Santos

et al . Setting lines frequency and capacity in dense railway rapid transit networks with simultaneous passenger assignment. Transport Res B: Meth 2016; 93: 251–267.

18.

Yin

Tang

Yang

et al . Energy-efficient metro train rescheduling with uncertain time-variant passenger demands: an approximate dynamic programming approach. Transport Res B: Meth 2016; 91: 178–210.

19.

Yin

Yang

Tang

et al . Dynamic passenger demand oriented metro train scheduling with energy-efficiency and waiting time minimization: mixed-integer linear programming approaches. Transport Res B: Meth 2017; 97: 182–213.

20.

Shi

Yang

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

21.

Shang

Liu

et al . Equity-oriented skip-stopping schedule optimization in an oversaturated urban rail transit network. Transport Res C: Emer 2018; 89: 321–343.

22.

Shang

Yang

Optimization of urban single-line metro timetable for total passenger travel time under dynamic passenger demand. Procedia Engineer 2016; 137: 151–160.

23.

Shang

Guo

et al . Integrating Lagrangian and Eulerian observations for passenger flow state estimation in an urban rail transit network: a space-time-state hyper network-based assignment approach. Transport Res B: Meth 2019; 121: 135–167.

24.

Kang

Sun

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

25.

Kang

Sun

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

26.

Yin

Sun

et al . Optimizing last trains timetable in the urban rail network: social welfare and synchronization. Transportmetrica B 2019; 7: 473–497.

27.

Kang

Zhu

Sun

et al . Last train timetabling optimization and bus bridging service management in urban railway transit networks. Omega 2019; 84: 31–44.

28.

Guo

Sun

et al . Timetable coordination of first trains in urban railway network: a case study of Beijing. Appl Math Model 2016; 40: 8048–8066.

29.

Kang

Zhu

A simulated annealing algorithm for first train transfer problem in urban railway networks. Appl Math Model 2016; 40: 419–435.

30.

Kang

Zhu

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

31.

Chen

Zhou

Yue

et al . Data-driven method to estimate the maximum likelihood space–time trajectory in an urban rail transit system. Sustainability 2018; 10: 1752.

32.

Zhang

Gao

Yang

et al . Integrated optimization of train scheduling and maintenance planning on high-speed railway corridors. Omega. Epub ahead of print 16 August 2018. DOI: 10.1016/j.omega.2018.08.005

33.

Aken

Bešinović

Goverde

RMP

. Designing alternative railway timetables under infrastructure maintenance possessions. Transport Res B: Meth 2017; 98: 224–238.

34.

Lidén

Kalinowski

Waterer

Resource considerations for integrated planning of railway traffic and maintenance windows. J Rail Transp Plan Manag 2018; 8: 1–15.

35.

Gleich

MatlabBGL, 2006, https://www.cs.purdue.edu/homes/dgleich/packages/matlab_bgl/

Scheduling overnight trains for improving both last and first train services in an urban subway network

Abstract

Keywords

Introduction

Motivation

Literature review

Contribution

Key concepts for model formulation

Notations

Problem statement

Space–time network construction based on the current first and last train services

Constructing candidate arcs in the space–time network for scheduling overnight trains

Benefit analysis based on the illustrated example

Model formulation and solution approach

Model formulation

Considering about the maintenance time window

Problem decomposition

Solution process

Numerical examples

A simple case

A real-world case

Conclusions

Footnotes

Acknowledgements

Declaration of conflicting interests

Funding

ORCID iD

References