# Structure Optimization of Mixed-Speed Train Traffic for Cyclic Timetable: Model and Algorithm Development

Authors: Jiamin Zhang; Jiarui Zhang
Journal: Discrete Dynamics in Nature and Society
 (2022)

---

## Abstract

Trains can be optimally spread over the period of the cyclic timetable. By integrating sequencing issue with headway time together, this paper studies the structure optimization of mixed-speed train traffic for a cyclic timetable. Firstly, by taking it as a job-shop problem with sequence-dependent setup times on one machine, in the type of infinite capacity resource with headway (ICR + H), the problem is transformed to alternative graph (AG) and then recast to the mixed-speed train traffic planning (MSTTP) model. For the multiobjective in MSTTP, three indicators are optimized, i.e., heterogeneity, cycle time, and buffer time, which correspond to diversity of train service toward passenger, capacity consumption of rail network, and stability of train operation, respectively. Secondly, the random-key genetic algorithm (RKGA) is proposed to tackle the sequence and headway simultaneously. Finally, RKGA is coded with visual studio C# and the proposed method is validated with a case study. The rail system considered is a line section encompassing a territory of 180 km with 15 mixed-speed trains in each cycle of the timetable. Results indicate the comprehensively balanced train plan for all stakeholders from random variations of train sequence and headway time. Both the quantitative proportion of heterogeneity/homogeneity (e.g., 2.5) about the optimized distribution of the mixed train traffic and the link between train headway time and the sequence for each traffic scenario are found. All the findings can be used to arrange the mixed-speed train traffic more scientifically.


---

## Body

## 1. Introduction

Usually, the railway industry provides the passenger services in the form of the train timetable, in order to satisfy the public travel demand and maintain the further development needs of the railway company. Any set of key performance indicators must be sufficient to adequately represent the requirements of all stakeholders. For timetabling, the key stakeholders include passengers, network operators, and train operators. However, the requirements of these stakeholders are prone to mutual conflict. The UIC capacity leaflet [1] showed the capacity balance relationship among the number of trains, the average speed, the heterogeneity, and the stability (Figure 1). Landex [2] added an extra dimension, capacity consumption, which formed the “capacity pyramid” as illustrated in Figure 1.Figure 1
Railway capacity: capacity balance (a) and capacity pyramid (b) (sourcing: UIC [1]; Landex [2]).
(a)(b)Capacity consumption may be different for each proportional mix of trains and the order in which they run on the route [3–6], as can be seen in Figure 2. It is possible to achieve a high stability/punctuality on a railway network or to provide a diverse service to the passengers. At the same time, it would also cost more capacity consumption. What is demonstrated in Figure 2 are just two typical extreme cases. A cyclic timetable means that each line of passenger trains is operated in a cyclic pattern, e.g., with regularly sequenced repeating train lines [7]. In Figure 2, we may get the maximal and minimal value of the cycle time, only benefiting the interest of a certain part of the stakeholders, e.g., the railway operators. However, what we concern is to seek a comprehensively balanced solution as optimal as possible for all of the involved stakeholders, by arranging the train traffic, which no doubt have great significance for train timetabling. And, these concerns just motivate us to quantitatively optimize the mixed-speed train traffic structure in an all-round balanced way, so as to lay the foundation for a more robust, stable, and efficient timetable with more reasonable transport capacity. According to whether they explicitly model the track structure and whether the timetable is intended to be periodic or not, Harrod [8] addressed four fundamental timetable formulations suitable for optimization, e.g., mixed integer sequencing linear programs, binary integer occupancy programs, hypergraph formulation, and periodic event scheduling problems, focusing on the planning objective and available data, regardless of the specific traffic carried or network size. Zhang [9] summarized some strategies for train operation plan under mixed traffic condition and analyzed them from both pros and cons aspects, which limited to a qualitative analysis of the mixed traffic structure rather than a quantitative optimization. Huang [10] presented a time supplements allocation method that incorporates historical train operation data to optimize buffer-time distribution in the sections and stations of a published timetable.Figure 2
Mixed train traffic arrangement from perspective of passengers with very heterogeneous (a) and that of network operators with slightly heterogeneous (b) (sourcing: Kaas [4]).
(a)(b)This paper studies the structure of the mixed-speed train traffic for a cyclic timetable in a passenger railway line section, integrating sequencing with headway optimization for train lines. As was defined by UIC [10], in our research, a railway line section is the part of a line in which the traffic mix and/or the number of trains or the infrastructure and signaling conditions do not change fundamentally. Infrastructure elements can be modeled by using resources with different properties in terms of capacity [11], one of which is the kind of infinite capacity resource with headway (ICR + H). In the type (ICR + H), the number of operations that can be simultaneously processed is not restricted. However, the starting times of two consecutive operations on the same resource are separated by a time interval. In this study, we assume the railway line section as the one-machine [12] type (ICR + H) and the trains as jobs to be processed.An alternative graph (AG) is a representation of a job-shop scheduling model with additional operational constraints [13]. The alternative arcs of AG are used to model choice of orders between operations on the same machine (open track segment) and are weighted with the setup time, i.e., minimal or optimized headway time. By taking it as a job-shop problem with sequence-dependent setup times [14] on one-machine type (ICR + H), we transform the problem to an alternative graph (AG). Then, we recast it to the mixed-speed train traffic planning (MSTTP) model so as to optimize the temporal-spatial distribution of trains quantitatively. To develop our model, we set up three objectives considering the concerns of the stakeholders. They are the maximization of heterogeneity from the perspective of passenger optimization, the minimization of cycle time from the perspective of capacity optimization, and the maximization of the minimal buffer time from the perspective of operational optimization, individually. For the level of infrastructure details considered in the models, we distinguish among microscopic models (which consider detailed description of infrastructure and train dynamics), macroscopic models (which represent the railway network as a simplified series of links connecting stations), and mesoscopic models [15]. In this regard, our model MSTTP belongs to the kind of mesoscopic representation, using a level of abstraction between macroscopic and microscopic representation. We take the railway line section under study as a unidirectional open track segment without overtaking place.The concept of genetic algorithm (GA) was first formalized by Holland [16] and then extended to optimization by De Jong [17]. Bean [18] introduced the concept of random keys, a method for representing solutions (chromosomal encoding) that produces feasible offspring for many sequencing and optimization problems. For the problem under study, any permutation of train sequence would be a feasible solution. This would also be the typical chromosome representation adopted in GA. However, when applying crossover genetic operator, additional efforts should be taken to avoid duplication of trains in any feasible solution; i.e., a train is processed only once. The random-key genetic algorithm (RKGA) approach can help overcome this shortcoming easily [19]. The unique feature of RKGA is that its search is over the random-key space instead of the problem space. Based on these characteristics, we propose the modified random-key genetic algorithm (RKGA) to solve the mixed-speed train traffic planning (MSTTP) model, which can tackle the sequence and headway simultaneously. The objective of our study is to optimize the structure of the mixed-speed train traffic for cyclic timetable, by integrating sequencing issue with headway time together. The innovative contributions of this paper are as follows:(i)
The structure optimization problem of the mixed-speed train traffic for cyclic timetable is innovatively transformed to an alternative graph (AG).(ii)
The mixed-speed train traffic planning (MSTTP) model is constructed innovatively, considering three optimization indicators, i.e., maximization of heterogeneity from the perspective of passenger optimization, minimization of cycle time from the perspective of capacity optimization, and maximization of the minimal buffer time from the perspective of operational optimization, individually. This innovative model can ensure to achieve an all-round satisfied solution for all involved stakeholders.(iii)
The random-key genetic algorithm (RKGA) is proposed to solve the mixed-speed train traffic planning (MSTTP) model, which can tackle the sequence and headway simultaneously. The RKGA is an innovative construction and application for solving the kind of MSTTP model.(iv)
The RKGA was coded with visual studio C#, and the proposed method is validated to work out the optimal solutions for a case study. Both the quantitative proportion of heterogeneity/homogeneity (e.g., 2.5) about the optimized distribution of the mixed train traffic and the link between train headway time and the sequence for each traffic scenario are found.The rest of the paper is organized as follows: Section2 demonstrates the mathematical formulation (AG and MSTTP) of the problem. Section 3 reports the RKGA for solving the problem, including one main algorithm and four subalgorithms. In Section 4, we apply the model and algorithm to a case study and investigate the results deeply. Finally, Section 5 concludes the paper.


## 2. Mathematical Formulation

### 2.1. Problem Statement by Alternative Graph

We associate with a sequence a modified alternative graphG = (Y, A) as follows. The set Y of nodes is obtained by adding two fictitious nodes O and D to the set I of jobs (trains): Y=I∪O,D; O is a job “beginning,” and D a job “end” in the machine (unidirectional track section between two timetable points without overtaking). The set A of arcs includes three sets A=A1∪A2∪A3. Let A1=O,i|i∈I; arc O,i is valued by yi, so that job i cannot start before the point in time yi. Let A2=i,D|i∈I; arc i,D is valued by di, since job i has to spend an amount of time di in the system after its beginning of processing by the machine. Let A3=i,j|jobiproceeds to jobjin the sequence; alternative arc i,j is valued by hij, which is a sequence-dependent setup time, since it should keep an amount of headway time hij between two consecutive operations i and j; these arcs set the sequence. The improved alternative graph is shown in Figure 3. It is formulated as a one-machine type (ICR + H) scheduling problem in the unidirectional track section.Figure 3
Alternative graph (AG) statement for mixed-speed train structure.


### 2.2. Notations

The notations used in the following discussion are presented in the following:F1 denotes the objective value of the heterogeneity from the perspective of the customer.F2 denotes the objective value of cycle time in the cyclic timetable from the perspective of capacity.F3 denotes the objective value of the stability from the perspective of operation.hij denotes the departure headway time between the subsequent trains i and j.kij denotes the pairwise train scheduling decisions, which is a binary variable. When train i proceeds to train j in the sequence, it equals 1, otherwise 0.hij− denotes the smallest scheduled headway time between train i and j on the track section, and the final train n is followed by train 1 in a cyclic manner.hijA denotes the headway time at arrival between train i and j on the track section, and the last train n proceeds train 1 due to cyclicity.Hij denotes the theoretical safety minimum headway time between the subsequent trains i and j.yi denotes the departure time of train i from the starting point of the track section.di denotes the running time of train i on the track section.n denotes the number of trains to be scheduled.SSHR denotes sum of shortest headway reciprocals.SAHR denotes sum of arrival headway reciprocals.α is a parameter of SSHR, and 0<α<1.M is a large positive number.


### 2.3. Model Description

#### 2.3.1. Optimization from the Perspective of Passengers

Regarding the permutation of mixed-speed train traffic, in most cases we believe that heterogeneity could decrease the reliability of the train timetable comparing to its homogeneous counterpart [20]. However, we cannot deny that the customers’ preference should be the right paradigm in the market-oriented environment. Passenger travel behavior is far more complex and multifaceted. Assessing railway performances by merely measuring punctuality or capacity would provide an unfair picture of the level of service experienced by passengers [21]. On the other hand, heterogeneity also implies diversity and balance, which can provide a variety of train service for passengers within an acceptable headway. According to [20], there are two measures for representing the heterogeneity of trains, which is sum of shortest headway reciprocals (SSHR) and sum of arrival headway reciprocals (SAHR), respectively. To be complementary, we maximize both of them from the perspective of passenger optimization as follows:(1)maxF1=αSSHR+1−αSAHR,(2)SSHR=∑i=1n∑j=1j≠in1hij−,(3)SAHR=∑i=1n∑j=1j≠in1hijA.


#### 2.3.2. Optimization from the Perspective of Capacity

Capacity consumption represents the utilization of an infrastructure’s physical attributes along a given section [22]. UIC 406 method defines a methodology to measure the capacity consumption based on compressing timetable graphs. Zhang [23] updated the norm for capacity measure as the time needed to fulfill the task list in train service-demand intention set. Heydar et al. [24] and Petering et al. [25] proposed a different definition of capacity; i.e., capacity is the minimal cycle length that can feasibly accommodate a given number of trains over a given section of track (double track, unidirectional) in each cycle. Zhang and Nie [26] proposed a minimal cycle time calculation model on the basis of periodic event scheduling problem for a given train line plan. In accordance with 2nd edition of UIC capacity leaflet [22], which defined the occupancy time of a line section as the timescale between the first and last train paths, we calculate the cycle length with formula (4) to minimize the capacity consumption for the network operators.(4)minF2=∑i=1n∑j=1j≠inhijkij.


#### 2.3.3. Optimization from the Perspective of Operation

This objective is to create a train plan that is as robust as possible to achieve stability. That means it can both deal with relatively small disturbances and achieve a high punctuality in the real-time operations. Robustness reflects the degree to which trains depart and arrive according to the plan.The headway between subsequent trains is used by many scholars as a measure of robustness or a target for robustness in various ways [27]. Thus, we maximize the minimal buffer time between train pairs with formula (5) to optimize the stability objective from the perspective of operation.(5)F3=max1≤i≤nmin1≤j≤nj≠ihij−Hijkij.Formula (5) is a max-min objective function. According to Burggraeve [28], we introduce an auxiliary constraint as follows:(6)F3≤hij−Hijkij,1≤i≤n,1≤j≤n,j≠i.And, we change the objective function of formula (5) to the maximization of F3 as follows:(7)maxF3.


#### 2.3.4. Constraints

According to the notations mentioned above, we put forward formulas (8) and (9) for calculation the value s of hij− and hijA.(8)hij−=minhij,yj+dj−yi+dikij,1≤i≤n,1≤j≤n,j≠i,(9)hijA=yj+dj−yi+dikij,1≤i≤n,1≤j≤n,j≠i.For any considered subsequent train pairs, the relationship of their departure times should follow the following formula:(10)yj≥yi+hij−Mkji,1≤i≤n,1≤j≤n,j≠i.For the pairwise train dispatching decisions, only one alternative arc of the train pairsi,j can be selected in Figure 3, so formulas (11) and (12) should be held.(11)kij=1,ifyi<yj0,otherwise,(12)kij+kji=1,1≤i≤n,1≤j≤n,j≠i.Regarding the security for trains running, any headway time should meet the requirements of the theoretical safety minimal headway time between the subsequent trains. Thus, formulas (13)–(15) should be obeyed.(13)hij≥Hij,1≤i≤n,1≤j≤n,j≠i,(14)hij−≥Hij,1≤i≤n,1≤j≤n,j≠i,(15)hijA≥Hij,1≤i≤n,1≤j≤n,j≠i.


#### 2.3.5. Complete MSTTP Model

As what are analyzed above, we set up the complete mixed-speed train traffic planning (MSTTP) model as follows.Obj:(16)maxF1=αSSHR+1−αSAHR,minF2=∑i=1n∑j=1j≠inhijkij,maxF3,s.t.(17)hij−=minhij,yj+dj−yi+dikij,1≤i≤n,1≤j≤n,j≠i,hijA=yj+dj−yi+dikij1≤i≤n,1≤j≤n,j≠i,F3≤hij−Hijkij1≤i≤n,1≤j≤n,j≠i,yj≥yi+hij−Mkji,1≤i≤n,1≤j≤n,j≠i,kij=1,ifyi<yj,0,otherwise,kij+kji=1,1≤i≤n,1≤j≤n,j≠i,hij≥Hij,1≤i≤n,1≤j≤n,j≠i,hij−≥Hij,1≤i≤n,1≤j≤n,j≠i,hijA≥Hij,1≤i≤n,1≤j≤n,j≠i,M is a large positive numberα is a weight parameter and 0<α<1


## 2.1. Problem Statement by Alternative Graph

We associate with a sequence a modified alternative graphG = (Y, A) as follows. The set Y of nodes is obtained by adding two fictitious nodes O and D to the set I of jobs (trains): Y=I∪O,D; O is a job “beginning,” and D a job “end” in the machine (unidirectional track section between two timetable points without overtaking). The set A of arcs includes three sets A=A1∪A2∪A3. Let A1=O,i|i∈I; arc O,i is valued by yi, so that job i cannot start before the point in time yi. Let A2=i,D|i∈I; arc i,D is valued by di, since job i has to spend an amount of time di in the system after its beginning of processing by the machine. Let A3=i,j|jobiproceeds to jobjin the sequence; alternative arc i,j is valued by hij, which is a sequence-dependent setup time, since it should keep an amount of headway time hij between two consecutive operations i and j; these arcs set the sequence. The improved alternative graph is shown in Figure 3. It is formulated as a one-machine type (ICR + H) scheduling problem in the unidirectional track section.Figure 3
Alternative graph (AG) statement for mixed-speed train structure.


## 2.2. Notations

The notations used in the following discussion are presented in the following:F1 denotes the objective value of the heterogeneity from the perspective of the customer.F2 denotes the objective value of cycle time in the cyclic timetable from the perspective of capacity.F3 denotes the objective value of the stability from the perspective of operation.hij denotes the departure headway time between the subsequent trains i and j.kij denotes the pairwise train scheduling decisions, which is a binary variable. When train i proceeds to train j in the sequence, it equals 1, otherwise 0.hij− denotes the smallest scheduled headway time between train i and j on the track section, and the final train n is followed by train 1 in a cyclic manner.hijA denotes the headway time at arrival between train i and j on the track section, and the last train n proceeds train 1 due to cyclicity.Hij denotes the theoretical safety minimum headway time between the subsequent trains i and j.yi denotes the departure time of train i from the starting point of the track section.di denotes the running time of train i on the track section.n denotes the number of trains to be scheduled.SSHR denotes sum of shortest headway reciprocals.SAHR denotes sum of arrival headway reciprocals.α is a parameter of SSHR, and 0<α<1.M is a large positive number.


## 2.3. Model Description

### 2.3.1. Optimization from the Perspective of Passengers

Regarding the permutation of mixed-speed train traffic, in most cases we believe that heterogeneity could decrease the reliability of the train timetable comparing to its homogeneous counterpart [20]. However, we cannot deny that the customers’ preference should be the right paradigm in the market-oriented environment. Passenger travel behavior is far more complex and multifaceted. Assessing railway performances by merely measuring punctuality or capacity would provide an unfair picture of the level of service experienced by passengers [21]. On the other hand, heterogeneity also implies diversity and balance, which can provide a variety of train service for passengers within an acceptable headway. According to [20], there are two measures for representing the heterogeneity of trains, which is sum of shortest headway reciprocals (SSHR) and sum of arrival headway reciprocals (SAHR), respectively. To be complementary, we maximize both of them from the perspective of passenger optimization as follows:(1)maxF1=αSSHR+1−αSAHR,(2)SSHR=∑i=1n∑j=1j≠in1hij−,(3)SAHR=∑i=1n∑j=1j≠in1hijA.


### 2.3.2. Optimization from the Perspective of Capacity

Capacity consumption represents the utilization of an infrastructure’s physical attributes along a given section [22]. UIC 406 method defines a methodology to measure the capacity consumption based on compressing timetable graphs. Zhang [23] updated the norm for capacity measure as the time needed to fulfill the task list in train service-demand intention set. Heydar et al. [24] and Petering et al. [25] proposed a different definition of capacity; i.e., capacity is the minimal cycle length that can feasibly accommodate a given number of trains over a given section of track (double track, unidirectional) in each cycle. Zhang and Nie [26] proposed a minimal cycle time calculation model on the basis of periodic event scheduling problem for a given train line plan. In accordance with 2nd edition of UIC capacity leaflet [22], which defined the occupancy time of a line section as the timescale between the first and last train paths, we calculate the cycle length with formula (4) to minimize the capacity consumption for the network operators.(4)minF2=∑i=1n∑j=1j≠inhijkij.


### 2.3.3. Optimization from the Perspective of Operation

This objective is to create a train plan that is as robust as possible to achieve stability. That means it can both deal with relatively small disturbances and achieve a high punctuality in the real-time operations. Robustness reflects the degree to which trains depart and arrive according to the plan.The headway between subsequent trains is used by many scholars as a measure of robustness or a target for robustness in various ways [27]. Thus, we maximize the minimal buffer time between train pairs with formula (5) to optimize the stability objective from the perspective of operation.(5)F3=max1≤i≤nmin1≤j≤nj≠ihij−Hijkij.Formula (5) is a max-min objective function. According to Burggraeve [28], we introduce an auxiliary constraint as follows:(6)F3≤hij−Hijkij,1≤i≤n,1≤j≤n,j≠i.And, we change the objective function of formula (5) to the maximization of F3 as follows:(7)maxF3.


### 2.3.4. Constraints

According to the notations mentioned above, we put forward formulas (8) and (9) for calculation the value s of hij− and hijA.(8)hij−=minhij,yj+dj−yi+dikij,1≤i≤n,1≤j≤n,j≠i,(9)hijA=yj+dj−yi+dikij,1≤i≤n,1≤j≤n,j≠i.For any considered subsequent train pairs, the relationship of their departure times should follow the following formula:(10)yj≥yi+hij−Mkji,1≤i≤n,1≤j≤n,j≠i.For the pairwise train dispatching decisions, only one alternative arc of the train pairsi,j can be selected in Figure 3, so formulas (11) and (12) should be held.(11)kij=1,ifyi<yj0,otherwise,(12)kij+kji=1,1≤i≤n,1≤j≤n,j≠i.Regarding the security for trains running, any headway time should meet the requirements of the theoretical safety minimal headway time between the subsequent trains. Thus, formulas (13)–(15) should be obeyed.(13)hij≥Hij,1≤i≤n,1≤j≤n,j≠i,(14)hij−≥Hij,1≤i≤n,1≤j≤n,j≠i,(15)hijA≥Hij,1≤i≤n,1≤j≤n,j≠i.


### 2.3.5. Complete MSTTP Model

As what are analyzed above, we set up the complete mixed-speed train traffic planning (MSTTP) model as follows.Obj:(16)maxF1=αSSHR+1−αSAHR,minF2=∑i=1n∑j=1j≠inhijkij,maxF3,s.t.(17)hij−=minhij,yj+dj−yi+dikij,1≤i≤n,1≤j≤n,j≠i,hijA=yj+dj−yi+dikij1≤i≤n,1≤j≤n,j≠i,F3≤hij−Hijkij1≤i≤n,1≤j≤n,j≠i,yj≥yi+hij−Mkji,1≤i≤n,1≤j≤n,j≠i,kij=1,ifyi<yj,0,otherwise,kij+kji=1,1≤i≤n,1≤j≤n,j≠i,hij≥Hij,1≤i≤n,1≤j≤n,j≠i,hij−≥Hij,1≤i≤n,1≤j≤n,j≠i,hijA≥Hij,1≤i≤n,1≤j≤n,j≠i,M is a large positive numberα is a weight parameter and 0<α<1


## 2.3.1. Optimization from the Perspective of Passengers

Regarding the permutation of mixed-speed train traffic, in most cases we believe that heterogeneity could decrease the reliability of the train timetable comparing to its homogeneous counterpart [20]. However, we cannot deny that the customers’ preference should be the right paradigm in the market-oriented environment. Passenger travel behavior is far more complex and multifaceted. Assessing railway performances by merely measuring punctuality or capacity would provide an unfair picture of the level of service experienced by passengers [21]. On the other hand, heterogeneity also implies diversity and balance, which can provide a variety of train service for passengers within an acceptable headway. According to [20], there are two measures for representing the heterogeneity of trains, which is sum of shortest headway reciprocals (SSHR) and sum of arrival headway reciprocals (SAHR), respectively. To be complementary, we maximize both of them from the perspective of passenger optimization as follows:(1)maxF1=αSSHR+1−αSAHR,(2)SSHR=∑i=1n∑j=1j≠in1hij−,(3)SAHR=∑i=1n∑j=1j≠in1hijA.


## 2.3.2. Optimization from the Perspective of Capacity

Capacity consumption represents the utilization of an infrastructure’s physical attributes along a given section [22]. UIC 406 method defines a methodology to measure the capacity consumption based on compressing timetable graphs. Zhang [23] updated the norm for capacity measure as the time needed to fulfill the task list in train service-demand intention set. Heydar et al. [24] and Petering et al. [25] proposed a different definition of capacity; i.e., capacity is the minimal cycle length that can feasibly accommodate a given number of trains over a given section of track (double track, unidirectional) in each cycle. Zhang and Nie [26] proposed a minimal cycle time calculation model on the basis of periodic event scheduling problem for a given train line plan. In accordance with 2nd edition of UIC capacity leaflet [22], which defined the occupancy time of a line section as the timescale between the first and last train paths, we calculate the cycle length with formula (4) to minimize the capacity consumption for the network operators.(4)minF2=∑i=1n∑j=1j≠inhijkij.


## 2.3.3. Optimization from the Perspective of Operation

This objective is to create a train plan that is as robust as possible to achieve stability. That means it can both deal with relatively small disturbances and achieve a high punctuality in the real-time operations. Robustness reflects the degree to which trains depart and arrive according to the plan.The headway between subsequent trains is used by many scholars as a measure of robustness or a target for robustness in various ways [27]. Thus, we maximize the minimal buffer time between train pairs with formula (5) to optimize the stability objective from the perspective of operation.(5)F3=max1≤i≤nmin1≤j≤nj≠ihij−Hijkij.Formula (5) is a max-min objective function. According to Burggraeve [28], we introduce an auxiliary constraint as follows:(6)F3≤hij−Hijkij,1≤i≤n,1≤j≤n,j≠i.And, we change the objective function of formula (5) to the maximization of F3 as follows:(7)maxF3.


## 2.3.4. Constraints

According to the notations mentioned above, we put forward formulas (8) and (9) for calculation the value s of hij− and hijA.(8)hij−=minhij,yj+dj−yi+dikij,1≤i≤n,1≤j≤n,j≠i,(9)hijA=yj+dj−yi+dikij,1≤i≤n,1≤j≤n,j≠i.For any considered subsequent train pairs, the relationship of their departure times should follow the following formula:(10)yj≥yi+hij−Mkji,1≤i≤n,1≤j≤n,j≠i.For the pairwise train dispatching decisions, only one alternative arc of the train pairsi,j can be selected in Figure 3, so formulas (11) and (12) should be held.(11)kij=1,ifyi<yj0,otherwise,(12)kij+kji=1,1≤i≤n,1≤j≤n,j≠i.Regarding the security for trains running, any headway time should meet the requirements of the theoretical safety minimal headway time between the subsequent trains. Thus, formulas (13)–(15) should be obeyed.(13)hij≥Hij,1≤i≤n,1≤j≤n,j≠i,(14)hij−≥Hij,1≤i≤n,1≤j≤n,j≠i,(15)hijA≥Hij,1≤i≤n,1≤j≤n,j≠i.


## 2.3.5. Complete MSTTP Model

As what are analyzed above, we set up the complete mixed-speed train traffic planning (MSTTP) model as follows.Obj:(16)maxF1=αSSHR+1−αSAHR,minF2=∑i=1n∑j=1j≠inhijkij,maxF3,s.t.(17)hij−=minhij,yj+dj−yi+dikij,1≤i≤n,1≤j≤n,j≠i,hijA=yj+dj−yi+dikij1≤i≤n,1≤j≤n,j≠i,F3≤hij−Hijkij1≤i≤n,1≤j≤n,j≠i,yj≥yi+hij−Mkji,1≤i≤n,1≤j≤n,j≠i,kij=1,ifyi<yj,0,otherwise,kij+kji=1,1≤i≤n,1≤j≤n,j≠i,hij≥Hij,1≤i≤n,1≤j≤n,j≠i,hij−≥Hij,1≤i≤n,1≤j≤n,j≠i,hijA≥Hij,1≤i≤n,1≤j≤n,j≠i,M is a large positive numberα is a weight parameter and 0<α<1


## 3. Random-Key Genetic Algorithm (RKGA) Development

### 3.1. Main Algorithm of RKGA

The whole flowchart of the main algorithm RKGA is demonstrated in Figure4.Step 0. Initialize, i.e., determine the parameters of the total number of trains L, the population P, the crossover probability pc, the mutation probability pm, and the maximal iteration time N.Step 1. Number each train l, l=1,2,…,L, N=1.Step 2. Sequence the trains initially.Step 2.1. Generate a random number between 0 and 1 for each train number, and then take the random number as the gene.Step 2.2. Combine the random numbers of L trains altogether to form the random-key chromosome.Step 2.3. Sequence the trains according to the random number genes (from smallest to largest) in the random-key chromosome.Step 3. Generate P random-key chromosomes and train sequences by iterating step 2 P times to build the initial population.Step 4. For each train sequence, generate the headway time hij for the adjacent corresponding genes by invoking the subalgorithm for generation of train departure headway time (GTDHT).Step 5. For each sequence and headway time, check whether the constraints are satisfied or not.Step 6. For each sequence and headway time, calculate the fitness value by invoking the subalgorithm for fitness estimation function of RKGA.Step 7. Sequence the fitness values descendingly.Step 8. N=N+1, check the value of N; if N does not reach the maximal iteration times, turn to step 9, else stop calculation and output the solution with the largest fitness.Step 9. Select the top m best solutions according to the fitness value.Step 10. For the selected m best solutions, use crossover operator and mutation operator to generate the new solutions. The search is over the random-key space instead of the problem space.Step 10.1. For the random-key chromosomes corresponding to the selected m best solutions, invoke crossover operator so as to generate a new generation of random-key chromosomes, and then sequence the trains again according to the random number genes (from smallest to largest) in the random-key chromosome.Step 10.2. For the random-key chromosomes corresponding to the selected m best solutions, invoke mutation operator so as to generate a new generation of random-key chromosomes, and then sequence the trains again according to the random number genes (from smallest to largest) in the random-key chromosome.Step 11. Repeat step 4～step 8.Figure 4
Flowchart of RKGA.


### 3.2. Fitness Estimation Function of RKGA

For the multiobjectiveF1,F2, and F3, it can be standardized according to(18)Fi′=Fi1+FiforminFi,11+FiformaxFi.Thus, the standardization for the objectives of MSTTP is expressed as(19)F1′=11+F1,F2′=F21+F2,F3′=11+F3.Thus, the vector of the standardized objectives for MSTTP can be expressed as(20)minF1′,F2′,F3′.So far, we transform the multiobjective problem to its single-objective counterpart as formula (21) by introducing the linear weighting sum method.(21)minF′=aF1′+bF2′+cF3′,where the weighting parameters 0<a<1, 0<b<1, 0<c<1, and a+b+c=1.Then, by using formula (22), we can get the fitness function for the random-key genetic algorithm, which means the larger the value of F is, the better is for the solution to MSTTP model.(22)maxF=1F′.However, any solution to MSTTP must satisfy its constraints. Considering the possible violence toward the constraints, we modify the fitness functionF by adding a penalty to it as(23)F=F+penalty,where(24)penalty=0,if all constraints are satisfied,a large positive number,otherwise.


### 3.3. Subalgorithm for Generation of Train Departure Headway Time (GTDHT)

Headway time must guarantee that the flow of mixed-speed trains traveling at different rates along the rail line section must be continuous. Letvi and vj denote the speed types (unit: km/h) of adjacent trains, Hijh the maximum reasonable headway time (unit: minute) between adjacent trains (which can be estimated from railway operational practice), s the length of the railway line section (unit: km), and the expression randomδ,φ generates a random number in δ,φ. The pseudocode for subalgorithm for generation of train departure headway time (GTDHT) is as follows.Ifvi≥vj,(25)hij=randomHij+F3,Hijh.Else,(26)hij=randomHij+F3,Hijh+svi+svj∗60.


### 3.4. Crossover Operator

Step 1. Assume pcmax and pcmin are the given upper and lower limits for crossover possibility. fl is the fitness value for a certain chromosome individual. favg is the average fitness value of the population; i.e., favg=∑l=1Lfl/L⋅fmax is the maximal fitness value of the population. We adopt the self-adaption method to calculate the crossover possibility Pc as(27)pc=pcmax−fl−favgpcmax−pcminfmax−favg,fl>favg,pcmax,fl≤favg.Step 2. Set i = 1.Step 3. Judge whether we can impose the crossover operation on chromosome individual i.Step 3.1. Select chromosome individual i, and calculate the crossover possibility pi using formula (27).Step 3.2. Generate a random number (0, 1); if random (0, 1) < pi, then put chromosome individual i into the arrays CROSS for crossover operation.Step 4.i=i+1. If i≤m, turn to step 3, else turn to step 5.Step 5. Reset i = 1. Assume the number of chromosome individuals in the arrays for crossover operation is mc.Step 6. Operate single-point crossover.Step 6.1. Select chromosome individuals i and i + 1 (each contains L genes) from the arrays CROSS.Step 6.2. An integer position k is selected randomly between [1, L], and the feature information of chromosome individuals i and i + 1 is exchanged between the parents before this point.Step 6.3. Put the new chromosome individuals into the new population after crossover operation.Step 7.i=i+2. If i<mc, turn to step 6; else turn to step 8.Step 8. The crossover operation is over.


### 3.5. Mutation Operator

Step 1. Assume pmmax and pmmin are the given upper and lower limits for mutation possibility. fl is the fitness value for a certain chromosome individual. favg is the average fitness value of the population; i.e., favg=∑l=1Lfl/L⋅fmax is the maximal fitness value of the population. We adopt the self-adaption method to calculate the mutation possibility pm as(28)pm=pmmax−fl−favgpmmax−pmminfmax−favg,fl>favg,pmmax,f1≤favg.Step 2. Set i = 1.Step 3. Judge whether we can impose the mutation operation on chromosome individual i.Step 3.1. Select chromosome individual i, and calculate the mutation possibility pi using formula (28).Step 3.2. Generate a random number (0, 1) in (0, 1); if random (0, 1) < pi, then turn to step 4 because chromosome individual i can be executed by the mutation operation, else turn to step 5.Step 4. Operate mutation.Step 4.1. For chromosome individual i, an integer position k is selected randomly between (1, L), and generate a new random number (0, 1) to replace its counterpart corresponding to position k.Step 4.2. Put the new chromosome individuals into the new population after crossover operation.Step 5.i=i+1. If i<m, then turn to step 3, else turn to step 6.Step 6. Mutation operation is over.


## 3.1. Main Algorithm of RKGA

The whole flowchart of the main algorithm RKGA is demonstrated in Figure4.Step 0. Initialize, i.e., determine the parameters of the total number of trains L, the population P, the crossover probability pc, the mutation probability pm, and the maximal iteration time N.Step 1. Number each train l, l=1,2,…,L, N=1.Step 2. Sequence the trains initially.Step 2.1. Generate a random number between 0 and 1 for each train number, and then take the random number as the gene.Step 2.2. Combine the random numbers of L trains altogether to form the random-key chromosome.Step 2.3. Sequence the trains according to the random number genes (from smallest to largest) in the random-key chromosome.Step 3. Generate P random-key chromosomes and train sequences by iterating step 2 P times to build the initial population.Step 4. For each train sequence, generate the headway time hij for the adjacent corresponding genes by invoking the subalgorithm for generation of train departure headway time (GTDHT).Step 5. For each sequence and headway time, check whether the constraints are satisfied or not.Step 6. For each sequence and headway time, calculate the fitness value by invoking the subalgorithm for fitness estimation function of RKGA.Step 7. Sequence the fitness values descendingly.Step 8. N=N+1, check the value of N; if N does not reach the maximal iteration times, turn to step 9, else stop calculation and output the solution with the largest fitness.Step 9. Select the top m best solutions according to the fitness value.Step 10. For the selected m best solutions, use crossover operator and mutation operator to generate the new solutions. The search is over the random-key space instead of the problem space.Step 10.1. For the random-key chromosomes corresponding to the selected m best solutions, invoke crossover operator so as to generate a new generation of random-key chromosomes, and then sequence the trains again according to the random number genes (from smallest to largest) in the random-key chromosome.Step 10.2. For the random-key chromosomes corresponding to the selected m best solutions, invoke mutation operator so as to generate a new generation of random-key chromosomes, and then sequence the trains again according to the random number genes (from smallest to largest) in the random-key chromosome.Step 11. Repeat step 4～step 8.Figure 4
Flowchart of RKGA.


## 3.2. Fitness Estimation Function of RKGA

For the multiobjectiveF1,F2, and F3, it can be standardized according to(18)Fi′=Fi1+FiforminFi,11+FiformaxFi.Thus, the standardization for the objectives of MSTTP is expressed as(19)F1′=11+F1,F2′=F21+F2,F3′=11+F3.Thus, the vector of the standardized objectives for MSTTP can be expressed as(20)minF1′,F2′,F3′.So far, we transform the multiobjective problem to its single-objective counterpart as formula (21) by introducing the linear weighting sum method.(21)minF′=aF1′+bF2′+cF3′,where the weighting parameters 0<a<1, 0<b<1, 0<c<1, and a+b+c=1.Then, by using formula (22), we can get the fitness function for the random-key genetic algorithm, which means the larger the value of F is, the better is for the solution to MSTTP model.(22)maxF=1F′.However, any solution to MSTTP must satisfy its constraints. Considering the possible violence toward the constraints, we modify the fitness functionF by adding a penalty to it as(23)F=F+penalty,where(24)penalty=0,if all constraints are satisfied,a large positive number,otherwise.


## 3.3. Subalgorithm for Generation of Train Departure Headway Time (GTDHT)

Headway time must guarantee that the flow of mixed-speed trains traveling at different rates along the rail line section must be continuous. Letvi and vj denote the speed types (unit: km/h) of adjacent trains, Hijh the maximum reasonable headway time (unit: minute) between adjacent trains (which can be estimated from railway operational practice), s the length of the railway line section (unit: km), and the expression randomδ,φ generates a random number in δ,φ. The pseudocode for subalgorithm for generation of train departure headway time (GTDHT) is as follows.Ifvi≥vj,(25)hij=randomHij+F3,Hijh.Else,(26)hij=randomHij+F3,Hijh+svi+svj∗60.


## 3.4. Crossover Operator

Step 1. Assume pcmax and pcmin are the given upper and lower limits for crossover possibility. fl is the fitness value for a certain chromosome individual. favg is the average fitness value of the population; i.e., favg=∑l=1Lfl/L⋅fmax is the maximal fitness value of the population. We adopt the self-adaption method to calculate the crossover possibility Pc as(27)pc=pcmax−fl−favgpcmax−pcminfmax−favg,fl>favg,pcmax,fl≤favg.Step 2. Set i = 1.Step 3. Judge whether we can impose the crossover operation on chromosome individual i.Step 3.1. Select chromosome individual i, and calculate the crossover possibility pi using formula (27).Step 3.2. Generate a random number (0, 1); if random (0, 1) < pi, then put chromosome individual i into the arrays CROSS for crossover operation.Step 4.i=i+1. If i≤m, turn to step 3, else turn to step 5.Step 5. Reset i = 1. Assume the number of chromosome individuals in the arrays for crossover operation is mc.Step 6. Operate single-point crossover.Step 6.1. Select chromosome individuals i and i + 1 (each contains L genes) from the arrays CROSS.Step 6.2. An integer position k is selected randomly between [1, L], and the feature information of chromosome individuals i and i + 1 is exchanged between the parents before this point.Step 6.3. Put the new chromosome individuals into the new population after crossover operation.Step 7.i=i+2. If i<mc, turn to step 6; else turn to step 8.Step 8. The crossover operation is over.


## 3.5. Mutation Operator

Step 1. Assume pmmax and pmmin are the given upper and lower limits for mutation possibility. fl is the fitness value for a certain chromosome individual. favg is the average fitness value of the population; i.e., favg=∑l=1Lfl/L⋅fmax is the maximal fitness value of the population. We adopt the self-adaption method to calculate the mutation possibility pm as(28)pm=pmmax−fl−favgpmmax−pmminfmax−favg,fl>favg,pmmax,f1≤favg.Step 2. Set i = 1.Step 3. Judge whether we can impose the mutation operation on chromosome individual i.Step 3.1. Select chromosome individual i, and calculate the mutation possibility pi using formula (28).Step 3.2. Generate a random number (0, 1) in (0, 1); if random (0, 1) < pi, then turn to step 4 because chromosome individual i can be executed by the mutation operation, else turn to step 5.Step 4. Operate mutation.Step 4.1. For chromosome individual i, an integer position k is selected randomly between (1, L), and generate a new random number (0, 1) to replace its counterpart corresponding to position k.Step 4.2. Put the new chromosome individuals into the new population after crossover operation.Step 5.i=i+1. If i<m, then turn to step 3, else turn to step 6.Step 6. Mutation operation is over.


## 4. Results and Discussion of a Case Study

### 4.1. Experiment Design

In the case study, the rail system considered is a line section encompassing a territory of 180 km with 15 mixed-speed trains in each cycle of the timetable. The details about the trains are shown in Table1. According to Tian [29], we determine the theoretical safety minimum headway time of subsequent trains as Table 2. And, we set the parameters for experimental trials as Table 3.Table 1
Identifier and speed type of trains within one cycle of the timetable.
Serial numberTrain identifierSpeed type of train (km/h)1L013002L023003L033004L042705L052706L062707L072508L082509L0925010L1025011L1125012L1223013L1323014L1420015L15200Table 2
Theoretical safety minimal headway time of subsequent trains (unit: minute).
3002702502302003005533327095453250151044323018141243200262018164Note. The items in the first column represent the speed type of the proceeding train, the items in the first row represent the speed type of the following train, and other numbers in the table represent the theoretical safety minimum headway time of adjacent trains.Table 3
Parameters for experimental trials.
Serial numberParameter nameParameter valueParameter meanings1P100Population scale2M40Number of selected chromosome individuals3pcmin0.4Lower limit of crossover possibility4pcmax0.8Upper limit of crossover possibility5pmmin0.001Lower limit of mutation possibility6pmmax0.1Upper limit of mutation possibility7α0.6Weight ofSSHR8A0.5Weight of objective for passenger optimization9B0.3Weight of objective for capacity optimization10C0.2Weight of objective for operation optimization


### 4.2. Results of Fitness and Multiobjective Value

The algorithm described above is coded with visual studio C#, and it can work out the optimized results within two minutes. The results for fitness value in Figure5 are obtained by executing the RKGA in 100, 150, and 200 generations individually. After experimental trials in 200 generations, we get the optimal heterogeneity value, i.e., 1.6121; the optimal cycle time, i.e., 179.7565 min; and the optimized minimal buffer time, i.e., 1 min, respectively.Figure 5
The fitness value of generations.


### 4.3. Results of Train Sequence

In general, the speed relationship between the sequential train pairs can be grouped into three traffic scenarios such as s1, s2, and s3. In scenario s1, the speed of the previous train is greater than that of its following counterpart. In scenario s2, the speed of the prior train is less than that of its succeeding one, while in scenario s3, the speed of two adjacent trains is identical to each other. The former two scenarios produce the heterogeneous traffic, and the scenario s3 belongs to the kind of homogeneous traffic condition. Statistically, 42.86% of the 14 sequenced train pairs fall into the scenario s1, and the percentage of two other scenarios are equal to each other, both of which are 28.57%, as shown in Table4. As can be seen, both the heterogeneous traffic and the homogeneous traffic coexist in the optimized train sequences. The homogeneous traffic scenario s3 emerges in the top three high speeds of trains, e.g., 300 km/h, 270 km/h, and 250 km/h. Particularly, three trains with the highest speed, i.e., 300 km/h, are arranged successively. Totally, the heterogeneity/homogeneity ratio is 2.5.Table 4
Optimized sequence of trains in one cycle of timetable.
L01L02L03L04L05L06L07L08L09L10L11L12L13L14L15L01010000000000000L02000001000000000L03100000000000000L04000000000010000L05000100000000000L06000000000000000L07000000010000000L08000000000001000L09000000000000100L10000000000000001L11001000000000000L12000010000000000L13000000000000010L14000000000100000L15000000100000000Note. The first column represents the proceeding train in the sequence, the first row represents the following train in the sequence, the number 1 in the table represents two trains are adjacent to each other, and the number 0 represents two trains are not adjacent.


### 4.4. Results of Train Headway Time

The optimized train departure headway time ranges from 4 min to 31 min, and its arrival counterpart disperses from 5 min to 20 min, as shown in Figure6. In Figure 6, the horizontal axis represents the train sequence number, while the vertical axis represents the headway time. Among all of the departure/arrival headway times, i.e., the dep.time headway and the arr.time headway, the smallest departure headway time emerges between trains L13 and L14, the speed of which is 230 km/h and 200 km/h, respectively; the largest departure headway time emerges between trains L15 and L07, the speed of which is 200 km/h and 250 km/h, respectively. Obviously, the variance of the departure headway time is sharper than that of its arrival counterpart. As far as the three scenarios defined before are concerned, in scenario s1, the departure headway time is always less than its corresponding arrival headway time over the trains’ running distance; in scenario s2, the situation is completely reverse; in scenario s3, they are equal.Figure 6
Spread of departure/arrival headway time.


### 4.5. Discussion

In the current work, we built the MSTTP model and RKGA for structure optimization of the mixed-speed train traffic for a cyclic timetable in a passenger railway line section. They are of permutation nature. Our study includes a high diversity of train speeds. With the known average speed and given number of trains, we get the optimized train plans from random variations of train sequence and headway time, which can represent a more general significance from the mathematical point of view. Moreover, it ensures the robustness of the timetable as possible as it can by means of random permutation and iteration.Compared with the previous studies, we find the quantitative proportion of heterogeneity/homogeneity (e.g., 2.5) about the optimized distribution of the mixed train traffic, instead of the merely qualitative assessment. It is a mathematical fact. The proportion is greater than 1, the potential reason for which is that we allocate greater weight value for the objective of heterogeneity, i.e., parametera = 0.5, from the perspective of passenger optimization. Usually, rail operators tend to think in terms of moving vehicles instead of people. However, putting customer first and tailoring the system to their needs is critical to success. In tune with this viewpoint, we set the values for parameters a, b, and c as Table 3 in the phase of experiment design. To a more rational extent, we achieve a comprehensively balanced solution (Table 4, Figures 5 and 6) among all of the timetabling stakeholders from the multiobjective optimization. Moreover, the higher the speed of the train is, the higher the possibility is that the trains of the same speed are sequentially bundled together to form the homogeneous traffic in a mixed traffic condition.We find the link between the train headway time and the train sequence. For the mixed-speed train traffic, e.g., the traffic scenarios s1 and s2, the train headway time is not only a function of its speed, but also sequence dependent. In scenario s1, the minimal headway time of the sequential trains in the railway line section equals their corresponding departure headway time; in scenario s2, with other similar conditions, the minimal headway time of the sequential trains in the railway line section equals their corresponding arrival headway time. However, for the homogeneous traffic as scenario s3, there is no difference between the departure and arrival headway time. In turn, these findings would be instrumental in a further revision of the theoretical safety minimal headway time of subsequent trains as shown in Table2, which is the prerequisite for train planning.


## 4.1. Experiment Design

In the case study, the rail system considered is a line section encompassing a territory of 180 km with 15 mixed-speed trains in each cycle of the timetable. The details about the trains are shown in Table1. According to Tian [29], we determine the theoretical safety minimum headway time of subsequent trains as Table 2. And, we set the parameters for experimental trials as Table 3.Table 1
Identifier and speed type of trains within one cycle of the timetable.
Serial numberTrain identifierSpeed type of train (km/h)1L013002L023003L033004L042705L052706L062707L072508L082509L0925010L1025011L1125012L1223013L1323014L1420015L15200Table 2
Theoretical safety minimal headway time of subsequent trains (unit: minute).
3002702502302003005533327095453250151044323018141243200262018164Note. The items in the first column represent the speed type of the proceeding train, the items in the first row represent the speed type of the following train, and other numbers in the table represent the theoretical safety minimum headway time of adjacent trains.Table 3
Parameters for experimental trials.
Serial numberParameter nameParameter valueParameter meanings1P100Population scale2M40Number of selected chromosome individuals3pcmin0.4Lower limit of crossover possibility4pcmax0.8Upper limit of crossover possibility5pmmin0.001Lower limit of mutation possibility6pmmax0.1Upper limit of mutation possibility7α0.6Weight ofSSHR8A0.5Weight of objective for passenger optimization9B0.3Weight of objective for capacity optimization10C0.2Weight of objective for operation optimization


## 4.2. Results of Fitness and Multiobjective Value

The algorithm described above is coded with visual studio C#, and it can work out the optimized results within two minutes. The results for fitness value in Figure5 are obtained by executing the RKGA in 100, 150, and 200 generations individually. After experimental trials in 200 generations, we get the optimal heterogeneity value, i.e., 1.6121; the optimal cycle time, i.e., 179.7565 min; and the optimized minimal buffer time, i.e., 1 min, respectively.Figure 5
The fitness value of generations.


## 4.3. Results of Train Sequence

In general, the speed relationship between the sequential train pairs can be grouped into three traffic scenarios such as s1, s2, and s3. In scenario s1, the speed of the previous train is greater than that of its following counterpart. In scenario s2, the speed of the prior train is less than that of its succeeding one, while in scenario s3, the speed of two adjacent trains is identical to each other. The former two scenarios produce the heterogeneous traffic, and the scenario s3 belongs to the kind of homogeneous traffic condition. Statistically, 42.86% of the 14 sequenced train pairs fall into the scenario s1, and the percentage of two other scenarios are equal to each other, both of which are 28.57%, as shown in Table4. As can be seen, both the heterogeneous traffic and the homogeneous traffic coexist in the optimized train sequences. The homogeneous traffic scenario s3 emerges in the top three high speeds of trains, e.g., 300 km/h, 270 km/h, and 250 km/h. Particularly, three trains with the highest speed, i.e., 300 km/h, are arranged successively. Totally, the heterogeneity/homogeneity ratio is 2.5.Table 4
Optimized sequence of trains in one cycle of timetable.
L01L02L03L04L05L06L07L08L09L10L11L12L13L14L15L01010000000000000L02000001000000000L03100000000000000L04000000000010000L05000100000000000L06000000000000000L07000000010000000L08000000000001000L09000000000000100L10000000000000001L11001000000000000L12000010000000000L13000000000000010L14000000000100000L15000000100000000Note. The first column represents the proceeding train in the sequence, the first row represents the following train in the sequence, the number 1 in the table represents two trains are adjacent to each other, and the number 0 represents two trains are not adjacent.


## 4.4. Results of Train Headway Time

The optimized train departure headway time ranges from 4 min to 31 min, and its arrival counterpart disperses from 5 min to 20 min, as shown in Figure6. In Figure 6, the horizontal axis represents the train sequence number, while the vertical axis represents the headway time. Among all of the departure/arrival headway times, i.e., the dep.time headway and the arr.time headway, the smallest departure headway time emerges between trains L13 and L14, the speed of which is 230 km/h and 200 km/h, respectively; the largest departure headway time emerges between trains L15 and L07, the speed of which is 200 km/h and 250 km/h, respectively. Obviously, the variance of the departure headway time is sharper than that of its arrival counterpart. As far as the three scenarios defined before are concerned, in scenario s1, the departure headway time is always less than its corresponding arrival headway time over the trains’ running distance; in scenario s2, the situation is completely reverse; in scenario s3, they are equal.Figure 6
Spread of departure/arrival headway time.


## 4.5. Discussion

In the current work, we built the MSTTP model and RKGA for structure optimization of the mixed-speed train traffic for a cyclic timetable in a passenger railway line section. They are of permutation nature. Our study includes a high diversity of train speeds. With the known average speed and given number of trains, we get the optimized train plans from random variations of train sequence and headway time, which can represent a more general significance from the mathematical point of view. Moreover, it ensures the robustness of the timetable as possible as it can by means of random permutation and iteration.Compared with the previous studies, we find the quantitative proportion of heterogeneity/homogeneity (e.g., 2.5) about the optimized distribution of the mixed train traffic, instead of the merely qualitative assessment. It is a mathematical fact. The proportion is greater than 1, the potential reason for which is that we allocate greater weight value for the objective of heterogeneity, i.e., parametera = 0.5, from the perspective of passenger optimization. Usually, rail operators tend to think in terms of moving vehicles instead of people. However, putting customer first and tailoring the system to their needs is critical to success. In tune with this viewpoint, we set the values for parameters a, b, and c as Table 3 in the phase of experiment design. To a more rational extent, we achieve a comprehensively balanced solution (Table 4, Figures 5 and 6) among all of the timetabling stakeholders from the multiobjective optimization. Moreover, the higher the speed of the train is, the higher the possibility is that the trains of the same speed are sequentially bundled together to form the homogeneous traffic in a mixed traffic condition.We find the link between the train headway time and the train sequence. For the mixed-speed train traffic, e.g., the traffic scenarios s1 and s2, the train headway time is not only a function of its speed, but also sequence dependent. In scenario s1, the minimal headway time of the sequential trains in the railway line section equals their corresponding departure headway time; in scenario s2, with other similar conditions, the minimal headway time of the sequential trains in the railway line section equals their corresponding arrival headway time. However, for the homogeneous traffic as scenario s3, there is no difference between the departure and arrival headway time. In turn, these findings would be instrumental in a further revision of the theoretical safety minimal headway time of subsequent trains as shown in Table2, which is the prerequisite for train planning.


## 5. Conclusion

Trains can be optimally spread over the period of the cyclic timetable. Focused on the structure optimization of the mixed-speed train traffic for cyclic timetable, this paper puts forward a new mixed-speed train traffic planning (MSTTP) model and the random-key genetic algorithm (RKGA). The MSTTP model is recast from the alternative graph (AG) and optimizes three indicators, i.e., heterogeneity, cycle time, and buffer time, which correspond to diversity of train service toward passenger, capacity consumption of rail network, and stability of train operation, respectively. Compared with the conventional algorithms, the proposed model and algorithm have the following advantages:(i)
Both sequence and headway time are taken into account as the core components of the timetable structure simultaneously. Taken together, the key results of our study have been the optimal arrangement of the mixed-speed train traffic, by integrating the sequencing problem with the headway time optimizing together for a cyclic timetable, and demonstration of how they can be achieved.(ii)
The time complexity of the proposed algorithm is low, and it can satisfy the requirement of real-time and fast computation.(iii)
Optimum headway time and train sequence can be recommended according to the concerns of the stakeholders, i.e., heterogeneity, cycle time, and buffer time, which correspond to diversity of train service toward passenger, capacity consumption of rail network, and stability of train operation, respectively.(iv)
Furthermore, it can be meaningful for the reasonable allocation of buffer time, which is related to the stability of the timetable.In addition, when taking the overtaking issues into account, further studies should explore the dynamic headway time according to the change of train sequence at the overtaking place. As enumerated in Landex and Kaas [5], we can firstly divide the line section due to overtaking, then dealing with each section as such a subproblem as we modeled in this article. In this way, the problem studied in this paper occurs as a subproblem in a decomposition procedure for more complicated railway line sections with overtaking stations.



---

*Source: 2228197-2022-01-04.xml*