# Train Stop Scheduling in a High-Speed Rail Network by Utilizing a Two-Stage Approach

Authors: Huiling Fu; Lei Nie; Benjamin R. Sperry; Zhenhuan He
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

Among the most commonly used methods of scheduling train stops are practical experience and various “one-step” optimal models. These methods face problems of direct transferability and computational complexity when considering a large-scale high-speed rail (HSR) network such as the one in China. This paper introduces a two-stage approach for train stop scheduling with a goal of efficiently organizing passenger traffic into a rational train stop pattern combination while retaining features of regularity, connectivity, and rapidity (RCR). Based on a three-level station classification definition, a mixed integer programming model and a train operating tactics descriptive model along with the computing algorithm are developed and presented for the two stages. A real-world numerical example is presented using the Chinese HSR network as the setting. The performance of the train stop schedule and the applicability of the proposed approach are evaluated from the perspective of maintaining RCR.


---

## Body

## 1. Introduction

A train stop schedule is one of the crucial parts in a train service plan (TSP). The train stop schedule specifies a set or subset of stations where individual trains will stop in order to satisfy passengers’ travel demand among stations in a rail network. From a system optimization point of view, passenger demand is heterogeneously distributed over space. Consequently, considering certain performance criteria, the presence of binary variables, and resource constraints such as restricted capacity, the train stop scheduling problem (TSSP) turns out to be NP-hard with uncontrollable computational complexity as scale of rail network or number of stations increases.Practical experience has played an important role in understanding the TSSP and appreciating the complexity of the problem. To providedifferentialtrain services among hierarchical stations and achieve connectivity over a large number of passenger origins and destinations (ODs) in a rail network, mature flexible combinations of typical train stop patterns exist in many established worldwide rail networks. Namely, express trains or trains with a few stops at stations of high classification (e.g., ICE train in Germany and IC train in The Netherlands), “skip-stop” or “zone-stop” trains stop at major stations to increase traveler’s alternatives (e.g., “Hikari” train in Japan), and “all-stop” pattern to service exchange passengers along train routes (e.g., AR train in The Netherlands and “Kodama” train in Japan), have been adopted in these countries for decades. Also adopted in these countries for many decades is the cyclic train operation mode, meaning that in every short time period (e.g., 1 hour), trains have the same operating frequencies, sequence, and speed, and trains with the same sequence in each period have identical stop pattern, departure and arrival time. By doing so, regularity in the train stop schedule is achieved, including high and fixed train frequencies between stations, short wait time, fast transfer, and flexible trip combinations for travelers.In terms of applying system optimization theory, the challenging TSSP has attracted much attention in the literature, and there exist a number of studies showing different kinds of TSSP models or heuristic algorithms. Early studies applied diverse approaches to seek the best train stop schedules based on zoning [1], local versus express [2], and specific stop schemes [3]. Two optimization models were established with the objectives of covering more passenger demand with less train stops and saving more passengers’ travel time [4]; in the second model, a GA algorithm was introduced and tested on partial rail network in southern Germany. In the context of The Netherlands’ rail network, integer models combined with the multicommodity flow problem were developed to minimize the rail operator’s operating cost to generate multitype train stop schedule on the basis of the fixed train stop patterns in real world [5]. Additionally, in some literature sources, authors refer to approaches based on a prior given set of train stop patterns, which have been successfully applied, albeit for single rail line without branches. In the setting of the Taiwan HSR system, a multiobjective model was formulated to yield TSP with TSSP embedded in the model with the objective of minimizing the rail operator’s operating cost and the passenger’s travel time loss. The model was solved by a fuzzy mathematical programming approach [6]. A bilevel programming model was proposed and combined with network equilibrium analysis of passenger flow assignment on trains in a lower-level problem [7], and in a numerical study, there were only seven train stop patterns among five stations along the line could be selected to generate the final train stop schedule. Using a 46 km long, six-station transit line in the northeastern US as the background, a cost-efficient operation model that optimized all-stop, short-turn, and express transit services was developed [8], and a logit-based model was used to estimate the ridership for the seven candidate train stop patterns.The TSSP has also attracted much attention of rail operators and researchers in China as the most extensive HSR system in the world is being built in that country. In practice, those mature train stop patterns and cyclic train operations employed in the above-mentioned countries are not directly transferable to this newly developed system because it is characterized by several large-scale, fully connected lines with many stations and uneven passenger demand distribution. In the literature studies, following closely with the Chinese HSR system’s specifics, the TSSP retains the challenge of combinatorial explosion yet now becomes more complex. This complexity is due in part because a great majority of passenger demands should be satisfied through train stops due to concentrated train ODs settings. It can be seen that numerical studies with various optimal models applications were still limited to simplified single line or downsizing network and largely dependent on adaptive heuristic algorithms [9–11]. When handling this kind of complexity coupled with purposes of increasing connectivity, regularity without ignoring rapidity of some train services among major stations, the TSSP turns out to be extremely challenging which has not been well studied.Motivated by above considerations, this study is different from “one-step” models commonly used in the literature. In this paper, we develop a computer-aided two-stage approach to efficiently solve the TSSP from RCR perspectives using the Chinese HSR network as a case study. As train ODs settings are concentrated at a few main stations and small percentages of major stations comprise a high proportion of passenger traffic, the station classification concept is followed. The first-stage of the approach utilizes mixed integer programming to organize passengers among scale-reduced higher classification stations; for the remaining passengers associated with lower classification stations, by developing a train operating tactics descriptive model, the second-stage of the approach computes additional train stops within the overall schedule frame determined in the first-stage. The remainder of this paper is organized as follows. Section2 describes the formulation of the two-stage approach and related solution algorithm. Section 3 provides a numerical example from the Chinese HSR network. Section 4 concludes the study and brings forward the future work.


## 2. Model Formulation

### 2.1. Notations and Assumptions

The parameters and variables associated with the model development are summarized in Table1.  The basic assumptions are as follows.(a)
Stations are divided into three classifications using aK-means cluster analysis considering issues such as the technical conditions of train-set maintenance, collecting and distributing of passenger traffic, political or economic factors.(b)
Train ODs are pregiven determined by ridership and technical regulations, for example, between stations which can service as terminals (generally are stations of the first two classifications) and route length being within train-set maintenance kilometers.(c)
Passengers among these ODs with ultralong travel distance are processed to be split into separate ODs which are disconnected at major transfer hubs such that a single passenger is not required to transfer more than two times during a single trip.(d)
Optimizing train operating frequencies is out of scope of this study. For modeling needs, frequencies are estimated for trains among given train ODs according to potential attracted passenger traffic.(e)
Passengers’ travel benefits in terms of RCR are mostly converted to train operating tactics during the two-stage train stop scheduling process, thus a seat reservation system is necessarily required to coordinate with the models practical application.Table 1
Notation of model parameters and variables.
Parameter/variable
Description
L
(gt)
Set of trains among given train ODs
L(ht)
Set of stop trains of higher classification
L(lt)
Set of stop trains of lower classification
ℓ
k
Trains in setL indexed by k
f
(
ℓ
k
)
Estimated frequency of trainℓk(∈L(gt))
h
(
ℓ
k
)
Route length of trainℓk (km)
V(fc)
Set of the first classification stations in HSR network
V(sc)
Set of the second classification stations in HSR network
V(tc)
Set of the third classification stations in HSR network
v
i or vj
Stations in setV indexed by i or j
E
Set of tracks in HSR network
e
m
Tracks in setE indexed by m, em∈E
ν
(
ℓ
k
,
e
m
)
Travel speed of trainℓk on track em (km/h)
L(gt, em)
Set of trains in setL(gt) with their routes covering track em
D
Set of passenger ODs
d
(
v
i
,
v
j
)
Passenger demand between stationvi and vj that D={(vi,vj)∈V×V∣d(vi,vj)>0}
κ
(
ℓ
k
)
Seating capacity of trainℓk
θ
(
ℓ
k
)
Loading coefficient of trainℓk
N
(
ℓ
k
)
The maximum times of stops can be added on trainℓk(∈L(gt)) for trains in set L(ht)
η
(
v
i
,
ℓ
k
)
Count parameter of whether stop being added at stationvi on train ℓk(∈L(gt))
L(gt, (vi,vj))
Set of possible trains on which stop(s) can be added for passenger OD(vi,vj), and L(gt, (vi,vj)) ={lk∈ L(gt) ∣(vi,vj)∈lk}
D
'
(
ℓ
k
)
Set of possible passenger ODs for which the stop(s) can be added on trainℓk(∈L(gt)), and D'(ℓk)={(vi,vj)∈D∣ℓk∈(vi,vj)}
x
(
ℓ
k
,
(
v
i
,
v
j
)
)
Binary variable, it is 1 only if for passenger OD(vi,vj), stop(s) is(are) added on train ℓk(∈L(gt)), else it equals 0
y
(
ℓ
k
,
(
v
i
,
v
j
)
)
The flow of passenger OD(vi,vj) assigned on train ℓk(∈L(gt)) with added stop(s) on it, y(ℓk,(vi,vj))≥0 and integer
r
(
ℓ
k
)
Proportion of through passengers out of total traffic attracted by trainℓk(∈L(gt))
ω
(
ℓ
k
)
Weights of influencing factor of adding stop(s) on trainℓk(∈L(gt))
ω
'
(
h
(
ℓ
k
)
,
ν
(
ℓ
k
,
e
m
)
),   ω″(r(ℓk))
Weights functions of influencing factors of adding stop(s) on trainℓk(∈L(gt))


### 2.2. The First-Stage Modeling of TSSP for Higher-Classification Trains

Higher-classification trains are defined as the trains running and dwelling only among stations of the highest two classifications. Frequent train stops results in negative impacts of reducing train’s rapidity, increasing passengers’ total travel time and train operating cost. Hence, stops are not given priority to be added on trains in setL(gt) with properties as follows:(a)
being operated between stations of the first classification,(b)
a long travel time (depending on routes length and technical speed standards of running sections),(c)
having high proportion of their dedicated origin and destination passengers (through passengers) out of total attracted traffic.As a consequence of (a), high-quality train services between stations of the first classification are ensured, while (b) and (c) allow competitive travel times on long-distance routes to the benefit of a large number of through passengers using such routes.By putting weights of the three influencing factors on trains in setL(gt), the negative impacts of adding stops on trains have to be minimized, giving rise to the objective of
(2.1)min∑(vi,vj)∈D:vi,vj∈V(fc),V(sc)∑ℓk∈L(gt,(vi,vj))(ω(ℓk)+ω′(h(ℓk),ν(ℓk,em))+ω′′(r(ℓk)))·x(ℓk,(vi,vj)),
where ω(ℓk), ω′(h(ℓk),ν(ℓk,em)), and ω′′(r(ℓk)) stand for weights of the three influencing factors, respectively. These weights are calibrated using a scoring approach, specifically, ω(ℓk) is 0 if the first factor is not applicable to train ℓk, ω′(h(ℓk),ν(ℓk,em)), and ω′′(r(ℓk)) are incremental with the increase of train travel time and proportion of through passengers for different trains.Additionally, the maximum stop times on trainℓk need to be limited, thus,
(2.2)∑vi∈V(fc),V(sc)η(vi,ℓk)·x(ℓk,(vi,vj))≤N(ℓk)∀ℓk∈L(gt).
The count parameter η(vi,ℓk) equals 0 if a stop will not be added at station vi and equals 1 if station vi is to be added as a stop for more than one passenger OD. The condition of vi,vj∈V(fc),V(sc) in (2.1) and (2.2) holds for all the following constraints.To ensure the total train stop frequencies at a given station are adequate to meet the passenger demand requirements, the supply-demand constraint is formulated as(2.3)∑ℓk∈L(gt,(vi,vj))x(ℓk,(vi,vj))·κ(ℓk)·f(ℓk)·θ(ℓk)≥d(vi,vj)∀(vi,vj)∈D.Furthermore, the flow of different passenger ODs assigned on a given trainℓk should not exceed that train’s seating capacity
(2.4)∑(vi,vj)∈D′(ℓk):(vi,vj,ℓk)⊇emy(ℓk,(vi,vj))≤κ(ℓk)·f(ℓk)·θ(ℓk)∀em∈E,ℓk∈L(gt,em).
in which (vi,vj,ℓk)⊇em means that only passenger OD(s) passing through track em is (are) taken into account.In the assignment process, passenger flow conservation is given by(2.5)∑ℓk∈L(gt,(vi,vj))y(ℓk,(vi,vj))=d(vi,vj)∀(vi,vj)∈D.Following constraint (2.6) denotes that if stop(s) is (are) not added on train ℓk for passenger OD (vi,vj), its flow assigned on train ℓk equals 0, M^ is a very large positive number
(2.6)y(ℓk,(vi,vj))≤M^·x(ℓk,(vi,vj))∀ℓk∈L(gt),(vi,vj)∈D.Aiming at achieving connectivity of train services, a binary variable of whether stop(s) is (are) added on trainℓk for passenger OD (vi,vj) rather than a stop being added at station vi on train ℓk or not (as is typically included in most studies) is designed here. The approach of defining on which train(s) travelers of each passenger OD are assigned is still followed in the second-stage modeling of TSSP. Two types of decision variables are restricted as follows:
(2.7)x(ℓk,(vi,vj))∈{0,1}∀ℓk∈L(gt),(vi,vj)∈D,y(ℓk,(vi,vj))≥0∀ℓk∈L(gt),(vi,vj)∈D.Additionally,x(ℓk,(vi,vj)) equals 1 only if for passenger OD (vi,vj), stop(s) is (are) added on train ℓk(∈L(gt)) in vi (if vj is origin or destination station of train ℓk) or vj (if vi is origin or destination station of train ℓk), or in both (if none of vi and vj is origin or destination station of train ℓk).


### 2.3. The Second-Stage Modeling of TSSP for Lower-Classification Trains

Lower-classification trains are defined as the trains dwelling at least once at stations of the third (i.e., lowest) classification. The train stop schedule generated in the first-stage (Section2.2) gives the overall scheme; based on this initial scheme, additional train stops are further scheduled for the remaining passengers associated with the third classification stations. Before starting the descriptive model and computing algorithm development, tactics of sequencing trains in set L(ht) involved in modeling and algorithm implementing process are interpreted below.(a)
Trains are categorized as in-line and cross-line trains corresponding to running within a single line and cross at least two different lines, respectively. In-line trains are given priority over cross-line trains to ensure a match between train route length and passenger travel distance.(b)
From short trains to long trains considering equilibrium of train timetabling.(c)
From trains with more stops to trains with fewer stops, leading to setting stops intensively on fewer trains aiming at increasing the proportion of trains with higher travel speed.It is noted that the proposed algorithm is flexible such that it is still possible for rail operator to design other tactics and adjust preferred train sequence as passenger demand warrants.  The descriptive model and computing algorithm are outlined in Algorithm1 as follows.Algorithm 1:Descriptive model/algorithm for computing train stop schedule for lower-classification trains.
(
1
) - Set sequence of the input trains in set L(ht) (including selected non-stop direct trains
(e.g., short-distance trains with running sections covering high passenger density) in set
L(gt))
(
2
)
repeat
(
3
)
for train ℓk (k=1 to K (K≤|L(ht)|)) do
(
4
)   - Enumerate all passenger OD pairs that can be covered
(
5
)   - Calculate the maximum remaining stop times that can be added on train ℓk
in set L(ht), notated as N′(ℓk)
(
6
)    Repeat
(
7
)    forN'(ℓk) (N'(ℓk)≠0) do
(
8
)     - Enumerate all station group(s) with combined N'(ℓk) station(s) of the
third classification (∈V(tc)), notated as V-(sg, n), where n is index symbol
(
9
)     - Calculate total passenger traffic of all combined passenger OD pairs
among station(s) in V-(sg, n) together with existing stop(s) and OD on train
ℓk, notated as TP(V-(sg, n)) =∑(vi,vj)d(vi,vj), where both vi and vj or at least
one of them belong to V-(sg, n)
(
10
)     - Select the group V-(sg, n) with the maximum TP(V-(sg, n))
(
11
)     if train ℓk has a cost-efficient frequency* to be operated with assigned
TP(V-(sg, n)) on it, do
(
12
)      - Add station(s) in the selected group on train ℓk as additional stop(s),
and update passenger flow, go to Step  7
(
13
)     elsedo
(
14
)      - Update N'(ℓk)=N'(ℓk)-1, go to Step  7
(
15
)    end for
(
16
)   untilN'(ℓk)=0
(
17
)  end for
(
18
)
until assigning the remaining passengers on trains is completed, then set of L(lt)
is obtained
*From the perspective of the rail operator, a cost-efficient train operating frequency is defined as
at least one train per day for a given train OD with a rational loading factor (e.g., ≥0.70).In Algorithm1, essentials including a train stop pattern enumeration technique, a train stop pattern decision-making criteria, and its corresponding passenger flow assignment procedure presented from Step 7 to Step 15 reveal the main objective of the descriptive model and computing algorithm: scheduling additional train stops to satisfy the remaining passenger demand with a minimum number of different train stop patterns.


## 2.1. Notations and Assumptions

The parameters and variables associated with the model development are summarized in Table1.  The basic assumptions are as follows.(a)
Stations are divided into three classifications using aK-means cluster analysis considering issues such as the technical conditions of train-set maintenance, collecting and distributing of passenger traffic, political or economic factors.(b)
Train ODs are pregiven determined by ridership and technical regulations, for example, between stations which can service as terminals (generally are stations of the first two classifications) and route length being within train-set maintenance kilometers.(c)
Passengers among these ODs with ultralong travel distance are processed to be split into separate ODs which are disconnected at major transfer hubs such that a single passenger is not required to transfer more than two times during a single trip.(d)
Optimizing train operating frequencies is out of scope of this study. For modeling needs, frequencies are estimated for trains among given train ODs according to potential attracted passenger traffic.(e)
Passengers’ travel benefits in terms of RCR are mostly converted to train operating tactics during the two-stage train stop scheduling process, thus a seat reservation system is necessarily required to coordinate with the models practical application.Table 1
Notation of model parameters and variables.
Parameter/variable
Description
L
(gt)
Set of trains among given train ODs
L(ht)
Set of stop trains of higher classification
L(lt)
Set of stop trains of lower classification
ℓ
k
Trains in setL indexed by k
f
(
ℓ
k
)
Estimated frequency of trainℓk(∈L(gt))
h
(
ℓ
k
)
Route length of trainℓk (km)
V(fc)
Set of the first classification stations in HSR network
V(sc)
Set of the second classification stations in HSR network
V(tc)
Set of the third classification stations in HSR network
v
i or vj
Stations in setV indexed by i or j
E
Set of tracks in HSR network
e
m
Tracks in setE indexed by m, em∈E
ν
(
ℓ
k
,
e
m
)
Travel speed of trainℓk on track em (km/h)
L(gt, em)
Set of trains in setL(gt) with their routes covering track em
D
Set of passenger ODs
d
(
v
i
,
v
j
)
Passenger demand between stationvi and vj that D={(vi,vj)∈V×V∣d(vi,vj)>0}
κ
(
ℓ
k
)
Seating capacity of trainℓk
θ
(
ℓ
k
)
Loading coefficient of trainℓk
N
(
ℓ
k
)
The maximum times of stops can be added on trainℓk(∈L(gt)) for trains in set L(ht)
η
(
v
i
,
ℓ
k
)
Count parameter of whether stop being added at stationvi on train ℓk(∈L(gt))
L(gt, (vi,vj))
Set of possible trains on which stop(s) can be added for passenger OD(vi,vj), and L(gt, (vi,vj)) ={lk∈ L(gt) ∣(vi,vj)∈lk}
D
'
(
ℓ
k
)
Set of possible passenger ODs for which the stop(s) can be added on trainℓk(∈L(gt)), and D'(ℓk)={(vi,vj)∈D∣ℓk∈(vi,vj)}
x
(
ℓ
k
,
(
v
i
,
v
j
)
)
Binary variable, it is 1 only if for passenger OD(vi,vj), stop(s) is(are) added on train ℓk(∈L(gt)), else it equals 0
y
(
ℓ
k
,
(
v
i
,
v
j
)
)
The flow of passenger OD(vi,vj) assigned on train ℓk(∈L(gt)) with added stop(s) on it, y(ℓk,(vi,vj))≥0 and integer
r
(
ℓ
k
)
Proportion of through passengers out of total traffic attracted by trainℓk(∈L(gt))
ω
(
ℓ
k
)
Weights of influencing factor of adding stop(s) on trainℓk(∈L(gt))
ω
'
(
h
(
ℓ
k
)
,
ν
(
ℓ
k
,
e
m
)
),   ω″(r(ℓk))
Weights functions of influencing factors of adding stop(s) on trainℓk(∈L(gt))


## 2.2. The First-Stage Modeling of TSSP for Higher-Classification Trains

Higher-classification trains are defined as the trains running and dwelling only among stations of the highest two classifications. Frequent train stops results in negative impacts of reducing train’s rapidity, increasing passengers’ total travel time and train operating cost. Hence, stops are not given priority to be added on trains in setL(gt) with properties as follows:(a)
being operated between stations of the first classification,(b)
a long travel time (depending on routes length and technical speed standards of running sections),(c)
having high proportion of their dedicated origin and destination passengers (through passengers) out of total attracted traffic.As a consequence of (a), high-quality train services between stations of the first classification are ensured, while (b) and (c) allow competitive travel times on long-distance routes to the benefit of a large number of through passengers using such routes.By putting weights of the three influencing factors on trains in setL(gt), the negative impacts of adding stops on trains have to be minimized, giving rise to the objective of
(2.1)min∑(vi,vj)∈D:vi,vj∈V(fc),V(sc)∑ℓk∈L(gt,(vi,vj))(ω(ℓk)+ω′(h(ℓk),ν(ℓk,em))+ω′′(r(ℓk)))·x(ℓk,(vi,vj)),
where ω(ℓk), ω′(h(ℓk),ν(ℓk,em)), and ω′′(r(ℓk)) stand for weights of the three influencing factors, respectively. These weights are calibrated using a scoring approach, specifically, ω(ℓk) is 0 if the first factor is not applicable to train ℓk, ω′(h(ℓk),ν(ℓk,em)), and ω′′(r(ℓk)) are incremental with the increase of train travel time and proportion of through passengers for different trains.Additionally, the maximum stop times on trainℓk need to be limited, thus,
(2.2)∑vi∈V(fc),V(sc)η(vi,ℓk)·x(ℓk,(vi,vj))≤N(ℓk)∀ℓk∈L(gt).
The count parameter η(vi,ℓk) equals 0 if a stop will not be added at station vi and equals 1 if station vi is to be added as a stop for more than one passenger OD. The condition of vi,vj∈V(fc),V(sc) in (2.1) and (2.2) holds for all the following constraints.To ensure the total train stop frequencies at a given station are adequate to meet the passenger demand requirements, the supply-demand constraint is formulated as(2.3)∑ℓk∈L(gt,(vi,vj))x(ℓk,(vi,vj))·κ(ℓk)·f(ℓk)·θ(ℓk)≥d(vi,vj)∀(vi,vj)∈D.Furthermore, the flow of different passenger ODs assigned on a given trainℓk should not exceed that train’s seating capacity
(2.4)∑(vi,vj)∈D′(ℓk):(vi,vj,ℓk)⊇emy(ℓk,(vi,vj))≤κ(ℓk)·f(ℓk)·θ(ℓk)∀em∈E,ℓk∈L(gt,em).
in which (vi,vj,ℓk)⊇em means that only passenger OD(s) passing through track em is (are) taken into account.In the assignment process, passenger flow conservation is given by(2.5)∑ℓk∈L(gt,(vi,vj))y(ℓk,(vi,vj))=d(vi,vj)∀(vi,vj)∈D.Following constraint (2.6) denotes that if stop(s) is (are) not added on train ℓk for passenger OD (vi,vj), its flow assigned on train ℓk equals 0, M^ is a very large positive number
(2.6)y(ℓk,(vi,vj))≤M^·x(ℓk,(vi,vj))∀ℓk∈L(gt),(vi,vj)∈D.Aiming at achieving connectivity of train services, a binary variable of whether stop(s) is (are) added on trainℓk for passenger OD (vi,vj) rather than a stop being added at station vi on train ℓk or not (as is typically included in most studies) is designed here. The approach of defining on which train(s) travelers of each passenger OD are assigned is still followed in the second-stage modeling of TSSP. Two types of decision variables are restricted as follows:
(2.7)x(ℓk,(vi,vj))∈{0,1}∀ℓk∈L(gt),(vi,vj)∈D,y(ℓk,(vi,vj))≥0∀ℓk∈L(gt),(vi,vj)∈D.Additionally,x(ℓk,(vi,vj)) equals 1 only if for passenger OD (vi,vj), stop(s) is (are) added on train ℓk(∈L(gt)) in vi (if vj is origin or destination station of train ℓk) or vj (if vi is origin or destination station of train ℓk), or in both (if none of vi and vj is origin or destination station of train ℓk).


## 2.3. The Second-Stage Modeling of TSSP for Lower-Classification Trains

Lower-classification trains are defined as the trains dwelling at least once at stations of the third (i.e., lowest) classification. The train stop schedule generated in the first-stage (Section2.2) gives the overall scheme; based on this initial scheme, additional train stops are further scheduled for the remaining passengers associated with the third classification stations. Before starting the descriptive model and computing algorithm development, tactics of sequencing trains in set L(ht) involved in modeling and algorithm implementing process are interpreted below.(a)
Trains are categorized as in-line and cross-line trains corresponding to running within a single line and cross at least two different lines, respectively. In-line trains are given priority over cross-line trains to ensure a match between train route length and passenger travel distance.(b)
From short trains to long trains considering equilibrium of train timetabling.(c)
From trains with more stops to trains with fewer stops, leading to setting stops intensively on fewer trains aiming at increasing the proportion of trains with higher travel speed.It is noted that the proposed algorithm is flexible such that it is still possible for rail operator to design other tactics and adjust preferred train sequence as passenger demand warrants.  The descriptive model and computing algorithm are outlined in Algorithm1 as follows.Algorithm 1:Descriptive model/algorithm for computing train stop schedule for lower-classification trains.
(
1
) - Set sequence of the input trains in set L(ht) (including selected non-stop direct trains
(e.g., short-distance trains with running sections covering high passenger density) in set
L(gt))
(
2
)
repeat
(
3
)
for train ℓk (k=1 to K (K≤|L(ht)|)) do
(
4
)   - Enumerate all passenger OD pairs that can be covered
(
5
)   - Calculate the maximum remaining stop times that can be added on train ℓk
in set L(ht), notated as N′(ℓk)
(
6
)    Repeat
(
7
)    forN'(ℓk) (N'(ℓk)≠0) do
(
8
)     - Enumerate all station group(s) with combined N'(ℓk) station(s) of the
third classification (∈V(tc)), notated as V-(sg, n), where n is index symbol
(
9
)     - Calculate total passenger traffic of all combined passenger OD pairs
among station(s) in V-(sg, n) together with existing stop(s) and OD on train
ℓk, notated as TP(V-(sg, n)) =∑(vi,vj)d(vi,vj), where both vi and vj or at least
one of them belong to V-(sg, n)
(
10
)     - Select the group V-(sg, n) with the maximum TP(V-(sg, n))
(
11
)     if train ℓk has a cost-efficient frequency* to be operated with assigned
TP(V-(sg, n)) on it, do
(
12
)      - Add station(s) in the selected group on train ℓk as additional stop(s),
and update passenger flow, go to Step  7
(
13
)     elsedo
(
14
)      - Update N'(ℓk)=N'(ℓk)-1, go to Step  7
(
15
)    end for
(
16
)   untilN'(ℓk)=0
(
17
)  end for
(
18
)
until assigning the remaining passengers on trains is completed, then set of L(lt)
is obtained
*From the perspective of the rail operator, a cost-efficient train operating frequency is defined as
at least one train per day for a given train OD with a rational loading factor (e.g., ≥0.70).In Algorithm1, essentials including a train stop pattern enumeration technique, a train stop pattern decision-making criteria, and its corresponding passenger flow assignment procedure presented from Step 7 to Step 15 reveal the main objective of the descriptive model and computing algorithm: scheduling additional train stops to satisfy the remaining passenger demand with a minimum number of different train stop patterns.


## 3. Numerical Example

This section demonstrates the applicability of the developed models and algorithm using the Chinese HSR network (Figure1) as a case study. The Chinese HSR network (planned for 2015, excluding intercity lines) consists of 21 lines with total mileage over 10,000 km. The center of the network is the Beijing-Shanghai (Jinghu) HSR line which is, to date, the longest HSR line in the network (1,318 km). The Jinghu HSR is built with the highest standards (the maximum speed is 350 km/h) and plays a significant role in entire network. In a selected study subnetwork (noted as dual lines) centered by the Jinghu HSR as shown in Figure 1, 38 train ODs associated with the Jinghu HSR among 27 stations of the first two classifications are pregiven. A total of 481 passenger ODs relating to the Jinghu HSR having known forecasted daily traffic are within the scope of this numerical example.Figure 1
The Chinese HSR network with study Jinghu HSR and its associated network noted.The trains seating capacity and loading coefficients are identically set equal to 1,060 seats/train-set and 1.0 (at maximum), respectively. Within the running section on the Jinghu HSR, the maximum stop times of higher-classification in-line trains is 4 and 7 for lower-classification in-line trains; cross-line trains’ maximum stop times are restricted as 6 and 9 for higher- and lower-classification trains, respectively. Due to data size, parameters below are not individually listed in detail: (a) passenger traffic of each OD, a total of 536,914 passengers (one direction, including passengers organized on nonstop direct trains) are considered in the scheduling process, for trains in setL(gt), as are their (b) routes length, (c) travel time, (d) estimated frequencies, and (e) integrated weights of three influencing factors valued between 0.37 to 1.0.The two-stage approach outlined here reduces the problem-solving scale, resulting in a total of 15 binary variables representing in-line passenger ODs and 118 binary variables for the other passenger ODs associated with the Jinghu HSR. Variablesy(ℓk,(vi,vj)), typically considered to be integer, are relaxed as real. Thus, the first-stage TSSP model is efficiently solved by a Branch-and-Bound algorithm coded in the LINGO 10.0 solver, which is embedded in a computer system written by C# programming language for computing the second-stage TSSP model. The computations are performed on an Intel i5 2.4 GHZ with 2 GB RAM in the environment of Microsoft Windows XP, with a processing time less than 30 minutes. Figure 2 shows the two-stage TSSP model result for the train stop schedule on the Jinghu HSR.Figure 2
Train stop schedule estimated from two-stage approach.It can be seen in Figure2 that the two-stage approach results in a flexible combination of train stop patterns. An “all-stop” train stop pattern is not recommended for the long-distance sections for example, Beijing South-Shanghai Hongqiao. For the sake of servicing exchange passengers which are not related to the Jinghu HSR at all and with unknown detailed traffic (e.g., passengers between Xian North and Zhengzhou East, Harbin West, and Changchun West), in this numerical example, it was assumed that cross-line trains adopted an all-stop pattern at stations of the first two classifications on their running sections outside the Jinghu HSR. For example, the train “Xian North-Shanghai Hongqiao” stops at “Zhengzhou East” station on the route.Since train frequencies optimization is not explicitly involved, regularity is not entirely the result of operating trains cyclically, but from restricting train stop times on different classification trains with different properties. Higher-classification trains’ average stop times is approximately 3, and the three trains with the highest integrated weights of influencing factors (“Beijing South-Shanghai Hongqiao,” “Beijing South-Wuhan,” and “Xian North-Shanghai Hongqiao”) stop an average of two times. Lower-classification trains stop an average of six times with a total of 23 stop patterns obtained. Stops are mostly allocated on in-line trains, and cross-line trains with short-medium travel distance constitute a low proportion totaling 8 stop patterns.In the current TSP on the Jinghu HSR, there are approximately 16 percent of all in-line passenger ODs that have no train service or are serviced only by a few “all-stop, medium-speed” trains, rather than high-speed trains. Comparatively, connectivity is sufficiently ensured, as previously mentioned, by tracking on which trains passengers are assigned. Due to the “cost-efficient frequency” restriction (see Step 11 in Algorithm 1), only two in-line passenger ODs have no direct train service within this numerical example: the “Cangzhou West-Wuxi East” OD and the “Dezhou East-Zhenjiang West” OD. Moreover, greater connectivity is achieved by using only 23 lower-classification train stop patterns, a reduction of approximately 39 percent compared to the current TSP on the Jinghu HSR. On a more practical level, the rail operator benefits by significantly improving the homogeneity of a train timetable.In terms of rapidity, considering in-line trains for statistics (at present a few cross-line trains only in two directions are in operation on the Jinghu HSR), the proportion of trains with 6 or 7 stops (the most commonly adopted train stop pattern) in the current TSP is about 66 percent. Comparatively, in this numerical example, the proportion of trains with 6 or 7 stops is reduced to approximately 46 percent of trains (36 percent of trains considering estimated frequencies). Furthermore, the number of trains making only 1 or 2 stops is nearly 38 percent in this numerical example (50 percent by considering estimated frequencies), in contrast to approximately 25 percent in the current TSP.


## 4. Conclusions

This paper presented a two-stage approach for solving the TSSP in a large-scale HSR network, such as the Chinese HSR network. A mixed integer programming model, a train operating tactics descriptive model, and algorithm were developed for the two stages, and a real-world numerical analysis demonstrated that the generated train stop schedule improved the combination of train stop patterns, while also improving the regularity, connectivity, and rapidity. In addition to ensuring optimization, to speed up the entire solving process, future research should consider using intelligent algorithms for the first-stage TSSP model. Another area of future work comprises integrating the TSSP into the optimization of train frequencies by expanding the two-stage approach so as to capture a more comprehensive efficiency evaluation, incorporating indicators such as the capacity utilization ratio, rail operator’s operating cost, and passenger’s travel frequencies.



---

*Source: 579130-2012-11-12.xml*