# A Pragmatic Optimization Method for Motor Train Set Assignment and Maintenance Scheduling Problem

Authors: Jian Li; Boliang Lin; Zhongkai Wang; Lei Chen; Jiaxi Wang
Journal: Discrete Dynamics in Nature and Society
 (2016)

---

## Abstract

With the rapid development of high-speed railway in China, the problem of motor train set assignment and maintenance scheduling is becoming more and more important for transportation organization. This paper focuses on considering the special maintenance items of motor train set and mainly meets the two maintenance cycle limits on aspects of mileage and time for each item. And then, a 0-1 integer programming model for motor train set assignment and maintenance scheduling is proposed, which aims at maximizing the accumulated mileage before each maintenance and minimizing the number of motor train sets. Restrictions of the model include the matching relation between motor train sets and routes as well as that between motor train sets and maintenance items and maintenance capacity of motor train set depot. A heuristic solution strategy based on particle swarm optimization is also proposed to solve the model. In the end, a case study is designed based on the background of Beijing south depot in China, and the result indicates that the model and algorithm proposed in this paper could solve the problem of motor train set assignment and maintenance scheduling effectively.


---

## Body

## 1. Introduction

In recent years, the high-speed railway in China has been developing quickly, and the number of motor train sets and trains running on the high-speed railway have been increasing year by year at the same time. By the end of year 2014, the total operation mileage of China railway is 112,000 kilometers, of which the operation mileage of high-speed railway is 16,000 kilometers, and there are 1411 motor train sets running for the high-speed railway passenger transportation. Therefore, in order to improve the service for high-speed railway transportation organization further, the problem of how to enhance the motor train set management including motor train set assignment and maintenance scheduling is becoming a focus of attention for the railway transportation department, and it is difficult to be solved effectively. The motor train set has a few special characteristics compared with the general rolling stock, which is reflected as follows: Firstly, the procurement cost of a motor train set is very expensive; for example, a normative “CRH” motor train set is worth 31,000,000 dollars approximately, which is much more expensive than the general rolling stock, so it is of great significance to minimize the number of motor train sets. Secondly, the inspection and repair system of motor train set in China is extremely complex; there are more than ten types of “CRH” motor train sets, and each type of motor train set includes a lot of different maintenance items. What is more, the maintenance cycle and maintenance place of each item range a lot as well, which together make it difficult to schedule the maintenance work. Thirdly, the mileage of the route ranges a lot; some are long route, while the others are short route, and the motor train set assignment for a route relies on the type of motor train set. Besides, there is a strong relevance between motor train set assignment and maintenance scheduling, so we should take the two sides into consideration at the same time while scheduling the motor train set assignment for a route and maintenance work. In practice, the motor train set assignment and maintenance scheduling is made by hand according to the experience of dispatcher in the motor train set depot generally, and it is nearly impossible to get an optimization schedule. Therefore, it is needed to take the train set assignment and maintenance scheduling into consideration simultaneously while making up the motor train set circulation plan, which is helpful to improve the quality of the plan. In this way, it not only increases the motor train set operation efficiency and reduces the number of motor train set as well as the procurement cost but also reduces the maintenance times and the maintenance cost during a fixed period.In this paper, we research the problem of motor train set assignment and maintenance scheduling based on the practical problem existing in the motor train set depot in China and propose a pragmatic method for optimizing the motor train set assignment and maintenance scheduling, which could produce an optimal result and provide a reference for motor train set assignment and maintenance scheduling in the motor train set depot.The organization of this paper is as follows: Section1 is the introduction. Section 2 is about the related literature review. In Section 3, we introduce the problem about motor train set assignment and maintenance scheduling. In Section 4, we analyze the optimization objective and constraints, and a 0-1 integer programming mathematical model is proposed. In Section 5, we discuss the solution algorithm for the optimization model. In Section 6, a practical case study is designed. Section 7 is the conclusion and prospects of this paper.


## 2. Related Literatures

With the development of high-speed railway around the world, many experts and scholars have researched the motor train set assignment and maintenance scheduling problem from different aspects and proposed different models and solution methods for the motor train set circulation. For the literatures, Kroon [1–4] researched the rolling stock assignment and connection problem extensively and profoundly, and these researches mainly aimed at minimizing the number of motor train sets and enhancing the robustness of the motor train set circulation plan which was based on the given train arcs and time table and considered the constraints including the type of motor train set and the maintenance condition. And then, a few diverse integer programming models were proposed according to the different concrete issues, and some algorithms such as branch and bound method were designed to solve the optimization models. Cordeau et al. [5] proposed a multicommodity network flow-based model for assigning locomotives and cars to trains in the context of passenger transportation and adopted a branch-and-bound method to solve the problem. Lingaya et al. [6] researched locomotives and cars assignment to a set of scheduled trains for the passenger railways, and they described a modeling and solution methodology for a car assignment problem. Noori and Ghannadpour [7] studied the locomotive assignment problem which is modeled using vehicle routing and scheduling problem in their research, and a two-phase approach based on a hybrid genetic algorithm is used to solve the problem. Maróti [8, 9] focused on the regular preventive maintenance of train unites at NS Reizigers and presented two integer programming models for solving the maintenance routing problem: one is the interchange model and the other is the transition model, which could solve the maintenance issue in the forthcoming one to three days for the train unites. Giacco et al. [10] focused on the motor train set connection problem on a transportation service network and then aimed at minimizing the number of motor train sets and constructed a mixed integer linear programming model for optimizing the short-period maintenance scheduling of motor train set, and the model took the transportation tasks, running without taking passengers, with short-period maintenance items into consideration. Many experts and scholars have researched the same problem in other relevant industries such as the fleet assignment problem (FAP). El Moudani and Mora-Camino [11] proposed a dynamic approach for the problems of assigning planes to fights and of feet maintenance operations scheduling in their research. Sherali et al. [12] presented a method to integrate the FAP with schedule design, aircraft maintenance routing, and crew scheduling and presented a randomized search procedures. Deris et al. [13] researched the problem of ship maintenance scheduling and modelled it as a constraint satisfaction problem (CSP) in their paper, and a genetic algorithm (GA) was adopted to solve the problem. Go et al. [14] researched the problem of operation and maintenance scheduling for a containership and developed a mixed integer programming model for the problem, based on which a heuristic algorithm was presented.There are also many Chinese experts and scholars who have researched the relevant problem according to the actual situation in China. Nie et al. [15] and Zhao and Tomii [16] comparatively early researched the operation problem of motor train set with mainly considering the following influences: empty motor train set dispatching, diverse types of motor train set, multibase of motor train set, and so on, which laid the theoretical foundation for optimizing the motor train set circulation. Huang [17] mainly aimed at the routine maintenance issue and attempted to optimize the motor train set operation and maintenance plan. In this research, the inspection and repair system, the supply system of spare parts, and the maintenance management information system were considered. Wang et al. [18] analyzed three statuses of motor train set, including undertaking route, being in maintenance, and waiting for maintenance and then a connection network composed of undertaking route and conducting maintenance is designed, based on which the author proposed an optimization model aiming at maximizing the accumulated mileage before conducting the corresponding maintenance. Zhang et al. [19] considered the constraints from two aspects particularly, that is, maintenance time period and maintenance mileage cycle of motor train set, and presented an optimization method to solve the problem. Wang et al. [20] researched the integrated optimization method for operation and maintenance planning of motor train set, which aimed at reducing the number of motor train sets and the maintenance cost, and designed a max-min ant colony algorithm to solve the problem. Li [21] presented a decomposition strategy to break down the motor train set operation planning problem into three subproblems from diverse dimensionality, which includes the time, the space, and the process. The motor train set plan was divided into the routine operation maintenance planning problem and the advanced maintenance planning problem, and then the author proposed an integer programming model for optimizing the former problem. Wang et al. [22] focused on the multidepot vehicle routing problem and proposed a novel fitness-scaling adaptive genetic algorithm with local search to solve the problem, which was superior to some other algorithm, such as the standard genetic algorithm. Zhang et al. [23] analyzed and summarized the application of particle swarm optimization in different areas, which is helpful for the solution strategy designing in this paper.From the literatures mentioned above, we could get a conclusion that the related issues about motor train set circulation problem are researched extensively and profoundly, and a few research achievements are got, such as optimization models and solution algorithms. However, the researches and the achievements are focused on some specific issues on the whole. What is more, the condition of high-speed railway in china is not the same with that abroad, and the corresponding research achievements abroad could not be used to serve the transportation organization of high-speed railway in china directly, and those in china mostly stay at a level of theoretical research.


## 3. Basic Problem Description

The problem discussed in this paper is the motor train set assignment and maintenance scheduling, and it refers to a few key elements including motor train sets, routes, and maintenance items. Therefore, the main tasks of motor train set assignment and maintenance scheduling are to assign a well-conditioned motor train set to each route every day and to arrange the maintenance work of motor train set, of which the accumulated mileage or time of the corresponding maintenance item after the latest maintenance is to meet the maintenance cycle. In this paper, we define the route as the ordered trains’ circulation which are undertaken by the same motor train set from the departure to the arrival at the motor train set depot. That is to say, the departure depot and the arrival depot are the same depot which is the attachment depot of the motor train set. In China, there is a certain time reserved for infrastructure inspection of high-speed railway, which is generally 4 to 6 hours, and the train is forbidden during this period. So the motor train set regularly stays at the attachment depot or the other depot at night. Therefore, the departure time and the arrival time of a route may not be in the same day, so according to the departure time and the arrival time of each route, we divide the route into one-day route and multiday route in this paper. In our opinion, if the departure time and the arrival time of a route are on the same day (00:00~24:00), we call the route a one-day route. And if the arrival time of a route is on the next day relative to the departure time, we call the route a two-day route, and the others can be called multiday route by that analogy. The definition of route could be helpful for the optimization model construction in the later research and it is much more tallied with the actual condition in the motor train set depot.According to the definition of route, we give a diagrammatic sketch of route which is shown in Figure1. In the diagrammatic sketch, there are three stations named station A, station B, and station C, respectively, and the motor train set depot is at the same place with station B. Station A sand station C are both the adjacent stations of station B, and the two stations are the turn-back stations for the motor train set, while station B is the departure station. Motor train sets depart from station B with undertaking the trains from station B to station A and from station B to station C, respectively, and come back to station B with undertaking the corresponding trains, and they may go to the motor train set depot for a fixed maintenance or staying. So the route composed of train T1 and train T2 is one-day route, and the route composed of train T3 and train T4 is two-day route.Figure 1
A diagrammatic sketch of route.It is relatively complex for the inspection and repair system of motor train set in China and the maintenance contents are divided into five grades. The grade one maintenance is generally called the routine maintenance, the grade two maintenance is generally called the special maintenance, and the grades three to five maintenance are generally called the advanced maintenance uniformly. While the accumulated mileage is to meet 4,000 kilometers or the accumulated time is to meet 48 hours after the last routine maintenance, the motor train set has to go back to the depot for the routine maintenance again. Compared with the other two kinds of maintenance, the maintenance period of the routine maintenance is much shorter and it occurs generally at night, so it is of high maintenance frequency. On the contrary, the advanced maintenance has a longer maintenance cycle and the time spent on the maintenance is comparatively longer as well. At present, the total accumulated mileage of most motor train set is not to meet the advanced maintenance period. Particularly, the special maintenance has a few maintenance items (or being called maintenance packet), such as I2 maintenance, M1 maintenance, flaw detection of hollow axle, and traction engine greasing. Besides, each maintenance item of the special maintenance ranges a lot in the aspects of maintenance cycle (including mileage and time cycle) and maintenance time. Thus, the problem of special maintenance scheduling is much more complex than any other, and its quality has a deep effect on the operation efficiency and the maintenance cost of motor train set. Because of this, we focus on taking the special maintenance into consideration in this paper and research the optimization method for train set assignment and maintenance scheduling. In Figure2 we give an example of motor train set assignment and maintenance schedule with considering the special maintenance.Figure 2
An example of motor train set assignment and maintenance schedule.For the motor train set assignment and maintenance schedule shown in Figure2, the motor train set EMU1 undertakes route 1 on the first day and conducts maintenance item A on the second day and undertakes route 1 again on the third day. The motor train set EMU2 undertakes route 2 on the first two days and conducts maintenance item B on the third day. The motor train set EMU3 undertakes the route 2 during the period. The motor train set EMU4 is being in standby mode on the first day and undertakes the route 1 and route 2, respectively, on the second day and the third day.


## 4. Mathematical Optimization Model

### 4.1. Basic Assumptions for Modelling

Assumption 1.
We set the “day” as the smallest unit of time in the scheduling process. If a motor train set is arranged to conduct more than one maintenance item on a certain day, we select the longest maintenance time of the arranged maintenance items as the maintenance time.Assumption 2.
We assume that the maintenance time of a sixteen-marshalling motor train set is equal to that of an eight-marshalling motor train set with the same type for any maintenance items. In practice, this can be achieved by sending two maintenance groups for the sixteen-marshalling motor train set while one group for eight-marshalling motor train set.Assumption 3.
Neglect the substitution among different types of motor train sets. In other words, a certain type of motor train set can only undertake the corresponding route.Assumption 4.
Various information including initial state, maintenance records, routes, and maintenance items are already known.


### 4.2. Parameters and Variables Definition

(1) Sets Notation. It is defined that D
=
t
∣
t
=
1,2
,
…
,
N
D is the set of dates for scheduling and N
D is the number of days, t is the index of date, when t
=
0, and it represents the day before the planning cycle; E
=
e
∣
e
=
1,2
,
…
,
N
E is the set of motor train sets, N
E is the number of motor train sets, and e is the index of motor train set. P
=
p
∣
p
=
1,2
,
…
,
N
P is the set of maintenance items, N
P is the total number of maintenance item, and p is the index of maintenance item. Each maintenance item has a restriction of maintenance mileage cycle S
p (unit: kilometer) and maintenance time cycle T
p (unit: day). μ
p (unit: day) is the length of maintenance time for maintenance item p. R
=
r
∣
r
=
1,2
,
…
,
N
R is the set of routes, where N
R and r are the number and index of the route, respectively. Each route r has two attributes, including running mileage s
r (unit: kilometer) and running time ε
r (unit: day). We define E
(
t
) as the set of motor train sets which are available to start undertaking a route on the tth day and, more specifically, they are the remaining ones except the motor train sets in operation or maintenance. The motor train set of E
(
t
) can be used for starting to undertake a route or conducting a maintenance item in advance or even being in standby state. E
(
t
) is generated during the scheduling process according to the initial state of the motor train set on that very day.(2) Parameters Notation. It is defined that δ
r
e is the matching parameter for motor train set e and route r. If the motor train set e matches well with the route r, the value of δ
r
e is 1; otherwise, the value of δ
r
e is 0. τ
p
e is the matching parameter for motor train set e and maintenance item p. If the motor train set e matches well with the maintenance item p, the value of τ
p
e is 1; otherwise, the value of τ
p
e is 0. C
p is the capability of maintenance item p for the motor train set depot, namely, the number of the motor train sets that can be arranged to conduct the maintenance item p on the same day. λ is the percentage that the accumulated mileage or time could exceed the maintenance cycle limit, and it is set to 10% generally in practice.(3) Variables Notation. It is defined that x
r
e
(
t
) is the decision variable which indicates whether the motor train set e starts to undertake the route r on the tth day or not. If the answer is yes, then let x
r
e
(
t
)
=
1; otherwise, let x
r
e
(
t
)
=
0. y
p
e
(
t
) be the decision variable which indicates whether the motor train set e starts to conduct the maintenance item p on the tth day or not. If the answer is yes, then let y
p
e
(
t
)
=
1; otherwise, let y
p
e
(
t
)
=
0. φ
r
e
(
t
) be the assistant decision variable which indicates whether the motor train set e undertakes the route r on the tth day or not. If the answer is yes, then let φ
r
e
(
t
)
=
1; otherwise, let φ
r
e
(
t
)
=
0. ϕ
p
e
(
t
) be the assistant variable which indicates whether the motor train set e conducts the maintenance item p on the tth day or not. If the answer is yes, then let ϕ
p
e
(
t
)
=
1; otherwise, let ϕ
p
e
(
t
)
=
0. α
e
(
t
) be the state decision variable which indicates whether the motor train set e is in operation on the tth day or not. If the answer is yes, then let α
e
(
t
)
=
1; otherwise, let α
e
(
t
)
=
0. β
e
(
t
) be the state decision variable which indicates whether the motor train set e is in maintenance on the tth day or not. If the answer is yes, then let β
e
(
t
)
=
1; otherwise, let β
e
(
t
)
=
0. γ
e
(
t
) be the state decision variable which indicates whether the motor train set e is in standby state on the tth day or not. If the answer is yes, then let γ
e
(
t
)
=
1; otherwise, let γ
e
(
t
)
=
0.The variablel
p
e
(
t
) (unit: kilometer) is the accumulated mileage of the motor train set e until the tth day after the latest maintenance of item p. The variable f
p
e
(
t
) (unit: day) is the accumulated time of motor train set e until the tth day after the latest maintenance of item p.


### 4.3. Optimization Objective

The main optimization objective of this paper is to make the accumulated mileage produced after the latest maintenance for a certain maintenance item of a motor train set be close to the maximal maintenance mileage cycle as much as possible, which could be helpful to decrease maintenance frequency during the scheduling cycle, which could reduce the maintenance cost, and to improve the operation efficiency. So in this paper, we aim at maximizing the accumulated mileage, which is described as the following formula:(1)
max
⁡
Z
1
=
∑
e
∈
E
∑
t
∈
D
∑
p
∈
P
l
p
e
t
-
1
y
p
e
t
.Because of the high procurement cost of motor train set, we aim at minimizing the number of motor train sets in operation in order to reduce the procurement cost, which is described as the following formula:(2)
min
⁡
Z
2
=
∑
e
∈
E
I
θ
e
.In formula (2), θ
e is the times motor train set e undertook a certain route during the scheduling cycle, which is described as formula (3). I
(
x
) is a common step function which is given as formula (4):(3)
θ
e
=
∑
r
∈
R
∑
t
∈
D
x
r
e
t
e
∈
E
,
(4)
I
x
=
1
,
x
>
0
0
,
x
≤
0
.In this paper, we transform the problem of multiobjective programming to a single-objective programming problem to simplify the process of solution. On the premise of no delayed maintenance, the maximization of accumulated mileage before each maintenance is equal to the minimization ofD-value between the maximal mileage limit of a certain maintenance item and the actual accumulated mileage. It can be described as formula (5), and “t
-
1” in this formula represents the day before the tth day:(5)
min
⁡
Z
3
=
∑
e
∈
E
∑
t
∈
D
∑
p
∈
P
S
p
1
+
λ
-
l
p
e
t
-
1
y
p
e
t
.On the basis of objectives described above, a conversion coefficientω is set for operating mileage and the number of motor train sets in operation. Thus, the number of motor train sets in operation can be transformed to the equivalent mileage, and formulas (3) and (5) can be integrated to the following formula:(6)
min
⁡
Z
=
∑
e
∈
E
∑
t
∈
D
∑
p
∈
P
S
p
1
+
λ
-
l
p
e
t
-
1
y
p
e
t
+
ω
∑
e
∈
E
I
θ
e
.The value of formula (5) increases with the days of the scheduling cycle, whereas function (3) has everything to do with the number of motor train sets. It is reasonable to introduce scheduling days in ω to keep the weight of these two formulas unaffected. Therefore, the value of ω can be calculated by formula (7). l
- is the average daily operating mileage of the motor train set:(7)
ω
=
l
-
×
N
D
.


### 4.4. Constraints Analysis

As the research contents in this paper are based on the practical problem existing in the motor train set depot in China, we determine the constraints according to the actual condition of the motor train set depot in China and analyze influence factors as comprehensive as possible.Only when the type and personnel quota of the motor train sete match well with the route r, the motor train set e could have the opportunity to undertake the route r. In other words, the motor train set and the route have to match with each other, which can be described as the following formula:(8)
x
r
e
t
≤
δ
r
e
e
∈
E
t
,
r
∈
R
,
t
∈
D
.Similarly, only when the motor train sete matches with the maintenance item p, the motor train set e could have the opportunity to conduct the maintenance item p. In other words, the motor train set and the maintenance item have to satisfy the matching relation which can be described as the following formula: (9)
y
p
e
t
≤
τ
p
e
e
∈
E
t
,
p
∈
P
,
t
∈
D
.For any motor train sete in the set E
(
t
), it can start to undertake just one route on the tth day at most, which can be described as the following formula:(10)
∑
r
∈
R
x
r
e
t
≤
1
e
∈
E
t
,
t
∈
D
.For any router in the set R, one and just one motor train set should be assigned to it on the tth day, which can be described as (11)
∑
e
∈
E
t
x
r
e
t
=
1
r
∈
R
,
t
∈
D
.The accumulated mileagel
p
e
(
t
) should not exceed the maximal mileage limit of the corresponding maintenance item, which can be described as (12)
l
p
e
t
≤
1
+
λ
S
p
e
∈
E
,
p
∈
P
,
t
∈
D
.The accumulated timef
p
e
(
t
) after the latest maintenance of each motor train set for a certain maintenance item should not exceed the maximal time cycle limit, which can be described as (13)
f
p
e
t
≤
1
+
λ
T
p
.The maintenance capacity limit of the motor train set depot should be taken into account in the maintenance arrangement of the motor train set to avoid centralized inspection and repair. Therefore, the following formula is obtained:(14)
∑
e
∈
E
ϕ
p
e
t
≤
C
p
p
∈
P
,
t
∈
D
.Each motor train set has its unique state, which is being in operation or in maintenance or in standby state, and it can be described as(15)
α
e
t
+
β
e
t
+
γ
e
t
=
1
e
∈
E
,
t
∈
D
.All the decision variables should satisfy the 0-1 integral constraint which can be described as(16)
x
r
e
t
,
y
p
e
t
,
φ
r
e
t
,
ϕ
p
e
t
,
α
e
t
,
β
e
t
,
γ
e
t
∈
0,1
.The accumulated mileagel
p
e
(
t
) and the accumulated time f
p
e
(
t
) can be calculated by formulas (17) and (18), respectively. If the motor train set e is not arranged to conduct the maintenance item p on the tth day, then the accumulated mileage l
p
e
(
t
) should be the sum of accumulated mileage on the day before l
p
e
(
t
-
1
) and the operating mileage of the route which is undertaken by the motor train set e on that very day. At the same time, the accumulated time f
p
e
(
t
) should increase by one day on the previous basis. On the contrary, if the motor train set e is arranged to conduct the maintenance item p on the tth day, then the corresponding accumulated mileage l
p
e
(
t
) and the accumulated time f
p
e
(
t
) should return to zero:(17)
l
p
e
t
=
0
,
if
ϕ
p
e
t
=
1
l
p
e
t
-
1
+
τ
p
e
∑
r
∈
R
x
r
e
t
s
r
,
e
l
s
e
e
∈
E
,
p
∈
P
,
t
∈
D
,
(18)
f
p
e
t
=
0
,
if
ϕ
p
e
t
=
1
f
p
e
t
-
1
+
1
×
τ
p
e
,
e
l
s
e
e
∈
E
,
p
∈
P
,
t
∈
D
.Decision variablesx
r
e
(
t
), y
p
e
(
t
), φ
r
e
(
t
), ϕ
p
e
(
t
), α
e
(
t
), β
e
(
t
), and γ
e
(
t
) are complementary to each other. If the motor train set e starts to undertake the route r, then it has to do so throughout the operating time cycle t
r. Otherwise, the value of φ
r
e
(
t
) should be zero. The relation can be described as (19)
∑
t
′
=
t
t
+
ε
r
-
1
φ
r
e
t
′
=
ε
r
,
i
f
x
r
e
t
=
1
φ
r
e
t
=
0
,
e
l
s
e
e
∈
E
t
,
r
∈
R
,
t
∈
D
.Similarly, if the motor train sete starts to conduct the maintenance item p on the tth day, then it should conduct the same maintenance item throughout the maintenance time t
p. Otherwise, the value of ϕ
p
e
(
t
) should be zero. The relation can be described as (20)
∑
t
′
=
t
t
+
μ
p
-
1
ϕ
p
e
t
′
=
μ
p
,
if
y
p
e
t
=
1
ϕ
p
e
t
=
0
,
e
l
s
e
e
∈
E
t
,
p
∈
P
,
t
∈
D
.The decision variablesα
e
(
t
) and β
e
(
t
) which decide whether the motor train set e is in maintenance or in operation on the tth day are influenced by the value of assistant variables φ
r
e
(
t
) and ϕ
p
e
(
t
), respectively. The relation can be described as (21)
α
e
t
=
∑
r
∈
R
φ
r
e
t
e
∈
E
,
t
∈
D
,
(22)
β
e
t
=
1
,
i
f
∑
p
∈
P
ϕ
p
e
t
≥
1
0
,
e
l
s
e
e
∈
E
,
t
∈
D
.Formula (21) indicates that if the motor train set is arranged to undertake a route on the tth day, it will be in operation state. Formula (22) indicates that if the motor train set e is arranged to conduct at least one maintenance item on the tth day, it will be in maintenance state.


### 4.5. Model Construction

On the basis of abovementioned analysis, a 0-1 integer programming model for motor train set assignment and maintenance collaboration scheduling is proposed in this paper, which is shown as follows:(23)
(M)  min
Z
=
∑
e
∈
E
∑
t
∈
D
∑
p
∈
P
S
p
1
+
λ
-
l
p
e
t
-
1
y
p
e
t
+
ω
∑
e
∈
E
I
θ
e
s.t.
8
~
16
.In this model, the relevant intermediate variables can be calculated by the corresponding formula on the basis of optimization objective and constraints above. Whent
=
0, the relevant variables represent the initial state of the motor train set. In other words, it indicates which state the motor train set was in, such as in operation or in maintenance or in standby state. Furthermore, it also shows the progress of undertaking a route or conducting a maintenance item. The model proposed in this paper is a nonlinear 0-1 integer programming model and cannot be directly solved by Lingo or any other business software. Thus, we design a heuristic solution strategy to address this problem in this paper.


## 4.1. Basic Assumptions for Modelling

Assumption 1.
We set the “day” as the smallest unit of time in the scheduling process. If a motor train set is arranged to conduct more than one maintenance item on a certain day, we select the longest maintenance time of the arranged maintenance items as the maintenance time.Assumption 2.
We assume that the maintenance time of a sixteen-marshalling motor train set is equal to that of an eight-marshalling motor train set with the same type for any maintenance items. In practice, this can be achieved by sending two maintenance groups for the sixteen-marshalling motor train set while one group for eight-marshalling motor train set.Assumption 3.
Neglect the substitution among different types of motor train sets. In other words, a certain type of motor train set can only undertake the corresponding route.Assumption 4.
Various information including initial state, maintenance records, routes, and maintenance items are already known.


## 4.2. Parameters and Variables Definition

(1) Sets Notation. It is defined that D
=
t
∣
t
=
1,2
,
…
,
N
D is the set of dates for scheduling and N
D is the number of days, t is the index of date, when t
=
0, and it represents the day before the planning cycle; E
=
e
∣
e
=
1,2
,
…
,
N
E is the set of motor train sets, N
E is the number of motor train sets, and e is the index of motor train set. P
=
p
∣
p
=
1,2
,
…
,
N
P is the set of maintenance items, N
P is the total number of maintenance item, and p is the index of maintenance item. Each maintenance item has a restriction of maintenance mileage cycle S
p (unit: kilometer) and maintenance time cycle T
p (unit: day). μ
p (unit: day) is the length of maintenance time for maintenance item p. R
=
r
∣
r
=
1,2
,
…
,
N
R is the set of routes, where N
R and r are the number and index of the route, respectively. Each route r has two attributes, including running mileage s
r (unit: kilometer) and running time ε
r (unit: day). We define E
(
t
) as the set of motor train sets which are available to start undertaking a route on the tth day and, more specifically, they are the remaining ones except the motor train sets in operation or maintenance. The motor train set of E
(
t
) can be used for starting to undertake a route or conducting a maintenance item in advance or even being in standby state. E
(
t
) is generated during the scheduling process according to the initial state of the motor train set on that very day.(2) Parameters Notation. It is defined that δ
r
e is the matching parameter for motor train set e and route r. If the motor train set e matches well with the route r, the value of δ
r
e is 1; otherwise, the value of δ
r
e is 0. τ
p
e is the matching parameter for motor train set e and maintenance item p. If the motor train set e matches well with the maintenance item p, the value of τ
p
e is 1; otherwise, the value of τ
p
e is 0. C
p is the capability of maintenance item p for the motor train set depot, namely, the number of the motor train sets that can be arranged to conduct the maintenance item p on the same day. λ is the percentage that the accumulated mileage or time could exceed the maintenance cycle limit, and it is set to 10% generally in practice.(3) Variables Notation. It is defined that x
r
e
(
t
) is the decision variable which indicates whether the motor train set e starts to undertake the route r on the tth day or not. If the answer is yes, then let x
r
e
(
t
)
=
1; otherwise, let x
r
e
(
t
)
=
0. y
p
e
(
t
) be the decision variable which indicates whether the motor train set e starts to conduct the maintenance item p on the tth day or not. If the answer is yes, then let y
p
e
(
t
)
=
1; otherwise, let y
p
e
(
t
)
=
0. φ
r
e
(
t
) be the assistant decision variable which indicates whether the motor train set e undertakes the route r on the tth day or not. If the answer is yes, then let φ
r
e
(
t
)
=
1; otherwise, let φ
r
e
(
t
)
=
0. ϕ
p
e
(
t
) be the assistant variable which indicates whether the motor train set e conducts the maintenance item p on the tth day or not. If the answer is yes, then let ϕ
p
e
(
t
)
=
1; otherwise, let ϕ
p
e
(
t
)
=
0. α
e
(
t
) be the state decision variable which indicates whether the motor train set e is in operation on the tth day or not. If the answer is yes, then let α
e
(
t
)
=
1; otherwise, let α
e
(
t
)
=
0. β
e
(
t
) be the state decision variable which indicates whether the motor train set e is in maintenance on the tth day or not. If the answer is yes, then let β
e
(
t
)
=
1; otherwise, let β
e
(
t
)
=
0. γ
e
(
t
) be the state decision variable which indicates whether the motor train set e is in standby state on the tth day or not. If the answer is yes, then let γ
e
(
t
)
=
1; otherwise, let γ
e
(
t
)
=
0.The variablel
p
e
(
t
) (unit: kilometer) is the accumulated mileage of the motor train set e until the tth day after the latest maintenance of item p. The variable f
p
e
(
t
) (unit: day) is the accumulated time of motor train set e until the tth day after the latest maintenance of item p.


## 4.3. Optimization Objective

The main optimization objective of this paper is to make the accumulated mileage produced after the latest maintenance for a certain maintenance item of a motor train set be close to the maximal maintenance mileage cycle as much as possible, which could be helpful to decrease maintenance frequency during the scheduling cycle, which could reduce the maintenance cost, and to improve the operation efficiency. So in this paper, we aim at maximizing the accumulated mileage, which is described as the following formula:(1)
max
⁡
Z
1
=
∑
e
∈
E
∑
t
∈
D
∑
p
∈
P
l
p
e
t
-
1
y
p
e
t
.Because of the high procurement cost of motor train set, we aim at minimizing the number of motor train sets in operation in order to reduce the procurement cost, which is described as the following formula:(2)
min
⁡
Z
2
=
∑
e
∈
E
I
θ
e
.In formula (2), θ
e is the times motor train set e undertook a certain route during the scheduling cycle, which is described as formula (3). I
(
x
) is a common step function which is given as formula (4):(3)
θ
e
=
∑
r
∈
R
∑
t
∈
D
x
r
e
t
e
∈
E
,
(4)
I
x
=
1
,
x
>
0
0
,
x
≤
0
.In this paper, we transform the problem of multiobjective programming to a single-objective programming problem to simplify the process of solution. On the premise of no delayed maintenance, the maximization of accumulated mileage before each maintenance is equal to the minimization ofD-value between the maximal mileage limit of a certain maintenance item and the actual accumulated mileage. It can be described as formula (5), and “t
-
1” in this formula represents the day before the tth day:(5)
min
⁡
Z
3
=
∑
e
∈
E
∑
t
∈
D
∑
p
∈
P
S
p
1
+
λ
-
l
p
e
t
-
1
y
p
e
t
.On the basis of objectives described above, a conversion coefficientω is set for operating mileage and the number of motor train sets in operation. Thus, the number of motor train sets in operation can be transformed to the equivalent mileage, and formulas (3) and (5) can be integrated to the following formula:(6)
min
⁡
Z
=
∑
e
∈
E
∑
t
∈
D
∑
p
∈
P
S
p
1
+
λ
-
l
p
e
t
-
1
y
p
e
t
+
ω
∑
e
∈
E
I
θ
e
.The value of formula (5) increases with the days of the scheduling cycle, whereas function (3) has everything to do with the number of motor train sets. It is reasonable to introduce scheduling days in ω to keep the weight of these two formulas unaffected. Therefore, the value of ω can be calculated by formula (7). l
- is the average daily operating mileage of the motor train set:(7)
ω
=
l
-
×
N
D
.


## 4.4. Constraints Analysis

As the research contents in this paper are based on the practical problem existing in the motor train set depot in China, we determine the constraints according to the actual condition of the motor train set depot in China and analyze influence factors as comprehensive as possible.Only when the type and personnel quota of the motor train sete match well with the route r, the motor train set e could have the opportunity to undertake the route r. In other words, the motor train set and the route have to match with each other, which can be described as the following formula:(8)
x
r
e
t
≤
δ
r
e
e
∈
E
t
,
r
∈
R
,
t
∈
D
.Similarly, only when the motor train sete matches with the maintenance item p, the motor train set e could have the opportunity to conduct the maintenance item p. In other words, the motor train set and the maintenance item have to satisfy the matching relation which can be described as the following formula: (9)
y
p
e
t
≤
τ
p
e
e
∈
E
t
,
p
∈
P
,
t
∈
D
.For any motor train sete in the set E
(
t
), it can start to undertake just one route on the tth day at most, which can be described as the following formula:(10)
∑
r
∈
R
x
r
e
t
≤
1
e
∈
E
t
,
t
∈
D
.For any router in the set R, one and just one motor train set should be assigned to it on the tth day, which can be described as (11)
∑
e
∈
E
t
x
r
e
t
=
1
r
∈
R
,
t
∈
D
.The accumulated mileagel
p
e
(
t
) should not exceed the maximal mileage limit of the corresponding maintenance item, which can be described as (12)
l
p
e
t
≤
1
+
λ
S
p
e
∈
E
,
p
∈
P
,
t
∈
D
.The accumulated timef
p
e
(
t
) after the latest maintenance of each motor train set for a certain maintenance item should not exceed the maximal time cycle limit, which can be described as (13)
f
p
e
t
≤
1
+
λ
T
p
.The maintenance capacity limit of the motor train set depot should be taken into account in the maintenance arrangement of the motor train set to avoid centralized inspection and repair. Therefore, the following formula is obtained:(14)
∑
e
∈
E
ϕ
p
e
t
≤
C
p
p
∈
P
,
t
∈
D
.Each motor train set has its unique state, which is being in operation or in maintenance or in standby state, and it can be described as(15)
α
e
t
+
β
e
t
+
γ
e
t
=
1
e
∈
E
,
t
∈
D
.All the decision variables should satisfy the 0-1 integral constraint which can be described as(16)
x
r
e
t
,
y
p
e
t
,
φ
r
e
t
,
ϕ
p
e
t
,
α
e
t
,
β
e
t
,
γ
e
t
∈
0,1
.The accumulated mileagel
p
e
(
t
) and the accumulated time f
p
e
(
t
) can be calculated by formulas (17) and (18), respectively. If the motor train set e is not arranged to conduct the maintenance item p on the tth day, then the accumulated mileage l
p
e
(
t
) should be the sum of accumulated mileage on the day before l
p
e
(
t
-
1
) and the operating mileage of the route which is undertaken by the motor train set e on that very day. At the same time, the accumulated time f
p
e
(
t
) should increase by one day on the previous basis. On the contrary, if the motor train set e is arranged to conduct the maintenance item p on the tth day, then the corresponding accumulated mileage l
p
e
(
t
) and the accumulated time f
p
e
(
t
) should return to zero:(17)
l
p
e
t
=
0
,
if
ϕ
p
e
t
=
1
l
p
e
t
-
1
+
τ
p
e
∑
r
∈
R
x
r
e
t
s
r
,
e
l
s
e
e
∈
E
,
p
∈
P
,
t
∈
D
,
(18)
f
p
e
t
=
0
,
if
ϕ
p
e
t
=
1
f
p
e
t
-
1
+
1
×
τ
p
e
,
e
l
s
e
e
∈
E
,
p
∈
P
,
t
∈
D
.Decision variablesx
r
e
(
t
), y
p
e
(
t
), φ
r
e
(
t
), ϕ
p
e
(
t
), α
e
(
t
), β
e
(
t
), and γ
e
(
t
) are complementary to each other. If the motor train set e starts to undertake the route r, then it has to do so throughout the operating time cycle t
r. Otherwise, the value of φ
r
e
(
t
) should be zero. The relation can be described as (19)
∑
t
′
=
t
t
+
ε
r
-
1
φ
r
e
t
′
=
ε
r
,
i
f
x
r
e
t
=
1
φ
r
e
t
=
0
,
e
l
s
e
e
∈
E
t
,
r
∈
R
,
t
∈
D
.Similarly, if the motor train sete starts to conduct the maintenance item p on the tth day, then it should conduct the same maintenance item throughout the maintenance time t
p. Otherwise, the value of ϕ
p
e
(
t
) should be zero. The relation can be described as (20)
∑
t
′
=
t
t
+
μ
p
-
1
ϕ
p
e
t
′
=
μ
p
,
if
y
p
e
t
=
1
ϕ
p
e
t
=
0
,
e
l
s
e
e
∈
E
t
,
p
∈
P
,
t
∈
D
.The decision variablesα
e
(
t
) and β
e
(
t
) which decide whether the motor train set e is in maintenance or in operation on the tth day are influenced by the value of assistant variables φ
r
e
(
t
) and ϕ
p
e
(
t
), respectively. The relation can be described as (21)
α
e
t
=
∑
r
∈
R
φ
r
e
t
e
∈
E
,
t
∈
D
,
(22)
β
e
t
=
1
,
i
f
∑
p
∈
P
ϕ
p
e
t
≥
1
0
,
e
l
s
e
e
∈
E
,
t
∈
D
.Formula (21) indicates that if the motor train set is arranged to undertake a route on the tth day, it will be in operation state. Formula (22) indicates that if the motor train set e is arranged to conduct at least one maintenance item on the tth day, it will be in maintenance state.


## 4.5. Model Construction

On the basis of abovementioned analysis, a 0-1 integer programming model for motor train set assignment and maintenance collaboration scheduling is proposed in this paper, which is shown as follows:(23)
(M)  min
Z
=
∑
e
∈
E
∑
t
∈
D
∑
p
∈
P
S
p
1
+
λ
-
l
p
e
t
-
1
y
p
e
t
+
ω
∑
e
∈
E
I
θ
e
s.t.
8
~
16
.In this model, the relevant intermediate variables can be calculated by the corresponding formula on the basis of optimization objective and constraints above. Whent
=
0, the relevant variables represent the initial state of the motor train set. In other words, it indicates which state the motor train set was in, such as in operation or in maintenance or in standby state. Furthermore, it also shows the progress of undertaking a route or conducting a maintenance item. The model proposed in this paper is a nonlinear 0-1 integer programming model and cannot be directly solved by Lingo or any other business software. Thus, we design a heuristic solution strategy to address this problem in this paper.


## 5. Solution Strategy

As the motor train set assignment and maintenance scheduling is an extremely complex work, and in order to provide reference to the dispatchers for their work, a fast solution method should be proposed for this problem. Particle swarm optimization has the advantage of fast convergence speed and high accuracy solution and it is easy to be applied in most areas, so we use the PSO in this study and design a solution strategy for the optimization model based on analysis and preprocess.


### 5.1. Application Principles of PSO

According to the fundamental principles of particle swarm optimization, and the practical problem of motor train set assignment and maintenance scheduling, the characteristic of the optimization model, we set that each particle represents a motor train set assignment schedule and the corresponding maintenance schedule is produced by the motor train set schedule. So we can conclude that the dimension of each particle isJ
=
N
E
×
N
D
×
N
R, and according to the definition of decision variable x
r
e
(
t
) of the model, the dimension j for a particle denotes that the motor train set e starts to undertake the route r on the tth day or not. On this base, we let parameter N
M represent the number of particle swarms, and m is the index of each particle. The motor train set assignment schedule which is represented by particle m is expressed as X
m
=
(
x
m
1
,
x
m
2
,
…
,
x
m
J
), and each particle m has a fitness function expressed as F
(
x
). During the process of iterative computation, each particle has a velocity vector expressed as V
m
=
(
v
m
1
,
v
m
2
,
…
,
v
m
J
) and has a historical optimal motor train set assignment schedule expressed as P
m
=
(
p
m
1
,
p
m
2
,
…
,
p
m
J
). Besides, there is a global optimal motor train set assignment schedule expressed as P
g
=
(
p
g
1
,
p
g
2
,
…
,
p
g
J
) for the whole particle swarm. The velocity update in the dimension j of particle m is computed according to (24)
v
m
j
k
+
1
=
ω
m
k
v
m
j
k
+
c
1
r
1
p
m
j
k
-
x
m
j
k
+
c
2
r
2
p
g
j
k
-
x
m
j
k
.The velocity of a particle is limited in the sectionv
m
i
n
,
v
m
a
x, and if the computation result is out of the range, we set the boundary value of the velocity section as actual velocity. In formula (24), k is the index of iteration times during the iteration process. The parameters r
1 and r
2 are the random number in the section 0,1, which could avoid falling into the local optimum and help to search the global optimal solution. The parameters c
1 and c
2 are called learning factor. On one hand, the iterative result could inherit the advantage of the historical optimal value of a particle through the parameter c
1, and on the other hand it could inherit the advantage of the global optimal value of the particle swarm through the parameter c
2. p
m
j
(
k
) and p
g
j
(
k
), respectively, represent the historical optimal value of a particle and the global optimal value of the particle swarm. ω
m
(
k
) is called the inertia weight, the value of which is generated by a function with the linear decreasing of the iteration times. The computational formula is shown as (25)
ω
m
k
=
ω
m
a
x
-
ω
m
a
x
-
ω
m
i
n
k
m
a
x
×
k
.In formula (26), ω
m
a
x represents the maximal inertia weight, and ω
m
i
n represents the minimal inertia weight, and the values are determined mainly by referring to the empirical results gotten in our computational experiments, as well as the existing relevant research results. The parameter k
m
a
x represents the maximal iteration times, the value of which also relies on the empirical results.In this paper, the decision variablex
r
e
(
t
) is a 0-1 integer variable, so the value of each particle x
m
j
(
k
+
1
) is also a 0-1 integer. Therefore, we adopt ambiguity function and random method to update the value of x
m
j
(
k
+
1
), and the computational formula is shown as (26)
x
m
j
k
+
1
=
1
,
ρ
<
S
i
g
m
o
i
d
v
m
j
k
+
1
0
,
o
t
h
e
r
s
.In formula (27), ρ is a random number in the section 0,1, and the S
i
g
m
o
i
d function is a common ambiguity function, which is shown as (27)
S
i
g
m
o
i
d
v
m
j
k
=
1
1
+
exp
⁡
-
v
m
j
k
.


### 5.2. Constraints Preprocess

In order to reduce the complexity and be easy to realize the optimization solution for the mathematical model, we propose to preprocess some of the constraints in this paper.Firstly, we remove the route constraint (11) of the model and set a corresponding penalty coefficient Q
1. If there is a route that is not assigned with a motor train set on a certain day, we add a value of Q
1 to the fitness function F
(
x
). For a calculated motor train set assignment schedule, we assume that the number of routes which are not assigned with motor train sets is N
1; then the total penalty value is N
1
Q
1.In the same way, we remove the maintenance capacity constraint (14) of the model and set a corresponding penalty coefficient Q
2. If the number of motor train sets arranged to conduct maintenance item p exceeds the maintenance capacity of the depot for the maintenance item p, we add a value of Q
2 to the fitness function F
(
x
) for each exceeding motor train set. According to the motor train set maintenance schedule, we assume that the extra number of motor train sets being to conduct maintenance item p is N
p
(
t
) on the tth day, then the total penalty value for exceeding maintenance capacity is ∑
t
∈
D
∑
p
∈
P
N
p
(
t
)
Q
2.Based on the preprocess for some complex constraints, we take the optimization objective value of the model as the primary component of the fitness function of a particle and add the total penalty value to the fitness function. So we can get the expression for the fitness function shown as the formula (28). We aim at minimizing the function and take it as the decision reference for iteration process:(28)
min
⁡
F
x
=
∑
e
∈
E
∑
t
∈
D
∑
p
∈
P
S
p
1
+
λ
-
l
p
e
t
-
1
y
p
e
t
+
ω
∑
e
∈
E
I
θ
e
+
N
1
Q
1
+
∑
t
∈
D
∑
p
∈
P
N
p
t
Q
2
.


### 5.3. The Key Solution Steps

On the bases of application principles analysis of PSO and constraints preprocess, we design the detailed solution process, which has four key steps as follows.(1) Generate the Available Motor Train Set
E
(
t
). For any particle m, on the tth day during the scheduling cycle, we generate the motor train set E according to the attachment motor train set of the depot at first. And then, we select the unavailable motor train set e in the set E which is to undertake a route or to conduct a maintenance item on the tth day and remove it from the set E. If the assistant decision variable α
e
(
t
)
=
1 or β
e
(
t
)
=
1, it indicates that the motor train set e is in a state of being in operation or in maintenance on the tth day, so it is an unavailable motor train set for a route, and it should be removed from the set E. Then circulate the motor train set in the set E, and until the motor train set E is traversed completely. So far the available motor train set E
(
t
) on the tth day is generated successfully.(2) Arrange Motor Train set to Conduct Maintenance. For any motor train set e in the available motor train set E
(
t
), we select the route r from the route set R, which is not only fit for the motor train set e but also has the shortest mileage. If the motor train set e is unable to undertake the route r during the maintenance cycle of each maintenance item, we remove it from the set E
(
t
), arrange it to conduct the corresponding maintenance item p, and let y
p
e
(
t
)
=
1. At the same time, we update the accumulated mileage l
p
e
(
t
) and time f
p
e
(
t
). We repeat this process until each motor train set in the set E
(
t
) is traversed completely.(3) Arrange Motor Train set to Undertake Route. (a) We adopt the random strategy to assign a motor train set to a route during the process of generating initial solution. For a route r in the route set R, we select a motor train set e from the set E
(
t
) randomly and determine whether it is able to undertake the route r or not by the motor train set type and maintenance cycle limit and so forth. If the motor train set e is able to undertake the route r, we let x
r
e
(
t
)
=
1 and remove it from the set E
(
t
) and update the accumulated mileage l
p
e
(
t
) and time f
p
e
(
t
). On the contrary, if the motor train set e is unable to undertake the route r, we continue to select another motor train set from the set E
(
t
) randomly and repeat this process. If there is no more motor train set which is able to undertake the route r, we skip this route and continue to focus on the next route until all the routes in the route set R are traversed completely.(b) We adopt the particle swarm optimization to assign a motor train set to a route during the process of optimization iteration. For a router in the route set R, we select a motor train set e from the set E
(
t
) randomly. If the motor train set e is fit for the route r, then we determine whether it is to undertake the route r or not according to formula (26). If the motor train set is assigned to undertake the route r, we let x
r
e
(
t
)
=
1, remove it from the set E
(
t
), and update the accumulated mileage l
p
e
(
t
) and time f
p
e
(
t
). If the motor train set e is not fit for the route r, or it is not assigned to undertake the route according to the iteration update formula (26), we select another motor train set from the set E
(
t
) randomly and repeat this process. If there is not any motor train set which is assigned to undertake the route r by the particle swarm optimization, we continue to adopt the random strategy to assign a motor train set to the route r.(4) Arrange the Remaining Motor Train sets to Conduct a Maintenance Item in Advance or to Be in Standby Mode. After the process of steps (2) and (3), the motor train sets in the set E
(
t
) are remaining motor train sets, and we propose to arrange the remaining motor train sets in the set E
(
t
) to conduct a maintenance item or to be in standby mode by random strategy, which indicates the maintenance of motor train set in advance. If a motor train set is arranged to conduct maintenance, we propose to arrange it to conduct the maintenance item p of which the accumulated mileage or time is mostly close to the maintenance cycle limit and let y
p
e
(
t
)
=
1 and update the accumulated mileage l
p
e
(
t
) and time f
p
e
(
t
) at the same time. If the motor train set is arranged to be in standby mode, only the accumulated time f
p
e
(
t
) is to be updated.To summarize the four key steps above, we give a flow chart for the solution process of motor train set assignment and maintenance scheduling based on the particle swarm optimization. The flow chart is shown as Figure3.Figure 3
The flow chart for solution process.


## 5.1. Application Principles of PSO

According to the fundamental principles of particle swarm optimization, and the practical problem of motor train set assignment and maintenance scheduling, the characteristic of the optimization model, we set that each particle represents a motor train set assignment schedule and the corresponding maintenance schedule is produced by the motor train set schedule. So we can conclude that the dimension of each particle isJ
=
N
E
×
N
D
×
N
R, and according to the definition of decision variable x
r
e
(
t
) of the model, the dimension j for a particle denotes that the motor train set e starts to undertake the route r on the tth day or not. On this base, we let parameter N
M represent the number of particle swarms, and m is the index of each particle. The motor train set assignment schedule which is represented by particle m is expressed as X
m
=
(
x
m
1
,
x
m
2
,
…
,
x
m
J
), and each particle m has a fitness function expressed as F
(
x
). During the process of iterative computation, each particle has a velocity vector expressed as V
m
=
(
v
m
1
,
v
m
2
,
…
,
v
m
J
) and has a historical optimal motor train set assignment schedule expressed as P
m
=
(
p
m
1
,
p
m
2
,
…
,
p
m
J
). Besides, there is a global optimal motor train set assignment schedule expressed as P
g
=
(
p
g
1
,
p
g
2
,
…
,
p
g
J
) for the whole particle swarm. The velocity update in the dimension j of particle m is computed according to (24)
v
m
j
k
+
1
=
ω
m
k
v
m
j
k
+
c
1
r
1
p
m
j
k
-
x
m
j
k
+
c
2
r
2
p
g
j
k
-
x
m
j
k
.The velocity of a particle is limited in the sectionv
m
i
n
,
v
m
a
x, and if the computation result is out of the range, we set the boundary value of the velocity section as actual velocity. In formula (24), k is the index of iteration times during the iteration process. The parameters r
1 and r
2 are the random number in the section 0,1, which could avoid falling into the local optimum and help to search the global optimal solution. The parameters c
1 and c
2 are called learning factor. On one hand, the iterative result could inherit the advantage of the historical optimal value of a particle through the parameter c
1, and on the other hand it could inherit the advantage of the global optimal value of the particle swarm through the parameter c
2. p
m
j
(
k
) and p
g
j
(
k
), respectively, represent the historical optimal value of a particle and the global optimal value of the particle swarm. ω
m
(
k
) is called the inertia weight, the value of which is generated by a function with the linear decreasing of the iteration times. The computational formula is shown as (25)
ω
m
k
=
ω
m
a
x
-
ω
m
a
x
-
ω
m
i
n
k
m
a
x
×
k
.In formula (26), ω
m
a
x represents the maximal inertia weight, and ω
m
i
n represents the minimal inertia weight, and the values are determined mainly by referring to the empirical results gotten in our computational experiments, as well as the existing relevant research results. The parameter k
m
a
x represents the maximal iteration times, the value of which also relies on the empirical results.In this paper, the decision variablex
r
e
(
t
) is a 0-1 integer variable, so the value of each particle x
m
j
(
k
+
1
) is also a 0-1 integer. Therefore, we adopt ambiguity function and random method to update the value of x
m
j
(
k
+
1
), and the computational formula is shown as (26)
x
m
j
k
+
1
=
1
,
ρ
<
S
i
g
m
o
i
d
v
m
j
k
+
1
0
,
o
t
h
e
r
s
.In formula (27), ρ is a random number in the section 0,1, and the S
i
g
m
o
i
d function is a common ambiguity function, which is shown as (27)
S
i
g
m
o
i
d
v
m
j
k
=
1
1
+
exp
⁡
-
v
m
j
k
.


## 5.2. Constraints Preprocess

In order to reduce the complexity and be easy to realize the optimization solution for the mathematical model, we propose to preprocess some of the constraints in this paper.Firstly, we remove the route constraint (11) of the model and set a corresponding penalty coefficient Q
1. If there is a route that is not assigned with a motor train set on a certain day, we add a value of Q
1 to the fitness function F
(
x
). For a calculated motor train set assignment schedule, we assume that the number of routes which are not assigned with motor train sets is N
1; then the total penalty value is N
1
Q
1.In the same way, we remove the maintenance capacity constraint (14) of the model and set a corresponding penalty coefficient Q
2. If the number of motor train sets arranged to conduct maintenance item p exceeds the maintenance capacity of the depot for the maintenance item p, we add a value of Q
2 to the fitness function F
(
x
) for each exceeding motor train set. According to the motor train set maintenance schedule, we assume that the extra number of motor train sets being to conduct maintenance item p is N
p
(
t
) on the tth day, then the total penalty value for exceeding maintenance capacity is ∑
t
∈
D
∑
p
∈
P
N
p
(
t
)
Q
2.Based on the preprocess for some complex constraints, we take the optimization objective value of the model as the primary component of the fitness function of a particle and add the total penalty value to the fitness function. So we can get the expression for the fitness function shown as the formula (28). We aim at minimizing the function and take it as the decision reference for iteration process:(28)
min
⁡
F
x
=
∑
e
∈
E
∑
t
∈
D
∑
p
∈
P
S
p
1
+
λ
-
l
p
e
t
-
1
y
p
e
t
+
ω
∑
e
∈
E
I
θ
e
+
N
1
Q
1
+
∑
t
∈
D
∑
p
∈
P
N
p
t
Q
2
.


## 5.3. The Key Solution Steps

On the bases of application principles analysis of PSO and constraints preprocess, we design the detailed solution process, which has four key steps as follows.(1) Generate the Available Motor Train Set
E
(
t
). For any particle m, on the tth day during the scheduling cycle, we generate the motor train set E according to the attachment motor train set of the depot at first. And then, we select the unavailable motor train set e in the set E which is to undertake a route or to conduct a maintenance item on the tth day and remove it from the set E. If the assistant decision variable α
e
(
t
)
=
1 or β
e
(
t
)
=
1, it indicates that the motor train set e is in a state of being in operation or in maintenance on the tth day, so it is an unavailable motor train set for a route, and it should be removed from the set E. Then circulate the motor train set in the set E, and until the motor train set E is traversed completely. So far the available motor train set E
(
t
) on the tth day is generated successfully.(2) Arrange Motor Train set to Conduct Maintenance. For any motor train set e in the available motor train set E
(
t
), we select the route r from the route set R, which is not only fit for the motor train set e but also has the shortest mileage. If the motor train set e is unable to undertake the route r during the maintenance cycle of each maintenance item, we remove it from the set E
(
t
), arrange it to conduct the corresponding maintenance item p, and let y
p
e
(
t
)
=
1. At the same time, we update the accumulated mileage l
p
e
(
t
) and time f
p
e
(
t
). We repeat this process until each motor train set in the set E
(
t
) is traversed completely.(3) Arrange Motor Train set to Undertake Route. (a) We adopt the random strategy to assign a motor train set to a route during the process of generating initial solution. For a route r in the route set R, we select a motor train set e from the set E
(
t
) randomly and determine whether it is able to undertake the route r or not by the motor train set type and maintenance cycle limit and so forth. If the motor train set e is able to undertake the route r, we let x
r
e
(
t
)
=
1 and remove it from the set E
(
t
) and update the accumulated mileage l
p
e
(
t
) and time f
p
e
(
t
). On the contrary, if the motor train set e is unable to undertake the route r, we continue to select another motor train set from the set E
(
t
) randomly and repeat this process. If there is no more motor train set which is able to undertake the route r, we skip this route and continue to focus on the next route until all the routes in the route set R are traversed completely.(b) We adopt the particle swarm optimization to assign a motor train set to a route during the process of optimization iteration. For a router in the route set R, we select a motor train set e from the set E
(
t
) randomly. If the motor train set e is fit for the route r, then we determine whether it is to undertake the route r or not according to formula (26). If the motor train set is assigned to undertake the route r, we let x
r
e
(
t
)
=
1, remove it from the set E
(
t
), and update the accumulated mileage l
p
e
(
t
) and time f
p
e
(
t
). If the motor train set e is not fit for the route r, or it is not assigned to undertake the route according to the iteration update formula (26), we select another motor train set from the set E
(
t
) randomly and repeat this process. If there is not any motor train set which is assigned to undertake the route r by the particle swarm optimization, we continue to adopt the random strategy to assign a motor train set to the route r.(4) Arrange the Remaining Motor Train sets to Conduct a Maintenance Item in Advance or to Be in Standby Mode. After the process of steps (2) and (3), the motor train sets in the set E
(
t
) are remaining motor train sets, and we propose to arrange the remaining motor train sets in the set E
(
t
) to conduct a maintenance item or to be in standby mode by random strategy, which indicates the maintenance of motor train set in advance. If a motor train set is arranged to conduct maintenance, we propose to arrange it to conduct the maintenance item p of which the accumulated mileage or time is mostly close to the maintenance cycle limit and let y
p
e
(
t
)
=
1 and update the accumulated mileage l
p
e
(
t
) and time f
p
e
(
t
) at the same time. If the motor train set is arranged to be in standby mode, only the accumulated time f
p
e
(
t
) is to be updated.To summarize the four key steps above, we give a flow chart for the solution process of motor train set assignment and maintenance scheduling based on the particle swarm optimization. The flow chart is shown as Figure3.Figure 3
The flow chart for solution process.


## 6. Case Study

In this paper, we design a case study on the background of Beijing south motor train set depot in China and apply the mathematical model and solution strategy to the practical problem of motor train set assignment and maintenance scheduling. According to partial actual data that we can get from the depot, we set that the scheduling cycle is from October 30, 2014, to November 5, 2014, which is called weekly schedule.We select 22 motor train sets with two types of CRH380BL and CRH380CL in this case study and select 10 routes according to the two types of motor train set. The routes which are suitable for the motor train set of CRH380BL type are No. R1~No. R6, and the other routes which are suitable for the motor train set of CRH380CL type are No. R7~No. R10. Routes R1, R5, R7, and R10 are two-day routes, and the others are one-day routes. The basic information of these routes is shown in Table1, which includes route name, suitable type, and route mileage and route time.Table 1
Basic information of routes.
Route name
Suitable type
Route mileage (km)
Route time (d)
R1
CRH380BL
4342
2
R2
CRH380BL
2670
1
R3
CRH380BL
2080
1
R4
CRH380BL
3216
1
R5
CRH380BL
4480
2
R6
CRH380BL
2902
1
R7
CRH380CL
4342
2
R8
CRH380CL
1994
1
R9
CRH380CL
1994
1
R10
CRH380CL
3616
2The basic information of the selected motor train sets is shown in Table2, which includes train set name, train set type, accumulated mileage, initial task, and task process. The accumulated mileage is the total mileage from the beginning of being in operation to the day before the scheduling cycle for a motor train set. The initial task is the state of a motor train set that it might undertake a route, conduct a maintenance item, or be in standby state. We assume that the motor train sets which did not undertake a route were all in standby state. The task process is calculated by the number of days already spent for this task. For the two-day route, it has two states of task process, including Day 1 and Day 2. In this case study, the day before the scheduling cycle is October 29, 2014. If a motor train set was in standby state, we set its task process as 0.Table 2
Basic information of motor train sets.
Train set name
Train set type
Accumulated mileage (km)
Initial task
Task process (d)
EMU1
CRH380BL
1895686
R5
1
EMU2
CRH380BL
1940792
R2
1
EMU3
CRH380BL
1868027
R5
2
EMU4
CRH380BL
1895082
Standby
0
EMU5
CRH380BL
1894356
Standby
0
EMU6
CRH380BL
1885061
R4
1
EMU7
CRH380BL
1854992
R3
1
EMU8
CRH380BL
1849781
Standby
0
EMU9
CRH380BL
1262735
Standby
0
EMU10
CRH380BL
1159710
R1
1
EMU11
CRH380BL
1216010
Standby
0
EMU12
CRH380BL
1171145
R6
1
EMU13
CRH380BL
1100308
R1
2
EMU14
CRH380CL
572107
R8
1
EMU15
CRH380CL
964404
R10
1
EMU16
CRH380CL
884219
R10
2
EMU17
CRH380CL
911571
R7
1
EMU18
CRH380CL
883828
Standby
0
EMU19
CRH380CL
763740
R7
2
EMU20
CRH380CL
793955
Standby
0
EMU21
CRH380CL
784786
Standby
0
EMU22
CRH380CL
830930
R9
1As the maintenance items of each type of motor train set are of great difference, we select a few typical maintenance items for motor train set of CRH380BL and CRH380CL. The basic information of the selected maintenance items is shown in Table3. It includes item name, train set type, mileage cycle, time cycle, and maintenance time. From Table 3 we can learn that each type of motor train set has seven maintenance items and the maintenance times of these maintenance items are all one day.Table 3
Basic information of maintenance items.
Item name
Train set type
Mileage cycle (km)
Time cycle (d)
Maintenance time (d)
I2
CRH380BL
20000
20
1
M1
CRH380BL
100000
90
1
M2
CRH380BL
400000
360
1
M3
CRH380BL
800000
720
1
Traction engine
CRH380BL
200000
180
1
Gearbox
CRH380BL
400000
360
1
Hollow axle
CRH380BL
100000
90
1
I2
CRH380CL
20000
10
1
M1
CRH380CL
100000
45
1
M2
CRH380CL
400000
180
1
M3
CRH380CL
800000
360
1
Traction engine
CRH380CL
200000
90
1
Gearbox
CRH380CL
400000
180
1
Hollow axle
CRH380CL
100000
45
1The maintenance record of motor train set lasts to October 29, 2015, which includes train set name, item name, date, and mileage. The date of maintenance is the day for the latest maintenance, and the mileage is the total accumulated mileage from the beginning of being in operation to the latest maintenance for the motor train set. As there are a lot of maintenance records, we just list the maintenance records of four motor train sets, for example, which are shown in Table4. According to the accumulated mileage in Tables 2 and 4, we can get the value of accumulated mileage by calculating theD-value between the mileage data of last maintenance and the day before the scheduling cycle.Table 4
Maintenance records of motor train sets.
Train set name
Item name
Date
Mileage (km)
CRH6202B
I2
2014.10.26
1891206
CRH6202B
M1
2014.09.09
1851620
CRH6202B
M2
2014.07.18
1743716
CRH6202B
M3
2013.09.06
1318710
CRH6202B
Traction engine
2014.10.24
1886726
CRH6202B
Gearbox
2014.07.18
1743716
CRH6202B
Hollow axle
2014.09.12
1851620
CRH6230B
I2
2014.10.26
1936310
CRH6230B
M1
2014.09.13
1839962
CRH6230B
M2
2014.07.23
1732774
CRH6230B
M3
2013.12.19
1317565
CRH6230B
Traction engine
2014.07.24
1732774
CRH6230B
Gearbox
2014.07.24
1732774
CRH6230B
Hollow axle
2014.09.13
1839962
CRH6301C
I2
2014.10.23
566125
CRH6301C
M1
2014.09.16
494039
CRH6301C
M2
2014.08.06
399489
CRH6301C
M3
2014.08.06
399489
CRH6301C
Traction engine
2014.08.06
399489
CRH6301C
Gearbox
2014.08.01
399489
CRH6301C
Hollow axle
2014.09.18
494039
CRH6303C
I2
2014.10.20
943358
CRH6303C
M1
2014.09.25
893546
CRH6303C
M2
2014.08.09
800586
CRH6303C
M3
2014.08.09
800586
CRH6303C
Traction engine
2014.08.07
800586
CRH6303C
Gearbox
2014.08.07
800586
CRH6303C
Hollow axle
2014.09.25
893546Other calculation parameters in this case study are set as follows: the days of planning cycleN
D
=
7, the maintenance capacity for each maintenance item C
p
=
3, the extended percentage λ
=
10
%, and the average daily mileage of motor train sets l
-
=
2000. In order to make sure that each route can be assigned with a motor train set and the maintenance capacity is not exceeded every day, the penalty coefficient is set to infinity. In this paper, we set Q
1
=
Q
2
=
1000000. According to the test results and experience, we set the population of particle swarm N
M
=
40, the maximal iteration times k
m
a
x
=
1000, the velocity section -
4,4, the inertia weight section 0.4,0.9, and the learning factor c
1
=
c
2
=
2.0.In this paper, we complete the program development by C++ programming language based on the visual studio 2010 programming platform. After 32 minutes of optimization calculation, a quasi-optimal motor train set assignment and maintenance schedule is generated, which is shown in Figure4.Figure 4
A quasi-optimal motor train set assignment and maintenance schedule.From the quasi-optimal motor train set assignment and maintenance schedule shown in Figure4, we can get a conclusion that there are 17 motor train sets in operation during the scheduling cycle, 10 of which are of type CRH380BL, and 7 motor train sets are of type CRH380CL. For the schedule, we arrange maintenance for 13 times in total for the motor train sets, including a 1-time M1 maintenance, a 1-time M3 maintenance, a 1-time traction engine maintenance, and a 10-time I2 maintenance. For example, the motor train set EMU9 conducts I2 maintenance on the 2nd day, the accumulated mileage of the motor train set up to this maintenance is 21452 kilometers relative to the latest I2 maintenance, and the accumulated time is 9 days. This maintenance arranged for the accumulated mileage is about to meet the maintenance mileage cycle limit of I2 maintenance item. For another motor train set EMU16, it is arranged to conduct I2 maintenance on the 4th day, the accumulated mileage of the motor train set up to this maintenance is 16018 kilometers relative to the latest I2 maintenance, and the accumulated time is 11 days. This maintenance arranged for the accumulated time is about to meet the maintenance time cycle limit of I2 maintenance item. It can be seen that because we take the maintenance time cycle into consideration, some motor train sets are arranged to conduct the corresponding maintenance item because the accumulated time is to meet the maximal time cycle limit of a certain maintenance item, which may lead to a huge waste of mileage before the maintenance. In practice, as the motor train set assignment and maintenance schedule is made by hand in general, the quality of the schedule mostly depends on the experience of scheduler, and it is impossible to get an optimization schedule. What is more, the motor train set sometimes may not be arranged to conduct the corresponding maintenance item while the accumulated mileage or accumulated time exceeds the maximal maintenance period limit. In this case study, through the optimization calculation, the accumulated mileage of the motor train set is as close to the maximal maintenance mileage cycle as possible and the operation efficiency of the motor train set is improved commendably. The premise of that is the accumulated time does not exceed the maintenance time period limit.


## 7. Conclusion

With the rapid development of high-speed railway, the problem of how to strengthen the management of motor train set operation and maintenance is more and more prominent. In this paper, on basis of practical situation of Beijing south motor train set depot in China, we focus on the special maintenance item of motor train set and research the optimization method for motor train set assignment and maintenance scheduling. After the analysis of the optimization objectives and constraints, the relationship between the related intermediate variables is determined, and then we propose a 0-1 integer programming model for optimizing the motor train set assignment and maintenance scheduling. According to the optimization objectives and constraints, we design a solution strategy for the mathematical model based on the fundamental principles of particle swarm optimization. In the end, we design a case study based on the basic data of Beijing south motor train set depot, and the optimization result indicates that we can get a satisfactory optimization result through the mathematical model and the solution strategy proposed in this paper. However, the practical situation is rather complex. For example, some special maintenance items are arranged at night together with the routine maintenance, so there is no need to arrange a full day for the maintenance and it could undertake a route in the daytime. What is more, there are situations which occur now and then. For example, a certain type of motor train set replaces another type of motor train set to undertake the route and motor train set depots invoke motor train sets against each other. Thus, it can be seen that the motor train set assignment and maintenance scheduling is affected by a lot of influence factors, and some related problems should be researched further.



---

*Source: 4540503-2016-03-15.xml*