Last train timetable optimization considering detour routing strategy in an urban rail transit network

Abstract

As an important means of transportation, urban rail transit provides effective mobility, sufficient punctuality, strong security, and environment-friendliness in large cities. However, this transportation mode cannot offer a 24-h service to passengers with the consideration of operation cost and the necessity of maintenance, that is, a final time should be set. Therefore, operators need to design a last train timetable in consideration of the number of successful travel passengers and the total passenger transfer waiting time. This paper proposes a bi-level last train timetable optimization model. Its upper level model aims to maximize the number of passengers who travel by the last train service successful and minimize their transfer waiting time, and its lower level model aims to determine passenger route choice considering the detour routing strategy based on the last train timetable. A genetic algorithm is proposed to solve the upper level model, and the lower level model is solved by a semi-assignment algorithm. The implementation of the proposed model in the Beijing urban rail transit network proves that the model can optimize not only the number of successful transfer directions and successful travel passengers but also the passenger transfer waiting time of successful transfer directions. The optimization results can provide operators detailed information about the stations inaccessible to passengers from all origin stations and uncommon path guides for passengers of all origin–destination pairs. These types of information facilitate the operation of real-world urban rail transit systems.

Introduction

Motivation and incitement

With the continuous expansion of urban traffic demand, the urban rail transit plays an increasingly important role in the urban public transport system because of its effective mobility, sufficient punctuality, strong security, and environment-friendliness.^1–3 As one of the most important stages in operation management, the timetable has a significant effect on the quality and efficiency of urban rail transit systems. Therefore, the issue of timetable synchronization and optimization in urban metro networks is attracting considerable interests.^4–6

A special case of timetable synchronization and optimization problems is the last train timetable problem. Due to the necessity of maintenance and saving operation cost, urban rail transit usually does not provide services to passengers during mid-night, that is, the final time need to be set for passengers to take the train or transfer.^7,8 The last train may be the last chance for passengers to complete their travels in an urban rail transit system. Therefore, the accessibility rather than travel time becomes the first-order consideration for passengers which makes detour routing strategy being available for passengers to complete their travel through the last train service. We use an illustrative example to explain the detour routing strategy in the following. As shown in Figure 1, passengers from the marked origin to the destination can intuitively select Route 1 or Route 2 to minimize their total travel time. However, if the passengers fail in the transfer at S2 in Route 1 and the transfer at S3 in Route 2, they are willing to choose a detour route (Route 3) and successfully transfer to the destination at S4, as it is their last chance to travel via the urban rail transit network at night. If passengers cannot reach their destination by the urban rail transit network, they will spend much more money on the taxi ride or give up their travel because there is no alternative to traveling at night.

Figure 1.

Detour routing strategy choice for passengers by the last train service.

Besides the detour routing strategy, the origin–destination (OD) based passenger demand should also be considered to assess the network accessibility for the last train service.^9,10 This is because the independent transfer optimization cannot guarantee that most of the passengers can complete their travel through the last train service under network operation. For example, Figure 2 shows a route from the origin station to the destination station containing two transfer directions. If one or two transfer directions are unsuccessful (Situations (a), (b), and (c) in Figure 2), then the passengers cannot complete their travel by this route. Therefore, this study further considers the OD-based passenger demand, and transfer directions are not optimized independently in this study but integrated into the passenger route choices.

Figure 2.

Three situations of unsuccessful travel: (a) Situation 1, (b) Situation 2, and (c) Situation 3.

In conclusion, we aim to propose a last train timetable optimization model in this study to maximize the number of successful travel passengers and minimize their transfer waiting time, while the OD-based passenger demand and the detour routing strategy are mainly considered for the particular last train services in an urban rail transit network.

Literature review

This study belongs to a special class of urban railway train timetable optimization problem (TTP), namely the last train timetable optimization problem (LTTP). One significant difference between the LTTP and general TTP is the objectives. Specifically, the optimization objective of TTP usually is to minimize the total traveling time or total waiting time of the passengers. In contrast, in the LTTP, the main objective is to ensure that maximum number of passengers can finish their trip successfully, while the traveling time and waiting time can just be viewed as a secondary objective. As LTTP is a special case of TTP, we discuss these two closely related streams of literature as follows.

Literature review on train TTP

TTP has received significant attention from the urban rail transit field.^4,5,11 Specifically, many researchers focused on timetable optimization problems which aim to minimize the total passenger transfer waiting time at transfer stations. For instance, Domschke ¹² proposed an optimization model for minimizing the total passenger transfer waiting time by optimizing train dispatch time, while the passenger demand has not been considered. Wong et al. ¹³ formulated the timetable synchronization problem as a mixed-integer programming model that minimizes the total transfer waiting time of passengers. Wu et al. ¹⁴ considered the waiting time equitably and developed a timetable synchronization optimization model to balance the transfer waiting time in all transfer stations.

Besides the transfer waiting time at transfer stations, studies have also resolved passenger total waiting time or total travel time. Vansteenwegen and Van Oudheusden ¹⁵ developed a linear programming model that aims to minimize the total waiting times and the late arrivals, and a real-world case for a small part of the Belgian railway network has been solved. Sun et al. ¹⁶ proposed three optimization models for designing demand-sensitive timetables to reduce passenger total waiting time. They also assessed the performance of the three models on a metro line in Singapore. Barrena et al.^17,18 and Shang et al. ¹⁹ proposed models under dynamic passenger demand and a single railway corridor for minimizing passenger average/total waiting time. Niu et al. ²⁰ and Gao et al. ²¹ studied the skip-stop pattern in urban rail lines and proposed optimization models applied in normal and disruption situations to minimize total passenger waiting time. Siebert and Goerigk, ²² Schmidt and Schöbel, ²³ and Wang et al. ²⁴ took the passenger demand into consideration and focused on the integration of train timetable and passenger routes; optimization models are proposed to minimize passenger total travel time.

Literature review on the first or last train timetable optimization problem

With the development of urban rail transit networks, the first or last train timetable optimization problems are attracting much more attention. Kang et al. ⁷ studied LTTP and proposed models to maximize passenger transfer connecting headways and transfer redundant time of the key directions in an urban rail transit network. Using the proposed model, they aimed to improve connectivity and reduce passenger transfer waiting time. A rescheduling model for last trains was also proposed by Kang et al., ²⁵ which considered the train delays caused by incidents. Dou et al. ²⁶ studied the bus and last train coordination problem; a mixed integer nonlinear programming model was proposed to reduce transfer failures on the basis of the given last train schedules. Kang et al. ²⁷ studied the first train timetable problem in an urban rail transit network and proposed suggestions to improve the operation and management of the urban rail transit network in Beijing. Yang et al. ²⁸ considered the transfer demand variability within passengers’ decision-process for LTTP and developed a model with consideration of the decision-makers’ risk preferences in subway systems under uncertainty.

However, few studies for optimizing last train timetable have not considered the detour routing strategy, which can considerably improve the possibility of successful travel. One of the main differences between the last train and regular time train is that accessibility instead of travel time becomes the most important factor passengers consider. Therefore, the OD-based passenger demand and detour routing strategy should not be ignored in the LTTPs.

Contributions and paper organization

The contributions of this study are summarized as follows:

1. We make a comparison in Table 1 to show the differences between previous last train studies and this paper. To further optimize the last train timetable, we take the OD-based passenger demand and possible detour routing strategy into consideration and propose a bi-level last train timetable optimization model.

2. To solve the proposed model efficiently and make it practical enough to be applied to the large urban rail transit network, a genetic algorithm (GA) is proposed for solving the upper level model. To solve the lower level model, we design a semi-assignment algorithm, which can offer successful travel variables based on a last train timetable generated from the upper model.

3. The implementation of the proposed bi-level last train timetable optimization model to the Beijing urban rail transit network proves that the model can optimize the number of successful transfer directions, the number of successful travel passengers, and the passenger transfer waiting time of successful transfer directions.

Table 1.

The comparisons of the previous last train studies and this paper.

Study	Problem	Objective function	Passenger demand	Routing strategy
Kang et al. 7	Last train timetable optimization	Maximize connection headway	Considered by key directions	Not considered
Kang et al. 25	Last train rescheduling	Minimize the running and the dwell times and the difference between the original and the rescheduled timetable, maximize the average transfer redundant time	Not considered	Not considered
Kang et al. 8	Last train timetable optimization	Minimize total transfer connection time	Transfer passenger demand	Not considered
Yin et al. 29	Last train timetable optimization	Maximize the social service efficiency and minimize the revenue loss for the operating companies	Probability density of transfer passenger	Not considered
Kang et al. 30	Last train timetable and bus bridging service design	Minimize the number of failed passengers for last train service and the transfer waiting time for first train service	Transfer passenger demand	Not considered
This study	Last train timetable optimization	Maximize the number of successful travel passengers, minimize the transfer waiting time	OD-based passenger demand	Shortest and detour routes

OD: origin–destination.

The remainder of this paper is organized as follows. In section “Bi-level last train timetable optimization model and solution approach,” the LTTP is stated. In section “Solution algorithm,” we proposed the bi-level model and the solution approach. In section “Simple network test,” the proposed model and algorithm test on a simple network. Further implementation of the proposed model into a case study based on the Beijing Subway Network is conducted in section “Case study.” Finally, we give our conclusion in section “Conclusion.”

Bi-level last train timetable optimization model and solution approach

Assumptions

The model is constructed based on the following assumptions.

Assumption 1

Only passengers who arrive at system right before the last trains arriving are considered. These passengers are selected because they are at the highest risk of not completing their travel. In other words, if this group of passengers can complete their travel by the last train service, then the other passengers arriving earlier can complete their travel as well.

Assumption 2

The passengers originating from stations between a terminal station and a transfer station or between two transfer stations on the same line are regarded to be in the same origin station group. The reason is that passengers who arrive at the urban rail transit network right before the last trains arrive make choices only at transfer stations and are insensitive to the travel time. The same assumption applies to the destination station group.

Assumption 3

The passengers who arrive at the urban rail transit network right before the last trains will select the route in which all the transfer directions are successful on the basis of the published last train timetable. They will select this route even if it is circuitous because it is their last chance to complete their travel.

Notations

The parameters, subscripts, and decision variables are stated in Tables 2 and 3.

Table 2.

Parameters and subscripts for the model formulation.

Notations	Definition
$l,l\prime$	Index of lines, $l,l\prime \in L$
$s,s\prime$	Index of stations, $s,s\prime \in S\left(l\right)$
$g,g\prime$	Index of station groups, $g,g\prime \in G$
$w$	Index of station group pairs, $w=(g,g\prime )\in W$
$p$	Index of routes, $p\in P_w$
$d$	Index of transfer directions, $d=(\mathrm{sl},s\prime l\prime )\in D,D\left(p\right)$
$L$	The set of lines in an urban rail transit network
$S\left(l\right)$	The set of stations on line $l$
$G$	The set of station groups
$W$	The set of station group pairs
$P_w$	The set of routes for passengers of station group pair $w$
$D$	The set of transfer directions in an urban rail transit network
$D\left(p\right)$	The set of transfer directions in the route $p$
$t_l^{\mathrm{Earlist}}$	The earliest operation closing time on line $l$
$t_l^{\mathrm{Latest}}$	The latest operation closing time on line $l$
$t_{\mathrm{sl}}^{\mathrm{Run},\min }$	The minimum running time of the last train from station $s-1$ to station $s$ on line $l$
$t_{\mathrm{sl}}^{\mathrm{Run},\max }$	The maximum running time of the last train from station $s-1$ to station $s$ on line $l$
$t_{\mathrm{sl}}^{\mathrm{Stop},\min }$	The minimum stopping time of the last train at station $s$ on line $l$
$t_{\mathrm{sl}}^{\mathrm{Stop},\max }$	The maximum stopping time of the last train at station $s$ on line $l$
$t_{\mathrm{sl},s\prime l\prime }^{\mathrm{Transfer}}$	The passenger transfer time from station $s$ on line $l$ to station $s\prime$ on line $l\prime$
$h_l$	The headway of the trains on line $l$
$f_w$	The passenger demand for the last train service of station group pair $w$
$c_{w,p}$	Travel time cost for passengers of station group pair $w$ using route $p$

Table 3.

Decision variables.

Notations	Definition
$t_{\mathrm{sl}}^{\mathrm{Arr}}$	The arrival time of the last train at station $s$ on line $l$
$t_{\mathrm{sl}}^{\mathrm{Dep}}$	The departure time of the last train at station $s$ on line $l$
$t_{\mathrm{sl}}^{\mathrm{Run}}$	The running time of the last train from station $s-1$ to station $s$ on line $l$
$t_{\mathrm{sl}}^{\mathrm{Stop}}$	The stopping time of the last train at station $s$ on line $l$
$x_{\mathrm{sl},s\prime l\prime }$	Transfer binary variable, which equals 1 if the passengers from the last feeder train at station $s$ on line $l$ can successfully transfer to the connecting train at station $s\prime$ on line $l\prime$ ; equals 0 otherwise
$n_{\mathrm{sl},s\prime l\prime }$	The number of trains before the last connecting train at station $s\prime$ on line $l\prime$ that passengers can board from the last feeder train at station $s$ on line $l$ , $n_{\mathrm{sl},s\prime l\prime }\in Z$
$y_{w,p}$	Passenger route choice binary variable, which equals 1 if the passengers of station group pair $w$ choose route $p$ to complete their travel; equals 0 otherwise
$z_w$	Passenger successful travel binary variable, which equals 1 if the passengers of station group pair $w$ can complete their travel by the last train service; equals 0 otherwise

Upper level model formulation

To improve the level of passenger satisfaction, an optimized last train timetable must be operationally feasible and must maximize the number of successful travel passengers and minimize passenger transfer waiting time of successful transfer directions. Along this line, the first objective function of the upper level model is to maximize the number of successful travel passengers given as the first term in equation (1). The second objective function of the upper model is to minimize passenger transfer waiting time of successful transfer directions given as the second term in equation (1). In particular, we need to minimize the passenger transfer waiting time presented by $[t_{s\prime l\prime }^{\mathrm{Dep}}-(t_{\mathrm{sl}}^{\mathrm{Arr}}+t_{\mathrm{sl},s\prime l\prime }^{\mathrm{Transfer}})-n_{\mathrm{sl},s\prime l\prime }\times h_l]$ only when the passengers from the feeder train at station $s$ on line $l$ can successfully transfer to the connecting train at station $s\prime$ on line $l\prime (x_{\mathrm{sl},s\prime l\prime }=1)$ . Conversely, if the passengers fail to transfer $(x_{\mathrm{sl},s\prime l\prime }=0)$ , then the transfer waiting time do not need to be minimized because the transfer direction is considered unsuccessful

$$\begin{array}{c}\multicolumn{1}{c}{maxZ=\sum _{w\in W}{f}_w\times z_w-\sum _{d=(\mathrm{sl},s\prime l\prime )\in D}{x}_{\mathrm{sl},s\prime l\prime }}\\ \times [t_{s\prime l\prime }^{\mathrm{Dep}}-(t_{\mathrm{sl}}^{\mathrm{Arr}}+t_{\mathrm{sl},s\prime l\prime }^{\mathrm{Transfer}})-n_{\mathrm{sl},s\prime l\prime }\times h_l]\hfill \end{array}$$

(1)

The arrival time $t_{\mathrm{sl}}^{\mathrm{Arr}}$ and departure time $t_{\mathrm{sl}}^{\mathrm{Dep}}$ of the last train at station $s$ on line $l$ are decided by the arrival time $t_{1l}^{\mathrm{Arr}}$ of the last train at the first station on line $l$ , running times $t_{\mathrm{sl}}^{\mathrm{Run}}$ between stations, and stopping times $t_{\mathrm{sl}}^{\mathrm{Stop}}$ at stations; $t_{\mathrm{sl}}^{\mathrm{Arr}}$ and $t_{\mathrm{sl}}^{\mathrm{Dep}}$ can be calculated by equations (2) and (3), respectively

$$t_{\mathrm{sl}}^{\mathrm{Arr}}=t_{1l}^{\mathrm{Arr}}+\sum _{s\prime =1}^{s-1}{t}_{s\prime l}^{\mathrm{Stop}}+\sum _{s\prime =1}^{s-1}{t}_{s\prime l}^{\mathrm{Run}}\forall l,\forall s\in S\left(l\right)$$

(2)

$$t_{\mathrm{sl}}^{\mathrm{Dep}}=t_{1l}^{\mathrm{Arr}}+\sum _{s\prime =1}^s{t}_{s\prime l}^{\mathrm{Stop}}+\sum _{s\prime =1}^{s-1}{t}_{s\prime l}^{\mathrm{Run}}\forall l,\forall s\in S\left(l\right)$$

(3)

Several operational requirements must be satisfied, that is, the last train operation closing time $t_{\left|S\left(l\right)\right|l}^{\mathrm{Dep}}$ on each line, running times $t_{\mathrm{sl}}^{\mathrm{Run}}$ between stations, and stopping times $t_{\mathrm{sl}}^{\mathrm{Stop}}$ at stations must be limited within their upper and lower bounds presented by equations (4)–(6)

$$t_l^{\mathrm{Earlist}}\le t_{\left|S\left(l\right)\right|l}^{\mathrm{Arr}}\le t_l^{\mathrm{Latest}}\forall l$$

(4)

$$t_{\mathrm{sl}}^{\mathrm{Run},\min }\le t_{\mathrm{sl}}^{\mathrm{Run}}\le t_{\mathrm{sl}}^{\mathrm{Run},\max }\forall l,\forall s\in S\left(l\right)$$

(5)

$$t_{\mathrm{sl}}^{\mathrm{Stop},\min }\le t_{\mathrm{sl}}^{\mathrm{Stop}}\le t_{\mathrm{sl}}^{\mathrm{Stop},\max }\forall l,\forall s\in S\left(l\right)$$

(6)

At transfer stations, $x_{\mathrm{sl},s\prime l\prime }$ is a binary variable that can be calculated by equation (7), where $M$ is an arbitrarily large positive number. In this constraint, $x_{\mathrm{sl},s\prime l\prime }$ is equal to 1 when the passengers from the feeder train at station $s$ on line $l$ can successfully transfer to the connecting train at station $s\prime$ on line $l\prime$ , if $t_{s\prime l\prime }^{\mathrm{Dep}}-(t_{\mathrm{sl}}^{\mathrm{Arr}}+t_{\mathrm{sl},s\prime l\prime }^{\mathrm{Transfer}})\ge 0$ ; if $t_{s\prime l\prime }^{\mathrm{Dep}}-(t_{\mathrm{sl}}^{\mathrm{Arr}}+t_{\mathrm{sl},s\prime l\prime }^{\mathrm{Transfer}})<0$ , then $x_{\mathrm{sl},s\prime l\prime }$ is equal to 0. The connecting train integer variable $n_{\mathrm{sl},s\prime l\prime }$ can be calculated by equation (8), where $n_{\mathrm{sl},s\prime l\prime }<0$ denotes that passengers from the last feeder train station $s$ on line $l$ cannot transfer to the connecting train at station $s\prime$ on line $l\prime$

$$\begin{array}{c}M\times (x_{\mathrm{sl},s\prime l\prime }-1)\le t_{s\prime l\prime }^{\mathrm{Dep}}-(t_{\mathrm{sl}}^{\mathrm{Arr}}+t_{\mathrm{sl},s\prime l\prime }^{\mathrm{Transfer}})\hfill \\ \le M\times x_{\mathrm{sl},s\prime l\prime }\forall d=(\mathrm{sl},s\prime l\prime )\in D\hfill \end{array}$$

(7)

$$\begin{array}{c}{n}_{\mathrm{sl},s\prime l\prime }\times h_l\le t_{s\prime l\prime }^{\mathrm{Dep}}-(t_{\mathrm{sl}}^{\mathrm{Arr}}+t_{\mathrm{sl},s\prime l\prime }^{\mathrm{Transfer}})\hfill \\ \le (n_{\mathrm{sl},s\prime l\prime }+1)\times h_l\forall d=(\mathrm{sl},s\prime l\prime )\in D\hfill \end{array}$$

(8)

Lower level model formulation

The lower level model aims to determine whether the passengers of station group pair $w$ can complete their travel by the last train services (given by the first term of the objective function (9)) and find the corresponding best route for successful travel passengers based on the last train timetable obtained from the upper model (given by the second term of the objective function (9))

$$min\sum _{w\in W}\sum _{p\in P_w\cup \{p\prime \}}{c}_{w,p}\times y_{w,p}$$

(9)

Equation (10) establishes the relation between the route choice binary variable and the corresponding successful travel binary variables for the passengers of station group pair $w$ . The successful travel binary $z_w$ can be 1 if the passengers of station group pair $w$ can complete their travel by at least one route in the route set $P_w$ by the constraint (10)

$$z_w\le \sum _{p\in P_w}{y}_{w,p}\forall w$$

(10)

Equation (11) is formulated to determine whether the passengers of station group pair $w$ can complete their travel through route $p$ . The route choice binary variable $y_{w,p}$ can be 1 only if all transfer directions $d=(\mathrm{sl},s\prime l\prime )$ in the set $D(p)$ are connected $(x_{\mathrm{sl},s\prime l\prime }=1)$

$$y_{w,p}\le x_{\mathrm{sl},s\prime l\prime }\forall w,\forall p\in P_w,\forall d=(\mathrm{sl},s\prime l\prime )\in D\left(p\right)$$

(11)

Passengers of station group pair $w$ need to choose one feasible route in the set $P_w$ , or they will choose a virtual route $p\prime$ , which denotes that they cannot complete their travel by the last train service. The route choice constraint is formulated as equation (12)

$$\sum _{p\in P_w\cup \{p\prime \}}{y}_{w,p}=1\forall w$$

(12)

Bi-level optimization model

In general, the proposed bi-level last train timetable optimization model can be stated as follows. The upper level model aims to maximize the number of successful travel passengers and minimize transfer waiting time of successful transfer directions under the operation constraints. The lower level model finds the corresponding best route for passengers based on the last train timetable obtained from the upper model.

• Upper level model:

Objective function: equation (1).

Subject to: equations (2)–(8).

• Lower level model:

Objective function: equation (9).

Subject to: equations (10)–(12).

Solution algorithm

Genetic algorithm for the upper level model

Ibarra-Rojas and Rios-Solis ³¹ have proved that the timetable synchronization problem in the network is a NP-hard problem, where the solution time will increase exponentially with the size of problems when using traditional exact optimization method. Meta-heuristic algorithms, including GA, simulated annealing (SA) algorithm, particle swarm optimization (PSO) algorithm, extremal optimization (EO) algorithm, and adaptive large neighborhood search (ALNS) are commonly used to solve large-scale NP-hard problems.^32–39 Specially, GA has been widely applied on numerous transportation researches (e.g. Liu et al., ⁴⁰ Niu et al., ⁴¹ and Kang et al. ⁷ ) due to its strong robustness, high efficiency, and practical applicability. Therefore, in this study, we intend to use GA to find high-quality feasible solutions for the proposed model.

Note that it is difficult and unnecessary for GA to obtain a global optimal solution. Especially, in the non-convex optimization problem such as this study, the global optimal solutions can be obtained only if all the combinations of specific values for the variables have been tested, which results in the memory and solution time rising exponentially with the size of the problem. Thus, in order to ensure the practical applicability of the proposed model and algorithm, we choose GA to solve the problem even though it can only obtain sub-optimal solutions. To mitigate traps in local optimality, the mutation and crossover operations in the GA are adapted to maintain diversity in a population.

The direct decision variables of the upper level model can be stated as follows: the arrival time $\{t_{1l}^{\mathrm{Arr}}\}$ of the last train on each line $l$ , the running time $\{t_{\mathrm{sl}}^{\mathrm{Run}}\}$ of the last train between adjacent on each line $l$ , and the stopping time $\{t_{\mathrm{sl}}^{\mathrm{Stop}}\}$ of the last train at each station $s$ on line $l$ . The other decision variables can be calculated based on these three types of direct decision variables. In specific, the arrival time $t_{\mathrm{sl}}^{\mathrm{Arr}}$ and departure time $t_{\mathrm{sl}}^{\mathrm{Dep}}$ at any station $s$ on each line $l$ can be calculated by equations (2) and (3). The transfer binary variable $\{x_{\mathrm{sl},s\prime l\prime }\}$ and the number of trains before the last connecting train $\{n_{\mathrm{sl},s\prime l\prime }\}$ can be determined by equations (7) and (8). Therefore, we choose the direct decision variables to comprise the chromosome in the genetic algorithm as shown in Figure 3. Specifically, each chromosome consists of blocks with the number of |L| and each block contains three kinds of direct decision variables for corresponding lines. When a new population is generated, the lower and upper bounds of variables should subject to constraints (4), (5), and (6).

Figure 3.

An example of chromosome.

The fitness function is the objective function presented by equation (1), in which the variable $\{z_w\}$ in the first term can be obtained by solving the lower level model. We adopt four operations in GA, namely selection, reproduction, crossover, and mutation. First, the selection operator is used to choose a set of chromosomes as the parents for the next generation. This selection process is mainly based on the scaled value of fitness function, that is, the chromosomes lead to a larger value of objective function would have a higher possibility to be selected, vice versa. The reproduction operation aims to keep high-quality individual to the next iteration directly. The crossover operation is used to combine two parents to generate new off-springs. Moreover, the mutation operation is used to provide genetic diversity and mitigate the local optimality ⁴² by producing slight changes in selected chromosomes. For every generation, the idea of elitism specifies that sufficient individuals with the high-performance gene are survived to ensure the fast convergence of the GA. The stop criterion of the GA is the generation limit, which means that the iteration stops when the maximum number of iterations is reached. The solution framework is shown in Figure 4.

Figure 4.

Solution framework of the generic algorithm.

In this study, we use the partially mapping crossover in the crossover operation as Figure 5. We can see that each chromosome is divided into the variables for single transportation lines and crossover positions are generated randomly to choose lines. Then, the partially mapping crossover is conducted to obtain new off-springs.

Figure 5.

An example of crossover operation.

The mutation operation is conducted inside each line gene. First, the positions of mutation are generated randomly. Then, the gene in the selected position will be changed. Note that the updated value needs to subject to constraints (4), (5), and (6) as well. An example of mutation operation is shown as Figure 6.

Figure 6.

An example of mutation operation.

A semi-assignment algorithm for the lower level model

The lower level model aims to find the best route $\{y_{w,p}\}$ for passengers of each station group pair $w$ based on the given last train timetable information presented by $\{{\hat{x}}_{\mathrm{sl},s\prime l\prime }\}$ , and then return the successful travel variable $\{z_w\}$ to the upper level model. In this sub-section, we propose a simple semi-assignment algorithm to solve the lower level model as follows.

Simple network test

Simple network description

In this section, the proposed last train timetable optimization model and algorithm is first tested in a simple urban rail transit network illustrated in Figure 7, which is same as the simple network used by Kang et al. ⁷ This network has three bi-direction lines (Lines 1, 2, and 3) and five transfer stations (S1–S5). The transfer times are all set to be 0.2 min. Lines 1 and 3 are straight lines where two terminal stations exist, and Line 2 is a loop line. Twelve station groups (station group 1 to station group 12) are marked by the red numerals in Figure 7.

Figure 7.

Simple urban rail transit network.

The initial last train timetable of the simple urban rail transit network is shown in Table 4. The passenger demand for the last train service of all station group pairs is shown in Table 5. The headway of the trains on each line is set to 1 min.

Step 1: Initialization.

Initialize $z_w=0$ for each station group pair $w$ ;

Initialize $y_{w,p}=0$ for each station group pair $w$ and each route $p$ in the set $P_w$ .

Step 2: Route determination.

For each station group pair $w$ :

For each route $p$ in the set $P_w$ :

If ${\hat{x}}_{\mathrm{sl},s\prime l\prime }=1$ for any $d=(\mathrm{sl},s\prime l\prime )$ , $d\in D(p)$ :

Set $y_{w,p}=1$ ;

End // If

End // For

End // For

For each station group pair $w$ :

If $y_{w,p}=0$ for any route $p$ in the set $P_w$ :

Set $z_w=0$ ;

Set $y_{w,p\prime }=1$ ;

Otherwise:

Set $z_w=1$ ;

Find the route $p^{*}$ with the minimum cost $c_{w,p^{*}}$ among all route $p$ with $y_{w,p}=1$ in the set $P_w$ ;

End // If

End // For

Step 3: Output.

Output the successful travel variable $\{z_w\}$ for each station group pair $w$ ;

Output the route variable $\{y_{w,p}\}$ for each station group pair $w$ .

Table 4.

Initial last train timetable of the simple urban rail transit network.

Line		1		2		3
Direction		Up	Down	Up	Down	Up	Down
S1	Arr.	–	–	5.0	1.0	4.5	1.0
	Dep.	–	–	5.5	1.5	5.0	1.5
S2	Arr.	1.0	5.0	1.0	5.0	–	–
	Dep.	1.5	5.5	1.5	5.5	–	–
S3	Arr.	3.5	2.5	–	–	2.0	3.5
	Dep.	4.0	3.0	–	–	2.5	4.0
S4	Arr.	5.0	1.0	4.0	2.0	–	–
	Dep.	5.5	1.5	4.5	2.5	–	–
S5	Arr.	–	–	3.0	3.0	1.0	4.5
	Dep.	–	–	3.5	3.5	1.5	5.0

Table 5.

Passenger demand for the last train service of each station group pair.

Station group	1	2	3	4	5	6	7	8	9	10	11	12
1	–	–	–	–	10	6	3	12	5	7	3	6
2	–	–	–	–	21	5	6	9	8	2	3	7
3	–	–	–	–	9	3	4	15	4	5	3	7
4	–	–	–	–	14	8	4	9	4	7	8	8
5	18	5	8	12	–	–	–	–	5	7	1	10
6	14	6	7	10	–	–	–	–	10	8	5	4
7	9	4	5	7	–	–	–	–	6	4	1	9
8	10	7	8	9	–	–	–	–	12	9	4	16
9	12	8	10	8	9	6	5	8	–	–	–	–
10	14	12	7	14	10	8	6	10	–	–	–	–
11	10	7	8	2	3	8	9	9	–	–	–	–
12	9	10	8	6	7	5	7	16	–	–	–	–

Optimization results

We test this case on a personal computer with Intel Core i5-4210U 2.40 GHz and 8 GB RAM. The population size, crossover probability, mutation probability, and the maximum iteration are set as 100, 0.8, 0.2, and 60, respectively. The optimization process of the genetic algorithm is shown in Figure 8, from which we can see that the best solution is obtained in 44th iteration within 2 min.

Figure 8.

Iteration process of the GA for the simple network case.

Table 6 shows the optimized last train timetable, and Table 7 lists the corresponding optimized transfer results.

Table 6.

Optimized timetable of the simple urban rail transit network.

Line		1		2		3
Direction		Up	Down	Up	Down	Up	Down
S1	Arr.	–	–	5.0	2.5	4.9	1.9
	Dep.	–	–	5.5	3.0	5.4	2.9
S2	Arr.	1.6	5.2	1.0	6.0	–	–
	Dep.	2.6	6.2	2.0	6.5	–	–
S3	Arr.	3.1	4.2	–	–	3.4	3.4
	Dep.	3.6	4.7	–	–	4.4	4.4
S4	Arr.	4.1	2.7	3.5	3.5	–	–
	Dep.	5.1	3.7	4.5	4.5	–	–
S5	Arr.	–	–	2.5	5.0	1.9	4.9
	Dep.	–	–	3.0	5.5	2.9	5.4

Table 7.

Optimized transfer results of the simple urban rail transit network.

Station	Direction	Initial		Optimized		Station	Direction	Initial		Optimized
		$x_{\mathrm{sl},s\prime l\prime }$	$t_{\mathrm{sl},s\prime l\prime }^{\mathrm{wait}}$	$x_{\mathrm{sl},s\prime l\prime }$	$t_{\mathrm{sl},s\prime l\prime }^{\mathrm{wait}}$			$x_{\mathrm{sl},s\prime l\prime }$	$t_{\mathrm{sl},s\prime l\prime }^{\mathrm{wait}}$	$x_{\mathrm{sl},s\prime l\prime }$	$t_{\mathrm{sl},s\prime l\prime }^{\mathrm{wait}}$
1	L2D-L3U a	1	0.8	1	0.7	3	L1D-L3D	1	0.3	1	0.1
1	L3D-L2U	1	0.3	1	0.4	3	L3U-L1U	0	–	1	0.1
1	L2D-L3D	1	0.3	1	0.2	3	L1D-L3U	0	–	1	0.0
1	L3U-L2U	1	0.8	1	0.4	3	L3D-L1U a	1	0.3	1	0.0
1	L2U-L3D	0	–	0	–	4	L1U-L2U	0	–	1	0.2
1	L3U-L2D	0	–	0	–	4	L2D-L1D	0	–	1	0.4
1	L2U-L3U a	0	–	1	0.2	4	L1U-L2D	0	–	1	0.2
1	L3D-L2D	1	0.3	1	0.9	4	L2U-L1D	0	–	1	0.0
2	L1U-L2D	1	0.3	1	0.7	4	L1D-L2D	1	0.3	1	0.6
2	L2U-L1D a	1	0.3	1	0.0	4	L2U-L1U a	1	0.3	1	0.4
2	L1U-L2U	1	0.3	1	0.2	4	L1D-L2U	0	–	1	0.6
2	L2D-L1D a	1	0.3	1	0.0	4	L2D-L1U a	1	0.3	1	0.4
2	L1D-L2U	0	–	0	–	5	L2U-L3U	0	–	1	0.2
2	L2D-L1U	0	–	0	–	5	L3D-L2D	0	–	1	0.4
2	L1D-L2D	1	0.3	1	0.1	5	L2U-L3D a	1	0.8	1	0.7
2	L2U-L1U	1	0.3	1	0.4	5	L3U-L2D	1	0.3	1	0.4
3	L1U-L3U a	0	–	1	0.1	5	L2D-L3D a	1	0.8	1	0.4
3	L3D-L1D	0	–	1	0.1	5	L3U-L2U	1	0.3	1	0.9
3	L1U-L3D a	1	0.3	1	0.1	5	L2D-L3U	0	–	0	–
3	L3U-L1D	0	–	1	0.1	5	L3D-L2U	0	–	1	0.4

a

Key directions defined by Kang et al. ⁷

As shown in Table 7, the number of successful transfer directions in the simple urban rail transit network is increased from 21 to 35 after the last train timetable is optimized by the bi-level last train timetable optimization model. In the proposed model, 87.5% of all the transfer directions are successful, and all the key directions defined by Kang et al. ⁷ are optimized to successful transfer directions. Furthermore, the number of successful travel passengers between the initial timetable and the optimized timetable is shown in Table 8. The station group pairs containing the origin station group and destination station group on the same line are ignored in the model. The reason is that these passengers can complete their travel consequentially.

As shown in Table 8, the passengers of 15 station group pairs cannot complete their travel under the initial timetable. After optimizing the timetable, the number of successful travel passengers increases from 624 to 746, and 100% of all considered passengers successfully complete their travel. Although five transfer directions are not successful, as shown in Table 7, all passengers still successfully complete their travel. The reason is that some passengers can use detour routes in which all transfer directions are successful. Thus, the results of the optimized transfer directions and optimized number of successful travel passengers suggest that operators would better design an optimized last train timetable to maximize the number of successful travel passengers with appropriate numbers of successful transfer directions in an urban rail transit network.

Table 8.

Optimized number of successful travel passengers.

	1	2	3	4	5	6	7	8	9	10	11	12
1	– ***	–	–	–	10 *	6	3	12	5	7	3	6
2	–	–	–	–	(0)21 **	(0)5	(0)6	(0)9	(0)8	(0)2	(0)3	7
3	–	–	–	–	(0)9	(0)3	4	15	4	5	3	7
4	–	–	–	–	14	8	4	9	4	7	8	8
5	18	5	8	12	–	–	–	–	5	7	1	10
6	14	6	7	10	–	–	–	–	10	8	5	4
7	9	4	5	7	–	–	–	–	6	4	1	9
8	10	7	(0)8	(0)9	–	–	–	–	12	9	4	16
9	12	8	(0)10	(0)8	9	6	5	8	–	–	–	–
10	14	12	(0)7	(0)14	10	8	6	10	–	–	–	–
11	10	7	8	2	3	8	9	9	–	–	–	–
12	9	10	8	6	7	5	7	16	–	–	–	–

10^*: The number of successful travel passengers is 10 under initial timetable and optimized timetable.(0)21^**: The number of successful travel passengers is 0 under the initial timetable and 21 under the optimized timetable, and the bold value denotes that the number of successful travel passengers is increased in the optimized timetable than the initial one.–^***: Passengers between this station group pair are not considered in the model.

Case study

Network description

In this section, the proposed bi-level last train timetable optimization model and solution approach are validated by a real-world case, the Beijing urban rail transit network ⁴³ as depicted in Figure 9.

Figure 9.

Beijing subway network.

The studied network has 14 lines (7 bi-directed lines), 17 transfer stations, and 38 station groups, and the total number and the indexes of station groups on each line are listed in Table 9. The adjustment ranges of operation parameters of the studied urban rail transit network are listed in Table 10.

Table 9.

Number of station groups on each line.

Line	Number of station groups	Index of station groups
1	6	1–6
2	7	7–13
4	5	14–18
8	2	19–20
5	6	21–26
10	7	27–33
13	5	34–38

Table 10.

Adjustment range of operation parameters.

Operation parameters	Adjustment range
$t_{\mathrm{first},l}^{\mathrm{Arr}}$	±20 min
$t_{\mathrm{sl}}^{\mathrm{Run}}$	±20%
$t_{\mathrm{sl}}^{\mathrm{Stop}}$	±20%

In the urban rail transit network shown in Figure 9, each station group pair $w$ contains numerous feasible paths. Thus, the method used by Canca et al. ⁴⁴ for constructing path set $P_w$ is adopted in this study. We compute the $k$ shortest paths for every station group pair $w$ in the urban rail transit network, and set $k$ to 3 to identify three feasible paths in $P_w$ for the passengers of station group pair $w$ . After this pre-processing, the computing times for solving the proposed bi-level last train timetable optimization model can be significantly reduced. The proposed model and algorithm would have the ability to solve significantly large urban rail transit networks, such as the networks in Beijing, London, New York, and Tokyo.

The passenger demand for the last train service can be obtained from the smart card automated fare collection systems. As shown in Figure 10, the input data are represented by the number of passengers who arrive at the urban rail transit network right before the last trains and travel between all station group pairs.

Figure 10.

Input last train passenger demand between all station group pairs.

Optimization results

We test the case on a personal computer with Intel Core i5-4210U 2.40 GHz and 8 GB RAM. The parameters for the genetic algorithm are set as Table 11.

Table 11.

The parameter for the genetic algorithm.

Parameter	Value
Population size	500
Crossover probability	0.8
Mutation probability	0.2
Maximum GA iteration	180

GA: genetic algorithm.

The optimization process of GA is shown in Figure 11, from which we can see that the best solution is obtained in 112th iteration within 10 min.

Figure 11.

Iteration process of the GA for the Beijing subway network case.

Optimization results of successful transfer directions

Figures 9 and 12 show the successful transfer directions and the passenger transfer waiting times under the initial timetable and optimized timetable, respectively. The detailed optimization results of the transfer directions are listed in Table 12. The number of successful transfer directions in the case Beijing subway network increases from 77 to 96 after the last train timetable is optimized. As a result, 66.7% of all the transfer directions are successful under the optimized last train timetable. Thus, the optimized last train timetable can ensure the appropriate number and reasonable distribution of successful transfer directions in the case urban rail transit network and minimize the corresponding passenger transfer waiting time for the successful transfer directions.

Figure 12.

Successful transfer directions under the optimized timetable.

Table 12.

Optimization results of transfer directions.

Transfer station	Successful directions		Transfer station	Successful directions
	Initial timetable	Optimized timetable		Initial timetable	Optimized timetable
Huoying	4	5	Dongzhimen	4	4
Lishuiqiao	4	6	Fuxingmen	4	5
Hai-zhuang	4	5	Xidan	4	5
Zhichunlu	4	4	Dongdan	4	5
Beitucheng	4	5	Jainguomen	5	8
Hui-kou	4	5	Guomao	4	6
Shaoyaoju	4	5	Xuanwumen	4	4
Xizhimen	12	14	Chongwenmen	4	5
Yonghegong	4	5	–	–	–

Optimization results of the successful travel passengers

The difference between the number of successful travel passengers in the optimized last train timetable and in the initial one is shown in Figure 13, where the value higher than 0 denotes that the number of successful travel passengers increases after the last train timetable is optimized by the proposed model. Correspondingly, a value equal to 0 means there is neither increase nor decrease. And a value lower than 0 indicates that the number of successful travel passengers decreases under the optimized last train timetable compared with the initial last train timetable. Therefore, more passengers can complete their travel under the optimized timetable than under the initial timetable. The detailed optimization results of successful travel station group pairs and successful travel passengers are listed in Table 13.

Figure 13.

Increase in number of successful travel passengers.

Table 13.

Optimization results of the successful travel station group pairs and the successful travel passengers.

Timetable	Station group pair			Passengers
	Total number	Successful number	Percent	Total number	Successful number	Percent
Initial	1220	241	19.75%	10,457	2723	26.04%
Optimized	1220	657	53.85%	10,457	6365	60.87%

As shown in Table 13, a total of 6365 passengers (60.87% of all passengers) can complete their travel under the optimized last train timetable, compared with only 2723 passengers (26.04% of all passengers) under the initial timetable. A total of 3642 additional passengers can complete their travel after the last train timetable is optimized. The optimized last train table can significantly improve the service level of the urban rail transit network as a public transportation mode when the other transportation modes finish the operation at night. However, 4092 passengers (39.13% of all passengers) still cannot complete their travel under the optimized last train timetable. For example, the passengers from the origin stations between Fuxingmen station and Jianguomen station are inaccessible to the stations located on Lines 4, 8, and 13 and part of Line 5, as shown in Figure 14. For the convenience of passengers, the operators should inform passengers about the inaccessible destination stations in the urban rail transit network when the passengers arrive at their origin stations.

Figure 14.

Illustration of passengers who cannot arrive at their destinations.

Parameter sensitivity analysis

Operation closing time of the last train

In the case study, the adjustment range of the operation closing time denoted by the departure time $t_{\mathrm{last},l}^{\mathrm{Dep}}$ of the last train at the last station on each line is limited within ±20 min to ensure that the optimized last train timetable does not deviate considerably from the initial timetable. However, testing the bi-level last train timetable optimization model with a narrow or wide adjustment range of the operation closing time $t_{\mathrm{last},l}^{\mathrm{Dep}}$ is interesting. With a wide adjustment range of the operation closing time, the last train can finish its operation with a high degree of freedom and may lead to more successful transfer directions and successful travel passengers. The adjustment ranges of $t_{\mathrm{sl}}^{\mathrm{Run}}$ and $t_{\mathrm{sl}}^{\mathrm{Stop}}$ are kept constant at $\pm 20$ in the following tests, and the adjustment range of the operation closing time of the last train increases from ±10 to ±50 min. The optimization results with different adjustment ranges of the operation closing time of the last train are shown in Figure 15 and Table 14.

Figure 15.

Optimization results with different adjustment ranges of the operation closing time.

Table 14.

Numbers of successful transfer directions and successful travel passengers with different adjustment ranges of the operation closing time.

Adjustment range	Successful transfer directions	Successful travel passengers
±10 min	90	4929
±20 min	95	6365
±30 min	102	7229
±40 min	106	8310
±50 min	106	8516

As shown in Figure 15 and Table 14, the numbers of successful transfer directions and successful travel passengers increase as the adjustment range of the operation closing time increases from ±10 to ±50 min. Therefore, with a wide adjustment range of the operation closing time, the last train can finish its operation with a high degree of freedom which leads to the increased numbers of successful transfer directions and successful travel passengers.

Train stopping time

Train stopping time is critical for both scheduling and rescheduling problems. ⁴⁵ In our p model, equations (2) and (3) show that the last train timetable is determined by the train stopping time $t_{\mathrm{sl}}^{\mathrm{Stop}}$ subjected to the constraint equation (6). Thus, we test the effect of train stopping times on the optimization results. Specifically, the adjustment range of the operation closing time and train running time are set to ±20 min. The optimization results with different adjustment ranges of the train stopping times are presented in Figure 16 and Table 15.

Figure 16.

Optimization results with different adjustment ranges of train stopping times.

Table 15.

Number of successful transfer directions and successful travel passengers with different adjustment ranges of train stopping times.

Adjustment range	Successful transfer directions	Successful travel passengers
±1 min	96	6365
±2 min	96	6365
±3 min	98	6616
±4 min	100	6846
±5 min	100	6851

As shown in Figure 16 and Table 15, the number of successful transfer directions and successful travel passengers increase as the adjustment range of the train stopping time varies from ±1 to ±5 min. Thus, similar to the conclusion in section “Operation closing time of the last train,” the numbers of successful transfer directions and successful travel passengers will increase with a higher degree of freedom to decide the stopping time.

Discussion on the detour routing strategy

As the analysis before, passengers will select the detour routes in which all transfers are successful even if the routes are circuitous. For the discussion of this phenomenon, “shortest route” and “detour route” are first defined as follows:

• Shortest route. The shortest route which has the minimum total travel time at day time.

• Detour route. The detour route which has longer total travel time than the shortest route and can be selected by passengers only when the shortest route cannot complete their travel.

Figure 17 shows an illustration of the shortest route and detour route for passengers from the origin station on Line 4 to the destination station on Line 10. We listed the number of successful travel passengers who can get to their destination stations by shortest routes and detour routes in Figure 17 and corresponding results of station group pairs.

Figure 17.

Illustration of the shortest and detour routes.

Table 16 reveals that 57% of all passengers (from 63.32% of all station group pairs) could complete their travel under the optimized last train timetable by the detour routes. Therefore, for these passengers, the route guide must be provided to assist the passengers in selecting the detour routes that will allow them to complete their travel. For example, the passengers from Renmindaxue station to Tuanjiehu station usually select the shortest path including a transfer from Line 4 to Line 10 at Haidianhuangzhuang station, which is an unsuccessful transfer direction in the optimized last train timetable. Therefore, the route guide must inform the passengers to select the detour route including two successful transfers (from Line 4 to Line 1 at Xidan station and from Line 1 to Line 10 at Guomao station) to complete their travel.

Table 16.

The number of successful travel passengers (station group pair) who can get to their destination stations by shortest routes and detour routes.

Path	Station group pair		Passenger
	Number	Percent	Number	Percent
Shortest	241	36.68%	2737	43.00%
Detour	416	63.32%	3628	57.00%
Total	657	100%	6365	100%

Conclusion

Urban rail transit is not able and unnecessary to provide 24 h service for passengers, which means the urban rail transit companies need to set a final time for each line. Therefore, the last train timetable optimization is an inevitable and challenging optimization problem to improve the service quality and reduce the operation costs of companies. However, independent transfer optimization cannot guarantee that the majority of the passengers are able to complete their travel by the last train service. Instead, the detour paths should also be taken into consideration as it is passengers’ last chance to reach their destination station via the urban rail transit. In this study, we propose a bi-level last train timetable optimization model. Its upper level model aims to maximize the number of successful travel passengers by the last train service and minimize passenger transfer waiting time of successful transfer directions, and the lower level model aims to determine passenger path choices based on the optimized last train timetable obtained from the upper model.

Genetic algorithm and semi-assignment algorithm are proposed to solve the upper level and lower level model, respectively. The bi-level last train timetable optimization model and the proposed solution approach are tested in a simple urban rail transit network and applied to the Beijing urban rail transit network. The optimization results show that the optimized last train timetable can increase the number of successful travel passengers and minimize the passenger transfer waiting time of successful transfer directions in successful transfer directions. In addition, the information about inaccessible stations from each origin station and corresponding route guide for passengers who need to select a detour route to complete their travel by the last train service can also be offered by the model. These types of information are practically useful for urban rail transit network operation.