# An Optimization Method for the Train Service Network Design Problem

Authors: Jie Xiao; Yi Xie; Haowei Yu; Hongying Yan
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

Effective railway freight transportation relies on a well-designed train service network. This paper investigates the train service network design problem at the tactical level for the Chinese railway system. It aims to determine the types of train services to be offered, how many trains of each service are to be dispatched per day (service frequency), and by which train services shipments are to be transported. An integer programming model is proposed to address this problem. The optimization model considers both through train services between nonadjacent yards, and two classes of service between two adjacent yards ( i.e., shuttle train services directly from one yard to its adjacent yard, and local train services that make at least one intermediate stop). The objective of the model is to optimize the transportation of all the shipments with minimal costs. The costs consist of accumulation costs, classification coststrain operation costs, and train travel costs. The NP-hard nature of the problem prevents an exact solution algorithm from finding the optimal solution within a reasonable time, even for small-scale cases. Therefore, an improved genetic algorithm is designed and employed here. To demonstrate the proposed model and the algorithm, a case study on a real-world sub-network in China is carried out. The computational results show that the proposed approach can obtain high-quality solutions with satisfactory speed. Moreover, comparative analysis on a case that assumes all the shuttle train services between any two adjacent yards to be provided without optimization reveals some interesting insights.


---

## Body

## 1. Introduction

Railway freight is an important logistical system supporting both global and regional economies. Millions of railcars are continuously moving every day and night. In 2018, around 2.6 trillion ton-km of goods were transported on the Chinese railway network, which comprises 131,000 kilometers of operating mileage [1]. The demand for transportation is growing more rapidly than infrastructure investment and construction, thus motivating the optimization of current railway operations.A physical railway network consists of terminals and links with restricted capacity. A freight shipment is defined as being between terminals. A common method of planning railway transportation is first to arrange direct services between high-demand or high-priority origin–destination (O–D) pairs. Scheduled train services are then dispatched hauling the high-value shipments. The remaining shipments undergo consolidation operations. At the appropriate yard, shipments with different final destinations are assembled into blocks, each of which is an arbitrary unit to be considered. The blocks are eventually attached to a train, and may be transferred from one train to another. When a block arrives at its destination, it is separated from the train, and its cars are sorted. Generally, this type of railway operation consists of the following sub-problems: the blocking problem, the block-to-train problem, and the train routing and scheduling problem. The blocking problem is the foremost sub-problem; its aim is to determine the overall blocks to be built at each yard and the specific shipments that should be placed into block to reduce the amount of intermediate handling as they travel from their origins to their respective destinations. Once a shipment is placed in a block, it will not be reclassified until it reaches that block’s destination. After a blocking policy is developed, the next step is to identify which trains should carry which blocks to their destinations. On the top of these two sub-problems, the train routing and scheduling problem is considered, which determines trains’ routes and time-tables so as to minimize the total costs of carrying the cars [2–5].There is rich literature on the blocking problem and block-to-train problem. Bodin et al. [6] established an arc-based mixed integer programming model that considered the capacity constraints at each yard to calculate the maximum number of blocks and the maximum volume of cars that can be handled. Barnhart et al. [7] formulated the railway blocking problem as a network design problem with maximum degree and flow constraints on the nodes; they proposed a heuristic Lagrangian relaxation approach to solve the problem. Ahuja et al. [8] proposed a model for the railway blocking problem using a very large-scale neighborhood search technique, as adopted by many railway companies. Jha et al. [9] formulated both arc-based and path-based time-space network models to solve the block-to-train problem at the operational level. Their models assigned a blocking plan for a given train schedule with respect to minimizing global transportation costs; they also developed greedy and Lagrangian relaxation heuristic algorithms to solve the model. Xiao et al. [10] also solved the block-to-train problem at the tactical level, which determines both the supplied services and the transportation strategy for each block established in the railway network. Yue et al. [11] introduced a model which can comprehensively describe the blocking policy and various combinations of multi-route O–D pairs in large scale railway networks, and proposed an improved ant colony algorithm to solve the problem. Lin et al. [12] formulated and solved the problem of train connection services in the Chinese network to determine the freight train services, and their frequency considering the differences between the freight rail networks in China and North America. However, they only considered single-block trains. Fügenschuh et al. [13] presented a linear mixed-integer model for the car routing problem arising from Deutsche Bahn’s operations. The model sought the most economical car routing, and considered train and car travel kilometers and the amount of used sorting tracks. For a railway network only using single-block trains, the blocking and train make-up problems are naturally combined.Given that the blocking, the block-to-train, and the train routing and scheduling sub-problems are interrelated, some researchers have considered several of the issues as an integrated optimization problem. Zhu et al. [14] presented a model integrating service selection and scheduling, car classification, and blocking based on a cyclic three-layer space-time network. Crainic et al. [15] presented a general optimization model that considered the interactions between routing freight traffic, scheduling train services, and allocating classification work on a rail network. Gorman [16] developed a heuristic approach based on the genetic algorithm and Tabu search to plan the freight railway operation by integrating train scheduling and demand-flow problems. Kwona et al. [17] developed an algorithm to improve a given blocking plan and block-to-train assignment, formulated the problem as a linear multi-commodity flow problem, and used the column generation technique to solve it. Keaton [18] formulated train operating problem as a mixed integer programming model to determine which pairs of terminals are to be provided with direct train connections and the frequencies of service. The objective was to minimize the sum of the costs of the train, car time, and classification yard, while not exceeding limits on train size and yard volumes.The voluminous literature on the blocking and block-to-train problems focuses mainly on the railway networks of North America and Europe, which are significantly different to that of China. Specifically, the railway operation is supervised by the China Railway Corporation, whose hierarchical management system is different to the parallel management by different companies in the North America. As the demand for passenger and freight transportation exceeds the capacity of the system, the emphasis in China is less on “scheduling”, and more on managing the train and line operations to operate freight trains between passenger traffic. Freight trains are arranged by waiting until enough cars have been collected that are traveling either to the destination yard or farther. Therefore, the models and algorithms applicable to North American and European systems cannot reflect the situation of the Chinese railway network, and the methods proposed in the literature cannot be applied directly in this study. The literature on the Chinese railway network (e.g., Lin et al. [12]) generally assumes that all the shuttle train services between any two adjacent yards are provided without optimization. This simplifies the problem and reduces the modeling complexity, but also leads to sub optimal solutions. Therefore, in order to find globally optimal solutions, it is necessary to relax the assumption and reformulate the mathematical model, which constitute the motivation the motive of this paper. Moreover, the train service network design problem is a typical combinatorial optimization problem and has an inherent NP-hard nature, making it difficult for an exact solution algorithm to find the optimal solution within a reasonable time. Therefore, it is of great significance to develop heuristic algorithms (e.g., evolutionary algorithms [19–23]) to obtain high-quality solutions quickly.This paper primarily addresses the problem of train service network design optimization at the tactical level. Its contributions are summarized as follows. (1) Two classes of train services between two adjacent yards are considered, which is different from the traditional method that assumes all the services between any two adjacent yards are shuttle services without optimization. (2) An optimization model for the problem of train service network design is proposed with respect to minimizing car-hour consumption across all the yards in the railway network. (3) An improved genetic algorithm is designed to solve the optimization model. (4) The proposed model and algorithm were tested in a realistically sized railway network. The computational results show the proposed approach can obtain reasonable-quality solutions with satisfactory speed. Moreover, a comparative analysis against a method with traditional assumptions reveals some interesting insights.The remainder of this paper is organized as follows. Section2 further describes the problem. An integer programming formulation is presented in Section 3. Section 4 presents a heuristic approach based on the improved genetic algorithm to solve the model. Section 5 tests the model and the approach to solving it. Finally, Section 6 summarizes the research.


## 2. Description of the Problem

There are various types of railway service including local train services, shuttle train services and through train services. These services can be used in different ways to transport a given shipment. The overall transportation process is outlined using the example in Figure1.Figure 1
A railway service network.Figure1 shows a simple line network consisting of four yards (i, k, d, j; red circles) and six railway logistics centers (s
i
k
1, s
i
k
2, s
k
d
1, s
k
d
2, s
k
d
3, s
d
j
1; green circles) located between pairs of adjacent yards. The green arcs (labeled 1–3) represent shuttle train services formed at one yard and broken up at the adjacent yard. The blue arcs (labeled 4–6) are through train services that are formed at one yard, pass through one or more yards and are finally broken up at a relatively distant yard. Both of these service types are collectively called direct train services. The red dotted arcs (labeled 7–9) denote local train services which pick-up and deliver shipments between yards and logistics centers and carry shipments among the logistics centers. The local and shuttle train services both run between two adjacent yards, the former makes intermediate stops while the latter goes directly from one yard to the other. The local train service naturally takes longer than the shuttle train service. We consider the methods of transporting shipments i
→
s
i
k
2, i
→
k, and i
→
j.The shipmenti
→
s
i
k
2 can only be shipped by the local train service Arc 7, which forms at yard i, stops at intermediate stations s
i
k
1 and s
i
k
2, and finally breaks up at yard k. There are two options for the shipment i
→
k: one is by Arc 1, a direct shuttle train service from i to k, the other is the local train service Arc 7, which stops both at the logistics centers s
i
k
1 and s
i
k
2 . These two intermediate stops make the travel time longer than that for direct shipping, despite both the trains following the same path. These train services can be represented as i
→
A
r
c
1
→
k and i
→
A
r
c
7
→
k, respectively. In summary, shipments between two adjacent yards can be carried either by a shuttle or local train service. The shipment i
→
j can be carried directly by the through train service Arc 4 from its origination to the destination without classification: i.e.,(1)
i
→
A
r
c
4
→
j,
Other strategies that are possible include (but are not limited to),
(2)
i
→
A
r
c
5
→
A
r
c
3
→
j,
(3)
i
→
A
r
c
5
→
A
r
c
9
→
j,
(4)
i
→
A
r
c
1
→
A
r
c
6
→
j,
(5)
i
→
A
r
c
7
→
A
r
c
6
→
j,
(6)
i
→
A
r
c
1
→
A
r
c
2
→
A
r
c
3
→
j,
(7)
i
→
A
r
c
7
→
A
r
c
8
→
A
r
c
9
→
j.Strategies (2), (3), (4), and (5) involve the shipment being classified once, while two classification operations are needed in strategies (6) and (7).The above analysis shows that different types of shipments have different transportation strategies, which involve different costs incurred from accumulation, reclassification, train operation, and train travel. Selecting the best shipping strategy for each shipment while minimizing the total costs is a combinatorial optimization problem.


## 3. Mathematical Model

This section proposes an integer programming formulation for this problem. The model aims to minimize the total costs while satisfying constraints on train and yard capacity. Two cost factors are considered: the economic costs of train operation and the time delay cost of cars at yards during the journey. The model determines the types and frequencies of train services to run between yards and which cars are to be consolidated into a given train service. The following assumptions facilitate the model formulation.The first assumption is that the shipment routing is given in advance. Each shipment is restricted to one transportation strategy (train service chain), and will not be split during the shipping. Each freight train is arranged when the collected cars reach its size. In general, local trains are unique in their size and operation costs compared with other types; their distinctive details are given in this paper. The positive shipment volumes among the logistics centers mean that local train services running between two adjacent yards must be provided without optimization.


### 3.1. Notations

The following notations are defined:V: Set of yards in the railway network. i
,
j
,
k
,
o, and
d refer to any yard belong to V.N
i
j: Set of yards along the path from yard i to j, including i, and j.A
i: Set of yards adjacent to yard i.S
i
j: Set of the intermediate logistics centers along the path from yard i to yard j, j
∈
A
i. s
i
j
n represents the n
th logistics center, s
i
j
n
∈
S
i
j.c
i: Average car accumulation parameter at yard i per day. The accumulation cost of a train is the product of the term c
i and the number of cars in the train (m
i
j, defined below). This parameter represents the influences of all factors other than the size of the train on the accumulation cost. It depends on the arrived car flow and the level of organizational work at the accumulation yard. Its detailed description and calculation can be found in the literature [24].γ
i: Utilization coefficient of classification capacity at yard i.t
k: Average extra time cost (in hours) per car at the yard k compared with when a train passes through the yard without classification.H
i: Number of shunting lines at yard i.M
k: Classification capacity in terms of the number of cars at yard k.a
i
j: The original shipment from yard i to yard j in terms of the number of cars.p
i
j
Z: Shipment originating from yard i and destined to the intermediate logistics centers located between yard i and yard j, j
∈
A
i.m
i
j: Average number of cars per train (excluding local trains).m
i
j
z: Average number of cars for local trains.n
i
j: Number of intermediate logistics centers along the path from yard i to yard j, j
∈
A
i.ε
s
i
j
n
,
s
i
j
n
+
1: Shipments from logistics center s
i
j
n to s
i
j
n
+
1, s
i
j
n
∈
S
i
j, 0
≤
n
≤
n
i
j.u
i
j: Fixed train operation costs of train i
→
j (excluding local trains).u
i
j
Z: Fixed operation cost of a local train i
→
j, j
∈
A
i.∂
i: Average accumulation time in hours for a local train at yard i without running a shuttle train.β
i: Average accumulation time in hours for a local train at yard i with running a shuttle train.t
i
j
Q: Average travel time in hours of a shuttle train i
→
j, j
∈
A
i.t
i
j
Z: Average travel time in hours of a local train i
→
j, j
∈
A
i.α: Coefficient of converting the train operation cost to the equivalent car-hour consumption.Three groups of decision variables are defined:x
i
j: Its value is 1, if the through train service i
→
j, j
∉
A
i is dispatched. Otherwise, it is zero.y
i
j: Its value is 1, if the shuttle train service i
→
j, j
∈
A
i is dispatched. Otherwise, it is zero.χ
i
j
k: Its value is 1, if the cars whose destination is yard j take the direct train service i
→
k at yard i. Otherwise, it is zero.The formulation also requires the following intermediate variables to be defined.f
i
j: Actual number of cars from yard i to j, including the original shipment demand a
i
j and cars from other yards to the yard j that are classified at yard i.g
i
j: Number of cars allocated to the train service i
→
j.F
k: Number of cars classified at yard k.τ
i
j
Z: Operational frequency of local train service i
→
j, j
∈
A
i.w
i
j: Number of cars from the yard i to j, j
∈
A
i.


### 3.2. Objective Function

The objective of the model is to minimize the total costs comprising those of accumulation, classification, train travel, and train operation. Cars traveling between two adjacent yards should be distinguished from those traveling among other yards. The final objective function is expressed as follows.(1)
min
Z
=
∑
i
∈
V
∑
j
∈
A
i
y
i
j
c
i
m
i
j
+
β
i
P
i
j
z
+
∑
i
∈
V
∑
j
∈
A
i
1
−
y
i
j
∂
i
w
i
j
+
p
i
j
Z
+
∑
i
∈
V
∑
j
∈
A
i
t
i
j
Q
y
i
j
w
i
j
+
t
i
j
Z
1
−
y
i
j
w
i
j
+
α
∑
i
∈
V
∑
j
∈
A
i
1
−
y
i
j
u
i
j
Z
τ
i
j
Z
+
α
∑
i
∈
V
∑
j
∈
A
i
y
i
j
u
i
j
w
i
j
m
i
j
+
∑
i
∈
V
∑
j
∉
A
i
x
i
j
c
i
m
i
j
+
∑
k
∈
V
F
k
t
k
+
α
∑
i
∈
V
∑
j
∉
A
i
x
i
j
u
i
j
g
i
j
m
i
j
,where∑
i
∈
V
∑
j
∈
A
i
y
i
j
c
i
m
i
j
+
β
i
P
i
j
z represents accumulation car-hour costs when a shuttle and a local train service are dispatched simultaneously between two adjacent yards; in this case, the shipments between two adjacent yards are transported by the shuttle train service. ∑
i
∈
V
∑
j
∈
A
i
1
−
y
i
j
∂
i
w
i
j
+
p
i
j
Z represents accumulation car-hour costs when only the local train service runs between two adjacent yards, and thus shipments between two adjacent yards are transported by the local train. In these two cases, the cars traveling between two adjacent yards take different types of train generating different travel costs, which can be calculated as ∑
i
∈
V
∑
j
∈
A
i
t
i
j
Q
y
i
j
w
i
j
+
t
i
j
Z
1
−
y
i
j
w
i
j. The operation costs of the local train are defined as α
∑
i
∈
V
∑
j
∈
A
i
1
−
y
i
j
u
i
j
Z
τ
i
j
Z, while those of shuttle train are α
∑
i
∈
V
∑
j
∈
A
i
y
i
j
u
i
j
w
i
j
/
m
i
j. For cars moving between two nonadjacent yards, the costs include those of accumulation ∑
i
∈
V
∑
j
∉
A
i
x
i
j
c
i
m
i
j, classification ∑
k
∈
V
F
k
τ
k, and train operation α
∑
i
∈
V
∑
j
∉
A
i
x
i
j
u
i
j
g
i
j
/
m
i
j.


### 3.3. Constraints

The formulation includes the following constraints:(1) The cars from yardi to yard j is either assigned to a through train service without classification or carried indirectly by a sequence of train services.
(2)
x
i
j
+
∑
k
∈
N
i
j
−
i
,
j
χ
i
j
k
=
1
∀
i
∈
V
,
j
∉
A
i
.
(2) Only if a train servicei
→
k is arranged, it is possible for cars going from yard i to yard j to be classified at the intermediate yard k.
(3)
x
i
k
−
χ
i
j
k
≥
0
∀
i
∈
V
,
∀
k
∈
N
i
j
−
i
,
j
.
(4)
y
i
k
−
χ
i
j
k
≥
0
∀
i
∈
V
,
∀
k
∈
A
i
.
(3) The number of cars classified at each yard should not exceed its classification capacity.
(5)
F
k
≤
γ
k
M
k
,
∀
k
∈
V
.
The value ofF
k is calculated as
(6)
F
k
=
∑
i
∈
V
∑
j
∈
V
f
i
j
χ
i
j
k
,
∀
k
∈
N
i
j
−
i
,
j
.
The value off
i
j is calculated as
(7)
f
i
j
=
a
i
j
+
∑
o
∈
V
f
o
j
χ
o
j
i
,
∀
i
,
j
∈
V
.
(4) The number of the occupied sorting tracks should be less than the number of the available tracks.
(8)
∑
j
∈
V
ϕ
g
i
j
≤
H
i
,
∀
i
∈
V
.
Hereϕ
g
i
j is a step function reflecting the utilization of the tracks. Assuming that one track can service a maximum of 200 cars, it is determined as follows:
(9)
ϕ
g
i
j
=
1
0
<
g
i
j
≤
200
2
200
<
g
i
j
≤
400
3
400
<
g
i
j
≤
600
…
…
∀
i
,
j
∈
V
,
whereg
i
j is calculated as
(10)
g
i
j
=
f
i
j
x
i
j
+
∑
d
∈
V
f
i
d
χ
i
d
j
∀
i
,
j
∈
V
.
(5) The operation frequency of the local train needs to meet the transportation demands.
(11)
m
i
j
Z
τ
i
j
Z
≥
ε
s
i
j
n
,
s
i
j
n
+
1
+
1
−
y
i
j
w
i
j
∀
i
∈
V
,
j
∈
A
i
,
s
i
j
n
∈
S
i
j
,
0
≤
n
≤
n
i
j
.
The value ofw
i
j is calculated as
(12)
w
i
j
=
f
i
j
y
i
j
+
∑
s
∈
V
f
i
s
χ
i
s
j
∀
i
∈
V
,
∀
j
∈
A
i
.
(6) The values of the decision variablesx
i
j, χ
i
j
k, and y
i
j can be either 0 or 1.
(13)
x
i
j
,
χ
i
j
k
,
y
i
j
∈
0
,
1
.


## 3.1. Notations

The following notations are defined:V: Set of yards in the railway network. i
,
j
,
k
,
o, and
d refer to any yard belong to V.N
i
j: Set of yards along the path from yard i to j, including i, and j.A
i: Set of yards adjacent to yard i.S
i
j: Set of the intermediate logistics centers along the path from yard i to yard j, j
∈
A
i. s
i
j
n represents the n
th logistics center, s
i
j
n
∈
S
i
j.c
i: Average car accumulation parameter at yard i per day. The accumulation cost of a train is the product of the term c
i and the number of cars in the train (m
i
j, defined below). This parameter represents the influences of all factors other than the size of the train on the accumulation cost. It depends on the arrived car flow and the level of organizational work at the accumulation yard. Its detailed description and calculation can be found in the literature [24].γ
i: Utilization coefficient of classification capacity at yard i.t
k: Average extra time cost (in hours) per car at the yard k compared with when a train passes through the yard without classification.H
i: Number of shunting lines at yard i.M
k: Classification capacity in terms of the number of cars at yard k.a
i
j: The original shipment from yard i to yard j in terms of the number of cars.p
i
j
Z: Shipment originating from yard i and destined to the intermediate logistics centers located between yard i and yard j, j
∈
A
i.m
i
j: Average number of cars per train (excluding local trains).m
i
j
z: Average number of cars for local trains.n
i
j: Number of intermediate logistics centers along the path from yard i to yard j, j
∈
A
i.ε
s
i
j
n
,
s
i
j
n
+
1: Shipments from logistics center s
i
j
n to s
i
j
n
+
1, s
i
j
n
∈
S
i
j, 0
≤
n
≤
n
i
j.u
i
j: Fixed train operation costs of train i
→
j (excluding local trains).u
i
j
Z: Fixed operation cost of a local train i
→
j, j
∈
A
i.∂
i: Average accumulation time in hours for a local train at yard i without running a shuttle train.β
i: Average accumulation time in hours for a local train at yard i with running a shuttle train.t
i
j
Q: Average travel time in hours of a shuttle train i
→
j, j
∈
A
i.t
i
j
Z: Average travel time in hours of a local train i
→
j, j
∈
A
i.α: Coefficient of converting the train operation cost to the equivalent car-hour consumption.Three groups of decision variables are defined:x
i
j: Its value is 1, if the through train service i
→
j, j
∉
A
i is dispatched. Otherwise, it is zero.y
i
j: Its value is 1, if the shuttle train service i
→
j, j
∈
A
i is dispatched. Otherwise, it is zero.χ
i
j
k: Its value is 1, if the cars whose destination is yard j take the direct train service i
→
k at yard i. Otherwise, it is zero.The formulation also requires the following intermediate variables to be defined.f
i
j: Actual number of cars from yard i to j, including the original shipment demand a
i
j and cars from other yards to the yard j that are classified at yard i.g
i
j: Number of cars allocated to the train service i
→
j.F
k: Number of cars classified at yard k.τ
i
j
Z: Operational frequency of local train service i
→
j, j
∈
A
i.w
i
j: Number of cars from the yard i to j, j
∈
A
i.


## 3.2. Objective Function

The objective of the model is to minimize the total costs comprising those of accumulation, classification, train travel, and train operation. Cars traveling between two adjacent yards should be distinguished from those traveling among other yards. The final objective function is expressed as follows.(1)
min
Z
=
∑
i
∈
V
∑
j
∈
A
i
y
i
j
c
i
m
i
j
+
β
i
P
i
j
z
+
∑
i
∈
V
∑
j
∈
A
i
1
−
y
i
j
∂
i
w
i
j
+
p
i
j
Z
+
∑
i
∈
V
∑
j
∈
A
i
t
i
j
Q
y
i
j
w
i
j
+
t
i
j
Z
1
−
y
i
j
w
i
j
+
α
∑
i
∈
V
∑
j
∈
A
i
1
−
y
i
j
u
i
j
Z
τ
i
j
Z
+
α
∑
i
∈
V
∑
j
∈
A
i
y
i
j
u
i
j
w
i
j
m
i
j
+
∑
i
∈
V
∑
j
∉
A
i
x
i
j
c
i
m
i
j
+
∑
k
∈
V
F
k
t
k
+
α
∑
i
∈
V
∑
j
∉
A
i
x
i
j
u
i
j
g
i
j
m
i
j
,where∑
i
∈
V
∑
j
∈
A
i
y
i
j
c
i
m
i
j
+
β
i
P
i
j
z represents accumulation car-hour costs when a shuttle and a local train service are dispatched simultaneously between two adjacent yards; in this case, the shipments between two adjacent yards are transported by the shuttle train service. ∑
i
∈
V
∑
j
∈
A
i
1
−
y
i
j
∂
i
w
i
j
+
p
i
j
Z represents accumulation car-hour costs when only the local train service runs between two adjacent yards, and thus shipments between two adjacent yards are transported by the local train. In these two cases, the cars traveling between two adjacent yards take different types of train generating different travel costs, which can be calculated as ∑
i
∈
V
∑
j
∈
A
i
t
i
j
Q
y
i
j
w
i
j
+
t
i
j
Z
1
−
y
i
j
w
i
j. The operation costs of the local train are defined as α
∑
i
∈
V
∑
j
∈
A
i
1
−
y
i
j
u
i
j
Z
τ
i
j
Z, while those of shuttle train are α
∑
i
∈
V
∑
j
∈
A
i
y
i
j
u
i
j
w
i
j
/
m
i
j. For cars moving between two nonadjacent yards, the costs include those of accumulation ∑
i
∈
V
∑
j
∉
A
i
x
i
j
c
i
m
i
j, classification ∑
k
∈
V
F
k
τ
k, and train operation α
∑
i
∈
V
∑
j
∉
A
i
x
i
j
u
i
j
g
i
j
/
m
i
j.


## 3.3. Constraints

The formulation includes the following constraints:(1) The cars from yardi to yard j is either assigned to a through train service without classification or carried indirectly by a sequence of train services.
(2)
x
i
j
+
∑
k
∈
N
i
j
−
i
,
j
χ
i
j
k
=
1
∀
i
∈
V
,
j
∉
A
i
.
(2) Only if a train servicei
→
k is arranged, it is possible for cars going from yard i to yard j to be classified at the intermediate yard k.
(3)
x
i
k
−
χ
i
j
k
≥
0
∀
i
∈
V
,
∀
k
∈
N
i
j
−
i
,
j
.
(4)
y
i
k
−
χ
i
j
k
≥
0
∀
i
∈
V
,
∀
k
∈
A
i
.
(3) The number of cars classified at each yard should not exceed its classification capacity.
(5)
F
k
≤
γ
k
M
k
,
∀
k
∈
V
.
The value ofF
k is calculated as
(6)
F
k
=
∑
i
∈
V
∑
j
∈
V
f
i
j
χ
i
j
k
,
∀
k
∈
N
i
j
−
i
,
j
.
The value off
i
j is calculated as
(7)
f
i
j
=
a
i
j
+
∑
o
∈
V
f
o
j
χ
o
j
i
,
∀
i
,
j
∈
V
.
(4) The number of the occupied sorting tracks should be less than the number of the available tracks.
(8)
∑
j
∈
V
ϕ
g
i
j
≤
H
i
,
∀
i
∈
V
.
Hereϕ
g
i
j is a step function reflecting the utilization of the tracks. Assuming that one track can service a maximum of 200 cars, it is determined as follows:
(9)
ϕ
g
i
j
=
1
0
<
g
i
j
≤
200
2
200
<
g
i
j
≤
400
3
400
<
g
i
j
≤
600
…
…
∀
i
,
j
∈
V
,
whereg
i
j is calculated as
(10)
g
i
j
=
f
i
j
x
i
j
+
∑
d
∈
V
f
i
d
χ
i
d
j
∀
i
,
j
∈
V
.
(5) The operation frequency of the local train needs to meet the transportation demands.
(11)
m
i
j
Z
τ
i
j
Z
≥
ε
s
i
j
n
,
s
i
j
n
+
1
+
1
−
y
i
j
w
i
j
∀
i
∈
V
,
j
∈
A
i
,
s
i
j
n
∈
S
i
j
,
0
≤
n
≤
n
i
j
.
The value ofw
i
j is calculated as
(12)
w
i
j
=
f
i
j
y
i
j
+
∑
s
∈
V
f
i
s
χ
i
s
j
∀
i
∈
V
,
∀
j
∈
A
i
.
(6) The values of the decision variablesx
i
j, χ
i
j
k, and y
i
j can be either 0 or 1.
(13)
x
i
j
,
χ
i
j
k
,
y
i
j
∈
0
,
1
.


## 4. Solution Approach

The optimization of the train service network design model can be regarded as a combinatorial optimization problem of the decision variables:x
i
j,y
i
j, and χ
i
j
k. The total number of decision variables increases exponentially with the number of yards in the network. This is a typical multi-variable NP-hard problem, which can be feasibly solved by heuristic methods such as genetic algorithm, particle swarm optimization, and simulated annealing algorithm. Most many-objective evolutionary algorithms use a one-by-one selection strategy to solve many-objective optimization problems because of their incapability to balance convergence and diversity in the high-dimensional objective space [25]. Considering that the first classification yard of cars between two yards is an integer value, it is convenient to implement encoding in a genetic algorithm, which is therefore applied here to solve the model. The genetic algorithm, first proposed by Holland [26], is an adaptive heuristic search algorithm based on the evolutionary ideas of natural selection and genetics. It is of high generality and robustness, and is especially suitable for solving combinatorial optimization problems, because the decision variables are easy to be represented during the encoding process. It has been used successfully to solve train service network design problems [27–30].The genetic algorithm includes the following elements: encoding, population size, initial population, fitness function, crossover, mutation, population regeneration, penalty function, and ending conditions. Figure2 shows the framework of using the genetic algorithm to solve constrained combinatorial optimization problems.Figure 2
The general framework of the genetic algorithm.The genetic algorithm is set up as follows to solve this specific optimization model.(1)
Encoding: We set the variable z
i
j
k to indicate the first classification yard of the cars from yard i to yard j as a gene to encode. The value range of each z
i
j
k is N
i
j
−
{
i
}. Note that the chosen value of the cars between two adjacent yards can be zero to indicate that only the local train service is dispatched. In a railway network with V yards, each z
i
j
k is set with a specific value and arranged in a fixed sequence, as shown in Figure 3, which forms a chromosome. Each chromosome is a possible solution for the model. Changing the value of each gene in the chromosome obtains different chromosomes that constitute the solution space of the problem.
(2)
Population size and initialization: The population size S has an important influence on the performance of the algorithm. Its preferred value usually depends on the size of the problem. The initial population is obtained by randomly choosing the first classification yard for each car flow.
(3)
Fitness function: The fitness function is the same as the objective function:(14)
F
T
h
=
Z
h
.
whereh represents a chromosome in the population.
(4)
Penalty function: The penalty function guarantees that the constraints (formulae 5 and 8) are satisfied.(15)
P
A
h
=
10000
F
T
h
F
i
≥
M
i
γ
i
o
r
∑
j
∈
V
ϕ
g
i
j
≥
H
i
∀
i
∈
V
0
.
(5)
New population generation: For each chromosome in POP(t), a selection probability is calculated as(16)
P
s
h
=
1
/
F
T
h
+
P
A
h
∑
h
=
1
S
1
/
F
T
h
+
P
A
h
.The new S chromosomes in NewPOP(t
+
1) are selected from the chromosomes in POP(t) by synthesizing rank selection and roulette wheel selection. The chromosomes initially in POP(t) are ranked from the largest to the smallest based on the values of P
s. The top n chromosomes are chosen directly. The remaining S
−
n chromosomes are chosen by roulette wheel selection.
(6)
Crossover: Two chromosomes in NewPOP(t
+
1) are randomly selected as the parent, and are recombined with probability P
c. This process is performed multiple times to generate multiple offspring; then the fittest offspring of each parent is selected. The offspring will inherit some characteristics of each parent. After the crossover operation, the newly generated chromosomes might not satisfy the constraints in formulae (3) and (4). Therefore, we use the following formula to evaluate the feasibility of the new chromosomes and adjust the value of the genes where necessary to guarantee that the chromosomes in CrossPOP(t
+
1) represent feasible solutions.(17)
z
i
j
k
=
z
i
d
k
∀
i
,
j
∈
V
i
f
z
i
j
k
=
d
and
z
i
d
k
≠
d
.
(7)
Dynamic mutation: Each gene in the chromosomes of CrossPOP (t
+
1) will be mutated with probability P
m that it is changed at each iteration. The initially chosen value for P
m is decreased by multiplying a decay factor ξ
m until it reaches a specified minimum value P
m. Similarly, after mutation formula (17) evaluates the feasibility of the newly generated chromosomes, and adjusts the values of the genes where necessary to guarantee that the chromosomes in MutPOP(t
+
1) represent feasible solutions. An operation that filters identical individuals retains only one in the population; the remaining repeated individuals are updated by the mutation operation.
(8)
Ending conditions: The calculation will terminate when t equals the defined maximum iteration number.


## 5. Model Testing

### 5.1. Data Preparation

This section tests the formulation and the proposed algorithm on a realistic railway sub-network in Northeast China, as shown in Figure4. The network contains 21 yards, numbered 1–21. Table 1 gives the original shipment demands a
i
j between any two yards. The fixed train operation costs u
i
j are listed in Table 2. The technical parameters of each yard are shown in Table 3. Note that the operation cost values here are not actual currency costs, but a relative value for comparison purposes. The value of α is defined as 3, the average train size m
i
j is 55, and the average local train size m
i
j
z is 40. The network diagram does not show logistics centers for clarity. The shipments from the yard to the logistics center p
i
j
Z and between two logistics centers ε
s
i
j
n
,
s
i
j
n
+
1 are listed in Appendix A. The Appendix also contains both the average accumulation time for local train at yard i with and without a shuttle train running ∂
i
j and β
i
j, the number of intermediate logistics centers between two adjacent yards n
i
j, the average travel time of a shuttle train t
i
j
Q, the average travel time of a local train t
i
j
Z and the fixed operation cost of a local train u
i
j
Z. The travel path of each shipment is defined in Appendix B. The row header indicates the origin yard, and the column header indicates the destination yard. The cell value is the yard sequence along the route: i.e., N
i
j. Note that real-world data are processed for some parameters. The dummy data used here are solely for testing the model and algorithm.Figure 3
Encoding of genetic algorithm.Figure 4
A 21-yard railway network.Table 1
Original shipments between two yardsa
i
j.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
1
—
41.3
39.1
24
26.9
40
9.7
18.9
27.1
34.9
14.7
35.1
6.3
9.3
12.7
25.4
22.7
10.3
17
31.1
37.4
2
11
—
33.1
27.9
34.6
33.1
28.4
20.6
9.9
9.1
23.3
32.1
16.4
33.7
13.9
15.1
16.4
7.7
37.4
15
26.7
3
15
37.7
—
30.1
34.1
17.3
27.3
28.1
11.3
18.7
13
27.9
10
22.3
7.9
9.1
15.3
12.7
32.7
36.9
7.7
4
16.9
7.1
13.9
—
9.9
16.9
24.6
16.6
35.3
38.6
16
19
6.1
11.6
17.7
38.7
38.3
40.9
13.7
34.3
8.1
5
38.6
34.6
39.6
14.3
—
10.4
33.1
13.4
10.9
20
30.6
30
29
35.6
24.9
25.9
23.6
40.6
31.7
12.7
9
6
22.4
16.9
27.4
9.3
26
—
33.3
9.6
23
15.6
10.9
36.4
30.6
29.6
15.1
25.6
27.6
39.6
40
31.4
11.1
7
16.6
36.1
41.4
11.3
10.7
18.1
—
25.6
37.7
36.6
8.1
8.1
36.3
23.4
23.6
21
23
22.1
32.9
5.9
25.1
8
29.7
17
41.3
36.6
37.3
27.1
21.9
—
9.1
22.1
41.1
23.6
10.4
27.6
33.3
39.7
14.9
32.3
26.6
38.4
39.4
9
14.1
32.4
25.7
34.9
30.1
25.4
11.3
36.9
—
11.6
36.6
8.9
8.4
20.7
11.6
23.1
17.6
31.1
36.3
25.7
31.6
10
22.9
39.3
24.3
29.3
21.4
20
31.4
10.9
32.6
—
12.3
8.3
26.6
7.7
35.4
28.6
29.7
12.1
37
38.1
21.6
11
33.4
25.7
24
37.7
31.3
11.7
6.6
35.3
38.3
13.9
—
9.1
41.1
28.4
11.4
6.6
25.4
37.9
24.9
36.3
24
12
41
39
28.3
34.7
17.1
25.3
11.6
19.4
39.4
39.7
33.3
—
31.9
9.3
28
10.6
28.9
12.9
21.7
20.3
14.6
13
13.1
35.6
40.6
40.1
32.4
14.1
26.7
7.4
23.4
16.3
33.7
34.6
—
30.3
13.9
15.3
15.3
21.1
18.4
12.7
24.9
14
27.7
33.9
39.7
23.6
24.9
11
8.6
16
17.3
8.3
16.4
18.1
32.7
—
8.6
23.9
21.4
29.6
19.4
36.3
6.7
15
34.9
36.4
24.4
21.4
36.1
21
31.4
25
38.9
30.1
12.1
22.7
38
40.4
—
38.4
38
9.1
6
27.4
20.3
16
7
26.7
7.6
10.7
31.4
31
30.9
32.7
8.1
39.3
34.7
9
8.7
11.1
13.9
—
27.6
37.7
38.9
31
26.3
17
13.4
30
8.1
25.3
39.3
21.4
26.1
22
22.3
14.3
31.3
10
26.9
17.4
40.1
36.7
—
27.6
33.7
25.9
25.7
18
16.1
12.4
15
7.3
41.3
17.3
20
40.9
35.6
17.4
15
32
21.6
13.7
27.4
32
12
—
32.6
23
26.1
19
37.9
31.4
26.7
9.3
17.9
36.7
26.9
35.6
37.1
22.7
13.9
8.9
21.1
35
8.6
24
25
7.7
—
30
9.6
20
10.3
39.9
26.6
38.6
28.4
24.9
25.1
26.1
14.6
9.7
17.4
26.9
28
17
29.7
29.1
34.9
19.6
40.4
—
13.9
21
13.7
35.9
30.9
35.3
40
25
9.4
22.7
37.3
15.3
30.9
19.4
15.3
14.4
35.3
10.4
19
28.7
9.9
28.1
—Table 2
Fixed train operation costu
i
j.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
1
—
305
323
303
295
321
295
323
325
348
345
363
348
318
345
347
348
359
345
345
345
2
295
—
309
347
323
295
323
345
356
356
359
323
325
312
363
323
298
356
363
363
363
3
323
311
—
312
330
323
318
333
323
325
348
345
363
348
318
345
363
348
318
318
318
4
318
295
332
—
326
318
323
295
318
315
345
325
312
363
323
345
323
348
323
323
323
5
323
323
310
323
—
353
345
323
325
348
345
363
348
318
345
348
359
298
345
345
348
6
345
318
359
345
321
—
318
318
323
323
313
345
298
317
323
325
345
363
323
323
298
7
312
323
378
312
295
332
—
305
318
345
325
312
363
323
345
363
324
323
345
345
363
8
363
345
312
363
323
356
315
—
206
356
356
359
323
224
356
312
313
359
356
356
323
9
356
312
295
356
318
340
295
297
—
327
348
312
359
345
229
345
323
345
229
229
359
10
345
363
323
340
323
295
323
315
358
—
325
348
345
363
348
318
345
324
348
348
345
11
356
356
318
295
345
298
317
295
315
317
—
311
324
377
359
325
348
313
359
359
324
12
348
345
323
323
312
363
323
323
348
323
310
—
313
348
348
312
359
171
348
348
313
13
359
356
345
318
363
356
345
317
323
345
291
291
—
281
325
348
345
363
348
318
345
14
356
348
312
323
356
340
312
313
356
356
359
323
314
—
307
359
198
359
312
359
359
15
348
359
363
345
345
295
363
315
231
327
348
312
345
307
—
305
224
356
345
300
356
16
384
356
356
312
356
323
356
348
359
323
348
312
359
345
326
—
345
348
295
295
348
17
325
348
345
363
348
318
345
323
356
356
359
323
377
347
377
348
—
359
301
290
303
18
345
384
356
356
359
323
356
356
356
359
323
316
348
345
348
312
359
—
308
318
345
19
316
325
348
345
356
345
348
327
348
312
348
312
359
325
348
345
300
305
—
296
358
20
329
345
359
356
348
312
359
295
329
345
359
295
348
312
359
295
295
323
320
—
313
21
327
316
356
348
384
363
356
310
327
316
356
310
384
363
356
310
310
359
301
343
—Table 3
Technical parameters of each yard.
Yard
c
i
t
k(hour)
H
i
M
k(car)
γ
i
1
13.8
4.8
12
1044
0.85
2
13.3
5.2
13
1004
0.85
3
14.2
4.7
14
1002
0.85
4
13.8
4.6
13
1062
0.85
5
14.1
4.1
15
1086
0.85
6
14.5
6.5
12
1078
0.85
7
14.2
3.5
15
1098
0.85
8
13.7
5.1
16
1024
0.85
9
13.3
6.4
15
1098
0.85
10
14.8
4.4
14
1044
0.85
11
13.9
5.8
12
1060
0.85
12
13.4
4.2
13
1032
0.85
13
14.5
4.3
15
1082
0.85
14
14.7
4.7
16
1006
0.85
15
14.5
4.1
14
1086
0.85
16
13.4
3.8
13
1062
0.85
17
13.4
5.4
13
1050
0.85
18
13.8
5.3
14
1006
0.85
19
13.9
3.4
15
1086
0.85
20
13.9
5.7
14
1094
0.85
21
14.7
4.1
15
1024
0.85


### 5.2. Computational Results and Algorithm Performance

The parameters of the proposed algorithm are set as follows: the population size is 10, the crossover probability is 0.5, the initial mutation probability is 0.1, the decay factor is 0.99, the minimum mutation probability is 0.01. We executed the algorithm 10 times and observed the variation of the results of each trail. Figure5 shows the optimization process of all 10 trails. The algorithm converges after 12,000 generations, and the solutions vary from 660,632 to 670,671 (a deviation of less than 2%). The solution time is 447 s. The minimum result of 660,632 is selected as the best solution. Table 4 shows the dispatched train services and frequencies. In total, 163 direct services, including 39 shuttle train services, are arranged. In addition, given that the arc in the network is directed, 62 local train services are arranged without optimization; they and their frequencies are listed in Table 5. Table 6 shows the value of z
i
j
k. The row header indicates the origin yard i and the column header indicates the destination yard j. The cell value is the first classification yard k of the cars going from i to j. Clearly, if the cell value k is equal to j, a train service from i to j is provided. Note that for a pair of adjacent yards i and j, if the cell value k is zero, only the local service is dispatched between them. Consider as an example the cars going from yard 2 to yard 9: they are firstly classified at yard 3, where they are merged with cars traveling from yard 3 to yard 9; these cars are then reclassified at yard 8, and merged with cars from that yard going also to yard 9; the final leg is the local service from yard 8 to yard 9. Table 7 shows the classified cars at each yard F
k and the utilized sorting tracks at each yard.Figure 5
10 Trials of the improved genetic algorithm.Table 4
Dispatched train service.
O–D
Freq
O–D
Freq
O–D
Freq
O–D
Freq
O–D
Freq
O–D
Freq
1–2
1.87
4–6
0.60
8–5
0.68
12–1
1.04
16–2
0.61
19–6
0.67
1–4
0.44
4–7
0.45
8–11
0.74
12–2
0.93
16–6
0.56
19–8
1.13
1–5
0.49
4–17
1.09
8–16
1.10
12–3
0.79
16–7
0.56
19–10
0.41
1–6
0.99
4–18
0.74
8–21
1.43
12–4
0.76
16–8
0.73
19–14
1.18
1–8
1.12
4–20
0.62
9–2
0.85
12–10
1.04
16–10
0.91
19–15
1.26
1–10
0.63
5–1
1.11
9–5
0.55
12–13
2.11
16–11
0.63
19–17
2.08
1–12
0.83
5–6
2.60
9–6
0.83
12–15
1.42
16–12
0.85
19–20
0.96
1–16
0.46
5–8
0.44
9–8
2.27
12–17
1.19
16–15
2.31
20–2
0.91
1–17
1.29
5–12
0.55
9–11
0.67
12–18
3.74
16–19
0.71
20–4
0.70
1–21
0.68
5–13
0.53
9–12
0.73
13–3
0.74
16–20
0.56
20–8
0.96
2–1
1.54
5–14
1.69
9–15
2.11
13–4
0.73
17–2
0.79
20–13
1.31
2–3
3.17
5–18
0.74
9–19
1.33
13–11
3.00
17–4
0.63
20–16
0.53
2–6
1.03
5–19
0.58
9–20
1.16
13–12
3.39
17–5
1.56
20–19
1.09
2–7
0.69
6–3
0.97
10–2
0.71
13–20
1.26
17–6
1.30
20–21
0.25
2–12
0.72
6–5
1.53
10–4
2.61
14–1
1.38
17–7
1.59
21–2
0.90
2–14
0.91
6–11
3.40
10–5
0.39
14–2
1.93
17–11
1.38
21–4
0.64
2–15
0.76
6–14
1.31
10–7
0.57
14–6
1.03
17–14
2.38
21–5
0.73
2–17
1.74
6–16
0.94
10–9
3.95
14–8
3.53
17–19
5.26
21–8
0.97
3–2
2.33
6–18
0.72
10–13
1.08
14–13
4.19
17–20
3.27
21–9
0.96
3–5
1.98
6–19
0.73
10–16
1.22
14–17
5.41
18–5
0.75
21–12
0.35
3–8
2.21
6–20
0.80
10–17
0.93
14–18
1.29
18–8
0.74
21–15
0.83
3–10
0.87
7–2
1.12
11–1
0.61
15–5
1.23
18–12
3.41
21–17
2.25
3–12
1.08
7–10
1.20
11–4
0.69
15–7
0.57
18–15
1.15
21–18
0.52
3–14
1.19
7–11
1.81
11–5
1.47
15–9
4.30
18–16
0.58
3–15
0.63
7–17
1.12
11–6
1.24
15–10
1.82
18–19
1.23
3–19
0.59
8–1
0.84
11-9
0.70
15–13
1.48
18–21
0.47
3–20
0.67
8–3
5.70
11–17
0.91
15–14
4.19
19–1
0.69
4–3
2.29
8–4
1.30
11–21
1.09
15–16
3.88
19–2
0.57Table 5
Operated local train services and frequencies.
Service
τ
i
j
z
Service
τ
i
j
z
Service
τ
i
j
z
Service
τ
i
j
z
Service
τ
i
j
z
1→2
1.98
6→5
2.23
10→4
2.18
14→13
1.53
18→12
2.10
1→4
1.85
6→7
3.89
10→9
2.15
14→15
5.22
18→19
2.15
2→1
1.95
6→11
2.23
11→6
2.23
14→17
1.85
19→17
2.05
2→3
2.20
7→6
3.33
11→7
3.75
15→9
1.93
19→18
3.50
3→2
2.23
7→8
3.96
11→12
3.72
15→14
1.98
19→20
1.85
3→4
4.24
7→11
2.23
11→13
4.45
15→16
1.90
20→17
3.00
3→5
2.23
8→3
2.23
12→11
3.56
15→17
3.81
20→19
2.10
3→8
1.85
8→7
3.48
12→13
1.68
16→15
1.75
20→21
1.70
4→1
3.20
8→9
5.43
12→18
1.48
17→14
2.13
21→17
2.18
4→3
2.10
8→14
3.26
13→11
2.23
17→15
3.72
21→20
2.75
4→10
3.17
9→8
1.98
13→12
1.78
17→19
2.38
5→3
2.94
9→10
3.53
13→14
3.92
17→20
2.28
5→6
2.18
9→15
1.68
14→8
2.23
17→21
6.44Table 6
Cars’ reclassification strategies.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
1
—
2
2
4
5
6
2
8
8
10
6
12
8
8
2
16
17
12
17
17
21
2
1
—
3
3
3
6
7
3
3
3
6
12
14
14
15
15
17
12
17
17
17
3
2
2
—
0
5
5
8
8
8
10
5
12
14
14
15
15
14
12
19
20
8
4
0
3
3
—
3
6
7
3
10
0
6
3
3
3
3
10
17
18
17
20
17
5
1
3
0
3
—
6
6
8
8
3
6
12
13
14
14
6
14
18
19
6
14
6
5
3
3
3
5
—
0
7
7
7
11
11
11
14
14
16
14
18
19
20
11
7
8
2
8
8
6
0
—
0
8
10
11
11
11
8
8
8
17
11
17
17
11
8
1
3
3
4
5
7
0
—
0
9
11
14
14
0
14
16
14
14
14
14
21
9
2
2
8
10
5
6
8
8
—
0
11
12
8
15
15
15
15
12
19
20
8
10
4
2
4
4
5
9
7
9
9
—
13
13
13
9
9
16
17
13
9
9
17
11
1
7
7
4
5
6
0
7
9
7
—
0
0
13
13
13
17
12
17
13
21
12
1
2
3
4
11
11
11
13
15
10
0
—
13
13
15
15
17
18
17
13
17
13
14
14
3
4
11
11
11
14
14
14
11
12
—
0
14
14
14
12
14
20
14
14
1
2
8
8
6
6
8
8
15
15
13
13
13
—
0
15
17
18
17
17
17
15
14
14
14
10
5
14
7
14
9
10
13
13
13
14
—
16
0
14
17
17
17
16
2
2
8
10
15
6
7
8
15
10
11
12
15
15
15
—
15
12
19
20
15
17
2
2
14
4
5
6
7
14
15
15
11
14
14
14
0
15
—
19
19
20
0
18
12
12
12
12
5
12
12
8
15
12
12
12
12
12
15
16
19
—
19
19
21
19
1
2
8
17
17
6
17
8
15
10
17
14
14
14
15
15
17
0
—
20
17
20
2
2
8
4
17
17
17
8
17
17
13
13
13
17
17
16
0
19
19
—
21
21
2
2
8
4
5
17
17
8
9
9
17
12
17
17
15
15
17
18
17
0
—Table 7
Yard workloads.
Yard
F
k
Classification load
Used track
% Track utilization
1
0
0%
10
83%
2
135
13%
8
62%
3
302.2
30%
9
64%
4
47.2
4%
7
54%
5
52.7
5%
9
60%
6
204.9
19%
9
75%
7
174.2
16%
7
47%
8
605
59%
12
75%
9
186.5
17%
10
67%
10
141
14%
9
64%
11
334.2
32%
10
83%
12
348.5
34%
11
85%
13
334.2
31%
7
47%
14
849.9
84%
10
63%
15
572.3
53%
11
79%
16
0
0%
10
77%
17
862.2
82%
11
85%
18
0
0%
7
50%
19
82.2
8%
9
60%
20
0
0%
8
57%
21
0
0%
9
60%The performance of the proposed improved genetic algorithm (IGA) is highlighted through comparison with two other state-of-the-art algorithms widely used in combinatorial optimization problems: the simulated annealing (SA) [31] and particle-swarm optimization (PSO) algorithms [32]. The SA and PSO algorithms were also run 10 times each in the same railway network, like the proposed IGA. The SA solutions (objective value) vary from 668,287 to 681,763. The variance is 13,580,513 and the average solution time is 501s. The PSO solutions vary from 661,896 to 673,411, with a variance of 13,288,476 and average solution time is 487s.Table8 presents the computational results of the three methods, IGA, SA, and PSO.Table 8
Computational results of IGA, SA, and PSO.
Algorithm
IGA
SA
PSO
Max obj. value
670671
681763
673411
Min obj. value
660632
668287
661896
Variance
8188599
13580513
13288476
Avg. obj. value
665076
679081
666762
Avg. solution time (s)
447
501
487Table8 shows that all three meta-heuristic methods find similar solutions for the same problem instance. Among them, the proposed IGA outperforms the others in terms of both solution quality and solution time. Therefore, it represents a good choice for solving the train service network design problem.


### 5.3. Comparison with the Traditional Assumption-Based Method

Consider another case having all the shuttle services between two adjacent yards provided without optimization which is a widely adopted assumption in existing literature, (see, for example [12]). The compositions of the objective function in each case are listed in Table 9. Compared with this situation, the optimization model proposed here reduces the total car-hour costs by 15,363 car-hours, and the total number of shuttle train services by 23, which decreases the accumulation costs by 11.2%. The associated increases of classification, train operation, and train travel costs increase by 4.7%, 0.5%, and 0.4%, respectively. This comparison suggests that assuming shuttle train services must be provided between any two adjacent yards beforehand tends to result in sub-optimal solutions in most cases.Table 9
Composition of the objective function of each case.
The optimized model
Comparative case
Reduced value
% Reduced
Total shuttle train service number
39
62
23
37.1%
Total direct train service number (including shuttle train service)
163
189
26
13.8%
Total local train service number
62
62
0
0.0%
Accumulation costs (car-hour)
145269
163635
18366
11.2%
Classification costs (car-hour)
18041
17235
−806
−4.7%
Train operation costs (car-hour)
459991
457930
−2061
−0.5%
Train travel costs (car-hour)
37331
37195
−136
−0.4%
Total costs (car-hour)
660632
675995
15363
2.3%


## 5.1. Data Preparation

This section tests the formulation and the proposed algorithm on a realistic railway sub-network in Northeast China, as shown in Figure4. The network contains 21 yards, numbered 1–21. Table 1 gives the original shipment demands a
i
j between any two yards. The fixed train operation costs u
i
j are listed in Table 2. The technical parameters of each yard are shown in Table 3. Note that the operation cost values here are not actual currency costs, but a relative value for comparison purposes. The value of α is defined as 3, the average train size m
i
j is 55, and the average local train size m
i
j
z is 40. The network diagram does not show logistics centers for clarity. The shipments from the yard to the logistics center p
i
j
Z and between two logistics centers ε
s
i
j
n
,
s
i
j
n
+
1 are listed in Appendix A. The Appendix also contains both the average accumulation time for local train at yard i with and without a shuttle train running ∂
i
j and β
i
j, the number of intermediate logistics centers between two adjacent yards n
i
j, the average travel time of a shuttle train t
i
j
Q, the average travel time of a local train t
i
j
Z and the fixed operation cost of a local train u
i
j
Z. The travel path of each shipment is defined in Appendix B. The row header indicates the origin yard, and the column header indicates the destination yard. The cell value is the yard sequence along the route: i.e., N
i
j. Note that real-world data are processed for some parameters. The dummy data used here are solely for testing the model and algorithm.Figure 3
Encoding of genetic algorithm.Figure 4
A 21-yard railway network.Table 1
Original shipments between two yardsa
i
j.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
1
—
41.3
39.1
24
26.9
40
9.7
18.9
27.1
34.9
14.7
35.1
6.3
9.3
12.7
25.4
22.7
10.3
17
31.1
37.4
2
11
—
33.1
27.9
34.6
33.1
28.4
20.6
9.9
9.1
23.3
32.1
16.4
33.7
13.9
15.1
16.4
7.7
37.4
15
26.7
3
15
37.7
—
30.1
34.1
17.3
27.3
28.1
11.3
18.7
13
27.9
10
22.3
7.9
9.1
15.3
12.7
32.7
36.9
7.7
4
16.9
7.1
13.9
—
9.9
16.9
24.6
16.6
35.3
38.6
16
19
6.1
11.6
17.7
38.7
38.3
40.9
13.7
34.3
8.1
5
38.6
34.6
39.6
14.3
—
10.4
33.1
13.4
10.9
20
30.6
30
29
35.6
24.9
25.9
23.6
40.6
31.7
12.7
9
6
22.4
16.9
27.4
9.3
26
—
33.3
9.6
23
15.6
10.9
36.4
30.6
29.6
15.1
25.6
27.6
39.6
40
31.4
11.1
7
16.6
36.1
41.4
11.3
10.7
18.1
—
25.6
37.7
36.6
8.1
8.1
36.3
23.4
23.6
21
23
22.1
32.9
5.9
25.1
8
29.7
17
41.3
36.6
37.3
27.1
21.9
—
9.1
22.1
41.1
23.6
10.4
27.6
33.3
39.7
14.9
32.3
26.6
38.4
39.4
9
14.1
32.4
25.7
34.9
30.1
25.4
11.3
36.9
—
11.6
36.6
8.9
8.4
20.7
11.6
23.1
17.6
31.1
36.3
25.7
31.6
10
22.9
39.3
24.3
29.3
21.4
20
31.4
10.9
32.6
—
12.3
8.3
26.6
7.7
35.4
28.6
29.7
12.1
37
38.1
21.6
11
33.4
25.7
24
37.7
31.3
11.7
6.6
35.3
38.3
13.9
—
9.1
41.1
28.4
11.4
6.6
25.4
37.9
24.9
36.3
24
12
41
39
28.3
34.7
17.1
25.3
11.6
19.4
39.4
39.7
33.3
—
31.9
9.3
28
10.6
28.9
12.9
21.7
20.3
14.6
13
13.1
35.6
40.6
40.1
32.4
14.1
26.7
7.4
23.4
16.3
33.7
34.6
—
30.3
13.9
15.3
15.3
21.1
18.4
12.7
24.9
14
27.7
33.9
39.7
23.6
24.9
11
8.6
16
17.3
8.3
16.4
18.1
32.7
—
8.6
23.9
21.4
29.6
19.4
36.3
6.7
15
34.9
36.4
24.4
21.4
36.1
21
31.4
25
38.9
30.1
12.1
22.7
38
40.4
—
38.4
38
9.1
6
27.4
20.3
16
7
26.7
7.6
10.7
31.4
31
30.9
32.7
8.1
39.3
34.7
9
8.7
11.1
13.9
—
27.6
37.7
38.9
31
26.3
17
13.4
30
8.1
25.3
39.3
21.4
26.1
22
22.3
14.3
31.3
10
26.9
17.4
40.1
36.7
—
27.6
33.7
25.9
25.7
18
16.1
12.4
15
7.3
41.3
17.3
20
40.9
35.6
17.4
15
32
21.6
13.7
27.4
32
12
—
32.6
23
26.1
19
37.9
31.4
26.7
9.3
17.9
36.7
26.9
35.6
37.1
22.7
13.9
8.9
21.1
35
8.6
24
25
7.7
—
30
9.6
20
10.3
39.9
26.6
38.6
28.4
24.9
25.1
26.1
14.6
9.7
17.4
26.9
28
17
29.7
29.1
34.9
19.6
40.4
—
13.9
21
13.7
35.9
30.9
35.3
40
25
9.4
22.7
37.3
15.3
30.9
19.4
15.3
14.4
35.3
10.4
19
28.7
9.9
28.1
—Table 2
Fixed train operation costu
i
j.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
1
—
305
323
303
295
321
295
323
325
348
345
363
348
318
345
347
348
359
345
345
345
2
295
—
309
347
323
295
323
345
356
356
359
323
325
312
363
323
298
356
363
363
363
3
323
311
—
312
330
323
318
333
323
325
348
345
363
348
318
345
363
348
318
318
318
4
318
295
332
—
326
318
323
295
318
315
345
325
312
363
323
345
323
348
323
323
323
5
323
323
310
323
—
353
345
323
325
348
345
363
348
318
345
348
359
298
345
345
348
6
345
318
359
345
321
—
318
318
323
323
313
345
298
317
323
325
345
363
323
323
298
7
312
323
378
312
295
332
—
305
318
345
325
312
363
323
345
363
324
323
345
345
363
8
363
345
312
363
323
356
315
—
206
356
356
359
323
224
356
312
313
359
356
356
323
9
356
312
295
356
318
340
295
297
—
327
348
312
359
345
229
345
323
345
229
229
359
10
345
363
323
340
323
295
323
315
358
—
325
348
345
363
348
318
345
324
348
348
345
11
356
356
318
295
345
298
317
295
315
317
—
311
324
377
359
325
348
313
359
359
324
12
348
345
323
323
312
363
323
323
348
323
310
—
313
348
348
312
359
171
348
348
313
13
359
356
345
318
363
356
345
317
323
345
291
291
—
281
325
348
345
363
348
318
345
14
356
348
312
323
356
340
312
313
356
356
359
323
314
—
307
359
198
359
312
359
359
15
348
359
363
345
345
295
363
315
231
327
348
312
345
307
—
305
224
356
345
300
356
16
384
356
356
312
356
323
356
348
359
323
348
312
359
345
326
—
345
348
295
295
348
17
325
348
345
363
348
318
345
323
356
356
359
323
377
347
377
348
—
359
301
290
303
18
345
384
356
356
359
323
356
356
356
359
323
316
348
345
348
312
359
—
308
318
345
19
316
325
348
345
356
345
348
327
348
312
348
312
359
325
348
345
300
305
—
296
358
20
329
345
359
356
348
312
359
295
329
345
359
295
348
312
359
295
295
323
320
—
313
21
327
316
356
348
384
363
356
310
327
316
356
310
384
363
356
310
310
359
301
343
—Table 3
Technical parameters of each yard.
Yard
c
i
t
k(hour)
H
i
M
k(car)
γ
i
1
13.8
4.8
12
1044
0.85
2
13.3
5.2
13
1004
0.85
3
14.2
4.7
14
1002
0.85
4
13.8
4.6
13
1062
0.85
5
14.1
4.1
15
1086
0.85
6
14.5
6.5
12
1078
0.85
7
14.2
3.5
15
1098
0.85
8
13.7
5.1
16
1024
0.85
9
13.3
6.4
15
1098
0.85
10
14.8
4.4
14
1044
0.85
11
13.9
5.8
12
1060
0.85
12
13.4
4.2
13
1032
0.85
13
14.5
4.3
15
1082
0.85
14
14.7
4.7
16
1006
0.85
15
14.5
4.1
14
1086
0.85
16
13.4
3.8
13
1062
0.85
17
13.4
5.4
13
1050
0.85
18
13.8
5.3
14
1006
0.85
19
13.9
3.4
15
1086
0.85
20
13.9
5.7
14
1094
0.85
21
14.7
4.1
15
1024
0.85


## 5.2. Computational Results and Algorithm Performance

The parameters of the proposed algorithm are set as follows: the population size is 10, the crossover probability is 0.5, the initial mutation probability is 0.1, the decay factor is 0.99, the minimum mutation probability is 0.01. We executed the algorithm 10 times and observed the variation of the results of each trail. Figure5 shows the optimization process of all 10 trails. The algorithm converges after 12,000 generations, and the solutions vary from 660,632 to 670,671 (a deviation of less than 2%). The solution time is 447 s. The minimum result of 660,632 is selected as the best solution. Table 4 shows the dispatched train services and frequencies. In total, 163 direct services, including 39 shuttle train services, are arranged. In addition, given that the arc in the network is directed, 62 local train services are arranged without optimization; they and their frequencies are listed in Table 5. Table 6 shows the value of z
i
j
k. The row header indicates the origin yard i and the column header indicates the destination yard j. The cell value is the first classification yard k of the cars going from i to j. Clearly, if the cell value k is equal to j, a train service from i to j is provided. Note that for a pair of adjacent yards i and j, if the cell value k is zero, only the local service is dispatched between them. Consider as an example the cars going from yard 2 to yard 9: they are firstly classified at yard 3, where they are merged with cars traveling from yard 3 to yard 9; these cars are then reclassified at yard 8, and merged with cars from that yard going also to yard 9; the final leg is the local service from yard 8 to yard 9. Table 7 shows the classified cars at each yard F
k and the utilized sorting tracks at each yard.Figure 5
10 Trials of the improved genetic algorithm.Table 4
Dispatched train service.
O–D
Freq
O–D
Freq
O–D
Freq
O–D
Freq
O–D
Freq
O–D
Freq
1–2
1.87
4–6
0.60
8–5
0.68
12–1
1.04
16–2
0.61
19–6
0.67
1–4
0.44
4–7
0.45
8–11
0.74
12–2
0.93
16–6
0.56
19–8
1.13
1–5
0.49
4–17
1.09
8–16
1.10
12–3
0.79
16–7
0.56
19–10
0.41
1–6
0.99
4–18
0.74
8–21
1.43
12–4
0.76
16–8
0.73
19–14
1.18
1–8
1.12
4–20
0.62
9–2
0.85
12–10
1.04
16–10
0.91
19–15
1.26
1–10
0.63
5–1
1.11
9–5
0.55
12–13
2.11
16–11
0.63
19–17
2.08
1–12
0.83
5–6
2.60
9–6
0.83
12–15
1.42
16–12
0.85
19–20
0.96
1–16
0.46
5–8
0.44
9–8
2.27
12–17
1.19
16–15
2.31
20–2
0.91
1–17
1.29
5–12
0.55
9–11
0.67
12–18
3.74
16–19
0.71
20–4
0.70
1–21
0.68
5–13
0.53
9–12
0.73
13–3
0.74
16–20
0.56
20–8
0.96
2–1
1.54
5–14
1.69
9–15
2.11
13–4
0.73
17–2
0.79
20–13
1.31
2–3
3.17
5–18
0.74
9–19
1.33
13–11
3.00
17–4
0.63
20–16
0.53
2–6
1.03
5–19
0.58
9–20
1.16
13–12
3.39
17–5
1.56
20–19
1.09
2–7
0.69
6–3
0.97
10–2
0.71
13–20
1.26
17–6
1.30
20–21
0.25
2–12
0.72
6–5
1.53
10–4
2.61
14–1
1.38
17–7
1.59
21–2
0.90
2–14
0.91
6–11
3.40
10–5
0.39
14–2
1.93
17–11
1.38
21–4
0.64
2–15
0.76
6–14
1.31
10–7
0.57
14–6
1.03
17–14
2.38
21–5
0.73
2–17
1.74
6–16
0.94
10–9
3.95
14–8
3.53
17–19
5.26
21–8
0.97
3–2
2.33
6–18
0.72
10–13
1.08
14–13
4.19
17–20
3.27
21–9
0.96
3–5
1.98
6–19
0.73
10–16
1.22
14–17
5.41
18–5
0.75
21–12
0.35
3–8
2.21
6–20
0.80
10–17
0.93
14–18
1.29
18–8
0.74
21–15
0.83
3–10
0.87
7–2
1.12
11–1
0.61
15–5
1.23
18–12
3.41
21–17
2.25
3–12
1.08
7–10
1.20
11–4
0.69
15–7
0.57
18–15
1.15
21–18
0.52
3–14
1.19
7–11
1.81
11–5
1.47
15–9
4.30
18–16
0.58
3–15
0.63
7–17
1.12
11–6
1.24
15–10
1.82
18–19
1.23
3–19
0.59
8–1
0.84
11-9
0.70
15–13
1.48
18–21
0.47
3–20
0.67
8–3
5.70
11–17
0.91
15–14
4.19
19–1
0.69
4–3
2.29
8–4
1.30
11–21
1.09
15–16
3.88
19–2
0.57Table 5
Operated local train services and frequencies.
Service
τ
i
j
z
Service
τ
i
j
z
Service
τ
i
j
z
Service
τ
i
j
z
Service
τ
i
j
z
1→2
1.98
6→5
2.23
10→4
2.18
14→13
1.53
18→12
2.10
1→4
1.85
6→7
3.89
10→9
2.15
14→15
5.22
18→19
2.15
2→1
1.95
6→11
2.23
11→6
2.23
14→17
1.85
19→17
2.05
2→3
2.20
7→6
3.33
11→7
3.75
15→9
1.93
19→18
3.50
3→2
2.23
7→8
3.96
11→12
3.72
15→14
1.98
19→20
1.85
3→4
4.24
7→11
2.23
11→13
4.45
15→16
1.90
20→17
3.00
3→5
2.23
8→3
2.23
12→11
3.56
15→17
3.81
20→19
2.10
3→8
1.85
8→7
3.48
12→13
1.68
16→15
1.75
20→21
1.70
4→1
3.20
8→9
5.43
12→18
1.48
17→14
2.13
21→17
2.18
4→3
2.10
8→14
3.26
13→11
2.23
17→15
3.72
21→20
2.75
4→10
3.17
9→8
1.98
13→12
1.78
17→19
2.38
5→3
2.94
9→10
3.53
13→14
3.92
17→20
2.28
5→6
2.18
9→15
1.68
14→8
2.23
17→21
6.44Table 6
Cars’ reclassification strategies.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
1
—
2
2
4
5
6
2
8
8
10
6
12
8
8
2
16
17
12
17
17
21
2
1
—
3
3
3
6
7
3
3
3
6
12
14
14
15
15
17
12
17
17
17
3
2
2
—
0
5
5
8
8
8
10
5
12
14
14
15
15
14
12
19
20
8
4
0
3
3
—
3
6
7
3
10
0
6
3
3
3
3
10
17
18
17
20
17
5
1
3
0
3
—
6
6
8
8
3
6
12
13
14
14
6
14
18
19
6
14
6
5
3
3
3
5
—
0
7
7
7
11
11
11
14
14
16
14
18
19
20
11
7
8
2
8
8
6
0
—
0
8
10
11
11
11
8
8
8
17
11
17
17
11
8
1
3
3
4
5
7
0
—
0
9
11
14
14
0
14
16
14
14
14
14
21
9
2
2
8
10
5
6
8
8
—
0
11
12
8
15
15
15
15
12
19
20
8
10
4
2
4
4
5
9
7
9
9
—
13
13
13
9
9
16
17
13
9
9
17
11
1
7
7
4
5
6
0
7
9
7
—
0
0
13
13
13
17
12
17
13
21
12
1
2
3
4
11
11
11
13
15
10
0
—
13
13
15
15
17
18
17
13
17
13
14
14
3
4
11
11
11
14
14
14
11
12
—
0
14
14
14
12
14
20
14
14
1
2
8
8
6
6
8
8
15
15
13
13
13
—
0
15
17
18
17
17
17
15
14
14
14
10
5
14
7
14
9
10
13
13
13
14
—
16
0
14
17
17
17
16
2
2
8
10
15
6
7
8
15
10
11
12
15
15
15
—
15
12
19
20
15
17
2
2
14
4
5
6
7
14
15
15
11
14
14
14
0
15
—
19
19
20
0
18
12
12
12
12
5
12
12
8
15
12
12
12
12
12
15
16
19
—
19
19
21
19
1
2
8
17
17
6
17
8
15
10
17
14
14
14
15
15
17
0
—
20
17
20
2
2
8
4
17
17
17
8
17
17
13
13
13
17
17
16
0
19
19
—
21
21
2
2
8
4
5
17
17
8
9
9
17
12
17
17
15
15
17
18
17
0
—Table 7
Yard workloads.
Yard
F
k
Classification load
Used track
% Track utilization
1
0
0%
10
83%
2
135
13%
8
62%
3
302.2
30%
9
64%
4
47.2
4%
7
54%
5
52.7
5%
9
60%
6
204.9
19%
9
75%
7
174.2
16%
7
47%
8
605
59%
12
75%
9
186.5
17%
10
67%
10
141
14%
9
64%
11
334.2
32%
10
83%
12
348.5
34%
11
85%
13
334.2
31%
7
47%
14
849.9
84%
10
63%
15
572.3
53%
11
79%
16
0
0%
10
77%
17
862.2
82%
11
85%
18
0
0%
7
50%
19
82.2
8%
9
60%
20
0
0%
8
57%
21
0
0%
9
60%The performance of the proposed improved genetic algorithm (IGA) is highlighted through comparison with two other state-of-the-art algorithms widely used in combinatorial optimization problems: the simulated annealing (SA) [31] and particle-swarm optimization (PSO) algorithms [32]. The SA and PSO algorithms were also run 10 times each in the same railway network, like the proposed IGA. The SA solutions (objective value) vary from 668,287 to 681,763. The variance is 13,580,513 and the average solution time is 501s. The PSO solutions vary from 661,896 to 673,411, with a variance of 13,288,476 and average solution time is 487s.Table8 presents the computational results of the three methods, IGA, SA, and PSO.Table 8
Computational results of IGA, SA, and PSO.
Algorithm
IGA
SA
PSO
Max obj. value
670671
681763
673411
Min obj. value
660632
668287
661896
Variance
8188599
13580513
13288476
Avg. obj. value
665076
679081
666762
Avg. solution time (s)
447
501
487Table8 shows that all three meta-heuristic methods find similar solutions for the same problem instance. Among them, the proposed IGA outperforms the others in terms of both solution quality and solution time. Therefore, it represents a good choice for solving the train service network design problem.


## 5.3. Comparison with the Traditional Assumption-Based Method

Consider another case having all the shuttle services between two adjacent yards provided without optimization which is a widely adopted assumption in existing literature, (see, for example [12]). The compositions of the objective function in each case are listed in Table 9. Compared with this situation, the optimization model proposed here reduces the total car-hour costs by 15,363 car-hours, and the total number of shuttle train services by 23, which decreases the accumulation costs by 11.2%. The associated increases of classification, train operation, and train travel costs increase by 4.7%, 0.5%, and 0.4%, respectively. This comparison suggests that assuming shuttle train services must be provided between any two adjacent yards beforehand tends to result in sub-optimal solutions in most cases.Table 9
Composition of the objective function of each case.
The optimized model
Comparative case
Reduced value
% Reduced
Total shuttle train service number
39
62
23
37.1%
Total direct train service number (including shuttle train service)
163
189
26
13.8%
Total local train service number
62
62
0
0.0%
Accumulation costs (car-hour)
145269
163635
18366
11.2%
Classification costs (car-hour)
18041
17235
−806
−4.7%
Train operation costs (car-hour)
459991
457930
−2061
−0.5%
Train travel costs (car-hour)
37331
37195
−136
−0.4%
Total costs (car-hour)
660632
675995
15363
2.3%


## 6. Conclusions

This paper proposes a model for the tactical optimization problem of train service network design. It aims to determine the type and frequency of each service provided among yards. The constraints are formulated in terms of classification capacity, number of tracks, and actual operational requirements. The objective function considers the train operation costs and the car-hour consumption due to accumulation, classification, and train travel. An improved genetic algorithm was developed to overcome the difficulties in solving the model, which includes an enormous number of decision variables and complicated constraints. It was tested in a real-world 21-yard Chinese railway sub-network. The approach produced relatively stable results within a reasonable computation time. The results show that, compared with the case that all shuttle train services between pairs of adjacent yards are dispatched, cost is saved by the optimization model, as it reduces the number of services and total number of dispatched trains. In particular, the decrease of the accumulation of car-hour consumption makes the largest contribution to the final saving of the total cost, although the costs of classification, train operation, and train travel slightly increase. Future research will focus on timetabling based on the train operation plans obtained here.



---

*Source: 9519267-2020-01-17.xml*