# Schedule-Based Passenger Assignment for High-Speed Rail Networks considering the Ticket-Booking Process

Authors: Huanyin Su; Feng Shi; Guangming Xu; Jin Qin; Xinghua Shan
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

This paper proposes a schedule-based passenger assignment method for high-speed rail networks considering the ticket-booking process. Passengers book tickets to reserve seats during the presale period in high-speed rail systems and passengers on trains are determined during the ticket-booking process. The ticket-booking process is modeled as a continuous and deterministic predecision process. A solution algorithm is designed using the discretization of the continuous process by partitioning the ticket-booking time and the optimal paths remain constant in any partition interval. Finally, an application to the Chinese high-speed rail network is presented. A comparison of the numerical results with the reality is conducted to validate the efficiency and precision of the method and algorithm. Based on the results, the operating efficiency of the current train schedule is evaluated and some specific improvement measures are proposed.


---

## Body

## 1. Introduction

In recent years, there is a rapid development of high-speed rail networks in the world, especially in China [1]. The passenger assignment is a key point for optimizing line planning problems and timetables in high-speed rail networks. The optimization effect is directly determined by the precision and efficiency of passenger assignment. Hence, designing an applicable assignment method is an important issue.In recent studies, passenger assignment problems have been widely studied with frequency-based models and schedule-based models [2], which were mainly focused on urban transit systems. Urban transit systems are characterized by uncertainty, space-time priority (time priority means that passengers are first-come–first-served and space priority means that passengers waiting at the upstream stations of the lines have the priority to obtain seats over passengers waiting at the downstream stations), and crowding. Hence, the focuses of the studies are also on the above characters. For example, Sumalee et al. [3] proposed a dynamic transit assignment model that had an explicit seat-allocation process. Nuzzolo et al. [4] proposed a dynamic assignment model with a joint choice for the departure time and number of stops and a space-time path in which users decided to leave at given times, to access the network at given stops, and to board given trains to reach their destinations. Hamdouch et al. [5] proposed a schedule-based transit assignment model with travel strategies and loaded passengers on a first-come–first-served basis.However, these features are not shared by high-speed rail systems. In high-speed rail systems, passengers can book tickets before the departure day, for example, two months early in China. Then, passengers can choose their optimal paths based on the available seats before departure, which is a predecision problem. Besides, the number of tickets sold is usually kept below each train’s seating capacity in many countries. Especially in China and Europe, a passenger should reserve a seat (In China, some standing tickets are sold but only during peak seasons, such as the Spring Festival) and this prevents overcrowding and overbooking on high-speed trains. Hence, in high-speed rail systems, a passenger’s choice of path depends entirely on the ticket-booking process, and then passengers on trains are determined in the process.The ticket-booking process in the rail systems has not been considered by researchers in the passenger assignment methods so far. The methods having been designed are shown as follows. The system split method [6] assigning passengers to the different train types was used for line planning [7, 8]. Cascetta and Coppola [9] adopted a stochastic network loading model with no capacity constraints to estimate the passengers on individual trains. Kaspi and Raviv [10] assigned passengers on the paths with minimum time and the capacity of the trains was not binding. Fu et al. [1] assumed that passengers sought the most time-saving paths from all the available routes and were assigned very dispersedly to the train service network. Passengers’ response to crowding was studied in a train passenger assignment model [11]. Cascetta and Coppola [12] presented an assessment of schedule-based and frequency-based assignment models of high-speed rail services and predicted passengers on individual trains and station-to-station segments. In these studies, the ticket-booking process was not described and analyzed.Hence, a new method for passenger assignment problems in high-speed rail systems should be built. Based on the characters in high-speed rail networks, the authors conclude that there are two key points in the ticket-booking process: the book-ticketing time and the path choice. In the literature, Carrier [13] analyzed the choice of airline itinerary and fare product using booking and seat availability data. Hetrakul and Cirillo [14] studied the ticket-booking time decisions of railway passengers based on the ticket fare variation over the sale horizon. Ticket fare discounts in the presale period were the mainly decision factor in the above two studies. However, the ticket fares of the high-speed rail system in China are fixed at present. Besides, the ticket-booking time is quite an uncertainty and complicated variable, which depends on many factors, such as when the decision of traveling is made, the available tickets, the travel distance, the destination, and many other personal factors. Hence, the distributions of passengers depending on the ticket-booking time are given as input data in this paper, which deserve deep study in a separate paper.The purpose of this paper is to study the path choices of passengers at any given ticket-booking time and load passengers on the trains in high-speed rail systems. Hence, this paper proposes a schedule-based passenger assignment method for high-speed rail networks considering the ticket-booking process. At any ticket-booking time, the optimal paths for passengers are deterministic based on the available tickets. Then, the ticket-booking process is modeled as a continuous and deterministic predecision process. A solution algorithm is designed using the discretization of the continuous process by partitioning the ticket-booking time and the optimal paths remain constant in any time partition interval. Finally, an application to the Chinese high-speed rail network is presented to validate the precision and efficiency of the proposed method and algorithm.The contributions of this paper include the following:(i)
This paper proposes a schedule-based passenger assignment method for high-speed rail networks with the consideration of the ticket-booking process.
(ii)
A solution algorithm is designed using the discretization of the continuous process by partitioning the ticket-booking time and the expected departure time, which reduces the complexity of calculation.
(iii)
In the application, passengers on any train segment and the paths with minimum cost at any ticket-booking time are calculated. A comparison of the results with the reality is conducted to validate the precision and efficiency of the method. Based on the results, the operating efficiency of the current train schedule is evaluated and some specific improvement measures are proposed.


## 2. Problem Definition

Schedule-based passenger assignment problems for high-speed rail networks can be described as follows:(i)
Inputs are as follows: high-speed rail network, high-speed train’s schedule, daily travel demands between any two stations, and the demand distributions depending on the expected departure time and ticket-booking time.
(ii)
Assumptions are as follows:
(a)
All the unsold tickets are open to any passenger in a fair way and all passengers have the same opportunity to book tickets.
(b)
All passengers have desired departure times based on their plans, which are called expected departure times, and the desired arrival time is not considered.
(c)
All passengers book tickets in advance during the presale period. At any ticket-booking time, the number of passengers booking tickets between any two stations is given and fixed, that is, not considering ticket-canceling.
(d)
Passengers reserve seats to choose paths with minimum cost when booking tickets. The number of tickets sold should not exceed the train seating capacity. The ticket class is not considered. The ticket fare variation is not considered. Every passenger on the train has a seat, so the crowding effect is not considered.
(e)
For every station, there is a minimum time required for passengers to switch trains.
(iii)
Output is as follows: passengers on every train segment.A passenger’s choice of path depends entirely on the ticket-booking process. Hence, passenger assignment in a high-speed rail network is determined by the ticket-booking process. Ticket-booking time is continuous and passengers always choose the paths with the current minimum cost based on the available train seating capacity at any ticket-booking time. The choices are deterministic and cannot be changed with the ticket-booking time continuing. Then, the ticket-booking process is modeled as a continuous and deterministic predecision process.


## 3. Travel Demand and Network

### 3.1. Travel Demand and Distribution

A high-speed rail network is represented byV
,
E, where V is the set of station nodes and E is the set of arcs. The operating period for a given high-speed rail network is denoted by t
1
,
t
2 (trains running overnight are not considered). The set of O-D pairs is denoted as R
S
⊂
V
×
V, and the daily travel demand of an O-D pair is denoted by q
r
s
,
r
,
s
∈
R
S.For any given O-D pair, there is a distribution depending on the expected departure time for the travel demand, for example, from Beijing to Shanghai, as shown in Figure1. The intensity distribution function is denoted by f
r
s
x
,
x
∈
t
1
,
t
2
,
r
,
s
∈
R
S, satisfying the following:(1)
∫
t
1
t
2
f
r
s
x
d
x
=
q
r
s
,
r
,
s
∈
R
S
.Figure 1
Intensity distribution of travel demand from Beijing to Shanghai depending on expected departure time on 1 July 2014.According to the assumptions, all passengers book tickets in advance during the presale periodt
-
,
0 (t
- is negative, t
- is the maximum presale time ahead of the departure day, and 0 means the departure day) and the number of passengers at any ticket-booking time is given. Hence, there is a distribution depending on the ticket-booking time for the travel demand, for example, from Beijing to Shanghai, as shown in Figure 2. The distributions were called booking curves by Tsai [15]. The intensity distribution function is denoted by g
r
s
y
,
y
∈
t
-
,
0
,
r
,
s
∈
R
S, satisfying the following:(2)
∫
t
-
0
g
r
s
y
d
y
=
q
r
s
,
r
,
s
∈
R
S
.Figure 2
Intensity distribution of travel demand from Beijing to Shanghai depending on ticket-booking time on 1 July 2014.The authors assume that the above two variables are mutually independent; the combined probability density distribution function of travel demand is expressed as follows:(3)
f
r
s
x
g
r
s
y
q
r
s
2
,
x
∈
t
1
,
t
2
,
y
∈
t
-
,
0
.The passenger intensity distribution function is expressed as follows:(4)
f
r
s
x
g
r
s
y
q
r
s
,
x
∈
t
1
,
t
2
,
y
∈
t
-
,
0
.The distributions of travel demand depending on the expected departure time and ticket-booking time can be obtained utilizing the historical reservation data in the ticket-booking system. First, the historical actual boarding times of passengers can be directly obtained from the ticket-booking system; then, the intensity distributions depending on the actual boarding time can be calculated, which can be used to forecast the expected departure times of passengers. Hence, the intensity distributions depending on the expected departure time can be obtained using some forecasting methods, such as the exponential smoothing method and the moving average method. Similarly, the intensity distributions of travel demand depending on the ticket-booking time for all O-D pairs result from the passengers’ experiences of ticket-booking process and can be forecasted based on the historical reservation data.


### 3.2. Space-Time Network

LetΩ
=
T be the set of trains running on the network V
,
E. For each train T
∈
Ω, h
T is the number of stops and v
i
T is the i
t
h stop. At the i
t
h stop of train T, a
i
T is the arrival time and d
i
T is the departure time, which are also called the arrival node and the departure node, respectively. Let T
(
i
,
j
) be the segment of train T’s route from stop v
i
T to stop v
j
T, called the “train segment” here. The length of T
(
i
,
j
) is represented by T
(
i
,
j
). Specifically, T
(
i
,
i
+
1
) is called a “segment” for short.If a passenger of an O-D pairr
,
s transfers in turn to train segments to reach the destination, then the path can be expressed as follows:(5)
P
r
s
T
r
a
n
=
T
1
i
1
,
j
1
+
T
2
i
2
,
j
2
+
⋯
+
T
u
i
u
,
j
u
.Here, “+” refers to the transfer link between the train segments.A space-time networkV
,
A is designed based on the itineraries graph designed by Kaspi and Raviv [10], shown in Figure 3, where V is a set of space-time nodes and A is a set of space-time arcs. Any path P
r
s
T
r
a
n matches a route on the network.Figure 3
A diagram of nodes and arcs in the space-time network.Lets
∞ be a virtual node for all passengers with destination station s, called the end node. This produces the following: (6)
V
=
d
i
T
∣
1
≤
i
<
h
T
,
T
∈
Ω
∪
a
i
T
∣
1
<
i
≤
h
T
,
T
∈
Ω
∪
s
∞
∣
s
∈
V
.Space-time arcs include five categories (for more details, see Kaspi and Raviv [10]):(i)
The set of arcs from noded
i
T to node a
i
+
1
T is denoted as A
b
o
a
r
d.
(ii)
The set of arcs from nodea
i
T to node a
i
+
1
T is denoted as A
p
a
s
s.
(iii)
The set of arcs from nodea
i
T to node d
j
T
′ is denoted as A
t
r
a
n.
(iv)
The set of arcs from noded
i
T to node d
j
T
′ is denoted as A
w
a
i
t.
(v)
The set of arcs from nodea
i
T to node s
∞ is denoted as A
e
n
d.


## 3.1. Travel Demand and Distribution

A high-speed rail network is represented byV
,
E, where V is the set of station nodes and E is the set of arcs. The operating period for a given high-speed rail network is denoted by t
1
,
t
2 (trains running overnight are not considered). The set of O-D pairs is denoted as R
S
⊂
V
×
V, and the daily travel demand of an O-D pair is denoted by q
r
s
,
r
,
s
∈
R
S.For any given O-D pair, there is a distribution depending on the expected departure time for the travel demand, for example, from Beijing to Shanghai, as shown in Figure1. The intensity distribution function is denoted by f
r
s
x
,
x
∈
t
1
,
t
2
,
r
,
s
∈
R
S, satisfying the following:(1)
∫
t
1
t
2
f
r
s
x
d
x
=
q
r
s
,
r
,
s
∈
R
S
.Figure 1
Intensity distribution of travel demand from Beijing to Shanghai depending on expected departure time on 1 July 2014.According to the assumptions, all passengers book tickets in advance during the presale periodt
-
,
0 (t
- is negative, t
- is the maximum presale time ahead of the departure day, and 0 means the departure day) and the number of passengers at any ticket-booking time is given. Hence, there is a distribution depending on the ticket-booking time for the travel demand, for example, from Beijing to Shanghai, as shown in Figure 2. The distributions were called booking curves by Tsai [15]. The intensity distribution function is denoted by g
r
s
y
,
y
∈
t
-
,
0
,
r
,
s
∈
R
S, satisfying the following:(2)
∫
t
-
0
g
r
s
y
d
y
=
q
r
s
,
r
,
s
∈
R
S
.Figure 2
Intensity distribution of travel demand from Beijing to Shanghai depending on ticket-booking time on 1 July 2014.The authors assume that the above two variables are mutually independent; the combined probability density distribution function of travel demand is expressed as follows:(3)
f
r
s
x
g
r
s
y
q
r
s
2
,
x
∈
t
1
,
t
2
,
y
∈
t
-
,
0
.The passenger intensity distribution function is expressed as follows:(4)
f
r
s
x
g
r
s
y
q
r
s
,
x
∈
t
1
,
t
2
,
y
∈
t
-
,
0
.The distributions of travel demand depending on the expected departure time and ticket-booking time can be obtained utilizing the historical reservation data in the ticket-booking system. First, the historical actual boarding times of passengers can be directly obtained from the ticket-booking system; then, the intensity distributions depending on the actual boarding time can be calculated, which can be used to forecast the expected departure times of passengers. Hence, the intensity distributions depending on the expected departure time can be obtained using some forecasting methods, such as the exponential smoothing method and the moving average method. Similarly, the intensity distributions of travel demand depending on the ticket-booking time for all O-D pairs result from the passengers’ experiences of ticket-booking process and can be forecasted based on the historical reservation data.


## 3.2. Space-Time Network

LetΩ
=
T be the set of trains running on the network V
,
E. For each train T
∈
Ω, h
T is the number of stops and v
i
T is the i
t
h stop. At the i
t
h stop of train T, a
i
T is the arrival time and d
i
T is the departure time, which are also called the arrival node and the departure node, respectively. Let T
(
i
,
j
) be the segment of train T’s route from stop v
i
T to stop v
j
T, called the “train segment” here. The length of T
(
i
,
j
) is represented by T
(
i
,
j
). Specifically, T
(
i
,
i
+
1
) is called a “segment” for short.If a passenger of an O-D pairr
,
s transfers in turn to train segments to reach the destination, then the path can be expressed as follows:(5)
P
r
s
T
r
a
n
=
T
1
i
1
,
j
1
+
T
2
i
2
,
j
2
+
⋯
+
T
u
i
u
,
j
u
.Here, “+” refers to the transfer link between the train segments.A space-time networkV
,
A is designed based on the itineraries graph designed by Kaspi and Raviv [10], shown in Figure 3, where V is a set of space-time nodes and A is a set of space-time arcs. Any path P
r
s
T
r
a
n matches a route on the network.Figure 3
A diagram of nodes and arcs in the space-time network.Lets
∞ be a virtual node for all passengers with destination station s, called the end node. This produces the following: (6)
V
=
d
i
T
∣
1
≤
i
<
h
T
,
T
∈
Ω
∪
a
i
T
∣
1
<
i
≤
h
T
,
T
∈
Ω
∪
s
∞
∣
s
∈
V
.Space-time arcs include five categories (for more details, see Kaspi and Raviv [10]):(i)
The set of arcs from noded
i
T to node a
i
+
1
T is denoted as A
b
o
a
r
d.
(ii)
The set of arcs from nodea
i
T to node a
i
+
1
T is denoted as A
p
a
s
s.
(iii)
The set of arcs from nodea
i
T to node d
j
T
′ is denoted as A
t
r
a
n.
(iv)
The set of arcs from noded
i
T to node d
j
T
′ is denoted as A
w
a
i
t.
(v)
The set of arcs from nodea
i
T to node s
∞ is denoted as A
e
n
d.


## 4. Choices of Paths with Minimum Cost

Travel cost on a high-speed rail network consists of the ticket fare, travel time, and transfer cost. The ticket fare rate per kilometer based on trainT’s route is denoted as r
p
(
T
); the ticket fare of the path in (5) is calculated as ∑
k
=
1
u
r
p
T
k
·
T
k
(
i
k
,
j
k
).There is a risk for passengers to switch trains at a station; then, penalty cost is used and called the transfer cost, denoted asρ. The total transfer cost of the path in (5) is expressed as ∑
k
=
1
u
-
1
ρ, where u
-
1 are transfer times.The cost of the travel time is defined as the fatigue cost. Let the fatigue cost per unit time bew; then, the fatigue cost of the path in (5) is calculated as w
a
j
u
T
u
-
d
i
1
T
1.In conclusion, the cost of the path in (5) is expressed as follows:(7)
P
r
s
T
r
a
n
=
∑
k
=
1
u
r
p
T
k
·
T
k
i
k
,
j
k
+
∑
k
=
1
u
-
1
ρ
+
w
a
j
u
T
u
-
d
i
1
T
1
.In the space-time network, the costs of arcs are expressed as follows:(8)
Φ
=
r
p
T
·
T
i
,
i
+
1
+
w
a
i
+
1
T
-
d
i
T
,
d
i
T
,
a
i
+
1
T
∈
A
b
o
a
r
d
r
p
T
·
T
i
,
i
+
1
+
w
a
i
+
1
T
-
a
i
T
,
a
i
T
,
a
i
+
1
T
∈
A
p
a
s
s
ρ
+
w
d
j
T
′
-
a
i
T
,
a
i
T
,
d
j
T
′
∈
A
t
r
a
n
w
d
i
T
′
-
a
i
T
,
d
i
T
,
d
i
T
′
∈
A
w
a
i
t
0
,
a
i
T
,
s
∞
∈
A
e
n
d
.For an O-D pairr
,
s, a path is a route from node d
i
T to node s
∞ on the network V
,
A and the path with minimum cost is expressed as P
^
r
s
T
r
a
n
d
i
T, which can be found through a shortest path algorithm on the network. Network V
,
A is acyclic, so a shortest path search over the space-time arcs from node s
∞ backwards toward all other nodes is used for any node s
∈
V. The complexity of this method is linear regarding A for each end node.The actual boarding time of passengers may be earlier or later than the expected departure time and the time deviation would bring extra travel costs, which was also considered by Cascetta and Coppola [12]. For example, for a passenger of O-D pair r
,
s with an expected departure time x and actual boarding time d
i
T, a travel plan is defined here as adding a start arc x
,
d
i
T to path P
^
r
s
T
r
a
n
d
i
T, denoted as P
r
s
(
x
) (note that a travel plan starts with an expected departure time and a path starts with an actual boarding time; the latter is part of the former). Let the “early” cost and “late” cost per unit time be θ; then, the cost of the start arc x
,
d
i
T is expressed as θ
x
-
d
i
T.In conclusion, travel planP
r
s
(
x
) is expressed as follows:(9)
P
r
s
x
=
x
,
d
i
T
+
P
^
r
s
T
r
a
n
d
i
T
.At any ticket-booking timey
∈
t
-
,
0, passengers always choose the paths with the current minimum cost based on the available train seating capacity and such paths are effective. Hence, P
^
r
s
T
r
a
n
d
i
T is extended as P
^
r
s
T
r
a
n
d
i
T
,
y and the travel plan with minimum cost is denoted as P
^
r
s
x
,
y. According to (9), the authors obtain the following:(10)
P
^
r
s
x
,
y
=
min
⁡
θ
x
-
d
i
T
+
P
^
r
s
T
r
a
n
d
i
T
,
y
∣
v
i
T
=
r
,
T
∈
Ω
.


## 5. Solution Algorithm

The calculation of (10) can determine the best paths for all passengers, and then passengers on every train can be calculated. Considering that the ticket-booking time and the expected departure time are continuous variables, the computational tasks are large. Hence, a discretization method by partitioning the ticket-booking period and the expected departure period into several discrete intervals is designed.


### 5.1. Discretization

(1) The Partitioning of the Ticket-Booking Period. As the ticket-booking time continues, some train segments become fully occupied and the travel plans with minimum cost change. Hence, the authors take the time of any such change as a partition node to separate the ticket-booking period into several intervals, and, as a result, in any partition interval, the travel plan with the minimum cost remains constant for passengers of the same O-D pair and expected departure time.The authors set vectorY
=
y
0
,
y
1
,
…
,
y
N
′ with t
-
=
y
0
≤
y
1
≤
⋯
≤
y
N
′
=
0, where y
n
(
n
=
1,2
,
…
,
N
′
) is a partition node. The ticket-booking period is partitioned by vector Y. When the number of partition intervals is the minimum, such a partition Y is denoted as the optimal partition. In any partition interval y
n
-
1
,
y
n
n
=
1,2
,
…
,
N
′, the travel plan with the minimum cost remains constant for all passengers; hence, P
^
r
s
x
,
y is denoted as P
^
r
s
n
x and P
^
r
s
T
r
a
n
d
i
T
,
y is denoted as P
^
r
s
n
T
r
a
n
d
i
T.(2) The Partitioning of the Expected Departure Period. In the optimal partition interval y
n
,
y
n
+
1
(
n
=
0,2
,
…
,
N
′
-
1
), the travel plan cost θ
x
-
d
i
T
+
P
^
r
s
n
T
r
a
n
d
i
T is a piecewise linear function according to the expected departure time x. Hence, the expected departure period t
1
,
t
2 can be partitioned into M
r
=
d
i
T
∣
v
i
T
=
r
,
T
∈
Ω continuity intervals at most [16, 17], denoted as x
r
s
n
0
,
x
r
s
n
1
,
x
r
s
n
1
,
x
r
s
n
2
,
…
,
x
r
,
s
,
n
,
M
r
-
1
,
x
r
s
n
M
r. The authors set the vector X
=
x
r
s
n
m
R
S
×
N
′
×
M
r. In any interval x
r
s
n
m
,
x
r
,
s
,
n
,
m
+
1, the travel plans with minimum cost include the same path P
^
r
s
n
T
r
a
n
x
^
r
s
n
m, where x
^
r
s
n
m is called the common actual boarding time, and if x
^
r
s
n
m
∈
x
r
s
n
m
,
x
r
,
s
,
n
,
m
+
1, then such a partition X is denoted as the optimal partition. Obviously, the authors obtain the following:(11)
P
^
r
s
n
x
^
r
s
n
m
=
x
^
r
s
n
m
,
x
^
r
s
n
m
+
P
^
r
s
n
T
r
a
n
x
^
r
s
n
m
=
P
^
r
s
n
T
r
a
n
x
^
r
s
n
m
.In conclusion, if optimal partitionsX
,
Y are obtained, the travel plan with minimum cost is P
^
r
s
n
x
=
x
,
x
^
r
s
n
m
+
P
^
r
s
n
T
r
a
n
x
^
r
s
n
m for passengers in the partition area x
r
s
n
m
,
x
r
,
s
,
n
,
m
+
1
×
y
n
,
y
n
+
1
,
0
≤
m
<
M
r
,
0
≤
n
<
N
′
,
r
,
s
∈
R
S.


### 5.2. Optimal Partitions

To obtain the optimal partitionsX
,
Y, the authors start from the ticket-booking time y
0
=
t
-. For any given optimal partition node y
n, first, a method is designed to calculate the optimal partition X of the expected departure period; then, the next optimal partition node y
n
+
1 is calculated, and as a result some train segment is fully occupied when the passengers in the interval y
n
,
y
n
+
1 are loaded or y
n
+
1
=
0. The process is repeated until y
n
+
1
=
0 or until a feasible assignment does not exist.


#### 5.2.1. Optimal Partitioning of Expected Departure Period

A simple example is shown in Figure4 to illustrate the partition process. There are seven departure nodes at station r and the paths with the minimum cost are P
^
r
s
n
T
r
a
n
x
~
i
,
i
=
1,2
,
…
,
7. Passengers always choose the travel plan with the minimum cost, so only paths P
^
r
s
n
T
r
a
n
x
~
1, P
^
r
s
n
T
r
a
n
x
~
4, P
^
r
s
n
T
r
a
n
x
~
5, and P
^
r
s
n
T
r
a
n
x
~
7 are chosen by passengers, and the costs of travel plans which include the other three paths are too high, so no passengers choose them. Then, the service period t
1
,
t
2 is partitioned into four intervals by the three vertical dashed lines. The time sequence {
x
r
s
n
0
,
x
r
s
n
1
,
…
,
x
r
s
n
4
} in Figure 4 is the optimal partition. For example, passengers with an expected departure time in the second interval choose path P
^
r
s
n
T
r
a
n
x
~
4.Figure 4
Optimal partitioning of the expected departure time.The rooftops method [16, 17] was used based on only one line and all trains have the same origin and destination, which is not suitable for complicated networks in this paper. Hence, a modified rooftops method is designed as follows. Assuming that there exists at least one effective travel plan for the O-D pair r
,
s, the set of trains passing through station r is denoted as Ω
r. According to the definition of the optimal partition of the expected departure period, if departure node d
i
T is the common actual boarding time of passengers at station r in an optimal interval, then it satisfies (11), which is equivalent to the following:(12)
P
^
r
s
n
T
r
a
n
d
i
T
<
min
⁡
θ
d
i
T
-
d
i
′
T
′
+
P
^
r
s
n
T
r
a
n
d
i
′
T
′
∣
d
i
′
T
′
≠
d
i
T
,
v
i
′
T
′
=
r
,
T
′
∈
Ω
r
.Giveny
n and O-D pair r
,
s, the correctness of (12) for all departure nodes at station r can be verified with complexity O
M
r, shown in the Appendix. Then, the departure node satisfying (12) is the common actual boarding time; that is, x
^
r
s
n
m
,
0
≤
m
<
M
r
,
r
,
s
∈
R
S.Timex
r
,
s
,
n
,
m
+
1 (0
≤
m
≤
M
r
-
2) is the optimal partition node between the interval x
r
s
n
m
,
x
r
,
s
,
n
,
m
+
1 and x
r
,
s
,
n
,
m
+
1
,
x
r
,
s
,
n
,
m
+
2, so it satisfies the following equation:(13)
θ
x
r
,
s
,
n
,
m
+
1
-
x
^
r
s
n
m
+
P
^
r
s
n
x
^
r
s
n
m
=
θ
x
^
r
,
s
,
n
,
m
+
1
-
x
r
,
s
,
n
,
m
+
1
+
P
^
r
s
n
x
^
r
,
s
,
n
,
m
+
1
.Then, the following can be obtained:(14)
x
r
,
s
,
n
,
m
+
1
=
1
2
θ
θ
x
^
r
s
n
m
-
P
^
r
s
n
x
^
r
s
n
m
+
θ
x
^
r
,
s
,
n
,
m
+
1
+
P
^
r
s
n
x
^
r
,
s
,
n
,
m
+
1
.Besides, let x
r
s
n
0
=
t
1 and x
r
s
n
M
r
=
t
2.


#### 5.2.2. Optimal Partitioning of Ticket-Booking Period

Assuming that the optimal partition nodey
n has been obtained, the authors solve the next optimal partition node y
n
+
1. In the partition area x
r
s
n
m
,
x
r
,
s
,
n
,
m
+
1
×
[
y
n
,
y
n
+
1, the number of passengers is (15)
F
r
s
n
m
=
∫
y
n
y
n
+
1
∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
1
q
r
s
f
r
s
x
g
r
s
y
d
x
d
y
.Those passengers choose the same pathP
^
r
s
n
T
r
a
n
x
^
r
s
n
m, so in the interval [
y
0
,
y
n
), the number of passengers passing through node a
i
T (passengers boarding on segment T
(
i
-
1
,
i
)) is(16)
F
T
n
,
i
=
∑
u
=
0
n
-
1
∑
r
,
s
∈
R
S
∑
m
=
0
M
r
-
1
δ
P
^
r
s
n
T
r
a
n
x
^
r
s
u
m
,
a
i
T
F
r
s
u
m
,where δ
P
,
a is the correlation function between path P and node a. If node a lies on path P, then δ
P
,
a
=
1; otherwise, δ
P
,
a
=
0. Assuming that a ticket-booking time y
n
+
1
′ satisfies y
n
≤
y
n
+
1
′
≤
y
n
+
1, then, in the interval [
y
n
,
y
n
+
1
′, the number of passengers through node a
i
T is as follows:(17)
F
T
n
′
i
=
∑
r
,
s
∈
R
S
∑
m
=
0
M
r
-
1
δ
P
^
r
s
n
T
r
a
n
x
^
r
s
n
m
,
a
i
T
F
r
s
n
m
′
,where F
r
s
n
m
′
=
∫
y
n
y
n
+
1
′
∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
(
1
/
q
r
s
)
f
r
s
x
g
r
s
y
d
x
d
y.In the networkV
,
A, passengers boarding on segments all pass through arrival nodes; hence, the capacity constraint on segment T
i
-
1
,
i (1
<
i
≤
h
T
,
T
∈
Ω) actually acts on node a
i
T, denoted as C
T
i, and capacity constraints are considered only on nodes in the set V
a
=
a
i
T
∣
1
<
i
≤
h
T
,
T
∈
Ω
⊂
V in the following parts of the paper.According to the definition of the optimal partition nodey
n
+
1, the authors obtain the following:(18)
y
n
+
1
=
max
⁡
y
n
+
1
′
∣
C
T
i
-
F
T
n
,
i
-
F
T
n
′
i
≥
0
,
a
i
T
∈
V
a
.Then, in the interval[
y
n
,
y
n
+
1, the number of passengers passing through node a
i
T is as follows:(19)
F
T
n
i
=
∑
r
,
s
∈
R
S
∑
m
=
0
M
r
-
1
δ
P
^
r
s
n
T
r
a
n
x
^
r
s
n
m
,
a
i
T
F
r
s
n
m
.


### 5.3. Algorithm Framework

Based on the above description, the general structure of the solution algorithm is developed as shown in Algorithm1.Algorithm 1
Input  high-speed rail network (
V
,
E
), space-time network (
V
,
A
), service period [
t
1
,
t
2
], train set Ω, O-D demand q
r
s,  (
r
,
s
)
∈
R
S,
intensity distribution functionsf
r
s
(
x
),  x
∈
[
t
1
,
t
2
], and g
r
s
(
y
),  y
∈
[
t
-
,
0
];
Output  passengers on every train segment, that is, F
T
(
n
,
i
),  1
<
i
≤
h
(
T
),  T
∈
Ω.
Begin
n
←
0,  y
0
←
t
-;
for alli
=
2,3
,
…
,
h
(
T
)
-
1,  T
∈
Ω do F
T
(
n
,
i
)
←
0;
whiley
n
<
0 do
begin
Search for the path with the minimum cost on the network(
V
,
A
), then obtain
P
^
r
s
n
T
r
a
n
d
i
T
∣
v
i
T
=
r
,
1
≤
i
<
n
T
,
T
∈
Ω
,
r
,
s
∈
R
S;
If an effective path does not exist, then break;
Obtain the optimal partitionX by the modified rooftops method;
Calculate the next optimal partition nodey
n
+
1 using (18);
CalculateF
r
s
n
m,  r
,
s
∈
R
S,  0
≤
m
<
M
r using (15);
CalculateF
T
n
(
i
),  1
<
i
≤
h
(
T
),  T
∈
Ω using (19);
Load passengers on network(
V
,
A
):
for alla
i
T
∈
V
a  do F
T
(
n
+
1
,
i
)
←
F
T
(
n
,
i
)
+
F
T
n
(
i
);
n
←
n
+
1;
end
endIn Algorithm1, n denotes the outer iterations. For example, n
=
3 means the third ticket-booking phase. In every phase, all the travel plans with minimum cost remain constant.For general intensity distribution functionsf
r
s
x
,
x
∈
t
1
,
t
2 and g
r
s
y
,
y
∈
t
-
,
0
,
r
,
s
∈
R
S, a numerical method for calculating y
n
+
1 is needed by (18), for example, the dichotomy method. But the computational task is large. For some special situations, a simplified method, as shown in the next section, can be designed.


### 5.4. A Special Case

In this section, the authors assume that there exists a probability density functiong
y that satisfies g
y
≡
g
r
s
y
/
q
r
s for any r
,
s
∈
R
S; that is, the probability density function is the same for any r
,
s
∈
R
S, and f
r
s
x is a step function with an hourly interval.In Algorithm1, the optimal partition node y
n
+
1 calculated by (18) has two situations. One is y
n
+
1
=
0 and the other is y
n
+
1
<
0. If y
n
+
1
=
0, then Algorithm 1 terminates; if y
n
+
1
<
0, then the following is satisfied:(20)
min
⁡
C
T
i
-
F
T
i
-
F
T
n
i
∣
a
i
T
∈
V
a
=
0
.Let a
i
′
T
′ be the solution of the above equation; then, the following is true:(21)
C
T
′
i
′
-
F
T
′
i
′
=
F
T
′
n
i
′
.And because g
y
≡
g
r
s
y
/
q
r
s, then (22)
F
r
s
n
m
=
∫
y
n
y
n
+
1
∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
f
r
s
x
g
y
d
x
d
y
=
∫
y
n
y
n
+
1
g
y
d
y
∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
f
r
s
x
d
x
.Hence,(23)
C
T
′
i
′
-
F
T
′
i
′
=
F
T
′
n
i
′
=
∫
y
n
y
n
+
1
g
y
d
y
∑
r
,
s
∈
R
S
∑
m
=
0
M
r
-
1
δ
P
^
r
s
n
T
r
a
n
x
^
r
s
n
m
,
a
i
′
T
′
∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
f
r
s
x
d
x
.Then,(24)
∫
y
n
y
n
+
1
g
y
d
y
=
C
T
′
i
′
-
F
T
′
i
′
∑
r
,
s
∈
R
S
∑
m
=
0
M
r
-
1
δ
P
^
r
s
n
T
r
a
n
x
^
r
s
n
m
,
a
i
′
T
′
∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
f
r
s
x
d
x
.Let(25)
Δ
n
=
min
⁡
C
T
i
-
F
T
i
∑
r
,
s
∈
R
S
∑
m
=
0
M
r
-
1
δ
P
^
r
s
n
T
r
a
n
x
^
r
s
n
m
,
a
i
T
∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
f
r
s
x
d
x
∣
a
i
T
∈
V
a
.Then, Δ
n
=
∫
y
n
y
n
+
1
g
y
d
y. Because g
y is a probability density function, 0
<
Δ
n
<
1. Equation (22) is rewritten as follows:(26)
F
r
s
n
m
=
Δ
n
∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
f
r
s
x
d
x
.Then,(27)
∑
m
=
0
M
r
-
1
F
r
s
n
m
=
Δ
n
∑
m
=
0
M
r
-
1
∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
f
r
s
x
d
x
=
Δ
n
∫
t
1
t
2
f
r
s
x
d
x
=
Δ
n
q
r
s
,
i
f
∃
v
i
T
=
r
,
T
∈
Ω
:
P
^
r
s
n
d
i
T
<
∞
Δ
n
∫
t
1
t
1
f
r
s
x
d
x
=
0
,
i
f
∄
v
i
T
=
r
,
T
∈
Ω
:
P
^
r
s
n
d
i
T
<
∞
.Equation (27) shows that if an effective travel plan exists for the O-D pair r
,
s
∈
R
S, the number of passengers booking tickets is Δ
n
q
r
s during period [
y
n
,
y
n
+
1. The number of passengers booking tickets for all O-D pairs is determined with the same proportion Δ
n by (25) during the period [
y
n
,
y
n
+
1. Calculating Δ
n using (25) does not require any specific probability density function g
y or partition time y
n
+
1. Hence, if the authors obtain Δ
n, then the number of passengers in period [
y
n
,
y
n
+
1 can be calculated using (26).Based on the above analysis, at thenth iteration, the process of passenger assignment is determined as follows. First, for the O-D pair r
,
s
∈
R
S and m
:
0
≤
m
<
M
r, according to the expectation of passengers, there are ∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
f
r
s
x
d
x passengers loaded on the path P
^
r
s
n
T
r
a
n
x
^
r
s
n
m and the expected number of passengers in every segment is obtained. Second, proportion Δ
n is calculated using (25), and the actual number of passengers loaded on segments is Δ
n times the expected one. Finally, if Δ
n
=
1
-
∑
u
=
0
n
-
1
Δ
u, that is, ∑
u
=
0
n
Δ
u
=
1, then the algorithm terminates (i.e., equal to y
n
+
1
=
0); otherwise, if Δ
n
<
1
-
∑
u
=
0
n
-
1
Δ
u, that is, ∑
u
=
0
n
Δ
u
<
1, then the algorithm continues to the next period. Hence, the authors obtain a simple method for the calculation of Algorithm 1.Under the assumption, the authors analyze the computational complexity of Algorithm1 as follows. The maximum iteration of the outer loop is N
=
O
A
b
o
a
r
d. In the body loop, at the nth iteration, there are four parts. These are, in order, as follows.First, the complexity of searching all paths with minimum cost for an end node isO
A and A
<
5
A
b
o
a
r
d; hence, the complexity of searching all paths with minimum cost for all end nodes is O
A
b
o
a
r
d
V.Second, the authors solve the optimal partitionX. This is a two-layer loop. The outer layer is for all O-D pairs, and the iterations of the inner layer are O
M
r. Hence, the complexity is O
V
∑
r
∈
V
M
r
=
O
A
b
o
a
r
d
V.Third, the authors calculate∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
f
r
s
x
d
x
,
0
≤
m
<
M
r
,
r
,
s
∈
R
S. The number of integrals is O
V
∑
r
∈
V
M
r
=
O
A
b
o
a
r
d
V. The complexity of calculating each integral is O
1 because f
r
s
x is an hourly step function. Hence, the complexity for calculating all integrals is O
A
b
o
a
r
d
V.Fourth, the authors load passengers on the paths with minimum cost. All the shortest paths to the end nodes
∞ generate a shortest path tree with a root node s
∞. After removing the nodes finishing the passenger loading process from the shortest path tree, the authors select a leaf node of the shortest path tree as the current node performing the passenger loading process. Following the shortest path, the authors load the passengers accumulated at the current node to the next neighboring node until the passengers at each node are loaded at the root node s
∞. Because every arc is processed at most once, the computational complexity for loading all passengers at one root node s
∞ is O
A
b
o
a
r
d
. Therefore, the computational complexity for loading passengers at all root nodes s
∞
∈
V is O
A
b
o
a
r
d
V.According to the third and fourth steps, the complexities of calculatingΔ
n, F
r
s
n
m
,
0
≤
m
<
M
r
,
r
,
s
∈
R
S, and F
T
n
i
,
1
<
i
≤
h
T
,
T
∈
Ω, are all O
A
b
o
a
r
d
V.In conclusion, the computational complexity of Algorithm1 under the assumption is O
A
b
o
a
r
d
2
V.


## 5.1. Discretization

(1) The Partitioning of the Ticket-Booking Period. As the ticket-booking time continues, some train segments become fully occupied and the travel plans with minimum cost change. Hence, the authors take the time of any such change as a partition node to separate the ticket-booking period into several intervals, and, as a result, in any partition interval, the travel plan with the minimum cost remains constant for passengers of the same O-D pair and expected departure time.The authors set vectorY
=
y
0
,
y
1
,
…
,
y
N
′ with t
-
=
y
0
≤
y
1
≤
⋯
≤
y
N
′
=
0, where y
n
(
n
=
1,2
,
…
,
N
′
) is a partition node. The ticket-booking period is partitioned by vector Y. When the number of partition intervals is the minimum, such a partition Y is denoted as the optimal partition. In any partition interval y
n
-
1
,
y
n
n
=
1,2
,
…
,
N
′, the travel plan with the minimum cost remains constant for all passengers; hence, P
^
r
s
x
,
y is denoted as P
^
r
s
n
x and P
^
r
s
T
r
a
n
d
i
T
,
y is denoted as P
^
r
s
n
T
r
a
n
d
i
T.(2) The Partitioning of the Expected Departure Period. In the optimal partition interval y
n
,
y
n
+
1
(
n
=
0,2
,
…
,
N
′
-
1
), the travel plan cost θ
x
-
d
i
T
+
P
^
r
s
n
T
r
a
n
d
i
T is a piecewise linear function according to the expected departure time x. Hence, the expected departure period t
1
,
t
2 can be partitioned into M
r
=
d
i
T
∣
v
i
T
=
r
,
T
∈
Ω continuity intervals at most [16, 17], denoted as x
r
s
n
0
,
x
r
s
n
1
,
x
r
s
n
1
,
x
r
s
n
2
,
…
,
x
r
,
s
,
n
,
M
r
-
1
,
x
r
s
n
M
r. The authors set the vector X
=
x
r
s
n
m
R
S
×
N
′
×
M
r. In any interval x
r
s
n
m
,
x
r
,
s
,
n
,
m
+
1, the travel plans with minimum cost include the same path P
^
r
s
n
T
r
a
n
x
^
r
s
n
m, where x
^
r
s
n
m is called the common actual boarding time, and if x
^
r
s
n
m
∈
x
r
s
n
m
,
x
r
,
s
,
n
,
m
+
1, then such a partition X is denoted as the optimal partition. Obviously, the authors obtain the following:(11)
P
^
r
s
n
x
^
r
s
n
m
=
x
^
r
s
n
m
,
x
^
r
s
n
m
+
P
^
r
s
n
T
r
a
n
x
^
r
s
n
m
=
P
^
r
s
n
T
r
a
n
x
^
r
s
n
m
.In conclusion, if optimal partitionsX
,
Y are obtained, the travel plan with minimum cost is P
^
r
s
n
x
=
x
,
x
^
r
s
n
m
+
P
^
r
s
n
T
r
a
n
x
^
r
s
n
m for passengers in the partition area x
r
s
n
m
,
x
r
,
s
,
n
,
m
+
1
×
y
n
,
y
n
+
1
,
0
≤
m
<
M
r
,
0
≤
n
<
N
′
,
r
,
s
∈
R
S.


## 5.2. Optimal Partitions

To obtain the optimal partitionsX
,
Y, the authors start from the ticket-booking time y
0
=
t
-. For any given optimal partition node y
n, first, a method is designed to calculate the optimal partition X of the expected departure period; then, the next optimal partition node y
n
+
1 is calculated, and as a result some train segment is fully occupied when the passengers in the interval y
n
,
y
n
+
1 are loaded or y
n
+
1
=
0. The process is repeated until y
n
+
1
=
0 or until a feasible assignment does not exist.


### 5.2.1. Optimal Partitioning of Expected Departure Period

A simple example is shown in Figure4 to illustrate the partition process. There are seven departure nodes at station r and the paths with the minimum cost are P
^
r
s
n
T
r
a
n
x
~
i
,
i
=
1,2
,
…
,
7. Passengers always choose the travel plan with the minimum cost, so only paths P
^
r
s
n
T
r
a
n
x
~
1, P
^
r
s
n
T
r
a
n
x
~
4, P
^
r
s
n
T
r
a
n
x
~
5, and P
^
r
s
n
T
r
a
n
x
~
7 are chosen by passengers, and the costs of travel plans which include the other three paths are too high, so no passengers choose them. Then, the service period t
1
,
t
2 is partitioned into four intervals by the three vertical dashed lines. The time sequence {
x
r
s
n
0
,
x
r
s
n
1
,
…
,
x
r
s
n
4
} in Figure 4 is the optimal partition. For example, passengers with an expected departure time in the second interval choose path P
^
r
s
n
T
r
a
n
x
~
4.Figure 4
Optimal partitioning of the expected departure time.The rooftops method [16, 17] was used based on only one line and all trains have the same origin and destination, which is not suitable for complicated networks in this paper. Hence, a modified rooftops method is designed as follows. Assuming that there exists at least one effective travel plan for the O-D pair r
,
s, the set of trains passing through station r is denoted as Ω
r. According to the definition of the optimal partition of the expected departure period, if departure node d
i
T is the common actual boarding time of passengers at station r in an optimal interval, then it satisfies (11), which is equivalent to the following:(12)
P
^
r
s
n
T
r
a
n
d
i
T
<
min
⁡
θ
d
i
T
-
d
i
′
T
′
+
P
^
r
s
n
T
r
a
n
d
i
′
T
′
∣
d
i
′
T
′
≠
d
i
T
,
v
i
′
T
′
=
r
,
T
′
∈
Ω
r
.Giveny
n and O-D pair r
,
s, the correctness of (12) for all departure nodes at station r can be verified with complexity O
M
r, shown in the Appendix. Then, the departure node satisfying (12) is the common actual boarding time; that is, x
^
r
s
n
m
,
0
≤
m
<
M
r
,
r
,
s
∈
R
S.Timex
r
,
s
,
n
,
m
+
1 (0
≤
m
≤
M
r
-
2) is the optimal partition node between the interval x
r
s
n
m
,
x
r
,
s
,
n
,
m
+
1 and x
r
,
s
,
n
,
m
+
1
,
x
r
,
s
,
n
,
m
+
2, so it satisfies the following equation:(13)
θ
x
r
,
s
,
n
,
m
+
1
-
x
^
r
s
n
m
+
P
^
r
s
n
x
^
r
s
n
m
=
θ
x
^
r
,
s
,
n
,
m
+
1
-
x
r
,
s
,
n
,
m
+
1
+
P
^
r
s
n
x
^
r
,
s
,
n
,
m
+
1
.Then, the following can be obtained:(14)
x
r
,
s
,
n
,
m
+
1
=
1
2
θ
θ
x
^
r
s
n
m
-
P
^
r
s
n
x
^
r
s
n
m
+
θ
x
^
r
,
s
,
n
,
m
+
1
+
P
^
r
s
n
x
^
r
,
s
,
n
,
m
+
1
.Besides, let x
r
s
n
0
=
t
1 and x
r
s
n
M
r
=
t
2.


### 5.2.2. Optimal Partitioning of Ticket-Booking Period

Assuming that the optimal partition nodey
n has been obtained, the authors solve the next optimal partition node y
n
+
1. In the partition area x
r
s
n
m
,
x
r
,
s
,
n
,
m
+
1
×
[
y
n
,
y
n
+
1, the number of passengers is (15)
F
r
s
n
m
=
∫
y
n
y
n
+
1
∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
1
q
r
s
f
r
s
x
g
r
s
y
d
x
d
y
.Those passengers choose the same pathP
^
r
s
n
T
r
a
n
x
^
r
s
n
m, so in the interval [
y
0
,
y
n
), the number of passengers passing through node a
i
T (passengers boarding on segment T
(
i
-
1
,
i
)) is(16)
F
T
n
,
i
=
∑
u
=
0
n
-
1
∑
r
,
s
∈
R
S
∑
m
=
0
M
r
-
1
δ
P
^
r
s
n
T
r
a
n
x
^
r
s
u
m
,
a
i
T
F
r
s
u
m
,where δ
P
,
a is the correlation function between path P and node a. If node a lies on path P, then δ
P
,
a
=
1; otherwise, δ
P
,
a
=
0. Assuming that a ticket-booking time y
n
+
1
′ satisfies y
n
≤
y
n
+
1
′
≤
y
n
+
1, then, in the interval [
y
n
,
y
n
+
1
′, the number of passengers through node a
i
T is as follows:(17)
F
T
n
′
i
=
∑
r
,
s
∈
R
S
∑
m
=
0
M
r
-
1
δ
P
^
r
s
n
T
r
a
n
x
^
r
s
n
m
,
a
i
T
F
r
s
n
m
′
,where F
r
s
n
m
′
=
∫
y
n
y
n
+
1
′
∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
(
1
/
q
r
s
)
f
r
s
x
g
r
s
y
d
x
d
y.In the networkV
,
A, passengers boarding on segments all pass through arrival nodes; hence, the capacity constraint on segment T
i
-
1
,
i (1
<
i
≤
h
T
,
T
∈
Ω) actually acts on node a
i
T, denoted as C
T
i, and capacity constraints are considered only on nodes in the set V
a
=
a
i
T
∣
1
<
i
≤
h
T
,
T
∈
Ω
⊂
V in the following parts of the paper.According to the definition of the optimal partition nodey
n
+
1, the authors obtain the following:(18)
y
n
+
1
=
max
⁡
y
n
+
1
′
∣
C
T
i
-
F
T
n
,
i
-
F
T
n
′
i
≥
0
,
a
i
T
∈
V
a
.Then, in the interval[
y
n
,
y
n
+
1, the number of passengers passing through node a
i
T is as follows:(19)
F
T
n
i
=
∑
r
,
s
∈
R
S
∑
m
=
0
M
r
-
1
δ
P
^
r
s
n
T
r
a
n
x
^
r
s
n
m
,
a
i
T
F
r
s
n
m
.


## 5.2.1. Optimal Partitioning of Expected Departure Period

A simple example is shown in Figure4 to illustrate the partition process. There are seven departure nodes at station r and the paths with the minimum cost are P
^
r
s
n
T
r
a
n
x
~
i
,
i
=
1,2
,
…
,
7. Passengers always choose the travel plan with the minimum cost, so only paths P
^
r
s
n
T
r
a
n
x
~
1, P
^
r
s
n
T
r
a
n
x
~
4, P
^
r
s
n
T
r
a
n
x
~
5, and P
^
r
s
n
T
r
a
n
x
~
7 are chosen by passengers, and the costs of travel plans which include the other three paths are too high, so no passengers choose them. Then, the service period t
1
,
t
2 is partitioned into four intervals by the three vertical dashed lines. The time sequence {
x
r
s
n
0
,
x
r
s
n
1
,
…
,
x
r
s
n
4
} in Figure 4 is the optimal partition. For example, passengers with an expected departure time in the second interval choose path P
^
r
s
n
T
r
a
n
x
~
4.Figure 4
Optimal partitioning of the expected departure time.The rooftops method [16, 17] was used based on only one line and all trains have the same origin and destination, which is not suitable for complicated networks in this paper. Hence, a modified rooftops method is designed as follows. Assuming that there exists at least one effective travel plan for the O-D pair r
,
s, the set of trains passing through station r is denoted as Ω
r. According to the definition of the optimal partition of the expected departure period, if departure node d
i
T is the common actual boarding time of passengers at station r in an optimal interval, then it satisfies (11), which is equivalent to the following:(12)
P
^
r
s
n
T
r
a
n
d
i
T
<
min
⁡
θ
d
i
T
-
d
i
′
T
′
+
P
^
r
s
n
T
r
a
n
d
i
′
T
′
∣
d
i
′
T
′
≠
d
i
T
,
v
i
′
T
′
=
r
,
T
′
∈
Ω
r
.Giveny
n and O-D pair r
,
s, the correctness of (12) for all departure nodes at station r can be verified with complexity O
M
r, shown in the Appendix. Then, the departure node satisfying (12) is the common actual boarding time; that is, x
^
r
s
n
m
,
0
≤
m
<
M
r
,
r
,
s
∈
R
S.Timex
r
,
s
,
n
,
m
+
1 (0
≤
m
≤
M
r
-
2) is the optimal partition node between the interval x
r
s
n
m
,
x
r
,
s
,
n
,
m
+
1 and x
r
,
s
,
n
,
m
+
1
,
x
r
,
s
,
n
,
m
+
2, so it satisfies the following equation:(13)
θ
x
r
,
s
,
n
,
m
+
1
-
x
^
r
s
n
m
+
P
^
r
s
n
x
^
r
s
n
m
=
θ
x
^
r
,
s
,
n
,
m
+
1
-
x
r
,
s
,
n
,
m
+
1
+
P
^
r
s
n
x
^
r
,
s
,
n
,
m
+
1
.Then, the following can be obtained:(14)
x
r
,
s
,
n
,
m
+
1
=
1
2
θ
θ
x
^
r
s
n
m
-
P
^
r
s
n
x
^
r
s
n
m
+
θ
x
^
r
,
s
,
n
,
m
+
1
+
P
^
r
s
n
x
^
r
,
s
,
n
,
m
+
1
.Besides, let x
r
s
n
0
=
t
1 and x
r
s
n
M
r
=
t
2.


## 5.2.2. Optimal Partitioning of Ticket-Booking Period

Assuming that the optimal partition nodey
n has been obtained, the authors solve the next optimal partition node y
n
+
1. In the partition area x
r
s
n
m
,
x
r
,
s
,
n
,
m
+
1
×
[
y
n
,
y
n
+
1, the number of passengers is (15)
F
r
s
n
m
=
∫
y
n
y
n
+
1
∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
1
q
r
s
f
r
s
x
g
r
s
y
d
x
d
y
.Those passengers choose the same pathP
^
r
s
n
T
r
a
n
x
^
r
s
n
m, so in the interval [
y
0
,
y
n
), the number of passengers passing through node a
i
T (passengers boarding on segment T
(
i
-
1
,
i
)) is(16)
F
T
n
,
i
=
∑
u
=
0
n
-
1
∑
r
,
s
∈
R
S
∑
m
=
0
M
r
-
1
δ
P
^
r
s
n
T
r
a
n
x
^
r
s
u
m
,
a
i
T
F
r
s
u
m
,where δ
P
,
a is the correlation function between path P and node a. If node a lies on path P, then δ
P
,
a
=
1; otherwise, δ
P
,
a
=
0. Assuming that a ticket-booking time y
n
+
1
′ satisfies y
n
≤
y
n
+
1
′
≤
y
n
+
1, then, in the interval [
y
n
,
y
n
+
1
′, the number of passengers through node a
i
T is as follows:(17)
F
T
n
′
i
=
∑
r
,
s
∈
R
S
∑
m
=
0
M
r
-
1
δ
P
^
r
s
n
T
r
a
n
x
^
r
s
n
m
,
a
i
T
F
r
s
n
m
′
,where F
r
s
n
m
′
=
∫
y
n
y
n
+
1
′
∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
(
1
/
q
r
s
)
f
r
s
x
g
r
s
y
d
x
d
y.In the networkV
,
A, passengers boarding on segments all pass through arrival nodes; hence, the capacity constraint on segment T
i
-
1
,
i (1
<
i
≤
h
T
,
T
∈
Ω) actually acts on node a
i
T, denoted as C
T
i, and capacity constraints are considered only on nodes in the set V
a
=
a
i
T
∣
1
<
i
≤
h
T
,
T
∈
Ω
⊂
V in the following parts of the paper.According to the definition of the optimal partition nodey
n
+
1, the authors obtain the following:(18)
y
n
+
1
=
max
⁡
y
n
+
1
′
∣
C
T
i
-
F
T
n
,
i
-
F
T
n
′
i
≥
0
,
a
i
T
∈
V
a
.Then, in the interval[
y
n
,
y
n
+
1, the number of passengers passing through node a
i
T is as follows:(19)
F
T
n
i
=
∑
r
,
s
∈
R
S
∑
m
=
0
M
r
-
1
δ
P
^
r
s
n
T
r
a
n
x
^
r
s
n
m
,
a
i
T
F
r
s
n
m
.


## 5.3. Algorithm Framework

Based on the above description, the general structure of the solution algorithm is developed as shown in Algorithm1.Algorithm 1
Input  high-speed rail network (
V
,
E
), space-time network (
V
,
A
), service period [
t
1
,
t
2
], train set Ω, O-D demand q
r
s,  (
r
,
s
)
∈
R
S,
intensity distribution functionsf
r
s
(
x
),  x
∈
[
t
1
,
t
2
], and g
r
s
(
y
),  y
∈
[
t
-
,
0
];
Output  passengers on every train segment, that is, F
T
(
n
,
i
),  1
<
i
≤
h
(
T
),  T
∈
Ω.
Begin
n
←
0,  y
0
←
t
-;
for alli
=
2,3
,
…
,
h
(
T
)
-
1,  T
∈
Ω do F
T
(
n
,
i
)
←
0;
whiley
n
<
0 do
begin
Search for the path with the minimum cost on the network(
V
,
A
), then obtain
P
^
r
s
n
T
r
a
n
d
i
T
∣
v
i
T
=
r
,
1
≤
i
<
n
T
,
T
∈
Ω
,
r
,
s
∈
R
S;
If an effective path does not exist, then break;
Obtain the optimal partitionX by the modified rooftops method;
Calculate the next optimal partition nodey
n
+
1 using (18);
CalculateF
r
s
n
m,  r
,
s
∈
R
S,  0
≤
m
<
M
r using (15);
CalculateF
T
n
(
i
),  1
<
i
≤
h
(
T
),  T
∈
Ω using (19);
Load passengers on network(
V
,
A
):
for alla
i
T
∈
V
a  do F
T
(
n
+
1
,
i
)
←
F
T
(
n
,
i
)
+
F
T
n
(
i
);
n
←
n
+
1;
end
endIn Algorithm1, n denotes the outer iterations. For example, n
=
3 means the third ticket-booking phase. In every phase, all the travel plans with minimum cost remain constant.For general intensity distribution functionsf
r
s
x
,
x
∈
t
1
,
t
2 and g
r
s
y
,
y
∈
t
-
,
0
,
r
,
s
∈
R
S, a numerical method for calculating y
n
+
1 is needed by (18), for example, the dichotomy method. But the computational task is large. For some special situations, a simplified method, as shown in the next section, can be designed.


## 5.4. A Special Case

In this section, the authors assume that there exists a probability density functiong
y that satisfies g
y
≡
g
r
s
y
/
q
r
s for any r
,
s
∈
R
S; that is, the probability density function is the same for any r
,
s
∈
R
S, and f
r
s
x is a step function with an hourly interval.In Algorithm1, the optimal partition node y
n
+
1 calculated by (18) has two situations. One is y
n
+
1
=
0 and the other is y
n
+
1
<
0. If y
n
+
1
=
0, then Algorithm 1 terminates; if y
n
+
1
<
0, then the following is satisfied:(20)
min
⁡
C
T
i
-
F
T
i
-
F
T
n
i
∣
a
i
T
∈
V
a
=
0
.Let a
i
′
T
′ be the solution of the above equation; then, the following is true:(21)
C
T
′
i
′
-
F
T
′
i
′
=
F
T
′
n
i
′
.And because g
y
≡
g
r
s
y
/
q
r
s, then (22)
F
r
s
n
m
=
∫
y
n
y
n
+
1
∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
f
r
s
x
g
y
d
x
d
y
=
∫
y
n
y
n
+
1
g
y
d
y
∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
f
r
s
x
d
x
.Hence,(23)
C
T
′
i
′
-
F
T
′
i
′
=
F
T
′
n
i
′
=
∫
y
n
y
n
+
1
g
y
d
y
∑
r
,
s
∈
R
S
∑
m
=
0
M
r
-
1
δ
P
^
r
s
n
T
r
a
n
x
^
r
s
n
m
,
a
i
′
T
′
∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
f
r
s
x
d
x
.Then,(24)
∫
y
n
y
n
+
1
g
y
d
y
=
C
T
′
i
′
-
F
T
′
i
′
∑
r
,
s
∈
R
S
∑
m
=
0
M
r
-
1
δ
P
^
r
s
n
T
r
a
n
x
^
r
s
n
m
,
a
i
′
T
′
∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
f
r
s
x
d
x
.Let(25)
Δ
n
=
min
⁡
C
T
i
-
F
T
i
∑
r
,
s
∈
R
S
∑
m
=
0
M
r
-
1
δ
P
^
r
s
n
T
r
a
n
x
^
r
s
n
m
,
a
i
T
∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
f
r
s
x
d
x
∣
a
i
T
∈
V
a
.Then, Δ
n
=
∫
y
n
y
n
+
1
g
y
d
y. Because g
y is a probability density function, 0
<
Δ
n
<
1. Equation (22) is rewritten as follows:(26)
F
r
s
n
m
=
Δ
n
∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
f
r
s
x
d
x
.Then,(27)
∑
m
=
0
M
r
-
1
F
r
s
n
m
=
Δ
n
∑
m
=
0
M
r
-
1
∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
f
r
s
x
d
x
=
Δ
n
∫
t
1
t
2
f
r
s
x
d
x
=
Δ
n
q
r
s
,
i
f
∃
v
i
T
=
r
,
T
∈
Ω
:
P
^
r
s
n
d
i
T
<
∞
Δ
n
∫
t
1
t
1
f
r
s
x
d
x
=
0
,
i
f
∄
v
i
T
=
r
,
T
∈
Ω
:
P
^
r
s
n
d
i
T
<
∞
.Equation (27) shows that if an effective travel plan exists for the O-D pair r
,
s
∈
R
S, the number of passengers booking tickets is Δ
n
q
r
s during period [
y
n
,
y
n
+
1. The number of passengers booking tickets for all O-D pairs is determined with the same proportion Δ
n by (25) during the period [
y
n
,
y
n
+
1. Calculating Δ
n using (25) does not require any specific probability density function g
y or partition time y
n
+
1. Hence, if the authors obtain Δ
n, then the number of passengers in period [
y
n
,
y
n
+
1 can be calculated using (26).Based on the above analysis, at thenth iteration, the process of passenger assignment is determined as follows. First, for the O-D pair r
,
s
∈
R
S and m
:
0
≤
m
<
M
r, according to the expectation of passengers, there are ∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
f
r
s
x
d
x passengers loaded on the path P
^
r
s
n
T
r
a
n
x
^
r
s
n
m and the expected number of passengers in every segment is obtained. Second, proportion Δ
n is calculated using (25), and the actual number of passengers loaded on segments is Δ
n times the expected one. Finally, if Δ
n
=
1
-
∑
u
=
0
n
-
1
Δ
u, that is, ∑
u
=
0
n
Δ
u
=
1, then the algorithm terminates (i.e., equal to y
n
+
1
=
0); otherwise, if Δ
n
<
1
-
∑
u
=
0
n
-
1
Δ
u, that is, ∑
u
=
0
n
Δ
u
<
1, then the algorithm continues to the next period. Hence, the authors obtain a simple method for the calculation of Algorithm 1.Under the assumption, the authors analyze the computational complexity of Algorithm1 as follows. The maximum iteration of the outer loop is N
=
O
A
b
o
a
r
d. In the body loop, at the nth iteration, there are four parts. These are, in order, as follows.First, the complexity of searching all paths with minimum cost for an end node isO
A and A
<
5
A
b
o
a
r
d; hence, the complexity of searching all paths with minimum cost for all end nodes is O
A
b
o
a
r
d
V.Second, the authors solve the optimal partitionX. This is a two-layer loop. The outer layer is for all O-D pairs, and the iterations of the inner layer are O
M
r. Hence, the complexity is O
V
∑
r
∈
V
M
r
=
O
A
b
o
a
r
d
V.Third, the authors calculate∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
f
r
s
x
d
x
,
0
≤
m
<
M
r
,
r
,
s
∈
R
S. The number of integrals is O
V
∑
r
∈
V
M
r
=
O
A
b
o
a
r
d
V. The complexity of calculating each integral is O
1 because f
r
s
x is an hourly step function. Hence, the complexity for calculating all integrals is O
A
b
o
a
r
d
V.Fourth, the authors load passengers on the paths with minimum cost. All the shortest paths to the end nodes
∞ generate a shortest path tree with a root node s
∞. After removing the nodes finishing the passenger loading process from the shortest path tree, the authors select a leaf node of the shortest path tree as the current node performing the passenger loading process. Following the shortest path, the authors load the passengers accumulated at the current node to the next neighboring node until the passengers at each node are loaded at the root node s
∞. Because every arc is processed at most once, the computational complexity for loading all passengers at one root node s
∞ is O
A
b
o
a
r
d
. Therefore, the computational complexity for loading passengers at all root nodes s
∞
∈
V is O
A
b
o
a
r
d
V.According to the third and fourth steps, the complexities of calculatingΔ
n, F
r
s
n
m
,
0
≤
m
<
M
r
,
r
,
s
∈
R
S, and F
T
n
i
,
1
<
i
≤
h
T
,
T
∈
Ω, are all O
A
b
o
a
r
d
V.In conclusion, the computational complexity of Algorithm1 under the assumption is O
A
b
o
a
r
d
2
V.


## 6. Application to a Large-Size Network

China’s high-speed rail network was used. There are 444 stations and 966 segments (Figure5). The train schedule on 1 July 2014 was used, and there were 2100 trains. The number of segments was A
b
o
a
r
d
=
15
,
263. In the space-time network V
,
A based on the train schedule, there were V
=
30
,
970 nodes and A
=
72
,
027 arcs. The total number of passengers was 1,876,255.Figure 5
High-speed rail network of China on 1 July 2014.The parameters are set as follows: The units of cost are Yuan (¥, Chinese monetary unit). Ticket fare rate is determined as ¥0.45 per kilometer for all trains based on the current ticket prices of high-speed trains in China. For example, from Beijingnan to Shanghai-Hongqiao, the travel distance is 1318 km and the ticket prices are ¥553 for second class, ¥933 for first class, and ¥1748 for business class. And most of the tickets are second class, but the classes of tickets are not considered in this paper; hence, ¥0.45 per kilometer is the average data. The fatigue cost is ¥0.5 per minute, which is determined by the average hourly wage (¥30/h) in 2014 in China. Let θ
=
¥
0.4 per minute, which is set to be lower than the fatigue cost, because, before boarding trains, passengers can do other things and the penalty for time deviation is thought to be lower than the fatigue cost in the travelling process. The minimum transfer time at a station is 40 min, and transfer cost at a station is ¥30, which is equivalent to the fatigue cost of an hour.


### 6.1. Indexes

To validate the results of passenger assignment, some indexes are used. The load factor refers to the number of on-board passenger kilometers divided by the number of seat kilometers of trains, denoted asL
F. The larger the load factor of a train, the higher the operational efficiency of the train:(28)
L
F
=
∑
i
=
2
h
T
F
T
i
T
i
-
1
,
i
∑
i
=
2
h
T
C
T
i
T
i
-
1
,
i
,where F
T
i denotes the actual passengers loaded on the train segment T
(
i
-
1
,
i
).To evaluate how well a train schedule coincides with time-dependent travel demand, the average time deviation between the expected departure time and the actual boarding time is used as another index. For passengers on all O-D pairs, the average time deviation is expressed as follows:(29)
A
T
D
=
∑
n
=
0
N
-
1
Δ
n
∑
r
,
s
∈
R
S
∑
m
=
0
M
r
-
1
∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
x
^
r
s
n
m
-
x
f
r
s
x
d
x
∑
r
,
s
∈
R
S
q
r
s
.Because the passenger assignment is restricted to one day, the indexes analyzed above are also restricted to one day.


### 6.2. Numerical Results and Analysis

All codes were written in C#, and computations were conducted on a 3.20 GHz PC with 8 GB of RAM under the assumption in Section5.4. The ticket-booking time in the passenger assignment was partitioned into 127 intervals, and the average running time was 3 min.For some ticket-booking time intervals, the optimal partitions of the expected departure time and paths with the minimum cost from city Beijing to city Shanghai are shown in Tables1 and 2. From the 1st ticket-booking time partition interval to the 16th one, the optimal partition showed no changes and there were 16 departure time partition intervals (Table 1). From the 112th ticket-booking time partition interval to the 116th one, the optimal partition showed no changes and there were 6 departure time partition intervals (Table 2).Table 1
Optimal partitions of the expected departure time from the first ticket-booking time partition interval to the 16th one.
Expected departure time interval
Travel time
Paths with minimum cost
Boarding station
Boarding time
Train number
Arrival time
Arrival station
[00:00, 07:16]
5 h 37 min
Beijingnan
7:05
G103
12:42
Shanghai-Hongqiao
[07:16, 08:18]
5 h 9 min
Beijingnan
8:00
G11
13:09
Shanghai-Hongqiao
[08:18, 09:35]
4 h 48 min
Beijingnan
9:00
G1
13:48
Shanghai-Hongqiao
[09:35, 10:30]
4 h 55 min
Beijingnan
10:00
G13
14:55
Shanghai-Hongqiao
[10:30, 12:00]
4 h 55 min
Beijingnan
11:00
G15
15:55
Shanghai-Hongqiao
[12:00, 12:26]
5 h 35 min
Beijingnan
12:13
G129
17:48
Shanghai-Hongqiao
[12:26, 12:32]
5 h 45 min
Beijingnan
12:27
G131
18:12
Shanghai-Hongqiao
[12:32, 12:54]
5 h 37 min
Beijingnan
12:48
G133
18:25
Shanghai-Hongqiao
[12:54, 14:36]
4 h 48 min
Beijingnan
14:00
G3
18:48
Shanghai-Hongqiao
[14:36, 15:41]
4 h 59 min
Beijingnan
15:00
G17
19:59
Shanghai-Hongqiao
[15:41, 16:41]
5 h 16 min
Beijingnan
16:00
G19
21:16
Shanghai-Hongqiao
[16:41, 17:09]
5 h 35 min
Beijingnan
17:00
G21
22:35
Shanghai-Hongqiao
[17:09, 17:16]
5 h 38 min
Beijingnan
17:10
G153
22:48
Shanghai-Hongqiao
[17:16, 17:34]
5 h 42 min
Beijingnan
17:22
G155
23:04
Shanghai-Hongqiao
[17:34, 17:46]
5 h 38 min
Beijingnan
17:45
G157
23:23
Shanghai-Hongqiao
[17:46, 23:59]
5 h 38 min
Beijingnan
17:50
G159
23:28
Shanghai-HongqiaoTable 2
Optimal partitions of the expected departure time from the 112th ticket-booking time partition interval to the 16th one.
Expected departure time interval
[00:00, 07:44]
[07:44, 08:13]
[08:13, 08:41]
[08:41, 09:52]
[09:52, 11:48]
[11:48, 23:59]
Travel time
8 h 8 min
8 h 25 min
7 h 56 min
7 h 57 min
10 h 32 min
6 h 1 min
Paths with minimum cost
Beijingnan
Beijingnan
Beijingnan
Beijingnan
Beijingnan
Beijingnan
7:05
8:06
8:35
9:05
11:24
16:29
G103
G107
G109
G113
D319
G151
11:24
12:31
12:50
13:05
18:53
22:30
Nanjingnan
Nanjingnan
Nanjingnan
Nanjingnan
Nanjingnan
Shanghai-
Nanjingnan
Nanjing
Nanjingnan
Nanjing
Nanjingnan
Hongqiao
12:15
14:38
13:38
15:07
19:42
D3012
G7065
D3044
G7067
D3074
13:15
16:31
14:06
17:02
21:56
Changzhou
Shanghai
Zhenjiang
Shanghai
Shanghai-
Changzhou
Zhenjiang
Hongqiao
14:00
15:01
G7059
G7065
15:13
16:31
Shanghai
ShanghaiThe paths in Table1 require no transfers in any of the departure time partition intervals, and the travel time is less than 6 h. However, in Table 2, there are fewer expected departure time partition intervals and some paths require two transfers or transfers to other stations in the same city. Also, travel time increases visibly. The path in the last expected departure time partition interval [11:48, 23:59] in Table 2 is direct. It involves taking train G151 with a travel time of 6 h 1 min, which is longer than the direct path shown in Table 1. Based on the analysis above, as ticket-booking time continues, the changes are as follows. There are fewer partition intervals for the expected departure time. A larger average time deviation, longer transfer times, and longer travel time occur.


### 6.3. Comparison

To validate the passenger assignment results, a comparison with the reality data was conducted. In this experiment, there are 177 trains on Jingguang Line and some stations on this line are numbered in Table3. The load factor of every train and the passengers on every train segment in this experiment (E) were compared with the ones in the reality (R) and let ε be the absolute error of the load factor. A part of the results are shown in Tables 4–6.Table 3
Station numbers on Jingguang Line.
Station
Beijingxi
Shijiazhuang
Zhengzhoudong
Wuhan
Xianningbei
Cibibei
Yueyangdong
Miluodong
Number
S1
S2
S3
S4
S5
S6
S7
S8
Station
Changshanan
Zhuzhouxi
Hengshanxi
Hengyangdong
Leiyangxi
Chenzhouxi
Shaoguan
Yingdexi
Number
S9
S10
S11
S12
S13
S14
S15
S16
Station
Qingyuan
Guangzhoubei
Guangzhounan
Shenzhenbei
Number
S17
S18
S19
S20Table 4
A distribution of 177 trains depending on absolute errorε on Jingguang Line.
ε
(0, 0.05)
(0.05, 0.2)
(0.2, 0.3)
(0.3, 0.5)
(0.5, 1)
Proportion of trains
34%
37%
12%
12%
5%Table 5
Passengers on segments of some trains on Jingguang Line.
Train
Capacity
Passengers on train segments
LF
(S4, S6)
(S4, S8)
(S8, S9)
(S9, S11)
(S11, S12)
(S12, S14)
(S14, S15)
(S15, S19)
G1103
556
139
210
238
448
450
493
454
500
0.68 (E)
153
162
178
333
314
370
394
478
0.57 (R)
(S4, S5)
(S5, S7)
(S7, S9)
(S9, S10)
(S10, S12)
(S12, S13)
(S13, S17)
(S17, S19)
G1105
556
74
111
326
381
427
474
545
545
0.72 (E)
156
186
374
374
448
428
484
509
0.71 (R)
(S4, S5)
(S5, S6)
(S6, S9)
(S9, S10)
(S10, S12)
(S12, S15)
(S15, S19)
G1135
556
538
547
541
474
491
548
541
0.96 (E)
525
529
506
546
550
550
551
0.97 (R)
(S4, S5)
(S5, S7)
(S7, S9)
(S9, S10)
(S10, S14)
(S14, S16)
(S16, S19)
G1125
610
285
261
581
551
607
557
601
0.85 (E)
493
517
530
522
539
520
551
0.87 (R)
(S4, S5)
(S5, S6)
(S6, S9)
(S9, S12)
(S12, S14)
(S14, S15)
(S15, S19)
G1133
1099
564
580
604
1047
1089
994
1008
0.80 (E)
474
507
493
1034
1038
923
1047
0.76 (R)
(S4, S5)
(S5, S6)
(S6, S7)
(S7, S9)
(S9, S12)
(S12, S14)
(S14, S19)
G1159
1099
69
57
41
128
267
227
195
0.16 (E)
223
204
181
243
306
257
199
0.21 (R)Table 6
Load factor of some trains on Jingguang Line.
Origin
Destination
Train
LF (E)
LF (R)
ε
S1
S19
G65
0.89
0.89
0
S1
S19
G69
0.87
0.85
0.02
S1
S20
G71
0.84
0.84
0
S1
S3
G89
0.83
0.87
0.04
S1
S9
G501
0.65
0.61
0.04
S1
S9
G505
0.84
0.82
0.02
S1
S4
G513
0.86
0.82
0.04
S1
S3
G563
0.26
0.24
0.02
S1
S4
D2031
0.76
0.77
0.01
S1
S2
G6705
0.21
0.17
0.04
S1
S2
G6707
0.16
0.18
0.02
S1
S2
G6713
0.56
0.61
0.05
S3
S20
G73
0.97
0.94
0.03
S3
S20
G75
0.82
0.86
0.04
S4
S20
G77
0.88
0.9
0.02
S4
S20
G1001
0.76
0.73
0.03
S4
S20
G1005
0.83
0.82
0.01
S4
S20
G1007
0.88
0.93
0.05
S4
S19
G1105
0.72
0.71
0.01
S4
S19
G1107
0.81
0.78
0.03
S4
S20
G1109
0.82
0.81
0.01
S4
S20
G1111
0.82
0.84
0.02
S4
S19
G1125
0.85
0.87
0.02
S4
S19
G1131
0.9
0.89
0.01
S4
S19
G1133
0.8
0.76
0.04
S4
S19
G1135
0.96
0.97
0.01
S4
S19
G1139
0.85
0.87
0.02
S4
S19
G1157
0.35
0.33
0.02
S9
S20
G6001
0.98
0.94
0.04
S9
S20
G6011
0.66
0.65
0.01
S9
S20
G6017
0.86
0.9
0.04
S9
S20
G6019
0.93
0.89
0.04There are 83% trains with the absolute error less than 0.3, 34% trains with the absolute error less than 0.05, and only 5% trains with the absolute error more than 0.5 (see Table4). For more details, some trains are chosen to show the passengers on segment and load factors (see Tables 5 and 6). By the comparison, the precision of the passenger assignment method in this paper is acceptable and the results can be used to evaluate the current train schedule.


### 6.4. Evaluations and Improvement Measures

The current train schedule was evaluated and improvement measures were proposed as follows.(1) Load Factor. As shown in Table 7, 52.96% of trains have load factors greater than 70%, indicating the high operating efficiency. On Jinghu Line, which is located in the developed east coast regions of China and has a dense population and high travel demand, 70.54% of the trains have load factors greater than 70%, making it one of the busiest lines in China. Jingha-Hada Line is the passenger corridor in northeastern China, and 61.9% of trains on this line have load factors above 50%. Jingguang Line is the main passage between south and north, and 53.25% of trains on this line have load factors above 50%. Although the transport capacity of these lines involves a surplus, to maintain a high service level, the lower load factors of some trains are also reasonable. But for some trains with very low load factors can be canceled and for some busy lines, more trains can be added.Table 7
The distributions of trains depending on the load factor on some lines.
LF interval
(90%, 100%)
(70%, 90%)
(50%, 70%)
(30%, 50%)
(0, 30%)
The whole rail network
20.52%
32.44%
19.52%
12.71%
14.81%
Jinghu Line
29.46%
41.08%
20.54%
4.46%
4.46%
Jingha-Hada Line
16.40%
24.87%
20.63%
17.99%
20.11%
Jingguang Line
6.49%
30.53%
16.23%
20.13%
26.62%(2) Average Time Deviation. As shown in Figure 6, the average time deviation of 90% of passengers was less than one hour and the average time deviation of 69.74% of passengers was less than half an hour. According to (29), the average time deviation for all passengers was 27.36 minutes. In this way, the train schedule matches time-dependent travel demand well. This evaluation index can be used to optimize the departure time distribution of trains to improve the level of service of the train timetable. For passengers of some O-D pairs with large time deviation, the departure times of trains should be adjusted or more trains should be added.Figure 6
Proportion of passengers experiencing average time deviations.(3) Improvement Measures. 31 trains from Beijingnan to Shanghai-Hongqiao were selected (see Table 8). Through the absolute error ε of the load factor of every train, it is shown that the assignment results on those trains are close to the reality. Based on the results in Table 8, the authors propose some improvement measures as follows:(i)
Capacity: the load factors of trains departing before 9:00 are about 0.5 except for train G11, of which the load factors are not high, and all their capacities are above 1000. Hence, the capacities of these trains can be reduced to about 600. Similarly, for some trains with very high load factors but low capacities, the capacities can be increased, for example, train G119.
(ii)
Stop pattern: for trains G11, G1, G13, G15, G3, G17, and G19, there are two common characters. First, the average distances of stops are relatively long; second, the load factors are very high. This is mainly because longer average distances of stops mean fewer stops for the same O-D pair, so the total travel time is shorter. Then, passengers with long travel distance would like to choose such trains to save time (the ticket fares of these trains are the same). Hence, to improve the service level, if the passengers on some trains are mostly with long travel distances, the middle stops of such trains can be reduced properly. This can save the time of passengers and attract more passengers.
(iii)
Departure time: the load factors of trains departing at[9:00, 11:00] and [14:00, 16:00] are very high, which are the peak hours in one day, and then more trains departing at the peak hours can be added if there are enough passengers. The load factors of trains departing before 8:00 are some low, and then the departure times of such trains can be pushed back properly.Table 8
The load factors, average distances of stops and the departure times of some train from Beijingnan to Shanghai-Hongqiao.
Train
Capacity
Departure time
Average distance of stops (km)
LF (E)
LF (R)
ε
G101
1043
7:00
146
0.51
0.50
0.01
G103
1066
7:05
146
0.56
0.67
0.11
G105
1015
7:36
146
0.55
0.67
0.12
G11
1066
8:00
264
0.96
0.85
0.11
G107
1066
8:06
188
0.64
0.57
0.07
G109
1043
8:35
146
0.64
0.61
0.03
G111
1015
8:40
165
0.52
0.38
0.14
G1
1066
9:00
659
0.99
0.87
0.12
G113
1015
9:05
188
0.94
0.84
0.1
G115
1043
9:16
165
0.63
0.64
0.01
G13
1066
10:00
439
0.96
0.88
0.08
G119
480
10:05
132
0.91
1.00
0.09
G121
556
10:28
132
0.87
0.92
0.05
G15
1066
11:00
439
0.98
0.94
0.04
G123
480
11:05
146
0.85
0.91
0.06
G127
1066
11:35
146
0.71
0.84
0.13
G131
1015
12:27
132
0.8
0.91
0.11
G133
1015
12:48
146
0.88
0.93
0.05
G135
1043
13:06
132
0.81
0.88
0.07
G137
1066
13:40
146
0.9
0.88
0.02
G3
1015
14:00
659
0.99
0.97
0.02
G139
1015
14:16
165
0.89
0.87
0.02
G141
1015
14:41
132
0.84
0.80
0.04
G17
1015
15:00
439
0.98
0.96
0.02
G143
1015
15:12
120
0.8
0.78
0.02
G145
1043
15:30
146
0.85
0.83
0.02
G19
1015
16:00
264
0.94
0.85
0.09
G147
1015
16:10
146
0.88
0.74
0.14
G149
1015
16:15
132
0.85
0.74
0.11
G21
1043
17:00
165
0.91
0.73
0.18
G155
556
17:22
132
0.94
0.85
0.09


## 6.1. Indexes

To validate the results of passenger assignment, some indexes are used. The load factor refers to the number of on-board passenger kilometers divided by the number of seat kilometers of trains, denoted asL
F. The larger the load factor of a train, the higher the operational efficiency of the train:(28)
L
F
=
∑
i
=
2
h
T
F
T
i
T
i
-
1
,
i
∑
i
=
2
h
T
C
T
i
T
i
-
1
,
i
,where F
T
i denotes the actual passengers loaded on the train segment T
(
i
-
1
,
i
).To evaluate how well a train schedule coincides with time-dependent travel demand, the average time deviation between the expected departure time and the actual boarding time is used as another index. For passengers on all O-D pairs, the average time deviation is expressed as follows:(29)
A
T
D
=
∑
n
=
0
N
-
1
Δ
n
∑
r
,
s
∈
R
S
∑
m
=
0
M
r
-
1
∫
x
r
s
n
m
x
r
,
s
,
n
,
m
+
1
x
^
r
s
n
m
-
x
f
r
s
x
d
x
∑
r
,
s
∈
R
S
q
r
s
.Because the passenger assignment is restricted to one day, the indexes analyzed above are also restricted to one day.


## 6.2. Numerical Results and Analysis

All codes were written in C#, and computations were conducted on a 3.20 GHz PC with 8 GB of RAM under the assumption in Section5.4. The ticket-booking time in the passenger assignment was partitioned into 127 intervals, and the average running time was 3 min.For some ticket-booking time intervals, the optimal partitions of the expected departure time and paths with the minimum cost from city Beijing to city Shanghai are shown in Tables1 and 2. From the 1st ticket-booking time partition interval to the 16th one, the optimal partition showed no changes and there were 16 departure time partition intervals (Table 1). From the 112th ticket-booking time partition interval to the 116th one, the optimal partition showed no changes and there were 6 departure time partition intervals (Table 2).Table 1
Optimal partitions of the expected departure time from the first ticket-booking time partition interval to the 16th one.
Expected departure time interval
Travel time
Paths with minimum cost
Boarding station
Boarding time
Train number
Arrival time
Arrival station
[00:00, 07:16]
5 h 37 min
Beijingnan
7:05
G103
12:42
Shanghai-Hongqiao
[07:16, 08:18]
5 h 9 min
Beijingnan
8:00
G11
13:09
Shanghai-Hongqiao
[08:18, 09:35]
4 h 48 min
Beijingnan
9:00
G1
13:48
Shanghai-Hongqiao
[09:35, 10:30]
4 h 55 min
Beijingnan
10:00
G13
14:55
Shanghai-Hongqiao
[10:30, 12:00]
4 h 55 min
Beijingnan
11:00
G15
15:55
Shanghai-Hongqiao
[12:00, 12:26]
5 h 35 min
Beijingnan
12:13
G129
17:48
Shanghai-Hongqiao
[12:26, 12:32]
5 h 45 min
Beijingnan
12:27
G131
18:12
Shanghai-Hongqiao
[12:32, 12:54]
5 h 37 min
Beijingnan
12:48
G133
18:25
Shanghai-Hongqiao
[12:54, 14:36]
4 h 48 min
Beijingnan
14:00
G3
18:48
Shanghai-Hongqiao
[14:36, 15:41]
4 h 59 min
Beijingnan
15:00
G17
19:59
Shanghai-Hongqiao
[15:41, 16:41]
5 h 16 min
Beijingnan
16:00
G19
21:16
Shanghai-Hongqiao
[16:41, 17:09]
5 h 35 min
Beijingnan
17:00
G21
22:35
Shanghai-Hongqiao
[17:09, 17:16]
5 h 38 min
Beijingnan
17:10
G153
22:48
Shanghai-Hongqiao
[17:16, 17:34]
5 h 42 min
Beijingnan
17:22
G155
23:04
Shanghai-Hongqiao
[17:34, 17:46]
5 h 38 min
Beijingnan
17:45
G157
23:23
Shanghai-Hongqiao
[17:46, 23:59]
5 h 38 min
Beijingnan
17:50
G159
23:28
Shanghai-HongqiaoTable 2
Optimal partitions of the expected departure time from the 112th ticket-booking time partition interval to the 16th one.
Expected departure time interval
[00:00, 07:44]
[07:44, 08:13]
[08:13, 08:41]
[08:41, 09:52]
[09:52, 11:48]
[11:48, 23:59]
Travel time
8 h 8 min
8 h 25 min
7 h 56 min
7 h 57 min
10 h 32 min
6 h 1 min
Paths with minimum cost
Beijingnan
Beijingnan
Beijingnan
Beijingnan
Beijingnan
Beijingnan
7:05
8:06
8:35
9:05
11:24
16:29
G103
G107
G109
G113
D319
G151
11:24
12:31
12:50
13:05
18:53
22:30
Nanjingnan
Nanjingnan
Nanjingnan
Nanjingnan
Nanjingnan
Shanghai-
Nanjingnan
Nanjing
Nanjingnan
Nanjing
Nanjingnan
Hongqiao
12:15
14:38
13:38
15:07
19:42
D3012
G7065
D3044
G7067
D3074
13:15
16:31
14:06
17:02
21:56
Changzhou
Shanghai
Zhenjiang
Shanghai
Shanghai-
Changzhou
Zhenjiang
Hongqiao
14:00
15:01
G7059
G7065
15:13
16:31
Shanghai
ShanghaiThe paths in Table1 require no transfers in any of the departure time partition intervals, and the travel time is less than 6 h. However, in Table 2, there are fewer expected departure time partition intervals and some paths require two transfers or transfers to other stations in the same city. Also, travel time increases visibly. The path in the last expected departure time partition interval [11:48, 23:59] in Table 2 is direct. It involves taking train G151 with a travel time of 6 h 1 min, which is longer than the direct path shown in Table 1. Based on the analysis above, as ticket-booking time continues, the changes are as follows. There are fewer partition intervals for the expected departure time. A larger average time deviation, longer transfer times, and longer travel time occur.


## 6.3. Comparison

To validate the passenger assignment results, a comparison with the reality data was conducted. In this experiment, there are 177 trains on Jingguang Line and some stations on this line are numbered in Table3. The load factor of every train and the passengers on every train segment in this experiment (E) were compared with the ones in the reality (R) and let ε be the absolute error of the load factor. A part of the results are shown in Tables 4–6.Table 3
Station numbers on Jingguang Line.
Station
Beijingxi
Shijiazhuang
Zhengzhoudong
Wuhan
Xianningbei
Cibibei
Yueyangdong
Miluodong
Number
S1
S2
S3
S4
S5
S6
S7
S8
Station
Changshanan
Zhuzhouxi
Hengshanxi
Hengyangdong
Leiyangxi
Chenzhouxi
Shaoguan
Yingdexi
Number
S9
S10
S11
S12
S13
S14
S15
S16
Station
Qingyuan
Guangzhoubei
Guangzhounan
Shenzhenbei
Number
S17
S18
S19
S20Table 4
A distribution of 177 trains depending on absolute errorε on Jingguang Line.
ε
(0, 0.05)
(0.05, 0.2)
(0.2, 0.3)
(0.3, 0.5)
(0.5, 1)
Proportion of trains
34%
37%
12%
12%
5%Table 5
Passengers on segments of some trains on Jingguang Line.
Train
Capacity
Passengers on train segments
LF
(S4, S6)
(S4, S8)
(S8, S9)
(S9, S11)
(S11, S12)
(S12, S14)
(S14, S15)
(S15, S19)
G1103
556
139
210
238
448
450
493
454
500
0.68 (E)
153
162
178
333
314
370
394
478
0.57 (R)
(S4, S5)
(S5, S7)
(S7, S9)
(S9, S10)
(S10, S12)
(S12, S13)
(S13, S17)
(S17, S19)
G1105
556
74
111
326
381
427
474
545
545
0.72 (E)
156
186
374
374
448
428
484
509
0.71 (R)
(S4, S5)
(S5, S6)
(S6, S9)
(S9, S10)
(S10, S12)
(S12, S15)
(S15, S19)
G1135
556
538
547
541
474
491
548
541
0.96 (E)
525
529
506
546
550
550
551
0.97 (R)
(S4, S5)
(S5, S7)
(S7, S9)
(S9, S10)
(S10, S14)
(S14, S16)
(S16, S19)
G1125
610
285
261
581
551
607
557
601
0.85 (E)
493
517
530
522
539
520
551
0.87 (R)
(S4, S5)
(S5, S6)
(S6, S9)
(S9, S12)
(S12, S14)
(S14, S15)
(S15, S19)
G1133
1099
564
580
604
1047
1089
994
1008
0.80 (E)
474
507
493
1034
1038
923
1047
0.76 (R)
(S4, S5)
(S5, S6)
(S6, S7)
(S7, S9)
(S9, S12)
(S12, S14)
(S14, S19)
G1159
1099
69
57
41
128
267
227
195
0.16 (E)
223
204
181
243
306
257
199
0.21 (R)Table 6
Load factor of some trains on Jingguang Line.
Origin
Destination
Train
LF (E)
LF (R)
ε
S1
S19
G65
0.89
0.89
0
S1
S19
G69
0.87
0.85
0.02
S1
S20
G71
0.84
0.84
0
S1
S3
G89
0.83
0.87
0.04
S1
S9
G501
0.65
0.61
0.04
S1
S9
G505
0.84
0.82
0.02
S1
S4
G513
0.86
0.82
0.04
S1
S3
G563
0.26
0.24
0.02
S1
S4
D2031
0.76
0.77
0.01
S1
S2
G6705
0.21
0.17
0.04
S1
S2
G6707
0.16
0.18
0.02
S1
S2
G6713
0.56
0.61
0.05
S3
S20
G73
0.97
0.94
0.03
S3
S20
G75
0.82
0.86
0.04
S4
S20
G77
0.88
0.9
0.02
S4
S20
G1001
0.76
0.73
0.03
S4
S20
G1005
0.83
0.82
0.01
S4
S20
G1007
0.88
0.93
0.05
S4
S19
G1105
0.72
0.71
0.01
S4
S19
G1107
0.81
0.78
0.03
S4
S20
G1109
0.82
0.81
0.01
S4
S20
G1111
0.82
0.84
0.02
S4
S19
G1125
0.85
0.87
0.02
S4
S19
G1131
0.9
0.89
0.01
S4
S19
G1133
0.8
0.76
0.04
S4
S19
G1135
0.96
0.97
0.01
S4
S19
G1139
0.85
0.87
0.02
S4
S19
G1157
0.35
0.33
0.02
S9
S20
G6001
0.98
0.94
0.04
S9
S20
G6011
0.66
0.65
0.01
S9
S20
G6017
0.86
0.9
0.04
S9
S20
G6019
0.93
0.89
0.04There are 83% trains with the absolute error less than 0.3, 34% trains with the absolute error less than 0.05, and only 5% trains with the absolute error more than 0.5 (see Table4). For more details, some trains are chosen to show the passengers on segment and load factors (see Tables 5 and 6). By the comparison, the precision of the passenger assignment method in this paper is acceptable and the results can be used to evaluate the current train schedule.


## 6.4. Evaluations and Improvement Measures

The current train schedule was evaluated and improvement measures were proposed as follows.(1) Load Factor. As shown in Table 7, 52.96% of trains have load factors greater than 70%, indicating the high operating efficiency. On Jinghu Line, which is located in the developed east coast regions of China and has a dense population and high travel demand, 70.54% of the trains have load factors greater than 70%, making it one of the busiest lines in China. Jingha-Hada Line is the passenger corridor in northeastern China, and 61.9% of trains on this line have load factors above 50%. Jingguang Line is the main passage between south and north, and 53.25% of trains on this line have load factors above 50%. Although the transport capacity of these lines involves a surplus, to maintain a high service level, the lower load factors of some trains are also reasonable. But for some trains with very low load factors can be canceled and for some busy lines, more trains can be added.Table 7
The distributions of trains depending on the load factor on some lines.
LF interval
(90%, 100%)
(70%, 90%)
(50%, 70%)
(30%, 50%)
(0, 30%)
The whole rail network
20.52%
32.44%
19.52%
12.71%
14.81%
Jinghu Line
29.46%
41.08%
20.54%
4.46%
4.46%
Jingha-Hada Line
16.40%
24.87%
20.63%
17.99%
20.11%
Jingguang Line
6.49%
30.53%
16.23%
20.13%
26.62%(2) Average Time Deviation. As shown in Figure 6, the average time deviation of 90% of passengers was less than one hour and the average time deviation of 69.74% of passengers was less than half an hour. According to (29), the average time deviation for all passengers was 27.36 minutes. In this way, the train schedule matches time-dependent travel demand well. This evaluation index can be used to optimize the departure time distribution of trains to improve the level of service of the train timetable. For passengers of some O-D pairs with large time deviation, the departure times of trains should be adjusted or more trains should be added.Figure 6
Proportion of passengers experiencing average time deviations.(3) Improvement Measures. 31 trains from Beijingnan to Shanghai-Hongqiao were selected (see Table 8). Through the absolute error ε of the load factor of every train, it is shown that the assignment results on those trains are close to the reality. Based on the results in Table 8, the authors propose some improvement measures as follows:(i)
Capacity: the load factors of trains departing before 9:00 are about 0.5 except for train G11, of which the load factors are not high, and all their capacities are above 1000. Hence, the capacities of these trains can be reduced to about 600. Similarly, for some trains with very high load factors but low capacities, the capacities can be increased, for example, train G119.
(ii)
Stop pattern: for trains G11, G1, G13, G15, G3, G17, and G19, there are two common characters. First, the average distances of stops are relatively long; second, the load factors are very high. This is mainly because longer average distances of stops mean fewer stops for the same O-D pair, so the total travel time is shorter. Then, passengers with long travel distance would like to choose such trains to save time (the ticket fares of these trains are the same). Hence, to improve the service level, if the passengers on some trains are mostly with long travel distances, the middle stops of such trains can be reduced properly. This can save the time of passengers and attract more passengers.
(iii)
Departure time: the load factors of trains departing at[9:00, 11:00] and [14:00, 16:00] are very high, which are the peak hours in one day, and then more trains departing at the peak hours can be added if there are enough passengers. The load factors of trains departing before 8:00 are some low, and then the departure times of such trains can be pushed back properly.Table 8
The load factors, average distances of stops and the departure times of some train from Beijingnan to Shanghai-Hongqiao.
Train
Capacity
Departure time
Average distance of stops (km)
LF (E)
LF (R)
ε
G101
1043
7:00
146
0.51
0.50
0.01
G103
1066
7:05
146
0.56
0.67
0.11
G105
1015
7:36
146
0.55
0.67
0.12
G11
1066
8:00
264
0.96
0.85
0.11
G107
1066
8:06
188
0.64
0.57
0.07
G109
1043
8:35
146
0.64
0.61
0.03
G111
1015
8:40
165
0.52
0.38
0.14
G1
1066
9:00
659
0.99
0.87
0.12
G113
1015
9:05
188
0.94
0.84
0.1
G115
1043
9:16
165
0.63
0.64
0.01
G13
1066
10:00
439
0.96
0.88
0.08
G119
480
10:05
132
0.91
1.00
0.09
G121
556
10:28
132
0.87
0.92
0.05
G15
1066
11:00
439
0.98
0.94
0.04
G123
480
11:05
146
0.85
0.91
0.06
G127
1066
11:35
146
0.71
0.84
0.13
G131
1015
12:27
132
0.8
0.91
0.11
G133
1015
12:48
146
0.88
0.93
0.05
G135
1043
13:06
132
0.81
0.88
0.07
G137
1066
13:40
146
0.9
0.88
0.02
G3
1015
14:00
659
0.99
0.97
0.02
G139
1015
14:16
165
0.89
0.87
0.02
G141
1015
14:41
132
0.84
0.80
0.04
G17
1015
15:00
439
0.98
0.96
0.02
G143
1015
15:12
120
0.8
0.78
0.02
G145
1043
15:30
146
0.85
0.83
0.02
G19
1015
16:00
264
0.94
0.85
0.09
G147
1015
16:10
146
0.88
0.74
0.14
G149
1015
16:15
132
0.85
0.74
0.11
G21
1043
17:00
165
0.91
0.73
0.18
G155
556
17:22
132
0.94
0.85
0.09


## 7. Conclusion

Schedule-based passenger assignment for high-speed rail networks has the following features. Passengers book tickets and reserve seats during the presale period, train capacity is taken up in the booking process, and the crowding effect does not occur. These are the essential differences from passenger assignment in urban transit networks. For a high-speed rail network, passenger assignment is completed in the ticket-booking process and the process can be modeled as a continuous and deterministic predecision process. Since the crowding effect is not considered, the minimum cost of travel plans remains constant during some stages of the booking process. Based on this feature, the authors design a method to optimally partition the ticket-booking period. For any optimal partition interval, the modified rooftops method is used to generate an optimal partition of the expected departure time. Finally, a solution algorithm is designed, and a large-scale application to the Chinese high-speed rail network is shown to validate the efficiency and precision of the proposed method and the solution algorithm.The limits of the proposed method are as follows:(i)
The assumption in Section5.4 does not agree with the reality. But considering that the ticket-booking time is quite an uncertainty and complicated variable, high cost is needed to determine the distributions of passengers depending on ticket-booking time. Hence, the method based on this assumption can be seen as a simplified computational method and can be applied in reality with low cost. What is more, the efficiency and precision of the method get validated by the comparison with the reality.
(ii)
The ticket class is not considered in this paper. The choices for different seat classes involve the different levels of income for passengers, which are planned to be further studied in another paper.The method developed in this paper can be applied with low cost for high-speed rail networks in reality and can also be expanded to other resource allocation problems with ticket-booking.



---

*Source: 1650839-2016-06-14.xml*