# Headway Optimisation for Metro Lines Based on Timetable Simulation and Simulated Annealing

Authors: Yong Cui; Qing Yu; Chenyang Wang
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

To improve the capacity of metro systems, it is important to evaluate and minimise headway, which is defined as the time interval calculated from “head to head” between two successive trains in this paper. With existing approaches for headway optimisation, the headway for moving block systems is often calculated based on the safe braking distance. However, the blocking time at movable elements (e.g., switches and crossings) and stops has special characteristics. Since train separation is dominated by a signalling system, the distance between two successive trains at movable elements and stops exceeds the safe braking distance. In this work, the theory for building a blocking time model and calculating line headway for moving block systems is investigated. A workflow to minimise line headway is designed to derive an optimised velocity profile before the identified bottlenecks. Several different optimisation algorithms, including grid search, Monte Carlo, and simulated annealing, are developed and compared. Among them, simulated annealing shows the best optimisation capability with the least computational effort. The designed algorithm has been tested for Hefei-Metro Line 1, and the line headway can be reduced from 116.776 seconds to 105.806 seconds. If the acceptable rate of the increased transport is set at 1%, the line capacity will increase by 6.5%.


---

## Body

## 1. Introduction

To improve the capacity of metro systems, it is important to evaluate and minimise headway, which is defined as the time or distance interval calculated from “head to head” between two successive trains [1]. In metro systems, operations are usually organised separately for each line. The capacity of a line can be calculated by dividing a time period (e.g., one hour) by the line headway evaluated through the time interval. The term “headway” used in this paper refers to the time interval between two successive trains.During the whole train run, the headway between two successive trains is varied continuously due to the changing velocity and operation conditions. On each line, the line headway is the minimum headway between two trains along the whole train run. To determine the minimum headway, a detailed blocking time model should be established.The purpose of calculating blocking time is to ensure a safe distance between trains, which depends on the principle of train separation. In railway operations, there are several different principles for train separation, including fixed blocks, moving blocks [2], and virtual moving blocks [3]. Communication-based train control (CBTC) is a typical signalling system based on the principle of moving blocks. It is widely implemented in metro systems, where the safety distance is not enforced by fixed signals but controlled based on the position and velocity of trains in real time.Since the 1990s, many studies have focused on headway optimisation for moving block systems. In Section2, a review of existing approaches is presented. The deficiencies and the necessity for improvements in headway optimisation for metro lines can be summarised as follows:(i)
In the existing approaches for headway optimisation, headway is simply derived from the running time calculation for the safe braking distance between two trains. However, the blocking time at movable elements (e.g., switches and crossings) and stops has special characteristics. Since train separation is dominated by signalling systems, the distance between two successive trains at movable elements exceeds the safe braking distance. Additional blocking time between two trains should be maintained to ensure that the movable elements can be blocked and released as a whole (see Section3.1). Many studies focus on reducing train headway near station areas. However, the bottlenecks of line capacity for moving block systems are often located near the areas of switches and crossings.(ii)
If the exact blocking time model is considered, the analytical models for headway optimisation are not capable of handling complex infrastructure layouts. The investigation into combining simulation and optimisation approaches should be deeply investigated to balance the line capacity and the transport time of train runs.(iii)
For some application purposes, e.g., energy-saving control or regulation of train movements, the headway is only set as a constraint for optimisation. The objective of optimisation is to minimise energy consumption or total delays. The headway itself is not minimised.This paper fills this research gap. A detailed blocking time model is applied to evaluate the line headway for moving block systems. Unlike most studies that only focus on simple infrastructure layouts, bottlenecks near switches and crossings can be identified through simulation-based capacity analysis. Furthermore, an optimisation model is developed to minimise the line headway as the main objective, while the acceptable transport time is set as a constraint during the optimisation process.In Section3, the blocking time model and the calculation of line headway for metro systems are presented in detail. Based on the model, the algorithm for identifying the bottleneck in the line’s headway is developed. Several simulation-based optimisation approaches are designed and compared in Section 4. These approaches are tested and validated in Section 5 based on the real case study of Hefei Metro Line 1.


## 2. Literature Review on Minimising Headway for Metro Lines

In the literature review, the methods to minimise line headway are first investigated. The principles and disadvantages of the existing approaches are summarised in Section2.1. To carry out microscopic calculations, the simulation methods and the blocking time model are presented. Many different approaches in regulating train runs and the applied optimisation algorithms are reviewed in Section 2.2.


### 2.1. Approaches to Minimise Line Headway

To minimise the headway of moving block systems, the genetic algorithm is used in [4] so that an optimal driving style can be obtained. In this work, it was found that the minimum headway can be reduced by decreasing the approaching velocity near the stop area. However, the exact headway calculation for metro operations is not implemented. The behaviour at movable elements (switches and crossings) is not considered. In [5], regulation strategies adapted to CBTC systems were developed. In this work, the objective is not to minimise the line headway; the headway is only set as a constraint for automatic train supervision. In [6], the operation on metro lines is simulated, and the minimum headway of the CBTC system is analysed. Although the safety-braking distance is calculated according to IEEE 1474.1, the blocking time for releasing infrastructure resources is not fully considered.Today, train-to-train communication systems are proposed to improve the efficiency of railway operation and control. Supported by exchanging train information in real time, the features of relative distance braking can be implemented [7]. The idea of separating trains by an optimised distance to minimise headway is also presented in [8]. A dynamic programming-based searching approach is applied in [9]. Line headway can be minimised by the multistep braking operation of trains during the phase of station entry. Although an analytic method can be used to verify the algorithm, it is difficult to model a real line with a high irregularity of velocity limits, which are subjected to the changing infrastructure layouts, curvatures, and gradients along the line.The existing methods to minimise line headway are implemented by reducing velocity near bottlenecks, which has been proven to be an effective approach. However, the exact blocking time on movable elements is not considered in existing methods. Furthermore, some analytic models are not capable of handling very complex infrastructure layouts.


### 2.2. Simulation Methods and Train Regulation

Simulation approaches are capable of mimicking very detailed railway models and complicated operations. A detailed blocking time model used in capacity research for moving block systems is presented in [10]. The characteristics of the blocking time bands in the diagram are reviewed for different infrastructure elements, including switches and stops. Although the review does not concentrate on the algorithm of headway minimisation, it can be referred to as the theoretical basis for blocking time modelling and headway calculation.Other research on moving block systems focuses on energy-saving solutions. For example, energy-saving control for moving block systems is designed and simulated in [11]. In [12], a genetic algorithm was applied for energy-efficient train operation on a metro line. A fuzzy train tracking algorithm for CBTC-equipped metro lines is described in [13]. Mixed-integer linear programming is applied in [14, 15] to meet actual passenger demands and achieve energy-efficient planning. In these approaches, the minimum line headway is not considered. In [16], both headway and energy-efficient driving styles are considered. However, the minimum headway is only calculated as a constraint for maintaining the safety distance based on a simplified braking model. In [17], population-based evolutionary algorithms and different solution encoding variants were applied. The passenger distribution along platforms and within vehicles is included in the simulation model. The blocking time model and safety-braking distance between successive trains are not considered in this passenger-oriented solution. Several optimisation methods can be applied to reach the maximum line capacity for moving block systems. In [18], the genetic algorithm and the simulated annealing method were combined. In [19], an algorithm based on swarm intelligence was developed.Although the main purpose of the research presented in Section2.2 is not to focus on headway minimisation, the blocking time model presented in [10] is used in this work. Inspired by the existing approaches, different algorithms are implemented and compared to minimise the line headway of moving block systems in this work. The important parameters that influence line headway are investigated. All of these algorithms are supported by simulation approaches, where the core of the simulation model depends on the theory of blocking time and headway calculation.


## 2.1. Approaches to Minimise Line Headway

To minimise the headway of moving block systems, the genetic algorithm is used in [4] so that an optimal driving style can be obtained. In this work, it was found that the minimum headway can be reduced by decreasing the approaching velocity near the stop area. However, the exact headway calculation for metro operations is not implemented. The behaviour at movable elements (switches and crossings) is not considered. In [5], regulation strategies adapted to CBTC systems were developed. In this work, the objective is not to minimise the line headway; the headway is only set as a constraint for automatic train supervision. In [6], the operation on metro lines is simulated, and the minimum headway of the CBTC system is analysed. Although the safety-braking distance is calculated according to IEEE 1474.1, the blocking time for releasing infrastructure resources is not fully considered.Today, train-to-train communication systems are proposed to improve the efficiency of railway operation and control. Supported by exchanging train information in real time, the features of relative distance braking can be implemented [7]. The idea of separating trains by an optimised distance to minimise headway is also presented in [8]. A dynamic programming-based searching approach is applied in [9]. Line headway can be minimised by the multistep braking operation of trains during the phase of station entry. Although an analytic method can be used to verify the algorithm, it is difficult to model a real line with a high irregularity of velocity limits, which are subjected to the changing infrastructure layouts, curvatures, and gradients along the line.The existing methods to minimise line headway are implemented by reducing velocity near bottlenecks, which has been proven to be an effective approach. However, the exact blocking time on movable elements is not considered in existing methods. Furthermore, some analytic models are not capable of handling very complex infrastructure layouts.


## 2.2. Simulation Methods and Train Regulation

Simulation approaches are capable of mimicking very detailed railway models and complicated operations. A detailed blocking time model used in capacity research for moving block systems is presented in [10]. The characteristics of the blocking time bands in the diagram are reviewed for different infrastructure elements, including switches and stops. Although the review does not concentrate on the algorithm of headway minimisation, it can be referred to as the theoretical basis for blocking time modelling and headway calculation.Other research on moving block systems focuses on energy-saving solutions. For example, energy-saving control for moving block systems is designed and simulated in [11]. In [12], a genetic algorithm was applied for energy-efficient train operation on a metro line. A fuzzy train tracking algorithm for CBTC-equipped metro lines is described in [13]. Mixed-integer linear programming is applied in [14, 15] to meet actual passenger demands and achieve energy-efficient planning. In these approaches, the minimum line headway is not considered. In [16], both headway and energy-efficient driving styles are considered. However, the minimum headway is only calculated as a constraint for maintaining the safety distance based on a simplified braking model. In [17], population-based evolutionary algorithms and different solution encoding variants were applied. The passenger distribution along platforms and within vehicles is included in the simulation model. The blocking time model and safety-braking distance between successive trains are not considered in this passenger-oriented solution. Several optimisation methods can be applied to reach the maximum line capacity for moving block systems. In [18], the genetic algorithm and the simulated annealing method were combined. In [19], an algorithm based on swarm intelligence was developed.Although the main purpose of the research presented in Section2.2 is not to focus on headway minimisation, the blocking time model presented in [10] is used in this work. Inspired by the existing approaches, different algorithms are implemented and compared to minimise the line headway of moving block systems in this work. The important parameters that influence line headway are investigated. All of these algorithms are supported by simulation approaches, where the core of the simulation model depends on the theory of blocking time and headway calculation.


## 3. Headway Calculation and Bottleneck Identification with an Exact Blocking Time Model

### 3.1. Headway Calculation and Blocking Time Model

The headway of a metro line is calculated by the difference between the first train and the following train. In a metro line, the train headway along the train run can be simplified as the blocking time at each point, as long as the same type of train is running along the same line with the same velocity profile. In this paper, this simplification is acceptable since only the line headway at peak hours is of interest.A simplified braking model and the method to calculate blocking time are illustrated in Figure1. The head of the train is located at position A. The blocking time at position A is the sum of the time for safe braking (t1) and the time for releasing the occupied infrastructure (t2). To calculate the time for safe braking, the distance for safe braking should be determined. The curve of the ATP (Automatic Train Protection) profile defines the velocity supervised by ATP systems. However, the braking distance calculated from the ATP profile is not sufficient for safe braking since the worst case should be fully considered. At point A, a special reaction time for train-borne ATP systems is needed. The train can still be accelerated before the propulsion of the train is disabled and emergency braking is initiated. After emergency braking is applied, the train will be braked at point D, which defines the limit of movement authority. The whole emergency brake curve covers the distance from A to D. In addition, the distance for position uncertainty from D to E should be included. The time t1 used for movement from A to E is therefore determined. To calculate the time required for releasing the occupied infrastructure, the time t2 is derived from A to C, which covers the length of the train and the position uncertainty from A to B. In this simplified diagram, the ATP overspeed allowance and the speed measurement error, as well as the time for communication, are ignored. A detailed illustration of the braking model is presented in [20].Figure 1
Simplified braking model and blocking time calculation.After the time for safe braking and the release time at each point are calculated, the blocking time and the headway along a train run can be derived. A typical blocking time model and headway are shown in Figure2, where several different types of blocking times are presented.(i)
E-F (running on a track): this is the most common form of the blocking time for moving block systems. If the train is running at a constant speed, the blocking time for the segment will be an occupation band parallel to the time-distance line.(ii)
A-B (at a movable element): for the blocking time at a movable element, e.g., a switch or a crossing, the movable element will be blocked and released as a whole to prevent unintended movement when a train is still occupying the movable element. Therefore, the blocking time on a movable element is not a band parallel to the time-distance line but is presented as a rectangle. The distance between two successive trains near a movable element therefore exceeds the safe braking distance.(iii)
C-D (approach to a stop): if a train approaches a stop, the blocking time for releasing the infrastructure is significantly higher since the train will be halted at the stop. The dwell time at the stop leads to the increased blocking time.(iv)
D-E (departure from a stop): before a train leaves a stop, a segment of the track in front of the stop of at least the length of the train should be reserved to ensure that the train can completely leave the stop. The occupied infrastructure will be released gradually, which is similar to the normal situation shown in parts E-F.Figure 2
An example of blocking time and headway.In Figure2, the headway along the train run is plotted in orange. As explained at the beginning of Section 3.1, the value of the headway at any point equals the blocking time at the point. From the calculated headway along each train run, the bottleneck of the line capacity and the minimum line headway can be determined.


### 3.2. The Bottleneck of the Line Capacity and the Minimum Line Headway

A simulation-based approach can be applied to identify the bottleneck. With the simulation results, the headway of all the points along each train run can be computed according to the blocking time model (see Section3.1). The position with the maximum value of headway is the bottleneck of the line capacity.An overview of the line headway for Hefei-Metro Line 1 is shown in Figure3. The bottleneck of the line headway is located at switch SW 2601, with the highest headway of 116.776 seconds. Much research concentrates on reducing line headway at the areas near stops since the dwell time will lead to a high value of blocking time and headway at the positions approaching stops (refer to Parts C-D in Figure 2). However, in this example, the headway at movable elements (switches and crossings) exhibits the maximum value. Based on the exact blocking time model, a movable element is applied and released as a whole. The end of the movable element will be reserved in advance, and the starting point of the movable element will be released until the whole movable element is released. Therefore, the total blocking time of a movable element is relatively higher than that of other positions. The high potential for bottlenecks at movable elements is one of the most important findings of this work.Figure 3
Overview of the headway in Hefei-metro line 1.The most common way to minimise line headway is to decrease the approaching velocity close to a bottleneck. With the decreased velocity, the required braking distance and braking time at the bottleneck will be reduced. An example to reduce the headway before bottleneck SW 2601 is illustrated in Figure4. The original velocity before the switch was 80 km/h. In the left part of Figure 4, the original blocking time diagram and the headway are shown. If the approaching velocity is decreased to 20 km/h before switched to SW 2601, the braking time and blocking time are reduced at the switch. With the decreased approaching velocity, the headway at the switch can be reduced from 116.776 seconds to 110.235 seconds. On the right side of Figure 4, the optimised headway (in green) and the original headway (in black) are compared.Figure 4
Headway minimisation through reducing velocity before the bottleneck.The side effects of decreasing the approaching velocity should be considered. As presented in Section3.1, the value of headway/blocking time is the sum of the braking time and the time for releasing infrastructure resources. Taking the example shown in Figure 1, the braking distance from point A to D and the braking time t1 will be reduced if the velocity at point A is decreased. However, the required release time (e.g., time t2 in Figure 1) will be increased due to the lowered velocity. Therefore, the optimal approaching velocity should be controlled to ensure that the reduced braking time exceeds the increased releasing time. In Figure 5, an example of the relation between headway and approaching velocity before bottleneck SW 2601 is presented. The speed is first reduced from 80 km/h to 50 km/h. The minimum headway is reached with an approaching velocity between 15 km/h and 50 km/h. If the velocity is further decreased, the headway increases due to the increased release time. To minimise line headway, an algorithm to determine the approaching velocity is developed (see Section 4).Figure 5
An example of the relation between headway and approaching velocity.


## 3.1. Headway Calculation and Blocking Time Model

The headway of a metro line is calculated by the difference between the first train and the following train. In a metro line, the train headway along the train run can be simplified as the blocking time at each point, as long as the same type of train is running along the same line with the same velocity profile. In this paper, this simplification is acceptable since only the line headway at peak hours is of interest.A simplified braking model and the method to calculate blocking time are illustrated in Figure1. The head of the train is located at position A. The blocking time at position A is the sum of the time for safe braking (t1) and the time for releasing the occupied infrastructure (t2). To calculate the time for safe braking, the distance for safe braking should be determined. The curve of the ATP (Automatic Train Protection) profile defines the velocity supervised by ATP systems. However, the braking distance calculated from the ATP profile is not sufficient for safe braking since the worst case should be fully considered. At point A, a special reaction time for train-borne ATP systems is needed. The train can still be accelerated before the propulsion of the train is disabled and emergency braking is initiated. After emergency braking is applied, the train will be braked at point D, which defines the limit of movement authority. The whole emergency brake curve covers the distance from A to D. In addition, the distance for position uncertainty from D to E should be included. The time t1 used for movement from A to E is therefore determined. To calculate the time required for releasing the occupied infrastructure, the time t2 is derived from A to C, which covers the length of the train and the position uncertainty from A to B. In this simplified diagram, the ATP overspeed allowance and the speed measurement error, as well as the time for communication, are ignored. A detailed illustration of the braking model is presented in [20].Figure 1
Simplified braking model and blocking time calculation.After the time for safe braking and the release time at each point are calculated, the blocking time and the headway along a train run can be derived. A typical blocking time model and headway are shown in Figure2, where several different types of blocking times are presented.(i)
E-F (running on a track): this is the most common form of the blocking time for moving block systems. If the train is running at a constant speed, the blocking time for the segment will be an occupation band parallel to the time-distance line.(ii)
A-B (at a movable element): for the blocking time at a movable element, e.g., a switch or a crossing, the movable element will be blocked and released as a whole to prevent unintended movement when a train is still occupying the movable element. Therefore, the blocking time on a movable element is not a band parallel to the time-distance line but is presented as a rectangle. The distance between two successive trains near a movable element therefore exceeds the safe braking distance.(iii)
C-D (approach to a stop): if a train approaches a stop, the blocking time for releasing the infrastructure is significantly higher since the train will be halted at the stop. The dwell time at the stop leads to the increased blocking time.(iv)
D-E (departure from a stop): before a train leaves a stop, a segment of the track in front of the stop of at least the length of the train should be reserved to ensure that the train can completely leave the stop. The occupied infrastructure will be released gradually, which is similar to the normal situation shown in parts E-F.Figure 2
An example of blocking time and headway.In Figure2, the headway along the train run is plotted in orange. As explained at the beginning of Section 3.1, the value of the headway at any point equals the blocking time at the point. From the calculated headway along each train run, the bottleneck of the line capacity and the minimum line headway can be determined.


## 3.2. The Bottleneck of the Line Capacity and the Minimum Line Headway

A simulation-based approach can be applied to identify the bottleneck. With the simulation results, the headway of all the points along each train run can be computed according to the blocking time model (see Section3.1). The position with the maximum value of headway is the bottleneck of the line capacity.An overview of the line headway for Hefei-Metro Line 1 is shown in Figure3. The bottleneck of the line headway is located at switch SW 2601, with the highest headway of 116.776 seconds. Much research concentrates on reducing line headway at the areas near stops since the dwell time will lead to a high value of blocking time and headway at the positions approaching stops (refer to Parts C-D in Figure 2). However, in this example, the headway at movable elements (switches and crossings) exhibits the maximum value. Based on the exact blocking time model, a movable element is applied and released as a whole. The end of the movable element will be reserved in advance, and the starting point of the movable element will be released until the whole movable element is released. Therefore, the total blocking time of a movable element is relatively higher than that of other positions. The high potential for bottlenecks at movable elements is one of the most important findings of this work.Figure 3
Overview of the headway in Hefei-metro line 1.The most common way to minimise line headway is to decrease the approaching velocity close to a bottleneck. With the decreased velocity, the required braking distance and braking time at the bottleneck will be reduced. An example to reduce the headway before bottleneck SW 2601 is illustrated in Figure4. The original velocity before the switch was 80 km/h. In the left part of Figure 4, the original blocking time diagram and the headway are shown. If the approaching velocity is decreased to 20 km/h before switched to SW 2601, the braking time and blocking time are reduced at the switch. With the decreased approaching velocity, the headway at the switch can be reduced from 116.776 seconds to 110.235 seconds. On the right side of Figure 4, the optimised headway (in green) and the original headway (in black) are compared.Figure 4
Headway minimisation through reducing velocity before the bottleneck.The side effects of decreasing the approaching velocity should be considered. As presented in Section3.1, the value of headway/blocking time is the sum of the braking time and the time for releasing infrastructure resources. Taking the example shown in Figure 1, the braking distance from point A to D and the braking time t1 will be reduced if the velocity at point A is decreased. However, the required release time (e.g., time t2 in Figure 1) will be increased due to the lowered velocity. Therefore, the optimal approaching velocity should be controlled to ensure that the reduced braking time exceeds the increased releasing time. In Figure 5, an example of the relation between headway and approaching velocity before bottleneck SW 2601 is presented. The speed is first reduced from 80 km/h to 50 km/h. The minimum headway is reached with an approaching velocity between 15 km/h and 50 km/h. If the velocity is further decreased, the headway increases due to the increased release time. To minimise line headway, an algorithm to determine the approaching velocity is developed (see Section 4).Figure 5
An example of the relation between headway and approaching velocity.


## 4. Headway Optimisation Through Decreasing the Approaching Velocity Before Bottlenecks

As analysed in Section3.2, the headway can be reduced by decreasing the approaching velocity close to a bottleneck. To minimise the line headway, the following questions should be answered:(i)
At which places should the approaching velocity be decreased? How can the general workflow be designed to minimise line headway?(ii)
How can the exact profile of reduced velocity be determined before the identified bottlenecks?The first question will be solved in Section4.1, in which a workflow to minimise line headway and identify the current bottleneck is presented. The optimisation approaches used to determine the exact velocity profile will be investigated in Section 4.2.


### 4.1. General Workflow to Minimise Line Headway

There are many possible ways to implement an optimised driving style. For example, the velocity of trains can be controlled and adjusted online by real-time operations or simulation processes. This approach is typically used for online dispatching and energy-efficient driving [21, 22]. For long-term or middle-term planning, it is also possible to optimise the velocity profile by gradually reducing the limits of the velocity profile. In this work, exemplary velocity limits, which are lower than the original velocity limits, are applied to the simulation tool to check the effectiveness of reducing the approach velocity before a bottleneck. With this approach, the velocity of the train can be controlled via the infrastructure-related attribute. This is easy to implement in a simulation environment. From the simulated results with the minimum line headway, the optimised velocity profile can be derived from the exemplary velocity limits.Although the headway of a certain potential bottleneck, e.g., at a movable element or at a stop, can be reduced by decreasing the approaching velocity, it is not worth minimising the velocity. The reduced approaching velocity will increase the total transport time and therefore decrease the system performance. The energy consumption and wear/tear costs will be increased due to the additional braking and acceleration. Moreover, there are several potential bottlenecks in one line. If the headway at a bottleneck in a metro line is reduced to a certain value, the bottleneck could be changed to a new place with the highest value of headway on the line. In this situation, it is not necessary to further reduce the headway at the previous bottleneck since the new bottleneck determines the minimal line headway.In Figure6, the general workflow to optimise line headway is presented with the following steps:(1)
The current bottleneckB is identified through a simulation-based approach (see Section 3.2), and the line headway h for bottleneck B is evaluated.(2)
The current line headwayh is used to initialise a variable h_min to record the minimised headway during the optimisation process.(3)
According to the applied algorithm (see Section4.2), a new neighbour solution in the form of a tuple s,v is searched in the solution space. The distance s and the velocity v specify the limits of velocity before the bottleneck B.(4)
If the resulting conveyance time of the solution exceeds the predefined threshold of the acceptable conveyance time for the train run, the solution will be treated as infeasible. This procedure will be repeated again from (step 3) until a new feasible solution is found.(5)
The new bottleneckB′ and the headway h′ will be derived from the simulation result for the new solution s,v (see Section 3.2).(6)
If the new headwayh′ is less than the current headway h_min, h_min will be updated with h′.(7)
The new bottleneckB′ will be compared with the current bottleneck B: if B′ and B are different, it is no longer necessary to optimise the headway for B since the bottleneck B′ becomes more critical than B. The current bottleneck B to be optimised will be updated as B′; (proceed to step 9).(8)
IfB′ and B are the same, if the maximum number of iterations has not been reached, the procedure will be repeated from step 3; (otherwise, proceed to step 9).(9)
If there is no further decrease in the minimum headway, the optimisation process will be finished. Otherwise, the recorded headwayh_min is less than h. The current headway h will be updated with h_min, and the procedure will be repeated again from step 2.Figure 6
General workflow to minimise line headway.The termination condition is checked in step 9. If there is no further decrease in the minimum headway after step 8, the optimisation process is terminated.


### 4.2. Methods to Determine Optimal Approaching Velocity Before Bottlenecks

#### 4.2.1. Intuitive Approaches: Grid Search and Monte Carlo Methods

During the process of minimising line headway, an optimised velocity profile will be derived for the current bottleneckB to be optimised. The optimised velocity profile is defined by the distance s and the velocity v before the bottleneck B, which are determined in the minimum to maximum range of the distances and the velocities, respectively. The optimal solution s,v will be continuously searched and evaluated in the solution space to reach a minimum headway with less computational effort.Several methods are available to find the optimal approaching velocity before bottlenecks. In this paper, the “naive” methods of grid search and Monte Carlo are applied first to observe the change in the headway as the approaching velocity varies at different locations.The grid search method is the most intuitive approach in finding a globally optimised solution. The solution space is constructed by all the combinations of the distance and the velocity, which are divided evenly in the minimum-maximum range. Given the number of distancesm and the number of velocities n, there are in total m×n solutions to be evaluated. For each solution, the headway and the bottleneck will be derived through the simulation results (see Section 3.2). After comparing all the solutions, the minimal headway is recorded in h_min (see Section 4.1). The case study of using grid search is demonstrated in Section 5. It is worth evaluating the most intuitive method first to learn the possible distribution of the solutions and the deficiencies of the method.Due to the coarseness of the grid search, good solutions may be neglected in the evenly distributed solution space. In this paper, the Monte Carlo method is used to implement random searching for function optimisation. The value of the distance and the velocity are sampled randomly within the minimum to maximum range. From the simulation results, the optimal solution with the minimal headway is derived from the randomly generated solutions.For a high-dimensional solution space, the computational complexity of the grid search method will be very high. The Monte Carlo method can be applied to control the computational efforts at an acceptable level. Although this advantage cannot be fully utilised for two-dimensional solution space in this work, it is worth using the Monte Carlo method for sampling approaching velocity and location independently. The results of the Monte Carlo simulation can serve as a reference for empirical comparison with other approaches.The results presented in Section5 show that the performances of the naive search methods, including grid search and Monte Carlo, are not satisfactory due to the extensive computational efforts. It is necessary to use a more efficient approach for headway optimisation. The gradient descent method is well known for finding an optimal solution for a convex function. However, the evaluated results from the grid search show that there are many local minima in the solution space. For instance, the line headway of different solutions before switch SW 2601 is presented in Figure 7. A local minimum of headway, e.g., located in the region 50 km/h < v < 60 km/h and 600 m < s < 1,200 m with a line headway of 112.558 seconds, exceeds the global minimum headway of 110.235 seconds.Figure 7
Line headway with reduced velocity before switch SW 2601 in Hefei-metro line 1.Therefore, a global optimisation algorithm based on simulated annealing is developed in this work to minimise the line headway at a bottleneck with reduced computational effort.


#### 4.2.2. Simulated Annealing

Simulated annealing is a metaheuristic algorithm to approximate global optimisation. In addition to simulated annealing, genetic algorithms and tabu search are also very popular metaheuristic methods. Simulated annealing has the advantages of a simpler principle, fewer parameters, and easier implementation. Compared with the genetic algorithm, the simulated annealing algorithm does not require coding, and there are no “crossover” and “mutation” operations in this algorithm. In this work, tabu search is not suitable for solving the line headway optimisation problem. With the tabu search algorithm, a tabu list should be maintained. As shown in Figure7, a flat area is often near a solution. A tabu list that is too small will lead to a circular search, and a tabu list that is too large will prevent finding a new solution. It is difficult to determine the suitable size of the tabu list and the neighbourhood space.The principle of the simulated annealing algorithm is inspired by the process of metal annealing. Molecules in a metal material will originally remain in the position for which the internal energy has a local minimum. The heating process will force molecules to move randomly and to leave their original positions by increasing their energy. The annealing process cools the material slowly to enable the molecules to find a new position with a lower internal energy than before so that an optimal molecular arrangement is reached.The algorithm of simulated annealing adopts a similar process. Starting from the current solution (s, v), a new solution (s′, v′) is searched in the solution space. The new solution is a random neighbour of the current solution, which is derived as follows:(1)s′=maxmins+a·X∼N0,1smaxsmin,(2)v′=maxminv+b·X∼N0,1vmaxvmin.The current distances [m] and velocity v [km/h] are added to a random variable that follows a Gaussian distribution. The ranges of the values [smin,smax] and [vmin,vmax] are used to prevent the generation of an invalid solution. The parameters a and b are used to control the searching space of the neighbour. The parameter study for different a and b values is presented in Table 1, by which the values for a and b are examined within the range from 1 to 1,000 metres and 1–20 km/h, respectively. The results show that values between a and b that are too small will limit the search space of the neighbour. In this work, the setting with a=10m and b=5km/h is applied since it results in the lowest value of headway compared to other settings.Table 1
Parameter study for controlling the neighbour range.
a (m)Rounds of simulationMin. headway (s)b (km/h)Rounds of simulationMin. headway (s)1107106.264164106.58110126105.8065126105.80610070105.88410170105.963100059106.13920159105.808The current solution and the new solution are evaluated from the resulting line headwaysh and h′, respectively (see Sections 3.1 and 3.2). If the new solution is better than the current solution, the new solution will be accepted; otherwise, the new solution will be accepted or rejected according to a certain probability. The acceptance probability of worse solutions decreases over time until the system converges to a stable state or reaches the maximum number of iterations. The process with a high acceptance probability at the beginning can be referred to as the heating process, which encourages the system to escape a local minimum and to find a good region of solutions. As the acceptance probability of worse solutions continuously decreases, the search is forced on converge to a minimum. This can be perceived as the annealing process. The material is slowly cooled with a low internal energy in an ordered state. Hence, the system approximates a global optimisation. The activity diagram of minimising line headway with simulated annealing is shown in Figure 8.Figure 8
Determination of velocity profile based on simulated annealing method.In this work, the metropolis acceptance criterion is used to calculate the acceptance probability.(3)P=1,h′<he−h′−h/Tt,h′≥h.The following notation is used:P [-] The acceptance probabilityh [s] The line headway of the current solution (s, v)h′ [s] The line headway of the new solution (s′, v′)Tt [-] The temperature parameter to control the speed of annealing at iteration t, calculated by Tt=T0/t+1. T0 is the initial temperature defined by the user.The pseudocode of the simulated annealing algorithm is presented in Figure9. The acceptance probability P is calculated in row 10. A randomly generated number between 0 and 1 will be compared to P. If the random number is less than P, a new solution will be accepted even if it is not better than the current solution. Hence, the search will not be limited to local optima. As the iteration continues, this probability value will decrease until the search reaches the globally optimal solution.Figure 9
Pseudocode is used to determine the velocity profile to minimise line headway.The initial temperatureT0 controls the level of randomness in the process. A low initial temperature will result in a low acceptance probability for worse solutions, which may lead to a local optimum. In Table 2, the results for different initial temperatures are compared. If the initial temperature is set at 10, it will be stuck in a local optimum with convergence that is too fast. After the temperature is set at 100 or higher, the process will reach the global optimum. In this work, the temperature is set at 1,000 to ensure a good balance between fast convergence and the global optimum.Table 2
Comparison of initial temperature.
Temperature [-]Rounds of simulationMin. headway (s)1087107.203100181105.8471,000126105.80610,000142105.955In this work, parameter tuning fora, b, and T0 is carried out in an iterative process. To avoid local optima, different settings of the parameter T0 were first investigated (see Table 2). After T0 was chosen as 1,000, the parameter study for parameters a and b was performed (see Table 1). With the tuned parameters a and b, the different settings of the initial temperature were checked again to ensure that the current value of T0 still provides the best performance.


## 4.1. General Workflow to Minimise Line Headway

There are many possible ways to implement an optimised driving style. For example, the velocity of trains can be controlled and adjusted online by real-time operations or simulation processes. This approach is typically used for online dispatching and energy-efficient driving [21, 22]. For long-term or middle-term planning, it is also possible to optimise the velocity profile by gradually reducing the limits of the velocity profile. In this work, exemplary velocity limits, which are lower than the original velocity limits, are applied to the simulation tool to check the effectiveness of reducing the approach velocity before a bottleneck. With this approach, the velocity of the train can be controlled via the infrastructure-related attribute. This is easy to implement in a simulation environment. From the simulated results with the minimum line headway, the optimised velocity profile can be derived from the exemplary velocity limits.Although the headway of a certain potential bottleneck, e.g., at a movable element or at a stop, can be reduced by decreasing the approaching velocity, it is not worth minimising the velocity. The reduced approaching velocity will increase the total transport time and therefore decrease the system performance. The energy consumption and wear/tear costs will be increased due to the additional braking and acceleration. Moreover, there are several potential bottlenecks in one line. If the headway at a bottleneck in a metro line is reduced to a certain value, the bottleneck could be changed to a new place with the highest value of headway on the line. In this situation, it is not necessary to further reduce the headway at the previous bottleneck since the new bottleneck determines the minimal line headway.In Figure6, the general workflow to optimise line headway is presented with the following steps:(1)
The current bottleneckB is identified through a simulation-based approach (see Section 3.2), and the line headway h for bottleneck B is evaluated.(2)
The current line headwayh is used to initialise a variable h_min to record the minimised headway during the optimisation process.(3)
According to the applied algorithm (see Section4.2), a new neighbour solution in the form of a tuple s,v is searched in the solution space. The distance s and the velocity v specify the limits of velocity before the bottleneck B.(4)
If the resulting conveyance time of the solution exceeds the predefined threshold of the acceptable conveyance time for the train run, the solution will be treated as infeasible. This procedure will be repeated again from (step 3) until a new feasible solution is found.(5)
The new bottleneckB′ and the headway h′ will be derived from the simulation result for the new solution s,v (see Section 3.2).(6)
If the new headwayh′ is less than the current headway h_min, h_min will be updated with h′.(7)
The new bottleneckB′ will be compared with the current bottleneck B: if B′ and B are different, it is no longer necessary to optimise the headway for B since the bottleneck B′ becomes more critical than B. The current bottleneck B to be optimised will be updated as B′; (proceed to step 9).(8)
IfB′ and B are the same, if the maximum number of iterations has not been reached, the procedure will be repeated from step 3; (otherwise, proceed to step 9).(9)
If there is no further decrease in the minimum headway, the optimisation process will be finished. Otherwise, the recorded headwayh_min is less than h. The current headway h will be updated with h_min, and the procedure will be repeated again from step 2.Figure 6
General workflow to minimise line headway.The termination condition is checked in step 9. If there is no further decrease in the minimum headway after step 8, the optimisation process is terminated.


## 4.2. Methods to Determine Optimal Approaching Velocity Before Bottlenecks

### 4.2.1. Intuitive Approaches: Grid Search and Monte Carlo Methods

During the process of minimising line headway, an optimised velocity profile will be derived for the current bottleneckB to be optimised. The optimised velocity profile is defined by the distance s and the velocity v before the bottleneck B, which are determined in the minimum to maximum range of the distances and the velocities, respectively. The optimal solution s,v will be continuously searched and evaluated in the solution space to reach a minimum headway with less computational effort.Several methods are available to find the optimal approaching velocity before bottlenecks. In this paper, the “naive” methods of grid search and Monte Carlo are applied first to observe the change in the headway as the approaching velocity varies at different locations.The grid search method is the most intuitive approach in finding a globally optimised solution. The solution space is constructed by all the combinations of the distance and the velocity, which are divided evenly in the minimum-maximum range. Given the number of distancesm and the number of velocities n, there are in total m×n solutions to be evaluated. For each solution, the headway and the bottleneck will be derived through the simulation results (see Section 3.2). After comparing all the solutions, the minimal headway is recorded in h_min (see Section 4.1). The case study of using grid search is demonstrated in Section 5. It is worth evaluating the most intuitive method first to learn the possible distribution of the solutions and the deficiencies of the method.Due to the coarseness of the grid search, good solutions may be neglected in the evenly distributed solution space. In this paper, the Monte Carlo method is used to implement random searching for function optimisation. The value of the distance and the velocity are sampled randomly within the minimum to maximum range. From the simulation results, the optimal solution with the minimal headway is derived from the randomly generated solutions.For a high-dimensional solution space, the computational complexity of the grid search method will be very high. The Monte Carlo method can be applied to control the computational efforts at an acceptable level. Although this advantage cannot be fully utilised for two-dimensional solution space in this work, it is worth using the Monte Carlo method for sampling approaching velocity and location independently. The results of the Monte Carlo simulation can serve as a reference for empirical comparison with other approaches.The results presented in Section5 show that the performances of the naive search methods, including grid search and Monte Carlo, are not satisfactory due to the extensive computational efforts. It is necessary to use a more efficient approach for headway optimisation. The gradient descent method is well known for finding an optimal solution for a convex function. However, the evaluated results from the grid search show that there are many local minima in the solution space. For instance, the line headway of different solutions before switch SW 2601 is presented in Figure 7. A local minimum of headway, e.g., located in the region 50 km/h < v < 60 km/h and 600 m < s < 1,200 m with a line headway of 112.558 seconds, exceeds the global minimum headway of 110.235 seconds.Figure 7
Line headway with reduced velocity before switch SW 2601 in Hefei-metro line 1.Therefore, a global optimisation algorithm based on simulated annealing is developed in this work to minimise the line headway at a bottleneck with reduced computational effort.


### 4.2.2. Simulated Annealing

Simulated annealing is a metaheuristic algorithm to approximate global optimisation. In addition to simulated annealing, genetic algorithms and tabu search are also very popular metaheuristic methods. Simulated annealing has the advantages of a simpler principle, fewer parameters, and easier implementation. Compared with the genetic algorithm, the simulated annealing algorithm does not require coding, and there are no “crossover” and “mutation” operations in this algorithm. In this work, tabu search is not suitable for solving the line headway optimisation problem. With the tabu search algorithm, a tabu list should be maintained. As shown in Figure7, a flat area is often near a solution. A tabu list that is too small will lead to a circular search, and a tabu list that is too large will prevent finding a new solution. It is difficult to determine the suitable size of the tabu list and the neighbourhood space.The principle of the simulated annealing algorithm is inspired by the process of metal annealing. Molecules in a metal material will originally remain in the position for which the internal energy has a local minimum. The heating process will force molecules to move randomly and to leave their original positions by increasing their energy. The annealing process cools the material slowly to enable the molecules to find a new position with a lower internal energy than before so that an optimal molecular arrangement is reached.The algorithm of simulated annealing adopts a similar process. Starting from the current solution (s, v), a new solution (s′, v′) is searched in the solution space. The new solution is a random neighbour of the current solution, which is derived as follows:(1)s′=maxmins+a·X∼N0,1smaxsmin,(2)v′=maxminv+b·X∼N0,1vmaxvmin.The current distances [m] and velocity v [km/h] are added to a random variable that follows a Gaussian distribution. The ranges of the values [smin,smax] and [vmin,vmax] are used to prevent the generation of an invalid solution. The parameters a and b are used to control the searching space of the neighbour. The parameter study for different a and b values is presented in Table 1, by which the values for a and b are examined within the range from 1 to 1,000 metres and 1–20 km/h, respectively. The results show that values between a and b that are too small will limit the search space of the neighbour. In this work, the setting with a=10m and b=5km/h is applied since it results in the lowest value of headway compared to other settings.Table 1
Parameter study for controlling the neighbour range.
a (m)Rounds of simulationMin. headway (s)b (km/h)Rounds of simulationMin. headway (s)1107106.264164106.58110126105.8065126105.80610070105.88410170105.963100059106.13920159105.808The current solution and the new solution are evaluated from the resulting line headwaysh and h′, respectively (see Sections 3.1 and 3.2). If the new solution is better than the current solution, the new solution will be accepted; otherwise, the new solution will be accepted or rejected according to a certain probability. The acceptance probability of worse solutions decreases over time until the system converges to a stable state or reaches the maximum number of iterations. The process with a high acceptance probability at the beginning can be referred to as the heating process, which encourages the system to escape a local minimum and to find a good region of solutions. As the acceptance probability of worse solutions continuously decreases, the search is forced on converge to a minimum. This can be perceived as the annealing process. The material is slowly cooled with a low internal energy in an ordered state. Hence, the system approximates a global optimisation. The activity diagram of minimising line headway with simulated annealing is shown in Figure 8.Figure 8
Determination of velocity profile based on simulated annealing method.In this work, the metropolis acceptance criterion is used to calculate the acceptance probability.(3)P=1,h′<he−h′−h/Tt,h′≥h.The following notation is used:P [-] The acceptance probabilityh [s] The line headway of the current solution (s, v)h′ [s] The line headway of the new solution (s′, v′)Tt [-] The temperature parameter to control the speed of annealing at iteration t, calculated by Tt=T0/t+1. T0 is the initial temperature defined by the user.The pseudocode of the simulated annealing algorithm is presented in Figure9. The acceptance probability P is calculated in row 10. A randomly generated number between 0 and 1 will be compared to P. If the random number is less than P, a new solution will be accepted even if it is not better than the current solution. Hence, the search will not be limited to local optima. As the iteration continues, this probability value will decrease until the search reaches the globally optimal solution.Figure 9
Pseudocode is used to determine the velocity profile to minimise line headway.The initial temperatureT0 controls the level of randomness in the process. A low initial temperature will result in a low acceptance probability for worse solutions, which may lead to a local optimum. In Table 2, the results for different initial temperatures are compared. If the initial temperature is set at 10, it will be stuck in a local optimum with convergence that is too fast. After the temperature is set at 100 or higher, the process will reach the global optimum. In this work, the temperature is set at 1,000 to ensure a good balance between fast convergence and the global optimum.Table 2
Comparison of initial temperature.
Temperature [-]Rounds of simulationMin. headway (s)1087107.203100181105.8471,000126105.80610,000142105.955In this work, parameter tuning fora, b, and T0 is carried out in an iterative process. To avoid local optima, different settings of the parameter T0 were first investigated (see Table 2). After T0 was chosen as 1,000, the parameter study for parameters a and b was performed (see Table 1). With the tuned parameters a and b, the different settings of the initial temperature were checked again to ensure that the current value of T0 still provides the best performance.


## 4.2.1. Intuitive Approaches: Grid Search and Monte Carlo Methods

During the process of minimising line headway, an optimised velocity profile will be derived for the current bottleneckB to be optimised. The optimised velocity profile is defined by the distance s and the velocity v before the bottleneck B, which are determined in the minimum to maximum range of the distances and the velocities, respectively. The optimal solution s,v will be continuously searched and evaluated in the solution space to reach a minimum headway with less computational effort.Several methods are available to find the optimal approaching velocity before bottlenecks. In this paper, the “naive” methods of grid search and Monte Carlo are applied first to observe the change in the headway as the approaching velocity varies at different locations.The grid search method is the most intuitive approach in finding a globally optimised solution. The solution space is constructed by all the combinations of the distance and the velocity, which are divided evenly in the minimum-maximum range. Given the number of distancesm and the number of velocities n, there are in total m×n solutions to be evaluated. For each solution, the headway and the bottleneck will be derived through the simulation results (see Section 3.2). After comparing all the solutions, the minimal headway is recorded in h_min (see Section 4.1). The case study of using grid search is demonstrated in Section 5. It is worth evaluating the most intuitive method first to learn the possible distribution of the solutions and the deficiencies of the method.Due to the coarseness of the grid search, good solutions may be neglected in the evenly distributed solution space. In this paper, the Monte Carlo method is used to implement random searching for function optimisation. The value of the distance and the velocity are sampled randomly within the minimum to maximum range. From the simulation results, the optimal solution with the minimal headway is derived from the randomly generated solutions.For a high-dimensional solution space, the computational complexity of the grid search method will be very high. The Monte Carlo method can be applied to control the computational efforts at an acceptable level. Although this advantage cannot be fully utilised for two-dimensional solution space in this work, it is worth using the Monte Carlo method for sampling approaching velocity and location independently. The results of the Monte Carlo simulation can serve as a reference for empirical comparison with other approaches.The results presented in Section5 show that the performances of the naive search methods, including grid search and Monte Carlo, are not satisfactory due to the extensive computational efforts. It is necessary to use a more efficient approach for headway optimisation. The gradient descent method is well known for finding an optimal solution for a convex function. However, the evaluated results from the grid search show that there are many local minima in the solution space. For instance, the line headway of different solutions before switch SW 2601 is presented in Figure 7. A local minimum of headway, e.g., located in the region 50 km/h < v < 60 km/h and 600 m < s < 1,200 m with a line headway of 112.558 seconds, exceeds the global minimum headway of 110.235 seconds.Figure 7
Line headway with reduced velocity before switch SW 2601 in Hefei-metro line 1.Therefore, a global optimisation algorithm based on simulated annealing is developed in this work to minimise the line headway at a bottleneck with reduced computational effort.


## 4.2.2. Simulated Annealing

Simulated annealing is a metaheuristic algorithm to approximate global optimisation. In addition to simulated annealing, genetic algorithms and tabu search are also very popular metaheuristic methods. Simulated annealing has the advantages of a simpler principle, fewer parameters, and easier implementation. Compared with the genetic algorithm, the simulated annealing algorithm does not require coding, and there are no “crossover” and “mutation” operations in this algorithm. In this work, tabu search is not suitable for solving the line headway optimisation problem. With the tabu search algorithm, a tabu list should be maintained. As shown in Figure7, a flat area is often near a solution. A tabu list that is too small will lead to a circular search, and a tabu list that is too large will prevent finding a new solution. It is difficult to determine the suitable size of the tabu list and the neighbourhood space.The principle of the simulated annealing algorithm is inspired by the process of metal annealing. Molecules in a metal material will originally remain in the position for which the internal energy has a local minimum. The heating process will force molecules to move randomly and to leave their original positions by increasing their energy. The annealing process cools the material slowly to enable the molecules to find a new position with a lower internal energy than before so that an optimal molecular arrangement is reached.The algorithm of simulated annealing adopts a similar process. Starting from the current solution (s, v), a new solution (s′, v′) is searched in the solution space. The new solution is a random neighbour of the current solution, which is derived as follows:(1)s′=maxmins+a·X∼N0,1smaxsmin,(2)v′=maxminv+b·X∼N0,1vmaxvmin.The current distances [m] and velocity v [km/h] are added to a random variable that follows a Gaussian distribution. The ranges of the values [smin,smax] and [vmin,vmax] are used to prevent the generation of an invalid solution. The parameters a and b are used to control the searching space of the neighbour. The parameter study for different a and b values is presented in Table 1, by which the values for a and b are examined within the range from 1 to 1,000 metres and 1–20 km/h, respectively. The results show that values between a and b that are too small will limit the search space of the neighbour. In this work, the setting with a=10m and b=5km/h is applied since it results in the lowest value of headway compared to other settings.Table 1
Parameter study for controlling the neighbour range.
a (m)Rounds of simulationMin. headway (s)b (km/h)Rounds of simulationMin. headway (s)1107106.264164106.58110126105.8065126105.80610070105.88410170105.963100059106.13920159105.808The current solution and the new solution are evaluated from the resulting line headwaysh and h′, respectively (see Sections 3.1 and 3.2). If the new solution is better than the current solution, the new solution will be accepted; otherwise, the new solution will be accepted or rejected according to a certain probability. The acceptance probability of worse solutions decreases over time until the system converges to a stable state or reaches the maximum number of iterations. The process with a high acceptance probability at the beginning can be referred to as the heating process, which encourages the system to escape a local minimum and to find a good region of solutions. As the acceptance probability of worse solutions continuously decreases, the search is forced on converge to a minimum. This can be perceived as the annealing process. The material is slowly cooled with a low internal energy in an ordered state. Hence, the system approximates a global optimisation. The activity diagram of minimising line headway with simulated annealing is shown in Figure 8.Figure 8
Determination of velocity profile based on simulated annealing method.In this work, the metropolis acceptance criterion is used to calculate the acceptance probability.(3)P=1,h′<he−h′−h/Tt,h′≥h.The following notation is used:P [-] The acceptance probabilityh [s] The line headway of the current solution (s, v)h′ [s] The line headway of the new solution (s′, v′)Tt [-] The temperature parameter to control the speed of annealing at iteration t, calculated by Tt=T0/t+1. T0 is the initial temperature defined by the user.The pseudocode of the simulated annealing algorithm is presented in Figure9. The acceptance probability P is calculated in row 10. A randomly generated number between 0 and 1 will be compared to P. If the random number is less than P, a new solution will be accepted even if it is not better than the current solution. Hence, the search will not be limited to local optima. As the iteration continues, this probability value will decrease until the search reaches the globally optimal solution.Figure 9
Pseudocode is used to determine the velocity profile to minimise line headway.The initial temperatureT0 controls the level of randomness in the process. A low initial temperature will result in a low acceptance probability for worse solutions, which may lead to a local optimum. In Table 2, the results for different initial temperatures are compared. If the initial temperature is set at 10, it will be stuck in a local optimum with convergence that is too fast. After the temperature is set at 100 or higher, the process will reach the global optimum. In this work, the temperature is set at 1,000 to ensure a good balance between fast convergence and the global optimum.Table 2
Comparison of initial temperature.
Temperature [-]Rounds of simulationMin. headway (s)1087107.203100181105.8471,000126105.80610,000142105.955In this work, parameter tuning fora, b, and T0 is carried out in an iterative process. To avoid local optima, different settings of the parameter T0 were first investigated (see Table 2). After T0 was chosen as 1,000, the parameter study for parameters a and b was performed (see Table 1). With the tuned parameters a and b, the different settings of the initial temperature were checked again to ensure that the current value of T0 still provides the best performance.


## 5. Case Study in Hefei-Metro Line 1

The algorithm of optimising line headway was applied in Hefei-Metro Line 1, with 23 stations and 24.34 kilometres in length. Given the original timetable, the minimum line headway is 116.776 seconds, located at switch SW 2601 (see Figures3 and 4). In the simulation software PULSim [23], the workflow of minimising line headway (see Section 4.1) and the three different optimisation approaches (see Section 4.2) are implemented in Java.The performances of grid search, Monte Carlo, and simulated annealing are compared in Figure10.Figure 10
Performance comparison between grid search, Monte Carlo, and simulated annealing.With regard to the minimised line headway and the required rounds of simulations, the simulated annealing method shows the best performance. Through grid search, the minimum line headway is 105.998 seconds, derived from 18,874 rounds of simulation. It takes 13,705 rounds of simulation with the Monte Carlo method to reach a minimised line headway of 105.829 seconds. The grid search and Monte Carlo methods require substantial computational efforts, although they can minimise the line headway to the same level as simulated annealing. In this work, the solution space is only two-dimensional. The advantage of the Monte Carlo method for solving high-dimensional problems cannot be fully utilised. As introduced in Section4.2.2, the simulated annealing method can efficiently converge to the global minima without being stuck in a local optimum. With this method, the line headway is minimised to 105.806 seconds through 126 rounds of simulation.In Figure11, an overview of the velocity profile and the optimised headway along Hefei-Metro Line 1 is shown. Compared with the original velocity profile (Figure 12), the velocity is reduced before the identified bottlenecks, which are located either before a switch or a stop. Accordingly, the headway at the bottleneck is reduced gradually. The difference in the headway is compared with different colours. The original headway is marked with a dashed black line, and the headway after optimisation is marked with a dashed green line. As explained in Section 4.1, exemplary velocity limits before bottlenecks are introduced to check the effects of reducing the approach velocity. Therefore, the velocity limits in Figure 11 are lower than the original velocity limits shown in Figure 12.Figure 11
Velocity profile and headway after optimisation with simulated annealing for Hefei-metro line 1.Figure 12
Original velocity profile without optimisation for Hefei-metro line 1.In this example, the line headway is reduced from 116.776 seconds to 105.806 seconds. Due to the reduced velocity, the transport time of a train run is increased from 2,541 seconds to 2,732 seconds. For this case study with the simulated annealing method, the relationship between the reduced headway and the increased transport time is shown in Figure13. If the acceptable transport time is set at 2,565 seconds, increased by 1.0%, the headway is reduced to 109.663 seconds. Without considering the buffer time, the line capacity is increased by 6.5%.Figure 13
Relationship between the minimum line headway and transport time.


## 6. Conclusion and Further Research

In this work, the theoretical considerations for building a blocking time model and calculating line headway for moving block systems are investigated. Based on the theory and simulation approaches, the bottleneck in the line capacity will be identified by calculating the minimum line headway. A workflow to minimise line headway is designed to derive an optimised velocity profile before the identified bottlenecks. Several different optimisation algorithms, including grid search, Monte Carlo, and simulated annealing, are developed and compared. Among them, simulated annealing shows the best optimisation capability with the least computational effort. The designed algorithm has been tested for Hefei-Metro Line 1, and the line headway can be reduced from 116.776 seconds to 105.806 seconds. If the acceptable rate of the increased transport is set at 1%, the line capacity will increase by 6.5%. Through parameter tuning and experiments with grid search and Monte Carlo methods, it can be proven that the simulated annealing method can reach a global optimum with stable performance.The developed method can be used not only to optimise line capacity for metro lines but also to evaluate the performance of moving block systems for railway main lines. This is especially important when the signalling system of main lines is planned to be upgraded from a fixed block to a moving block (e.g., ETCS level 3 or CTCS level 4). Although the capacity is expected to be improved on tracks with moving block systems, the possible limits of line capacity at stops and movable elements (switches and crossings) have not been comprehensively investigated. Supported by simulation approaches, the impacts of the bottlenecks can be identified and studied, and the potential benefits of moving block systems will be evaluated during the planning phase.In this work, the improvement in line capacity through decreasing dwell time at stops has not been evaluated. In future studies, this would provide great potential after the application of automatic train operation. Simulated annealing shows great performance in headway optimisation. The computational efficiency can be further improved, e.g., by setting a suitable convergence rate [24]. In this work, a fixed acceptable rate for the increased transport time is set to solve the conflict between improving capacity and reducing transport time. It is worth finding an optimal solution to solve the conflict through further research. Finally, a unified optimisation algorithm will enable us to build a comprehensive framework for both long-term planning and short-term dispatching, in which various aspects, including line capacity, energy savings, punctuality, and the robustness of timetables, can be fully integrated.



---

*Source: 7035214-2022-12-12.xml*