# Optimization of Multiperiod Mixed Train Schedule on High-Speed Railway

Authors: Wenliang Zhou; Junli Tian; Jin Qin; Lianbo Deng; TangJian Wei
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

For providing passengers with periodic operation trains and making trains’ time distribution better fit that of passengers, the multiperiod mixed train schedule is first proposed in this paper. It makes each type of train having same origin, destination, route, and stop stations operate based on a periodic basis and allows different types of train to have various operation periods. Then a model of optimizing multiperiod mixed train schedule is built to minimize passengers generalized travel costs with the constraints of trains of same type operating periodically, safe interval requirements of trains’ departure, and arrival times, and so forth. And its heuristic algorithm is designed to optimize the multiperiod mixed train schedule beginning with generating an initial solution by scheduling all types of train type by type and then repeatedly improving their periodic schedules until the objective value cannot be reduced or the iteration number reaches its maximum. Finally, example results illustrate that the proposed model and algorithm can effectively gain a better multiperiod mixed train schedule. However, its passengers deferred times and advanced times are a little higher than these of an aperiodic train schedule.


---

## Body

## 1. Introduction

Train schedule which determines all trains’ arrival times, departures times, and dwell times at stations is the cornerstone of trains organization and operation for rail enterprise. Generally, it is formulated based on a predesigned train plan which has stipulated all trains origin and destination stations, routes, stop stations, and operation frequencies. However, there are still very few studies such as Michaelis and Schöbel [1], Kaspi and Raviv [2], and Zhou et al. [3] trying to optimize train plan and train schedule integrally in recent years. Obviously, a high-quality train schedule not only contributes to providing passengers with less in-vehicle times and waiting times at origins, but also can bring railway enterprise great convenience in trains organization and operation, which can effectively improve the competitiveness of rail transit in passenger public transportation market. Moreover, train schedule is also the basis of designing the usage plan of railway Electric Multiple Units or locomotives and crew schedule. Surely a better train schedule can effectively reduce the usage count of Electric Multiple Units and crews, which means that more investment and operation costs will be saved for rail enterprise.According to train organization mode, train schedule can be divided into two types, namely, periodic train schedule and aperiodic train schedule. Periodic train schedule makes trains operate on a periodic basis, for example, 1 hour, and has the obvious advantage of regularity of train operation, which is convenient for passengers to be familiar with. Thus, it has been widely adopted in not only high-speed railway but also urban railway system in the world, especially in Japan and European countries. Regarding the optimizing approach of periodic train schedule, trains of peak hour in one day are generally scheduled firstly and then they are copied to other nonpeak hours, and some trains of nonpeak hours are deleted for fitting the decrease of passenger demand. Periodic train scheduling for railway is usually modeled by the Periodic Event Scheduling Problem (PESP) which was first proposed by Willem and Peeters [4]. The main advantage of this model is easily to describe many requirements that practitioners impose on periodic train schedule. Moreover, Liebchen [5] further integrated symmetry into it, and Caimi et al. [6] extended it to propose the Flexible Periodic Event Scheduling Problem (FPESP), which can generate flexible time slots for the departure and arrival times instead of exact times. Besides the PESP model, Serafini and Ukovich [7] proposed a mathematical model for scheduling periodic events with particular time constraints and designed an algorithm of implicit enumeration type for it. Odijk [8] used a mathematical model consisting of periodic time window constraints to construct periodic train schedule. Lindner and Zimmermann [9] developed a mixed integer linear programming model of periodic train schedule with the aim of minimizing operational cost and then decomposed it for being solved by an algorithm integrating cutting plane and branch-and-bound method. For more studies about periodic train schedule, refer to Nachtigall [10], Liebchen [11], and Liebchen and Möhring [12].Compared with periodic train schedule, aperiodic train schedule has not the periodic regularity of train operation and is optimized integrally based on the time-distance distribution of passenger demand in one day. As aperiodic train scheduling need not consider train periodic operation restriction, and it has more flexibility to arrange trains arrival and departure times. Thus, it can make trains’ time distribution fit that of passenger demand better, which contributes not only to reducing passengers deferred times or advanced times at origin stations, but also improving rail enterprise operation efficiency. Since now, many studies have strived to optimize the aperiodic train schedule with different objectives such as minimizing train travel time and maximizing passenger travel cost using many approaches including mathematics programming method, simulation method, and artificial intelligence method. For example, Szpigel [13] first developed a linear programming model to optimize the aperiodic train schedule for minimizing trains total travel time. Higgins et al. [14] developed a branch-and-bound solution framework to optimize aperiodic train schedule. And Zhou and Zhong [15] further applied a lagrangian-relaxation-based lower bound rule, an exact lower bound rule, and a tight upper bound rule into it to improve the optimizing quality and efficiency. Carey and Lockwood [16, 17] developed an iterative decomposition approach which contains several node branches, variable fixing, and bounding strategies to solve the train scheduling and pathing problems. Medanic and Dorfman [18, 19] proposed a local feedback based train travel advance strategy (TAS) by using a discrete-event model to simulate train advance along railway line. Li et al. [20] further proposed an algorithm based on the global information of the train to obtain an effective train travel advance strategy. Carey and Crawford [21] developed some heuristic algorithms to find and resolve the conflicts in draft train schedules. In addition, in some literatures, train scheduling problem is modeled as a blocking parallel-machine job shop scheduling problem solved by the alternative graph model. For example, Liu and Kozan [22] regarded the train scheduling problem as a blocking parallel-machine job shop scheduling problem and solved it by a feasibility satisfaction procedure algorithm. And Burdett and Kozan [23] proposed a novel hybrid job shop approach to scheduling trains; Törnquist and Persson [24] proposed an approach to reschedule railway traffic in an n-tracked network when a disturbance has occurred with the aim of minimizing the consequences for multiple stakeholders. For more studies about periodic train schedule, refer to Li and Lo [25], Sahana et al. [26], and Dollevoet et al. [27].It is hard and not necessary to decide which is better between periodic train schedule and aperiodic train schedule as they both have their own advantages and disadvantages. For periodic train schedule, it has the rhythmicity of train periodic operation and brings great conveniences to passengers. For aperiodic train schedule, it has the advantage of better making trains operation time distribution fit that of passenger demand. In this paper, we attempt to formulate a train schedule having the advantages of both periodic and aperiodic train schedules; that is, trains not only operate periodically, but also can better fit demands’ time distribution. And so for that, we first propose a new type of train schedule called multiperiod mixed train schedule in which trains having the same origin, destination, route, and stop stations are regarded as one same type, and the same type of train operates based on a periodic basis. Moreover, trains of different types can have various operation periods. For example, while the operation period of trains of the first type is 1 hour, these of the second type can operate with the period of 1 hour or other periods such as 1.5 hour and 2 hour. For description convenience, trains of one type are also called as the same period trains. Compared with the general periodic train schedule in which all trains operate with only one period, the multiperiod mixed train schedule has the following differences. Firstly, it is optimized integrally like aperiodic train schedule, so we need not delete any trains to fit the decrease of passenger, which may disrupt trains periodic operation regularity. Secondly, trains of different types not only can have various operation periods, but also operate with different numbers, operation time ranges. Thirdly, we have to coordinate the start times, periods, and end times of operation of all types of train to make trains time distribution better fit that of passenger demand.The main contributions of this paper are as follows:(1)
First propose a new type of train schedule; that is, multiperiod mixed train schedule, which not only can provide passengers with periodic operation trains, but also can better fit demand time distribution.
(2)
An optimization model of multiperiod mixed train schedule is built to minimize passengers generalized travel costs under the constraints of trains of same type operating periodically, safe interval among trains departure times and arrival times, and so forth.
(3)
A solving algorithm is designed to solve the proposed optimization model. It is first to schedule each type of train type by type and then to repeatedly adjust their schedules until it reaches the stop conditions.The remainder of this paper is organized as follows. In next section, we present an optimization model of multiperiod mixed train schedule. In Section3, passenger travel costs are analyzed and their calculation method is proposed. In Section 4, an algorithm is designed for scheduling trains of one type based on a given partial train schedule, and then an optimization algorithm of multiperiod mixed train schedule is given in Section 5. An example of Wu-guang high-speed railway is used to illustrate the effectiveness of the proposed model and algorithm in Section 6. Finally, the conclusion and further study are given in Section 7.


## 2. Optimization Model of Multiperiod Mixed Train Schedule

A high-speed railway lineL
=
S
,
E is represented by an ordered sequence of stations S
=
1,2
,
…
,
L
S and 1,2
,
…
,
L
S is arranged by the down direction. The set of double-tracks sections is denoted by E
=
e
(
k
,
k
′
)
∣
k
,
k
′
∈
S in which e
k
,
k
′ and e
k
′
,
k, respectively represent the up and down sections between stations k and k
′. The mileage of section e
k
,
k
′ is w
e and is also denoted by w
(
k
,
k
′
).A given train plan of lineL is denoted by Ω which has specified trains origin and destination stations, travel routes, and stop stations. In this paper, all trains are assumed to be configured with a same type of Electric Multiple Unit; thus they have the same technical speed in each rail section and vehicle number. In reality, the Electric Multiple Units used on a same high-speed railway generally are the same type because this contributes to their management and maintenance, but the number of Electric Multiple Units among trains is usually set as 8 or 16, which will lead to a difference of passenger capacities among trains. Thus, we have to further consider the different passenger capacity restriction of trains when arranging passengers to trains if without this assumption. According to train’s origin station, destination station, travel route, and stop stations, trains of Ω are classified into n types. Trains of same type have same origin and destination stations, travel route, and stop stations and operate with a same period.For trains of typei
=
1,2
,
…
,
n, their origin and destination stations are, respectively, denoted by s
i
d and s
i
a, their route is expressed with a sequence of stations denoted by K
i
=
{
k
i
1
,
k
i
2
,
…
}, and their stop stations set is expressed by K
^
i
∈
K
i whose element number is denoted by m
i. All trains of this type will operate according to a start time and a fixed period. In other words, their first train departs at a start time, and, after a fixed period, their second train departs again; then their third train departs until all trains have departed. This periodic operation requirement of trains of one type can be clearly illustrated with Figure 1, in which one type of train originally departs at station 1, stops at station 2, and gets through station 3, finally arriving at station 4. As you can see, its first train departs at 8:00, and after a period of 2 hours, that is, at 10:00, its second train departs, and then its third, fourth, and fifth trains depart at 12:00, 14:00, and 16:00, respectively.Figure 1
Periodic operation of trains of a type.For description convenience, thejth train of the ith type is denoted by (
i
,
j
), and its arrival time and departure time at stationk are expressed by y
i
j
k and x
i
j
k, respectively. As trains of the same type operate periodically, the difference of arrival and departure times between train i
,
j and train i
,
1 is j
-
1 times of T
i which is the operation period of trains of the ith type. That is(1)
y
i
j
k
=
y
i
1
k
+
j
-
1
T
i
j
=
1,2
,
…
,
m
i
,
(2)
x
i
j
k
=
x
i
1
k
+
j
-
1
T
i
j
=
1,2
,
…
,
m
i
.Thus, the schedule of theith type of train denoted by X
i
,
Y
i can be obtained once its first train’s arrival and departure times y
i
1
k, x
i
1
k and its operation period T
i are determined. Hence, the arrival and departure times y
i
1
k, x
i
1
k and period T
i are selected as the decision variables in this paper. Theoretically, period T
i can be any integer numbers that can ensure that this type of train departs in one day, but for bringing memory convenience to passengers, it is suggested to be the integer times of 10 min, 15 min, or 30 min.All types of periodic trains’ schedules constitute a multiperiod mixed train schedule denoted byX
,
Y in which each type of periodic train has an operation period. In fact, if they have a same period, it becomes a general single-period train schedule. Figure 2 shows a simple example of multiperiod mixed train schedule. As seen from it, there are total 3 types of periodic trains which all have the same origin, destination, and route but have different stop stations. The first type of periodic train with stop-by-stop pattern shown with red solid line has the period of 60 min and its earliest departure time is 8:00; the second type of periodic train only stopping at station 2 shown with blue dotted line has the period of 70 min and departs at 8:21 at the earliest; and the third type of periodic train, that is, through trains, shown with green dotted line operates with period of 100 min and departs earliest at 8:42.Figure 2
A simple example of multiperiod mixed train schedule.The key of multiperiod mixed train schedule optimization is to coordinate all types of periodic trains’ schedules and operation periods aiming to maximize passenger service level on the basis of satisfying all types of constraints such as operation time and safety interval requirements.Besides periodic operation constraints among trains of the same type, that is, satisfying formula (1) and (2), another five type constraints below should be satisfied when optimizing a multiperiod mixed train schedule.(1) Operation Time Constraints. All trains must operate during the operation time t
s
,
t
e of high-speed railway, and railway maintenance is usually performed during the nonoperation time. Hence, train’s arrival and departure times y
i
j
k and x
i
j
k should satisfy(3)
t
s
≤
y
i
j
k
≤
t
e
i
=
1,2
,
…
,
n
;
j
=
1,2
,
…
,
m
i
;
∀
k
∈
K
i
,
t
s
≤
x
i
j
k
≤
t
e
i
=
1,2
,
…
,
n
;
j
=
1,2
,
…
,
m
i
;
∀
k
∈
K
i
.(2) Constraints of Train Minimum Travel Times in Sections. Train’s minimum travel time in a section is composed partly or completely of additional time for starting, pure travel time, and additional time for stopping, which depends on whether train stops at section’s endpoints. Obviously, train travel time in section should be greater than this value.(4)
y
i
1
k
′
-
x
i
1
k
≥
δ
i
1
k
τ
′
k
,
k
′
+
τ
k
,
k
′
+
δ
i
1
k
′
τ
′′
k
,
k
′
∀
i
;
e
k
,
k
′
∣
k
,
k
′
∈
K
i
,where τ
′
k
,
k
′, τ
k
,
k
′, and τ
′
′
k
,
k
′ are, respectively, train’s additional time for starting, pure travel time, and additional time for stopping in section e
(
k
,
k
′
), and δ
i
1
k is the symbol used to describe whether train i
,
1 stops at station k. If it stops at station k, then δ
i
1
k
=
1; otherwise, δ
i
1
k
=
0.(3) Constraints of Train Minimum Dwell Times at Stations. For making passengers have normal necessary time for getting on and off a train at stations, train’s dwell time at each stop station should not be less than a normal necessary time; namely,(5)
x
i
1
k
-
y
i
1
k
≥
τ
i
k
∀
i
;
k
∈
K
^
i
,where τ
i
k is the minimum dwell time of the ith type of periodic train at stop station k.(4) Safe Interval Constraints of Train Departure Times. For ensuring that trains depart safe at stations, the interval of departure times between any two trains entering into a same section must be more than the safe interval. That is(6)
x
i
r
k
-
x
i
j
k
≥
τ
k
k
′
d
∀
i
;
j
≠
r
;
k
∈
K
i
,
x
i
′
r
k
-
x
i
j
k
≥
τ
k
k
′
d
∀
i
≠
i
′
;
j
,
r
;
k
∈
K
i
∩
K
i
′
,where τ
k
k
′
d is the safe departure time interval of trains departing from station k to station k
′.(5) Safe Interval Constraints of Train Arrival Times. Similarly, for ensuring that trains arrive safe at stations, the arrival time interval among any two trains arriving from a same section must not be less than the safe arrival time interval. That is(7)
y
i
r
k
-
y
i
j
k
≥
τ
k
′
k
a
∀
i
;
j
≠
r
;
k
∈
K
i
,
(8)
y
i
′
r
k
-
y
i
j
k
≥
τ
k
′
k
a
∀
i
≠
i
′
;
j
,
r
;
k
∈
K
i
∩
K
i
′
,where τ
k
′
k
a is the safe arrival time interval of trains arriving at station k from station k
′.Minimizing trains total travel time is mostly used as the objective of optimizing train schedule; for example, Higgins et al. [14], Zhou and Zhong [15], Carey and Crawford [21], and Zhou et al. [28] all took it as the optimization objective of train schedule. Besides, some studies optimized train schedule with other objectives such as maximizing railway profit (Brännlund et al. [29]) or passengers expected waiting time (Zhou and Zhong [15]) and maximizing trains adjustment ability (Ghoseiri et al. [30]). However, these objectives cannot roundly reflect passenger service level related to train schedule. In this paper, we strive to not only reduce passenger in-vehicle time, but also lower their deferred time or advanced time at origins. Thus, minimizing passenger generalized travel cost is chosen as the objective of multiperiod mixed train schedule optimization. That is(9)
min
⁡
⁡
Z
=
∑
r
∑
s
≠
r
C
r
s
,where C
r
s is the generalized travel cost of OD (
r
,
s
), whose components and calculation method are given in detail in Section 3.


## 3. Analysis and Calculation of Passenger Generalized Travel Costs

High-speed railway demand varies with not only OD pair, but also time of one day. Passenger demand of ODr
,
s at time t is denoted by q
r
s
(
t
). They usually have two travel strategies based on a multiperiod mixed train schedule. One strategy is arriving in origin station at time t and then boarding a train departing after that time, which is called Later Travel, and other one is arriving at station in advance for getting on a train departing before time t, which is called Earlier Travel.In this paper, it is assumed that passengers only choose trains that will stop successively at their origin and destination stations and do not transfer between two trains, which is very common on rail network, because the stop-by-stop trains generally have to be operated on the high-speed railway for ensuring that passengers can travel with at least one type through train. The set of candidate trains of ODr
,
s passengers at time t is denoted by Ω
r
s
(
t
). It can be divided into two subsets denoted by Ω
r
s
′
t and Ω
r
s
′
′
t, respectively for Earlier Travel and Later Travel.For Earlier Travel passengers, their generalized travel costs include price expense, in-vehicle time, and additional cost of advanced travel, while Later Travel passengers have to bear price expense, in-vehicle time, and additional cost of deferred travel. In fact, additional costs of advanced travel and deferred travel are just a penalty fee for making trains departure time distribution better fit demand time distribution, which contributes to satisfying more passengers’ expectation of departing at their favorite time.When passengersq
r
s
t choose train i
,
j
∈
Ω
r
s
′
′
t for Later Travel, their price expense p
r
s
i
j
t, in-vehicle time b
r
s
i
j
t and deferred time w
r
s
i
j
t can be given as follows:(10)
p
r
s
i
j
t
=
μ
i
∑
e
(
k
,
k
′
)
∈
E
r
s
l
k
,
k
′
,
(11)
b
r
s
i
j
t
=
y
i
j
s
-
x
i
j
r
,
(12)
w
r
s
i
j
t
=
x
i
j
r
-
t
,where μ
i is the price rate of the ith type of periodic train, l
k
,
k
′ is the mileage of section e
k
,
k
′, and E
r
s is the section set from station r to station s.For balancing price expense, in-vehicle time and deferred time, the parameter of penalty rateα is introduced to describe passenger generalized travel cost as follows:(13)
c
r
s
i
j
t
=
p
r
s
i
j
t
+
ϵ
b
r
s
i
j
t
+
α
w
r
s
i
j
t
,where ϵ is the average time value of passengers.When passengersq
r
s
t choose train i
,
j
∈
Ω
r
s
′
t for Earlier Travel, their price expense p
r
s
i
j
t in-vehicle time b
r
s
i
j
t can also be calculated by formulas (10) and (11), and their advanced time d
r
s
i
j
t is given by(14)
d
r
s
i
j
t
=
t
-
x
i
j
r
.Similarly, two parameters, that is, time valueϵ and penalty rate β, are introduced for balancing price expense, in-vehicle time, and additional cost; namely,(15)
c
r
s
i
j
t
=
p
r
s
i
j
t
+
ϵ
b
r
s
i
j
t
+
β
d
r
s
i
j
t
.According to the generalized travel cost of passengers travelling with each candidate train, we can determine the finally chosen train of passengersq
r
s
t as i
∗
,
j
∗ with minimum travel cost c
r
s
∗
t. Consider(16)
c
r
s
∗
t
=
min
⁡
⁡
c
r
s
i
j
t
∣
i
,
j
∈
Ω
r
s
t
=
Ω
r
s
′
t
∪
Ω
r
s
′′
t
.Considering that passenger demand of each OD is a continuous distribution of time, passenger travel periodt
s
,
t
e in one day is divided into G subperiods with a same length δ
=
t
e
-
t
s
/
G, for example, 1 min, which are denoted by w
1
,
w
2
,
…
,
w
G, respectively. For subperiod w
g, its start time and end time are t
s
+
δ
g
-
1 and t
s
+
δ
g, respectively, and its total demand q
r
s
g is given by(17)
q
r
s
g
=
∫
t
s
+
δ
(
g
-
1
)
t
s
+
δ
g
q
r
s
t
d
t
.Thus, the total generalized travel costC
r
s of OD r
,
s passengers in objective function (9) can be obtained by accumulating the travel costs of passengers at each subperiod in one day; namely,(18)
C
r
s
=
∑
g
=
1
G
q
r
s
g
c
r
s
∗
t
g
.Obviously, we can get passenger minimum generalized travel cost by comparing their travel costs of all candidate trains, which is one most direct method but with less efficiency. However, a more efficient approach can be designed according to some characteristics of multiperiod mixed train schedule.Property 1.
Passengersq
r
s
g have the lowest generalized travel cost traveling with train departing latest comparing with other trains in set Ω
r
s
′
t
g, or with train departing earliest comparing with other trains in set Ω
r
s
′′
t
g.Property1 is true because passengers have same price expense and in-vehicle time when they travel with the same type of periodic trains, and the closer the train departure time is to their expectant time, the less their deferred times or advanced times are.Meanwhile, as passengers deferred time and advanced times monotonously change with the departure time of their travel train, another two properties can be drawn.Property 2.
For time periodt
w
,
t
h between two departure times of neighbor trains in set Ω
r
s, if passengers q
r
s
t
w have the minimum generalized cost c
r
s
′′
t
w when traveling with train (
i
′′
,
j
′′
) from set Ω
r
s
′′
t
w, passengers of any time t
∈
t
w
,
t
h also have the lowest generalized cost c
r
s
′′
t
w
-
α
t
-
t
w with train (
i
′′
,
j
′′
) from set Ω
r
s
′′
t
w.Property 3.
For time periodt
w
,
t
h between two departure times of neighbor trains in set Ω
r
s, if passengers q
r
s
t
w have the minimum generalized cost c
r
s
′
t
w when traveling with train i
′
,
j
′ from set Ω
r
s
′
t
w, passengers of any time t
∈
t
w
,
t
h also have the lowest generalized cost c
r
s
′
t
w
+
β
t
-
t
w with train i
′
,
j
′ from set Ω
r
s
′
t
w.For ODr
,
s passengers in period t
w
,
t
h, their minimum generalized travel cost can be calculated based on Properties 1, 2, and 3. Firstly, the minimum travel cost of time t
w passengers for Later Travel and Earlier Travel can be obtained, respectively, as c
r
s
′
′
t
w and c
r
s
′
t
w by comparing their lowest cost among all types of periodic train according to Property 1. Then the minimum generalized travel cost of other time passengers in t
w
,
t
h for Later Travel and Earlier Travel can be calculated as c
r
s
′′
t
=
c
r
s
′
′
t
w
-
α
t
-
t
w and c
r
s
′
t
=
c
r
s
′
t
w
+
β
t
-
t
w, respectively, based on Properties 2 and 3. Finally, the minimum generalized travel cost of passengers in t
w
,
t
h can be obtained according to the change relation of c
r
s
′
′
t and c
r
s
′
t with time t shown in Figure 3.Figure 3
The change relation ofc
r
s
′
′
t and c
r
s
′
t with time t
.
(a)
(b)
(c)Obviously, the minimum travel cost of passengers at any timet
∈
t
w
,
t
h is c
r
s
′
′
t in Figure 3(a), that is, c
r
s
′
t in Figure 3(b). But in Figure 3(c), passengers are divided into two parts, these in time t
∈
t
w
,
t
¯ have the minimum travel cost of c
r
s
′
t, and the other part passengers’ minimum travel cost is c
r
s
′′
t.Based on the above analysis, a high-efficiency algorithm for calculating passengers minimum travel costs is designed as in Algorithm1.Algorithm 1:Calculating the minimum travel cost of OD (r
,
s) passengers.
Input is a multiperiod mixed train schedule(
X
,
Y
), and OD (r
,
s) demand;
Output is minimum travel costc
r
s
∗
(
t
g
) (g
=
1,2
,
…
,
G).
start
Sort trains departure times at stationr by ascending order, and create the set of time periods;
S
=
{
[
t
w
,
t
h
]
};
For∀
[
t
w
,
t
h
]
∈
S, calculate the minimum travel cost c
r
s
′
′
(
t
w
) and c
r
s
′
(
t
w
), then
Ifc
r
s
′
′
(
t
w
)
≤
c
r
s
′
(
t
w
), then
Forg
=
1,2
,
…
,
G, if t
g
∈
[
t
w
,
t
h
], then c
r
s
∗
(
t
g
)
=
c
r
s
′
′
(
t
w
)
-
α
(
t
-
t
w
).
Else ifc
r
s
′
(
t
w
)
+
β
(
t
h
-
t
w
)
≤
c
r
s
′
′
(
t
w
)
-
α
(
t
h
-
t
w
), then
Forg
=
1,2
,
…
,
G, if t
g
∈
[
t
w
,
t
h
], then c
r
s
∗
(
t
g
)
=
c
r
s
′
(
t
w
)
+
β
(
t
-
t
w
).
Else
Determinet
¯ by solving equation c
r
s
′
′
(
t
w
)
-
α
(
t
-
t
w
)
=
c
r
s
′
(
t
w
)
+
β
(
t
-
t
w
);
Forg
=
1,2
,
…
,
G, if t
g
∈
[
t
w
,
t
¯
], then c
r
s
∗
(
t
g
)
=
c
r
s
′
(
t
w
)
+
β
(
t
-
t
w
);
Forg
=
1,2
,
…
,
G, if t
g
∈
[
t
¯
,
t
h
], then c
r
s
∗
(
t
g
)
=
c
r
s
′
′
(
t
w
)
-
α
(
t
-
t
w
).
End if
End for
End


## 4. Scheduling One Type of Trains Based on a Given Partial Train Schedule

This section focuses to schedule a new type of periodic train based on a given multiperiod mixed train scheduleX
,
Y in which partial type of periodic trains have been scheduled. Suppose the new train type being scheduled is the ith one. For this type of periodic train, their service OD pairs are denoted as F
i. After scheduling them, OD r
,
s
∈
F
i passengers travel with the ith type of periodic train instead of other type of periodic train if the former has less travel costs than the latter, which will lead to a decrease of their travel costs.For ODr
,
s
∈
F
i passengers q
r
s
g, their travel cost is denoted as c
r
s
(
t
g
) before scheduling the ith type of periodic train, and their travel cost turns to c
r
s
i
(
t
g
) after that. Obviously, if c
r
s
i
t
g
<
c
r
s
(
t
g
), passengers q
r
s
g give up the former train and rechoose the ith type of periodic train for travel, and they have the following decrease of travel cost:(19)
Δ
c
r
s
i
t
g
=
c
r
s
t
g
-
c
r
s
i
t
g
.Else if c
r
s
i
t
g
≥
c
r
s
(
t
g
), passengers q
r
s
g still choose their former train for travel and their decrease of travel cost is regarded as Δ
c
r
s
i
t
g
=
0. Thus, passengers’ total decrease of travel cost of OD r
,
s can be calculated by(20)
Δ
c
r
s
i
=
∑
g
=
1
G
Δ
c
r
s
i
t
g
.Similarly, we can determine the travel cost decrease of other OD passengers in setF
i. Based on these, the total decrease of passenger travel costs caused by scheduling the ith type of periodic train can be given by(21)
Δ
c
i
=
∑
r
,
s
∈
F
i
Δ
c
r
s
i
.And minimizing it is chosen as the objective of scheduling the ith type of periodic train; namely,(22)
min
⁡
⁡
Δ
c
i
=
∑
r
,
s
∈
F
i
Δ
c
r
s
i
.Meanwhile, all trains’ departure and arrival times have to satisfy the constraints of formula (1) through formula (8) when scheduling X
i
,
Y
i.Before scheduling theith type of periodic train, if there are other types of scheduled periodic trains traversing section e
(
k
i
1
,
k
i
2
), the operation period T
s
,
T
e can be divided into H subperiods denoted as t
_
1
,
t
¯
1
,
t
_
2
,
t
¯
2
,
…
,
[
t
_
H
,
t
¯
H
], respectively, by their departure times at station k
i
1; otherwise, we express period t
s
,
t
e also by [
t
_
1
,
t
¯
1
] for uniform description. A train of the ith type can depart in subperiod [
t
_
h
,
t
¯
h
] only when the next condition shown in Figure 4 is satisfied:(23)
t
_
h
≤
t
¯
h
-
t
i
e
t
_
h
=
T
s
,
t
¯
h
=
T
e
t
_
h
≤
min
⁡
⁡
t
¯
h
-
φ
e
,
t
¯
h
+
t
e
′′
-
ϑ
e
-
t
i
e
t
_
h
=
T
s
,
t
¯
h
≠
T
e
max
⁡
⁡
t
_
h
+
φ
e
,
t
_
h
+
t
e
′
+
ϑ
e
-
t
i
e
≤
t
¯
h
-
t
i
e
t
_
h
≠
T
s
,
t
¯
h
=
T
e
max
⁡
⁡
t
_
h
+
φ
e
,
t
_
h
+
t
e
′
+
ϑ
e
-
t
i
e
≤
min
⁡
⁡
t
¯
h
-
φ
e
,
t
¯
h
+
t
e
′′
-
ϑ
e
-
t
i
e
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
t
_
h
≠
T
s
,
t
¯
h
≠
T
e
,where t
i
e is the travel time of the ith type of periodic train in section e
(
k
i
1
,
k
i
2
), and t
e
′, t
e
′
′ are, respectively, these of trains departing at times t
_
h and t
¯
h in section e
(
k
i
1
,
k
i
2
).Figure 4
Train’s feasible departure time range in subperiodt
_
h
,
t
¯
h.
(a)
t
_
h
=
T
s
,
t
¯
h
=
T
e
(b)
t
_
h
=
T
s
,
t
¯
h
≠
T
e
(c)
t
_
h
≠
T
s
,
t
¯
h
=
T
e
(d)
t
_
h
≠
T
s
,
t
¯
h
≠
T
eAccordingly, the feasible departure period[
d
_
h
,
d
¯
h
] of the ith type of periodic train in subperiod [
t
_
h
,
t
¯
h
] can be determined by(24)
d
_
h
,
d
¯
h
=
[
t
_
h
,
t
¯
h
-
t
e
]
t
_
h
=
T
s
,
t
¯
h
=
T
e
[
t
_
h
,
min
⁡
⁡
t
¯
h
-
φ
e
,
t
¯
h
+
t
e
′′
-
ϑ
e
-
t
e
]
h
h
h
h
h
h
h
h
h
h
h
t
_
h
=
T
s
,
t
¯
h
≠
T
e
[
max
⁡
⁡
t
_
h
+
φ
e
,
t
_
h
+
t
e
′
+
ϑ
e
-
t
e
,
t
¯
h
-
t
e
]
h
h
h
h
h
h
h
h
h
h
h
t
_
h
≠
T
s
,
t
¯
h
=
T
e
max
⁡
⁡
t
_
h
+
φ
e
,
t
_
h
+
t
e
′
+
ϑ
e
-
t
e
,
min
⁡
⁡
t
¯
h
-
φ
e
,
t
¯
h
+
t
e
′′
-
ϑ
e
-
t
e
h
h
h
h
h
h
h
h
h
h
h
t
_
h
≠
T
s
,
t
¯
h
≠
T
e
.All feasible departure periods of one day form the candidate set of departure time denoted byR
i
k
i
1
,
k
i
2 of the ith type of periodic train in section e
(
k
i
1
,
k
i
2
).The beginning of scheduling theith type of periodic train is to choose n
i time numbers constituting an arithmetic progression with the difference of T
i from R
i
k
i
1
,
k
i
2 as their departure times at origins. As the number of their combination solution is enormous, two strategies are applied to reduce the search scope:(1)
Take timet
^
i at which a train departing can make largest decrease of passenger travel cost as one necessary departure time for the ith type of periodic train.
(2)
Make the operation period of theith type of periodic train only be an integer time of λ (λ can be 10 min, 15 min, or 30 min) which contributes to remembering trains operation regularity for passengers.Based on above two strategies, we only have to determine which train is departing at timet
^
i and how many integer times of λ are being the operation period. Denote the train departing at time t
^
i as the j
∗th train, that is, train i
,
j, and ω
∗ as the integer times. Then the departure and arrival times in section e
k
i
1
,
k
i
2 of the ith type of periodic train can be obtained as follows:(25)
x
i
j
1
=
t
^
i
-
λ
(
j
∗
-
j
)
ω
∗
1
≤
j
<
j
∗
t
^
i
j
=
j
∗
t
^
i
+
λ
(
j
-
j
∗
)
ω
∗
j
∗
<
j
≤
n
i
j
=
1,2
,
…
,
n
i
(26)
y
i
j
2
=
x
i
j
1
+
t
e
.Obviously, the value scope of integerj
∗ is from 1 to n
i, and the value of integer ω
∗ must satisfy(27)
t
^
i
-
λ
j
∗
-
1
ω
∗
≥
T
s
t
^
i
+
λ
n
i
-
j
∗
ω
∗
≤
T
e
.That is(28)
ω
∗
≤
min
⁡
⁡
t
^
i
-
T
s
λ
j
∗
-
1
,
T
e
-
t
^
i
λ
n
i
-
j
∗
.However, departure times calculated by formula (25) do not always belong to R
i
k
i
1
,
k
i
2, we have to ignore these solutions not belonging to R
i
k
i
1
,
k
i
2. As the combination of j
∗ and ω
∗ is very limited, we can search their all possible combinations and determine their best one according to the decrease Δ
c
i of passenger travel cost.Given a feasible solution(
j
∗
,
ω
∗
), the departure and arrival times of the ith type of periodic train in their first traverse section e
k
i
1
,
k
i
2 can be easily determined by formulas (25) and (26). However, we still have to arrange their departure and arrival times in other traverse sections. In section e
k
i
2
,
k
i
3, their earliest departure times can be given firstly by(29)
x
i
j
2
=
y
i
j
2
+
τ
i
2
j
=
1,2
,
…
,
n
i
.And similarly, a candidate set of departure times of the ith type of periodic train in section e
(
k
i
2
,
k
i
3
) can be determined as R
i
k
i
2
,
k
i
3. Then a minimum value of Δ
t
≥
0 is determined for satisfying(30)
x
i
j
2
+
Δ
t
∈
R
i
k
i
2
,
k
i
3
j
=
1,2
,
…
,
n
i
.Then the departure and arrival times of the ith type of periodic train in section e
k
i
2
,
k
i
3 can be given by(31)
x
i
j
2
=
x
i
j
2
+
Δ
t
j
=
1,2
,
…
,
n
i
y
i
j
3
=
x
i
j
2
+
t
i
e
j
=
1,2
,
…
,
n
i
.And their departure and arrival times in other left traverse sections can be determined similarly. Now a whole periodic schedule of the ith type of periodic train is got according to (
j
∗
,
ω
∗
). Based on it, passenger travel cost decrease Δ
c
i can be calculated according to formulas (19), (20), and (21).It should be pointed out that if there are no feasible solutions when taking the time with the maximum decrease of passenger travel cost as one necessary departure timet
^
i of the ith type of periodic train, another time making that has secondary maximum decrease can be chosen as its necessary departure time t
^
i.


## 5. Optimization Algorithm of Multiperiod Mixed Train Schedule

This section gives a general optimization algorithm of multiperiod mixed train schedule based on the scheduling algorithm of one type of periodic train proposed in Section4. Its solving frame is to circularly optimize each type of periodic train. Firstly, all types of periodic trains are scheduled type by type according to a given initializing order using Algorithm 2. The initializing order of each type of periodic train is determined based on trains’ travel mileage and their number of stop stations. The more travel mileage and less number of stop stations one type of train has, the earlier scheduled it is. Secondly, we calculate the total numbers of passengers on each type of periodic train, and, based on these, determine their adjustment orders, and then reschedule each type of periodic train according to this adjustment order with Algorithm 2. The rescheduling process of all types of trains’ is repeated until one of the given termination conditions of the algorithm is satisfied.Algorithm 2:Scheduling the ith type of periodic train based on a given train schedule.
Input is partial train schedule(
X
,
Y
), and the ith type of periodic train;
Output is multiperiod mixed train schedule(
X
,
Y
)
∪
(
X
i
,
Y
i
);
Start
Determine OD setF
i, and set of train candidate departure time R
i
(
k
i
1
,
k
i
2
) in its first traverse
sectione
(
k
i
1
,
k
i
2
);
Calculate passenger travel cost decreaseΔ
c
i
(
t
) when an ith type of periodic train departing
at timet
∈
R
i
(
k
i
1
,
k
i
2
);
Sett
^
i as the time with maximum value of Δ
c
i
(
t
);
SetΔ
c
¯
i
=
0, j
∗
=
0, and ω
∗
=
0;
Forj
=
1,2
,
…
,
n
i, do
Setω
=
1;
Whileω satisfies formula (28), do
If(
j
,
ω
) satisfies formula (27), then
Calculate trains departure and arrival times in sectione
(
k
i
1
,
k
i
2
) by formula (25), (26)
Ifx
i
j
2
∈
R
i
(
k
i
1
,
k
i
2
) for all j, then
For trains’ next traverse sectione
(
k
i
,
m
,
k
i
,
m
+
1
) (m
=
2,3
,
…), do
Calculate trains earliest departure times according to formula (29);
DetermineΔ
t and calculate trains departure and arrival times;
End for
Calculate passenger travel cost decreaseΔ
c
i;
IfΔ
c
¯
i
<
Δ
c
i, then Δ
c
¯
i
=
Δ
c
i, j
∗
=
j, ω
∗
=
ω;
End if
End if
Setω
=
ω
+
1;
End while
End for
Scheduling theith type of periodic train based on (
j
∗
,
ω
∗
);
EndBefore this algorithm starting, all OD passengers cannot choose any trains for travelling because train scheduleX
,
Y is empty. Thus, their travel cost is set as a very big number Z
=
M. Then one type of periodic train, for example, the ith type, is selected according to the initializing order, and scheduled using Algorithm 2. After that, passengers’ total travel cost declines fromZ
=
M to Z
=
M
-
Δ
c
i, and train schedule is updated as X
,
Y
=
X
,
Y
∪
X
i
,
Y
i. When all types of periodic trains are scheduled, an initial multiperiod mixed train schedule is obtained.As passengers’ traveling trains have changed with the scheduling of all types of periodic trains one by one; trains passengers numbers and service levels also have changed. Thus, it is necessary to repeatedly reschedule all types of periodic trains for improving trains service level after generating the initial train schedule. Thus, we sort all types of periodic trains by the descent order of their passenger numbers and denoteo
i as the order position of the ith type of periodic train. When rescheduling the ith type of periodic train, they are deleted from X
,
Y firstly, which results in that passengers travelling originally with these types of trains have to choose other type of trains, and their total travel costs increase by Δ
c
-
i. Then we reschedule the ith type of periodic train based on the current train schedule X
,
Y, which also leads to that some passengers choose this type trains again and have their travel cost decrease by Δ
c
+
i. Thus, passengers’ travel cost changes from Z to Z
+
Δ
c
-
i
-
Δ
c
+
i after rescheduling the ith type of periodic train.The termination condition of the algorithm is that passenger total travel cost changes in a little range for more thanΥ times of rescheduling or the number of rescheduling has reached its maximum allowed value.


## 6. Example Analysis in Wu-Guang High-Speed Railway

In this section, an example in Wu-guang high-speed railway is given to analyze the convergence and effectiveness of the proposed model and algorithm. The Wu-guang high-speed railway between Wuhan city and Guangzhou city operates since 2009 in China, and is a busy passenger railway line operating with 57 trains each day, more trains in festival and holiday such as Spring Festival. It consists of 16 stations and has the total length of 1069 km as shown detailed in Table1. Wuhan station and Guangzhou station are its endpoint stations, and Changsha station, Shaoguang station are regarded as the big stations at which all type of periodic trains have to stop.Table 1
Stations and mileages of Wu-guang high-speed railway.
No.
Station name
Abbreviation
Mileage/km
1
Wuhan
WH
0
2
Xianning
XN
85
3
Chibi
CB
128
4
Yueyang
YY
215
5
Miluo
ML
285
6
Changsha
CS
362
7
Zhuzhou
ZZ
414
8
Hengshan
HS
498
9
Hengyang
HY
539
10
Leiyang
LY
594
11
Chenzhou
CZ
692
12
Shaoguan
SG
842
13
Yingde
YD
929
14
Qingyuan
QY
986
15
Guangzhoubei
GZB
1022
16
Guangzhou
GZ
1069Considering that most trains operating on Wu-guang high-speed railway have different stop stations and the numbers of trains having some stop stations are very small, just 1 or 2. Thus, almost one train can form a type of train, which is not appropriate for arranging them as a multiperiod mixed train schedule. Hence, we reassume that there are total 11 types of trains, whose origins, destinations, stop stations and numbers as shown in Table2, operating on the down direction of Wu-guang high-speed railway. As seen from there, the first type of train has the least stop stations, that is, Changsha and Shaoguang stations, and they mainly service the passengers among big stations. The last type of train stops at all traverse stations, and they mainly provide services for passengers whose origins and destinations locate between two big stations. And the other types of train have the stop stations with the average number of 6, and service passengers between big stations and other stations. All types of train have the maximum technical speed of 300 km/h and their additional times for starting and stopping are 1 min in all railway sections, and they have the minimum dwell time of 1 min at all stop stations.Table 2
All types of trains and their numbers.
Type number
Origin
Destination
Stop stations
Number
1
WH
GZ
CS, SG
3
2
WH
GZ
XN, YY, CS, ZZ, SG, YD
4
3
WH
GZ
XN, YY, CS, HS, LY, SG, GZB
5
4
WH
GZ
XN, YY, CS, HY, CZ, SG, QY
4
5
WH
GZ
CB, CS, ZZ, SG, QY
4
6
WH
GZ
CB, CS, HS, LY, SG, YD
4
7
WH
GZ
CB, CS, HY, CZ, SG, GZB
5
8
WH
GZ
ML, CS, ZZ, SG, GZB
6
9
WH
GZ
ML, CS, HS, LY, SG, QY
5
10
WH
GZ
ML, CS, HY, CZ, SG, YD
4
11
WH
GZ
XN, CB, YY, ML, CS, ZZ, HS, HY, LY, CZ, SG, YD, QY, GZB
3Algorithm3 is developed with computer language C# on the platform of Microsoft Visual Studio.net. The computer language C# developed by the development team of Anders Hejlsberg is released by Microsoft in 2000. It aims to become an object-oriented programming language with the characteristics of simple, modern and general. This language is derived from the computer language C and C++, and has inherited their powerful performances. Moreover, it takes the  .NET Framework Class Library as a basis, and therefore has the advantage of rapid application development similarly to Visual Basic. All instances run on the computer with the system of Microsoft Windows XP (Home Edition), RAM configuration of Pentium(R) Dual-Core CPU E5800, 3.19 GHz, 2.96 GB. The values of parameters in the above model and its solving algorithm are given in Table 3.Table 3
Parameter values of model and algorithm.
Symbol
Value
Unit
t
s
360
Min
τ
k
k
′
d
4
Min
μ
1
0.35
¥/passenger·km
μ
i (i
=
1,2
,
…
,
10)
0.28
¥/passenger·km
α
65
¥/h
M
9999999
—
Υ
6
—
t
e
1380
Min
τ
k
′
k
a
5
Min
μ
11
0.20
¥/passenger·km
ϵ
80
¥/h
β
90
¥/h
Ψ
max
⁡
15
—
ε
0.05
—Algorithm 3:Optimizing the multiperiod mixed train schedule of high-speed railway.
Input is High-speed rail lineL, train plan Ω, all operating time standard;
Output is multiperiod mixed train schedule(
X
∗
,
Y
∗
), passenger total travel cost Z
∗;
Start
Determine the initializing order of all type of periodic train;
Set(
X
,
Y
)
=
∅, and Z
=
M;
Foro
i
=
1,2
,
…
,
n do
Schedule theith type of periodic train, and calculate the decrease of travel time Δ
c
i;
Set(
X
,
Y
)
=
(
X
,
Y
)
∪
(
X
i
,
Y
i
), and Z
=
Z
-
Δ
c
i;
End for
SetΨ
max
⁡ be the maximum number of rescheduling, Ψ
=
0 be its current number, and φ
=
0
be the count of travel cost without reducing, andε
=
0.05;
Do
Set(
X
′
,
Y
′
)
=
(
X
,
Y
), and Z
′
=
Z;
Foro
i
=
1,2
,
…
,
n do
Delete theith type of periodic train, that is, set (
X
′
,
Y
′
)
=
(
X
′
,
Y
′
)
∖
(
X
i
′
,
Y
i
′
);
Calculate the increase of passenger travel costΔ
c
-
i, and set Z
′
=
Z
′
+
Δ
c
-
i;
Reschedule theith type of periodic train, and set (
X
′
,
Y
′
)
=
(
X
′
,
Y
′
)
∪
(
X
i
′
,
Y
i
′
);
Calculate the decrease of passenger travel costΔ
c
+
i and set Z
′
=
Z
′
-
Δ
c
+
i;
End for
IfZ
′
-
Z
/
Z
≤
ε, then φ
=
φ
+
1, else φ
=
0;
SetΨ
=
Ψ
+
1;
Whileφ
≤
Υ and Ψ
≤
Ψ
max
⁡
Set(
X
∗
,
Y
∗
)
=
(
X
′
,
Y
′
), and Z
∗
=
Z
′;
EndBased on the above inputs and parameter values, a multiperiod mixed train schedule is optimized as shown in Figure5, in which each type of line represents one type of train, when all types of train operating with the periods of the multiples of 10 min. As we can see, each type of train has its own operation periods and start times and end times of operation as shown detailed in Table 4. For example, the first type of train operates with start time of 6:52, end time of 16:52, and its operation period is 5 h, while the second type of train has the operation period of 2 h and 50 min and operates starting from 8:43 to 17:13. Obviously, the operation periods of all types of train are the multiples of 10 min.Table 4
Trains operation times and periods.
Train type number
Start time of operation
Operation period/min
End time of operation
1
6:52
5 h
16:52
2
8:43
2 h 50 min
17:13
3
7:00
2 h 30 min
17:00
4
9:10
2 h
15:10
5
7:35
3 h
16:35
6
8:32
2 h 10 min
15:02
7
6:40
3 h
18:40
8
8:10
2 h
18:10
9
8:55
2 h 30 min
18:55
10
8:22
2 h 30 min
15:52
11
7:10
5 h 20 min
17:50Figure 5
The multiperiod mixed train diagram with periods of the multiples of 10 min.Although this multiperiod mixed train schedule provides 11 types of periodic trains for passengers, actually passengers of each OD need not know the operation regularity of all types of train and just to know these of their candidate trains. Hence, the information that passengers should be familiar with is smaller than these of all types of train. For example, most of passengers from Hengshan station to Guangzhou station would like to choose the 3rd, 6th, and 9th type of train for travelling because that the 11th type of train has too many stop stations for them, and the other types of train do not stop both at their origins and destinations. Thus, they only have to remember the operation regularities of these three types of train.Next, we analyze the convergence of Algorithm3. The operation periods of all types of train are set as the multiples of 10 min, 15 min (one quarter), and 30 min (half an hour), respectively, and then optimize their corresponding multiperiod mixed train schedules for 20 times, each case based on the above inputs and parameter values. The computational results show that some instances of three cases cannot obtain a feasible solution because a small part of types of trains are not scheduled successfully as the restriction of its operation period and other scheduled trains. The numbers of invalid instances in three cases are 1, 3, and 7, respectively. Obviously, it becomes larger with the period multiple increasing from 10 min to 15 min and then to 30 min. However, we can avoid them by adjusting train scheduling order and then rescheduling them.The change relation of objectiveZ with the iteration number is given as shown in Figure 6, and the change relationship of computing time with the iteration number is shown in Figure 7. As seen from Figure 6, when trains’ operation periods are set as the multiples of 10 min, the algorithm terminates as the objective value changes in a little range for more than Υ
=
6 times, and it can be better converge to a satisfactory solution. However, when they are set as these of 15 min and 30 min, although the objective value also descents quickly at the first 8 iterations, it waves among a small range later. Finally, the algorithm stops as it reaches the maximum iteration count, that is, 16 times. Based on Figure 7, we can find that the computing time of the case with the multiples of 10 min being trains’ operation periods is far smaller than these of the other two cases. The computing time of the case with λ
=
10min is only 6 min while these of the cases with λ
=
15min and λ
=
30min are 15 min and 32 min, respectively. Moreover, the average computing times per iteration also have a lot of differences among these three cases. The average computing time per iteration in the case with λ
=
10min is 0.6 min, while these of the other two cases are 1.0 min and 2.3 min, respectively. The most reasonable explanation is that with the value of λ increasing from 10 min to 15 min and then to 30 min, more and more impossible train schedules may appear when scheduling each type of train because of the operation period restriction, which not only leads to a lower solution quality, but also resulted in more computing times.Figure 6
The change relation of objectiveZ with the iteration number.Figure 7
The change relation of computing time with the iteration number.In order to compare with an aperiodic train schedule, firstly each train is regarded as one type and is scheduled to create an aperiodic train schedule. Then optimize the multiperiod mixed train schedule with operation periods as the multiples of 10 min, 15 min, and 30 min, respectively. Passenger service level indexes including average deferred time and average advanced time of the aperiodic train schedule and the three multiperiod mixed train schedules are given in Table5. As seem from there, three multiperiod mixed train schedules have more deferred times and advanced times comparing with the aperiodic train schedule. While the average deferred time of the aperiodic train schedule is 35 min, these of the three multiperiod mixed train schedules are 45 min, 48 min, and 54 min, respectively, which are larger than the former by 28.5%, 37.1%, and 54.3%. That is because the optimization of multiperiod mixed train schedule has more restrictions comparing with the aperiodic train schedule for making same type of train operate periodically. Hence, it is suggested that it is prior to take the multiples of 10 min or 15 min as trains’ operation periods.Table 5
The service level comparison between aperiodic and multiperiod mixed train schedules.
Items
Aperiodic train schedule
Multiperiods of multiples of 10 min
Multiperiods of multiples of 15 min
Multiperiods of multiples of 30 min
Average deferred time/min
35
45
48
54
Maximum deferred time/min
153
189
183
198
Average advanced time/min
24
31
32
39
Maximum advanced time/min
114
131
128
134
Objective value/Yuan
834578
876473
903767
934354


## 7. Conclusion and Further Study

In this paper, a new type of train schedule called multiperiod mixed train schedule is first proposed to make trains operate with multivarious periodic bases. Then its optimization model is built to minimize passengers generalized travel costs including price expense, in-vehicle time, and penalty cost for deferred or advanced travel subjecting to lots of constraints covering the periodic operation requirement of trains of same type, high-speed railway operation time, and safe headway requirement of train departure and arrival times. Then a heuristic algorithm, in which each type of periodic train is rescheduled circularly, is designed to solving this model. Example results illustrate that a satisfactory multiperiod mixed train schedule can be gained using the proposed model and algorithm. However, it has more average deferred or advanced time comparing with the aperiodic train schedule.This paper only considers the optimization of multiperiod mixed train schedule on a high-speed rail line. It is very necessary to optimize that of a rail network in the further researches because those trains on different rail lines interact with one another. Moreover, as passenger demands of high-speed railway largely depend on their service level under the competitive environment with air transportation and highway, another further research is to take this effect into consideration when optimizing multiperiod mixed train schedule.



---

*Source: 107048-2015-04-20.xml*