# Combinatorial Optimization of Service Order and Overtaking for Demand-Oriented Timetabling in a Single Railway Line

Authors: Dewei Li; Shishun Ding; Yizhen Wang
Journal: Journal of Advanced Transportation
 (2018)

---

## Abstract

Train timetabling is crucial for passenger railway operation. Demand-oriented train timetable optimization by minimizing travel time plays an important role in both theory and practice. Most of the current researches of demand-oriented timetable models assume an idealized situation in which the service order is fixed and in which zero overtaking exists between trains. In order to extend the literature, this paper discusses the combinatorial effect of service order and overtaking by developing four mixed-integer quadratic programming timetabling models with different service order as well as overtaking conditions. With the objective of minimizing passengers’ waiting time and in-vehicle time, the models take five aspects as constraints, namely dwell time, running time, safety interval, overtaking, and capacity. All four models are solved by ILOG CPLEX; and the results, which are based on Shanghai-Hangzhou intercity high-speed rail data, show that either allowing overtaking or changing service order can effectively optimize the quality of timetable with respect to reducing the total passengers’ travel time. Although optimizing train overtaking and service order simultaneously can optimize the timetable more significantly, compared to overtaking, allowing the change of service order can help passengers save total travel time without extending the train travel time. Moreover, considering the computation effort, satisfying both of the conditions in the meantime, when optimizing timetable has not got a good cost benefit.


---

## Body

## 1. Introduction

Railway timetabling is the basis for train operation, whose quality affects the service level and the efficiency of the whole network. In the form of timetables, the railway operators provide access to their transport products for consumers; passengers then choose the appropriate train according to the schedule. The quality of the train schedule determines whether the passengers are satisfied with the train service, which influences the railway operators’ competitiveness in the passenger transportation market. However, it is quite difficult to design a timetable that can meet the needs of both operators and passengers; thus, the train timetabling problem has attracted much attention from researchers over the past few decades.


### 1.1. Literature Review

Railway timetabling has been widely addressed by providing a closed analytical form for determining the involved time rates, e.g., travel times, dwell times [1], inversion times, buffer times [2], reserve times, and layover times [3]. Besides, some researchers have studied the problem of train timetable optimization to improve its performance by considering stop-skipping [4–6], overtaking, and service scheduling [7, 8].Many researchers have studied the problem from the perspective of railway operators; meanwhile, various train schedule optimization models have been established to minimize the total travel time of all trains in a system. Two kinds of timetables have been studied in this literature, namely, cyclic timetables and noncyclic timetables.Most studies on cyclic train timetables are based on the Periodic Event Scheduling Problem (PESP) model that was put forward by Serafini and Ukovich [9]. In 1993, Voorhoeve [10] first provided a PESP-based model that takes into account the main operating constraints, such as dwell time, running time, and safety headway. Odijk [11] designed a cutting plane algorithm to solve the PESP model. This method can quickly obtain the train timetable of a small railway network. In addition, some researchers [12, 13] transformed the PESP model into the Cycle Periodicity Formulation (CPF) model, which can reduce the number of constraints and variables. A stochastic optimization model was developed by Kroon [14] to allocate the time supplements and buffer times in a given cyclic timetable to enhance the robustness of the timetable. Liebchen [15] integrated many nonstandard requirements and other planning phases into PESP. Caimi [16, 17] developed a timetable model with partial periodicity. Zhou [18] modeled the multiperiodic train timetabling problem to simultaneously optimize operation periods, arrival times, and departure times of various types of trains of all periods. A cyclic train timetable is easier and more convenient for passengers to remember exactly the arrival times and the departure times. However, a cyclic timetable is not sensitive to irregular passengers’ demand, which can result in long waiting time under low frequency and a waste of capacity under high frequency.With regard to the noncyclic train timetabling problem, Szpigel [19] first studied the optimal train scheduling problem on a single line track and presented a linear programming model originally based on job-shop scheduling problem to minimize the total travel time, while the best crossing and overtaking positions are determined. The problem is proved to be NP-hard by Cai [20] and Caprara [21], so it is difficult to obtain the optimal solution, especially for large-scale cases. In Carey [22], total service running time was the objective, and binary variables were used to describe the precedence between service. Higgins [23] provided a lower bound that allows the branch-and-bound algorithm to find the optimal solution of complex instances in a reasonable time. Lindner [24] developed a timetable model by minimizing the total operation cost. In order to find the suboptimal solution, Zhou and Zhong [25] developed a bi-criteria train scheduling model. With effective dominance rules, utility evaluation rules, and a beam search algorithm, the train scheduling model considered the acceleration and deceleration times and solved by a branch-and-bound algorithm. Caprara [26] designed train timetables. The train timetables took into account several additional constraints, which arose in real-world applications and provided a Lagrangian heuristic algorithm for real-world instances. Zhou and Zhong [27] studied a single-track train timetabling problem, aiming to minimize the total travel time. They proposed lower bound rules and heuristic upper bound construction methods to improve computational performance. Cacchiani [28] proposed a column generation approach to solve train timetabling problem. R.L. Burdett [29] extended a discrete sequencing approach for train scheduling, considering multiple overtaking conflicts and compound moves. Corman [30] described a train dispatching support tool to manage more saturated railway networks by changing dwell times and train orders and routes. Cordone [31] proposed a mixed-integer nonlinear model with a nonconvex continuous relaxation. In the same year, to construct a feasible NWBPMJSS train schedule, satisfying the blocking and no-wait constraints in job-shop environments, Liu [32] proposed a two-stage hybrid heuristic algorithm. Canca [33] proposed a tactical model to determine optimal policies of short-turning and nonstopping at certain stations, considering the objective of minimizing the arrival times of the last shuttle. Kroon [34] dealt with connection problem in cyclic passenger railway timetabling. Fröidh [35] discussed how different dwell times and skip-stop operation affected capacity. To minimize delays after an unexpected event perturbs the operations, Pellegrini et al. [36] proposed a mixed-integer linear model for the real-time railway traffic management problem and represented the infrastructure with fine granularity. Considering the stopping and skipping stations for skip-stop rail operation, Lee et al. [37] proposed a mathematical model; and a Genetic Algorithm is used to solve the model. Chen [38] integrated optimization of train service headways and stop-skipping strategy to improve the operation efficiency and service quality of a BRT system. He also proposed a genetic algorithm to solve the problem. Castillo et al. [39] presented a time partition technique to reduce the complexity of the problem. Liu [40] considered different kinds of headway time; an integer linear programming and a branch and price algorithm are proposed to optimize the timetable.In recent years, passenger demand for service quality has grown ever higher, while the supply capacity of rail service operators has increased as well. Therefore, some researchers focus on the dynamic passenger demand and construct models to maximize the benefit of passengers.In [41] and [42], Niu studied the time-dependent characteristics of passenger demand and formulated a timetabling model under oversaturated conditions to minimize passenger waiting times at stations. A local improvement algorithm was presented to find the optimal timetables for individual stations and a genetic algorithm was provided to solve the whole line problem. Barrena [43] discretized the time horizon and assumed that the arrival of passengers in each small interval is subject to a uniform distribution. A nonlinear programming model was formulated and solved by branch-and-bound algorithm. The algorithm is insufficient to solve the large-scale case, so Barrena [44] introduced Riemann’s sum theory to calculate the passenger waiting time and developed a simulated annealing algorithm to solve large instances of the problem within short computation times. Sun [45] proposed the concept of equivalent time to synchronize train operations and passenger demand, then he provided a mixed-integer programming model that allows for train capacity constraints in order to design demand-driven timetables for metro services. The capacitated metro service timetabling problem can simply be solved by CPLEX. Canca [46] presented a nonlinear integer programming model to meet the dynamic passenger demand; this model can also be used to measure the timetable quality and to offer the service provider a trade-off between service quality and operational cost. Niu [5] considered time-dependent demand and skip-stop patterns; a nonlinear integer programming model with quadratic and quasi-quadratic objective functions was proposed to compute the total passenger waiting time under both minute-dependent demand and hour-dependent demand. However, the above studies only considered passenger waiting time at stations; the in-vehicle travel time is ignored. Wang [47, 48] proposed a nonlinear nonconvex model, the objective function of which is total energy consumption and total passenger travel time. A set of possible approaches is used to solve the model. Besides, the iterative convex programming approach is proved to provide a better trade-off between the quality of solution and computational time. Xu [49] proposed a multiobjective timetable optimization approach to minimize the passenger time and energy consumption. Robenek et al. [50, 51] proposed the Elastic Passenger Centric Train Timetabling Problem (EPCTTP) model with the objective of maximizing the train operating company’s revenue. Robenek [52] proposed a hybrid timetable combining the benefits of cyclic and demand-oriented timetables. Hassannayebi et al. [53] applied an adaptive and variable neighborhood search algorithm to optimize the train timetable problem. Yin [54] developed a timetable optimizing model, considering the dynamic passenger demands and energy saving objective. A Lagrangian relaxation-based heuristic algorithm is proposed to solve the model. Zhang [6] considered flexible skip-stop scheme and proposed a mixed-integer nonlinear programming model to minimize the average passenger travel time. Shen [55] and Zhang [56] proposed timetabling model to minimize the passenger travel time under congestion conditions. Liu [57] considered joint routing and scheduling between freight and passenger trains and proposed a model to study the robust passenger train timetable. A branch-and-bound framework with hybrid heuristics is used to solve the model. A systematic comparison among the typical existing studies is shown in Table 1.Table 1
Overview of existing demand-oriented timetabling models.
Model
Type
Objective
Unset Serviceorder
Overtaking allowed
Skipstop
Algorithm
Niu [42]
Non-linear
AWT
×
×
×
Genetic Algorithm
Barrena [43]
linear
AWT
×
×
×
Branch-and-cut
Barrena [44]
Non-linear
AWT
×
×
×
Adaptive large neighborhood search
Shang [58]
Non-linear
TTT
×
×
×
Branch and bound
Sun [45]
MIP
AWT
×
×
×
Branch and bound
Canca [46]
Non-linear
AWT and Operational benefit
×
×
×
Branch and bound
Niu [5]
Non-linear
AWT
×
×
√
Branch and bound
Wang [47]
Non-linear Non-convex
TTT and energy
×
×
×
Iterative convex programming
Wang [48]
Non-linear Non-convex
AWT
×
×
×
Sequential quadratic programming
Yin [59]
Stochastic
TTT and train operational costs
×
×
×
Approximate dynamic programming
Note: AWT = average passenger waiting time; TTT = total passenger travel time.
×: not considered in the model; √: considered in the model.Table1 shows that all of the timetable models are based on dynamic passenger demand in the existing literature. In summary, all models fix the service order and do not allow trains to overtake one another. These assumptions are made to simplify the model; however, they create certain drawbacks to this approach.First, the assumption of fixed service order or zero overtaking can lead to more travel time of passengers, especially when there are more than one stop plan for trains. Taking Figure1 as an example, there are three stations on a railway line, represented as Station 1, Station 2, and Station 3, respectively; there are three trains, Train 1, Train 2, and Train 3, which is a stop train, a nonstop train, and a stop train, respectively. The given service order is shown in Figure 1(a). The time-dependent OD matrix is shown in Table 2. The original timetable can satisfy passenger demand. However, we can see from the OD matrix that there are some long-distance travelers between stations 1 and 3 at the second minute and some short-distance travelers between stations 2 and 3 at the fourth minute. If Train 2 overtakes Train 1 at Station 2 (Figure 1(b)), passengers’ waiting time will decrease. From the OD matrix, we also notice that there are many long-distance travelers between stations 1 and 3 at the fourth minute. If we change the service order (Figure 1(c)), passengers’ in-vehicle time will decrease. Moreover, if overtaking and variable service order is permitted simultaneously (Figure 1(d)), passengers’ in-vehicle time and passengers’ waiting time will decrease. Detailed results of each situation are shown in Table 3. Obviously, variable service order and overtaking are necessary to reduce total travel time. If one optimizes the timetable with the given order and there is not any overtaking, it is difficult to obtain a satisfactory solution. As the number of trains increases, and the number of combinations of service orders and overtaking becomes much larger, the gap between the obtained solution and the real optimal timetable can be expected to widen.Table 2
Passenger demand.
OD
Time
1
2
3
4
5
6
7
Total
1-2
30
0
0
0
0
0
0
30
2-3
0
0
10
20
0
0
0
30
1-3
10
20
0
50
0
0
0
80Table 3
The result of each situation.
Fixed order, zero overtaking
Fixed order, allowing overtaking
Variable order, zero overtaking
Variable order, allowing overtaking
Passengers’ waiting time
60
10
100
60
Passengers’ in-vehicle time
280
290
200
220
Passengers’ travel time
340
300
300
280Figure 1
Illustration of timetable.
(a)
(b)
(c)
(d)Second, the assumption of zero overtaking can cause infeasible solutions of the model to be obtained for large-scale instances. When dealing with large numbers of trains, for example, the trains cannot be assigned within the given time period due to the capacity problem.In order to overcome the two drawbacks mentioned above, this paper provides a mixed-integer quadratic programming model, in which the train departure order at the origin station is not defined in advance and overtaking is allowed for any pair of trains. The model takes the dwell time, running time, safety interval, overtaking, and capacity as constraints, with the objective of minimizing the sum of passengers’ waiting time and in-vehicle time.The remainder of this paper is structured as follows. Section2 describes the problem and some basic assumptions; Section 3 presents four models based on the combinatorial condition of service order and train overtaking, as shown in Table 4. The passenger demand for the Shanghai-Hangzhou intercity high-speed rail provides the input data for the proposed models and the computational results are compared in Section 4. Sensitivity analysis is shown in Section 5. We discuss the passenger delays and the train robustness in Section 6. We conclude with the paper’s main contributions and propose the problems that need to be further investigated.Table 4
Combinational conditions of different models presented in this paper.
Service order
Train overtaking
Zero overtaking
Allowing overtaking
Fixed order
Model M1
Model M2
Variable order
Model M3
Model M4


### 1.2. Main Contribution

To the best of our knowledge, many demand-oriented timetable models have been developed. Besides, stop-skipping conditions have been considered in some of the models [5, 6]. However, the combinatorial influence of train service order and overtaking condition on the timetabling is not fully elucidated in these existing studies. Through the illustration, we can find that changing train service order and overtaking condition exactly reduces the passengers’ total travel time. Therefore, this paper tries to fill this gap by comprehensively investigating the timetabling with different operating conditions, e.g., the fixed order with zero overtaking, the variable order with zero overtaking, the fixed order with overtaking, and the variable order with overtaking.


## 1.1. Literature Review

Railway timetabling has been widely addressed by providing a closed analytical form for determining the involved time rates, e.g., travel times, dwell times [1], inversion times, buffer times [2], reserve times, and layover times [3]. Besides, some researchers have studied the problem of train timetable optimization to improve its performance by considering stop-skipping [4–6], overtaking, and service scheduling [7, 8].Many researchers have studied the problem from the perspective of railway operators; meanwhile, various train schedule optimization models have been established to minimize the total travel time of all trains in a system. Two kinds of timetables have been studied in this literature, namely, cyclic timetables and noncyclic timetables.Most studies on cyclic train timetables are based on the Periodic Event Scheduling Problem (PESP) model that was put forward by Serafini and Ukovich [9]. In 1993, Voorhoeve [10] first provided a PESP-based model that takes into account the main operating constraints, such as dwell time, running time, and safety headway. Odijk [11] designed a cutting plane algorithm to solve the PESP model. This method can quickly obtain the train timetable of a small railway network. In addition, some researchers [12, 13] transformed the PESP model into the Cycle Periodicity Formulation (CPF) model, which can reduce the number of constraints and variables. A stochastic optimization model was developed by Kroon [14] to allocate the time supplements and buffer times in a given cyclic timetable to enhance the robustness of the timetable. Liebchen [15] integrated many nonstandard requirements and other planning phases into PESP. Caimi [16, 17] developed a timetable model with partial periodicity. Zhou [18] modeled the multiperiodic train timetabling problem to simultaneously optimize operation periods, arrival times, and departure times of various types of trains of all periods. A cyclic train timetable is easier and more convenient for passengers to remember exactly the arrival times and the departure times. However, a cyclic timetable is not sensitive to irregular passengers’ demand, which can result in long waiting time under low frequency and a waste of capacity under high frequency.With regard to the noncyclic train timetabling problem, Szpigel [19] first studied the optimal train scheduling problem on a single line track and presented a linear programming model originally based on job-shop scheduling problem to minimize the total travel time, while the best crossing and overtaking positions are determined. The problem is proved to be NP-hard by Cai [20] and Caprara [21], so it is difficult to obtain the optimal solution, especially for large-scale cases. In Carey [22], total service running time was the objective, and binary variables were used to describe the precedence between service. Higgins [23] provided a lower bound that allows the branch-and-bound algorithm to find the optimal solution of complex instances in a reasonable time. Lindner [24] developed a timetable model by minimizing the total operation cost. In order to find the suboptimal solution, Zhou and Zhong [25] developed a bi-criteria train scheduling model. With effective dominance rules, utility evaluation rules, and a beam search algorithm, the train scheduling model considered the acceleration and deceleration times and solved by a branch-and-bound algorithm. Caprara [26] designed train timetables. The train timetables took into account several additional constraints, which arose in real-world applications and provided a Lagrangian heuristic algorithm for real-world instances. Zhou and Zhong [27] studied a single-track train timetabling problem, aiming to minimize the total travel time. They proposed lower bound rules and heuristic upper bound construction methods to improve computational performance. Cacchiani [28] proposed a column generation approach to solve train timetabling problem. R.L. Burdett [29] extended a discrete sequencing approach for train scheduling, considering multiple overtaking conflicts and compound moves. Corman [30] described a train dispatching support tool to manage more saturated railway networks by changing dwell times and train orders and routes. Cordone [31] proposed a mixed-integer nonlinear model with a nonconvex continuous relaxation. In the same year, to construct a feasible NWBPMJSS train schedule, satisfying the blocking and no-wait constraints in job-shop environments, Liu [32] proposed a two-stage hybrid heuristic algorithm. Canca [33] proposed a tactical model to determine optimal policies of short-turning and nonstopping at certain stations, considering the objective of minimizing the arrival times of the last shuttle. Kroon [34] dealt with connection problem in cyclic passenger railway timetabling. Fröidh [35] discussed how different dwell times and skip-stop operation affected capacity. To minimize delays after an unexpected event perturbs the operations, Pellegrini et al. [36] proposed a mixed-integer linear model for the real-time railway traffic management problem and represented the infrastructure with fine granularity. Considering the stopping and skipping stations for skip-stop rail operation, Lee et al. [37] proposed a mathematical model; and a Genetic Algorithm is used to solve the model. Chen [38] integrated optimization of train service headways and stop-skipping strategy to improve the operation efficiency and service quality of a BRT system. He also proposed a genetic algorithm to solve the problem. Castillo et al. [39] presented a time partition technique to reduce the complexity of the problem. Liu [40] considered different kinds of headway time; an integer linear programming and a branch and price algorithm are proposed to optimize the timetable.In recent years, passenger demand for service quality has grown ever higher, while the supply capacity of rail service operators has increased as well. Therefore, some researchers focus on the dynamic passenger demand and construct models to maximize the benefit of passengers.In [41] and [42], Niu studied the time-dependent characteristics of passenger demand and formulated a timetabling model under oversaturated conditions to minimize passenger waiting times at stations. A local improvement algorithm was presented to find the optimal timetables for individual stations and a genetic algorithm was provided to solve the whole line problem. Barrena [43] discretized the time horizon and assumed that the arrival of passengers in each small interval is subject to a uniform distribution. A nonlinear programming model was formulated and solved by branch-and-bound algorithm. The algorithm is insufficient to solve the large-scale case, so Barrena [44] introduced Riemann’s sum theory to calculate the passenger waiting time and developed a simulated annealing algorithm to solve large instances of the problem within short computation times. Sun [45] proposed the concept of equivalent time to synchronize train operations and passenger demand, then he provided a mixed-integer programming model that allows for train capacity constraints in order to design demand-driven timetables for metro services. The capacitated metro service timetabling problem can simply be solved by CPLEX. Canca [46] presented a nonlinear integer programming model to meet the dynamic passenger demand; this model can also be used to measure the timetable quality and to offer the service provider a trade-off between service quality and operational cost. Niu [5] considered time-dependent demand and skip-stop patterns; a nonlinear integer programming model with quadratic and quasi-quadratic objective functions was proposed to compute the total passenger waiting time under both minute-dependent demand and hour-dependent demand. However, the above studies only considered passenger waiting time at stations; the in-vehicle travel time is ignored. Wang [47, 48] proposed a nonlinear nonconvex model, the objective function of which is total energy consumption and total passenger travel time. A set of possible approaches is used to solve the model. Besides, the iterative convex programming approach is proved to provide a better trade-off between the quality of solution and computational time. Xu [49] proposed a multiobjective timetable optimization approach to minimize the passenger time and energy consumption. Robenek et al. [50, 51] proposed the Elastic Passenger Centric Train Timetabling Problem (EPCTTP) model with the objective of maximizing the train operating company’s revenue. Robenek [52] proposed a hybrid timetable combining the benefits of cyclic and demand-oriented timetables. Hassannayebi et al. [53] applied an adaptive and variable neighborhood search algorithm to optimize the train timetable problem. Yin [54] developed a timetable optimizing model, considering the dynamic passenger demands and energy saving objective. A Lagrangian relaxation-based heuristic algorithm is proposed to solve the model. Zhang [6] considered flexible skip-stop scheme and proposed a mixed-integer nonlinear programming model to minimize the average passenger travel time. Shen [55] and Zhang [56] proposed timetabling model to minimize the passenger travel time under congestion conditions. Liu [57] considered joint routing and scheduling between freight and passenger trains and proposed a model to study the robust passenger train timetable. A branch-and-bound framework with hybrid heuristics is used to solve the model. A systematic comparison among the typical existing studies is shown in Table 1.Table 1
Overview of existing demand-oriented timetabling models.
Model
Type
Objective
Unset Serviceorder
Overtaking allowed
Skipstop
Algorithm
Niu [42]
Non-linear
AWT
×
×
×
Genetic Algorithm
Barrena [43]
linear
AWT
×
×
×
Branch-and-cut
Barrena [44]
Non-linear
AWT
×
×
×
Adaptive large neighborhood search
Shang [58]
Non-linear
TTT
×
×
×
Branch and bound
Sun [45]
MIP
AWT
×
×
×
Branch and bound
Canca [46]
Non-linear
AWT and Operational benefit
×
×
×
Branch and bound
Niu [5]
Non-linear
AWT
×
×
√
Branch and bound
Wang [47]
Non-linear Non-convex
TTT and energy
×
×
×
Iterative convex programming
Wang [48]
Non-linear Non-convex
AWT
×
×
×
Sequential quadratic programming
Yin [59]
Stochastic
TTT and train operational costs
×
×
×
Approximate dynamic programming
Note: AWT = average passenger waiting time; TTT = total passenger travel time.
×: not considered in the model; √: considered in the model.Table1 shows that all of the timetable models are based on dynamic passenger demand in the existing literature. In summary, all models fix the service order and do not allow trains to overtake one another. These assumptions are made to simplify the model; however, they create certain drawbacks to this approach.First, the assumption of fixed service order or zero overtaking can lead to more travel time of passengers, especially when there are more than one stop plan for trains. Taking Figure1 as an example, there are three stations on a railway line, represented as Station 1, Station 2, and Station 3, respectively; there are three trains, Train 1, Train 2, and Train 3, which is a stop train, a nonstop train, and a stop train, respectively. The given service order is shown in Figure 1(a). The time-dependent OD matrix is shown in Table 2. The original timetable can satisfy passenger demand. However, we can see from the OD matrix that there are some long-distance travelers between stations 1 and 3 at the second minute and some short-distance travelers between stations 2 and 3 at the fourth minute. If Train 2 overtakes Train 1 at Station 2 (Figure 1(b)), passengers’ waiting time will decrease. From the OD matrix, we also notice that there are many long-distance travelers between stations 1 and 3 at the fourth minute. If we change the service order (Figure 1(c)), passengers’ in-vehicle time will decrease. Moreover, if overtaking and variable service order is permitted simultaneously (Figure 1(d)), passengers’ in-vehicle time and passengers’ waiting time will decrease. Detailed results of each situation are shown in Table 3. Obviously, variable service order and overtaking are necessary to reduce total travel time. If one optimizes the timetable with the given order and there is not any overtaking, it is difficult to obtain a satisfactory solution. As the number of trains increases, and the number of combinations of service orders and overtaking becomes much larger, the gap between the obtained solution and the real optimal timetable can be expected to widen.Table 2
Passenger demand.
OD
Time
1
2
3
4
5
6
7
Total
1-2
30
0
0
0
0
0
0
30
2-3
0
0
10
20
0
0
0
30
1-3
10
20
0
50
0
0
0
80Table 3
The result of each situation.
Fixed order, zero overtaking
Fixed order, allowing overtaking
Variable order, zero overtaking
Variable order, allowing overtaking
Passengers’ waiting time
60
10
100
60
Passengers’ in-vehicle time
280
290
200
220
Passengers’ travel time
340
300
300
280Figure 1
Illustration of timetable.
(a)
(b)
(c)
(d)Second, the assumption of zero overtaking can cause infeasible solutions of the model to be obtained for large-scale instances. When dealing with large numbers of trains, for example, the trains cannot be assigned within the given time period due to the capacity problem.In order to overcome the two drawbacks mentioned above, this paper provides a mixed-integer quadratic programming model, in which the train departure order at the origin station is not defined in advance and overtaking is allowed for any pair of trains. The model takes the dwell time, running time, safety interval, overtaking, and capacity as constraints, with the objective of minimizing the sum of passengers’ waiting time and in-vehicle time.The remainder of this paper is structured as follows. Section2 describes the problem and some basic assumptions; Section 3 presents four models based on the combinatorial condition of service order and train overtaking, as shown in Table 4. The passenger demand for the Shanghai-Hangzhou intercity high-speed rail provides the input data for the proposed models and the computational results are compared in Section 4. Sensitivity analysis is shown in Section 5. We discuss the passenger delays and the train robustness in Section 6. We conclude with the paper’s main contributions and propose the problems that need to be further investigated.Table 4
Combinational conditions of different models presented in this paper.
Service order
Train overtaking
Zero overtaking
Allowing overtaking
Fixed order
Model M1
Model M2
Variable order
Model M3
Model M4


## 1.2. Main Contribution

To the best of our knowledge, many demand-oriented timetable models have been developed. Besides, stop-skipping conditions have been considered in some of the models [5, 6]. However, the combinatorial influence of train service order and overtaking condition on the timetabling is not fully elucidated in these existing studies. Through the illustration, we can find that changing train service order and overtaking condition exactly reduces the passengers’ total travel time. Therefore, this paper tries to fill this gap by comprehensively investigating the timetabling with different operating conditions, e.g., the fixed order with zero overtaking, the variable order with zero overtaking, the fixed order with overtaking, and the variable order with overtaking.


## 2. Problem Statement

### 2.1. Demand-Oriented Timetable Design Problem

The demand-oriented timetable design problem is here defined as finding an optimal timetable that contains arrival times, departure times, order number, and overtaking properties for each train at each station on a railway line, given a certain line stopping plan for all services and time-dependent passenger demand during the planning period. It is especially designed for railway lines in which each direction runs relatively separately, e.g., in medium and long distances railway lines. The links of both directions, turn back time, and rolling stock issues are not considered. The goal is to meet the passenger demand, more explicitly, to minimize the total travel time of all passengers.We focus on designing a demand-oriented timetable for a single bidirectional railway line, so that train overcrossing is not necessarily considered. The railway line is defined as stations and sections (see Figure2). The planning period is defined as T
=
T
0
,
T
1, which is discretized into times of length δ. The departure times and arrival times of each train i at station m are indicated as two integers within the planning period: d
i
m
∈
T
0
,
T
1, a
i
m
∈
T
0
,
T
1. The time-dependent passenger demand of the railway is represented by the OD matrix for each δ.Figure 2
Representation of one direction of railway line.


### 2.2. Assumptions and Notations

#### 2.2.1. Assumptions

In order to construct the timetabling model based on passenger demand, we introduce the following assumptions:(1)
The dynamic passenger demand is known with accuracy to the minute. This assumption is reasonable, because, nowadays, most railways are equipped with automatic fare collection systems; from this system, the time-dependent OD matrix can easily be obtained.
(2)
For a given input of line plan, the total capacity of all trains is larger than the total passenger demand, so that all passengers arriving at the stations can be served.
(3)
Passengers board train according to a first-in, first-served rule. Passengers may take the train that arrives second if they can arrive at their destination station earlier by taking this train.
(4)
Each train has a capacity; when the number of passengers achieves this capacity, no more passengers can be loaded until at least one passenger alights. When an arrival train is full, no further passengers can board and passengers at this station will continue to wait until a train that is not full arrives.
(5)
The departure time of the last train for each station is known, which is the deadline for the arrival time of passengers. This assumption is to ensure that all passengers arrive at their destination stations during the planning horizon [5].
(6)
The temporal gap between the moment when a passenger enters (leaves) a station and the moment when the same passenger boards (alights) the train is neglected.


#### 2.2.2. Notations

ParametersN: The set of trains, i
,
j
∈
N.S: The set of stations, m
,
n
∈
S.T: The study period.t: Index of time interval, t
∈
T.T
m: The departure time of the last train from stationm.t
a
c
c: Acceleration time needed to reach maximum speed.t
d
e
c: Deceleration time needed to stop from maximum speed.τ
i
m
,
n: Coupled-stop index, equal to 1 if train i stops at both station m and stationn, otherwise, equal to 0.h
m
d: The departure headway for two consecutive trains at station m.h
m
a: The arrival headway for two consecutive trains at station m.M: A large positive integer.C
i: The maximum number of passengers that train i can load.Datap
m
,
n
(
t
): The number of passengers arriving at the stationmwho want to go to stationn within the time interval t.s
i
m: Skip-stop index, equal to 1 if train i stops at station m, otherwise, equal to 0.r
i
m: Minimum running time of train i from station m to station m
+
1; running time equals to the sum of pure running time, acceleration time, and deceleration time.Δ
r
i
m: Allowed deviation of running time of train i from stationm to station m
+
1.p
r
i
m: Pure running time of train i from station m to station m
+
1.w
i
m
_: Minimum dwell time of train i at station m.Δ
w
i
m: Allowed deviation of dwell time of train i at station m.Decision Variables:d
i
m: The departure time of train i at station m.a
i
m: The arrival time of train i at station m.z
i
m
(
t
): Binary variable, equal to 1 if a passenger who arrives at station m in time interval t can get on train i, otherwise, equal to 0. Whether the passenger has the chance to get on the train or not depends on the passenger’s arrival time and the departure time of the train. If the passenger’s arrival time is smaller than the departure time of the train, the passenger has the chance to board the train, otherwise, the passenger has no chance to board the train.L
i
m
,
n
(
t
): Binary variable, equal to 1 if the passenger who arrives at station m in time intervalt successfully gets on train i, otherwise, equal to 0. Whether a passenger can successfully gets on the train depends not only on the of the passenger’s arrival time and the departure time of the train, but also on the remaining capacity of the train.q
i
,
j
m: Binary variable, equal to 1 if trainj overtakes train i at station m, otherwise, equal to 0;x
i
j
m: Binary variable, equal to 1 if train j departs from station m before train i, otherwise, equal to 0.y
i
j
m: Binary variable, equal to 1 if the train j arrives at station m before train i, otherwise, equal to 0.b
i
m
,
n: The realized number of passengers boarding train i from the station m to station n.C
a
p
i
m: The number of passengers on train i after departing from station m.T
s
i
m
,
n: Waiting time of passengers boarding train i from the station m to station n.T
r
i
m
,
n: In-vehicle time of passengers boarding train i from the station m to station n.


## 2.1. Demand-Oriented Timetable Design Problem

The demand-oriented timetable design problem is here defined as finding an optimal timetable that contains arrival times, departure times, order number, and overtaking properties for each train at each station on a railway line, given a certain line stopping plan for all services and time-dependent passenger demand during the planning period. It is especially designed for railway lines in which each direction runs relatively separately, e.g., in medium and long distances railway lines. The links of both directions, turn back time, and rolling stock issues are not considered. The goal is to meet the passenger demand, more explicitly, to minimize the total travel time of all passengers.We focus on designing a demand-oriented timetable for a single bidirectional railway line, so that train overcrossing is not necessarily considered. The railway line is defined as stations and sections (see Figure2). The planning period is defined as T
=
T
0
,
T
1, which is discretized into times of length δ. The departure times and arrival times of each train i at station m are indicated as two integers within the planning period: d
i
m
∈
T
0
,
T
1, a
i
m
∈
T
0
,
T
1. The time-dependent passenger demand of the railway is represented by the OD matrix for each δ.Figure 2
Representation of one direction of railway line.


## 2.2. Assumptions and Notations

### 2.2.1. Assumptions

In order to construct the timetabling model based on passenger demand, we introduce the following assumptions:(1)
The dynamic passenger demand is known with accuracy to the minute. This assumption is reasonable, because, nowadays, most railways are equipped with automatic fare collection systems; from this system, the time-dependent OD matrix can easily be obtained.
(2)
For a given input of line plan, the total capacity of all trains is larger than the total passenger demand, so that all passengers arriving at the stations can be served.
(3)
Passengers board train according to a first-in, first-served rule. Passengers may take the train that arrives second if they can arrive at their destination station earlier by taking this train.
(4)
Each train has a capacity; when the number of passengers achieves this capacity, no more passengers can be loaded until at least one passenger alights. When an arrival train is full, no further passengers can board and passengers at this station will continue to wait until a train that is not full arrives.
(5)
The departure time of the last train for each station is known, which is the deadline for the arrival time of passengers. This assumption is to ensure that all passengers arrive at their destination stations during the planning horizon [5].
(6)
The temporal gap between the moment when a passenger enters (leaves) a station and the moment when the same passenger boards (alights) the train is neglected.


### 2.2.2. Notations

ParametersN: The set of trains, i
,
j
∈
N.S: The set of stations, m
,
n
∈
S.T: The study period.t: Index of time interval, t
∈
T.T
m: The departure time of the last train from stationm.t
a
c
c: Acceleration time needed to reach maximum speed.t
d
e
c: Deceleration time needed to stop from maximum speed.τ
i
m
,
n: Coupled-stop index, equal to 1 if train i stops at both station m and stationn, otherwise, equal to 0.h
m
d: The departure headway for two consecutive trains at station m.h
m
a: The arrival headway for two consecutive trains at station m.M: A large positive integer.C
i: The maximum number of passengers that train i can load.Datap
m
,
n
(
t
): The number of passengers arriving at the stationmwho want to go to stationn within the time interval t.s
i
m: Skip-stop index, equal to 1 if train i stops at station m, otherwise, equal to 0.r
i
m: Minimum running time of train i from station m to station m
+
1; running time equals to the sum of pure running time, acceleration time, and deceleration time.Δ
r
i
m: Allowed deviation of running time of train i from stationm to station m
+
1.p
r
i
m: Pure running time of train i from station m to station m
+
1.w
i
m
_: Minimum dwell time of train i at station m.Δ
w
i
m: Allowed deviation of dwell time of train i at station m.Decision Variables:d
i
m: The departure time of train i at station m.a
i
m: The arrival time of train i at station m.z
i
m
(
t
): Binary variable, equal to 1 if a passenger who arrives at station m in time interval t can get on train i, otherwise, equal to 0. Whether the passenger has the chance to get on the train or not depends on the passenger’s arrival time and the departure time of the train. If the passenger’s arrival time is smaller than the departure time of the train, the passenger has the chance to board the train, otherwise, the passenger has no chance to board the train.L
i
m
,
n
(
t
): Binary variable, equal to 1 if the passenger who arrives at station m in time intervalt successfully gets on train i, otherwise, equal to 0. Whether a passenger can successfully gets on the train depends not only on the of the passenger’s arrival time and the departure time of the train, but also on the remaining capacity of the train.q
i
,
j
m: Binary variable, equal to 1 if trainj overtakes train i at station m, otherwise, equal to 0;x
i
j
m: Binary variable, equal to 1 if train j departs from station m before train i, otherwise, equal to 0.y
i
j
m: Binary variable, equal to 1 if the train j arrives at station m before train i, otherwise, equal to 0.b
i
m
,
n: The realized number of passengers boarding train i from the station m to station n.C
a
p
i
m: The number of passengers on train i after departing from station m.T
s
i
m
,
n: Waiting time of passengers boarding train i from the station m to station n.T
r
i
m
,
n: In-vehicle time of passengers boarding train i from the station m to station n.


## 2.2.1. Assumptions

In order to construct the timetabling model based on passenger demand, we introduce the following assumptions:(1)
The dynamic passenger demand is known with accuracy to the minute. This assumption is reasonable, because, nowadays, most railways are equipped with automatic fare collection systems; from this system, the time-dependent OD matrix can easily be obtained.
(2)
For a given input of line plan, the total capacity of all trains is larger than the total passenger demand, so that all passengers arriving at the stations can be served.
(3)
Passengers board train according to a first-in, first-served rule. Passengers may take the train that arrives second if they can arrive at their destination station earlier by taking this train.
(4)
Each train has a capacity; when the number of passengers achieves this capacity, no more passengers can be loaded until at least one passenger alights. When an arrival train is full, no further passengers can board and passengers at this station will continue to wait until a train that is not full arrives.
(5)
The departure time of the last train for each station is known, which is the deadline for the arrival time of passengers. This assumption is to ensure that all passengers arrive at their destination stations during the planning horizon [5].
(6)
The temporal gap between the moment when a passenger enters (leaves) a station and the moment when the same passenger boards (alights) the train is neglected.


## 2.2.2. Notations

ParametersN: The set of trains, i
,
j
∈
N.S: The set of stations, m
,
n
∈
S.T: The study period.t: Index of time interval, t
∈
T.T
m: The departure time of the last train from stationm.t
a
c
c: Acceleration time needed to reach maximum speed.t
d
e
c: Deceleration time needed to stop from maximum speed.τ
i
m
,
n: Coupled-stop index, equal to 1 if train i stops at both station m and stationn, otherwise, equal to 0.h
m
d: The departure headway for two consecutive trains at station m.h
m
a: The arrival headway for two consecutive trains at station m.M: A large positive integer.C
i: The maximum number of passengers that train i can load.Datap
m
,
n
(
t
): The number of passengers arriving at the stationmwho want to go to stationn within the time interval t.s
i
m: Skip-stop index, equal to 1 if train i stops at station m, otherwise, equal to 0.r
i
m: Minimum running time of train i from station m to station m
+
1; running time equals to the sum of pure running time, acceleration time, and deceleration time.Δ
r
i
m: Allowed deviation of running time of train i from stationm to station m
+
1.p
r
i
m: Pure running time of train i from station m to station m
+
1.w
i
m
_: Minimum dwell time of train i at station m.Δ
w
i
m: Allowed deviation of dwell time of train i at station m.Decision Variables:d
i
m: The departure time of train i at station m.a
i
m: The arrival time of train i at station m.z
i
m
(
t
): Binary variable, equal to 1 if a passenger who arrives at station m in time interval t can get on train i, otherwise, equal to 0. Whether the passenger has the chance to get on the train or not depends on the passenger’s arrival time and the departure time of the train. If the passenger’s arrival time is smaller than the departure time of the train, the passenger has the chance to board the train, otherwise, the passenger has no chance to board the train.L
i
m
,
n
(
t
): Binary variable, equal to 1 if the passenger who arrives at station m in time intervalt successfully gets on train i, otherwise, equal to 0. Whether a passenger can successfully gets on the train depends not only on the of the passenger’s arrival time and the departure time of the train, but also on the remaining capacity of the train.q
i
,
j
m: Binary variable, equal to 1 if trainj overtakes train i at station m, otherwise, equal to 0;x
i
j
m: Binary variable, equal to 1 if train j departs from station m before train i, otherwise, equal to 0.y
i
j
m: Binary variable, equal to 1 if the train j arrives at station m before train i, otherwise, equal to 0.b
i
m
,
n: The realized number of passengers boarding train i from the station m to station n.C
a
p
i
m: The number of passengers on train i after departing from station m.T
s
i
m
,
n: Waiting time of passengers boarding train i from the station m to station n.T
r
i
m
,
n: In-vehicle time of passengers boarding train i from the station m to station n.


## 3. Models

In this section, we construct four mathematical programming models according to different combinations of service order and overtaking conditions to design demand-oriented timetables, as follows:(i)
Model M1: fixed service order and zero overtaking timetabling model. In this model, service order at the origin station is fixed and train overtaking is strictly prohibited.
(ii)
Model M2: fixed service order and limited overtaking timetabling model. In this model, service order at the origin station is fixed and only adjacent trains are allowed to overtake each other.
(iii)
Model M3: variable service order and zero overtaking are allowed.
(iv)
Model M4: unfixed service order and extended overtaking timetabling model. In this model, service order at the origin station is allowed to change and overtaking is allowed between any two arbitrary trains.


### 3.1. Fix Service Order Zero Overtaking Model M1

In this model, the service order at the origin station is predefined and trains cannot overtake each other. The details of the model are described as follows.


#### 3.1.1. Objective Function

The objective function of model M1 is set to minimize the total travel time of passengers. The travel time of a passenger on a single railway line is defined as the sum of the passenger waiting time at stations and in-vehicle time. The literature [60] shows that the perceived time elapsed inside and outside of the train may be different, so the perceived total travel time is represented as a weighted sum of waiting time and in-vehicle time, as shown in the following formula:(1)
min
⁡
∑
i
=
1
N
∑
m
=
1
S
-
1
∑
n
=
m
+
1
S
ω
1
∗
T
s
i
m
,
n
+
ω
2
∗
T
r
i
m
,
nwhere ω
1 is the weight of passenger waiting time at stations and ω
2 is the weight of in-vehicle time.(1) Passenger Waiting Time at Stations. The number of passengers who get on train i from station m to station n can be computed from the following formula:(2)
b
i
m
,
n
=
∑
t
=
1
T
m
L
i
m
,
n
t
∗
p
m
,
n
t
∗
τ
i
m
,
nThe total waiting time for traini for passengers who arrive at station m within time intervaltand want to go to station n can be computed from the following formula:(3)
T
s
i
m
,
n
=
b
i
m
,
n
∗
d
i
m
-
t
i
=
1
…
N
,
m
=
1
…
S
-
1
,
n
=
m
+
1
…
S(2) In-Vehicle Time of Passengers. The in-vehicle time of passengers who get on train i at station m to station n can be computed from the following formula:(4)
T
r
i
m
,
n
=
b
i
m
,
n
∗
a
i
n
-
d
i
m
i
=
1
…
N
,
m
=
1
…
S
-
1
,
n
=
m
+
1
…
S


#### 3.1.2. Constraints

(1) Dwell Time Constraints. Generally speaking, the lower limit of dwell time is determined by signaling system, door opening, and closing time. The upper limit of dwell time is determined by the number of passengers and line capacity. To simplify these complex influencing factors, it is defined within a scope.(5)
w
i
m
_
∗
s
i
m
≤
d
i
m
-
a
i
m
≤
w
i
m
_
+
Δ
w
i
m
∗
s
i
m
i
=
1
…
N
,
m
=
2
…
S
-
1(2) Running Time Constraints
(6)
r
i
m
≤
a
i
m
+
1
-
d
i
m
≤
r
i
m
+
Δ
r
i
m
i
=
1
…
N
,
m
=
1
…
S
-
1
(7)
r
i
m
=
p
r
i
m
+
s
i
m
∗
t
a
c
c
+
s
i
m
+
1
∗
t
d
e
c
i
=
1
…
N
,
m
=
1
…
S
-
1(3) Headway Constraints. The adjacent trains need to meet the arrival interval and the departure interval in order to run safely. In this model, one train is not allowed to be overtaken by another train, so the service order will not change along any sections of the railway line. Thus, the constraints can be written as the arrival headway and departure headway constraints for two adjacent trains, as in the following:(8)
a
i
+
1
m
-
a
i
m
≥
h
m
a
i
=
1
…
N
-
1
,
m
=
2
…
S
(9)
d
i
+
1
m
-
d
i
m
≥
h
m
d
i
=
1
…
N
-
1
,
m
=
1
…
S
-
1(4) Character of the Variable
z
i
m
(
t
). If a passenger arriving at station m within time interval t has the chance to get on train i, the passenger arriving at stationm within time interval t
-
1 has the chance to get on train i too, so the variable z
i
m
(
t
)is nonincreasing. For example, in Figure 3, if train i departs at time interval 4, z
i
m
(
1
)
=
z
i
m
(
2
)
=
z
i
m
(
3
)
=
z
i
m
(
4
)
=
1, while the remaining values are equal to 0.(10)
Hence
z
i
m
t
-
1
>
=
z
i
m
t
t
=
2
…
T
m
,
i
=
1
…
N
,
m
=
1
…
S
-
1Figure 3
Character of variablez
i
m
(
t
).(5) The Relationship between
z
i
m
(
t
)
and
d
i
m. If a train departs at the end of time intervalt, then z
i
m
(
t
)
=
1, z
i
m
(
t
+
1
)
=
0, then z
i
m
(
t
)
-
z
i
m
(
t
+
1
)
=
1, so the relationship between z
i
m
(
t
) and d
i
m can be written as formula (11). For example, in Figure 4, if traini departs at time interval 4, z
i
m
(
4
)
=
1, z
i
m
(
5
)
=
0, obviously z
i
m
(
4
)
-
z
i
m
(
5
)
=
1.(11)
d
i
m
=
∑
t
=
1
T
-
1
t
∗
z
i
m
t
-
z
i
m
t
+
1Figure 4
The relationship betweenz
i
m
(
t
) and d
i
m.(6) The Relationship between
z
i
m
(
t
)
and
L
i
m
,
n
(
t
). If the variable L
i
m
,
n
(
t
)
=
1, then the variable z
i
m
(
t
) must be equal to 1. If the variable z
i
m
(
t
)
=
0, then the variable L
i
m
,
n
(
t
) must be 0. If the variable L
i
m
,
n
(
t
)
=
0, the variable z
i
m
(
t
) is not necessarily equal to 0. The relationship between z
i
m
(
t
) and L
i
m
,
n
(
t
) can be written as the following formula:(12)
L
i
m
,
n
t
<
=
z
i
m
t
t
=
1
…
T
m
,
i
=
1
…
N
,
m
=
1
…
S
-
1
,
n
=
m
+
1
…
S(7) Train Choice Constraint. Formula (13) means that the passenger arriving at station m who wants to go to station n can only choose one train.(13)
∑
i
=
1
N
τ
i
m
,
n
∗
L
i
m
,
n
t
=
1
m
=
1
…
S
-
1
,
n
=
m
+
1
…
S(8) Train Capacity Constraints. The number of passengers on the train i after departing from station m must be less than or equal to the train capacity. This constraint can be written as formula (14). The number of passengers on train i after departing from station m is equal to the total number of passengers boarding at station m and previous stations minus the number of passengers getting off at station m and previous stations.Moreover, the number of passengers on train i after departing from station m is also equal to the number of passengers boarding at station m and previous stations who want to go to the stations after station m. Therefore, it can be written as formula (15). (14)
C
a
p
i
m
≤
C
i
i
=
1
…
N
,
m
=
1
…
S
-
1
(15)
C
a
p
i
m
=
∑
m
′
=
1
m
∑
n
=
m
′
+
1
S
∑
t
=
1
T
m
p
m
′
,
n
t
∗
L
i
m
′
,
n
t
∗
τ
i
m
′
,
n
-
∑
m
′
=
1
m
-
1
∑
n
=
m
′
+
1
m
∑
t
=
0
T
p
m
′
,
n
t
∗
L
i
m
′
,
n
t
∗
τ
i
m
′
,
n
=
∑
m
′
=
1
m
∑
n
=
m
+
1
S
∑
t
=
1
T
m
p
m
′
,
n
t
∗
L
i
m
′
,
n
t
∗
τ
i
m
′
,
n


### 3.2. Fix Service Order Allowing Overtaking Model M2

The model M2 fixes the service order at the origin station and allows adjacent trains to overtake one another. In this model, it is assumed that a train can be overtaken at most once. In order to realize the overtaking between two adjacent trains, a dummy variableq
i
,
j
m is introduced, where q
i
,
j
m equals 1 if train i can overtake train j, otherwise q
i
,
j
m equals 0. The following constraints from (16) to (25) are used to replace constraints (8) and (9): (16)
a
i
+
1
m
+
1
+
h
m
+
1
a
-
a
i
m
+
1
<
=
M
1
-
∑
k
=
1
m
q
i
,
j
k
i
=
1
…
N
-
1
,
j
=
i
+
1
,
m
=
1
…
S
-
1
(17)
a
i
-
1
m
+
1
+
h
m
+
1
a
-
a
i
+
1
m
+
1
<
=
M
1
-
∑
k
=
1
m
q
i
,
j
k
i
=
1
…
N
-
1
,
j
=
i
+
1
,
m
=
1
…
S
-
1
(18)
a
i
m
+
1
+
h
m
+
1
a
-
a
i
+
2
m
+
1
<
=
M
1
-
∑
k
=
1
m
q
i
,
j
k
i
=
1
…
N
-
1
,
j
=
i
+
1
,
m
=
1
…
S
-
1
(19)
a
i
m
+
h
m
a
-
a
i
+
1
m
<
=
M
∗
∑
k
=
1
m
-
1
q
i
,
j
k
i
=
1
…
N
-
1
,
j
=
i
+
1
,
m
=
2
…
S
(20)
d
i
+
1
m
+
h
m
d
-
d
i
m
<
=
M
1
-
∑
k
=
1
m
q
i
,
j
k
i
=
1
…
N
-
1
,
j
=
i
+
1
,
m
=
1
…
S
-
1
(21)
d
i
-
1
m
+
h
m
d
-
d
i
+
1
m
<
=
M
1
-
∑
k
=
1
m
q
i
,
j
k
i
=
1
…
N
-
1
,
j
=
i
+
1
,
m
=
1
…
S
-
1
(22)
d
i
m
+
h
m
d
-
d
i
+
2
m
<
=
M
1
-
∑
k
=
1
m
q
i
,
j
k
i
=
1
…
N
-
1
,
j
=
i
+
1
,
m
=
1
…
S
-
1
(23)
d
i
m
-
1
+
h
m
-
1
d
-
d
i
+
1
m
-
1
<
=
M
∗
∑
k
=
1
m
-
1
q
i
,
j
k
i
=
1
…
N
-
1
,
j
=
i
+
1
,
m
=
2
…
S
(24)
∑
m
=
2
S
-
1
q
i
,
j
m
<
=
1
i
=
1
…
N
,
j
=
i
+
1
(25)
q
i
,
j
m
∈
0,1The above constraints also adjust to the situation in which the trains do not overtake each other. For example, if the trains do not overtake each other,∑
k
=
1
m
q
i
,
j
k
=
0, then constraints (19) and (23) can secure the safety arrival interval and the safety departure interval, while the other constraints will always be satisfied when q
i
,
j
m is equal to 0.If traini
+
1 overtakes train i at station m, i.e., ∑
k
=
1
m
q
i
,
j
k
=
1, ∑
k
=
1
m
-
1
q
i
,
j
k
=
0, as illustrated in Figure 5, then constraints (19) and (23) can secure the safety interval for train i and traini+1 before the overtaking stationm. When traini+1 overtakes train i at station m, the service order becomesi-1, i+1, i, i+2. Constraints (16) and (20) can secure the safety interval for train i and traini+1 after the overtaking station m. Likewise, the constraints (17) and (21) can secure the safety interval for traini−1 and traini+1 after the overtaking stationm, and the constraints (18) and (22) can secure the safety interval for train i and traini+2 after the overtaking stationm. The constraints (24) ensure that train i can be overtaken by traini+1 at most once.Figure 5
Diagram of train overtaking.


### 3.3. Variable Service Order Zero Overtaking Model M3

Model M3 does not fix the service order, and zero overtaking is allowed. A dummy variablex
i
j
∈
{
0,1
} is introduced, which represents the running order of train i and train j
.Since this order does not change when train runs along the railway line, so the value of this variable for any two trains is the same in all sections. If trainjruns after train i
,then x
i
j
=
1, otherwise, x
i
j
=
0. Now the headway constraints of Model 1 can be reformulated as constraints from (26) to (29).(26)
a
j
m
-
a
i
m
≥
h
m
a
·
x
i
j
-
M
·
1
-
x
i
j
i
=
1,2
…
N
,
j
=
1,2
…
N
(27)
a
i
m
-
a
j
m
≥
h
m
a
·
1
-
x
i
j
-
M
·
x
i
j
i
=
1,2
…
N
,
j
=
1,2
…
N
(28)
d
j
m
-
d
i
m
≥
h
m
d
·
x
i
j
-
M
·
1
-
x
i
j
i
=
1,2
…
N
,
j
=
1,2
…
N
(29)
d
j
m
-
d
i
m
≥
h
m
d
·
x
i
j
-
M
·
1
-
x
i
j
i
=
1,2
…
N
,
j
=
1,2
…
N


### 3.4. Variable Service Order Allowing Overtaking Model M4

Model M4 does not fix the service order at the origin station and allows arbitrary trains to overtake one another. Two new binary variables are introduced to represent the order of train arrivals and departures, namelyx
i
j
m and y
i
j
m
+
1. As is shown in Figure 6(a), if d
j
m
-
d
i
m
>
0, namely trainjdeparts from stationmafter traini, then x
i
j
m
=
0, otherwise, x
i
j
m
=
1. As is shown in Figure 6(b), if a
j
m
+
1
-
a
i
m
+
1
>
0, namely if trainj arrives at stationm+1 after traini, then y
i
j
m
+
1
=
0, otherwise y
i
j
m
+
1
=
1.Figure 6
Safety interval constraints.The safety constraints of model M3 can be written as equations containing the service order variablesx
i
j
m and y
i
j
m
+
1, as shown in (30) and (31). These two kinds of constraints can be used to ensure the safety departure interval and safety arrival interval, in the situation where the service order at the origin station is not fixed.(30)
h
m
d
≤
d
j
m
-
d
i
m
+
T
∗
x
i
j
m
≤
T
-
h
m
d
i
,
j
=
1
…
N
,
j
>
i
,
m
=
1
…
S
-
1
(31)
h
m
a
≤
a
j
m
-
a
i
m
+
T
∗
y
i
j
m
≤
T
-
h
m
a
i
,
j
=
1
…
N
,
j
>
i
,
m
=
2
…
SIn order to illustrate how constraints (30) and (31) ensure the safety interval and allow arbitrary trains to overtake one another, the following proof is given.Proof of Constraint (30).
Situation 1. Trainj departs from station m after train i
Left-Hand Side of Constraint (30). As shown in Figure 6(a), if trainj departs from stationm after train i, then x
i
j
m
=
0; in order to meet the safety departure interval, d
j
m
-
d
i
m
≥
h
m
d is necessary.
Right-Hand Hand of Constraint (30). Let m
=
S
-
1; then the equation d
j
S
-
1
+
r
j
S
-
1
=
a
j
S is always satisfied, where a
j
S is the arrival time at station s of train j.
Becausea
j
S
≤
T, we have d
j
S
-
1
+
r
j
S
-
1
=
a
j
S
≤
T;
Becauser
S
-
1
n
>
=
h
S
-
1
d (the running time is usually larger than the safety interval), we have the equation d
j
S
-
1
<
=
T
-
r
j
S
-
1
<
=
T
-
h
s
-
1
d;
Therefore, at stationS−1, d
j
S
-
1
-
d
i
S
-
1
≤
T
-
h
-
d
i
S
-
1
<
=
T
-
h
s
-
1
d;
Whenm
≤
S
-
1, d
j
m
<
d
j
S
-
1
≤
T
-
h
s
-
1
d, d
i
m
≥
0, so d
j
m
-
d
i
m
<
T
-
h
m
d;
Therefore, the consistency of the constraint (30) is proved.
Situation 2. Train i departs from station m after train j
If traini departs from station m after train j, in order to meet the safety departure interval, d
i
m
-
d
j
m
≥
h
m
d is necessary. Multiplying both sides of the equation by −1, then addingT, we have the equation d
j
m
-
d
i
m
+
T
≤
T
-
h
m
d, namely, the right-hand side of (30) is proved.
Because traini departs from stationm after train j, according to the proof above, d
i
m
-
d
j
m
<
=
T
-
h
m
d must be satisfied. Multiplying both sides of the equation by −1, then addingT, we have the equation d
j
m
-
d
i
m
+
T
>
=
h
m
d, so the left-hand side of (30) is proved.Proof of the Constraint (31).
Situation 1. Train j arrives at station m after train i
Left-Hand Side of Constraint (31). As shown in Figure 6(a), if trainj arrives at stationm after traini, in order to meet the safety arrival interval, a
j
m
-
a
i
m
≥
h
m
a is necessary.
Right-Hand Side of Constraint (31). Because a
j
m
≤
T and a
i
m
=
d
i
m
-
1
+
r
i
m
-
1
≥
h
m
a, therefore, a
j
m
-
a
i
m
≤
T
-
h
m
a is always satisfied.
Situation 2. Train i arrives at station m after train j
If traini arrives at stationm after trainj, in order to meet the safety arrival interval, a
i
m
-
a
j
m
≥
h
m
a is necessary. Multiplying both sides of the equation by −1, then addingT, we have the equation a
j
m
-
a
i
m
+
T
≤
T
-
h
m
a, thus the right-hand side of constraint (31) is proved.
If traini arrives at stationm after trainj, then, according to the proof above, a
i
m
-
a
j
m
<
=
T
-
h
m
a is necessary. Multiplying both sides of the equation by −1, then addingT, we have the equation a
j
m
-
a
i
m
+
T
≥
h
m
a, so the left-hand side of constraint (31) is proved.According to the proof above, we can conclude that constraints (30) and (31) can ensure the safety departure interval and safety arrival interval of two arbitrary trains. These two sets of constraints also allow trains to overtake each other at stations.


## 3.1. Fix Service Order Zero Overtaking Model M1

In this model, the service order at the origin station is predefined and trains cannot overtake each other. The details of the model are described as follows.


### 3.1.1. Objective Function

The objective function of model M1 is set to minimize the total travel time of passengers. The travel time of a passenger on a single railway line is defined as the sum of the passenger waiting time at stations and in-vehicle time. The literature [60] shows that the perceived time elapsed inside and outside of the train may be different, so the perceived total travel time is represented as a weighted sum of waiting time and in-vehicle time, as shown in the following formula:(1)
min
⁡
∑
i
=
1
N
∑
m
=
1
S
-
1
∑
n
=
m
+
1
S
ω
1
∗
T
s
i
m
,
n
+
ω
2
∗
T
r
i
m
,
nwhere ω
1 is the weight of passenger waiting time at stations and ω
2 is the weight of in-vehicle time.(1) Passenger Waiting Time at Stations. The number of passengers who get on train i from station m to station n can be computed from the following formula:(2)
b
i
m
,
n
=
∑
t
=
1
T
m
L
i
m
,
n
t
∗
p
m
,
n
t
∗
τ
i
m
,
nThe total waiting time for traini for passengers who arrive at station m within time intervaltand want to go to station n can be computed from the following formula:(3)
T
s
i
m
,
n
=
b
i
m
,
n
∗
d
i
m
-
t
i
=
1
…
N
,
m
=
1
…
S
-
1
,
n
=
m
+
1
…
S(2) In-Vehicle Time of Passengers. The in-vehicle time of passengers who get on train i at station m to station n can be computed from the following formula:(4)
T
r
i
m
,
n
=
b
i
m
,
n
∗
a
i
n
-
d
i
m
i
=
1
…
N
,
m
=
1
…
S
-
1
,
n
=
m
+
1
…
S


### 3.1.2. Constraints

(1) Dwell Time Constraints. Generally speaking, the lower limit of dwell time is determined by signaling system, door opening, and closing time. The upper limit of dwell time is determined by the number of passengers and line capacity. To simplify these complex influencing factors, it is defined within a scope.(5)
w
i
m
_
∗
s
i
m
≤
d
i
m
-
a
i
m
≤
w
i
m
_
+
Δ
w
i
m
∗
s
i
m
i
=
1
…
N
,
m
=
2
…
S
-
1(2) Running Time Constraints
(6)
r
i
m
≤
a
i
m
+
1
-
d
i
m
≤
r
i
m
+
Δ
r
i
m
i
=
1
…
N
,
m
=
1
…
S
-
1
(7)
r
i
m
=
p
r
i
m
+
s
i
m
∗
t
a
c
c
+
s
i
m
+
1
∗
t
d
e
c
i
=
1
…
N
,
m
=
1
…
S
-
1(3) Headway Constraints. The adjacent trains need to meet the arrival interval and the departure interval in order to run safely. In this model, one train is not allowed to be overtaken by another train, so the service order will not change along any sections of the railway line. Thus, the constraints can be written as the arrival headway and departure headway constraints for two adjacent trains, as in the following:(8)
a
i
+
1
m
-
a
i
m
≥
h
m
a
i
=
1
…
N
-
1
,
m
=
2
…
S
(9)
d
i
+
1
m
-
d
i
m
≥
h
m
d
i
=
1
…
N
-
1
,
m
=
1
…
S
-
1(4) Character of the Variable
z
i
m
(
t
). If a passenger arriving at station m within time interval t has the chance to get on train i, the passenger arriving at stationm within time interval t
-
1 has the chance to get on train i too, so the variable z
i
m
(
t
)is nonincreasing. For example, in Figure 3, if train i departs at time interval 4, z
i
m
(
1
)
=
z
i
m
(
2
)
=
z
i
m
(
3
)
=
z
i
m
(
4
)
=
1, while the remaining values are equal to 0.(10)
Hence
z
i
m
t
-
1
>
=
z
i
m
t
t
=
2
…
T
m
,
i
=
1
…
N
,
m
=
1
…
S
-
1Figure 3
Character of variablez
i
m
(
t
).(5) The Relationship between
z
i
m
(
t
)
and
d
i
m. If a train departs at the end of time intervalt, then z
i
m
(
t
)
=
1, z
i
m
(
t
+
1
)
=
0, then z
i
m
(
t
)
-
z
i
m
(
t
+
1
)
=
1, so the relationship between z
i
m
(
t
) and d
i
m can be written as formula (11). For example, in Figure 4, if traini departs at time interval 4, z
i
m
(
4
)
=
1, z
i
m
(
5
)
=
0, obviously z
i
m
(
4
)
-
z
i
m
(
5
)
=
1.(11)
d
i
m
=
∑
t
=
1
T
-
1
t
∗
z
i
m
t
-
z
i
m
t
+
1Figure 4
The relationship betweenz
i
m
(
t
) and d
i
m.(6) The Relationship between
z
i
m
(
t
)
and
L
i
m
,
n
(
t
). If the variable L
i
m
,
n
(
t
)
=
1, then the variable z
i
m
(
t
) must be equal to 1. If the variable z
i
m
(
t
)
=
0, then the variable L
i
m
,
n
(
t
) must be 0. If the variable L
i
m
,
n
(
t
)
=
0, the variable z
i
m
(
t
) is not necessarily equal to 0. The relationship between z
i
m
(
t
) and L
i
m
,
n
(
t
) can be written as the following formula:(12)
L
i
m
,
n
t
<
=
z
i
m
t
t
=
1
…
T
m
,
i
=
1
…
N
,
m
=
1
…
S
-
1
,
n
=
m
+
1
…
S(7) Train Choice Constraint. Formula (13) means that the passenger arriving at station m who wants to go to station n can only choose one train.(13)
∑
i
=
1
N
τ
i
m
,
n
∗
L
i
m
,
n
t
=
1
m
=
1
…
S
-
1
,
n
=
m
+
1
…
S(8) Train Capacity Constraints. The number of passengers on the train i after departing from station m must be less than or equal to the train capacity. This constraint can be written as formula (14). The number of passengers on train i after departing from station m is equal to the total number of passengers boarding at station m and previous stations minus the number of passengers getting off at station m and previous stations.Moreover, the number of passengers on train i after departing from station m is also equal to the number of passengers boarding at station m and previous stations who want to go to the stations after station m. Therefore, it can be written as formula (15). (14)
C
a
p
i
m
≤
C
i
i
=
1
…
N
,
m
=
1
…
S
-
1
(15)
C
a
p
i
m
=
∑
m
′
=
1
m
∑
n
=
m
′
+
1
S
∑
t
=
1
T
m
p
m
′
,
n
t
∗
L
i
m
′
,
n
t
∗
τ
i
m
′
,
n
-
∑
m
′
=
1
m
-
1
∑
n
=
m
′
+
1
m
∑
t
=
0
T
p
m
′
,
n
t
∗
L
i
m
′
,
n
t
∗
τ
i
m
′
,
n
=
∑
m
′
=
1
m
∑
n
=
m
+
1
S
∑
t
=
1
T
m
p
m
′
,
n
t
∗
L
i
m
′
,
n
t
∗
τ
i
m
′
,
n


## 3.1.1. Objective Function

The objective function of model M1 is set to minimize the total travel time of passengers. The travel time of a passenger on a single railway line is defined as the sum of the passenger waiting time at stations and in-vehicle time. The literature [60] shows that the perceived time elapsed inside and outside of the train may be different, so the perceived total travel time is represented as a weighted sum of waiting time and in-vehicle time, as shown in the following formula:(1)
min
⁡
∑
i
=
1
N
∑
m
=
1
S
-
1
∑
n
=
m
+
1
S
ω
1
∗
T
s
i
m
,
n
+
ω
2
∗
T
r
i
m
,
nwhere ω
1 is the weight of passenger waiting time at stations and ω
2 is the weight of in-vehicle time.(1) Passenger Waiting Time at Stations. The number of passengers who get on train i from station m to station n can be computed from the following formula:(2)
b
i
m
,
n
=
∑
t
=
1
T
m
L
i
m
,
n
t
∗
p
m
,
n
t
∗
τ
i
m
,
nThe total waiting time for traini for passengers who arrive at station m within time intervaltand want to go to station n can be computed from the following formula:(3)
T
s
i
m
,
n
=
b
i
m
,
n
∗
d
i
m
-
t
i
=
1
…
N
,
m
=
1
…
S
-
1
,
n
=
m
+
1
…
S(2) In-Vehicle Time of Passengers. The in-vehicle time of passengers who get on train i at station m to station n can be computed from the following formula:(4)
T
r
i
m
,
n
=
b
i
m
,
n
∗
a
i
n
-
d
i
m
i
=
1
…
N
,
m
=
1
…
S
-
1
,
n
=
m
+
1
…
S


## 3.1.2. Constraints

(1) Dwell Time Constraints. Generally speaking, the lower limit of dwell time is determined by signaling system, door opening, and closing time. The upper limit of dwell time is determined by the number of passengers and line capacity. To simplify these complex influencing factors, it is defined within a scope.(5)
w
i
m
_
∗
s
i
m
≤
d
i
m
-
a
i
m
≤
w
i
m
_
+
Δ
w
i
m
∗
s
i
m
i
=
1
…
N
,
m
=
2
…
S
-
1(2) Running Time Constraints
(6)
r
i
m
≤
a
i
m
+
1
-
d
i
m
≤
r
i
m
+
Δ
r
i
m
i
=
1
…
N
,
m
=
1
…
S
-
1
(7)
r
i
m
=
p
r
i
m
+
s
i
m
∗
t
a
c
c
+
s
i
m
+
1
∗
t
d
e
c
i
=
1
…
N
,
m
=
1
…
S
-
1(3) Headway Constraints. The adjacent trains need to meet the arrival interval and the departure interval in order to run safely. In this model, one train is not allowed to be overtaken by another train, so the service order will not change along any sections of the railway line. Thus, the constraints can be written as the arrival headway and departure headway constraints for two adjacent trains, as in the following:(8)
a
i
+
1
m
-
a
i
m
≥
h
m
a
i
=
1
…
N
-
1
,
m
=
2
…
S
(9)
d
i
+
1
m
-
d
i
m
≥
h
m
d
i
=
1
…
N
-
1
,
m
=
1
…
S
-
1(4) Character of the Variable
z
i
m
(
t
). If a passenger arriving at station m within time interval t has the chance to get on train i, the passenger arriving at stationm within time interval t
-
1 has the chance to get on train i too, so the variable z
i
m
(
t
)is nonincreasing. For example, in Figure 3, if train i departs at time interval 4, z
i
m
(
1
)
=
z
i
m
(
2
)
=
z
i
m
(
3
)
=
z
i
m
(
4
)
=
1, while the remaining values are equal to 0.(10)
Hence
z
i
m
t
-
1
>
=
z
i
m
t
t
=
2
…
T
m
,
i
=
1
…
N
,
m
=
1
…
S
-
1Figure 3
Character of variablez
i
m
(
t
).(5) The Relationship between
z
i
m
(
t
)
and
d
i
m. If a train departs at the end of time intervalt, then z
i
m
(
t
)
=
1, z
i
m
(
t
+
1
)
=
0, then z
i
m
(
t
)
-
z
i
m
(
t
+
1
)
=
1, so the relationship between z
i
m
(
t
) and d
i
m can be written as formula (11). For example, in Figure 4, if traini departs at time interval 4, z
i
m
(
4
)
=
1, z
i
m
(
5
)
=
0, obviously z
i
m
(
4
)
-
z
i
m
(
5
)
=
1.(11)
d
i
m
=
∑
t
=
1
T
-
1
t
∗
z
i
m
t
-
z
i
m
t
+
1Figure 4
The relationship betweenz
i
m
(
t
) and d
i
m.(6) The Relationship between
z
i
m
(
t
)
and
L
i
m
,
n
(
t
). If the variable L
i
m
,
n
(
t
)
=
1, then the variable z
i
m
(
t
) must be equal to 1. If the variable z
i
m
(
t
)
=
0, then the variable L
i
m
,
n
(
t
) must be 0. If the variable L
i
m
,
n
(
t
)
=
0, the variable z
i
m
(
t
) is not necessarily equal to 0. The relationship between z
i
m
(
t
) and L
i
m
,
n
(
t
) can be written as the following formula:(12)
L
i
m
,
n
t
<
=
z
i
m
t
t
=
1
…
T
m
,
i
=
1
…
N
,
m
=
1
…
S
-
1
,
n
=
m
+
1
…
S(7) Train Choice Constraint. Formula (13) means that the passenger arriving at station m who wants to go to station n can only choose one train.(13)
∑
i
=
1
N
τ
i
m
,
n
∗
L
i
m
,
n
t
=
1
m
=
1
…
S
-
1
,
n
=
m
+
1
…
S(8) Train Capacity Constraints. The number of passengers on the train i after departing from station m must be less than or equal to the train capacity. This constraint can be written as formula (14). The number of passengers on train i after departing from station m is equal to the total number of passengers boarding at station m and previous stations minus the number of passengers getting off at station m and previous stations.Moreover, the number of passengers on train i after departing from station m is also equal to the number of passengers boarding at station m and previous stations who want to go to the stations after station m. Therefore, it can be written as formula (15). (14)
C
a
p
i
m
≤
C
i
i
=
1
…
N
,
m
=
1
…
S
-
1
(15)
C
a
p
i
m
=
∑
m
′
=
1
m
∑
n
=
m
′
+
1
S
∑
t
=
1
T
m
p
m
′
,
n
t
∗
L
i
m
′
,
n
t
∗
τ
i
m
′
,
n
-
∑
m
′
=
1
m
-
1
∑
n
=
m
′
+
1
m
∑
t
=
0
T
p
m
′
,
n
t
∗
L
i
m
′
,
n
t
∗
τ
i
m
′
,
n
=
∑
m
′
=
1
m
∑
n
=
m
+
1
S
∑
t
=
1
T
m
p
m
′
,
n
t
∗
L
i
m
′
,
n
t
∗
τ
i
m
′
,
n


## 3.2. Fix Service Order Allowing Overtaking Model M2

The model M2 fixes the service order at the origin station and allows adjacent trains to overtake one another. In this model, it is assumed that a train can be overtaken at most once. In order to realize the overtaking between two adjacent trains, a dummy variableq
i
,
j
m is introduced, where q
i
,
j
m equals 1 if train i can overtake train j, otherwise q
i
,
j
m equals 0. The following constraints from (16) to (25) are used to replace constraints (8) and (9): (16)
a
i
+
1
m
+
1
+
h
m
+
1
a
-
a
i
m
+
1
<
=
M
1
-
∑
k
=
1
m
q
i
,
j
k
i
=
1
…
N
-
1
,
j
=
i
+
1
,
m
=
1
…
S
-
1
(17)
a
i
-
1
m
+
1
+
h
m
+
1
a
-
a
i
+
1
m
+
1
<
=
M
1
-
∑
k
=
1
m
q
i
,
j
k
i
=
1
…
N
-
1
,
j
=
i
+
1
,
m
=
1
…
S
-
1
(18)
a
i
m
+
1
+
h
m
+
1
a
-
a
i
+
2
m
+
1
<
=
M
1
-
∑
k
=
1
m
q
i
,
j
k
i
=
1
…
N
-
1
,
j
=
i
+
1
,
m
=
1
…
S
-
1
(19)
a
i
m
+
h
m
a
-
a
i
+
1
m
<
=
M
∗
∑
k
=
1
m
-
1
q
i
,
j
k
i
=
1
…
N
-
1
,
j
=
i
+
1
,
m
=
2
…
S
(20)
d
i
+
1
m
+
h
m
d
-
d
i
m
<
=
M
1
-
∑
k
=
1
m
q
i
,
j
k
i
=
1
…
N
-
1
,
j
=
i
+
1
,
m
=
1
…
S
-
1
(21)
d
i
-
1
m
+
h
m
d
-
d
i
+
1
m
<
=
M
1
-
∑
k
=
1
m
q
i
,
j
k
i
=
1
…
N
-
1
,
j
=
i
+
1
,
m
=
1
…
S
-
1
(22)
d
i
m
+
h
m
d
-
d
i
+
2
m
<
=
M
1
-
∑
k
=
1
m
q
i
,
j
k
i
=
1
…
N
-
1
,
j
=
i
+
1
,
m
=
1
…
S
-
1
(23)
d
i
m
-
1
+
h
m
-
1
d
-
d
i
+
1
m
-
1
<
=
M
∗
∑
k
=
1
m
-
1
q
i
,
j
k
i
=
1
…
N
-
1
,
j
=
i
+
1
,
m
=
2
…
S
(24)
∑
m
=
2
S
-
1
q
i
,
j
m
<
=
1
i
=
1
…
N
,
j
=
i
+
1
(25)
q
i
,
j
m
∈
0,1The above constraints also adjust to the situation in which the trains do not overtake each other. For example, if the trains do not overtake each other,∑
k
=
1
m
q
i
,
j
k
=
0, then constraints (19) and (23) can secure the safety arrival interval and the safety departure interval, while the other constraints will always be satisfied when q
i
,
j
m is equal to 0.If traini
+
1 overtakes train i at station m, i.e., ∑
k
=
1
m
q
i
,
j
k
=
1, ∑
k
=
1
m
-
1
q
i
,
j
k
=
0, as illustrated in Figure 5, then constraints (19) and (23) can secure the safety interval for train i and traini+1 before the overtaking stationm. When traini+1 overtakes train i at station m, the service order becomesi-1, i+1, i, i+2. Constraints (16) and (20) can secure the safety interval for train i and traini+1 after the overtaking station m. Likewise, the constraints (17) and (21) can secure the safety interval for traini−1 and traini+1 after the overtaking stationm, and the constraints (18) and (22) can secure the safety interval for train i and traini+2 after the overtaking stationm. The constraints (24) ensure that train i can be overtaken by traini+1 at most once.Figure 5
Diagram of train overtaking.


## 3.3. Variable Service Order Zero Overtaking Model M3

Model M3 does not fix the service order, and zero overtaking is allowed. A dummy variablex
i
j
∈
{
0,1
} is introduced, which represents the running order of train i and train j
.Since this order does not change when train runs along the railway line, so the value of this variable for any two trains is the same in all sections. If trainjruns after train i
,then x
i
j
=
1, otherwise, x
i
j
=
0. Now the headway constraints of Model 1 can be reformulated as constraints from (26) to (29).(26)
a
j
m
-
a
i
m
≥
h
m
a
·
x
i
j
-
M
·
1
-
x
i
j
i
=
1,2
…
N
,
j
=
1,2
…
N
(27)
a
i
m
-
a
j
m
≥
h
m
a
·
1
-
x
i
j
-
M
·
x
i
j
i
=
1,2
…
N
,
j
=
1,2
…
N
(28)
d
j
m
-
d
i
m
≥
h
m
d
·
x
i
j
-
M
·
1
-
x
i
j
i
=
1,2
…
N
,
j
=
1,2
…
N
(29)
d
j
m
-
d
i
m
≥
h
m
d
·
x
i
j
-
M
·
1
-
x
i
j
i
=
1,2
…
N
,
j
=
1,2
…
N


## 3.4. Variable Service Order Allowing Overtaking Model M4

Model M4 does not fix the service order at the origin station and allows arbitrary trains to overtake one another. Two new binary variables are introduced to represent the order of train arrivals and departures, namelyx
i
j
m and y
i
j
m
+
1. As is shown in Figure 6(a), if d
j
m
-
d
i
m
>
0, namely trainjdeparts from stationmafter traini, then x
i
j
m
=
0, otherwise, x
i
j
m
=
1. As is shown in Figure 6(b), if a
j
m
+
1
-
a
i
m
+
1
>
0, namely if trainj arrives at stationm+1 after traini, then y
i
j
m
+
1
=
0, otherwise y
i
j
m
+
1
=
1.Figure 6
Safety interval constraints.The safety constraints of model M3 can be written as equations containing the service order variablesx
i
j
m and y
i
j
m
+
1, as shown in (30) and (31). These two kinds of constraints can be used to ensure the safety departure interval and safety arrival interval, in the situation where the service order at the origin station is not fixed.(30)
h
m
d
≤
d
j
m
-
d
i
m
+
T
∗
x
i
j
m
≤
T
-
h
m
d
i
,
j
=
1
…
N
,
j
>
i
,
m
=
1
…
S
-
1
(31)
h
m
a
≤
a
j
m
-
a
i
m
+
T
∗
y
i
j
m
≤
T
-
h
m
a
i
,
j
=
1
…
N
,
j
>
i
,
m
=
2
…
SIn order to illustrate how constraints (30) and (31) ensure the safety interval and allow arbitrary trains to overtake one another, the following proof is given.Proof of Constraint (30).
Situation 1. Trainj departs from station m after train i
Left-Hand Side of Constraint (30). As shown in Figure 6(a), if trainj departs from stationm after train i, then x
i
j
m
=
0; in order to meet the safety departure interval, d
j
m
-
d
i
m
≥
h
m
d is necessary.
Right-Hand Hand of Constraint (30). Let m
=
S
-
1; then the equation d
j
S
-
1
+
r
j
S
-
1
=
a
j
S is always satisfied, where a
j
S is the arrival time at station s of train j.
Becausea
j
S
≤
T, we have d
j
S
-
1
+
r
j
S
-
1
=
a
j
S
≤
T;
Becauser
S
-
1
n
>
=
h
S
-
1
d (the running time is usually larger than the safety interval), we have the equation d
j
S
-
1
<
=
T
-
r
j
S
-
1
<
=
T
-
h
s
-
1
d;
Therefore, at stationS−1, d
j
S
-
1
-
d
i
S
-
1
≤
T
-
h
-
d
i
S
-
1
<
=
T
-
h
s
-
1
d;
Whenm
≤
S
-
1, d
j
m
<
d
j
S
-
1
≤
T
-
h
s
-
1
d, d
i
m
≥
0, so d
j
m
-
d
i
m
<
T
-
h
m
d;
Therefore, the consistency of the constraint (30) is proved.
Situation 2. Train i departs from station m after train j
If traini departs from station m after train j, in order to meet the safety departure interval, d
i
m
-
d
j
m
≥
h
m
d is necessary. Multiplying both sides of the equation by −1, then addingT, we have the equation d
j
m
-
d
i
m
+
T
≤
T
-
h
m
d, namely, the right-hand side of (30) is proved.
Because traini departs from stationm after train j, according to the proof above, d
i
m
-
d
j
m
<
=
T
-
h
m
d must be satisfied. Multiplying both sides of the equation by −1, then addingT, we have the equation d
j
m
-
d
i
m
+
T
>
=
h
m
d, so the left-hand side of (30) is proved.Proof of the Constraint (31).
Situation 1. Train j arrives at station m after train i
Left-Hand Side of Constraint (31). As shown in Figure 6(a), if trainj arrives at stationm after traini, in order to meet the safety arrival interval, a
j
m
-
a
i
m
≥
h
m
a is necessary.
Right-Hand Side of Constraint (31). Because a
j
m
≤
T and a
i
m
=
d
i
m
-
1
+
r
i
m
-
1
≥
h
m
a, therefore, a
j
m
-
a
i
m
≤
T
-
h
m
a is always satisfied.
Situation 2. Train i arrives at station m after train j
If traini arrives at stationm after trainj, in order to meet the safety arrival interval, a
i
m
-
a
j
m
≥
h
m
a is necessary. Multiplying both sides of the equation by −1, then addingT, we have the equation a
j
m
-
a
i
m
+
T
≤
T
-
h
m
a, thus the right-hand side of constraint (31) is proved.
If traini arrives at stationm after trainj, then, according to the proof above, a
i
m
-
a
j
m
<
=
T
-
h
m
a is necessary. Multiplying both sides of the equation by −1, then addingT, we have the equation a
j
m
-
a
i
m
+
T
≥
h
m
a, so the left-hand side of constraint (31) is proved.According to the proof above, we can conclude that constraints (30) and (31) can ensure the safety departure interval and safety arrival interval of two arbitrary trains. These two sets of constraints also allow trains to overtake each other at stations.


## 4. Case Study

### 4.1. Case Description

In this section, an illustrative case study is provided to validate the effectiveness of the proposed model. The high-speed railway system from Shanghai-Hangzhou is selected. As is shown in Figure7, there are nine stations on this line, Hangzhoudong, Yuhang, Hainingxi, Tongxiang, Jiaxingnan, Jiashannan, Jinshanbei, Songjiangnan, and Shanghai Hongqiao, which are, respectively, marked as 1, 2, 3, 4, 5, 6, 7, 8, and 9. The pure running time of each section is shown in Table 5. The dynamic passenger demand of the Shanghai-Hangzhou intercity high-speed rail in China provides the input data to examine the proposed models. The study period is 8:00-9:00 and the passenger arrival rate of station 1 during this period is shown in Figure 8. The whole dataset can be found. The passenger demand of the other stations is similar to that of station 1, but the numbers are relatively small. Through the passenger arrival rate curve, we can find how the passenger demand changes with time. Eight trains are planned during this period and they are designated ast1,t2,t3,t4,t5,t6,t7, andt8. The line planning is illustrated in Figure 9.Table 5
Pure running time of each section.
Section
1-2
2-3
3-4
4-5
5-6
6-7
7-8
8-9
Pure running time (min)
5
6
5
6
5
7
6
5Figure 7
Shanghai-Hangzhou high-speed railway.Figure 8
Passenger arrival rate at stations.Figure 9
Line planning.The parameters of the model are set as follows:ω
1
=
ω
2
=
1, acceleration time is 2 min, deceleration time is 3 min, safety arrival time for every station is 3 min, safety departure time for every station is 3 min, the minimum dwell time at each station is 2 min, the deviation of dwell time at station 1, station 2, and station 4 is 4 min, the deviation of dwell time at the other stations is 0 min, and the deviation of running time is 0 min. The capacity of each train is 600.The four models are all mixed-integer quadratic programming, so the ILOG CPLEX (version 12.6) is used to solve the problem running on CPU i3-3110M with 2.4 GHz and 4G RAM.


### 4.2. Results

#### 4.2.1. Overall Results

The results of the four models are shown in Table6, and the time and space diagrams of the four models are shown in Figures 10(a)–10(d). The timetables of four models are listed in Appendixes.Table 6
Solution comparison of the four models.
Total train running time (min)
Total passenger travel time (min)
Optimal service order
Overtake information
Times
Trains
Period
Station
M1
591
196570
t1, t2, t3, t4, t5, t6, t7, t8
0
-
-
-
M2
593
190330
t1, t2, t3, t4, t5, t6,t7,t8
1
t4/t3
9:10-9:20
6
M3
591
190550
t4, t1, t6, t5, t3, t2, t7, t8
0
-
-
-
M4
593
187962
t2, t1, t6, t5, t3, t4, t7, t8
1
t4/t3
9:25-9:35
6Figure 10
(a)
Time and space diagram based on M1
(b)
Time and space diagram based on M2
(c)
Time and space diagram based on M3
(d)
Time and space diagram based on M4From Figures10(a)–10(d), we can find that the service order or allow overtaking condition can significantly influence the optimal result. For example, in model M1, where the service order is fixed and overtaking is not allowed, the result order is exactly the same as the original order, namely,t1,t2,t3,t4,t5,t6,t7,t8. In model M2, where the service order from the first station is fixed and overtaking between adjacent trains is allowed, the optimal solution shows the service order at station 1 in M2 is the same as M1, namely,t1,t2,t3,t4,t5,t6,t7. Traint3 overtakes train t
4 at station 6, meaning that the service order changes tot1,t5,t6,t4,t3,t2,t7,t8 after station 6. In model M3, the service order is not fixed and overtaking is not allowed, the optimal service order becomest4,t2,t6,t1,t3,t5,t7,t8. In model M4, the service order is not fixed and overtaking is allowed for any pair of trains. The result order of trains at station 1 is changed tot2,t1,t6,t5,t3,t4,t7,t8. After station 6, the service order is changed tot2,t1,t6,t5,t4,t3,t7,t8. The results show that model M4 can effectively adjust the service order according to the dynamic passenger demand. We can also easily find that the optimal solution of model Mi-1 is also a feasible solution of Model Mi.


#### 4.2.2. The Influence of Service Order and Overtaking on Passenger Travel Time

Table6 shows that the total passenger travel times are 196570 min in M1, 190330 min in M2, 189832 min in M3, and 187962 min in M4, respectively. Compared with fixed order zero overtaking model M1, the total passenger travel time of the variable order allowing overtaking model M4 is reduced by 4.4%. Compared with fixed order zero overtaking M1, the objective value of variable order zero overtaking model M3 is reduced by 3.4%. And compared with fixed order zero overtaking model M1, the objective value of fixed order allow overtaking model M2 is reduced by 3.2%. All of the results above show that model M4 performs best among the four models, which demonstrates that the timetable based on M4 can effectively reduce the total travel time of passengers and meet passengers demand better. The reason could be that allowing overtaking of trains not only decreases the running time of fully occupied passenger trains, but also reduces passengers’ waiting time.Moreover, the effects of service order and train overtaking condition on the quality of the solution are different. In Figure11, by comparing the total passenger travel times of M1 and M3, we can see that if overtaking is not allowed, the value decreases by 3.4% by optimize the service order. In contrast, by comparing the value of M2 and M4, we can see that if overtaking is allowed, the value decreases by 1.08%. With regard to the train overtaking condition, let us fix the departure service order, then overtaking decreases the total passenger travel time by 3.2% (M1->M2). If service order is allowed to change, overtaking decreases the total passenger travel time by only 1.0% (M3->M4). The combined optimization of train overtaking and service order can reduce the total passenger travel time by 4.22% (M1->M4). In summary, either allowing overtaking or changing order can optimize the quality of timetable from total passenger travel time. However, the influence of changing order on passenger travel time is more significant than overtaking condition.Figure 11
The effects of service order and train overtaking on the quality of the solution.


#### 4.2.3. The Influence of Service Order and Overtaking on Train Occupancy

Table7 shows the number of passengers in each train after it departs from different stations. From Table 7, we can obtain the following findings.Table 7
Comparison of the number of passengers in each train after departing from the station.
Model
Station
Train
t
1
t
2
t
3
t
4
t
5
t
6
t
7
t
8
total
M1
1
307
160
126
600
250
192
436
110
2181
2
307
160
161
600
250
225
436
141
2280
3
307
160
161
600
312
225
436
165
2366
4
285
161
161
600
312
286
417
231
2453
5
254
148
142
600
258
241
408
223
2274
6
254
148
139
600
258
241
600
306
2546
7
254
129
139
600
247
241
600
287
2497
8
254
129
118
600
247
241
549
271
2409
Average
278
149
143
600
267
237
485
217
19006
M2
1
477
232
65
577
120
176
424
110
2181
2
477
232
123
577
120
193
424
134
2280
3
477
232
123
577
182
193
424
158
2366
4
460
260
123
577
182
222
408
221
2453
5
415
253
92
551
167
184
400
212
2274
6
415
253
131
551
167
184
566
279
2546
7
415
227
131
551
163
184
566
260
2497
8
415
227
100
551
163
184
520
249
2409
Average
444
240
111
564
158
190
467
203
19006
M3
1
436
179
189
470
312
127
357
111
2181
2
436
179
219
470
312
179
357
128
2280
3
436
179
219
470
379
179
357
147
2366
4
425
182
219
470
379
219
350
209
2453
5
397
186
207
418
354
185
332
195
2274
6
397
186
305
418
354
185
437
264
2546
7
397
160
305
418
351
185
437
244
2497
8
397
160
250
418
351
185
408
240
2409
Average
415
176
239
444
349
181
379
192
19006
M4
1
342
236
114
592
351
185
247
114
2181
2
342
236
144
592
351
237
247
131
2280
3
342
236
144
592
400
237
247
168
2366
4
353
220
144
592
400
285
229
230
2453
5
328
198
130
566
376
250
215
211
2274
6
328
198
255
566
376
250
293
280
2546
7
328
185
255
566
359
250
293
261
2497
8
328
185
204
566
359
250
260
257
2409
Average
336
212
174
579
372
243
254
207
19006First, the number of passengers during each section of each model is the same. It means that all passenger demand is satisfied. However, the number of passengers in each train is different. In particular,t4 is always fully loaded with passengers from the first station. This is because traint4 is the fastest train with only one stop. By assigning more passengers to fast trains, the total travel time of the passengers can be reduced. Train t
4 has the least number of train stops, namely, three, so passengers from stations 1, 5, 9 would prefer to take t
4 to reduce their travel times. Similarly, train t
1 also has a relatively high occupancy with four train stops. Train t
2 has the third highest occupancy. Train t
3 has low occupancy. Figure 12 illustrates the relationship between train stops and the train occupancy. It shows that the train occupancy is related to the total number of stops of the train, the less the train stops, the larger the train occupancy is.Figure 12
The relationship between the number of stops and the number of passengers in trains in the optimal solution of M4.The second finding is obvious that a full loaded train overtaking a less loaded train can reduce the total travel time of passengers. Lett4 overtake other trains with fewer passengers, e.g.,t3 can reduce the travel time of passengers in traint4; meanwhile, this strategy will not increase the waiting time at stations, because no more passengers can boardt4 due to the capacity of the train, which proves the inference.


#### 4.2.4. The Influence of Service Order and Overtaking on Train Running Time

Table6 shows that the total running times of trains in the four models are 591 min, 593 min, 591 min and 593 min, respectively. This result suggests that the effects of demand-driven timetabling could decrease the benefits for train operators by overtaking, due to longer running times, which usually means higher operating costs. A trade-off should be made between minimizing the travel times of trains and passengers. The decision should be made according to the total benefits.


#### 4.2.5. Computation Effort

On the aspect of model computation time, we show in Table8 that model with variable order has much longer computation times than fixed order. Model M4 has a computation time of 30400 seconds, which is the longest, compared with 94 seconds for M1, 1007 seconds for M2, and 2092 seconds for M3. This is because M3 and M4 are designed not only to obtain optimal departure and arrival times for each train, but also to find an optimal service order, which in turn increases the number of variables and constraints. This increases the complexity of the model and leads to longer computation times. A combination of optimization of train overtaking and changing order can optimize the timetable more significantly. However, considering the computation effort, it may not be cost beneficial.Table 8
Model computation times.
Computation time
The number of variables
M1
94
35954
M2
1007
36320
M3
2092
36361
M4
30400
36402


## 4.1. Case Description

In this section, an illustrative case study is provided to validate the effectiveness of the proposed model. The high-speed railway system from Shanghai-Hangzhou is selected. As is shown in Figure7, there are nine stations on this line, Hangzhoudong, Yuhang, Hainingxi, Tongxiang, Jiaxingnan, Jiashannan, Jinshanbei, Songjiangnan, and Shanghai Hongqiao, which are, respectively, marked as 1, 2, 3, 4, 5, 6, 7, 8, and 9. The pure running time of each section is shown in Table 5. The dynamic passenger demand of the Shanghai-Hangzhou intercity high-speed rail in China provides the input data to examine the proposed models. The study period is 8:00-9:00 and the passenger arrival rate of station 1 during this period is shown in Figure 8. The whole dataset can be found. The passenger demand of the other stations is similar to that of station 1, but the numbers are relatively small. Through the passenger arrival rate curve, we can find how the passenger demand changes with time. Eight trains are planned during this period and they are designated ast1,t2,t3,t4,t5,t6,t7, andt8. The line planning is illustrated in Figure 9.Table 5
Pure running time of each section.
Section
1-2
2-3
3-4
4-5
5-6
6-7
7-8
8-9
Pure running time (min)
5
6
5
6
5
7
6
5Figure 7
Shanghai-Hangzhou high-speed railway.Figure 8
Passenger arrival rate at stations.Figure 9
Line planning.The parameters of the model are set as follows:ω
1
=
ω
2
=
1, acceleration time is 2 min, deceleration time is 3 min, safety arrival time for every station is 3 min, safety departure time for every station is 3 min, the minimum dwell time at each station is 2 min, the deviation of dwell time at station 1, station 2, and station 4 is 4 min, the deviation of dwell time at the other stations is 0 min, and the deviation of running time is 0 min. The capacity of each train is 600.The four models are all mixed-integer quadratic programming, so the ILOG CPLEX (version 12.6) is used to solve the problem running on CPU i3-3110M with 2.4 GHz and 4G RAM.


## 4.2. Results

### 4.2.1. Overall Results

The results of the four models are shown in Table6, and the time and space diagrams of the four models are shown in Figures 10(a)–10(d). The timetables of four models are listed in Appendixes.Table 6
Solution comparison of the four models.
Total train running time (min)
Total passenger travel time (min)
Optimal service order
Overtake information
Times
Trains
Period
Station
M1
591
196570
t1, t2, t3, t4, t5, t6, t7, t8
0
-
-
-
M2
593
190330
t1, t2, t3, t4, t5, t6,t7,t8
1
t4/t3
9:10-9:20
6
M3
591
190550
t4, t1, t6, t5, t3, t2, t7, t8
0
-
-
-
M4
593
187962
t2, t1, t6, t5, t3, t4, t7, t8
1
t4/t3
9:25-9:35
6Figure 10
(a)
Time and space diagram based on M1
(b)
Time and space diagram based on M2
(c)
Time and space diagram based on M3
(d)
Time and space diagram based on M4From Figures10(a)–10(d), we can find that the service order or allow overtaking condition can significantly influence the optimal result. For example, in model M1, where the service order is fixed and overtaking is not allowed, the result order is exactly the same as the original order, namely,t1,t2,t3,t4,t5,t6,t7,t8. In model M2, where the service order from the first station is fixed and overtaking between adjacent trains is allowed, the optimal solution shows the service order at station 1 in M2 is the same as M1, namely,t1,t2,t3,t4,t5,t6,t7. Traint3 overtakes train t
4 at station 6, meaning that the service order changes tot1,t5,t6,t4,t3,t2,t7,t8 after station 6. In model M3, the service order is not fixed and overtaking is not allowed, the optimal service order becomest4,t2,t6,t1,t3,t5,t7,t8. In model M4, the service order is not fixed and overtaking is allowed for any pair of trains. The result order of trains at station 1 is changed tot2,t1,t6,t5,t3,t4,t7,t8. After station 6, the service order is changed tot2,t1,t6,t5,t4,t3,t7,t8. The results show that model M4 can effectively adjust the service order according to the dynamic passenger demand. We can also easily find that the optimal solution of model Mi-1 is also a feasible solution of Model Mi.


### 4.2.2. The Influence of Service Order and Overtaking on Passenger Travel Time

Table6 shows that the total passenger travel times are 196570 min in M1, 190330 min in M2, 189832 min in M3, and 187962 min in M4, respectively. Compared with fixed order zero overtaking model M1, the total passenger travel time of the variable order allowing overtaking model M4 is reduced by 4.4%. Compared with fixed order zero overtaking M1, the objective value of variable order zero overtaking model M3 is reduced by 3.4%. And compared with fixed order zero overtaking model M1, the objective value of fixed order allow overtaking model M2 is reduced by 3.2%. All of the results above show that model M4 performs best among the four models, which demonstrates that the timetable based on M4 can effectively reduce the total travel time of passengers and meet passengers demand better. The reason could be that allowing overtaking of trains not only decreases the running time of fully occupied passenger trains, but also reduces passengers’ waiting time.Moreover, the effects of service order and train overtaking condition on the quality of the solution are different. In Figure11, by comparing the total passenger travel times of M1 and M3, we can see that if overtaking is not allowed, the value decreases by 3.4% by optimize the service order. In contrast, by comparing the value of M2 and M4, we can see that if overtaking is allowed, the value decreases by 1.08%. With regard to the train overtaking condition, let us fix the departure service order, then overtaking decreases the total passenger travel time by 3.2% (M1->M2). If service order is allowed to change, overtaking decreases the total passenger travel time by only 1.0% (M3->M4). The combined optimization of train overtaking and service order can reduce the total passenger travel time by 4.22% (M1->M4). In summary, either allowing overtaking or changing order can optimize the quality of timetable from total passenger travel time. However, the influence of changing order on passenger travel time is more significant than overtaking condition.Figure 11
The effects of service order and train overtaking on the quality of the solution.


### 4.2.3. The Influence of Service Order and Overtaking on Train Occupancy

Table7 shows the number of passengers in each train after it departs from different stations. From Table 7, we can obtain the following findings.Table 7
Comparison of the number of passengers in each train after departing from the station.
Model
Station
Train
t
1
t
2
t
3
t
4
t
5
t
6
t
7
t
8
total
M1
1
307
160
126
600
250
192
436
110
2181
2
307
160
161
600
250
225
436
141
2280
3
307
160
161
600
312
225
436
165
2366
4
285
161
161
600
312
286
417
231
2453
5
254
148
142
600
258
241
408
223
2274
6
254
148
139
600
258
241
600
306
2546
7
254
129
139
600
247
241
600
287
2497
8
254
129
118
600
247
241
549
271
2409
Average
278
149
143
600
267
237
485
217
19006
M2
1
477
232
65
577
120
176
424
110
2181
2
477
232
123
577
120
193
424
134
2280
3
477
232
123
577
182
193
424
158
2366
4
460
260
123
577
182
222
408
221
2453
5
415
253
92
551
167
184
400
212
2274
6
415
253
131
551
167
184
566
279
2546
7
415
227
131
551
163
184
566
260
2497
8
415
227
100
551
163
184
520
249
2409
Average
444
240
111
564
158
190
467
203
19006
M3
1
436
179
189
470
312
127
357
111
2181
2
436
179
219
470
312
179
357
128
2280
3
436
179
219
470
379
179
357
147
2366
4
425
182
219
470
379
219
350
209
2453
5
397
186
207
418
354
185
332
195
2274
6
397
186
305
418
354
185
437
264
2546
7
397
160
305
418
351
185
437
244
2497
8
397
160
250
418
351
185
408
240
2409
Average
415
176
239
444
349
181
379
192
19006
M4
1
342
236
114
592
351
185
247
114
2181
2
342
236
144
592
351
237
247
131
2280
3
342
236
144
592
400
237
247
168
2366
4
353
220
144
592
400
285
229
230
2453
5
328
198
130
566
376
250
215
211
2274
6
328
198
255
566
376
250
293
280
2546
7
328
185
255
566
359
250
293
261
2497
8
328
185
204
566
359
250
260
257
2409
Average
336
212
174
579
372
243
254
207
19006First, the number of passengers during each section of each model is the same. It means that all passenger demand is satisfied. However, the number of passengers in each train is different. In particular,t4 is always fully loaded with passengers from the first station. This is because traint4 is the fastest train with only one stop. By assigning more passengers to fast trains, the total travel time of the passengers can be reduced. Train t
4 has the least number of train stops, namely, three, so passengers from stations 1, 5, 9 would prefer to take t
4 to reduce their travel times. Similarly, train t
1 also has a relatively high occupancy with four train stops. Train t
2 has the third highest occupancy. Train t
3 has low occupancy. Figure 12 illustrates the relationship between train stops and the train occupancy. It shows that the train occupancy is related to the total number of stops of the train, the less the train stops, the larger the train occupancy is.Figure 12
The relationship between the number of stops and the number of passengers in trains in the optimal solution of M4.The second finding is obvious that a full loaded train overtaking a less loaded train can reduce the total travel time of passengers. Lett4 overtake other trains with fewer passengers, e.g.,t3 can reduce the travel time of passengers in traint4; meanwhile, this strategy will not increase the waiting time at stations, because no more passengers can boardt4 due to the capacity of the train, which proves the inference.


### 4.2.4. The Influence of Service Order and Overtaking on Train Running Time

Table6 shows that the total running times of trains in the four models are 591 min, 593 min, 591 min and 593 min, respectively. This result suggests that the effects of demand-driven timetabling could decrease the benefits for train operators by overtaking, due to longer running times, which usually means higher operating costs. A trade-off should be made between minimizing the travel times of trains and passengers. The decision should be made according to the total benefits.


### 4.2.5. Computation Effort

On the aspect of model computation time, we show in Table8 that model with variable order has much longer computation times than fixed order. Model M4 has a computation time of 30400 seconds, which is the longest, compared with 94 seconds for M1, 1007 seconds for M2, and 2092 seconds for M3. This is because M3 and M4 are designed not only to obtain optimal departure and arrival times for each train, but also to find an optimal service order, which in turn increases the number of variables and constraints. This increases the complexity of the model and leads to longer computation times. A combination of optimization of train overtaking and changing order can optimize the timetable more significantly. However, considering the computation effort, it may not be cost beneficial.Table 8
Model computation times.
Computation time
The number of variables
M1
94
35954
M2
1007
36320
M3
2092
36361
M4
30400
36402


## 4.2.1. Overall Results

The results of the four models are shown in Table6, and the time and space diagrams of the four models are shown in Figures 10(a)–10(d). The timetables of four models are listed in Appendixes.Table 6
Solution comparison of the four models.
Total train running time (min)
Total passenger travel time (min)
Optimal service order
Overtake information
Times
Trains
Period
Station
M1
591
196570
t1, t2, t3, t4, t5, t6, t7, t8
0
-
-
-
M2
593
190330
t1, t2, t3, t4, t5, t6,t7,t8
1
t4/t3
9:10-9:20
6
M3
591
190550
t4, t1, t6, t5, t3, t2, t7, t8
0
-
-
-
M4
593
187962
t2, t1, t6, t5, t3, t4, t7, t8
1
t4/t3
9:25-9:35
6Figure 10
(a)
Time and space diagram based on M1
(b)
Time and space diagram based on M2
(c)
Time and space diagram based on M3
(d)
Time and space diagram based on M4From Figures10(a)–10(d), we can find that the service order or allow overtaking condition can significantly influence the optimal result. For example, in model M1, where the service order is fixed and overtaking is not allowed, the result order is exactly the same as the original order, namely,t1,t2,t3,t4,t5,t6,t7,t8. In model M2, where the service order from the first station is fixed and overtaking between adjacent trains is allowed, the optimal solution shows the service order at station 1 in M2 is the same as M1, namely,t1,t2,t3,t4,t5,t6,t7. Traint3 overtakes train t
4 at station 6, meaning that the service order changes tot1,t5,t6,t4,t3,t2,t7,t8 after station 6. In model M3, the service order is not fixed and overtaking is not allowed, the optimal service order becomest4,t2,t6,t1,t3,t5,t7,t8. In model M4, the service order is not fixed and overtaking is allowed for any pair of trains. The result order of trains at station 1 is changed tot2,t1,t6,t5,t3,t4,t7,t8. After station 6, the service order is changed tot2,t1,t6,t5,t4,t3,t7,t8. The results show that model M4 can effectively adjust the service order according to the dynamic passenger demand. We can also easily find that the optimal solution of model Mi-1 is also a feasible solution of Model Mi.


## 4.2.2. The Influence of Service Order and Overtaking on Passenger Travel Time

Table6 shows that the total passenger travel times are 196570 min in M1, 190330 min in M2, 189832 min in M3, and 187962 min in M4, respectively. Compared with fixed order zero overtaking model M1, the total passenger travel time of the variable order allowing overtaking model M4 is reduced by 4.4%. Compared with fixed order zero overtaking M1, the objective value of variable order zero overtaking model M3 is reduced by 3.4%. And compared with fixed order zero overtaking model M1, the objective value of fixed order allow overtaking model M2 is reduced by 3.2%. All of the results above show that model M4 performs best among the four models, which demonstrates that the timetable based on M4 can effectively reduce the total travel time of passengers and meet passengers demand better. The reason could be that allowing overtaking of trains not only decreases the running time of fully occupied passenger trains, but also reduces passengers’ waiting time.Moreover, the effects of service order and train overtaking condition on the quality of the solution are different. In Figure11, by comparing the total passenger travel times of M1 and M3, we can see that if overtaking is not allowed, the value decreases by 3.4% by optimize the service order. In contrast, by comparing the value of M2 and M4, we can see that if overtaking is allowed, the value decreases by 1.08%. With regard to the train overtaking condition, let us fix the departure service order, then overtaking decreases the total passenger travel time by 3.2% (M1->M2). If service order is allowed to change, overtaking decreases the total passenger travel time by only 1.0% (M3->M4). The combined optimization of train overtaking and service order can reduce the total passenger travel time by 4.22% (M1->M4). In summary, either allowing overtaking or changing order can optimize the quality of timetable from total passenger travel time. However, the influence of changing order on passenger travel time is more significant than overtaking condition.Figure 11
The effects of service order and train overtaking on the quality of the solution.


## 4.2.3. The Influence of Service Order and Overtaking on Train Occupancy

Table7 shows the number of passengers in each train after it departs from different stations. From Table 7, we can obtain the following findings.Table 7
Comparison of the number of passengers in each train after departing from the station.
Model
Station
Train
t
1
t
2
t
3
t
4
t
5
t
6
t
7
t
8
total
M1
1
307
160
126
600
250
192
436
110
2181
2
307
160
161
600
250
225
436
141
2280
3
307
160
161
600
312
225
436
165
2366
4
285
161
161
600
312
286
417
231
2453
5
254
148
142
600
258
241
408
223
2274
6
254
148
139
600
258
241
600
306
2546
7
254
129
139
600
247
241
600
287
2497
8
254
129
118
600
247
241
549
271
2409
Average
278
149
143
600
267
237
485
217
19006
M2
1
477
232
65
577
120
176
424
110
2181
2
477
232
123
577
120
193
424
134
2280
3
477
232
123
577
182
193
424
158
2366
4
460
260
123
577
182
222
408
221
2453
5
415
253
92
551
167
184
400
212
2274
6
415
253
131
551
167
184
566
279
2546
7
415
227
131
551
163
184
566
260
2497
8
415
227
100
551
163
184
520
249
2409
Average
444
240
111
564
158
190
467
203
19006
M3
1
436
179
189
470
312
127
357
111
2181
2
436
179
219
470
312
179
357
128
2280
3
436
179
219
470
379
179
357
147
2366
4
425
182
219
470
379
219
350
209
2453
5
397
186
207
418
354
185
332
195
2274
6
397
186
305
418
354
185
437
264
2546
7
397
160
305
418
351
185
437
244
2497
8
397
160
250
418
351
185
408
240
2409
Average
415
176
239
444
349
181
379
192
19006
M4
1
342
236
114
592
351
185
247
114
2181
2
342
236
144
592
351
237
247
131
2280
3
342
236
144
592
400
237
247
168
2366
4
353
220
144
592
400
285
229
230
2453
5
328
198
130
566
376
250
215
211
2274
6
328
198
255
566
376
250
293
280
2546
7
328
185
255
566
359
250
293
261
2497
8
328
185
204
566
359
250
260
257
2409
Average
336
212
174
579
372
243
254
207
19006First, the number of passengers during each section of each model is the same. It means that all passenger demand is satisfied. However, the number of passengers in each train is different. In particular,t4 is always fully loaded with passengers from the first station. This is because traint4 is the fastest train with only one stop. By assigning more passengers to fast trains, the total travel time of the passengers can be reduced. Train t
4 has the least number of train stops, namely, three, so passengers from stations 1, 5, 9 would prefer to take t
4 to reduce their travel times. Similarly, train t
1 also has a relatively high occupancy with four train stops. Train t
2 has the third highest occupancy. Train t
3 has low occupancy. Figure 12 illustrates the relationship between train stops and the train occupancy. It shows that the train occupancy is related to the total number of stops of the train, the less the train stops, the larger the train occupancy is.Figure 12
The relationship between the number of stops and the number of passengers in trains in the optimal solution of M4.The second finding is obvious that a full loaded train overtaking a less loaded train can reduce the total travel time of passengers. Lett4 overtake other trains with fewer passengers, e.g.,t3 can reduce the travel time of passengers in traint4; meanwhile, this strategy will not increase the waiting time at stations, because no more passengers can boardt4 due to the capacity of the train, which proves the inference.


## 4.2.4. The Influence of Service Order and Overtaking on Train Running Time

Table6 shows that the total running times of trains in the four models are 591 min, 593 min, 591 min and 593 min, respectively. This result suggests that the effects of demand-driven timetabling could decrease the benefits for train operators by overtaking, due to longer running times, which usually means higher operating costs. A trade-off should be made between minimizing the travel times of trains and passengers. The decision should be made according to the total benefits.


## 4.2.5. Computation Effort

On the aspect of model computation time, we show in Table8 that model with variable order has much longer computation times than fixed order. Model M4 has a computation time of 30400 seconds, which is the longest, compared with 94 seconds for M1, 1007 seconds for M2, and 2092 seconds for M3. This is because M3 and M4 are designed not only to obtain optimal departure and arrival times for each train, but also to find an optimal service order, which in turn increases the number of variables and constraints. This increases the complexity of the model and leads to longer computation times. A combination of optimization of train overtaking and changing order can optimize the timetable more significantly. However, considering the computation effort, it may not be cost beneficial.Table 8
Model computation times.
Computation time
The number of variables
M1
94
35954
M2
1007
36320
M3
2092
36361
M4
30400
36402


## 5. Sensitivity Analysis

In this section, sensitivity of two parameters on the objective is discussed.


### 5.1. Effect of Travel Time Weight

In the model, there are two parameters representing the travel time weight, namely,ω
1 and ω
2, which reflect the passengers’ perception of waiting time at stations and in-vehicle time, respectively. In general, passengers perceived time lapse on waiting time at stations is larger than the in-vehicle time [60]. In other words, passengers feel that time is longer when they wait for an available train at the station than in a vehicle. In order to have a deep insight on the effect of the two weights on the objective of the model. Let ω
2
=
1, and change the value of ω
1 to 1, 1.5, 2, and 2.5, respectively. The objectives of the model M1 to M4 are shown in Figures 13–16 (The EPGAP in the experiments are all equal to 0). It shows that, with the increasing value of the weight of passengers’ waiting time at stations, the objective, perceived waiting time of the passenger and perceived in-vehicle time increase. However, the realized (unweighted) passenger waiting time decreases. It is easy to explain, if the value of ω
1 is larger than ω
2, it indicates that the objective tends to minimize the passenger waiting time, then trains would be arranged to ensure this objective, which may increase the total travel time of all passengers. Moreover, the performance of different models is different. For examplee, for model 1, with the increasing value of the weights, either passengers’ waiting time or passengers’ in-vehicle time does not change too much. However, for other models, the value of passengers’ waiting time and in-vehicle time changes significantly.Figure 13
Results of value of objective with different weights.Figure 14
Results of weighted passengers’ waiting time with different weights.Figure 15
Results of realized passengers’ waiting time with different weights.Figure 16
Results of passengers’ in-vehicle time with different weights.


### 5.2. Effect of EPGAP

EPGAP is a parameter in the algorithm of branch and bound. The parameter is calculated by the difference of upper bound and lower bound divided by the upper bound. This parameter has big influence on the optimization effect and computation time. The smaller the value of EPGAP is, the closer the upper bound reaches the optimal value, and the longer the computation time and vice versa is. Table9 shows the model computation time and solution under different value of EPGAP. It shows that when the value of EPGAP equals 0, the objective is the best, but the computation time is the longest. With the increasing value of EPGAP, upper bound of each model increases. That is to say, the value of objective increases. Moreover, the difference between the value of the upper bound of each model and under different values of EPGAP is large. With the increasing value of EPGAP, computation time decreases. When the value of EPGAP equals 0, computation time is the longest. However, when the value of EPGAP equals 0.05 and 0.1, values of computation time of the same model are almost the same. Therefore, a balance between the objective and computation time is the condition when the EPGAP equals 0.05.Table 9
Computation time of each model.
EPGAP
0
0.05
0.1
Computation time/s
Upper bound/min
Lower bound/min
Computation time/s
Upper bound/min
Lower bound/min
Computation time/s
Upper bound/min
Lower bound/min
M1
94
196570
196570
4
196915
192300
4
203815
192300
M2
1007
190330
190330
15
191873
183720
7
193202
180837
M3
2092
189832
189832
178
192829
183206
89
194227
179078
M4
30400
187962
187962
384
189797
180383
152
190412
179140


## 5.1. Effect of Travel Time Weight

In the model, there are two parameters representing the travel time weight, namely,ω
1 and ω
2, which reflect the passengers’ perception of waiting time at stations and in-vehicle time, respectively. In general, passengers perceived time lapse on waiting time at stations is larger than the in-vehicle time [60]. In other words, passengers feel that time is longer when they wait for an available train at the station than in a vehicle. In order to have a deep insight on the effect of the two weights on the objective of the model. Let ω
2
=
1, and change the value of ω
1 to 1, 1.5, 2, and 2.5, respectively. The objectives of the model M1 to M4 are shown in Figures 13–16 (The EPGAP in the experiments are all equal to 0). It shows that, with the increasing value of the weight of passengers’ waiting time at stations, the objective, perceived waiting time of the passenger and perceived in-vehicle time increase. However, the realized (unweighted) passenger waiting time decreases. It is easy to explain, if the value of ω
1 is larger than ω
2, it indicates that the objective tends to minimize the passenger waiting time, then trains would be arranged to ensure this objective, which may increase the total travel time of all passengers. Moreover, the performance of different models is different. For examplee, for model 1, with the increasing value of the weights, either passengers’ waiting time or passengers’ in-vehicle time does not change too much. However, for other models, the value of passengers’ waiting time and in-vehicle time changes significantly.Figure 13
Results of value of objective with different weights.Figure 14
Results of weighted passengers’ waiting time with different weights.Figure 15
Results of realized passengers’ waiting time with different weights.Figure 16
Results of passengers’ in-vehicle time with different weights.


## 5.2. Effect of EPGAP

EPGAP is a parameter in the algorithm of branch and bound. The parameter is calculated by the difference of upper bound and lower bound divided by the upper bound. This parameter has big influence on the optimization effect and computation time. The smaller the value of EPGAP is, the closer the upper bound reaches the optimal value, and the longer the computation time and vice versa is. Table9 shows the model computation time and solution under different value of EPGAP. It shows that when the value of EPGAP equals 0, the objective is the best, but the computation time is the longest. With the increasing value of EPGAP, upper bound of each model increases. That is to say, the value of objective increases. Moreover, the difference between the value of the upper bound of each model and under different values of EPGAP is large. With the increasing value of EPGAP, computation time decreases. When the value of EPGAP equals 0, computation time is the longest. However, when the value of EPGAP equals 0.05 and 0.1, values of computation time of the same model are almost the same. Therefore, a balance between the objective and computation time is the condition when the EPGAP equals 0.05.Table 9
Computation time of each model.
EPGAP
0
0.05
0.1
Computation time/s
Upper bound/min
Lower bound/min
Computation time/s
Upper bound/min
Lower bound/min
Computation time/s
Upper bound/min
Lower bound/min
M1
94
196570
196570
4
196915
192300
4
203815
192300
M2
1007
190330
190330
15
191873
183720
7
193202
180837
M3
2092
189832
189832
178
192829
183206
89
194227
179078
M4
30400
187962
187962
384
189797
180383
152
190412
179140


## 6. Discussions

Demand-oriented train timetabling is a complex problem as there are a lot of input data to be taken into consideration. In our paper, we consider dwell time, running time, headway of trains, and passenger dynamic demand. There are three important issues to be discussed, passenger delay, train robust, and demand input.(1) Passenger Delay. Due to the limited capacity of trains, some passengers may be left behind at stations during peak hours. Whether such delays can be avoided is dependent on the infrastructure conditions. For example, if the platform is long enough, the capacity can be enhanced by coupling extra trains. If the capacity of infrastructure is not oversaturated, more trains can be dispatched. The delay can also be eliminated in a network level; for example, there is more than one route for passengers to select to go to the destination. Recently, “Reserve-A-ride trains” has attracted more and more attention (which is also successfully operated in Shaanxi Province, China). Passengers can reserve trains which they want to board prior to their departure. Under the circumstance, the “first-in and first-out” paradigm is broken; thus the “passenger fail-to board” phenomenon will disappear and passenger delays may be avoided.(2) Train Robust. Traditionally, the focus in railway timetabling is train-oriented. To meet the on-time requirements of the trains, railway timetables need to be robust against delays. There are some methods to enhance the robustness, such as adding time supplements, adding buffer time, cancelling trains, reducing network interdependencies, lowering heterogeneity, and so on [61]. In most of the demand-oriented timetabling studies, the buffer time to resist delay is neglected. In this case, small delay may significantly increase the optimized passenger travel time. This problem is worthy to be considered by all demand-oriented timetabling researches.(3) Demand Input. The proposed application of passenger demand is computed on the basis of the data from the automatic fare collection system. So, the model can be adapted to the railways which has already been operated and where time-dependent demand data are available. When there is a new line and no AFC data are available, if we want to design a timetable of the new line, theoretically, we can predict the passenger demand and use it to design the timetable. However, the granularity of current prediction approach is not enough. In fact, for many demand-driven timetables, there is a hidden condition where time-dependent passenger demand is known, either by smart card or by the reservation system. So strictly speaking, for a new line, the approach is not applicable.Another issue is the interaction between demand and timetable. In the condition of the model of this study, the service frequency is quite high. Under the circumstance, passengers’ arrival time is close to their real demand. Therefore, the data from the AFC system can almost reflect passengers’ real demand. When the time-dependent passenger demand data are accurate, the method we propose can be used to optimize timetable to reduce the passengers’ total travel time. When the service frequency is low, it is likely that passengers would choose their arrival time based on the timetable. In this case, if we use this demand data from AFC system to obtain a new timetable, we must wait until a new equilibrium situation is reached and then measure the results.


## 7. Conclusions

In this paper, we consider the time variant characteristics of passenger rail demand and establish mixed-integer quadratic programming models to minimize the total travel time of passengers under different conditions. The contribution of this paper is that the effect of combinatorial optimization of service order and overtaking condition is analyzed. Taking the Shanghai-Hangzhou intercity high-speed railway as a case study, the calculation results show that the model with free service order and allowing train overtaking performs best among all four models, in reducing the total travel time of the passengers. The total travel time of passengers was decreased by 4.4% when compared with the model with a fixed service order and with zero overtaking, which shows that this model is more suitable for meeting the dynamic passenger demand. The result also shows that, compared to overtaking, allowing the change of service order can save passengers’ total travel time without extending the train travel time. Besides, the optimization of service order and train overtaking can increase the computation time significantly in the meantime. Therefore, in practice, service order optimization should be considered with higher priority than overtaking. We conclude that the combinatorial optimization can effectively reduce the total travel time of passengers.There are two aspects of the train timetabling problem that need to be researched in the future. First, because the proposed model is based on a fixed train stop plan, which limits the optimization effect to a certain extent, the question how to integrate train stop plan optimization and timetabling optimization will be studied in the next stage. Although there are some preliminary studies on this problem, the efficient solving approach of the integrated problem is still an open challenge. Second, the computation time of the model for large-scale use is relatively long. This is the one of the most critical obstacles to apply such models for practical use. So the design of an efficient solution algorithm is another research need in future.



---

*Source: 4613468-2018-09-12.xml*