Sage Journals: Discover world-class research

Abstract

This article focuses on synchronizing timetables of train services at a rail transfer station. The main aim is to determine an optimal schedule of train services, given that the departure and arrival times of some particular trains are known. An exponential utility function is introduced to measure the synchronization levels between different train services. A nonlinear integer programming model is proposed to achieve the objective of a synchronized timetable. A dynamic programming approach is then designed to solve the developed model. Finally, a numerical example with real-world datasets is implemented to demonstrate the effectiveness of the proposed approaches.

Keywords

Train timetable synchronization optimization dynamic programming approach

Introduction

The main goal of train timetable with synchronization is to ensure feasible and efficient connections between different train services, namely, ensuring the smooth transfer of passengers from one service to another at transfer stations in a railway network. It is clear that the synchronization quality of train services is a crucial concern for both passengers and operational companies. A train timetable with better connections can quickly evacuate the arrival and departure passengers at transfer stations.

Synchronizing timetables for public transit systems has recently received considerable attention. Some early studies considered stochastic environments and set the delay and line headway as the decision variables in their models.^1–3 In contrast, other studies have straightforward viewed the departure and arrival times as the decision variables.^4–10 The primary reason leading to this distinction is that the assumption conditions of these studies (i.e. deterministic and probabilistic conditions) are different. Of course, the headway of line and the arrival and departure times of trains can be converted to each other. Due to reliability and punctuality of passenger train operation, this article also treats the arrival and departure times of each train at the transfer station as decision variables in order to synchronize train timetables.

A proper timetable must concentrate on minimizing the passengers’ waiting time associated with a high-quality train services. Mohring et al.¹¹ found that passengers often perceived their waiting times to be almost twice that of the actual waiting times. Niu et al.^12,13 developed several nonlinear optimization models to minimize the total passenger waiting time based on time-dependent demand for a rail corridor. Of course, a number of existing studies considered the transfer passenger demands to calculate the total transfer waiting time. Liebchen¹⁴ optimized the periodic event-scheduling problem by considering shorter passenger waiting time, at both stops and transfers. Wong et al.⁶ and Kwan and Chang⁷ considered the transfer passengers to be “weights” in an objective function to estimate the passenger transfer time. Hsu¹⁵ formulated a continuous model to calculate the mean passenger transfer waiting time. Recently, Niu et al.¹⁰ calculated the exact total transfer waiting time under the condition of time-varying demand. Furthermore, some papers calculated the approximate passenger transfer waiting time.^3,16,17 To summarize, it is more important to calculate the transfer passenger waiting time in the connection optimization process.

However, it must be noted that the number of transfer passengers can hardly be accurately calculated at a station with several transfer directions. Ceder et al.⁴ assumed that the running time is fixed and proposed a mixed integer linear programming model that aimed at maximizing the number of simultaneous bus arrivals at transfer nodes. On this basis, Ibarra-Rojas et al.⁵ formulated the timetabling problem for a network that aimed to maximize the number of synchronizations to facilitate passenger transfers and avoid bus bunching along the network, and they provided an effective multi-start iterated local search algorithm for the problem. However, these studies are mainly applied to bus scheduling in public transit networks and are rarely used to synchronize train timetables for railway networks.

Combined with the passenger dissatisfaction index in Kwan and Chang,⁷ this article converts the connection slack time (i.e. the time between the arrival time of the feeder train and the departure time of the connecting train) into the level of services for train synchronization. Then, the total level of services of train connections is defined as the optimization objective, which can simultaneously maximize the number of seamless connections and minimize the slack times of all the trains. Without loss of generality, our model can also treat the requirement of the transfer demand by embedding the “weight” of transfer passengers in the objection function, similar to Wong et al.⁶ and Kwan and Chang.⁷

In addition, because connection optimization is a complex task, the synchronizing train timetables in different networks are optimized using special models and algorithms. The example of two lines with a transfer station was studied by Niu et al.¹⁰ Sivakumaran et al.¹⁸ considered an idealized system that delivers its users to a common destination by requiring each transfer from a feeder to a trunk-line vehicle. For reducing transfer time in real time, Chowdhury and Chien¹⁹ optimized dynamic dispatching vehicles at transfer stations by connecting four transit routes. Dou et al.²⁰ researched the coordination between buses and trains. These studies challenged special physical network structures from different perspectives.

For a special transfer station with different grade routes, for instance, at a transfer node with high-speed rail routes and ordinary rail routes, generally speaking, establishing timetables of high-speed trains take precedence over timetables of ordinary trains. Hence, it is completely necessary to develop a model and high-performance algorithm to optimize the synchronizing train timetables for the specific transfer station. The article mainly focuses on the connection relationship at a transfer station. Because train operation conditions are limited, the departure and arrival times of some trains at the transfer station generally cannot be changed, for example, high-speed trains. However, to facilitate passenger transfer, these particular trains also need to be connected by the other trains (e.g. ordinary trains) that have several alternative departure and arrival times. Naturally, the purpose of this article is to schedule the latter trains to connect the special trains.

Although the train timetable with synchronization problem for the public transit system has been studied extensively, we still do a lot of work. First, we describe a connection process between trains in detail and define connecting time windows and feeder time windows. Second, based on the exponential utility, an efficient objective function is established to depict the level of services for train synchronization in the proposed model, which can maximize the number of train seamless connections and minimize the connection slack time. Finally, we design the exact dynamic programming (DP) optimization algorithm to solve this problem and achieve better results.

The remainder of this article is organized as follows. First, we present an analysis for our defined problem in section “Problem statement.” Our developed formulation is presented in section “Optimization model.” In section “DP approach,” DP approach is established to solve the problem. In section “Numerical example,” a numerical example is provided to illustrate the application of the model. Finally, the section “Results” summarizes our results and suggests areas of further research.

Problem statement

As mentioned, it usually occurs that some special trains require connection to other trains at a given transfer station, while the departure and arrival times of all the special trains at the transfer station cannot be changed. To clarify the problem, we refer to these special trains as fixing trains, for example, high-speed trains, running longer-distance trains, and high-load trains which have a higher grade than the others, and the priority will be given to draw up timetables of the fixing trains. Compared to the fixing trains, the lower grade trains are considered as non-fixing trains (e.g. ordinary trains, running shorter distance trains, and low-load trains), namely, the timetables of the fixing trains are predetermined before finishing schedule of the non-fixing trains. Moreover, there are two necessary preconditions that should be known in this study. The first hypothesis is that all trains stop at the transfer station and then traverse it. The other is that the two types of trains stop at independent platforms without operation conflicts.

We use $[0, T]$ to denote the study period; $H = {i | i = 1, 2, 3, \dots, m}$ to indicate the set of fixing trains, $i \in H$ ; and V to represent the set of non-fixing trains, $V = {j | j = 1, 2, 3, \dots, n}$ , $j \in V$ , where m and n are the total number of fixing and non-fixing trains, respectively. $D_{i}$ is used to denote the departure time of the fixing train i at the station, and $A_{i}$ is used to index the arrival time of the train i. As noted above, the departure and arrival times of the fixing trains at the transfer station are pre-specified as input data. Therefore, this article focuses on how to capture the optimal departure and arrival times of the non-fixing trains to synchronize the fixing trains. The key decision variables are defined as follows

$a_{j}$ : Arrival time of the non-fixing train j at the transfer station, $j \in V$ ;

$d_{j}$ : Departure time of the non-fixing train j at the transfer station, $j \in V$ ;

$s_{j}$ : Dwelling time of the non-fixing train j at the transfer station, $s_{j} = d_{j} - a_{j}$ , $j \in V$ .

As shown in Figure 1, the fixing trains stop at platform A and the non-fixing trains stop at platform B. It should be noted that the non-fixing trains with departure times greater than $A_{i + 1} + σ$ and less than T can connect the fixing arrival train $i + 1$ , where $σ$ is a fixed transfer time, which allows the passengers to get off the feeder train and then walk across the transfer aisle to board the connecting train. Each fixing arrival train has a corresponding time window for the non-fixing departure trains to connect, which is referred to as the connecting time window, indexed as $C W_{i}$ , $i \in H$ . The connecting time window can be determined as follows

C W_{i} = [A_{i} + σ, T], i \in H

(1)

Figure 1.

Illustration of the connections at the transfer station.

Similarly, a fixing departure train has a corresponding time window for the non-fixing arrival trains, which is referred to the feeder time window, denoted as $F W_{i}$ , $i \in H$ . In practice, the non-fixing trains that arrive at the transfer station in the feeder time window $F W_{i}$ can be connected by the fixing departure train i. That is to say, the feeder time window is actually the effective arrival time of the non-fixing trains between $D_{i - 1} - σ$ and $D_{i} - σ$ . Except for $F W_{1} = [0, D_{i} - σ]$ , the feeder time window is expressed as follows

F W_{i} = (D_{i - 1} - σ, D_{i} - σ], i \in H \ {1}

(2)

Optimization model

Objective function

We introduce the level of service of train synchronization to measure the connection slack time and the number of connections in this article. To establish the objective function, we define the following

$f (i, j)$ : Level of service of connection from the fixing train i to the non-fixing train j;

$\tilde{f} (j, i)$ : Level of service of connection from the non-fixing train j to the fixing train i;

$α_{i, j}$ : Equal to 1 if the fixing train i is connected by the non-fixing train j; 0 otherwise;

$β_{j, i}$ : Equal to 1 if the non-fixing train j is connected by the fixing train i; 0 otherwise.

Connection from the fixing train to the non-fixing train

As for a fixing arrival train, Wong et al.⁶ supposed that it can be connected by one departure train at most, which is consistent with the hypothesis in this article. Figure 2 shows the sequence of events at the transfer station. Common sense dictates that the fixing arrival train i cannot be connected to the non-fixing train $j - 1$ , which leaves before train i arrives, that is, $d_{j - 1} \notin C W_{i}$ . Although the departure times of train j and $j + 1$ are included in the connecting time window, the only non-fixing train j can connect the fixing train i according to the above assumption.

Figure 2.

Illustration of a connection from a fixing train to a non-fixing train.

Subsequently, we use $μ_{i}$ to index the connecting train of the fixing arrival train i, which can be determined by the following equation

μ_{i} = {\begin{matrix} min_{j \in V} {j | d_{j} \in C W_{i}} & if \exists d_{j} \in C W_{i} \\ 0 & otherwise \end{matrix}, i \in H

(3)

where $μ_{i} = 0$ indicates that none of the non-fixing departure trains can join the arrival train i. The binary variable $α_{i, j}$ is calculated as follows

α_{i, j} = {\begin{matrix} 1 & if j = μ_{i} \\ 0 & otherwise \end{matrix}, i \in H, j \in V

(4)

We use the exponential utility function to reflect the level of services of the connections, which increases with the decrease in the connection slack time and is defined as below

f (i, j) = \exp [- (d_{j} - A_{i} - σ)] \cdot α_{i, j} \cdot p_{i}, i \in H, j \in V

(5)

where $p_{i}$ denotes the number of transfer passengers from the fixing train i to non-fixing train.

Connection from the non-fixing train to the fixing train

For connecting each non-fixing arrival train, we note that the non-fixing trains with arrival times within the feeder time window can connect with the fixing departure train. As shown in Figure 3, the fixing departure train i can join train $j + 1$ and j simultaneously, but cannot connect with train $j - 1$ .

Figure 3.

Illustration of a connection from a non-fixing train to a fixing train.

We use vector $υ_{i}$ to indicate a set of the non-fixing arrival trains connected by the fixing departure train i, which is formulated as below

υ_{i} = {j | a_{j} \in F W_{i}, j \in V}, i \in H

(6)

The binary variable $β_{j, i}$ and the level of service of the connections $\tilde{f} (j, i)$ can be represented as follows

β_{j, i} = {\begin{matrix} 1 & if j \in υ_{i} \\ 0 & otherwise \end{matrix}, i \in H, j \in V

(7)

\tilde{f} (j, i) = \exp [- (D_{i} - a_{j} - σ)] \cdot β_{j, i} \cdot q_{j}, i \in H, j \in V

(8)

where $q_{j}$ denotes the number of transfer passengers from the non-fixing train j to fixing train.

In the above formulation, if $α_{i, j} = 0$ or $β_{j, i} = 0$ , then $f (i, j) = 0$ or $\tilde{f} (j, i) = 0$ ; else $f (i, j) and \tilde{f} (i, j) \in (0, 1]$ . Apparently, if $f (i, j) = 1$ or $\tilde{f} (j, i) = 1$ , a seamless connection is formed between train i and train j. Combined with equation (5) and (8), we can obtain the total level of service for all the trains as follows

max Z = \sum_{i \in H} \sum_{j \in V} [f (i, j) + \tilde{f} (j, i)]

(9)

It should be noted that potential information is hidden in equation (9), that is, the objective function can maximize the number of connections between trains. In this study, given that the departure time of the last non-fixing train is equal to T, the total number of connections depends on the arrival times of the last train. As shown in Figure 4, train m is the last fixing train and train n is the last non-fixing train. Apparently, the connection number in Figure 4(b) is higher than that in (a), and the objective value of that in (b) is higher than that in (a). Therefore, the proposed objective function can simultaneously optimize the connection slack time and the number of connections.

Figure 4.

Example of connection between the last fixing and non-fixing trains.

Constraints

1. The dwelling time $s_{j}$ of the non-fixing train j depends on the departure and arrival times at the transfer station, which must satisfy the maximum and the minimum dwelling time constraints

s_{min} \leq s_{j} \leq s_{max}, j \in V

(10)

where $s_{min}$ and $s_{max}$ denote the minimum and the maximum dwelling times at the transfer station, respectively.

2. To fulfill the service requirements, the departure times of two consecutive trains should satisfy the following inequality (11). Simultaneously, to ensure safe operation conditions, the arrival times must satisfy inequality (12), as shown in Figure 5

I_{min} \leq d_{j + 1} - d_{j} \leq I_{max}, j \in V

(11)

I_{min} \leq a_{j + 1} - a_{j} \leq I_{max}, j \in V

(12)

where $I_{min}$ and $I_{max}$ denote the minimum and the maximum headways between two consecutive trains, respectively.

Figure 5.

Illustration of the time interval constraints for two consecutive trains.

3. When two consecutive trains come into the station, the time gap between the departure time of the last train and the arrival time of the former train is less than the additional minimum safety headway, as shown in Figure 5

a_{j + 1} - d_{j} \geq τ, j \in V

(13)

where $τ$ denotes the fixing time interval to ensure the safe departure and arrival of all non-fixing trains at the station.

4. During the study period $[0, T]$ , the arrival times of each train cannot extend beyond this time horizon. In addition to meeting the above requirement, the arrival times of the first train and the departure time of the last train are limited by the following inequality

I_{max} - a_{1} \geq 0

(14)

d_{n} = T

(15)

DP approach

For synchronizing train timetabling problem, the intelligent heuristic algorithms, such as genetic algorithm and simulated annealing algorithm, are widely applied.^6–10 Although these algorithms are tractable, so far, it is difficult to appraise the quality of solution obtained by these algorithms, especially for large-scale problem. Thus, DP is designed for the proposed nonlinear integer programming model in this article, which is accurate algorithm and can obtain the optimum solution. It is well known that the shortcoming of the DP is curse of dimensionality. However, due to exquisite design in the algorithm, it is fully able to obtain an accurate solution in a short time for our model.

Stage and state

In DP, the state variables of each stage naturally consist of the arrival and departure times of the non-fixing trains. This article sets 1 min as the time unit of the study horizon $[0, T]$ . We use the number of non-fixing trains to denote the stages of the problem.

On the premise of the determining stage, it is essential to analyze the inherent relations of state variables for the two adjacent stages. In this problem, when the arrival and departure times of train $j + 1$ is given, we need to calculate the impossible arrival and departure times of train j. This article uses $T_{a} (j, a_{j + 1})$ to denote the impossible arrival times of the non-fixing train j when the arrival time of train j+1 is known, and $T_{d} (j, a_{j}, a_{j + 1}, d_{j + 1})$ to indicate the impossible departure times of the non-fixing train j when $a_{j}$ , $a_{j + 1}$ , and $d_{j + 1}$ are given.

First, because each non-fixing train is limited by constant time intervals in constraints (10)–(12), the arrival time window, defined as $F_{a} (j)$ , is obtained as below

\begin{matrix} F_{a} (j) = [(j - 1) \cdot I_{min}, j \cdot I_{max}] \cap \\ [T - s_{max} - (n - j) \cdot I_{max}, T - s_{min} - (n - j) \cdot I_{min} \end{matrix}]

(16)

If the arrival time of train j is given, that is, $a_{j} \in F_{a} (j)$ , the departure time window of the train j, denoted by $F_{d} (j, a_{j})$ , can be calculated as follows

F_{d} (j, a_{j}) = [a_{j} + s_{min}, min {T, a_{j} + s_{max}}]

(17)

Second, when the arrival and the departure times of train j+1 are assigned, that is, $a_{j + 1} \in F (j + 1)$ and $d_{j + 1} \in F (j + 1, a_{j + 1})$ , the arrival and departure time windows of train j, denoted by $B_{a} (j, a_{j + 1})$ and $B_{d} (j, a_{j + 1}, d_{j + 1})$ ,respectively, are obtained by the derivation from train j+1 to train j, as shown in Figure 6.

B_{a} (j, a_{j + 1}) = [max {a_{j + 1} - I_{max}, 0}, a_{j + 1} - I_{min}]

(18)

\begin{matrix} B_{d} (j, a_{j + 1}, d_{j + 1}) = [max {d_{j + 1} - I_{max}, 0}, \\ min {d_{j + 1} - I_{min}, a_{j + 1} - τ}] \end{matrix}

(19)

Figure 6.

Illustration of the time windows.

It is clear that $T_{a} (j, a_{j + 1})$ equals to the intersection of $F_{a} (j)$ and $B_{a} (j, a_{j + 1})$ , and that $T_{d} (j, a_{j}, a_{j + 1}, d_{j + 1})$ equals to the intersection of $F_{d} (j, a_{j})$ and $B_{d} (j, a_{j + 1}, d_{j + 1})$ as follows

T_{a} (j, a_{j + 1}) = F_{a} (j) \cap B_{a} (j, a_{j + 1})

(20)

T_{d} (j, a_{j}, a_{j + 1}, d_{j + 1}) = F_{d} (j, a_{j}) \cap B_{d} (j, a_{j + 1}, d_{j + 1})

(21)

For clarifying the above content, a simple case is developed. The number of fixing trains and the non-fixing trains are three and five, respectively. The arrival times of the three fixing trains are 1, 6, and 11, and their departure times are 4, 9, and 14, respectively. The other parameters are $I_{max} = 5$ , $I_{min} = 1$ , $s_{min} = 1$ , $s_{max} = 3$ , $T = 15$ , $τ = 1$ , and $σ = 2$ .

From equation (16), we can calculate the value of $F_{a} (j)$ for the five non-fixing trains as [0, 5], [1, 10], [2, 12], [7, 13], and [12, 14], respectively. For instance, if the departure time and the arrival time of the fifth non-fixing train are 13 and 15, respectively, we can determine that the departure and the arrival time windows of the fourth train are $B_{a} (4, 13) = [8, 12]$ and $B_{d} (4, 13, 15) = [10, 12]$ from equations (18) and (19), respectively. Finally, $T_{a} (4, 13) = [8, 12]$ and $T_{d} (4, 8, 13, 15) = [10, 11]$ , as shown in Figure 7.

Figure 7.

Example of solving the time windows.

Recursion equation

In Figure 8, when the arrival and the departure times of train j+1 are given, we can calculate the arrival and the departures time windows of train j, $T_{a} (j, a_{j + 1})$ and $T_{d} (j, a_{j}, a_{j + 1}, d_{j + 1})$ , according to the above content. Our purpose is to select the optimal arrival and departure times of train j in the time windows $T_{a} (j, a_{j + 1})$ and $T_{d} (j, a_{j}, a_{j + 1}, d_{j + 1})$ , respectively. We suppose time k and $\bar{k}$ are the best arrival and departure times of the non-fixing train j, which are represented as follows.

\bar{k} = \underset{d_{j} \in T_{d} (j, k, a_{j + 1}, d_{j + 1})}{\arg max} {\sum_{i \in H} f (i, j)}

(22)

\begin{matrix} k = \underset{a_{j} \in T_{d} (j, a_{j + 1})}{\arg max} \\ {Z (j, a_{j}, d_{j}) + \sum_{i \in H} \tilde{f} (j, i) + max_{d_{j} \in T_{d} (j, a_{j}, a_{j + 1}, d_{j + 1})} {\sum_{i \in H} f (i, j)}} \end{matrix}

(23)

Figure 8.

Illustration of the transmitting state variables in adjacent stages.

where $Z (j, a_{j}, d_{j})$ is an evaluation function, which also denotes the optimal value of the total level of services of train connections. We can calculate the marginal evaluation function increase as $\sum_{i \in H} \tilde{f} (j, i) + max_{d_{j} \in T_{d} (j, a_{j}, a_{j + 1}, d_{j + 1})} {\sum_{i \in H} f (i, j)}$ from $Z (j, a_{j}, d_{j})$ to $Z (j + 1, a_{j + 1}, d_{j + 1})$ .

By assuming that the initial state is $j = 0$ and $Z (0, a_{0}, d_{0}) = 0$ , the recursive equation is established as follows

\begin{matrix} Z (j + 1, a_{j + 1}, d_{j + 1}) = max_{a_{j} \in T_{d} (j, a_{j + 1})} \\ {Z (j, a_{j}, d_{j}) + \sum_{i \in H} \tilde{f} (j, i) + max_{d_{j} \in T_{d} (j, a_{j}, a_{j + 1}, d_{j + 1})} {\sum_{i \in H} f (i, j)}} \end{matrix}

(24)

Algorithm procedure

Input: the data and parameters are

A_{i}, D_{i}, I_{min}, I_{max}, τ, s_{min}, s_{max}, σ

Output: the departure and the arrival times of non-fixing trains

a_{j}, d_{j}

Step 1: (Initialization)

Initialize

Z (j + 1, a_{j + 1}, d_{j + 1}) = 0

Zd (j + 1, a_{j}, a_{j + 1}, d_{j + 1}) = 0

;

Step 2: (Recursive)

For (

j = 1 to n

) do

For (

a_{j + 1} \in F_{a} (j + 1))

) do

For (

d_{j + 1} \in F_{d} (j + 1, a_{j + 1})

) do

For (

a_{j} \in T_{a} (j, a_{j + 1})

) do

For (

d_{j} \in T_{d} (j, a_{j}, a_{j + 1}, d_{j + 1})

) do

Zd' (j + 1, a_{j}, a_{j + 1}, d_{j + 1}) \leftarrow \sum_{i \in H} f (i, j)

If (

Zd' (j + 1, a_{j}, a_{j + 1}, d_{j + 1}) > Zd (j + 1, a_{j}, a_{j + 1}, d_{j + 1})

) then

Zd (j + 1, a_{j}, a_{j + 1}, d_{j + 1}) \leftarrow Zd' (j + 1, a_{j}, a_{j + 1}, d_{j + 1})

Record processor

pd (j + 1, a_{j}, a_{j + 1}, d_{j + 1}) \leftarrow d_{j}

End if

End for //

d_{j}

Z' (j + 1, a_{j + 1}, d_{j + 1}) \leftarrow Z (j, a_{j}, d_{j}) + \sum_{i \in H} \tilde{f} (j, i) + Zd (j + 1, a_{j}, a_{j + 1}, d_{j + 1})

If (

Z' (j + 1, a_{j + 1}, d_{j + 1}) > Z (j + 1, a_{j + 1}, d_{j + 1})

) then

Z (j + 1, a_{j + 1}, d_{j + 1}) \leftarrow Z' (j + 1, a_{j + 1}, d_{j + 1})

Record processor

pa (j + 1, a_{j + 1}, d_{j + 1}) \leftarrow a_{j}

End if

End for //

a_{j}

End for //

d_{j + 1}

End for //

a_{j + 1}

End for // j

Step 3: (Retrieve optimal solution)

For (

j = n

to 1) do

The optimal arrival time of train j is

pa (j + 1, a_{j + 1}, d_{j + 1})

;

temp \leftarrow pa (j + 1, a_{j + 1}, d_{j + 1})

;

The optimal departure time of train j is

pd (j + 1, temp, a_{j + 1}, d_{j + 1})

;

Output the optimal arrival and departure times of all the non-fixing trains.

End for // j

To verify the validity of the algorithm, we calculate the above example using the DP approach, for which the optimal schedule is obtained, as shown in Figure 9; its objection value is 6.14. The connection relationship of each train is expressed in this figure, in which (H1→V1):1.00 means that the objective value of the train connection is 1 (i.e. seamless connection) from the first fixing train to the first non-fixing train.

Figure 9.

An illustration of the timetable synchronization of simple example.

Numerical example

Input data

In this section, there are 56 fixing trains and 60 non-fixing trains traversing a transfer station in the study horizon from 6:30 to 21:30. The maximum and the minimum headways for the non-fixing trains at the station are 25 and 5 min, respectively; the maximum and the minimum dwelling times are 10 and 2 min, respectively. The additional minimum safety headway of trains coming into the station is 5 min. The time for passengers to walk across the interchange platform $σ$ is 10 min. Furthermore, we assume that the departure and arrival times of the fixing trains are known as shown in Table 1, and the weights of the transfer passengers are equal to 1.

Table 1.

Arrival and departure times of all fixing trains at the transfer station.

Trains	Arrival time	Departure time	Trains	Arrival time	Departure time	Trains	Arrival time	Departure time	Trains	Arrival time	Departure time
1	6:50	6:54	15	9:50	9:58	29	13:40	13:48	43	18:20	18:24
2	7:10	7:14	16	10:00	10:08	30	13:55	14:03	44	18:30	18:38
3	7:30	7:34	17	10:10	10:18	31	14:10	14:18	45	18:40	18:48
4	7:45	7:49	18	10:30	10:34	32	14:30	14:38	46	18:50	18:58
5	8:00	8:04	19	10:50	10:54	33	14:50	14:58	47	19:00	19:08
6	8:15	8:19	20	11:10	11:14	34	15:10	15:18	48	19:10	19:18
7	8:30	8:34	21	11:30	11:34	35	15:40	15:44	49	19:20	19:28
8	8:40	8:48	22	11:50	11:54	36	16:10	16:14	50	19:30	19:38
9	8:50	8:58	23	12:10	12:14	37	16:40	16:44	51	19:40	19:48
10	9:00	9:08	24	12:25	12:33	38	17:10	17:14	52	19:50	19:58
11	9:10	9:18	25	12:40	12:48	39	17:25	17:29	53	20:05	20:13
12	9:20	9:28	26	12:55	13:03	40	17:40	17:44	54	20:20	20:28
13	9:30	9:38	27	13:10	13:18	41	17:55	17:59	55	20:35	20:43
14	9:40	9:48	28	13:25	13:33	42	18:10	18:14	56	20:50	20:58

Results

Through the DP approach to solve this example, the best departure and arrival times of all the non-fixing trains are obtained as shown in Table 2, during 420.51 s of computational time by C++ language programming on a workstation of Inter Core E5-2609 with 2.50 GHz and 32GB RAM.

Table 2.

Optimal arrival and departure times of all non-fixing trains.

Trains	Arrival time	Departure time	Trains	Arrival time	Departure time	Trains	Arrival time	Departure time	Trains	Arrival time	Departure time
1	6:55	7:00	16	10:08	10:10	31	14:28	14:30	46	18:28	18:30
2	7:18	7:20	17	10:24	10:26	32	14:48	14:55	47	18:38	18:40
3	7:39	7:41	18	10:44	10:46	33	15:13	15:20	48	18:48	18:50
4	7:54	7:56	19	11:04	11:06	34	15:34	15:36	49	18:58	19:00
5	8:09	8:11	20	11:24	11:26	35	15:48	15:50	50	19:08	19:10
6	8:24	8:26	21	11:44	11:46	36	16:04	16:06	51	19:18	19:20
7	8:38	8:40	22	12:04	12:06	37	16:18	16:20	52	19:28	19:30
8	8:48	8:50	23	12:23	12:25	38	16:34	16:36	53	19:38	19:40
9	8:58	9:00	24	12:38	12:40	39	16:48	16:50	54	19:48	19:50
10	9:08	9:10	25	12:53	12:55	40	17:04	17:06	55	20:03	20:05
11	9:18	9:20	26	13:08	13:10	41	17:19	17:21	56	20:18	20:20
12	9:28	9:30	27	13:23	13:25	42	17:34	17:36	57	20:33	20:35
13	9:38	9:40	28	13:38	13:40	43	17:49	17:51	58	20:48	20:50
14	9:48	9:50	29	13:53	13:55	44	18:04	18:06	59	21:03	21:05
15	9:58	10:00	30	14:08	14:10	45	18:14	18:20	60	21:28	21:30

From Table 2, we can easily summarize the relationships of connections between the non-fixing trains to the fixing trains, as shown in Table 3, where WT denotes the transfer waiting time, V1 is the first non-fixing train, H2 indicates the second fixing train, V1→H2 is the connection from the first non-fixing train to the second fixing train, and V60→∅ denotes that the 60th non-fixing train is not connected by any fixing trains. It should be noted that the total number of connections is 114 and the number of seamless connections (i.e. WT = 0) is 80 in Table 3. Because the seamless connection dominates in the optimum solution, that is to say, the proposed method is effective for this problem.

Table 3.

Relationships of connections between the non-fixing trains to the fixing trains.

From the non-fixing trains to the fixing trains						From the fixing trains to the non-fixing trains
Connection	WT	Connection	WT	Connection	WT	Connection	WT	Connection	WT	Connection	WT
V1→H2	9	V21→H22	0	V41→H39	0	H1→V1	0	H20→V20	6	H39→V42	1
V2→H3	6	V22→H23	0	V42→H40	0	H2→V2	0	H21→V21	6	H40→V43	1
V3→H4	0	V23→H24	0	V43→H41	0	H3→V3	1	H22→V22	6	H41→V44	1
V4→H5	0	V24→H25	0	V44→H42	0	H4→V4	1	H23→V23	5	H42→V45	0
V5→H6	0	V25→H26	0	V45→H43	0	H5→V5	1	H24→V24	5	H43→V46	0
V6→H7	0	V26→H27	0	V46→H44	0	H6→V6	1	H25→V25	5	H44→V47	0
V7→H8	0	V27→H28	0	V47→H45	0	H7→V7	0	H26→V26	5	H45→V48	0
V8→H9	0	V28→H29	0	V48→H46	0	H8→V8	0	H27→V27	5	H46→V49	0
V9→H10	0	V29→H30	0	V49→H47	0	H9→V9	0	H28→V28	5	H47→V50	0
V10→H11	0	V30→H31	0	V50→H48	0	H10→V10	0	H29→V29	5	H48→V51	0
V11→H12	0	V31→H32	0	V51→H49	0	H11→V11	0	H30→V30	5	H49→V52	0
V12→H13	0	V32→H33	0	V52→H50	0	H12→V12	0	H31→V31	10	H50→V53	0
V13→H14	0	V33→H35	21	V53→H51	0	H13→V13	0	H32→V32	15	H51→V54	0
V14→H15	0	V34→H35	0	V54→H52	0	H14→V14	0	H33→V33	20	H52→V55	5
V15→H16	0	V35→H36	16	V55→H53	0	H15→V15	0	H34→V33	0	H53→V56	5
V16→H17	0	V36→H36	0	V56→H54	0	H16→V16	0	H35→V35	0	H54→V57	5
V17→H18	0	V37→H37	6	V57→H55	0	H17→V17	6	H36→V37	0	H55→V58	5
V18→H19	0	V38→H37	0	V58→H56	0	H18→V18	6	H37→V39	0	H56→V59	5
V19→H20	0	V39→H38	16	V59→∅	–	H19→V19	6	H38→V41	1
V20→H21	0	V40→H38	0	V60→∅	–

To further verify the effectiveness of the proposed model and algorithm, this article compares the DP and regular connection plan in Table 4, which has even departure and constant dwelling times of 5 min for each non-fixing train. We can see that the objective value and the average dwelling time associated with the designed plan are much better than the regular plan.

Table 4.

Comparison of the different schedules.

Schedule	Objective	Number of connections	Average dwelling time (min)
Designed plan	81.05 (100%)	114 (100%)	2.28 (100%)
Regular plan	13.55 (16.72%)	114 (100%)	5.00 (219.30%)

Conclusion

This study formulated a nonlinear integer programming model to synchronize the fixing trains and the non-fixing trains at a transfer station. In order to clarify the problem, the connecting time window and the feeder time window are introduced in the model. An exponential utility function is adopted as the objective function to measure the level of the train connection quality, which can ensure the maximum number of seamless connection and the minimum transfer waiting time. For generating accurate solution in shorter time, the DP approach is designed to solve the proposed model, and its effectiveness is verified by a real-world example. Moreover, further research should consider several transfer stations in a railway network to optimize the timetable synchronization and design a more efficient optimization algorithm.

Footnotes

Academic Editor: Xiaobei Jiang

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: The work described in this paper was supported by the National Natural Science Foundation of China (grant no. 71261014).

References

Hall

RW.

Vehicle scheduling at a transportation terminal with random delay en route. Transport Sci 1985; 19: 308–320.

Lee

Schonfeld

Optimal slack time for timed transfers at a transit terminal. J Adv Transport 1991; 25: 281–308.

Teodorović

Lučić

Schedule synchronization in public transit using the fuzzy ant system. Transport Plan Techn 2005; 28: 47–76.

Ceder

Golany

Tal

Creating bus timetables with maximal synchronization. Transport Res A 2001; 35: 913–928.

Ibarra-Rojas

Rios-Solis

YA.

Synchronization of bus timetabling. Transport Res B 2012; 46: 599–614.

Wong

Yuen

Fung

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

Kwan

Chang

Timetable synchronization of mass rapid transit system using multi-objective evolutionary approach. IEEE T Syst Man Cy C 2008; 38: 636–648.

Kang

Sun

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

Zhou

Deng

Xie

. Coordination optimization of the first and last trains’ departure time on urban rail transit network. Adv Mech Eng 2013; 5: 848292.

10.

Niu

Tian

Zhou

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

11.

Mohring

Schroeter

Wiboonchuikula

The values of waiting time, travel times, and a seat on a bus. Rand J Econ 1987; 18: 40–56.

12.

Niu

Zhou

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

13.

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 2015; 76: 117–135.

14.

Liebchen

The first optimized railway timetable in practice. Transport Sci 2008; 42: 420–435.

15.

Hsu

SC.

Determinants of passenger transfer waiting time at multi-modal connecting stations. Transport Res E 2010; 46: 404–413.

16.

Shafahi

Khani

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

17.

Guo

Wilson

Assessing the cost of transfer inconvenience in public transport systems: a case study of the London underground. Transport Res A 2011; 45: 91–104.

18.

Sivakumaran

Cassidy

. Cost-saving properties of schedule coordination in a simple trunk-and-feeder transit system. Transport Res A 2012; 46: 131–139.

19.

Chowdhury

Chien

Dynamic vehicle dispatching at the intermodal transfer station. Transp Res Record 2001; 1753: 61–68.

20.

Dou

Meng

Guo

Bus schedule coordination for the last train service in an intermodal bus-and-train transport network. Transport Res C 2015; 60: 360–376.

A dynamic programming approach to synchronize train timetables

Abstract

Keywords

Introduction

Problem statement

Optimization model

Objective function

Connection from the fixing train to the non-fixing train

Connection from the non-fixing train to the fixing train

Constraints

DP approach

Stage and state

Recursion equation

Algorithm procedure

Numerical example

Input data

Results

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References