# Analysis of Urban Rail Transit Station Planning Combining Simulated Annealing Algorithm

Authors: Kailing Dong
Journal: Discrete Dynamics in Nature and Society
 (2022)

---

## Abstract

As a crucial node in the network system of urban transportation infrastructure, the consistent planning of the urban rail transit stations scientifically and reasonably is of highly significant importance to have a thorough understanding of the functional area division of a city and assess the improvement of facilities correlated with the rail transit infrastructure. In this study, the simulated annealing algorithm (SAA) is applied to the data analysis of the rail transit stations in a city. The method for the analysis of the urban rail transit stations combined with the SAA can achieve the dimensionality reduction in high-dimensional data information and the assessment of the similarity in traffic rail transits effectively. Finally, through in-depth analysis of the daily passenger flow features and the spatial location distribution of each type of station, a valuable reference can be obtained for the planning and design of urban rail transit stations.


---

## Body

## 1. Introduction

Rail transit stations are the critical nodes of the most fundamental road transportation network systems in urban rail transit. With the full extension of many urban rail transits in China, rail transit has gradually occupied an increasingly significant position in urban transportation. Scientific and reasonable planning of rail connection stations is of highly significant importance to have a thorough understanding of the division of the functional areas in a city, know the travel habits of urban residents, master the urban spatial pattern and evolution process, and evaluate the urban rail transit infrastructure effectively. From the perspective of the features of urban rail lines, the tough problem of unbalanced passenger flow between urban areas can be resolved effectively through the application of urban rail transit station planning, and the quality of passenger services can be guaranteed as well. The studies on urban rail transit station planning and optimization station to save the travel time of passengers effectively are of vital significance [1–3]. According to the case analysis of website planning, the operation mode of the train is formulated according to the operation conditions and driving route of the train [4]. On the premise of the shortest time required for direct passenger travel, the optimization model of train operation plan is studied [5]. Under the condition that the train schedule is unchanged, taking full consideration of several constraints such as the topological structure of the road network, a parking method combining fast and slow trains is proposed [6]. In the urban rail transit station planning mode, based on the detailed analysis of passenger travel costs, a bi-objective hybrid nonlinear programming model is built [7] .As an important part of national road infrastructure, the urban rail transit network plays an important role and value in promoting people to travel and convenient travel. On the other hand, as the artery of urban development, the planning and construction of urban rail transit network must be comprehensively considered in combination with the scale of the city, the distribution of functional areas, and the actual travel needs of residents. Therefore, in the process of planning and construction, the characteristics of urban rail transit lines must be comprehensively considered and analyzed to avoid the imbalance of passenger flow temporal and spatial distribution, average ride distance, and other indicators. Based on the characteristics of urban rail transit lines, realizing the linkage of multiple transportation modes and constructing a reasonable line stop scheme and operation frequency will help to maximize the social and economic benefits of urban rail transit lines.Scientific and reasonable urban rail transit station planning is inseparable from the effective prediction of passenger flow, as well as the research support of urban public transport station spacing and urban rail transit station location. Firstly, the research on rail transit passenger flow prediction mainly focuses on the influence of price mechanism, departure time, and other factors, as well as the station accessibility analysis based on spatial model. Secondly, the research on urban public transport station spacing mainly focuses on the analysis and optimization of rail transit station spacing, for example, the analysis of influencing factors based on a double-layer optimization model. In addition, the research on the location of urban rail transit stations mainly focuses on several factors such as pipeline positioning and operation cost and uses diagnostic models to confirm the optimal location.With the continuous advances of science and technology, the techniques of mining and visualization based on the simulated annealing algorithm (SAA) have also been developed rapidly. The simulated annealing algorithm is applied in many fields such as urban space, urban hierarchical systems, and spatial and temporal activities of residents. In this study, the traffic data of Japanese tourists using IC cards on rail stations in a certain city for three consecutive months were analyzed, which covered 195 complete data source websites. The IC card inbound and outbound data are used to establish a time series of card data to study the problems in the planning of the rail transit stations.


## 2. Station Optimization Model Based on the Simulated Annealing Algorithm

The stop scheme for urban rail transit trains is analyzed, similar to that of the stop scheme for rail transit trains. The transfer method between trains is developed without considering the passengers and the trains with different speeds. The difference in the running time of the train is mainly dependent on the effect of the rail stop stations, including the initial departure time, the stop time, and the waiting time. The trains are only running and stopping at the set stations, and each station has its respective operating conditions.The formulation and consideration of parking scheme in rail transit train are jointly determined by multiple factors, and the actual parking scheme formulated for this purpose is also in different forms. Among them, the scheme of cross-station parking can effectively reduce the operation time of rail trains, but this scheme also has significant disadvantages, mainly in that the waiting time of passengers at the station is difficult to control. Secondly, based on the centripetality and tidal passenger flow of passengers, a targeted rail transit parking scheme is formulated, which can optimize the travel time of passengers. In addition, based on the integer programming model, analyzing the dynamic changes in rail train operation cost can significantly improve the economy of rail train operation. Generally speaking, the parking scheme in rail transit trains is to achieve an effective balance between passenger flow distribution, convenient transfer, and operation cost.The length of travel time of passengers is a crucial index to measure the service level of urban rail transit. Hence, the method for minimizing the travel time of passengers is an essential goal of optimizing the train stop schemes [8, 9]. The travel time of passengers includes the waiting time and the movement time of the passengers. Since the travel time of the passengers is fixed, and the corresponding price is the same based on the scheme, the passenger travel time is not discussed in this study.As an important part of urban rail transit station planning, the optimization of passenger travel time is an important means to improve passenger travel experience, travel convenience, and reduce travel cost. Generally speaking, the length of passenger travel time is often directly related to the number of stations. Dense stations will greatly reduce the travel cost of passengers, but will bring significant growth in station construction cost, especially in operation and maintenance cost. Therefore, the optimization of passenger travel time needs to comprehensively consider the influence of various factors, especially the cost of the operator. The optimization of passenger travel time needs to establish the upper- and lower-level models of operation and travel, comprehensively consider the optimization of passenger travel time and the cost of the operator, define the sum of the two as the comprehensive transportation cost of urban rail transit, and establish the optimization model based on passenger convenient travel.Taking the urban rail transit station planning model into consideration, whether there are rail transit trains at each station in the route and whether each station of rail transit stops are different. Hence, passengers have different choices of trains that they can take based on the section where the departure point is located, and the waiting time of the passengers is different accordingly. Since the train has the overtaking possibility, the waiting time of passengers taking the train at the initial departure station will also be increased accordingly. In comparison, the route operation section can be divided into two parts: the noncollinear operation section of the rail transit and the rail transit section (as shown in Figure1).Figure 1
Schematic diagram of the planning sections of urban rail transit stations.Based on the location of the departure point of passengers, the model for calculating the waiting time of passengers is developed as follows:(1)tw,i=∑j=i+1nQi,jt2xf,ef1+xf,1f2+xs,1f3.In the above equation,tw,i is the waiting time of passengers at different starting points; Qi,j is the passenger flow from station i to station j; t is the length of the research period; n is the number of stations on the whole line; f1, f2, and f3 indicate the stop time of trains corresponding to the rail transit and the stops at each station during the morning rush hours. xf,e, xf,1, and xs,1 stand for the time point when passengers take the rail transit train, respectively. When the passengers take a rail transit train xf,e, the value of 1 is taken; the value taken under deceleration is xf,1, and the value of 1 is taken; the value taken for the rest is 0. The value taken under acceleration when passengers take a rail transit train is xs,1, and the value of 1 is taken; the value taken for the rest is 0. When passengers take a rail transit train, the value taken for xf,1 and xs,1 is 1, and the value taken for the rest is 0. When passengers take any train, the value taken for all the aforesaid three is 1.


### 2.1. The Model of Stop and Departure Cases

(1)
Starting pointi is a train in a non-co-line section of rail transit; that is, passengers take a rail transit train.(2)
Starting stationi is a stop in the non-co-line operation section of rail transit, and terminal j is the train of the corresponding section; that is, passengers take the rail transit train. The terminal j is the train station in the corresponding section.(3)
Starting stationi is a station with a relatively small operation interval in the rail transit line. Terminal j is a train station in a rail transit section. Terminal j is a late train station in the non-co-line rail transit interval; that is to say, passengers take a rail transit train.(4)
The starting stationi is a common rail transit stop: the terminal j is a train in a rail transit section, where passengers can take rail transit trains with a higher capacity. Terminal j is an express station in the rail transit section, where passengers can take all trains available. The terminal station j is a station with a relatively slow rail transit in the non-co-line operation section, which indicates that passengers can take a rail transit train. Terminal j is a train station in a non-co-line section of the rail transit; that is, passengers can take a rail transit train.


### 2.2. Total Waiting Time of Passengers at Stops

The total waiting time of passengers for the train is mainly composed of two parts. The first part is the regular stop time experienced by passengers when they travel by training running at different speeds. The second part is the other possible waiting time of passengers when they take the train during their trip, as shown in Figure2.Figure 2
Schematic diagram of the train operation.The waiting time of passengers from getting on the train from stationi and getting off the train at station j is as follows:(2)ts=tsn+tf,(3)tsn=∑j=i+1nQi,j∑k=i+1j−1tk,1+tk,2+∑k=i+1j−1sktk,1+tk,2,(4)tf=∑j=i+1nQi,j∑k=i+1j−1ckt1d′−t1d.In the above equation:tk,1 and tk,2 indicate the train stop time at the kth station and the kth station in turn. sk is the variable ranging from 0 to 1. In the case of emergency stops, the value of 1 is taken; otherwise, the value of 0 is taken. ck indicates the variable ranging from 0 to 1. In the case when the train takes shelter shunt, the value of 1 is taken; otherwise, the value of 0 is taken.Based on the above analysis, the objective function with the minimum total travel timeZ can be established as follows:(5)Zmin=∑i=1n−1tw,i+ts,i,(6)s.t.f1≥1,f2≥1,f3≥1,(7)f1+f2+f3≤f,(8)f≥12,(9)x1=1,xn=1,(10)∑j=i+1nQi,j≤ηmaxafkk=1,2,3.Equations (6) and (7) can ensure that all types of trains in a certain time period will be operated at least once. In the case that the other conditions remain unchanged, it is stipulated in the construction standard for the urban rail transit projects that the train operation should not be less than 12 h during peak hours. Hence, equation (8) can ensure that the trains in each line should meet the minimum number of departures. Equation (9) indicates the first and last stop required on the line. Equation (6) can guarantee that when the number of trains is a, the trains on each traffic route should meet the requirements of the full load rate ηmax in the section.


### 2.3. Specific Calculation Steps of the Genetic Algorithm

In the simulated annealing algorithm put forward in this study, the optimization model for the departure scheme of urban rail transit line trains is a monocular nonlinear planning model. The specific steps for the calculation in the genetic algorithm are described as follows:(1)
The parameters of several variables should be determined, including initial temperature and population number, variation, and difference. Chromosomes that meet the constraints are established.(2)
Encode and decode, and use binary to encode. Then, the initial population is formed by randomly obtaining the feasible solution. The chromosome genes are encoded using a binary encoding method in the form of 110110101, one of which stands for a stop station, and so on.(3)
In addition, the objective function is processed by determining the fitness function, and the weight coefficient is established. The initial generation is randomized. The number of the first group should be selected in a reasonable and scientific manner. The fitness of each chromosome is calculated. Adaptability is the only index that can reflect the superiority and inferiority of chromosomes, and the genetic algorithm is to identify the most adaptable chromosomes.(11)Fx=M−Zx.In the above equation:F(x) indicates the fitness function established; M indicates the maximum value estimated based on the model; and Z(x) indicates objective function.(4)
The duplication, crossover, and mutation operators are used to prepare the individuals at the child nodes. The aforesaid three operators are the basic operators of the genetic algorithm, where replication has indicated the natural law of superiority and inferiority, the crossover has indicated the concept of sexual reproduction, and mutation has indicated the mutation of genetic factors in the evolutionary process.(5)
Steps (3) and (4) are repeated until the termination conditions are met.


## 2.1. The Model of Stop and Departure Cases

(1)
Starting pointi is a train in a non-co-line section of rail transit; that is, passengers take a rail transit train.(2)
Starting stationi is a stop in the non-co-line operation section of rail transit, and terminal j is the train of the corresponding section; that is, passengers take the rail transit train. The terminal j is the train station in the corresponding section.(3)
Starting stationi is a station with a relatively small operation interval in the rail transit line. Terminal j is a train station in a rail transit section. Terminal j is a late train station in the non-co-line rail transit interval; that is to say, passengers take a rail transit train.(4)
The starting stationi is a common rail transit stop: the terminal j is a train in a rail transit section, where passengers can take rail transit trains with a higher capacity. Terminal j is an express station in the rail transit section, where passengers can take all trains available. The terminal station j is a station with a relatively slow rail transit in the non-co-line operation section, which indicates that passengers can take a rail transit train. Terminal j is a train station in a non-co-line section of the rail transit; that is, passengers can take a rail transit train.


## 2.2. Total Waiting Time of Passengers at Stops

The total waiting time of passengers for the train is mainly composed of two parts. The first part is the regular stop time experienced by passengers when they travel by training running at different speeds. The second part is the other possible waiting time of passengers when they take the train during their trip, as shown in Figure2.Figure 2
Schematic diagram of the train operation.The waiting time of passengers from getting on the train from stationi and getting off the train at station j is as follows:(2)ts=tsn+tf,(3)tsn=∑j=i+1nQi,j∑k=i+1j−1tk,1+tk,2+∑k=i+1j−1sktk,1+tk,2,(4)tf=∑j=i+1nQi,j∑k=i+1j−1ckt1d′−t1d.In the above equation:tk,1 and tk,2 indicate the train stop time at the kth station and the kth station in turn. sk is the variable ranging from 0 to 1. In the case of emergency stops, the value of 1 is taken; otherwise, the value of 0 is taken. ck indicates the variable ranging from 0 to 1. In the case when the train takes shelter shunt, the value of 1 is taken; otherwise, the value of 0 is taken.Based on the above analysis, the objective function with the minimum total travel timeZ can be established as follows:(5)Zmin=∑i=1n−1tw,i+ts,i,(6)s.t.f1≥1,f2≥1,f3≥1,(7)f1+f2+f3≤f,(8)f≥12,(9)x1=1,xn=1,(10)∑j=i+1nQi,j≤ηmaxafkk=1,2,3.Equations (6) and (7) can ensure that all types of trains in a certain time period will be operated at least once. In the case that the other conditions remain unchanged, it is stipulated in the construction standard for the urban rail transit projects that the train operation should not be less than 12 h during peak hours. Hence, equation (8) can ensure that the trains in each line should meet the minimum number of departures. Equation (9) indicates the first and last stop required on the line. Equation (6) can guarantee that when the number of trains is a, the trains on each traffic route should meet the requirements of the full load rate ηmax in the section.


## 2.3. Specific Calculation Steps of the Genetic Algorithm

In the simulated annealing algorithm put forward in this study, the optimization model for the departure scheme of urban rail transit line trains is a monocular nonlinear planning model. The specific steps for the calculation in the genetic algorithm are described as follows:(1)
The parameters of several variables should be determined, including initial temperature and population number, variation, and difference. Chromosomes that meet the constraints are established.(2)
Encode and decode, and use binary to encode. Then, the initial population is formed by randomly obtaining the feasible solution. The chromosome genes are encoded using a binary encoding method in the form of 110110101, one of which stands for a stop station, and so on.(3)
In addition, the objective function is processed by determining the fitness function, and the weight coefficient is established. The initial generation is randomized. The number of the first group should be selected in a reasonable and scientific manner. The fitness of each chromosome is calculated. Adaptability is the only index that can reflect the superiority and inferiority of chromosomes, and the genetic algorithm is to identify the most adaptable chromosomes.(11)Fx=M−Zx.In the above equation:F(x) indicates the fitness function established; M indicates the maximum value estimated based on the model; and Z(x) indicates objective function.(4)
The duplication, crossover, and mutation operators are used to prepare the individuals at the child nodes. The aforesaid three operators are the basic operators of the genetic algorithm, where replication has indicated the natural law of superiority and inferiority, the crossover has indicated the concept of sexual reproduction, and mutation has indicated the mutation of genetic factors in the evolutionary process.(5)
Steps (3) and (4) are repeated until the termination conditions are met.


## 3. Data and Methods

### 3.1. Data Description

Based on the data from the Rail Transit Bureau, there are 74,516,289 complete trips (including card settlement records for complete admission and exit stations) in the city from March 1 to 20, 2018, without major special festivals, and there are a total of 209 at rail stations. For the purpose of ensuring the accuracy and quality of the data, the acquired data are processed, and the stations with incomplete settlement records of inbound and outbound cards are removed [10, 11]. The essential data information contained in the records is shown in Table 1.Table 1
0-D passenger flow (unit: persons/unit time).
0DNumber of people on the bus1234567891011121310200300350905105010050100405030187020040030080510200300502305030090251030001503050501602700709060930400000030501304060502506105000000503070170602006064060000006004020070060401010700000007040210601003051080000000040010080205065090000000005070204018010000000000050601102201100000000000180160340120000000000007070130000000000001010Number of people who get off the train01503006002301420980750121097054011308809160In this study, only the one-way stop scheme of the train is discussed. Hence, the triangle value in the 0-D table is set to 0.


### 3.2. SAA Method

#### 3.2.1. Symbolic Representation

Based on the SAA, the lengthm in a random time period is converted into the length nn≪m. The code line n is the number of segmented subsequences. According to the time series thus obtained, the process of the SAA algorithm can mainly be divided into 3 steps as follows:(1)
The time seriesX of the normalized source is standardized based on equation (1) into a series with the mean value of 0 and the square difference of 1. The standardization will not change the shape or scale of the original sequence X.(12)xi′=xi−uxσx.In the above equation: observation value corresponding to variableXi at a certain time xi; ux stands for the mean value of all observations in the sequence X; σx stands for the standard deviation of all observations in the sequence X.(2)
The PAA method is applied, where the subsequence lengthw and the length m time series are divided into sequences with the length of n. In addition, the mean value of each layer subsequence is calculated based on equation X¯=x¯1,x¯2,…,x¯n (13) as follows:(13)x˜j=nm∑i=m/nj−1+1m/njxi′.(3)
As the code display sequence is similar to the Gaussian distribution, it is divided into equal intervals based on probability. The values for the division points of the distinguishing interval series are taken according to Table2 and are denoted by the sequence∼value∼ the same symbol located in the same interval. Finally, the code demonstration is obtained.Table 2
Optimization results ofA and B train parking plan.
Station number12345678910111213XA1011101100011XB1011010011011ΔTΔT=254.7min


#### 3.2.2. Similarity Measurement Method

For any two time seriesQ=q1,q2,…,qm and C=c1,c2,…,cm with the time-series length of m, the SAA method is adopted to set the coding sequence representation of length n as the sum. For the purpose of simulating the annealing of a symbol sequence, firstly, it is necessary to calculate the similarity between various symbol sequences. Based on the SAA method, equation (3) is used to calculate the distance between the sequences and to indicate the similarity between them, which stands for the distance between two symbols.(14)MINDISTQ˜,C˜=mn∑i=1ndistq˜i−c˜i2.


### 3.3. Experimental Analysis and Results

#### 3.3.1. Case Design and Calculation

It is assumed that there is a railway line with 13 stations. During a certain period, the passenger flow between stations on this line 0-D is shown in Table1. The train will stop at the two stations to meet the demand of all passengers.According to the operating parameters of subway trains [12, 13], the starting acceleration of the train is 0379 m/s2, the braking deceleration speed is 140 m/s2, the maximum running speed is 85 km/h, the departure interval is h = 2.6 min, hAB=2.25min, hA/B=5min, the stopping time is 0.5 min, and the number of repetitions is 500. The above parameters are introduced into the model, Pentium 4 3.2 Hz, and 1000M RAM computer. The Tabu search algorithm is programmed and executed based on the VC+ platform, and the A and B train stop scheme that saves the most travel time for passengers is obtained. The optimization results of the train A and train B stop scheme are shown in Table 2.According to the data in Table2, train A and train B are required to stop at the same time at the second and ninth stations in addition to stopping at the initial departure station. They should also stop at the other stations according to the optimal scheme. In addition, under the conditions that the parameters and O-D passenger flow are known, the total travel time of passengers can be saved to 253.6 minutes when the train stops at intersections based on the method described above. The results of the calculation indicate that under the given parameter conditions, the span stop scheme is feasible.


#### 3.3.2. Parking Scheme of Other Stations

The determination of the parking scheme of other stations according to the best scheme also needs opportunities to shorten the travel time of passengers and reduce the operation cost of enterprises. Therefore, the mathematical model constraints of the established stop scheme are shown in the following equation:(15)ZminT≤∑i=1s∑k=1nLi,k≤ZmaxT,where T is the number of slow train departures in the optimization period, L is the passenger flow from station i to station k, and Zmin and Zmax are the minimum and maximum passenger capacity of the train, respectively.Under the above constraint model, the reference formulas for establishing the best parking scheme are shown in equations (16) and (17). Formula (16) is the function of the best parking scheme reflecting the interests of passengers, and formula (17) is the function of the best parking scheme reflecting the rail transit operation enterprise.(16)fpassenger=fwait+fon+fstop,(17)fenterprise=ffix+fvariable+fstop.For the purpose of further verifying the convergence of the Tabu search algorithm, the length of each Tabu table is 6–9, and its effects on the algorithm calculation are compared, as shown in Figure3. The curve in Figure 4 converges to the neighboring values of the function, which indicates that the Tabu search algorithm has superior robustness. If the Tabu length is 6, the function value obtained by most iterations is relatively small, the fluctuation is significant, and the convergence speed is slow. The length of the Tabu is 7 points, the convergence speed is 6 points earlier than the length of the Tabu, and the value of each function is relatively small apparently. ΔT=254.3min, when the length of the Tabu is 8, the function value converges to ΔT=254.7min, the change in the curve is mild, and the convergence speed is the highest. When the number of repetitions is 110 times, the function value converges. The length of the Tabu is 9, and the function value will converge to ΔT=254.7min. The number of iterations converges close to 120, and the speed of convergence is relatively slow. If the stability and convergence rate of the objective function in the iterative process are combined, the Tabu length is designed to be 8 in the given parameters, which is appropriate.Figure 3
Schematic diagram of the iterative process of the objective function value.Figure 4
Comparative analysis of the passenger waiting time.The total waiting time of passengers is mainly composed of two parts. The comparison is shown in Figure4. It can be seen from Figure 4 that the normal parking time that passengers on trains with different speeds can experience is significantly shorter than that of passengers who change trains during the journey. This result is consistent with people's practical cognition, mainly because passengers need to spend more time in the process of transfer.


#### 3.3.3. Analysis of Parameter Sensitivity

In the model, the departure interval, stop time, and maximum operating speed of the trains are correlated with the saving in the travel time of all passengers. Different values are taken for each parameter to carry out sensitivity analysis of the objective function value. The results are shown in Figure5.Figure 5
Schematic diagram of the relationship between the changes in the parameter andΔT. (a) The impact of departure interval hAB on ΔT. (b) The impact of departure interval hA/B on ΔT. (c) The impact of stop interval ts on ΔT. (d) The impact of maximum speed Vmax on ΔT.
(a)(b)(c)(d)From Figure5, the following conclusions can be drawn:(1)
From Figures5(a) and 5(b), it can be seen that with other parameters fixed, the objective function value hAB is decreased as the departure interval of the train increases and is increased as the departure interval hA/B increases. In addition, the change in the function value is more significant. The change in ΔT is mild when hA/B is in the range from 2.5 min to 3.5 min, such as area A; when hA/B is greater than 3.5 min, the change in ΔT is significant. Hence, it is recommended that the value taken for hA/B should be greater than 3.5 min. Thus, it can be observed that the changes in hAB and hA/B can change ΔT effectively. However, in view of the fact that hAB and hA/B are also significantly influenced by passenger demand, and its changes have an enormous impact on the adjustment of train operation schedules, it is recommended that hAB and hA/B should be adjusted as appropriate based on the requirements of the schedule so as to achieve the purpose of optimizing the AT.(2)
As indicated in Figure5(c), if 20 s-60 s is selected for discussion, it has a linear and positive correlation with the stop time, and the change is significant. This suggests that for the purpose of increasing ts and also taking into consideration the safety of passengers who get on and off the train, it is necessary to increase ts as appropriate. However, if a substantial increase in ts is made, the waiting time of passengers at the stations will be extended, and their satisfaction with rail transit services will be reduced. Hence, it is necessary to make adjustments based on the number of passengers at the stations as appropriate. In general, the stop time at a Chinese urban rail transit station not in the peak period is 30 s.(3)
From Figure5(d), it can be observed that the maximum operating speed Vmax has a linear positive correlation with ΔT. However, the change is not significant, probably because it is subject to the influence of customer traffic. In addition, as Vmax is subject to restrictions on the performance and operating conditions of the vehicle itself, Vmax cannot be improved at will. Moreover, it is stipulated in the metro-vehicle design standard that the maximum operating speed should be 80 km/h [14, 15]. However, for the purpose of increasing the maximum operating speed under the cross-station plan, increasing the maximum operating speed to above 80 km/h will not only increase the cost significantly, but the increase in the operating costs is not meaningful for improving the operational efficiency.To improve the robustness of the algorithm, it is necessary to further optimize the function model, mainly taking the minimum comprehensive station planning cost as the objective function to establish the optimization model of rail transit station location. Based on the basic characteristics of large correlation between station combination scheme and passenger flow, the station model is optimized to establish a positive correlation between passenger flow and target value. In addition, by associating the station model with the comprehensive cost model of individual passengers, a two-tier optimization model is constructed, which greatly improves the robustness and robustness of the algorithm.To sum up, in the well-known O-D state, the changes in the departure intervalshAB and hA/B have a more significant impact than the other parameters, whereas the stop time ts and the maximum operating speed Vmax have a less significant impact on the changes in ΔT than the aforesaid two parameters. For the purpose of maximizing the value of the objective function, the operator can adjust the parameters described above under the condition of considering the operating costs and benefits comprehensively and give priority to the adjustment of the departure intervals hAB and hA/B. In addition, as the starting acceleration and braking deceleration are determined based on the features of the vehicle, it is unusual to adjust the parameters so that they can adapt to the operating modes of different trains.


## 3.1. Data Description

Based on the data from the Rail Transit Bureau, there are 74,516,289 complete trips (including card settlement records for complete admission and exit stations) in the city from March 1 to 20, 2018, without major special festivals, and there are a total of 209 at rail stations. For the purpose of ensuring the accuracy and quality of the data, the acquired data are processed, and the stations with incomplete settlement records of inbound and outbound cards are removed [10, 11]. The essential data information contained in the records is shown in Table 1.Table 1
0-D passenger flow (unit: persons/unit time).
0DNumber of people on the bus1234567891011121310200300350905105010050100405030187020040030080510200300502305030090251030001503050501602700709060930400000030501304060502506105000000503070170602006064060000006004020070060401010700000007040210601003051080000000040010080205065090000000005070204018010000000000050601102201100000000000180160340120000000000007070130000000000001010Number of people who get off the train01503006002301420980750121097054011308809160In this study, only the one-way stop scheme of the train is discussed. Hence, the triangle value in the 0-D table is set to 0.


## 3.2. SAA Method

### 3.2.1. Symbolic Representation

Based on the SAA, the lengthm in a random time period is converted into the length nn≪m. The code line n is the number of segmented subsequences. According to the time series thus obtained, the process of the SAA algorithm can mainly be divided into 3 steps as follows:(1)
The time seriesX of the normalized source is standardized based on equation (1) into a series with the mean value of 0 and the square difference of 1. The standardization will not change the shape or scale of the original sequence X.(12)xi′=xi−uxσx.In the above equation: observation value corresponding to variableXi at a certain time xi; ux stands for the mean value of all observations in the sequence X; σx stands for the standard deviation of all observations in the sequence X.(2)
The PAA method is applied, where the subsequence lengthw and the length m time series are divided into sequences with the length of n. In addition, the mean value of each layer subsequence is calculated based on equation X¯=x¯1,x¯2,…,x¯n (13) as follows:(13)x˜j=nm∑i=m/nj−1+1m/njxi′.(3)
As the code display sequence is similar to the Gaussian distribution, it is divided into equal intervals based on probability. The values for the division points of the distinguishing interval series are taken according to Table2 and are denoted by the sequence∼value∼ the same symbol located in the same interval. Finally, the code demonstration is obtained.Table 2
Optimization results ofA and B train parking plan.
Station number12345678910111213XA1011101100011XB1011010011011ΔTΔT=254.7min


### 3.2.2. Similarity Measurement Method

For any two time seriesQ=q1,q2,…,qm and C=c1,c2,…,cm with the time-series length of m, the SAA method is adopted to set the coding sequence representation of length n as the sum. For the purpose of simulating the annealing of a symbol sequence, firstly, it is necessary to calculate the similarity between various symbol sequences. Based on the SAA method, equation (3) is used to calculate the distance between the sequences and to indicate the similarity between them, which stands for the distance between two symbols.(14)MINDISTQ˜,C˜=mn∑i=1ndistq˜i−c˜i2.


## 3.2.1. Symbolic Representation

Based on the SAA, the lengthm in a random time period is converted into the length nn≪m. The code line n is the number of segmented subsequences. According to the time series thus obtained, the process of the SAA algorithm can mainly be divided into 3 steps as follows:(1)
The time seriesX of the normalized source is standardized based on equation (1) into a series with the mean value of 0 and the square difference of 1. The standardization will not change the shape or scale of the original sequence X.(12)xi′=xi−uxσx.In the above equation: observation value corresponding to variableXi at a certain time xi; ux stands for the mean value of all observations in the sequence X; σx stands for the standard deviation of all observations in the sequence X.(2)
The PAA method is applied, where the subsequence lengthw and the length m time series are divided into sequences with the length of n. In addition, the mean value of each layer subsequence is calculated based on equation X¯=x¯1,x¯2,…,x¯n (13) as follows:(13)x˜j=nm∑i=m/nj−1+1m/njxi′.(3)
As the code display sequence is similar to the Gaussian distribution, it is divided into equal intervals based on probability. The values for the division points of the distinguishing interval series are taken according to Table2 and are denoted by the sequence∼value∼ the same symbol located in the same interval. Finally, the code demonstration is obtained.Table 2
Optimization results ofA and B train parking plan.
Station number12345678910111213XA1011101100011XB1011010011011ΔTΔT=254.7min


## 3.2.2. Similarity Measurement Method

For any two time seriesQ=q1,q2,…,qm and C=c1,c2,…,cm with the time-series length of m, the SAA method is adopted to set the coding sequence representation of length n as the sum. For the purpose of simulating the annealing of a symbol sequence, firstly, it is necessary to calculate the similarity between various symbol sequences. Based on the SAA method, equation (3) is used to calculate the distance between the sequences and to indicate the similarity between them, which stands for the distance between two symbols.(14)MINDISTQ˜,C˜=mn∑i=1ndistq˜i−c˜i2.


## 3.3. Experimental Analysis and Results

### 3.3.1. Case Design and Calculation

It is assumed that there is a railway line with 13 stations. During a certain period, the passenger flow between stations on this line 0-D is shown in Table1. The train will stop at the two stations to meet the demand of all passengers.According to the operating parameters of subway trains [12, 13], the starting acceleration of the train is 0379 m/s2, the braking deceleration speed is 140 m/s2, the maximum running speed is 85 km/h, the departure interval is h = 2.6 min, hAB=2.25min, hA/B=5min, the stopping time is 0.5 min, and the number of repetitions is 500. The above parameters are introduced into the model, Pentium 4 3.2 Hz, and 1000M RAM computer. The Tabu search algorithm is programmed and executed based on the VC+ platform, and the A and B train stop scheme that saves the most travel time for passengers is obtained. The optimization results of the train A and train B stop scheme are shown in Table 2.According to the data in Table2, train A and train B are required to stop at the same time at the second and ninth stations in addition to stopping at the initial departure station. They should also stop at the other stations according to the optimal scheme. In addition, under the conditions that the parameters and O-D passenger flow are known, the total travel time of passengers can be saved to 253.6 minutes when the train stops at intersections based on the method described above. The results of the calculation indicate that under the given parameter conditions, the span stop scheme is feasible.


### 3.3.2. Parking Scheme of Other Stations

The determination of the parking scheme of other stations according to the best scheme also needs opportunities to shorten the travel time of passengers and reduce the operation cost of enterprises. Therefore, the mathematical model constraints of the established stop scheme are shown in the following equation:(15)ZminT≤∑i=1s∑k=1nLi,k≤ZmaxT,where T is the number of slow train departures in the optimization period, L is the passenger flow from station i to station k, and Zmin and Zmax are the minimum and maximum passenger capacity of the train, respectively.Under the above constraint model, the reference formulas for establishing the best parking scheme are shown in equations (16) and (17). Formula (16) is the function of the best parking scheme reflecting the interests of passengers, and formula (17) is the function of the best parking scheme reflecting the rail transit operation enterprise.(16)fpassenger=fwait+fon+fstop,(17)fenterprise=ffix+fvariable+fstop.For the purpose of further verifying the convergence of the Tabu search algorithm, the length of each Tabu table is 6–9, and its effects on the algorithm calculation are compared, as shown in Figure3. The curve in Figure 4 converges to the neighboring values of the function, which indicates that the Tabu search algorithm has superior robustness. If the Tabu length is 6, the function value obtained by most iterations is relatively small, the fluctuation is significant, and the convergence speed is slow. The length of the Tabu is 7 points, the convergence speed is 6 points earlier than the length of the Tabu, and the value of each function is relatively small apparently. ΔT=254.3min, when the length of the Tabu is 8, the function value converges to ΔT=254.7min, the change in the curve is mild, and the convergence speed is the highest. When the number of repetitions is 110 times, the function value converges. The length of the Tabu is 9, and the function value will converge to ΔT=254.7min. The number of iterations converges close to 120, and the speed of convergence is relatively slow. If the stability and convergence rate of the objective function in the iterative process are combined, the Tabu length is designed to be 8 in the given parameters, which is appropriate.Figure 3
Schematic diagram of the iterative process of the objective function value.Figure 4
Comparative analysis of the passenger waiting time.The total waiting time of passengers is mainly composed of two parts. The comparison is shown in Figure4. It can be seen from Figure 4 that the normal parking time that passengers on trains with different speeds can experience is significantly shorter than that of passengers who change trains during the journey. This result is consistent with people's practical cognition, mainly because passengers need to spend more time in the process of transfer.


### 3.3.3. Analysis of Parameter Sensitivity

In the model, the departure interval, stop time, and maximum operating speed of the trains are correlated with the saving in the travel time of all passengers. Different values are taken for each parameter to carry out sensitivity analysis of the objective function value. The results are shown in Figure5.Figure 5
Schematic diagram of the relationship between the changes in the parameter andΔT. (a) The impact of departure interval hAB on ΔT. (b) The impact of departure interval hA/B on ΔT. (c) The impact of stop interval ts on ΔT. (d) The impact of maximum speed Vmax on ΔT.
(a)(b)(c)(d)From Figure5, the following conclusions can be drawn:(1)
From Figures5(a) and 5(b), it can be seen that with other parameters fixed, the objective function value hAB is decreased as the departure interval of the train increases and is increased as the departure interval hA/B increases. In addition, the change in the function value is more significant. The change in ΔT is mild when hA/B is in the range from 2.5 min to 3.5 min, such as area A; when hA/B is greater than 3.5 min, the change in ΔT is significant. Hence, it is recommended that the value taken for hA/B should be greater than 3.5 min. Thus, it can be observed that the changes in hAB and hA/B can change ΔT effectively. However, in view of the fact that hAB and hA/B are also significantly influenced by passenger demand, and its changes have an enormous impact on the adjustment of train operation schedules, it is recommended that hAB and hA/B should be adjusted as appropriate based on the requirements of the schedule so as to achieve the purpose of optimizing the AT.(2)
As indicated in Figure5(c), if 20 s-60 s is selected for discussion, it has a linear and positive correlation with the stop time, and the change is significant. This suggests that for the purpose of increasing ts and also taking into consideration the safety of passengers who get on and off the train, it is necessary to increase ts as appropriate. However, if a substantial increase in ts is made, the waiting time of passengers at the stations will be extended, and their satisfaction with rail transit services will be reduced. Hence, it is necessary to make adjustments based on the number of passengers at the stations as appropriate. In general, the stop time at a Chinese urban rail transit station not in the peak period is 30 s.(3)
From Figure5(d), it can be observed that the maximum operating speed Vmax has a linear positive correlation with ΔT. However, the change is not significant, probably because it is subject to the influence of customer traffic. In addition, as Vmax is subject to restrictions on the performance and operating conditions of the vehicle itself, Vmax cannot be improved at will. Moreover, it is stipulated in the metro-vehicle design standard that the maximum operating speed should be 80 km/h [14, 15]. However, for the purpose of increasing the maximum operating speed under the cross-station plan, increasing the maximum operating speed to above 80 km/h will not only increase the cost significantly, but the increase in the operating costs is not meaningful for improving the operational efficiency.To improve the robustness of the algorithm, it is necessary to further optimize the function model, mainly taking the minimum comprehensive station planning cost as the objective function to establish the optimization model of rail transit station location. Based on the basic characteristics of large correlation between station combination scheme and passenger flow, the station model is optimized to establish a positive correlation between passenger flow and target value. In addition, by associating the station model with the comprehensive cost model of individual passengers, a two-tier optimization model is constructed, which greatly improves the robustness and robustness of the algorithm.To sum up, in the well-known O-D state, the changes in the departure intervalshAB and hA/B have a more significant impact than the other parameters, whereas the stop time ts and the maximum operating speed Vmax have a less significant impact on the changes in ΔT than the aforesaid two parameters. For the purpose of maximizing the value of the objective function, the operator can adjust the parameters described above under the condition of considering the operating costs and benefits comprehensively and give priority to the adjustment of the departure intervals hAB and hA/B. In addition, as the starting acceleration and braking deceleration are determined based on the features of the vehicle, it is unusual to adjust the parameters so that they can adapt to the operating modes of different trains.


## 3.3.1. Case Design and Calculation

It is assumed that there is a railway line with 13 stations. During a certain period, the passenger flow between stations on this line 0-D is shown in Table1. The train will stop at the two stations to meet the demand of all passengers.According to the operating parameters of subway trains [12, 13], the starting acceleration of the train is 0379 m/s2, the braking deceleration speed is 140 m/s2, the maximum running speed is 85 km/h, the departure interval is h = 2.6 min, hAB=2.25min, hA/B=5min, the stopping time is 0.5 min, and the number of repetitions is 500. The above parameters are introduced into the model, Pentium 4 3.2 Hz, and 1000M RAM computer. The Tabu search algorithm is programmed and executed based on the VC+ platform, and the A and B train stop scheme that saves the most travel time for passengers is obtained. The optimization results of the train A and train B stop scheme are shown in Table 2.According to the data in Table2, train A and train B are required to stop at the same time at the second and ninth stations in addition to stopping at the initial departure station. They should also stop at the other stations according to the optimal scheme. In addition, under the conditions that the parameters and O-D passenger flow are known, the total travel time of passengers can be saved to 253.6 minutes when the train stops at intersections based on the method described above. The results of the calculation indicate that under the given parameter conditions, the span stop scheme is feasible.


## 3.3.2. Parking Scheme of Other Stations

The determination of the parking scheme of other stations according to the best scheme also needs opportunities to shorten the travel time of passengers and reduce the operation cost of enterprises. Therefore, the mathematical model constraints of the established stop scheme are shown in the following equation:(15)ZminT≤∑i=1s∑k=1nLi,k≤ZmaxT,where T is the number of slow train departures in the optimization period, L is the passenger flow from station i to station k, and Zmin and Zmax are the minimum and maximum passenger capacity of the train, respectively.Under the above constraint model, the reference formulas for establishing the best parking scheme are shown in equations (16) and (17). Formula (16) is the function of the best parking scheme reflecting the interests of passengers, and formula (17) is the function of the best parking scheme reflecting the rail transit operation enterprise.(16)fpassenger=fwait+fon+fstop,(17)fenterprise=ffix+fvariable+fstop.For the purpose of further verifying the convergence of the Tabu search algorithm, the length of each Tabu table is 6–9, and its effects on the algorithm calculation are compared, as shown in Figure3. The curve in Figure 4 converges to the neighboring values of the function, which indicates that the Tabu search algorithm has superior robustness. If the Tabu length is 6, the function value obtained by most iterations is relatively small, the fluctuation is significant, and the convergence speed is slow. The length of the Tabu is 7 points, the convergence speed is 6 points earlier than the length of the Tabu, and the value of each function is relatively small apparently. ΔT=254.3min, when the length of the Tabu is 8, the function value converges to ΔT=254.7min, the change in the curve is mild, and the convergence speed is the highest. When the number of repetitions is 110 times, the function value converges. The length of the Tabu is 9, and the function value will converge to ΔT=254.7min. The number of iterations converges close to 120, and the speed of convergence is relatively slow. If the stability and convergence rate of the objective function in the iterative process are combined, the Tabu length is designed to be 8 in the given parameters, which is appropriate.Figure 3
Schematic diagram of the iterative process of the objective function value.Figure 4
Comparative analysis of the passenger waiting time.The total waiting time of passengers is mainly composed of two parts. The comparison is shown in Figure4. It can be seen from Figure 4 that the normal parking time that passengers on trains with different speeds can experience is significantly shorter than that of passengers who change trains during the journey. This result is consistent with people's practical cognition, mainly because passengers need to spend more time in the process of transfer.


## 3.3.3. Analysis of Parameter Sensitivity

In the model, the departure interval, stop time, and maximum operating speed of the trains are correlated with the saving in the travel time of all passengers. Different values are taken for each parameter to carry out sensitivity analysis of the objective function value. The results are shown in Figure5.Figure 5
Schematic diagram of the relationship between the changes in the parameter andΔT. (a) The impact of departure interval hAB on ΔT. (b) The impact of departure interval hA/B on ΔT. (c) The impact of stop interval ts on ΔT. (d) The impact of maximum speed Vmax on ΔT.
(a)(b)(c)(d)From Figure5, the following conclusions can be drawn:(1)
From Figures5(a) and 5(b), it can be seen that with other parameters fixed, the objective function value hAB is decreased as the departure interval of the train increases and is increased as the departure interval hA/B increases. In addition, the change in the function value is more significant. The change in ΔT is mild when hA/B is in the range from 2.5 min to 3.5 min, such as area A; when hA/B is greater than 3.5 min, the change in ΔT is significant. Hence, it is recommended that the value taken for hA/B should be greater than 3.5 min. Thus, it can be observed that the changes in hAB and hA/B can change ΔT effectively. However, in view of the fact that hAB and hA/B are also significantly influenced by passenger demand, and its changes have an enormous impact on the adjustment of train operation schedules, it is recommended that hAB and hA/B should be adjusted as appropriate based on the requirements of the schedule so as to achieve the purpose of optimizing the AT.(2)
As indicated in Figure5(c), if 20 s-60 s is selected for discussion, it has a linear and positive correlation with the stop time, and the change is significant. This suggests that for the purpose of increasing ts and also taking into consideration the safety of passengers who get on and off the train, it is necessary to increase ts as appropriate. However, if a substantial increase in ts is made, the waiting time of passengers at the stations will be extended, and their satisfaction with rail transit services will be reduced. Hence, it is necessary to make adjustments based on the number of passengers at the stations as appropriate. In general, the stop time at a Chinese urban rail transit station not in the peak period is 30 s.(3)
From Figure5(d), it can be observed that the maximum operating speed Vmax has a linear positive correlation with ΔT. However, the change is not significant, probably because it is subject to the influence of customer traffic. In addition, as Vmax is subject to restrictions on the performance and operating conditions of the vehicle itself, Vmax cannot be improved at will. Moreover, it is stipulated in the metro-vehicle design standard that the maximum operating speed should be 80 km/h [14, 15]. However, for the purpose of increasing the maximum operating speed under the cross-station plan, increasing the maximum operating speed to above 80 km/h will not only increase the cost significantly, but the increase in the operating costs is not meaningful for improving the operational efficiency.To improve the robustness of the algorithm, it is necessary to further optimize the function model, mainly taking the minimum comprehensive station planning cost as the objective function to establish the optimization model of rail transit station location. Based on the basic characteristics of large correlation between station combination scheme and passenger flow, the station model is optimized to establish a positive correlation between passenger flow and target value. In addition, by associating the station model with the comprehensive cost model of individual passengers, a two-tier optimization model is constructed, which greatly improves the robustness and robustness of the algorithm.To sum up, in the well-known O-D state, the changes in the departure intervalshAB and hA/B have a more significant impact than the other parameters, whereas the stop time ts and the maximum operating speed Vmax have a less significant impact on the changes in ΔT than the aforesaid two parameters. For the purpose of maximizing the value of the objective function, the operator can adjust the parameters described above under the condition of considering the operating costs and benefits comprehensively and give priority to the adjustment of the departure intervals hAB and hA/B. In addition, as the starting acceleration and braking deceleration are determined based on the features of the vehicle, it is unusual to adjust the parameters so that they can adapt to the operating modes of different trains.


## 4. Conclusions

As the feedback on the real-time and accurate data of the stations that the train stops is required for vehicles on the rail when they stop at the station, broadcasting or electronic information can be used at the stop stations to disseminate relevant data information to the driver and passengers so as to ensure that the passengers can get on the train in time. In this study, a reasonable method for the analysis of the urban rail transit station planning is established by evaluating multiple factors such as the random arrival of the passenger flow at the station, the distance between trains, and the passenger capacity comprehensively.



---

*Source: 3941554-2022-03-07.xml*