# Study on Comprehensive Optimization of Electric Multiple Unit Trains Passing Station Route and Rolling Stock Scheduling

Authors: Yajing Zheng; Zihan Ma; Wenzhou Jin
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

In order to overcome the contradiction between the rolling stock scheduling problem of EMU at a macro level and the problem of EMU train passing station route at a micro level in some special cases, this paper comprehensively optimizes the electric multiple unit train passing station route and rolling stock scheduling. By taking the operation of the Chinese high-speed railway EMU trains as the actual background and using the actual situation that the first-level inspection and repair cycle time is twice the cycle of a high-speed railway train timetable, based on the establishment of a 48-hour continuous network, a 0-1 type integer linear programming model is constructed. While obtaining the rolling stock scheduling of EMU trains, the EMU train passing station route scheme is obtained. The experimental results show that, compared with solving the problem in two stages, the comprehensive optimization according to the method in this paper can better ensure the feasibility of the passing station route scheme and provide decision support for the actual operation.


---

## Body

## 1. Introduction

The problem of electric multiple unit (EMU) train operation is divided into the rolling stock scheduling problem of EMU trains and the passing station route problem of EMU trains through the station.The rolling stock scheduling problem of EMU trains is similar to the rolling stock scheduling problem of the locomotive. Scholars generally transform the train diagram into a network structure and then use the multicommodity flow theory to solve it. The routing problem of EMU train passing the station can be decomposed into arrival operation route problem, occupying the arrival-departure track problem and departure operation route problem.In the daily operation management, the rolling stock scheduling problem of EMU trains is generally solved first, and then the passing station route problem of EMU trains through the station is solved on the basis of this problem. That is, the above two problems are generally solved at two levels. However, this method of dividing the EMU train operation problem into two different levels and optimizing these levels can reduce the optimization workload, but the feasibility of EMU train operation cannot be ensured.For example, Figure1 shows the rolling stock scheduling and the passing station route by using two-step optimization method on a certain day between Station A and Station B shown in Figure 2. In fact, the rolling stock scheduling shown in Figure 2 cannot be realized because when EMU 3 enters Station B after inspection and repair, two departure tracks of Station B are occupied by EMU 1 and EMU 2.Figure 1
Schematic diagram of rolling stock scheduling.Figure 2
Schematic diagram of rolling stock scheduling.This also indicates that if the classical two-step optimization method is adopted, the rolling stock scheduling or the passing station route very likely cannot be realized. In fact, on the premise of the original timetable and inspection and repair requirements of EMU 3, there is an achievable rolling stock scheduling and passing station routes as shown in Figure3.Figure 3
Schematic diagram of rolling stock scheduling.Therefore, in practical work, it is necessary to consider both the macro level rolling stock scheduling problem and the micro level train passing station route plan for optimization. In this way, not only can the feasibility of the rolling stock scheduling plan be guaranteed to the greatest extent, but also the centralization and automation of railway dispatching command can be further promoted.


## 2. Literature Review

From the current research of scholars, it is rare to comprehensively consider the rolling stock scheduling problem of EMU trains and the passing station route problem of EMU trains through the station; and there are more studies about the rolling stock scheduling problem of EMU trains or the passing station route problem of EMU trains through the station.In the study of the rolling stock scheduling problem, Ziarati et al. [1] were the first to report an Operations Research- (OR-) based approach to assign locomotives to segments using an arc-based multicommodity flow formulation. After that, Cordeau et al. [2, 3] also proposed an arc-based multicommodity flow model to assign locomotives and train departures. There should be emphasis placed on the fact that Abbink et al. [4] utilized an assignment-based approach rather than the multicommodity flow approach. Vaidyanathan et al. [5] made a representative research in 2007; they proposed a novel two-phase solution approach using linear, integer, and network programming. In this regard, the papers of Alfieri et al. [6] and Fioole et al. [7] are notable contributions, as they were the first papers to include train compositions in the developed approaches, and these researches are close to the rolling stock scheduling problem of EMU trains in this paper. At the same time, scholars began to consider maintenance. For example, Maroti et al. [8, 9] first gave a fixed rolling stock schedule as the basis of a directed graph, and then the models are developed to modify the schedule by inserting maintenance tasks into this directed graph so that the units close to its mileage maintenance restriction can arrive at a maintenance facility in time. In an optimization-based approach, Wang et al. [10] utilized the Dantzig-Wolfe Decomposition to study distance-based maintenance routing. Li et al. [11] described a heuristic using column generation to reach a multicommodity flow formulation, which is applied to a French case study to route trains with distance-based maintenance restrictions. Giacco et al. [12] modeled the problem of punctuality of maintenance as a minimal cost Hamiltonian cycle problem. On this foundation, Nishi et al. [13] used a column generation based heuristic approach instead of using a commercial solver to solve a mathematical model. With the construction of the world’s largest high-speed railway network in China, a large number of studies on China’s high-speed railway began to emerge. For example, literature [14] is one of the representatives. Because passengers have to face huge challenging variables generated by unexpectedness, such as weather and equipment failure, many scholars have also promoted the research of rolling stock schedule to the field of train rescheduling. For example, Meng et al. [15], Stoilova [16] and Li et al. [17] have made contributions in this regard.In the study of the passing station route problem, Carey [18] used linear programming to optimize the operation route, occupation of arrival-departure track, and departure operation route. Kroon et al. [19] considered the problem of a train passing the station route from different perspectives, abstracted this problem as a node encapsulation problem, and established the integer programming model of the problem. Zwaneveld et al. [20] transformed the problem into a WNPP (weighted node packing problem) model. Corman et al. [21] studied the adjustment problem of station operation plan in the case of emergency, aiming at minimizing the delay time of a train, and realized the dynamic adjustment of the station operation plan by adjusting the stop time, train speed, arrival sequence, and route allocation. Zhou and Teng [22] applied the Lagrangian relaxation decomposition method to the train to study the route assignment and timetable of passenger trains in the railway network composed of single-way and two-way tracks. By using mixed-integer linear programming and job shop scheduling theory, Zeng et al. [23] constructed a multicriteria station access allocation model without morning and evening time windows and a station access allocation model with morning and evening time windows. In addition, Li et al. [24] optimized the access route of a depot and the application of arrival-departure track in the depot and also further expanded the scope of application of the problem of EMU train passing the route.Although the rolling stock scheduling problem of EMU trains and the passing station route problem of EMU trains have been more in-depth, the research on the combination of the two is still relatively rare. Although the above-mentioned treatment methods that divide the problem of EMU train operation into two different levels and optimize these levels separately can reduce optimization workload, they do not guarantee the feasibility of EMU train operation. Therefore, this paper combines the research of the rolling stock scheduling problem of EMU trains and the passing station route problem of EMU trains to ensure the feasibility of relevant schemes.


## 3. Problem Definition and Analysis

### 3.1. Inspection and Repair of EMU Trains

In order to ensure both safety and reliability of EMU train scheduling, an economical and reasonable inspection and repair system is necessary. At present, the inspection and repair work of China EMU trains can be roughly divided into five levels, as shown in Table1.Table 1
The inspection and repair work of China EMU trains.
TypeLevel ILevel IILevel IIILevel IVLevel VCRH1/CRH380D≤ (4000 + 400) km or 48 hours15 days(1200 ± 100) thousand km or three years(2400 ± 100) thousand km or six years(4800 ± 100) thousand km or 12 yearsCRH2/CRH380A≤ (4000 + 400) km or 48 hours30,000 km or 30 days(600 + 20/-50) thousand km or 1.5 years(1200 + 50/-100) thousand km or three years(2400 ± 100) thousand km or six yearsCRH3/CRH380B≤ (4000 + 400) km or 48 hours20,000 km(1200 ± 120) thousand km or three years(2400 ± 120) thousand km or six years(4800 ± 120) thousand km or 12 yearsCRH5/CRH380C≤ (5000 + 500) km or 48 hours60,000 km(1200 ± 120) thousand km or three years(2400 ± 120) thousand km or three years(4800 ± 120) thousand km or 12 yearsNotes: China Railway Group Limited [25].In Table1, except for the staying time of the first-level inspection and repair, that is, four hours, the staying times of the second and higher inspection and repair levels are far longer than the current timetable cycle of China Railway High-speed, which is 24 hours. Therefore, EMU trains in the second- and higher-level inspection and repair can be directly replaced by standby EMU trains without considering it in the formulation of the rolling stock scheduling plan. In other words, in the process of rolling stock scheduling optimization, only the influence of the first-level inspection and repair work needs to be considered. The detailed system of the first-level inspection and repair of EMU trains in China is as follows. First, the time interval and accumulated mileage of two first-level inspection and repair of EMU trains shall not exceed the interval and accumulated mileage specified for the first-level inspection and repair. Second, the first-level inspection and repair of EMU trains must be carried out in a specific inspection and repair base, and the staying time in the inspection and repair base shall not be less than that of the first-level inspection and repair duration, which is four hours. If the running mileage is taken as a constraint condition of the first-level inspection and repair to optimize the turnover plan, the nature of the optimization model of rolling stock scheduling will change from linear to nonlinear, so it will be difficult to solve. With the maturity of EMU train technology in China, the accumulated mileage of the first-level inspection and repair of EMU trains has increased accordingly. Based on this, by using the method of Wang et al. [26] and assuming the actual situation that the first-level inspection and repair cycle time (48 hours) is exactly twice the cycle of high-speed railway timetable, this paper establishes the rolling stock scheduling connection network with a time span of 48 hours. For the convenience of calculation and description, the starting and ending times of the high-speed railway timetable are set to 0 : 00, and the time between them is called the crossing time, which is used as a basis of the optimization scheme in this paper.


### 3.2. Relationship between Rolling Stock Scheduling and Train Passing Station Route Schemes

The route optimization of the train passing the station is a comprehensive optimization of the route arrangement of the arrival-departure operation and application of the arrival-departure track. This problem can be simply described as arranging EMU trains with overlapping stoppage time (including entry and exit times) at stations on different arrival-departure tracks, as shown in Figure4(a), or as arranging trains with time-space conflicts in the arrival-departure process on the entry and exit routes that can be operated in parallel. As long as the corresponding arrival and departure routes meet the compatibility of station turnouts in terms of time, the operation scheme of the arrival-departure track shown in Figure 4(a) and the turnover scheme shown in Figure 4(b), where the turnover connecting line corresponds to the arrival-departure line of the station, can be unified. In other words, when determining the rolling stock scheduling plan, the train passing station route plan can also be determined.Figure 4
The comparison diagram of the application scheme of arrival-departure track and the rolling stock scheduling connection scheme. (a) Schematic diagram of the application scheme of arrival-departure track. (b) Schematic diagram of the rolling stock scheduling connection.
(a)(b)


### 3.3. Compatibility Analysis of Train Passing Station Route

As the route arrangement scheme of the arrival operation directly determines the arrival-departure track occupied by a passenger train, the compatibility of a train passing station route is reflected in the compatibility of arrival-departure track operation and turnout occupation. Namely, an arrival-departure track can only be occupied by one EMU train at the same time, and a group of switches can only be occupied by one EMU train at the same time. When describing the occupation compatibility of an arrival-departure track, there is a need to determine a specific track occupied by EMU train and the occupation time. The specific track occupied by the EMU train is determined by the arrival and departure routes, and the occupation time is determined by the rolling stock scheduling plan; the compatibility of turnout occupation is determined by the specific turnout occupied by receiving departure operation and occupation time. The specific calculation method can be found in the work of Kroon et al. [10].


## 3.1. Inspection and Repair of EMU Trains

In order to ensure both safety and reliability of EMU train scheduling, an economical and reasonable inspection and repair system is necessary. At present, the inspection and repair work of China EMU trains can be roughly divided into five levels, as shown in Table1.Table 1
The inspection and repair work of China EMU trains.
TypeLevel ILevel IILevel IIILevel IVLevel VCRH1/CRH380D≤ (4000 + 400) km or 48 hours15 days(1200 ± 100) thousand km or three years(2400 ± 100) thousand km or six years(4800 ± 100) thousand km or 12 yearsCRH2/CRH380A≤ (4000 + 400) km or 48 hours30,000 km or 30 days(600 + 20/-50) thousand km or 1.5 years(1200 + 50/-100) thousand km or three years(2400 ± 100) thousand km or six yearsCRH3/CRH380B≤ (4000 + 400) km or 48 hours20,000 km(1200 ± 120) thousand km or three years(2400 ± 120) thousand km or six years(4800 ± 120) thousand km or 12 yearsCRH5/CRH380C≤ (5000 + 500) km or 48 hours60,000 km(1200 ± 120) thousand km or three years(2400 ± 120) thousand km or three years(4800 ± 120) thousand km or 12 yearsNotes: China Railway Group Limited [25].In Table1, except for the staying time of the first-level inspection and repair, that is, four hours, the staying times of the second and higher inspection and repair levels are far longer than the current timetable cycle of China Railway High-speed, which is 24 hours. Therefore, EMU trains in the second- and higher-level inspection and repair can be directly replaced by standby EMU trains without considering it in the formulation of the rolling stock scheduling plan. In other words, in the process of rolling stock scheduling optimization, only the influence of the first-level inspection and repair work needs to be considered. The detailed system of the first-level inspection and repair of EMU trains in China is as follows. First, the time interval and accumulated mileage of two first-level inspection and repair of EMU trains shall not exceed the interval and accumulated mileage specified for the first-level inspection and repair. Second, the first-level inspection and repair of EMU trains must be carried out in a specific inspection and repair base, and the staying time in the inspection and repair base shall not be less than that of the first-level inspection and repair duration, which is four hours. If the running mileage is taken as a constraint condition of the first-level inspection and repair to optimize the turnover plan, the nature of the optimization model of rolling stock scheduling will change from linear to nonlinear, so it will be difficult to solve. With the maturity of EMU train technology in China, the accumulated mileage of the first-level inspection and repair of EMU trains has increased accordingly. Based on this, by using the method of Wang et al. [26] and assuming the actual situation that the first-level inspection and repair cycle time (48 hours) is exactly twice the cycle of high-speed railway timetable, this paper establishes the rolling stock scheduling connection network with a time span of 48 hours. For the convenience of calculation and description, the starting and ending times of the high-speed railway timetable are set to 0 : 00, and the time between them is called the crossing time, which is used as a basis of the optimization scheme in this paper.


## 3.2. Relationship between Rolling Stock Scheduling and Train Passing Station Route Schemes

The route optimization of the train passing the station is a comprehensive optimization of the route arrangement of the arrival-departure operation and application of the arrival-departure track. This problem can be simply described as arranging EMU trains with overlapping stoppage time (including entry and exit times) at stations on different arrival-departure tracks, as shown in Figure4(a), or as arranging trains with time-space conflicts in the arrival-departure process on the entry and exit routes that can be operated in parallel. As long as the corresponding arrival and departure routes meet the compatibility of station turnouts in terms of time, the operation scheme of the arrival-departure track shown in Figure 4(a) and the turnover scheme shown in Figure 4(b), where the turnover connecting line corresponds to the arrival-departure line of the station, can be unified. In other words, when determining the rolling stock scheduling plan, the train passing station route plan can also be determined.Figure 4
The comparison diagram of the application scheme of arrival-departure track and the rolling stock scheduling connection scheme. (a) Schematic diagram of the application scheme of arrival-departure track. (b) Schematic diagram of the rolling stock scheduling connection.
(a)(b)


## 3.3. Compatibility Analysis of Train Passing Station Route

As the route arrangement scheme of the arrival operation directly determines the arrival-departure track occupied by a passenger train, the compatibility of a train passing station route is reflected in the compatibility of arrival-departure track operation and turnout occupation. Namely, an arrival-departure track can only be occupied by one EMU train at the same time, and a group of switches can only be occupied by one EMU train at the same time. When describing the occupation compatibility of an arrival-departure track, there is a need to determine a specific track occupied by EMU train and the occupation time. The specific track occupied by the EMU train is determined by the arrival and departure routes, and the occupation time is determined by the rolling stock scheduling plan; the compatibility of turnout occupation is determined by the specific turnout occupied by receiving departure operation and occupation time. The specific calculation method can be found in the work of Kroon et al. [10].


## 4. Rolling Stock Scheduling Problem Model

According to the current operation of the China Railway High-speed, the research of this paper is based on the following premises:①
The target timetable is a 24-hour periodic timetable, and the running lines in the timetable have the same speed level.②
The EMU trains shall not be reconnected and reorganized during the operation.③
In the target section, the number of EMU trains in the up direction is equal to the number in the down direction; that is to say, there is no need to consider the feedback scheme of empty EMU trains in the target section.Then, the corresponding research network of this paper is constructed according to the following steps.Step 1.
Consider the train timetable shown in Figure5, where station A and station D are turn-back stations, station B is the station where the depot is located, and station C is the intermediate station, as dividing points to divide the EMU train timetable, as shown in Figure 6.Figure 5
The original train timetable.Figure 6
The divided train timetable.Step 2.
Transfer each running line in the section between two adjacent stations into a node (e.g., nodes 1, 2, 3, 4, 5, and 6 in Figure7, which are called the running line nodes); and add two virtual nodes on the left and right sides of each turn-back station, starting and terminal station, and the station where the depot is located in the train timetable (e.g., nodes 7, 8, 9, 10, 11, and 12 in Figure 7).Figure 7
Schematic diagram of converting the running lines in the train timetable into nodes.Step 3.
Connect the nodes belonging to the same EMU train according to the operation time, as shown in Figure8, where directed arc a is from node 5 to node 3, and directed arc b is from node 4 to node 6. In this paper, the connection constructed in this step is called the train arc, which represents the connection relationship of the same EMU train in the nodes constructed above.Figure 8
Schematic diagram of the train arcs.Step 4.
Connect relevant nodes based on the possibility of rolling stock scheduling between nodes, as shown in Figure9, where directed arc c from node 3 to node 4, directed arc d from node 3 to node 2, and directed arc e from node 9 to node 5 are called the connecting arcs, which means the train stops at the corresponding stations. In particular, among these connection arcs, the arc with one end as a virtual node, such as arc c and arc d, is called the incomplete connection arc, and the arc with both ends as virtual nodes, such as arc e, is called the complete connection arc.Figure 9
Schematic diagram of the connection arc.Step 5.
Connect relevant nodes based on the possibility of rolling stock scheduling between nodes and inspection and repair of the station where the depot is located, as shown in Figure10, where directed arc f from node 3 to node 4 is called the inspection and repair arc, and it indicates the process of a train entering the depot for the purpose of inspection and repair; in Figure 10, the difference between directed arcs c and f is that directed arc c indicates that the train stops at station B, while directed arc f indicates that the train enters the depot for inspection and repair at station B. Similar to the connecting arc, the inspection and repair arc is also divided into complete inspection and repair arc and incomplete inspection and repair arc.
In the presented model, if the use of EMU train is regarded as a flow, the rolling stock scheduling problem of EMU trains can be transformed into a network flow problem. Therefore, the constructed network is called the rolling stock scheduling optimization network of EMU trains in this paper.Figure 10
Schematic diagram of the inspection and repair arc.


## 5. Comprehensive Optimization Model of EMU Trains Passing Station Route and Rolling Stock Scheduling

### 5.1. Variables and Parameters

The set of stations is denoted asS=sc,c=1,2,⋯,ε. In particular, the EMU train performs the first-level inspection and repair at station sΩ where the depot is located and turns back at the first and last stations in set S which are denoted by s1 and sε. Define direction from s1 to sξ as the down direction of the section; then, the down direction section set is expressed as Πdown=sc,sc+1,c=1,2,⋯,ε−1. Similarly, the up direction section set is expressed as Πup=sc+1,sc,c=1,2,⋯,ε−1.Copy the 24-hour timetable once, and expand it to 48 hours such that the leftmost side of the extended timetable is the coordinate origin of time, corresponding to the time of zero, and the rightmost side is the coordinate endpoint of time, corresponding to the time of 2880 min. The relevant time in the timetable is taken according to the value of 2880 min. The set of running lines in the down direction is denoted asLdown=lidown,i=1,2,⋯,2α, where α denotes the numbers of running lines in the down direction in the 24-hour train timetable, respectively; similarly, the set of running lines in the up direction is denoted as Lup=liup,i=1,2,⋯,2β.According to the steps presented in Chapter 3, convert the running linelidown in section sc,sc+1 into a running line node Θic,c+1; similarly, the running line liup in section sc+1,sc is converted into a running line node Θic+1,c.The start time of nodeΘic,c+1, that is, the time when the running line lidown enters section sc,sc+1, is denoted as tric,c+1; similarly, the end time of node Θic,c+1 is denoted as tcic,c+1. tric+1,c and tcic+1,c have similar meanings to tric,c+1 and tcic,c+1.Two virtual nodesΘOc,c and ΘDc,c are added to the left and right sides of the horizontal line represented by station sc in the illustrated train timetable. Obviously, the departure time of node ΘOc,c is tcOc,c=0 and the entry time of node ΘOc,c is trDc,c=2880min.The connection process of train (connecting arc or train arc) from nodeΘi1c1,c to node Θi2c,c2 is denoted as 0-1 parameter ac1,c,i1c,c2,i2, where c1=c±1, or c1=c; c2=c±1 or c2=c; if the connection process has the possibility of existence, then ac1,c,i1c,c2,i2=1; otherwise, ac1,c,i1c,c2,i2=0.The connection process of train (inspection and repair arc) from nodeΘi1c1,Ω to node Θi2Ω,c2 is denoted as 0-1 parameter bc1,Ω,i1Ω,c2,i2, where c1=Ω±1 or c1=Ω; c2=Ω±1 or c2=Ω; if the connection process has the possibility of existence, then bc1,Ω,i1Ω,c2,i2 equals one; otherwise, it equals zero.Obviously, as long as the values of the parametersac1,c,i1c,c2,i2 and bc1,Ω,i1Ω,c2,i2 are determined, the rolling stock scheduling optimization network can be constructed.The connection time from nodesΘi1c1,c to Θi2c,c2 is denoted as parameter dc1,c,i1c,c2,i2, and its value can be obtained by tri2c,c2−tci1c1,c.The standard connection time of an EMU train turnover from directionc1⟶c to direction c⟶c2 at station c is denoted as parameter Λc1,cc,c2. Λc1,cc,c2 involves different operations, including emptying the passengers, cleaning the cars, handing over to the crew, and initiating waiting for passengers after the EMU train arrives. The standard time involves different operations, including emptying the passengers, cleaning the cars, handing over the cars to the stewards, and initiating waiting for passengers after the EMU train arrives. Similarly, parameter Δc1,ΩΩ,c2 denotes the standard time for the inspection and repair of EMU trains connection at station sΩ from direction c1⟶Ω to direction Ω⟶c2. Δc1,ΩΩ,c2 involves the following operations: emptying the passengers, cleaning the cars, entering and exiting the vehicle depot, and initiating waiting for passengers after the EMU train arrives at station sΩ.The set of EMU trains is denoted asE=em,m=1,2,⋯,γ, where em refers to the EMU train with the number m.The set of the tracks in stationsc is denoted as Gc=gwc,w=1,2,⋯,ϕ, where gwc refers to the track with the number w.Define 0-1 parameterδc1,ci1⟶c,cDc,cO⟶c,c2i2, such that when c1=c±1, c2=c±1, and dc1,c,i1c,c,D+dc,c,Oc,c2,i2≥Λc1,cc,c2, the parameter δc1,ci1⟶c,cDc,cO⟶c,c2i2=1; otherwise, δc1,ci1⟶c,cDc,cO⟶c,c2i2=0. This parameter indicates whether incomplete connecting arc ac,c,Oc,c1,i1 and incomplete connecting arc ac1,c,i1c,c,D can form a complete connecting arc; one indicates that this arc can be formed.Define the 0-1 parameterσc1,Ωi1⟶Ω,ΩDΩ,ΩO⟶Ω,c2i2, such that when c1=Ω±1, c2=Ω±1, and dc1,Ω,i1Ω,Ω,D+dΩ,Ω,OΩ,c2,i2≥Δc1,ΩΩ,c2, σc1,Ωi1⟶Ω,ΩDΩ,ΩO⟶Ω,c2i2=1; otherwise, σc1,Ωi1⟶Ω,ΩDΩ,ΩO⟶Ω,c2i2=0. This parameter indicates whether inspection and repair arc bΩ,Ω,OΩ,c2,i2 and inspection and repair arc bc1,Ω,i1Ω,Ω,D can form a complete inspection and repair arc; one indicates that this arc can be formed.Define the 0-1 decision variableqm,ac1,c,i1⟶c,c2,i2. If qm,ac1,c,i1⟶c,c2,i2=1, it means that train em passes through the arc ac1,c,i1c,c2,i2; otherwise, train em does not pass through the arc ac1,c,i1c,c2,i2. Similarly, define the 0-1 decision variable qm,bc1,Ω,i1⟶Ω,c2,i2. If qm,bc1,Ω,i1⟶Ω,c2,i2=1, it means that train em passes through the arc bc1,Ω,i1Ω,c2,i2; otherwise, train em does not pass through the arc bc1,Ω,i1Ω,c2,i2.Define the 0-1 decision variableρm,a,wc1,c,i1⟶c,c2,i2. If ρm,a,wc1,c,i1⟶c,c2,i2=1, it means that qm,ac1,c,i1⟶c,c2,i2=1 and the process represented by qm,ac1,c,i1⟶c,c2,i2 occupies the arrival-departure track w of station sc. Similarly, define the 0-1 decision variable ρm,b,wc1,Ω,i1⟶Ω, and its meaning is similar to that of decision variable ρm,a,wc1,c,i1⟶c,c2,i2.Define the 0-1 decision variableκpc1,c,i1⟶w. If κpc1,c,i1⟶w=1, it means that there is a route p from node Θi1c1,c to enter track w of station sc. Similarly, define 0-1 decision variable κpw⟶c,c1,i1, and its meaning is similar to that of decision variable κpc1,c,i1⟶w.Define the 0-1 decision variableψpc1,Ω,i1|w⟶Ω. If ψpc1,Ω,i1|w⟶Ω=1, it means that route p is selected when the EMU train enters the depot from node Θi1c1,Ω through the arrival-departure track w of station SΩ. Similarly, define the 0-1 decision variable ψpΩ,c1,i1|Ω⟶w, and its meaning is similar to that of decision variable ψpc1,Ω,i1|w⟶Ω.Define the 0-1 parameterχc1,c,i1⟶c,c2,i2c3,c,i3⟶c,c4,i4, such that ac3,c,i3c,c4,i4 and ac1,c,i1c,c2,i2 can be completed on the same track; the parameter χc1,c,i1⟶c,c2,i2c3,c,i3⟶c,c4,i4=1; otherwise, χc1,c,i1⟶c,c2,i2c3,c,i3⟶c,c4,i4=0. Similarly, define the 0-1 parameters: χc1Ω,i1⟶Ωc2,Ω,i2⟶Ω, χΩ⟶Ω,c1,i1Ω⟶Ω,c2,i2, χc1,Ω,i1⟶Ω,c2,i2c3,Ω,i3⟶Ω, χc1,Ω,i1⟶Ω,c2,i2Ω⟶Ω,c3,i3, and χΩ⟶c,c1,i1c2,c,i2⟶Ω.Define the 0-1 parameterγc1,c⟶w2|p2c1,c⟶w1|p1, such that the route associated with κp1c1,c,i1⟶w1 and the route associated with κp2c1,c,i2⟶w2 are compatible; the parameter γc1,c⟶w2|p2c1,c⟶w1|p1=1; otherwise, γc1,c⟶w2|p2c1,c⟶w1|p1=0. Similarly, define the 0-1 parameters: γw2⟶c,c1,i2|p2c1,c,i1⟶w1|p1, γw2⟶c,c1,i2|p2w1⟶c,c1,i1|p1, γc2,Ω,i2|w2⟶Ω|p2c1,Ω,i1|w1⟶Ω|p1, γΩ,c2,i2|Ω|⟶w2|p2Ω,c1,i1|Ω|⟶w1|p1, γΩ,c2,i2|Ω⟶w2|p2c1,Ω,i1|w1⟶Ω|p1, γΩ,c2,i2|Ω⟶w2|p2c1,Ω,i1⟶w1|p1, γc2,Ω,i2|w2⟶Ω|p2c1,Ω,i1⟶w1|p1, γΩ,c2,i2|Ω⟶w2|p2w1⟶Ω,c1,i1|p1, and γc2,Ω,i2|w2⟶Ω|p2w1⟶c,c1,i1|p1.The unit time utility value of the route associated withκpc1,c,i1⟶w is denoted as vpc1,c⟶w; the value of this parameter can be determined based on the route direction, whether crossing the mainline, and other factors. Similarly, define parameter vpw⟶c1,c.The unit time utility value of the route from trackw of station sΩ to the depot is denoted as ypw⟶Ω; the value of this parameter can be determined based on the position relationship between the arrival-departure track and the depot. Similarly, define parameter ypΩ⟶w.The unit time utility value of the connection arcac1,c,i1c,c2,i2 that stops on track w of station sc is denoted as uwc1,c⟶c,c2; the value of this parameter can be determined based on the position relationship between the track and the station entrance.


### 5.2. Rolling Stock Scheduling Connection Constraints

①
The EMU train entering running line nodeΘi2c2,c3 must exit from the same running line node:(1)∑Θi1c1,c2qm,ac1,c2,i1⟶c2,c3,i2+qm,bc1,c2,i1⟶c2,c3,i2=∑Θi3c3,c4qm,ac2,c3,i2⟶c3,c4,i3+qm,bc2,c3,i2⟶c3,c4,i3∀em,Θi2c2,c3,where:c2≠c3,②
Running lineΘi2c2,c3 must have one EMU train passing by(2)∑em∑Θi1c1,c2qm,ac1,c2,i1⟶c2,c3,i2+qm,bc1,c2,i1⟶c2,c3,i2=1∀Θi2c2,c3,where:c2≠c3.③
The timetable takes 48 hours as a cycle. Thus, if it is strictly required that each EMU train starts from a left virtual nodeΘOc,c, it will enter the corresponding right virtual node ΘDc,c:(3)∑Θi2c,c2qm,ac,c,O⟶c,c2,i2+qm,bc,c,O⟶c,c2,i2,=∑Θi1c1,cqm,ac1,c,i1⟶c,c,D+qm,bc1,c,i1⟶c,c,D∀m,ΘOc,c,ΘDc,c.④
Any EMU train can appear at most once at all left virtual nodes:(4)∑ΘOc,c∑Θi1c,c1qm,ac,c,O⟶c,c1,i1+qm,bc,c,O⟶c,c1,i1≤1∀em⑤
The EMU train starting from a left virtual node must go through an inspection and repair arc only once in 48 hours:(5)∑ΘOΩ,Ω∑ΘiΩ,cqm,aΩ,Ω,O⟶Ω,c,i+qm,bΩ,Ω,O⟶Ω,c,i=∑Θi1x1,Ω∑Θi2Ω,x2bx1,Ω,i1Ω,x2,i2⋅qm,bx1,Ω,i1⟶Ω,x2,i2∀em,x1≠Ω,i1≠O.Since an inspection and repair arc of the left virtual node and an inspection and repair arc of the right virtual node are calculated repeatedly, the right side of (5) needs to omit the left or the right virtual node. That is, x1≠Ω and i1≠O in equation (5).⑥
EMU trains must be on an inspection and repair or connection arc, which is expressed as follows (taking the connecting arc as the example, the constraint formula of the inspection and repair edge is similar to it):(6)∑emqm,ax1,c,i1⟶c,x2,i2≤ax1,c,i1c,x2,i2⑦
The connection requirements should be met at the crossing time, which is expressed as follows (taking the connecting arc as the example, the constraint formula of the inspection and repair edge is similar to it):(7)qm,ax1,ci1⟶c,cD+qm,ac,cO⟶c,x2i2≤1+δx1,ci1⟶c,cDc,cO⟶c,x2i2.


### 5.3. Constraints on the Route of the Train Passing through the Station

①
The path of the train passing through the station and the path of entering and leaving the depot need to stop or pass through a station track:(8)qm,ac1,c,i1⟶c,c2,i2=∑wρm,a,wc1,c,i1⟶c,c,D,qm,bc1,Ω,i1⟶Ω,c2,i2=∑wρm,b,wc1,Ω,i1⟶Ω,qm,bc1,Ω,i1⟶Ω,c2,i2=∑wρm,b,wΩ⟶Ω,c2,i2.②
The access trackw must be realized through a path connected to it:(9)∑mρm,a,wc1,c,i1⟶c,c2,i2=∑pκpc1,c,i1⟶w,∑mρm,a,wc1,c,i1⟶c,c2,i2=∑pκpw⟶c,c2,i2,∑mρm,b,wc1,Ω,i1⟶Ω=∑pκpc1,Ω,i1⟶w,∑mρm,b,wc1,Ω,i1⟶Ω=∑pψpc1,Ω,i1|w⟶Ω,∑mρm,b,wΩ⟶Ω,c2,i2=∑pκpw⟶Ω,c2,i2,∑mρm,b,wΩ⟶Ω,c1,i1=∑pψpΩ,c1,i1|Ω⟶w.③
Constraints of the arrival-departure track compatibility are expressed as follows (taking two EMU trains passing through the station as an example, other situations are similar to it):(10)ρm1,a,wc1,c,i1⟶c,c2,i2+ρm2,a,wc3,c,i3⟶c,c4,i4+χc1,c,i1⟶c,c2,i2c3,c,i3⟶c,c4,i4≤2.④
The stopping or passing process with overlapping time cannot be realized on the same track or the same switch:(11)κp1c1,c,i1⟶w1+κp2c1,c,i2⟶w2+γc1,c,i2⟶w2|p2c1,c,i1⟶w1|p1≤2,κp1c1,c,i1⟶w1+κp2w2⟶c,c1,i2+γw2⟶c,c1,i2|p2c1,c,i1⟶w1|p1≤2,κp1w1⟶c,c1,i1+κp2w2⟶c,c1,i2+γw2⟶c,c1,i2|p2w1⟶c,c1,i1|p1≤2,ρm1,a,wc1,c,i1⟶c,c2,i2+ρm2,a,wc3,c,i3⟶c,c4,i4+χc1,c,i1⟶c,c2,i2c3,c,i3⟶c,c4,i4≤2,ρm1,b,wc1,Ω,i1⟶Ω+ρm2,b,wc2,Ω,i2⟶Ω+χc1,Ω,i1⟶Ωc2,Ω,i2⟶Ω≤2,ρm1,b,wΩ⟶Ω,c1,i1+ρm2,b,wΩ⟶Ω,c2,i2+χΩ⟶Ω,c1,i1Ω⟶Ω,c2,i2≤2,ρm1,a,wc1,Ω,i1⟶Ω,c2,i2+ρm2,b,wc3,Ω,i3⟶Ω+χc1,Ω,i1⟶Ω,c2,i2c3,Ω,i3⟶Ω≤2,ρm1,a,wc1,Ω,i1⟶Ω,c2,i2+ρm2,b,wΩ⟶Ω,c3,i3+χc1,Ω,i1⟶Ω,c2,i2Ω⟶Ω,c3,i3≤2,ρm1,b,wΩ⟶c,c1,i1+ρm2,b,wc2,c,i2⟶Ω+χΩ⟶c,c1,i1c2,c,i2⟶Ω≤2,ψp1c1,Ω,i1|w1⟶Ω+ψp2c2,Ω,i2|w2⟶Ω+γc2,Ω,i2|w2⟶Ωp2c1,Ω,i1|w1⟶Ωp1≤2,ψp1Ω,c1,i1|Ω⟶w1+ψp2Ω,c2,i2|Ω⟶w2+γΩ,c2,i2|Ω⟶w2p2Ω,c1,i1|Ω⟶w1p1≤2,ψp1c1,Ω,i1|w1⟶Ω+ψp2Ω,c2,i2|Ω⟶w2+γΩ,c2,i2|Ω⟶w2p2c1,Ω,i1|w1⟶Ωp1≤2,κp1c1,Ω,i1⟶w1+ψp2Ω,c2,i2|Ω⟶w2+γΩ,c2,i2|Ω⟶w2p2c1,Ω,i1⟶w1p1≤2,κp1c1,Ω,i1⟶w1+ψp2c2,Ω,i2|w2⟶Ω+γc2,Ω,i2|w2⟶Ωp2c1,Ω,i1⟶w1p1≤2,κp1w1⟶Ω,c1,i1+ψp2Ω,c2,i2|Ω⟶w2+γΩ,c2,i2|Ω⟶w2p2w1⟶Ω,c1,i1p1≤2,κp1w1⟶c,c1,i1+ψp2c2,Ω,i2|w2⟶Ω+γc2,Ω,i2|w2⟶Ωp2w1⟶c,c1,i1p1≤2.


### 5.4. Optimization Objectives

①
Minimize the number of EMU trains in the operation:(12)minZ1=∑m∑Θi1c,c1qm,ac,c,O⟶c,c1,i1+∑Θi2Ω,c2qm,bΩ,Ω,O⟶Ω,c2,i2.②
Maximize the utility of arrival-departure tracks and turnouts:(13)maxZ2=∑Θi1c1,c∑pvpc1,c⟶w,κpc1,c,i1⟶w+∑Θi1c1,c∑wvpw⟶c1,c⋅κpw⟶c1,c,i1+∑Θi1c1,Ω∑pypΩ⟶w⋅ψpΩ,c1,i1|Ω⟶w+∑Θi1Ω,c1∑pypΩ⟶w⋅ψpΩ,c1,i1|Ω⟶w+∑w∑m∑ac1,c,i1c,c2,i2uwc1,c⟶c,c2⋅ρm,a,wc1,c,i1⟶c,c2,i2.The model presented in this section is a 0-1 integer linear programming model, which can be solved by commercial optimization software, such as ILOG CPLEX software.


## 5.1. Variables and Parameters

The set of stations is denoted asS=sc,c=1,2,⋯,ε. In particular, the EMU train performs the first-level inspection and repair at station sΩ where the depot is located and turns back at the first and last stations in set S which are denoted by s1 and sε. Define direction from s1 to sξ as the down direction of the section; then, the down direction section set is expressed as Πdown=sc,sc+1,c=1,2,⋯,ε−1. Similarly, the up direction section set is expressed as Πup=sc+1,sc,c=1,2,⋯,ε−1.Copy the 24-hour timetable once, and expand it to 48 hours such that the leftmost side of the extended timetable is the coordinate origin of time, corresponding to the time of zero, and the rightmost side is the coordinate endpoint of time, corresponding to the time of 2880 min. The relevant time in the timetable is taken according to the value of 2880 min. The set of running lines in the down direction is denoted asLdown=lidown,i=1,2,⋯,2α, where α denotes the numbers of running lines in the down direction in the 24-hour train timetable, respectively; similarly, the set of running lines in the up direction is denoted as Lup=liup,i=1,2,⋯,2β.According to the steps presented in Chapter 3, convert the running linelidown in section sc,sc+1 into a running line node Θic,c+1; similarly, the running line liup in section sc+1,sc is converted into a running line node Θic+1,c.The start time of nodeΘic,c+1, that is, the time when the running line lidown enters section sc,sc+1, is denoted as tric,c+1; similarly, the end time of node Θic,c+1 is denoted as tcic,c+1. tric+1,c and tcic+1,c have similar meanings to tric,c+1 and tcic,c+1.Two virtual nodesΘOc,c and ΘDc,c are added to the left and right sides of the horizontal line represented by station sc in the illustrated train timetable. Obviously, the departure time of node ΘOc,c is tcOc,c=0 and the entry time of node ΘOc,c is trDc,c=2880min.The connection process of train (connecting arc or train arc) from nodeΘi1c1,c to node Θi2c,c2 is denoted as 0-1 parameter ac1,c,i1c,c2,i2, where c1=c±1, or c1=c; c2=c±1 or c2=c; if the connection process has the possibility of existence, then ac1,c,i1c,c2,i2=1; otherwise, ac1,c,i1c,c2,i2=0.The connection process of train (inspection and repair arc) from nodeΘi1c1,Ω to node Θi2Ω,c2 is denoted as 0-1 parameter bc1,Ω,i1Ω,c2,i2, where c1=Ω±1 or c1=Ω; c2=Ω±1 or c2=Ω; if the connection process has the possibility of existence, then bc1,Ω,i1Ω,c2,i2 equals one; otherwise, it equals zero.Obviously, as long as the values of the parametersac1,c,i1c,c2,i2 and bc1,Ω,i1Ω,c2,i2 are determined, the rolling stock scheduling optimization network can be constructed.The connection time from nodesΘi1c1,c to Θi2c,c2 is denoted as parameter dc1,c,i1c,c2,i2, and its value can be obtained by tri2c,c2−tci1c1,c.The standard connection time of an EMU train turnover from directionc1⟶c to direction c⟶c2 at station c is denoted as parameter Λc1,cc,c2. Λc1,cc,c2 involves different operations, including emptying the passengers, cleaning the cars, handing over to the crew, and initiating waiting for passengers after the EMU train arrives. The standard time involves different operations, including emptying the passengers, cleaning the cars, handing over the cars to the stewards, and initiating waiting for passengers after the EMU train arrives. Similarly, parameter Δc1,ΩΩ,c2 denotes the standard time for the inspection and repair of EMU trains connection at station sΩ from direction c1⟶Ω to direction Ω⟶c2. Δc1,ΩΩ,c2 involves the following operations: emptying the passengers, cleaning the cars, entering and exiting the vehicle depot, and initiating waiting for passengers after the EMU train arrives at station sΩ.The set of EMU trains is denoted asE=em,m=1,2,⋯,γ, where em refers to the EMU train with the number m.The set of the tracks in stationsc is denoted as Gc=gwc,w=1,2,⋯,ϕ, where gwc refers to the track with the number w.Define 0-1 parameterδc1,ci1⟶c,cDc,cO⟶c,c2i2, such that when c1=c±1, c2=c±1, and dc1,c,i1c,c,D+dc,c,Oc,c2,i2≥Λc1,cc,c2, the parameter δc1,ci1⟶c,cDc,cO⟶c,c2i2=1; otherwise, δc1,ci1⟶c,cDc,cO⟶c,c2i2=0. This parameter indicates whether incomplete connecting arc ac,c,Oc,c1,i1 and incomplete connecting arc ac1,c,i1c,c,D can form a complete connecting arc; one indicates that this arc can be formed.Define the 0-1 parameterσc1,Ωi1⟶Ω,ΩDΩ,ΩO⟶Ω,c2i2, such that when c1=Ω±1, c2=Ω±1, and dc1,Ω,i1Ω,Ω,D+dΩ,Ω,OΩ,c2,i2≥Δc1,ΩΩ,c2, σc1,Ωi1⟶Ω,ΩDΩ,ΩO⟶Ω,c2i2=1; otherwise, σc1,Ωi1⟶Ω,ΩDΩ,ΩO⟶Ω,c2i2=0. This parameter indicates whether inspection and repair arc bΩ,Ω,OΩ,c2,i2 and inspection and repair arc bc1,Ω,i1Ω,Ω,D can form a complete inspection and repair arc; one indicates that this arc can be formed.Define the 0-1 decision variableqm,ac1,c,i1⟶c,c2,i2. If qm,ac1,c,i1⟶c,c2,i2=1, it means that train em passes through the arc ac1,c,i1c,c2,i2; otherwise, train em does not pass through the arc ac1,c,i1c,c2,i2. Similarly, define the 0-1 decision variable qm,bc1,Ω,i1⟶Ω,c2,i2. If qm,bc1,Ω,i1⟶Ω,c2,i2=1, it means that train em passes through the arc bc1,Ω,i1Ω,c2,i2; otherwise, train em does not pass through the arc bc1,Ω,i1Ω,c2,i2.Define the 0-1 decision variableρm,a,wc1,c,i1⟶c,c2,i2. If ρm,a,wc1,c,i1⟶c,c2,i2=1, it means that qm,ac1,c,i1⟶c,c2,i2=1 and the process represented by qm,ac1,c,i1⟶c,c2,i2 occupies the arrival-departure track w of station sc. Similarly, define the 0-1 decision variable ρm,b,wc1,Ω,i1⟶Ω, and its meaning is similar to that of decision variable ρm,a,wc1,c,i1⟶c,c2,i2.Define the 0-1 decision variableκpc1,c,i1⟶w. If κpc1,c,i1⟶w=1, it means that there is a route p from node Θi1c1,c to enter track w of station sc. Similarly, define 0-1 decision variable κpw⟶c,c1,i1, and its meaning is similar to that of decision variable κpc1,c,i1⟶w.Define the 0-1 decision variableψpc1,Ω,i1|w⟶Ω. If ψpc1,Ω,i1|w⟶Ω=1, it means that route p is selected when the EMU train enters the depot from node Θi1c1,Ω through the arrival-departure track w of station SΩ. Similarly, define the 0-1 decision variable ψpΩ,c1,i1|Ω⟶w, and its meaning is similar to that of decision variable ψpc1,Ω,i1|w⟶Ω.Define the 0-1 parameterχc1,c,i1⟶c,c2,i2c3,c,i3⟶c,c4,i4, such that ac3,c,i3c,c4,i4 and ac1,c,i1c,c2,i2 can be completed on the same track; the parameter χc1,c,i1⟶c,c2,i2c3,c,i3⟶c,c4,i4=1; otherwise, χc1,c,i1⟶c,c2,i2c3,c,i3⟶c,c4,i4=0. Similarly, define the 0-1 parameters: χc1Ω,i1⟶Ωc2,Ω,i2⟶Ω, χΩ⟶Ω,c1,i1Ω⟶Ω,c2,i2, χc1,Ω,i1⟶Ω,c2,i2c3,Ω,i3⟶Ω, χc1,Ω,i1⟶Ω,c2,i2Ω⟶Ω,c3,i3, and χΩ⟶c,c1,i1c2,c,i2⟶Ω.Define the 0-1 parameterγc1,c⟶w2|p2c1,c⟶w1|p1, such that the route associated with κp1c1,c,i1⟶w1 and the route associated with κp2c1,c,i2⟶w2 are compatible; the parameter γc1,c⟶w2|p2c1,c⟶w1|p1=1; otherwise, γc1,c⟶w2|p2c1,c⟶w1|p1=0. Similarly, define the 0-1 parameters: γw2⟶c,c1,i2|p2c1,c,i1⟶w1|p1, γw2⟶c,c1,i2|p2w1⟶c,c1,i1|p1, γc2,Ω,i2|w2⟶Ω|p2c1,Ω,i1|w1⟶Ω|p1, γΩ,c2,i2|Ω|⟶w2|p2Ω,c1,i1|Ω|⟶w1|p1, γΩ,c2,i2|Ω⟶w2|p2c1,Ω,i1|w1⟶Ω|p1, γΩ,c2,i2|Ω⟶w2|p2c1,Ω,i1⟶w1|p1, γc2,Ω,i2|w2⟶Ω|p2c1,Ω,i1⟶w1|p1, γΩ,c2,i2|Ω⟶w2|p2w1⟶Ω,c1,i1|p1, and γc2,Ω,i2|w2⟶Ω|p2w1⟶c,c1,i1|p1.The unit time utility value of the route associated withκpc1,c,i1⟶w is denoted as vpc1,c⟶w; the value of this parameter can be determined based on the route direction, whether crossing the mainline, and other factors. Similarly, define parameter vpw⟶c1,c.The unit time utility value of the route from trackw of station sΩ to the depot is denoted as ypw⟶Ω; the value of this parameter can be determined based on the position relationship between the arrival-departure track and the depot. Similarly, define parameter ypΩ⟶w.The unit time utility value of the connection arcac1,c,i1c,c2,i2 that stops on track w of station sc is denoted as uwc1,c⟶c,c2; the value of this parameter can be determined based on the position relationship between the track and the station entrance.


## 5.2. Rolling Stock Scheduling Connection Constraints

①
The EMU train entering running line nodeΘi2c2,c3 must exit from the same running line node:(1)∑Θi1c1,c2qm,ac1,c2,i1⟶c2,c3,i2+qm,bc1,c2,i1⟶c2,c3,i2=∑Θi3c3,c4qm,ac2,c3,i2⟶c3,c4,i3+qm,bc2,c3,i2⟶c3,c4,i3∀em,Θi2c2,c3,where:c2≠c3,②
Running lineΘi2c2,c3 must have one EMU train passing by(2)∑em∑Θi1c1,c2qm,ac1,c2,i1⟶c2,c3,i2+qm,bc1,c2,i1⟶c2,c3,i2=1∀Θi2c2,c3,where:c2≠c3.③
The timetable takes 48 hours as a cycle. Thus, if it is strictly required that each EMU train starts from a left virtual nodeΘOc,c, it will enter the corresponding right virtual node ΘDc,c:(3)∑Θi2c,c2qm,ac,c,O⟶c,c2,i2+qm,bc,c,O⟶c,c2,i2,=∑Θi1c1,cqm,ac1,c,i1⟶c,c,D+qm,bc1,c,i1⟶c,c,D∀m,ΘOc,c,ΘDc,c.④
Any EMU train can appear at most once at all left virtual nodes:(4)∑ΘOc,c∑Θi1c,c1qm,ac,c,O⟶c,c1,i1+qm,bc,c,O⟶c,c1,i1≤1∀em⑤
The EMU train starting from a left virtual node must go through an inspection and repair arc only once in 48 hours:(5)∑ΘOΩ,Ω∑ΘiΩ,cqm,aΩ,Ω,O⟶Ω,c,i+qm,bΩ,Ω,O⟶Ω,c,i=∑Θi1x1,Ω∑Θi2Ω,x2bx1,Ω,i1Ω,x2,i2⋅qm,bx1,Ω,i1⟶Ω,x2,i2∀em,x1≠Ω,i1≠O.Since an inspection and repair arc of the left virtual node and an inspection and repair arc of the right virtual node are calculated repeatedly, the right side of (5) needs to omit the left or the right virtual node. That is, x1≠Ω and i1≠O in equation (5).⑥
EMU trains must be on an inspection and repair or connection arc, which is expressed as follows (taking the connecting arc as the example, the constraint formula of the inspection and repair edge is similar to it):(6)∑emqm,ax1,c,i1⟶c,x2,i2≤ax1,c,i1c,x2,i2⑦
The connection requirements should be met at the crossing time, which is expressed as follows (taking the connecting arc as the example, the constraint formula of the inspection and repair edge is similar to it):(7)qm,ax1,ci1⟶c,cD+qm,ac,cO⟶c,x2i2≤1+δx1,ci1⟶c,cDc,cO⟶c,x2i2.


## 5.3. Constraints on the Route of the Train Passing through the Station

①
The path of the train passing through the station and the path of entering and leaving the depot need to stop or pass through a station track:(8)qm,ac1,c,i1⟶c,c2,i2=∑wρm,a,wc1,c,i1⟶c,c,D,qm,bc1,Ω,i1⟶Ω,c2,i2=∑wρm,b,wc1,Ω,i1⟶Ω,qm,bc1,Ω,i1⟶Ω,c2,i2=∑wρm,b,wΩ⟶Ω,c2,i2.②
The access trackw must be realized through a path connected to it:(9)∑mρm,a,wc1,c,i1⟶c,c2,i2=∑pκpc1,c,i1⟶w,∑mρm,a,wc1,c,i1⟶c,c2,i2=∑pκpw⟶c,c2,i2,∑mρm,b,wc1,Ω,i1⟶Ω=∑pκpc1,Ω,i1⟶w,∑mρm,b,wc1,Ω,i1⟶Ω=∑pψpc1,Ω,i1|w⟶Ω,∑mρm,b,wΩ⟶Ω,c2,i2=∑pκpw⟶Ω,c2,i2,∑mρm,b,wΩ⟶Ω,c1,i1=∑pψpΩ,c1,i1|Ω⟶w.③
Constraints of the arrival-departure track compatibility are expressed as follows (taking two EMU trains passing through the station as an example, other situations are similar to it):(10)ρm1,a,wc1,c,i1⟶c,c2,i2+ρm2,a,wc3,c,i3⟶c,c4,i4+χc1,c,i1⟶c,c2,i2c3,c,i3⟶c,c4,i4≤2.④
The stopping or passing process with overlapping time cannot be realized on the same track or the same switch:(11)κp1c1,c,i1⟶w1+κp2c1,c,i2⟶w2+γc1,c,i2⟶w2|p2c1,c,i1⟶w1|p1≤2,κp1c1,c,i1⟶w1+κp2w2⟶c,c1,i2+γw2⟶c,c1,i2|p2c1,c,i1⟶w1|p1≤2,κp1w1⟶c,c1,i1+κp2w2⟶c,c1,i2+γw2⟶c,c1,i2|p2w1⟶c,c1,i1|p1≤2,ρm1,a,wc1,c,i1⟶c,c2,i2+ρm2,a,wc3,c,i3⟶c,c4,i4+χc1,c,i1⟶c,c2,i2c3,c,i3⟶c,c4,i4≤2,ρm1,b,wc1,Ω,i1⟶Ω+ρm2,b,wc2,Ω,i2⟶Ω+χc1,Ω,i1⟶Ωc2,Ω,i2⟶Ω≤2,ρm1,b,wΩ⟶Ω,c1,i1+ρm2,b,wΩ⟶Ω,c2,i2+χΩ⟶Ω,c1,i1Ω⟶Ω,c2,i2≤2,ρm1,a,wc1,Ω,i1⟶Ω,c2,i2+ρm2,b,wc3,Ω,i3⟶Ω+χc1,Ω,i1⟶Ω,c2,i2c3,Ω,i3⟶Ω≤2,ρm1,a,wc1,Ω,i1⟶Ω,c2,i2+ρm2,b,wΩ⟶Ω,c3,i3+χc1,Ω,i1⟶Ω,c2,i2Ω⟶Ω,c3,i3≤2,ρm1,b,wΩ⟶c,c1,i1+ρm2,b,wc2,c,i2⟶Ω+χΩ⟶c,c1,i1c2,c,i2⟶Ω≤2,ψp1c1,Ω,i1|w1⟶Ω+ψp2c2,Ω,i2|w2⟶Ω+γc2,Ω,i2|w2⟶Ωp2c1,Ω,i1|w1⟶Ωp1≤2,ψp1Ω,c1,i1|Ω⟶w1+ψp2Ω,c2,i2|Ω⟶w2+γΩ,c2,i2|Ω⟶w2p2Ω,c1,i1|Ω⟶w1p1≤2,ψp1c1,Ω,i1|w1⟶Ω+ψp2Ω,c2,i2|Ω⟶w2+γΩ,c2,i2|Ω⟶w2p2c1,Ω,i1|w1⟶Ωp1≤2,κp1c1,Ω,i1⟶w1+ψp2Ω,c2,i2|Ω⟶w2+γΩ,c2,i2|Ω⟶w2p2c1,Ω,i1⟶w1p1≤2,κp1c1,Ω,i1⟶w1+ψp2c2,Ω,i2|w2⟶Ω+γc2,Ω,i2|w2⟶Ωp2c1,Ω,i1⟶w1p1≤2,κp1w1⟶Ω,c1,i1+ψp2Ω,c2,i2|Ω⟶w2+γΩ,c2,i2|Ω⟶w2p2w1⟶Ω,c1,i1p1≤2,κp1w1⟶c,c1,i1+ψp2c2,Ω,i2|w2⟶Ω+γc2,Ω,i2|w2⟶Ωp2w1⟶c,c1,i1p1≤2.


## 5.4. Optimization Objectives

①
Minimize the number of EMU trains in the operation:(12)minZ1=∑m∑Θi1c,c1qm,ac,c,O⟶c,c1,i1+∑Θi2Ω,c2qm,bΩ,Ω,O⟶Ω,c2,i2.②
Maximize the utility of arrival-departure tracks and turnouts:(13)maxZ2=∑Θi1c1,c∑pvpc1,c⟶w,κpc1,c,i1⟶w+∑Θi1c1,c∑wvpw⟶c1,c⋅κpw⟶c1,c,i1+∑Θi1c1,Ω∑pypΩ⟶w⋅ψpΩ,c1,i1|Ω⟶w+∑Θi1Ω,c1∑pypΩ⟶w⋅ψpΩ,c1,i1|Ω⟶w+∑w∑m∑ac1,c,i1c,c2,i2uwc1,c⟶c,c2⋅ρm,a,wc1,c,i1⟶c,c2,i2.The model presented in this section is a 0-1 integer linear programming model, which can be solved by commercial optimization software, such as ILOG CPLEX software.


## 6. Numerical Experiments

In the test, four high-speed railway stations denoted as A, B, C, and D were designed on a high-speed railway line, among which stations A and D denoted turn-back stations, station B was equipped with a depot, station C represented an intermediate station, A⟶D was the downward direction, and D⟶A was the upward direction.The plan sketches of stations A, B, C, and D are shown in Figures11–14.Figure 11
Plan sketch of station A.Figure 12
Plan sketch of station B.Figure 13
Plan sketch of station C.Figure 14
Plan sketch of station D.The train timetable on the text line is shown in Table2.Table 2
Train timetable.
Downward directionUpward directionTrain no.ABBCCDTrain no.DCCBBAG17:167:467:488:18G20:150:450:471:171:192:19G37:038:03G40:451:151:171:47G58:489:189:209:50G61:101:401:422:122:143:14G79:169:469:4810:18G88:209:20G98:299:29G108:449:149:169:46G1111:3312:0312:0512:35G1210:1311:13G1310:4711:47G149:289:5810:0010:30G1513:0013:3013:3214:02G1610:3811:0811:1011:40G1712:0713:07G1812:4513:45G1913:2914:29G2013:2814:28G2115:2615:5615:5816:28G2213:2013:5013:5214:22G2315:0616:06G2415:0015:3015:3216:02G2517:4518:1518:1718:47G2615:3716:37G2717:2618:26G2817:1818:18G2919:1619:4619:4820:18G3017:0017:3017:3218:02G3120:3121:0121:0321:33G3218:5019:50G3319:4420:4420:5521:2521:2721:57G3419:0319:3319:3520:05G3520:0421:0421:0721:3721:3922:09G3619:2520:25G3720:3821:38G3820:4021:1021:1221:42G3920:4821:4821:5022:2022:2222:52G4022:5023:50G4121:1022:1022:2422:5422:5623:26G4218:0018:3018:3219:0219:3520:35G4321:2822:28G4423:230:23G4521:5722:57G4622:4123:1123:1323:4323:450:45G4722:1623:1623:1823:4823:500:20G4823:1023:4023:420:120:141:14G4923:310:010:030:33G5023:430:130:150:450:471:47G5122:4023:4023:480:180:200:50G520:050:350:371:07According to the arrangement position of the arrival track at stations A, B, C, and D, the utility of occupying the track and station access routes was determined, and the obtained values are shown in Tables3–6.Table 3
Utility value of parking in each track of station A.
TypeI35II468BA-AB1008060100806040Table 4
Utility value of parking in each track of station B.
TypeI357II46AB-BA1008060401008060AB-BC300280260240−100−120−140CB-BA−100−120−140−160300280260CB-BC1008060401008060AB-depot90705030−90−110−130CB-depot−110−130−150−1701109070Depot-BA−110−130−150−1701109070Depot-BC90705030−90−110−130Table 5
Utility value of parking in each track of station C.
TypeI3II4BC-CD300280−100−120DC-CB−100−120300280Table 6
Utility value of parking in each track of station D.
TypeI35II468CD-DC1008060100806040Due to the limited paper length, the utility values of all access routes of each station cannot be presented.In the optimization model of rolling stock scheduling and train passing through the station route presented in Section3, the minimum connection time of EMU train changing train number in the station was set to 20 min, and the route preparation time and turnout unlocking time were set to 2 min, while the first-level inspection and repair time was set to 240 min. In addition to the time of cleaning of the EMU train and the time of entering and leaving the depot, the minimum connection time of the inspection and repair arc was 260 min in total.By adopting the proposed model and above-defined conditions, it was obtained that at least 12 EMU trains were required to complete the relevant operational tasks on the test high-speed railway line. The operation tasks of each EMU train are presented in Table7.①
The connection scheme of station B is shown in Table8.②
The track utilization scheme of station B is shown in Figure15.③
The use scheme of turnout is given in Table9.Table 7
Optimal task allocation scheme of EMU train for the test high-speed railway.
EMU numberTask1-Depot (inspection and repair)-Station B (track I)-G7- station C (track I)-G7- station D (track II)-G16- station C (track II)-G16- station B (track I)-G15- station C (track I)-G15-station D (track I)G30- station C (track II)-G30- station B (track I)-G29- station C (track I)-G29-station D (track I)-G38- station C (track II)-G38- station B (track II)-G44- station A (track 6)-G71- station B (track II)-G78- station A (track 4)-G99- station B (track I)-G99- station C (track I)-G99-station D (track I)-G4- station C (track II)-G4- station B (track II)-Depot (inspection and repair)-2-Depot (inspection and repair)-Station B (track II)-G12-station A (track 4)-G27-station B (track II)-G32-station A (track II)-G41-station B (track I)-G41-station C (track I)-G41-station D (track 4)-G104-station C (track II)-G104-station B (track 3)-G57-station C (track I)-G57-station D (track II)-G68-station C (track II)-G68-station B (track I)-G67-station C (track I)-G67-station D (track II)-G76-station C (track II)-G76-station B (track I)-G77-station C (track I)-G77-station D (track I)-G86-station B (track II)-Depot (inspection and repair)-3-Depot (inspection and repair)-Station B (track I)-G25-station C (track I)-G25-station D (track I)-G34-station C (track II)-G34-station B (track 4)-G40-station A (track 5)-G91-station B (track I)-G91-station C (track I)-G91-station D (track I)-G100-station C (track II)-G100-station B (track II)-G100-station A (track II)-G9-station B (track I)-Depot (inspection and repair)-4-Depot (inspection and repair)-Station B (track I)-G73-station C (track I)-G73-station D (track II)-G82-station C (track II)-G82-station B (track II)-G88-station A (track II)-G97-station B (track 3)-G101-station C (track I)-G101-station D (track II)-G6-station C (track II)-G6-station B (track II)-G6-station A (track 6)-G51-station B (track I)-G51-station C (track I)-G51-station D (track I)-G66-station C (track II)-G66-station B (track II)-Depot (inspection and repair)-5-Depot (inspection and repair)-Station B (track I)-G59-station C (track I)-G59-station D (track I)-G94-station C (track II)-G94-station B (track 4)-G94-station A (track I)-G93-station B (track I)-G93-station C (track I)-G93-station D (track I)-G102-station C (track II)-G102-station B (track II)-G102-station A (track I)-G3-station B (track I)-G5-station C (track I)-G5-station D (track I)-G22-station C (track II)-G22-station B (track 4)-G21-station C (track I)-G21-station D (track II)-G42-station C (track II)-G42-station B (track II)-G42-station A (track 3)-G47-station B (track I)-G47-station C (track I)-G47-station D (track I)-G56-station C (track II)-G56-station B (track II)-Depot (inspection and repair)-6-Depot (inspection and repair)-Station B (track I)-G1-station C (track I)-G1-station D (track II)-G14-station C (track II)-G14-station B (track I)-G11-station C (track I)-G11-station D (track II)-G24-station C (track II)-G24-station B (track II)-G28-station A (track 4)-G45-station B (track 3)-G49-station C (track I)-G49-station D (track II)-G58-station C (track II)-G58-station B (track II)-G58-station A (track 4)-G75-station B (track 3)-G83-station C (track I)-G83-station D (track II)-G52-station C (track II)-G52-station B (track II)-Depot (inspection and repair)-7-Depot (inspection and repair)-Station B (track I)-G31-station C (track I)-G31-station D (track II)-G54-station C (track II)-G54-station B (track II)-G54-station A (track I)-G55-station B (track II)-G60-station A (track II)-G65-station B (track II)-G70-station A (track II)-G79-station B (track I)-G81-station C (track I)-G81-station D (track I)-G90-station C (track II)-G90-station B (track II)-G92-station A (track 4)-G13-station B (track II)-G18-station A (track II)-G23-station B (track I)-Depot (inspection and repair)-8-Depot (inspection and repair)-Station B (track I)-G53-station C (track I)-G53-station D (track II)-G62-station C (track II)-G62-station B (track I)-G63-station C (track I)-G63-station D (track II)-G74-station C (track II)-G74-station B (track 4)-G84-station A (track 6)-G95-station B (track 4)-G96-station A (track 5)-G37-station B (track I)-Depot (inspection and repair)-9-Depot (inspection and repair)-Station B (track II)-G80-station A (track II)-G85-station B (track I)-G85-station C (track I)-G85-station D (track 3)-G2-station C (track II)-G2-station B (track II)-G2-station A (track 8)-G43-station B (track I)-Depot (inspection and repair)-10-Depot (inspection and repair)-Station B (track II)-G26-station A (track II)-G33-station B (track I)-G33-station C (track I)-G33-station D (track I)-G46-station C (track II)-G46-station B (track II)-G46-station A (track 8)-G103-station B (track I)-G103-station C (track I)-G103-station D (track I)-G10-station C (track II)-G10-station B (track II)-Depot (inspection and repair)-11-Depot (inspection and repair)-Station B (track II)-G8-station A (track I)-G17-station B (track I)-G20-station A (track I)-G35-station B (track I)-G35-station C (track I)-G35-station D (track 3)-G48-station C (track II)-G48-station B (track II)-G48-station A (track 3)-G69-station B (track I)-G72-station A (track 3)-G89-station B (track I)-Depot (inspection and repair)-12-Depot (inspection and repair)-Station B (track 4)-G36-station A (track I)-G39-station B (track I)-G39-station C (track I)-G39-station D (track I)-G50-station C (track II)-G50-station B (track II)-G50-station A (track II)-G61-station B (track II)-G64-station A (track I)-G87-station B (track I)-G87-station C (track I)-G87-station D (track I)-G98-station C (track II)-G98-station B (track II)-G98-station A (track 3)-G19-station B (track I)-Depot (inspection and repair)-The tasks presented in Table7 can be divided into three schemes (due to the length of the paper, only station B is taken as an example).Table 8
Optimal connection scheme of EMU trains at station B.
Arrival train no.Arrival timeDeparture train numberDeparture timeConnect time (min)G41 : 47(1)Overhauled1 : 52(1)5Overhauled9 : 01(1)G79 : 16(1)15G1611 : 40(1)G1513 : 00(1)80G3018 : 02(1)G2919 : 16(1)74G3821 : 42(1)G4423 : 23(1)101Overhauled9 : 58(1)G1210 : 13(1)15G2718 : 26(1)G3218 : 50(1)24G4122 : 10(1)G4122 : 24(1)14G99 : 29(1)Overhauled9 : 34(1)5Overhauled17 : 30(1)G2517 : 45(1)15G3420 : 05(1)G4022 : 50(1)165G62 : 12(1)G62 : 14(1)2G5123 : 40(1)G5123 : 48(1)8Overhauled15 : 11(1)G7315 : 26(1)15G38 : 03(1)G58 : 48(1)45G2214 : 22(1)G2115 : 26(1)64G4219 : 02(1)G4219 : 35(1)33G4723 : 16(1)G4723 : 18(1)2Overhauled9 : 01(1)G599 : 16(1)15G521 : 07(1)Overhauled1 : 12(1)5Overhauled7 : 01(1)G17 : 16(1)15G1410 : 30(1)G1111 : 33(1)63G2416 : 02(1)G2817 : 18(1)76G4522 : 57(1)G4923 : 31(1)34G1311 : 47(1)G1812 : 45(1)58G2316 : 06(1)Overhauled16 : 11(1)5Overhauled20 : 16(1)G3120 : 31(1)15G3721 : 38(1)Overhauled21 : 43(1)5Overhauled7 : 01(1)G537 : 16(1)15G21 : 17(1)G21 : 19(1)2G4322 : 28(1)Overhauled22 : 33(1)5Overhauled17 : 03(1)G8017 : 18(1)15G109 : 46(1)Overhauled9 : 51(1)5Overhauled15 : 22(1)G2615 : 37(1)15G3320 : 44(1)G3320 : 55(1)11Overhauled8 : 05(1)G88 : 20(1)15G1713 : 07(1)G2013 : 28(1)21G3521 : 04(1)G3521 : 07(1)3G7114 : 29(2)G7815 : 37(2)68G9923 : 16(2)G9923 : 18(2)2G8620 : 05(2)Overhauled20 : 10(2)5G1041 : 07(2)G578 : 48(2)461G6811 : 40(2)G6713 : 00(2)80G7616 : 02(2)G7717 : 45(2)103G1000 : 12(2)G1000 : 14(2)2G9121 : 48(2)G9121 : 50(2)2G6610 : 30(2)Overhauled10 : 35(2)5G8218 : 02(2)G8819 : 25(2)83G9722 : 57(2)G10123 : 31(2)34G1020 : 45(2)G1020 : 47(2)2G561 : 47(2)Overhauled1 : 52(2)5G9419 : 02(2)G9419 : 35(2)33G9322 : 10(2)G9322 : 24(2)14G582 : 12(2)G582 : 14(2)2G7516 : 06(2)G8320 : 31(2)265G541 : 17(2)G541 : 19(2)2G558 : 03(2)G608 : 20(2)17G6511 : 47(2)G7012 : 45(2)58G7918 : 26(2)G8119 : 16(2)50G9021 : 42(2)G9222 : 50(2)68G629 : 46(2)G6311 : 33(2)107G7414 : 22(2)G8418 : 50(2)268G9522 : 28(2)G9623 : 23(2)55G8520 : 44(2)G8520 : 55(2)11G10323 : 40(2)G10323 : 48(2)8G8921 : 38(2)Overhauled21 : 43(2)5G6913 : 07(2)G7213 : 28(2)21G619 : 29(2)G6410 : 13(2)44G8721 : 04(2)G8721 : 07(2)3G9823 : 43(2)G9823 : 45(2)2G480 : 12(1)G480 : 14(1)2G1914 : 29(1)Overhauled14 : 34(1)5Overhauled19 : 10(1)G3619 : 25(1)15G3921 : 48(1)G3921 : 50(1)2G500 : 45(1)G500 : 47(1)2If this problem is solved in two stages, on the basis that at least 12 EMUs can complete the operation requirements and obtain the rolling stock scheduling of EMU trains in the first stage, the scheme in the second stage will have a certain probability that it cannot be realized due to the limitation of the number of arrival-departure tracks in the station. This proves the accuracy of this method from the side and also shows that this method can ensure the feasibility of relevant schemes.Figure 15
The station track utilization schematic of station B.Table 9
The optimal arrival-departure route scheme at the right throat of station B.
Reception and departure of trainsEMU train no.DirectionStartEndRouteReceptionSide near station ATrack 3 of station B3-11-15-17-31T97, T45, T75ReceptionSide near station ATrack 4 of station B3-7-13–23T95ReceptionSide near station ATrack I of station B3-11-19–27T99, T41, T9, T91, T51, T3, T47, T93, T23, T79, T37, T43, T85, T33, T103, T17, T35, T69, T89, T19, T39, T87ReceptionSide near station ATrack II of station B3-7-13-21-29T71, T27, T13, T55, T65, T61Leave the depotThe depotTrack 4 of station B23–23T36Leave the depotThe depotTrack I of station B23-13-7-3-1-1-3-11-19-27T7, T25, T73, T59, T1, T31, T53Leave the depotThe depotTrack II of station B23-13-7-3-1-1-3-7-13-21-29T12, T80, T26, T8DepartureTrack 4 of station BSide near station A23-13-5T40, T94, T84, T96, T36DepartureTrack I of station BSide near station A27-19-11-7-5T20, T72Enter the depotTrack I of station BThe depot27-19-11-3-1-1-3-7-13–23T9, T23, T37, T43, T89, T19DepartureTrack II of station BSide near station A29-21-13-5T44, T78, T12, T32, T100, T6, T88, T102, T42, T28, T58, T18, T54, T60, T70, T92, T2, T80, T26, T46, T8, T48, T50, T64, T98Enter the depotTrack II of station BThe depot29-21-13-7-3-1-1-3-7-13-23T4, T86, T66, T56, T52, T10DepartureTrack 4 of station BSide near station A23-13-5T40, T94, T84, T96, T36


## 7. Conclusions

In this paper, a comprehensive optimization model of rolling stock scheduling and train passing station routes for Chinese high-speed railway is proposed. The proposed model can obtain the rolling stock scheduling and train passing station route scheme at the same time. The proposed model not only simplifies the process of preparing relevant schemes but also ensures the applicability of the rolling stock scheduling and train passing station routes schemes.The proposed model is verified by the test using the data of the Chinese high-speed railway. However, it should be noted that the proposed model is widely applicable to other countries or regions.Although the proposed model can achieve good performance, this paper only preliminarily analyzes the comprehensive optimization method of rolling stock scheduling and train crossing routes. The factors such as different speed levels, different number of marshalling groups, and feedback scheme of empty EMU trains have not been deeply studied. Therefore, the above factors need to be taken into account in future research. In addition, the matching between the scheme and passenger service scheme should be further studied on the basis of this achievement.



---

*Source: 3288109-2022-05-06.xml*