# Optimizing Schedules of Rail Train Circulations by Tabu Search Algorithm

Authors: Mingming Chen; Huimin Niu
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

This paper develops an integer programming model for the scheduling problem in train circulations on an intercity rail line. The model that aims to minimize the sum of interval time for any two consecutive tasks is proposed to characterize the train operation process. Two main constraints, namely, time-shift and equilibrium constraint, are considered to get the feasible and practical solution of train schedules. A heuristic procedure using tabu search algorithm is also designed to solve the model by introducing the penalty function and a neighborhood search method with the trip exchange and insert strategy. A computational experiment performed on test instances provided by two major stations on the Beijing–Tianjin Intercity Railway in China illustrates the proposed model and algorithm.


---

## Body

## 1. Introduction

Transit scheduling problem is a major area in operations research because of the complexity of problems that arise from various transit modes, such as airlines, railways, maritime, and urban transit. Vehicle scheduling and crew scheduling are two main problems that arise in this area. Generally, these two problems are considered separately, where the first is the vehicle scheduling problem and the second is the crew scheduling problem [1–3].Recently, most scholars have focused on the two problems simultaneously. In [4], a single depot case with a homogeneous fleet of vehicles was considered and an exact approach was proposed to solve the simultaneous vehicle and crew scheduling problem in urban mass transit systems. An integrated approach to solve a vehicle scheduling problem and a crew scheduling problem on a single bus route was presented in [5]. An integrated vehicle and crew scheduling problem was described using an integer linear programming formulation combining a multicommodity network flow model with a set partitioning/covering model in [6]. An approach was presented to solve the bus crew scheduling problem that considers early, day, and late duty modes with time-shift and work intensity constraints in [7]. The authors in [8] proposed an integrated vehicle-crew-roster model with days-off pattern, which aimed to simultaneously determine minimum cost vehicle and daily crew schedules.In the field of rail transit, train and crew scheduling problems are key steps in the rail operational process. The train scheduling problem involves assigning trains to a set of trips generated by a train timetable. The crew scheduling problem involves assigning crews to trains that operate at a given schedule. The authors in [9] proposed a phase-regular scheduling method and applied a regular train-departing interval and the same train length for each period under the period-dependent demand conditions. In [10], a binary integer programming model incorporated with passenger loading and departure events was built to optimize the passenger train timetable in a heavily congested urban rail corridor. The authors in [11] established an optimization model based on maximum passenger satisfaction for train operations at the junction station in passenger dedicated lines. The authors in [12] described research in progress that would determine the minimum circulation of trains needed to execute a given timetable with given bounds on demand and capacities.Train and crew scheduling is an NP hard problem. Generally, the difficulties stem from a large set of complex and conflicting restrictions that must be satisfied by any solution. Most of these restrictions are reflected in a sizable number of operational conditions that involve trips in daily train timetables, train numbers, train capacities, crew numbers, and certain constraints related to time-shift, equilibrium, and work intensity. The authors in [13] proposed an algorithm which was based on local optimality criteria in the event of a potential crossing conflict to solve the train scheduling problem. A model designed to optimize train schedules on single line rail corridors was described in [14]. In [15], a multiobjective optimization model was developed for the passenger train-scheduling problem on a railroad network which included single and multiple tracks, as well as multiple platforms with different train capacities. To minimize shortages in capacity during rush hours, the authors in [16] described a model that could be used to find an optimal allocation of train types and subtypes for lines.Meanwhile, various optimization models that relate to many aspects of train and crew schedules in railways are being studied extensively. The column generation approach is an effective algorithm for solving these problems. For example, the authors in [17] developed a column generation approach for a rail crew rescheduling problem. The authors in [18] presented a column generation approach based on the decomposition algorithm, which would achieve high-quality solutions at reasonable runtimes.In recent years, a number of studies have paid more attention to developing a heuristic algorithm for the train scheduling problem. An algorithm that combined a compact assign and a matrix, as well as an operational time strategy was proposed in [19]. The authors in [20] developed two-solution approaches based on a space-time network representation that would operate a predetermined set of train duties to satisfy the strict day-off requirement for crew in railways. On the premise of unfixed train used sections, the authors in [21] built an optimized train operation and maintenance planning model using an algorithm with a penalty function and a 3-opt neighborhood structure to solve the model. A particle swarm optimization algorithm with a local search heuristic was presented to solve the crew scheduling problem in [22].For an overview of the above papers, most studies on constructing the train scheduling model have been paid to the factors associated with train numbers, train capacities, interval time of trains, and so on. Moreover, interval time often includes night waiting time, which allows a train to conduct the trip tasks for the following day when the shortest layover time is less than the interval time of two consecutive trips. In fact, most trains run on the intercity line with high frequency, which is highly similar to bus transit. The origin and destination stations are generally equipped with train bases. In this paper, the factor of night waiting time is neglected, and the train scheduling problem is merely based on the train timetables in one day.This paper is organized as follows. In Section2, the rail train scheduling problem and an optimization model that minimizes the total interval time cost are described. A tabu search algorithm is presented in Section 3. In Section 4, a numerical example is provided to illustrate the application of the model and algorithm. The last section draws conclusions and discusses future research directions.


## 2. Rail Train Scheduling Model

### 2.1. Problem Description

This paper considers train scheduling on a bidirectional intercity railway line with several stations. The location and number of trains available in each station are known. Every day, the trains are arranged from the designated stations to perform a set of trips. For each trip, the departure and arrival times and locations, which are determined by train timetables, are also known. Figure1 shows a simple train timetable with three stations and 10 trips.Figure 1
A simple train timetable.Train scheduling aims to assign a number of timetabled trips to a set of trains with the objective of minimizing total train operation costs and satisfying a range of constraints, including labor union agreements, government regulations, and company policy. For clarity, the following assumptions have to be considered.(1)
Any two consecutive trips arranged for a train should have compatible terminals. Deadhead trips are not considered in this paper. Thus, the arrival location of a trip should be similar to the departure location of the next trip (e.g., Trips 1 and 6).(2)
Any two consecutive trips arranged for a train should be compatible in time. A lower bound, called layover time, is present when a train arrives at a terminus. During this time, the trains wait for passengers to alight, board, turnaround, and so on. If the interval time of two trips cannot exceed the shortest layover time, the two trips for any train is voided. If we assume that the shortest layover time is 15 minutes, then we can say that Trips 4 and 5 cannot be compatible.(3)
The train scheduling problem is solved as a daily problem in which every train schedule is assumed to be obtained from a daily train timetable. For two consecutive trips, the departure time of one trip should not be earlier than the arrival time of the next trip (e.g., Trips 1 and 2).(4)
The number of required trains cannot exceed the prescribed maximum number of trains.Figure2 illustrates train schedules corresponding to the data from the train timetable in Figure 1. Three trains are arranged for 12 trips. Each row corresponds to the trip tasks of a train. For instance, the trip tasks of the first train (no. 1) are in a chain with C-A, A-C, C-B, B-C, and C-A. The columns correspond to the trips in a timetable. Notably, the number of columns that correspond to different trains differs from one another. For any trip task of a particular train, the departure station of the first trip and the arrival station of the last trip are not necessarily the same.Figure 2
Illustration of train schedules.


### 2.2. Objective Function

The train is an important piece of equipment used in intercity railways, which is expensive to produce or purchase. To complete train timetables, the required number of trains should be as few as possible. Furthermore, the interval time of trains, a key factor in measuring their circulation efficiency, can be described as follows: a train runs in a section and reaches an intermediate station in one trip. It operates and waits at the station and then departs from the station for the following trip task. The interval time includes the operation time and waiting time at the station. When the train arrives and departs from the terminus, the interval time can be called the turn-back time. Therefore, the optimal objective of rail train scheduling is to determine the minimum number of trains required and ensure the minimum cost of interval time.As the sum of interval time and running time of trains is a multiple of the number of trains, and the running time of each train is a constant number, the objective of having the smallest number of trains is equivalent to the objective of having minimal cost in interval time. In this paper, the optimal objective is to minimize the total interval time, which can be formulated as follows:(1)min∑k=1m∑i=1n∑j=1ncij·yijk,
where m represents the number of trains required in a day, n represents the number of trips provided by a train timetable in a day and cij is the interval time between trip i and trip j. yijk is a binary 0-1 variable that indicates the status of trip i and trip j conducted by train k. yijk has two values: yijk=1 if trip j is the next trip after trip i conducted by train k, and yijk=0 otherwise.The interval time of any two trips in train timetables is significantly influenced by factors related to the trip, such as origin station, destination station, and arrival and departure time at the two stations. For any two trips, if the destination station of the former trip is different from the origin station of the latter trip, or if the interval time is less than the shortest layover timeT0, then the two trips cannot be arranged using the same train. Obviously, the two trips cannot satisfy the time-shift constraint. In this paper, the interval time can be set to an infinite positive number M. If the interval time of the two trips meets the time-shift constraint, then it can be calculated using the formula dj-ai. Therefore, interval time cij between trips i and j can be expressed as follows:
(2)cij={dj-ai,zi=sj,dj-ai≥T0,M,zi≠sjorzi=sj,dj-ai<T0,
where zi is the destination station of trip i, sj is the origin station of trip j, ai is the arrival time of trip i at destination station, and dj is the departure time of trip j at origin station.


### 2.3. Constraints

(1)
To ensure that each trip can be conducted using only one train, we formulate(3)∑k=1mxik=1,∀i.
(2)
The relationship between decision variablexik and auxiliary variable yijk can be formulated using the following equation:
(4)yijk=xik·xjk,∀k.
(3)
The two consecutive trips taken by the same train should satisfy the time-shift constraint, which means that the arrival time when the former trip ends at the destination station must be earlier than the departure time when the latter trip starts at the origin station. The minimum difference should be not less thanT0,
(5)I(dj-ai-T0)≥yijk,∀k,
where I(x) represents sign function, which is calculated using (6),
(6)I(x)={1,x≥0,0,x<0.
(4)
To ensure that the running mileage between different trains is equal, we have to make sure that the actual operation time between different trains does not vary significantly because of the constant speed of each train. The parameterGk, which represents the total operation time of train k, can be calculated using the following equation:
(7)Gk=∑i=1nxik(ai-di).
Therefore, we can calculate the maximum and minimum operation times of trains, and the difference should not exceed the maximum value of the operation time between any two trains T1,
(8)maxk,k′|Gk-Gk′|≤T1.
(5)
The decision variablexik is a 0-1 variable to indicate whether trip i is conducted by train k. xik has two values: xik=1 if trip i is conducted by train k, and xik=0 otherwise. Thus,
(9)xik∈{0,1},∀i,k.


## 2.1. Problem Description

This paper considers train scheduling on a bidirectional intercity railway line with several stations. The location and number of trains available in each station are known. Every day, the trains are arranged from the designated stations to perform a set of trips. For each trip, the departure and arrival times and locations, which are determined by train timetables, are also known. Figure1 shows a simple train timetable with three stations and 10 trips.Figure 1
A simple train timetable.Train scheduling aims to assign a number of timetabled trips to a set of trains with the objective of minimizing total train operation costs and satisfying a range of constraints, including labor union agreements, government regulations, and company policy. For clarity, the following assumptions have to be considered.(1)
Any two consecutive trips arranged for a train should have compatible terminals. Deadhead trips are not considered in this paper. Thus, the arrival location of a trip should be similar to the departure location of the next trip (e.g., Trips 1 and 6).(2)
Any two consecutive trips arranged for a train should be compatible in time. A lower bound, called layover time, is present when a train arrives at a terminus. During this time, the trains wait for passengers to alight, board, turnaround, and so on. If the interval time of two trips cannot exceed the shortest layover time, the two trips for any train is voided. If we assume that the shortest layover time is 15 minutes, then we can say that Trips 4 and 5 cannot be compatible.(3)
The train scheduling problem is solved as a daily problem in which every train schedule is assumed to be obtained from a daily train timetable. For two consecutive trips, the departure time of one trip should not be earlier than the arrival time of the next trip (e.g., Trips 1 and 2).(4)
The number of required trains cannot exceed the prescribed maximum number of trains.Figure2 illustrates train schedules corresponding to the data from the train timetable in Figure 1. Three trains are arranged for 12 trips. Each row corresponds to the trip tasks of a train. For instance, the trip tasks of the first train (no. 1) are in a chain with C-A, A-C, C-B, B-C, and C-A. The columns correspond to the trips in a timetable. Notably, the number of columns that correspond to different trains differs from one another. For any trip task of a particular train, the departure station of the first trip and the arrival station of the last trip are not necessarily the same.Figure 2
Illustration of train schedules.


## 2.2. Objective Function

The train is an important piece of equipment used in intercity railways, which is expensive to produce or purchase. To complete train timetables, the required number of trains should be as few as possible. Furthermore, the interval time of trains, a key factor in measuring their circulation efficiency, can be described as follows: a train runs in a section and reaches an intermediate station in one trip. It operates and waits at the station and then departs from the station for the following trip task. The interval time includes the operation time and waiting time at the station. When the train arrives and departs from the terminus, the interval time can be called the turn-back time. Therefore, the optimal objective of rail train scheduling is to determine the minimum number of trains required and ensure the minimum cost of interval time.As the sum of interval time and running time of trains is a multiple of the number of trains, and the running time of each train is a constant number, the objective of having the smallest number of trains is equivalent to the objective of having minimal cost in interval time. In this paper, the optimal objective is to minimize the total interval time, which can be formulated as follows:(1)min∑k=1m∑i=1n∑j=1ncij·yijk,
where m represents the number of trains required in a day, n represents the number of trips provided by a train timetable in a day and cij is the interval time between trip i and trip j. yijk is a binary 0-1 variable that indicates the status of trip i and trip j conducted by train k. yijk has two values: yijk=1 if trip j is the next trip after trip i conducted by train k, and yijk=0 otherwise.The interval time of any two trips in train timetables is significantly influenced by factors related to the trip, such as origin station, destination station, and arrival and departure time at the two stations. For any two trips, if the destination station of the former trip is different from the origin station of the latter trip, or if the interval time is less than the shortest layover timeT0, then the two trips cannot be arranged using the same train. Obviously, the two trips cannot satisfy the time-shift constraint. In this paper, the interval time can be set to an infinite positive number M. If the interval time of the two trips meets the time-shift constraint, then it can be calculated using the formula dj-ai. Therefore, interval time cij between trips i and j can be expressed as follows:
(2)cij={dj-ai,zi=sj,dj-ai≥T0,M,zi≠sjorzi=sj,dj-ai<T0,
where zi is the destination station of trip i, sj is the origin station of trip j, ai is the arrival time of trip i at destination station, and dj is the departure time of trip j at origin station.


## 2.3. Constraints

(1)
To ensure that each trip can be conducted using only one train, we formulate(3)∑k=1mxik=1,∀i.
(2)
The relationship between decision variablexik and auxiliary variable yijk can be formulated using the following equation:
(4)yijk=xik·xjk,∀k.
(3)
The two consecutive trips taken by the same train should satisfy the time-shift constraint, which means that the arrival time when the former trip ends at the destination station must be earlier than the departure time when the latter trip starts at the origin station. The minimum difference should be not less thanT0,
(5)I(dj-ai-T0)≥yijk,∀k,
where I(x) represents sign function, which is calculated using (6),
(6)I(x)={1,x≥0,0,x<0.
(4)
To ensure that the running mileage between different trains is equal, we have to make sure that the actual operation time between different trains does not vary significantly because of the constant speed of each train. The parameterGk, which represents the total operation time of train k, can be calculated using the following equation:
(7)Gk=∑i=1nxik(ai-di).
Therefore, we can calculate the maximum and minimum operation times of trains, and the difference should not exceed the maximum value of the operation time between any two trains T1,
(8)maxk,k′|Gk-Gk′|≤T1.
(5)
The decision variablexik is a 0-1 variable to indicate whether trip i is conducted by train k. xik has two values: xik=1 if trip i is conducted by train k, and xik=0 otherwise. Thus,
(9)xik∈{0,1},∀i,k.


## 3. Algorithm Design

The tabu search algorithm uses a neighborhood search procedure to iteratively move from one potential solution to an improved solution, until a stopping criterion is satisfied. Tabu search is a metaheuristic local search algorithm that can be used to solve combinatorial optimization problems. The major advantages of this algorithm are its simplicity, speed, and flexibility, and the scheduling model for rail train circulations in this paper is a complex zero-one programming problem. Thus, the tabu search algorithm can be used easily. The main parameters of the algorithm are designed as follows.


### 3.1. Expression of Solution

The two-dimensional integer array encoding method can be used to solve the train scheduling problem. In this method, rows represent trains, and columns represent trips. The trips are numbered according to departure time in ascending order. For example, in the train operation data presented in Figure2, the trip chains of each train can be expressed as follows: train 1: 1-6-7-8-9, train 2: 2-5-10, and train 3: 3-4-11-12. The expression of solution is shown in Figure 3.Figure 3
Expression of solution.Based on the values in the two-dimensional array, the decoding process is the inverse of the encoding process. For example, Figure3 contains 3 trains and 12 trips. The numbers of trips conducted by train 2 are 2, 5, and 10. Thus the variables are x22=1, x52=1, x102=1, y2,52=1, and y5,102=1. Other trains are decoded using the same method used in the former method.


### 3.2. Generation of Initial Solution

The initial solution is the starting point of the algorithmic search. A superior initial solution enables the algorithm to arrive quickly at the optimal solution. In the process of generating the initial solution, the time-shift constraint should be satisfied. The procedure of the algorithm is as follows.Step 1 (initialization).
The set of trips to be conducted by traink is set Pk=⌀, for all k. Let i=1, k=1, and a0=-T0.Step 2.
The train numberk′ and consecutive trip number i′ corresponding to trip i are determined. If Pk=⌀, then let k′=k and Step 4 is performed. Otherwise, i′=min{αl∣l∈{1,2,…,k}}, k′={l∣i′=αl,l∈{1,2,…,k}}, where αl=max{s∣s∈Pl}, and go to Step 3.Step 3.
The time-shift constraint is verified. Ifdi-ai′≥T0 and si=zi′, then go to Step 4. Otherwise, k←k+1, and go to Step 2.Step 4.
LetPk′=Pk′∪{i}, i←i+1; go to Step 5.Step 5.
Ifi>n, then the algorithm ends and the results are obtained. Otherwise, go to Step 2.


### 3.3. Neighborhood Structure

The neighborhood structure uses trips exchange and insert strategies between different trains. The trips exchange strategy can be described as follows: a single exchange point on both the trip chains of the two parents is selected. The trip number of that point is swapped between the two parent organisms. The resulting organisms are the children. For example, trip 7 of train 1 (1-6-7-8-9) is exchanged with trip 5 of train 2 (2-5-10), and new solutions can be obtained. The trip chain of train 1 becomes 1-6-5-8-9 and that of train 2 becomes 2-7-10, as shown in Figure4.Figure 4
Trips exchange strategy.The trips insert strategy can be described as follows: two consecutive trips from train 1 are inserted into the trip chain of train 2. The insert point depends on the departure time in the trips chain of train 2 in ascending order, and two new trip chains for the trains result. For example, if trip 5 of train 1 (1-5-7-8-10) is inserted into the trip chain of train 2 (2-6-9), then new solutions can be obtained. The trip chain of train 1 becomes 1-8-10 and the trip chain of train 2 becomes 2-5-7-6-9, as shown in Figure5. The trips exchange or insert operation cannot be performed if the trip chain of any crew cannot satisfy the time-shift constraint using any operation.Figure 5
Trips insert strategy.


### 3.4. Evaluation of Solution

To search for better solutions in the algorithmic iterative process, we have to evaluate the solution. It must simultaneously calculate the value of the objective function and consider the constraints. Given that the initial solution satisfies the time-shift constraint and the new solution generated in the neighborhood search also satisfies the former constraint, we can consider only the equilibrium constraint as the only factor in the former steps that should be punished.In this study, the parameters inα can be considered as the punish factors and the value becomes a large positive number. If the solution can satisfy the equilibrium constraint, then the values of the fitness function and the objective function become equal. Otherwise, the value of the fitness function becomes significantly larger than that of the objective function, which means that the set of values for the decision variables cannot create a feasible solution. The fitness function can be formulated as follows:
(10)f=Z+α·max{maxk,k′|Gk-Gk′|-T1,0},
where Z=∑k=1m∑i=1n∑j=1ncij·yijk represents the value of the objective function.


### 3.5. Other Parameters

The record of the tabu table is the transform (exchange or insert) node, and tabu length has a fixed value. Regulation is selected based on the value of evaluation as the aspiration criterion. In other words, the solution of the objective can be free if it is better than any of the best candidate solutions currently known. The stopping criterion is based on the value of the fitness function. If the best value does not change after a given number of iterations, then the algorithm stops the calculation.


## 3.1. Expression of Solution

The two-dimensional integer array encoding method can be used to solve the train scheduling problem. In this method, rows represent trains, and columns represent trips. The trips are numbered according to departure time in ascending order. For example, in the train operation data presented in Figure2, the trip chains of each train can be expressed as follows: train 1: 1-6-7-8-9, train 2: 2-5-10, and train 3: 3-4-11-12. The expression of solution is shown in Figure 3.Figure 3
Expression of solution.Based on the values in the two-dimensional array, the decoding process is the inverse of the encoding process. For example, Figure3 contains 3 trains and 12 trips. The numbers of trips conducted by train 2 are 2, 5, and 10. Thus the variables are x22=1, x52=1, x102=1, y2,52=1, and y5,102=1. Other trains are decoded using the same method used in the former method.


## 3.2. Generation of Initial Solution

The initial solution is the starting point of the algorithmic search. A superior initial solution enables the algorithm to arrive quickly at the optimal solution. In the process of generating the initial solution, the time-shift constraint should be satisfied. The procedure of the algorithm is as follows.Step 1 (initialization).
The set of trips to be conducted by traink is set Pk=⌀, for all k. Let i=1, k=1, and a0=-T0.Step 2.
The train numberk′ and consecutive trip number i′ corresponding to trip i are determined. If Pk=⌀, then let k′=k and Step 4 is performed. Otherwise, i′=min{αl∣l∈{1,2,…,k}}, k′={l∣i′=αl,l∈{1,2,…,k}}, where αl=max{s∣s∈Pl}, and go to Step 3.Step 3.
The time-shift constraint is verified. Ifdi-ai′≥T0 and si=zi′, then go to Step 4. Otherwise, k←k+1, and go to Step 2.Step 4.
LetPk′=Pk′∪{i}, i←i+1; go to Step 5.Step 5.
Ifi>n, then the algorithm ends and the results are obtained. Otherwise, go to Step 2.


## 3.3. Neighborhood Structure

The neighborhood structure uses trips exchange and insert strategies between different trains. The trips exchange strategy can be described as follows: a single exchange point on both the trip chains of the two parents is selected. The trip number of that point is swapped between the two parent organisms. The resulting organisms are the children. For example, trip 7 of train 1 (1-6-7-8-9) is exchanged with trip 5 of train 2 (2-5-10), and new solutions can be obtained. The trip chain of train 1 becomes 1-6-5-8-9 and that of train 2 becomes 2-7-10, as shown in Figure4.Figure 4
Trips exchange strategy.The trips insert strategy can be described as follows: two consecutive trips from train 1 are inserted into the trip chain of train 2. The insert point depends on the departure time in the trips chain of train 2 in ascending order, and two new trip chains for the trains result. For example, if trip 5 of train 1 (1-5-7-8-10) is inserted into the trip chain of train 2 (2-6-9), then new solutions can be obtained. The trip chain of train 1 becomes 1-8-10 and the trip chain of train 2 becomes 2-5-7-6-9, as shown in Figure5. The trips exchange or insert operation cannot be performed if the trip chain of any crew cannot satisfy the time-shift constraint using any operation.Figure 5
Trips insert strategy.


## 3.4. Evaluation of Solution

To search for better solutions in the algorithmic iterative process, we have to evaluate the solution. It must simultaneously calculate the value of the objective function and consider the constraints. Given that the initial solution satisfies the time-shift constraint and the new solution generated in the neighborhood search also satisfies the former constraint, we can consider only the equilibrium constraint as the only factor in the former steps that should be punished.In this study, the parameters inα can be considered as the punish factors and the value becomes a large positive number. If the solution can satisfy the equilibrium constraint, then the values of the fitness function and the objective function become equal. Otherwise, the value of the fitness function becomes significantly larger than that of the objective function, which means that the set of values for the decision variables cannot create a feasible solution. The fitness function can be formulated as follows:
(10)f=Z+α·max{maxk,k′|Gk-Gk′|-T1,0},
where Z=∑k=1m∑i=1n∑j=1ncij·yijk represents the value of the objective function.


## 3.5. Other Parameters

The record of the tabu table is the transform (exchange or insert) node, and tabu length has a fixed value. Regulation is selected based on the value of evaluation as the aspiration criterion. In other words, the solution of the objective can be free if it is better than any of the best candidate solutions currently known. The stopping criterion is based on the value of the fitness function. If the best value does not change after a given number of iterations, then the algorithm stops the calculation.


## 4. Numerical Example

The Beijing-Tianjin intercity rail line is a major railway system that serves passengers who travel between the cities of Beijing and Tianjin in China. The line starts from Beijing South Railway Station and ends at Tianjin Railway Station. It has a total length of 119.4 km and covers 74 trips in two directions every day. The main pieces of information about each trip, such as origin and destination stations as well as departure and arrival time, are presented in Table1.Table 1
Departure and arrival time of trips.
No.
DT
AT
No.
DT
AT
No.
DT
AT
No.
DT
AT
1
6:25
6:58
38
10:40
11:13
75
14:40
15:13
112
18:25
18:58
2
6:30
7:03
39
10:45
11:23
76
14:25
14:58
113
18:30
19:08
3
6:40
7:18
40
10:45
11:18
77
14:50
15:23
114
18:35
19:08
4
6:45
7:23
41
11:00
11:33
78
14:35
15:13
115
18:50
19:28
5
7:10
7:43
42
10:55
11:28
79
15:00
15:33
116
19:05
19:38
6
7:05
7:38
43
11:20
11:53
80
14:45
15:18
117
19:00
19:33
7
7:20
7:58
44
11:10
11:48
81
15:05
15:43
118
19:15
19:53
8
7:25
8:03
45
11:25
11:58
82
14:55
15:33
119
19:10
19:43
9
7:40
8:13
46
11:25
11:58
83
15:15
15:48
120
19:30
20:03
10
7:35
8:08
47
11:30
12:08
84
15:15
15:48
121
19:30
20:03
11
7:55
8:28
48
11:35
12:08
85
15:20
15:53
122
19:40
20:13
12
7:45
8:18
49
11:50
12:23
86
15:25
15:58
123
19:40
20:18
13
8:00
8:38
50
11:55
12:33
87
15:35
16:13
124
19:55
20:28
14
7:55
8:33
51
12:00
12:33
88
15:35
16:13
125
20:05
20:38
15
8:10
8:43
52
12:20
12:53
89
15:50
16:23
126
20:10
20:43
16
8:20
8:53
53
12:20
12:53
90
15:50
16:23
127
20:15
20:48
17
8:25
9:03
54
12:30
13:03
91
15:55
16:28
128
20:30
21:03
18
8:30
9:08
55
12:25
12:58
92
16:05
16:43
129
20:20
20:53
19
8:40
9:13
56
12:40
13:18
93
16:05
16:38
130
20:40
21:18
20
8:45
9:18
57
12:45
13:23
94
16:15
16:48
131
20:30
21:08
21
8:45
9:18
58
12:55
13:28
95
16:15
16:48
132
20:50
21:23
22
9:00
9:38
59
13:10
13:43
96
16:20
16:53
133
20:55
21:28
23
9:05
9:38
60
13:05
13:38
97
16:30
17:08
134
21:00
21:33
24
9:20
9:53
61
13:20
13:53
98
16:30
17:03
135
21:05
21:38
25
9:10
9:43
62
13:10
13:43
99
16:45
17:18
136
21:15
21:53
26
9:30
10:03
63
13:25
13:58
100
16:40
17:18
137
21:20
21:53
27
9:25
10:03
64
13:15
13:48
101
17:05
17:43
138
21:30
22:03
28
9:40
10:13
65
13:50
14:28
102
17:00
17:38
139
21:35
22:08
29
9:35
10:08
66
13:30
14:03
103
17:25
17:58
140
21:40
22:13
30
9:50
10:28
67
14:05
14:38
104
17:20
17:53
141
21:50
22:23
31
9:55
10:28
68
13:40
14:13
105
17:35
18:13
142
21:55
22:28
32
10:00
10:33
69
14:10
14:43
106
17:25
17:58
143
22:00
22:33
33
10:10
10:48
70
13:45
14:23
107
17:50
18:23
144
22:10
22:43
34
10:10
10:43
71
14:25
15:03
108
17:40
18:18
145
22:15
22:48
35
10:20
10:53
72
14:05
14:38
109
18:00
18:38
146
22:25
22:58
36
10:25
11:03
73
14:35
15:08
110
18:05
18:43
147
22:45
23:18
37
10:35
11:08
74
14:15
14:48
111
18:15
18:48
148
23:00
23:33
Notes: “DT” stands for departure time and “AT” stands for arrival time. Trains with odd numbers run from Tianjin Station to Beijing Station, and trains with even numbers run from Beijing Station to Tianjin Station.The shortest layover time for trains at switchback station is 15 minutes, and the maximum deviation value of any two trains is set to 90 minutes. The parameters for the tabu search algorithm are as follows: the tabu length is 6; the punish factor is 10,000; and the given number of iterations without improving the solution is 100. The optimal solution can be calculated using the VC++ program, as shown in Table2. The objective value of the optimal solution is 5,099 minutes.Table 2
The optimal results for train scheduling.
Train number
Trips
Operation time (min)
01
1-16-31-46-61-76-91-106-121-136
335
02
2-17-32-47-62-77-96-107-122-137
340
03
3-18-33-48-63-78-93-108-123-138
360
04
4-19-38-49-64-85-100-109-126-139
345
05
5-20-35-50-65-80-95-110-125-140
345
06
6-21-42-51-66-81-92-111-130-141
345
07
7-22-37-52-67-82-97-112-127-142
350
08
8-23-34-53-72-83-98-113-134-143
340
09
9-24-39-54-69-84-99-114-129-144
335
10
10-15-40-55-70-79-94-115-128-145
340
11
11-26-41-56-71-86-101-116-131-146
350
12
12-29-44-59-74-89-104-117-124
302
13
13-28-43-58-73-88-103-118-133-148
345
14
14-27-36-57-68-87-102-119-132-147
360
15
15-30-45-60-75-90-105-120-135
307Table2 indicates that the total number of trains is 15 in two directions. The maximum value of train operation time is no more than 360 minutes (nos. 3 and 14). The minimum value of train operation time is 302 minutes (no. 12). The deviation value of operation time between train nos. 3 and 12 is 58 minutes, which is less than the specified value of 90 minutes. Thus, the equilibrium constraint is satisfied.


## 5. Conclusions

In this paper, we present an optimized scheduling method of rail train circulations on a bidirectional intercity railway line. A binary integer programming model with the objective of minimizing the train fleet and the total interval times is presented to show the schedule process. To work out a practical schedule, the time-shift and equilibrium constraints are also considered. We have developed a tabu search algorithm to solve the proposed scheduling model.Computational results with the trip data on Beijing-Tianjin have shown that the algorithm can produce high-quality train scheduling solutions. Furthermore, this method can be widely applied to rail train circulations characterized by high-density trips and large-quantity trains. During the peak period of an intercity railway line, because of the unbalanced feature of trip numbers in both two directions, future research work may focus on considering the rail train circulations with deadhead strategy.



---

*Source: 102346-2013-12-09.xml*