The integrated optimization of robust train timetabling and electric multiple unit circulation and maintenance scheduling problem

Abstract

Train timetables provide trains’ departure and arrival times at each space node, and electric multiple unit circulation and maintenance schedules assign the tasks of trips and maintenance to electric multiple units. Forming two schedules independently could bring infeasible solutions in both phases of forming and practice, so the purpose of this study is to avoid infeasibilities and generate a better integrated solution. To illustrate the two problems in one mathematical model, we introduce a space–time–state framework, which can show not only electric multiple units’ trajectories, but also their accumulative running distance (the core factor in maintenance) as the state dimension simultaneously. Due to the occurrence of the disruptions, delays might be caused in both trains’ traveling and maintenance. Therefore, the buffer time should be inserted into the activities such as running in sections, electric multiple unit circulation and maintenance in order to guarantee robustness. A 0-1 nonlinear integer programming model is built, which integrates the formulations of both robust train timetabling and electric multiple unit circulation and maintenance scheduling problems. It is verified by GAMS solver within small-scale instance. However, due to the large scale of the real-world cases, the GAMS solver cannot deal with that in a receivable computational time. In order to solve this integrated model effectively, we propose an improved ant colony algorithm. This algorithm provides solutions not only as good as GAMS in small-scale cases, but also of high quality in large-scale cases. We obtain the robust train timetables and electric multiple unit assignment and maintenance schedules of Beijing–Shanghai high-speed railway in a relatively short time using the proposed ant colony algorithm.

Introduction

In recent years, due to the high safety and efficiency of high-speed railways (HSR), more and more passengers are attracted to take its services. Also the studies on train timetabling and electric multiple unit (EMU) circulation and maintenance scheduling in HSR are becoming more focused. Traditionally, railway corporations construct these two schedules independently. Train timetables are generated first with the input data of line plans, and then EMU circulation and maintenance schedules are made based on train timetables. In this way, a good train timetable might be obtained. But some infeasibilities could also be brought into the EMU circulation and maintenance schedules. Therefore, we propose an integrated model of train timetabling and EMU circulation and maintenance scheduling. The terminologies of the line plan, the train timetable, and the EMU circulation and maintenance schedule are illustrated as follows.

Line plans specify a set of routes (paths) in a network of tracks, operated at a given frequency. ¹ It serves as the input data of timetabling.

For example, Figure 1 shows the line plans of weekdays and weekends that are made based on the passengers’ demand data.

Figure 1.

Line plan of Friday and Saturday.

Train timetables define trains’ arrival and departure times at yards, terminals, and sidings along the routes of trains. ² Based on the line plan shown in Figure 1, the train timetables of Friday and Saturday are displayed with the space–time graph in Figure 2.

Figure 2.

Train timetables of Friday and Saturday.

EMU circulation and maintenance schedules assign the tasks of trips and maintenances to EMUs, aiming to minimize the total operating cost. The blue and orange lines in Figure 2 can be regarded as tasks of train trips. Once EMU’s cumulative running distance is near to a specified value, it must be sent to the depot to undertake maintenance. The maintenance will take at least several hours represented by the red block in Figure 3, during which EMUs are unavailable for working. After maintenance, its accumulative running distance is set to zero again. Before the end of the day, EMUs have to return to its belonging depot after finishing all today’s work.

Figure 3.

EMU circulation and maintenance schedule.

Figure 3 also presents the minimum turn-around time. After EMU completes a task trip, it needs some time to do the preparation for the next trip, such as cleaning the cars and checking the EMUs’ statuses.

There is some relevant literature about line plans, train timetables, and EMU circulation and maintenance schedules (we call them rolling stock schedules in conventional railways).

Goossens et al. ¹ focused on the line planning with the aim of decreasing the total operating costs. It was solved by a branch-and-cut approach, which was developed using a variety of valid inequalities and reduction methods. Lin et al. ³ proposed an integer programming model and a systematic approach to determining the optimal train stopping patterns for a railway company. Then an integer-coded genetic algorithm with new encoding mechanism and genetic operators was proposed, which was used to solve real-world problems in Taiwan.

In the train timetabling field, Zhou and Zhong^2,4 and Niu et al. ⁵ made many contributions to the modeling and proposed effective algorithms. These three papers dealt with train timetabling problem in single-track, double-track, and railway corridor scenarios, respectively, aiming at minimizing the waiting and traveling times of trains and passengers. Branch-and-bound and Lagrangian relaxation technologies were utilized in the proposed algorithms.

Kroon et al. ⁶ studied on rolling stock rescheduling undertaken. Also Nielsen et al. ⁷ presented the online rolling stock rescheduling based on the dynamic passenger flows. Moreover, it was performed on real-life instances of Netherlands Railways, with different settings for the trade-offs between solution quality and computation time.

Papers with respect to both line plans and train timetables are listed below.

Yang et al. ⁸ focused on collaborative optimization of the line plan and the train timetable generation. They built a multi-objective mixed integer linear programming model on a single-track HSR corridor and then used GAMS to solve it.

Yue et al. ⁹ aimed to develop train timetables to take full advantage of the HSR system’s capacity. They proposed a column-generation-based heuristic algorithm to simultaneously consider both passenger service demands and train scheduling. Finally, they optimized stopping patterns and schedules in Beijing–Shanghai high-speed railway.

Kaspi and Raviv ¹⁰ formulated an integrated line planning and timetabling model with the objective of minimizing both user inconvenience and operational costs, which was solved using a cross-entropy metaheuristic. The method was testified in Israel Railways as a benchmark, with an average 20% reduction in passengers’ traveling time.

In this article, we integrate the optimization of train timetables and EMU circulation and maintenance schedules. Besides the advantage of avoiding infeasible solutions, we also consider both directions of trains’ trajectories. However, in some preceding literature it is assumed that trains’ trajectories are the same and independent in the two directions, so the trajectories are solved only in one direction.

Table 1 shows some literature focusing on the line plan, train timetable, and rolling stock schedule or any two of them together. For example, the contents of the cells under the Line planning row and the Line planning column indicate that the corresponding papers study only line planning. The contents of the cells under the Train timetabling column and the Line planning row indicate that these papers focus on both train timetabling and rolling stock scheduling.

Table 1.

Focus of the literature.

Research contents	Line planning	Train timetabling	Rolling stock scheduling
Line planning	Goossens et al. 1 and Lin et al. 3	Yang et al., 8 Yue et al., 9 and Kaspi and Raviv 10	–
Train timetabling	–	Zhou and Zhong2,4	This study
Rolling stock scheduling	–	–	Kroon and colleagues6,7

With respect to the robustness of the timetable, Bešinović et al. ¹¹ presented a framework for timetable design which combined a microscopic and a macroscopic model to generate a feasible and stable timetable with the trade-off between minimal travel times and maximal robustness. In this article, we insert a suitable buffer time into traveling and maintenance activities.

The contributions of this article are listed as follows:

1. We build a mathematical model integrating both train timetabling and EMU circulation and maintenance scheduling problems. Moreover, we introduce the time–space–state framework to represent EMUs’ instant trajectories and the state of accumulative running distances (the core factors in maintenance).

   Finally, we obtain the train timetable and the EMU circulation and maintenance schedule simultaneously with more robustness and less EMUs than the traditional methods.

2. Our model includes more constraints of EMUs’ management in reality: (1) all EMUs must return to their belonging depots at night; (2) all EMUs must get maintenance after running for a certain running distances. These two constraints make the model more difficult to build or even generate infeasibilities in the solving process.

   We consider both running directions of trains, as in the real world the trajectories of two directions might not be symmetrical, but they have some relations with each other.

3. Aiming to obtain the result effectively and efficiently, we propose several improvements to traditional ant colony algorithm. In practice, the problem cannot be solved by GAMS directly due to the large scale, so the improved ant colony is designed.

In the remaining parts, the advantages of integrating the train timetable and the EMU circulation and maintenance schedule are described in detail in section “Problem description.” The mathematical model is then demonstrated in section “Model description.” Section “Illustrative example” gives an illustrative example to testify the mathematical model. The algorithm used in the large-scale problem is proposed in section “Solution algorithm.” Section “Numerical experiment” studies the real-world cases and then we present the conclusions in section “Conclusion.”

Problem description

Currently, railway corporations construct train timetables and EMU circulation and maintenance schedules following a process shown in Figure 4(a). It means that the timetable is viewed as the input in the EMU circulation and maintenance scheduling even though there is a feedback to the timetable at last. Both of these plans are finally constructed through several iterations of the same process. However, from Figure 4(b) it is observed that our approach solves these two problems in an integrated way. They are generated at the same time without any feedbacks. We make a comparison between these two methods through a simple case from Figures 5–9.

Figure 4.

(a) Conventional method and (b) proposed method.

Figure 5.

Example of line plan.

Figure 6.

Example of train timetable.

Figure 7.

Example of EMU circulation and maintenance schedule.

Figure 8.

The train timetable.

Figure 9.

The EMU circulation and maintenance schedule.

There are four stations along the railway line. Stations A and D have EMU depots for maintenance. Figure 5 shows the trajectories and stopping patterns of six trains in the line plan. Based on the line plan, the train timetable (in Figure 6) gives trains’ departure and arrival times at each station. Then the timetable is viewed as the input of EMU circulation and maintenance schedules. From Figure 7, it is observed that at least three EMUs are needed to perform task trips. However, there would be the possibility of improvement.

In Figure 6, the blue circle indicates that even if the two trains do not have conflicts, their arrival and departure times are too “close.” Hence, if the arrival of the preceding train is delayed, the next departure train will be affected. Moreover, in Figures 6 and 7, the purple circles indicate that these trips can share the same EMUs, and then the total cost of EMUs can be saved.

Finally, if we solve these two schedules in a traditional way, even though the train timetable is generated with less traveling time, it might bring risks of delays in turn-around or additional costs in EMU circulation and maintenance schedules. Therefore, we should try to solve them in an integrated way.

When we integrate these two schedules, the results are shown in Figures 8 and 9, in contrast to Figures 6 and 7, respectively.

From Figures 8 and 9, we can save one EMU and increase robustness in the turn-around period. If we are faced with a more extreme situation that the EMUs are insufficient for the train timetable in Figure 6, only constructing train timetables and EMU circulation and maintenance schedules together could generate a feasible solution.

Our process of the integrated method is shown in Figure 10. It indicates that the physical railway network and line plans are seen as the input data, and robust train timetables and EMU circulation and maintenance schedules are the output.

Figure 10.

Input and output of the method.

Model description

Notations and terminologies

For modeling clearance, Table 2 lists all the subscripts, input parameters, and decision variables used in this article.

Table 2.

Notations and definitions.

Notations	Definitions
$S$	Set of stations and depots
$E$	Set of EMUs
$S_d$	Subset of S, the set of depots
$S_n$	Subset of S, the set of stations
$L$	Set of train trips
$L^{\mathrm{lp}}$	Set of line plan
$T$	Set of discrete time
$S_D$	Set of stations which own EMU depots
$s$	Index of stations
$d$	Index of depots, $d\in D$
$s_d$	The depot d which belongs to the station s, $s\in S$ , $d\in D$
$l$	Index of a train trip, $l\in L$
$l^{\mathrm{lp}}$	Index of the set $L^{\mathrm{lp}}$
$s_{\mathrm{ori}}^l$	The original station of the train task trip l
$s_{\mathrm{des}}^l$	The destination station of the train task trip l
$t_{\mathrm{start}}$	Start running time of a day
$t_{\mathrm{end}}$	End running time of a day
$t$	Index of discrete time, $t\in T$
$e$	Index of EMUs, $e\in E$
$m_{s,s+1}$	Distance between the stations s and s + 1
$b_d(s)$	Whether the station s is a depot ( which is 1 if it is and 0 otherwise)
$M_{\mathrm{ma}}$	Maximum accumulative running distance of an EMU
${\alpha }_{\mathrm{ma}}$	Allowable range of $M_{\mathrm{ma}}$
$t_{\mathrm{dwell}}$	Minimum time of stop at an intermediate station
$t_{\mathrm{turn}-a}$	Minimum time of EMU turn-around work
$t_{\mathrm{ma}}$	Minimum time of EMU maintenance work
$t_{[s_1,s_2]}$	Running time between the stations $s_1$ and $s_2$
$t_h$	Headway
$n_{\mathrm{side}}^s$	Number of sidetracks in the station s or lines in the depot
$c_h$	Cost of one headway delay in a section
$c_{\mathrm{ma}}$	Cost of one maintenance delay in a depot
$c_{\mathrm{turn}-a}$	Cost of one turn-around delay in a station or a depot
$c_e$	Cost of an EMU e
$b_h$	Buffer time inserted into the headway
$b_{\mathrm{ma}}$	Buffer time inserted into the maintenance task
$b_{\mathrm{turn}-a}$	Buffer inserted into the turn-around activity
$f_{s_1,s_2}^l$	Train trip parameter (which is 1 if the train line of the train task trip $l^{\mathrm{lp}}$ departs from the place $s_1$ and arrives at the place $s_2$ and 0 otherwise)
$f_{s_1}^l$	Train trip parameter (which is 1 if the train must stop at the station $s_1$ for picking up and dropping off passengers and 0 otherwise)
$p_{\mathrm{ll}\prime }$	Pheromone $p_{\mathrm{ll}\prime }$ of two train task trips $l$ and $l\prime$
$x_{s_1,s_2}^{t_1,t_2}(e,l)$	Decision variable (which is 1 if the EMU e takes on the train trip task l and departs from the place $s_1$ and arrives at the place $s_2$ and 0 otherwise). If e is deadheading between the stations and depots or stopping without tasks, then l is replaced by 0

EMU: electric multiple unit.

Time–space–state graph can be adopted to present the real-time positions and running statuses of EMUs. The state dimension can be used to display the accumulative running distances of EMUs, which is the core factor in maintenance. There are two types of arcs in the time–space–state graph:

1. Traveling arcs, where s and s + 1 are two adjacent stations or depots;

2. Waiting arcs, where $s_1=s_2$ or $d_1=d_2$ .

For example, in Figures 11–13, the EMUs are traveling from the depot $S_{d1}$ to the depot $S_{d3}$ during the time period from t + 0 to t + 8. When their accumulative running distances are approaching the maximum value, EMUs must be sent to depots to for maintenance.

Figure 11.

Railway line.

Figure 12.

Time–space–state graph of time from 0 to t + 4.

Figure 13.

Time–space–state graph of time from t + 4 to t + 8.

Assumptions

• Assumption 1. All the railway lines are double-track. The capacities of both tracks are sufficient.

• Assumption 2. Deadheading between stations is not allowed.

• Assumption 3. The EMU can undertake maintenance in any depots, but it must return to its belonging depot at the end of the day.

• Assumption 4. The velocities of all the EMUs are the same. Namely, in each section, the running times of all the EMUs are the same.

• Assumption 5. we do not consider the extra travel time caused by acceleration and deceleration in train timetable.

• Assumption 6. Due to the specific station facility distribution, train speed, and signal system, we assume that headways for departure and arrival are the same. Therefore, only the headway for departure is considered.

Objective

Railway companies aim to operate trains with high robustness and low cost. To achieve these goals, we can maximize the robustness by minimizing the operational cost of possible delay and minimize the cost of using EMUs. Therefore, the objective function can be formulated as shown in equation (1). The $C_{\mathrm{EMU}}$ part represents the costs of EMUs and $C_{\mathrm{delay}}$ shows the costs of possible delays

$$f=min(C_{\mathrm{EMU}}+C_{\mathrm{delay}})$$

(1)

These two parts of the objective function can be presented as the following formulations

$$C_{\mathrm{EMU}}=\sum _e(c_e·\sum _{s_1=S_D,s_2\in S_n,t_1,t_2}{x}_{s_1,s_2}^{t_1,t_2}(e,0))$$

(2)

$$C_{\mathrm{delay}}=C_{\mathrm{turn}-a}+C_{\mathrm{ma}}+C_h$$

(3)

where $C_{\mathrm{turn}-a}$ , $C_{\mathrm{ma}}$ , and $C_h$ are total costs of turn-around delays, maintenance delays and headway delays respectively, calculated using equations (4)–(6). These three costs are related to the buffer times $b_{\mathrm{turn}-a}$ , $b_{\mathrm{ma}}$ , and $b_h$ , respectively. We will illustrate their calculation in Figure 14

$$C_{\mathrm{turn}-a}=\sum _{e,l,s_1,t_1,t_2}\{x_{s_1,s_{\mathrm{des}}^l}^{t_1,t_2}(e,l)·\sum _{t=0}^{t_{\mathrm{turn}-a}+b_{\mathrm{turn}-a}-1}[c_{\mathrm{turn}-a}·(1-x_{s_{\mathrm{des}}^l,s_{\mathrm{des}}^l}^{t_2+t,t_2+1+t}(e,0))]\}$$

(4)

$$C_{\mathrm{ma}}=\sum _{e,l,s_1,s_{d1},t_1,t_2}(x_{s_1,s_{d1}}^{t_1,t_2}(e,0)·\sum _{t=0}^{t_{\mathrm{ma}}+b_{\mathrm{ma}}-1}(c_{\mathrm{ma}}·(1-x_{s_{d1},s_{d1}}^{t_2+t,t_2+1+t}(e,0))))$$

(5)

$$C_h=\sum _{e,l,t_1,s_1,s_2\ne s_1}(x_{s_1,s_2}^{t_1,t_1+t_{[s_1,s_2]}}(e,l)·\sum _{t=0}^{t_h+b_h-1}\sum _{e\prime }\sum _{l\prime }(c_h·(t_h+b_h-t)·x_{s_1,s_2}^{t_1+t,t_1+t_{[s_1,s_2]}+t}(e\prime ,l\prime )))$$

(6)

Let us consider the calculation of $C_{\mathrm{turn}-a}$ as an example; the other two are similar. If the EMU e takes task trip 2 after task trip 1, the cost will be $C_{\mathrm{turn}-a}$ (a specific value) as the duration between the arrival time of trip 1 and the departure time of trip 2 is not adequate time for buffering. But the cost of trip 3 is 0 as the duration is long enough.

Figure 14.

Calculation of $C_{\mathrm{turn}-a}$ , $C_{\mathrm{ma}}$ , and $C_h$ .

Constraints

Headway constraint

To guarantee the safety of two adjacent trains in the same direction, the interval time between two departures should be greater than a regulation value $t_h$ . Figure 15 gives the explanation of the in equation (7) that at most one train can be managed in the duration of headway time. Due to Assumption 6, we consider only the headway for departure time

$$\sum _{t=0}^{t_h-1}\sum _{e,l}{x}_{s_1,s_2}^{t_1+t,t_1+t+t_{[s_1,s_2]}}(e,l)\le 1,\forall t_1,s_1,s_2$$

(7)

Figure 15.

Explanation for headway constraint.

EMU maintenance constraints

EMUs must undergo maintenance before their accumulative running distances reach the maximum value. From equation (8), it can be observed that during any time period $[t_1,t_4]$ the accumulative distances of each EMU cannot exceed the maximum value, unless it enters the depot for maintenance

$${\displaystyle \sum _{s_1,s_2,l,t_2<t_3\in \left[t_1,t_4\right]}\left(x_{s_1,s_2}^{t_2,t_3}\left(e,l\right)·m_{s_1,s_2}·\left(1-b_d\left(s_2\right)·G\right)\right)}\le \left(1+{\alpha }_{ma}\right)·M_{ma},\forall e,t_1\le t_4$$

(8)

where $G$ is a very large number.

Furthermore, maintenance must be performed at the depot within a specified time period

$$\begin{array}{l}{t}_{ma}·x_{s_1,s_d}^{t_1,t_1+t_{\left[s_1,s_d\right]}}\left(e,0\right)\\ \le {\displaystyle \sum _{t=0}^{t_{ma}-1}{x}_{s_d,s_d}^{t_1+t_{\left[s_1,s_d\right]}+t,t_1+t_{\left[s_1,s_d\right]}+t+1}}\left(e,0\right),\forall e,s_1,s_d,t_1\end{array}$$

(9)

EMU turn-around connection constraint

It defines the minimum time between two consecutive task trips performed by the same EMU

$$\begin{array}{l}{t}_{turn-a}·x_{s_1,s_2}^{t_1,t_2}\left(e,l\right)\le {\displaystyle \sum _{t=0}^{t_{turn-a}-1}{x}_{s_1,s_2}^{t_2+t,t_2+t+1}\left(e,0\right)},\\ \forall s_1,s_2=s_{des}^l,t_1,t_2,e,l\end{array}$$

(10)

Station (or depot) sidetrack capacity constraint

Capacity of the sidetracks in stations and depots is assured by this constraint

$$\sum _e\sum _l{x}_{s_1,s_1}^{t_1,t_1+1}(e,l)\le n_{\mathrm{side}}^{s_1},\forall s_1,t_1$$

(11)

Flow balance constraint

This constraint maintains flow conservation of the EMUs at each node in the network. Three equations in (12) ensure the flow balance in origins, destinations, and intermediate stations, respectively

$$\{\begin{array}{c}\sum _{s_2,t_2,l}{x}_{s_1,s_2}^{t_1,t_2}(e,l)=1,t_1=t_{\mathrm{start}}\forall e,s_1\hfill \\ \multicolumn{1}{c}{\sum _{s_1,t_1,l}{x}_{s_1,s_2}^{t_1,t_2}(e,l)=1,t_2=t_{\mathrm{end}}\forall e,s_2}\\ \multicolumn{1}{c}{\sum _{s_1,t_1,l}{x}_{s_1,s_2}^{t_1,t_2}(e,l)-\sum _{s_1,t_1,l}{x}_{s_2,s_1}^{t_2,t_1}(e,l)=0,\forall e,t_2\ne t_{\mathrm{start}}\ne t_{\mathrm{end}},s_2}\end{array}$$

(12)

Task covering constraint

1. Trains must stop at intermediate stations ruled in the line plan to ensure the route accessibilities for passengers.

2. Stop at the destinations

   $$\begin{array}{l}{x}_{s_1,s_2}^{t_1,t_2}\left(e,l\right)\le x_{s_2,s_2}^{t_2-1,t_2}\left(e,l\right),\\ \forall e,l\ne 0,s_2=s_{des}^l,s_2,t_1,t_2\end{array}$$

   (14)

3. Stop at the intermediate stations

   $$\sum _{t_1,e}{x}_{s_1,s_1}^{t_1,t_1+1}(e,l)\ge f_{s_1}^l,\forall l\ne 0,s_1\in S_N$$

   (15)

Train trips must travel in specified segments

$$\sum _{t_1,t_2,e}{x}_{s_1,s_2}^{t_1,t_2}(e,l)=f_{[s_1,s_2]}^l,\forall l\ne 0,s_1,s_2$$

(16)

The whole train trip must be finished by only one EMU

$$\begin{array}{l}{\displaystyle \sum _{s_1,t_1}{x}_{s_1,s_2}^{t_1,t_2}\left(e,l\right)}={\displaystyle \sum _{s_3,t_3}{x}_{s_2,s_3}^{t_2,t_3}\left(e,l\right)},\\ \forall l\ne 0,t_2,s_2\ne s_{des}^l\ne s_{ori}^l,e\end{array}$$

(17)

Illustrative example

There are three stations located in the railway line shown in Figure 16. Stations 1 and 3 own depots. Three EMUs are belonging to the two depots, respectively. The numbers in Figure 16 represent the running distances and times, respectively. We consider the time period of 20 h, with the other parameters listed below (Table 3). The GAMS solver is used to solve this illustrative example to testify the feasibility of the mathematical model. As reported by Rosenthal, ¹² in the GAMS user guide, the GAMS model representation is in a form that can be easily read by people and by computers. This means that the GAMS program itself is the documentation of the model.

Figure 16.

The railway structure.

Table 3.

Parameters in the illustrative experiment.

Parameter	Value	Parameter	Value
$t_{[s_1,s_2]}$	1 h	$t_{\mathrm{dwell}}$	1 h
$t_{[s_2,s_3]}$	2 h	$t_h$	1 h
$t_{[s_1,s_{d1}]}$	1 h	$b_{\mathrm{turn}-a}$	1 h
$t_{[s_3,s_{d2}]}$	1 h	$b_{\mathrm{ma}}$	1 h
$t_{\mathrm{turn}-a}$	1 h	$b_h$	1 h
$t_{\mathrm{ma}}$	2 h	$M_{\mathrm{ma}}$	190 km
∂	1000	$t_{\mathrm{day}}$	20 h

What is more, from Wikipedia ¹³ the GAMS system is available for use on various computer platforms. Models are portable from one platform to another. And it has users from various backgrounds, from economics and management science to engineering and science (Table 4).

Table 4.

The belonging EMU and sidetrack number of depots.

EMU ID	Belonging depot	Sidetrack number of belonging depot
$e_1$	$s_{d1}$	2
$e_2$	$s_{d3}$	2
$e_3$	$s_{d1}$	2

EMU: electric multiple unit.

As shown in the line plan (Tables 5 and 6), “•” represents the stations for passengers’ pickup and drop-off, which could be the origins, destinations, or intermediate stations; “–” indicates that those stations are not in the trains’ routes.

Table 5.

The line plan of the up direction.

$l^{\mathrm{lp}}$	$s_1$	$s_2$	$s_3$
$l_1^{\mathrm{lp}}$	•	•	–
$l_2^{\mathrm{lp}}$	•	•	–
$l_3^{\mathrm{lp}}$	•	•	•

Table 6.

The line plan of the down direction.

$l^{\mathrm{lp}}$	$s_3$	$s_2$	$s_1$
$l_4^{\mathrm{lp}}$	–	•	•
$l_5^{\mathrm{lp}}$	–	•	•
$l_6^{\mathrm{lp}}$	•	•	•

Due to the existence of the nonlinear objective function and six dimensions of variables $x_{s_1,s_2}^{t_1,t_2}(e,l)$ , GAMS will require a large amount of time to get the optimal solution (Table 7). In the calculation process which spends more than 3 h, it can hardly obtain the optimal solution or even a feasible solution. For the purpose of only testifying that the constructed model’s feasible region is not empty, we modify the objective function to transform it into a linear programming model and get a feasible solution in a shorter time because railway corporations prefer relatively good or even feasible solutions in a shorter computational time to find the optimal solution by consuming a lot of time.

Table 7.

Comparison between two calculation methods.

	By GAMS	By ant colony algorithm in C#
RAM consumption (GB)	≈3.4	≈0.1
Time consumption (s)	>10,800/≈4.9 (origin/modified objective function)	≈1.2

So we only show the feasible solution in Figure 17 to demonstrate that the model is feasible. The numbers above the lines are the index of train task trips. Finally, we need three EMUs to perform the tasks in the train timetable.

Figure 17.

Solution generated by GAMS.

Therefore, we need a more effective algorithm to get a receivable good solution, which will be introduced in section “Solution algorithm.”

Solution algorithm

To fully address the NP-hard large-scale train timetabling and EMU circulation and maintenance scheduling problems in the real world, we have to propose an improved algorithm to ensure a relatively optimal result and the receivable computational time.

Terminologies and calculations of parameters

The ant colony algorithm is proposed as a new metaheuristic approach for solving hard combinatorial optimization problems. In railway filed, most of the literature uses ant colony algorithm to deal with complex problems: timetabling, ¹⁴ rolling stock planning, ¹⁵ railroad blocking problem, ¹⁶ and rescheduling. ¹⁷ In this article, we improve the ant colony to solve integrated timetabling and EMU circulation and maintenance scheduling problems. Terminologies and calculations of parameters are illustrated as follows.

Conflicts

For train $l$ , $\exists l\prime (l\prime \ne l)$ , if $|t_{s,\mathrm{dep}}^{l\prime }-t_{s,\mathrm{dep}}^l|<t_h$ or $|t_{s,\mathrm{arr}}^{l\prime }-t_{s,\mathrm{arr}}^l|<t_h$ , then $l$ has conflicts with $l\prime$ . In other words, every two trains must meet the headway constraint.

Enter the depot

If EMU cannot go back to the depot before the end of the day $t_{\mathrm{arr}}^l>t_{\mathrm{end}}$ , we replace $l$ by another train task trip $l\prime$ , the arrival station of which is e’s depot. So EMU can get back after this trip. But if $l\prime$ does not exist, we remove the last trip task of $e$ and continue searching.

If $t_{\mathrm{arr}}^l\le t_{\mathrm{end}}$ , we search for another train task trip $l\prime$ as e’s following trip task, the arrival station of which is e’s depot. If $l\prime$ does not exist, we remove the last task trip and continue searching.

These operations aim to ensure that $e$ can return to its belonging depot at the end of the day.

Choosing rule

It is a rule about how to choose the next train task trip of EMUs. The candidate tasks should be those that have not been carried out by any EMU before, and their departure station must be e’s last train task trip l’s arrival station. These candidate trips constitute a candidate set $A_e$ for the EMU e. Then we choose one task from it according to the pheromone by formulation (18)

$${\tau }_{\mathrm{ll}\prime }=\{\begin{array}{cc}\frac{p_{\mathrm{ll}\prime }}{\sum p_{\mathrm{lr}}},\hfill & l\prime \in A_e,r\in L\hfill \\ \multicolumn{1}{c}{0,}& \mathrm{otherwise}\hfill \end{array}$$

(18)

Update pheromone

For every two train task trips in this solution, their corresponding pheromone increases by $Q/(C_{\mathrm{EMU}}+C_{\mathrm{delay}})$ in each iteration. Other train trips’ pheromones keep the same as before.

Evaporate pheromone

Every pheromone will decrease by a certain percentage in each iteration.

Revise the buffer time

At the start of the iterations, the buffer time should be set as the same relatively large value. In the real world, delays occur most frequently in the turn-around period, then in the maintenance period, and least in the running period. To save the capacity, we decrease the buffer time step by step in the following sequence: first, decrease buffer between headway, then maintenance, and finally turn-around.

• if ( $b_h=b_{\mathrm{ma}}$ and $b_{\mathrm{ma}}=b_{\mathrm{turn}-a}$ )

• $b_h=b_h-1$ ;

• else if ( $b_h<b_{\mathrm{ma}}$ and $b_{\mathrm{ma}}=b_{\mathrm{turn}-a}$ )

• $b_{\mathrm{ma}}=b_{\mathrm{ma}}-1$ ;

• else if ( $b_h=b_{\mathrm{ma}}$ and $b_{\mathrm{ma}}<b_{\mathrm{turn}-a}$ )

• $b_{\mathrm{turn}-a}=b_{\mathrm{turn}-a}-1$ .

Limit pheromone

If the pheromone exceeds the maximum pheromone, then we set the pheromone to the maximum value. Similarly, it will be set as the minimum value when it is less than that.

The pheromone $p_{\mathrm{ll}\prime }$ is defined as the probability of choosing the task trip $l\prime$ as the l’s following task with the same EMU, as shown in Figure 18(a). When choosing the first task trip of an EMU, we could introduce a dummy task trip at the start time as the preceding task of the first one in Figure 18(b). Then we calculate the probabilities between the task trips and the dummy one.

Figure 18.

(a) and (b) Definition of pheromone.

Algorithm steps

The main steps of the proposed ant colony algorithm are as follows: (1) obtain the initial solution and (2) get the relative optimal solution by iterations.

Initial solution

• (1) Initialize all pheromones with one initial value. Let $b_h=0$ , $b_{\mathrm{ma}}=0$ , and $b_{\mathrm{turn}-a}=0$ .

• (2) For e = 1 to number of EMUs do

From the train trip candidate set, we get one $l$ randomly, departing at the beginning of the day;

• while $(t_{\mathrm{arr}}^l\le t_{\mathrm{end}})$ do

•  We continue to choose another train trip randomly, which departs from l’s arrival station. Then we denote it as $l\prime$ ;

•  if ( $M_e\ge (1-2\alpha )·M_{\mathrm{ma}}$ and $s_{\mathrm{arr}}^{l\prime }$ has a depot)

•  e enters this depot to do maintenance. $M_e=0$ . $t_{\mathrm{dep}}^{l\prime }$ is set to $t_{\mathrm{arr}}^l+t_{\mathrm{ma}}$ ;

• else

•  We set $t_{\mathrm{dep}}^{l\prime }$ as $t_{\mathrm{arr}}^l+t_{\mathrm{turn}-a}$ ;

• while ( $l\prime$ has conflicts with another train task trip) do

•   $t_{\mathrm{dep}}^{l\prime }=t_{\mathrm{dep}}^{l\prime }+1$ ;

• End while

• If $(t_{\mathrm{arr}}^{l\prime }\le t_{\mathrm{end}})$

•   $l\prime$ is denoted as $l$ . $M_e=M_e+m_l$ ;

• Else

•  eenter its depot.

• End while

• End for

• (3) Update pheromone.

• (4) Evaporate pheromone.

Initialize the pheromone of each train.

Iteration

During the generation of the solution, two approaches can speed up the solving process and convergence.

• Approach 1. If the train with long traveling time departs late, little time might be left for the following trains to use. For example, in the purple part of Figure 19, due to the late departure of train 1, the following train’s arrival time might exceed the end of the timetable. Therefore, we should arrange the long-distance train to depart as early as possible.

• Approach 2. If the best solution’s objective value does not vary for many iterations, all the pheromones should be reset.

The iteration part is shown as follows:

• For r = 1 to number of iterations do

• For a = 1 to number of ants do

•   $b_h=3$ , $b_{\mathrm{ma}}=3$ , $b_{\mathrm{turn}-a}=3$

•  For e = 1 to number of EMUs do

•   Choose one train task trip by choosing rules based on the pheromone and $t_l$ .

•   Set its departure time at the start time of the timetable.

•   while $(t_{\mathrm{arr}}^l\le t_{\mathrm{end}})$ do

•    we choose another train task trip randomly, whose departure station is l’s arrival station, then defined as $l\prime$ ;

•    if ( $M_e\ge (1-2\alpha )·M_{\mathrm{ma}}$ and $s_{\mathrm{arr}}^{l\prime }$ has a depot)

•     e enters the depot to undertake maintenance. $M_e=0$ . We set $t_{\mathrm{dep}}^{l\prime }$ as $t_{\mathrm{arr}}^l+t_{\mathrm{ma}}+b_{\mathrm{ma}}$ ;

•    else

•     We set $t_{\mathrm{dep}}^{l\prime }$ as $t_{\mathrm{arr}}^l+t_{\mathrm{turn}-a}+b_{\mathrm{turn}-a}$ ;

•    while ( $l\prime$ has conflicts with another train task trip) do

•      $t_{\mathrm{dep}}^{l\prime }=t_{\mathrm{dep}}^{l\prime }+1$ ;

•    End while;

•    If $(t_{\mathrm{arr}}^{l\prime }\le 0.7·t_{\mathrm{end}})$

•     define $l\prime$ as $l$ . $M_e=M_e+m_l$ ;

•    Else

•     eenter its depot. End while;

•   End while

•  End for

•  If some train task trips are not carried out by an EMU, then revise the buffer time. $a=a-1$ . End for.

• If the solution is better than the best solution, then restore it as the best solution;

• If the best solution is the same for some iterations, then initialize the pheromones.

• End for

• Update pheromone;

• Evaporate pheromone;

• Limit pheromone;

• End for.

Figure 19.

Approach to speed up the solving process.

Comparison and analysis with GAMS

To compare with the result of the illustrative example, we list the solution generated by the improved algorithm below, with smaller EMU number than that produced by GAMS.

Trains’ trajectories are also shown below (Figure 20).

Figure 20.

Solution generated by the developed ant colony algorithm.

The proposed algorithm could get a relatively good solution with shorter time and less computational resources. That is suitable for railway corporations in practice, which prefer more efficiency in calculation to costing much time to obtain the optimal solution, especially in the complicated Chinese HSR networks.

Numerical experiment

Background

In this part, we tackle the sophisticated train timetabling and EMU circulation and maintenance scheduling problems in Chinese HSR. The railway network consists of one main line (thick line in Figure 21) and seven feeder railway lines. Depots located on the mainline or feeder lines are equipped with 20 or 10 sidetracks, respectively. The two biggest stations Beijing and Shanghai have 30 sidetracks and others 20. The traveling time between the stations and the nearest depots is 10 min.

Figure 21.

Railway network structure.

Because all of the trains are running on the main line, we consider only the trains’ departure and arrival times on the mainline. Then the departure and arrival times of feeder stations are easier to determine in practice.

The information on our computer’s CPU and RAM is as follows: the CPU—core i7-4770 3.40 GHz, and RAM—16 GB DDR3 1600 MHz.

Table 8 provides the running distance and time in each segment. Table 9 shows the line plan. The ant number is set to 30 and the iteration number is set to 30.

Table 8.

Running time and distance in segments.

Section name	Running distance (km)	Running time (min)	Section name	Running distance (km)	Running time (min)
[BJ, TJ]	131	26.2	[XZ, BB]	152	30.4
[TJ, CZ]	88	17.6	[BB, CHZ]	115	23
[CZ, JN]	187	37.4	[CHZ, NJ]	64	12.8
[JN, TA]	56	11.2	[NJ, WX]	178	35.6
[TA, QF]	71	14.2	[WX, SZ]	26	5.2
[QF, XZ]	159	31.8	[SZ, SS]	91	18.2

Table 9.

The line plan.

Stopping stations	Number of train task trips	Stopping stations	Number of train task trips
BJ→NJ→SS	13	SS→NJ→BJ	13
BJ→JN→NJ→SS	6	SS→NJ→JN→BJ	6
BJ→TJ→JN→XZ→NJ→SS	8	SS→NJ→XZ→JN→TJ→BJ	8
BJ→CZ→TA→QF→SZ→SS	8	SS→SZ→QF→TA→CZ→BJ	8
BJ→JN→BB→WX→SS	5	SS→WX→BB→JN→BJ	5
BJ→CZ→XZ→SZ→SS	5	SS→SZ→XZ→CZ→SS	5
BJ→JN→QD	3	QD→JN→BJ	3
BJ→NJ→HZ	3	HZ→NJ→BJ	3
BJ→JN→BB→HF	3	HF→BB→JN→SS	3
BJ→TJ→QHD	3	QHD→TJ→BJ	3
BJ→XZ→ZZ	3	ZZ→XZ→BJ	3
QD →JN→NJ→SS	3	SS →NJ→JN→QD	3
ZZ→XZ→WX→SS	3	SS→WZ→XX→ZZ	3
HF→NJ→SS	3	SS→NJ→HF	3

Result

Five convergences of solutions are displayed in Figure 22.

Figure 22.

Convergence graph.

From Table 10, the absolute gap between the minimum and maximum values is 1 and the relative gap is less than 1%. The computational time is nearly 21 sec for each calculation.

Table 10.

Five results of solutions.

Time	First	Second	Third	Fourth	Fifth
Objective value	990	989	989	989	990

The result of the best solution is shown in Figure 23, with 43 EMUs needed. The red connection lines represent the maintenance work and the green lines represent turn-around.

Figure 23.

The result of the numerical experiment.

Conclusion

In this article, we build an integrated train timetabling and EMU circulation and maintenance scheduling model based on the space–time–state structure. The mathematical model is solved by an improved ant colony algorithm effectively and efficiently. In contrast to the separate train timetabling and EMU circulation and maintenance scheduling models, the proposed model and the algorithm have the following improvements.

1. Using the time–space–state framework, we can construct both train timetable and EMU circulation and maintenance schedule simultaneously, which is more optimized than the traditionally independent method in EMU number and robustness of turn-around, maintenance, and headway.

2. Through the illustrative example and numerical experiment, it is implied that our algorithm can save time and memory to get a relatively good solution. Moreover, facing the real-world problem with a large scale, the algorithm can also exhibit good performance.