# Train Scheduling Optimization for an Urban Rail Transit Line: A Simulated-Annealing Algorithm Using a Large Neighborhood Search Metaheuristic

Authors: Hai Zhang; Shaoquan Ni
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

This paper describes an optimization model for an irregular train schedule. The aim is to optimize both the maximum train loading rate and the average deviation of departure intervals under time-varying passenger transport demand for an urban rail transit line in consideration of practical train operation constraints, i.e., headway, running time between stations, dwell time, and capacity. A heuristic simulated-annealing algorithm is designed to solve the optimization model, and a case study of an urban rail transit line is performed to assess its efficacy. The results show that, compared with the current regular train schedule, the total train dwell time under the optimized irregular schedule is reduced from 900 s to 848 s, and the reduction ratio for the maximum train loading rate is from 1.2% to 3.6% for different stations. When the average train departure interval is allowed to vary from 120 to 170 s, the optimized irregular schedule decreases the maximum train loading rate of the collinear and noncollinear sections by 3.21%–4.82% and 2.52%–3.64%, respectively. Sensitivity analysis is performed for a nonnegative weight coefficient, average train departure interval, and proportion of full-length and short-turn routings. The proposed approach can be used to support capacity improvement and schedule optimization for urban rail transit lines.


---

## Body

## 1. Introduction

Urban rail transit (URT) is very important for the stability, efficiency, and sustainability of public transportation. As an important target of optimization in railway transportation, train scheduling has received considerable attention. The models designed to generate or optimize train schedules [1–7] can be divided into two different categories: regular and irregular. Unlike irregular train schedules, regular ones are easy for travelers to remember and can be computed with less effort by railway planners [8]. Various optimization models for railway transportation have been proposed to generate periodic timetables that minimize passenger waiting times [9–11]. Odijk [12] used a particular mathematical model to generate periodic timetables, while Liebchen [13] formulated a periodic event-scheduling problem based on a well-established graph model. Shafahi and Khani [14] presented two models with constant headway for minimizing the transfer waiting time in transit networks, and Li and Lo [15] proposed an integrated energy-efficient operation model that jointly optimizes train timetables and speed profiles, thus minimizing energy consumption. Aksu and Akyol [16] proposed a heuristic genetic algorithm (GA) that considers both the operational and transfer costs when creating timetables with homogeneous headways. Yang et al. [17] proposed a cooperative scheduling approach to optimize subway system timetables so that the recovery energy can be used directly and designed a GA with binary encoding to solve the integer-programming optimization model.Regular train schedules with a constant headway between consecutive trains reduce passenger waiting times under the condition that the passengers arrive at stations following a uniform or Poisson process [18]. However, regular train schedules may result in longer passenger traveling and waiting times under time-varying passenger transport demand (PTD). Nowadays, with the formation of URT networks, PTD is increasing. When the passenger arrival rate at URT stations is distributed unevenly, regular train schedules are not conducive to matching transport capacity with passenger flow demand, whereas irregular schedules have substantial potential to reduce the total passenger waiting time by matching the actual passenger demand. Therefore, to provide a more efficient timetable that can deal with variable passenger arrival rates, researchers have begun to focus on generating nonfixed-headway train schedules.Assis et al. [19] proposed a linear-programming model that effectively optimizes train schedules considering time-varying PTD. Guihaire and Hao [20] discussed the scheduling problem in terms of passenger satisfaction and showed that it would be preferable to obtain more detailed data for real-world PTD. Albrecht [21] proposed a multilevel optimization algorithm that produces flexible timetables for a demand-oriented service. Hassannayebi et al. [22] proposed a two-stage GA-based simulation optimization approach to minimize passenger waiting cost for a single-loop URT line, while Sun et al. [23] presented three optimization models for demand-sensitive timetables and found that a dynamic timetable built with capacity constraints offers the greatest ability to reduce the total waiting time. Niu et al. [24] considered train scheduling under time-dependent PTD and train skip-stop patterns and established a unified quadratic integer-programming model that minimizes the total passenger waiting time. Wang et al. [25] proposed an iterative convex programming approach for train scheduling based on time-varying passenger flow, allowing both the total energy consumption and passenger travel time to be minimized. Zhu et al. [26] proposed a bilevel programming model for train-timetable optimization with full consideration of PTD for a URT line. Shi et al. [27] proposed a joint optimization model for collaboratively optimizing the train timetable and passenger flow control strategy for an oversaturated URT line, and Wang et al. [28] proposed three approaches for solving a multiobjective mixed-integer nonlinear programming model to deliver both an irregular train schedule and a rolling-stock circulation plan under time-varying PTD. Xie et al. [29] established a PTD-oriented approach and stop-plan synchronization optimization model that give an energy-saving and stable timetable, whereas Huang et al. [30] developed nonlinear mixed-integer programming models to reschedule trains during disruption, with the purpose of alleviating passenger inconvenience and regaining nominal train regularity. Yin et al. [31] proposed an integrated approach for train scheduling with dynamic PTD on a bidirectional URT line to minimize operational costs and passenger waiting time. Barrena et al. [32] proposed two nonlinear programming formulations for optimizing a rapid-transit timetable under dynamic PTD, with the objective of minimizing the average passenger waiting time at stations. Canca et al. [33] presented a nonlinear integer-programming model for determining noncyclic railway timetables under dynamic PTD, while Chen et al. [34] presented an energy-saving timetable optimization model that minimizes the energy consumption of train stops and the travel time of trains. Meng et al. [35] presented an optimization model and heuristic technique for reallocating the time margins in train timetables so as to minimize train delays under operational disturbances. Barrena et al. [36] presented three linear formulations for timetabling adapted to a dynamic PTD pattern, with the objective of minimizing passenger average waiting time at stations, and developed a branch-and-cut algorithm applicable to all models. Yang et al. [37] presented an integrated biobjective optimization model to generate an irregular timetable, thus enabling the joint optimization of passenger travel time and energy consumption. Dong et al. [38] proposed an integrated optimization model that considers both train stop plans and timetables under time-dependent PTD and showed that the integrated model improved passenger travel efficiency and reduced train running times.URT has become an important part of urban public transport, offering large-volume transport at fast speeds with high levels of punctuality. Compared with other public transport methods, URT is a closed operating environment with high passenger density. Since the outbreak of COVID-19, the difficulties in controlling the spread of epidemics have increased. To reduce the risk of epidemic transmission, reducing the train loading rate is now required for epidemic normalization and control in China. In this paper, under the premise of a certain average train departure interval, the capacities of irregular trains are accurately determined via an optimized train schedule to reduce the maximum train loading rate. Previous studies of irregular train timetables have not accounted for the negative impact of unbalanced train departure intervals on passengers. If the train departure intervals are too uneven, there will be an excessive imbalance in waiting times, which will make it difficult for passengers to adapt and will increase the complexity of preparing and operating train timetables. Therefore, this paper presents an optimization model for an irregular train schedule during peak hours. The model achieves the cooperative optimization of the maximum train loading rate and equilibrium of train departure intervals, thus improving the passenger experience.The remainder of this paper is structured as follows: in Section2, the problem and related assumptions are presented, and an optimization model for minimizing the maximum train loading rate and the average deviation of train departure intervals is described. In Section 3, the solution approach for the optimization model is introduced. Section 4 evaluates the performance of the proposed model through a case study. Finally, the conclusions to this study and directions for future research are given in Section 5.


## 2. Problem Description and Model Formulation

### 2.1. Problem Description

Considering the double-track URT line shown in Figure1, I platforms are set in each direction, giving a total of 2I platforms. Both full-length and short-turn routings are used for train operations, with platform F used for the turn-back operation of short-turn routing. The train turns back before the initial station and after the tail station.Figure 1
Schematic of the track layout of a URT line.For a traditional regular train schedule, the scheduled running time and dwell time are configured to have the same values for each train. However, a fixed dwell time consumes transport capacity for stations with small passenger flows and often cannot meet the demand for boarding and alighting passengers at stations with large passenger flows, resulting in train delays. This paper correlates the train dwell time with the number of boarding and alighting passengers; see equation (5) in Section 2.5 for details.As well as the loading rate of train services, passenger satisfaction is influenced by the deviation of train departure intervals. Therefore, this paper constructs an irregular train-scheduling optimization model that jointly optimizes the maximum train loading rate and the average deviation of train departure intervals so as to match passenger demands more accurately.


### 2.2. Assumptions

Based on the practical operational situation of a URT line, the train-scheduling problem involves the following assumptions:(1)
All the service trains are of the same type and formation.(2)
Each train stops at each station, and there is no overtaking along sections or at stations.(3)
The origin-destination (O-D) matrix of passenger flow demand comes from recent Automatic Fare Collection System (AFC) data. The passenger arrival rate is obtained after sorting, screening, and other related preprocessing.(4)
After all passengers disembark at the turn-back platform, the train starts its turn-back operation.(5)
After each train completes one service in peak hours, it immediately starts the next service rather than returning to the depot.


### 2.3. Notation and Variables

Table1 lists the parameters and intermediate variables used in the model, and Table 2 lists the decision variables.Table 1
Parameters and intermediate variables.
NotationDefinitionKSet of train servicesZSet of stationsTSet of operation periodskIndex of train servicesi,r,jIndex of stationsδk,iTrain load factor between stationsi and i + 1 for train service ktk,iwDwell time at stationi for train service kβDwell-time coefficientnk,ialNumber of passengers that alight train servicek at station ink,ibNumber of passengers that board train servicek at station idiMinimal dwell time at stationitk,idDeparture time of train servicek at station itk,iaArrival time of train servicek at station iti,minrMinimal running time from stationi to station i + 1ti,maxrMaximal running time from stationi to station i + 1hi,minMinimal train departure interval at stationihi,maxMaximal train departure interval at stationitk,r1Train running time of full-length routingtr1,minMinimal train running time of full-length routingtr1,maxMaximal train running time of full-length routingtk,r2Train running time of short-turn routingtr2,minMinimal train running time of short-turn routingtr2,maxMaximal train running time of short-turn routingtr1Average train running time of full-length routingtr2Average train running time of short-turn routingNr1Number of trains for full-length routingNr2Number of trains for short-turn routingNNumber of trains availableηTrain operation proportion of full-length and short-turn routingshr1Average train departure interval of full-length routinghr2Average train departure interval of short-turn routinglktk,idNumber of passengers onboard train servicek at station i after the boarding process has completedlktk,iaNumber of passengers onboard train servicek at station i before the start of the boarding processnk,i,jbNumber of passengers onboard train servicek at station i with destination station jni,jt1,t2Number of passengers arriving at stationi with destination station j during time period t1,t2tk,icArrival time at stationi of last passenger to board train service klk,itNumber of passengers onboard train servicek at time tδmMaximum allowable train loading factorckCapacity of trains in terms of maximum number of onboard passengersnit1,t2Number of passengers arriving at stationi during time period t1,t2τi,jtPassenger arrival rate at stationi with destination station j at time tniptk,idNumber of passengers waiting at stationi after the boarding process has completed for train service k at station ini,jptk,idNumber of passengers waiting at stationi with destination station j after the boarding process has completed for train service k at station itturnback,iTrain turn-back time at reversal stationδmaxMaximum loading rate of all the trains passing through each stationtk,irRunning time from stationi to station i + 1 for train service kTable 2
Decision variables.
NotationDefinitionhk,iTrain departure interval at stationi between train services k and k + 1tk,irRunning time of train servicek from station i to station i + 1


### 2.4. Objective Function

The optimization objective is to minimize the maximum train loading rate and the average deviation in the train departure interval. The relevant equations are as follows:(1)minf=5λδmax+1−λhΔ,(2)δmax=maxδk,i,∀k∈K;∀i∈Z,(3)have=∑k=1K∑i=12Ihk,iK2I−2,(4)hΔ=∑k=1K∑i=12Ihk,i−haveK2I−2.Equation (1) is the objective function, where λ is a positive weight. In equation (2), δmax is the maximum loading rate of all the trains passing through each station. In equation (3), have is the average value of the departure intervals of all adjacent trains passing through each station. Equation (4) is the formula for the average deviation of the train departure interval.


### 2.5. Systematic Constraints

In this subsection, systematic constraints are formulated regarding train operation regulations and passenger capacity. In peak hours, the doors of a train usually open and close many times at each station because of excessive passenger flow, especially at transfer stations, resulting in delays to this and subsequent trains. The delayed train further increases the number of passengers gathered on the platform, putting additional pressure on the crew and causing potential safety hazards. Herein, the train dwell time is related to the number of passengers boarding and alighting the train at a station. The constraint on the train dwell timetk,iw is as follows:(5)tk,iw=βnk,ial+nk,ib+di,∀k∈K;∀i∈Z,which indicates that the dwell time of train servicek at station i is directly proportional to the total number of passengers boarding and alighting the train.The train running time and interval constraints are as follows:(6)tk,id=tk,ia+tk,iw,∀k∈K;∀i∈Z,(7)tk,i+1a=tk,id+tk,ir,∀k∈K;∀i∈Z,(8)tk,2I−1r=tturnback,1,∀k∈K,tk,Fr=tturnback,F,∀k∈K,tk,Ir=tturnback,I,∀k∈K,(9)ti,minr≤tk,ir≤ti,maxr∀k∈K;∀i∈Z,(10)hi,min≤hk,i≤hi,max,∀k∈K;∀i∈Z,(11)hk,i=tk+1,id−tk,id,∀k∈K;∀i∈Z,(12)tk,r1=∑i=12I−1tk,ir+tk,iw∀k∈K,(13)tr1,min≤tk,r1≤tr1,max,∀k∈K,(14)tk,r2=∑i=1Ftk,ir+tk,iw+∑i=2I−F+12I−1tk,ir+tk,iw,∀k∈K,(15)tr2,min≤tk,r2≤tr2,max,∀k∈K.Equation (6) indicates that the time at which train service k leaves station i is the time at which train service k arrives at station i plus the dwell time at station i. Equation (7) indicates that the time at which train service k arrives at station i + 1 is the time at which train service k leaves station i plus its running time in section i,i+1. Equation (8) defines the turn-back time as the train’s running time between the turn-back station and the reversal track. Equation (9) is the train’s running time constraint between stations, and Equation (10) is the train departure interval constraint. The departure interval of adjacent trains at the same station must be greater than the minimum train departure interval of the station and less than the maximum train departure interval of the station. Equation (11) is the formula for calculating the departure interval of adjacent trains at station i. Equations (12)–(15) are the running-time constraints of full-length and short-turn routings.In the following, equation (16) is the constraint for the number of trains required, and equations (17)–(19) are constraints on the average train departure interval for full-length and short-turn routings:(16)Nr1+Nr2≤N,(17)hr1=tr1Nr1,(18)hr2=tr2Nr2,(19)hr2hr1=η.The constraints in equations (20)–(28) are related to the train loading rate and passenger capacity, and when passenger demand exceeds the maximum loading capacity of the train, passengers will be unable to board the arriving train and will have to wait for subsequent trains:(20)lktk,id=lktk,ia−nk,ial+nk,ib,∀k∈K;∀i∈Z,(21)nk,ib=∑j=i+12Ink,i,jb=∑j=i+12Ini,jtk−1,i,ctk,ic,∀k∈K;∀i∈Z,(22)tk,ic=mintk,id,maxt|lk,it<δmaxck≤lk,it+nit,t+1,∀k∈K;∀i∈Z;∀t∈T,(23)nit,t+1=∑j=i+12Ini,jt,t+1,∀i∈Z;∀t∈T,(24)nit1,t2=∑j=i+12Ini,jt1,t2=∑j=i+12I∫t1t2τi,jtdt,∀i∈Z;∀t1,t2∈T,(25)nk,ial=∑r=1i−1nk,r,ib,∀k∈K;∀i∈Z,(26)niptk,id=niptk−1,id+nitk−1,id,tk,id−nk,ib=∑j=i+12Ini,jptk−1,id+ni,jtk−1,id,tk,id−nk,i,jb,∀k∈K;∀i∈Z,(27)nIptk,Id=nFptk,Fd=0,∀k∈K,(28)δk,i=lktk,idck≤δm,∀k∈K;∀i∈Z.Equation (20) indicates that the number of passengers onboard train service k at station i after the boarding process has been completed is related to the number of passengers onboard train service k when it arrives at station i and the number of passengers boarding and alighting at station i. Equation (21) is the formula for the number of passengers boarding train service k at station i. Equations (22) and (23) show that, under the condition of passenger flow saturation, only some of the passengers on the platform can board the train because of the limited train capacity; the other passengers have to wait for the next train, where tk,ic is the arrival time at station i of the last passenger to board train service k, tk,ic∈tk−1,ic,tk,id. Equation (24) indicates that the number of passengers arriving at station i is the total number of passengers starting off at station i within the corresponding time range. Equation (25) specifies that the number of passengers alighting train service k at station i comprises the number of passengers boarding at all stations prior to station i with station i as the destination. Equation (26) indicates that the number of passengers waiting at station i after the boarding process has been completed for train service k at station i is related to the number of passengers waiting at station i when the previous train left station i, the number of passengers arriving at station i before train service k departs station i, and the number of passengers boarding at station i. Equation (27) specifies that all passengers alight at turn-back platforms I and F, and no passengers board the train. Equation (28) is the constraint for the maximum loading rate of the train.


## 2.1. Problem Description

Considering the double-track URT line shown in Figure1, I platforms are set in each direction, giving a total of 2I platforms. Both full-length and short-turn routings are used for train operations, with platform F used for the turn-back operation of short-turn routing. The train turns back before the initial station and after the tail station.Figure 1
Schematic of the track layout of a URT line.For a traditional regular train schedule, the scheduled running time and dwell time are configured to have the same values for each train. However, a fixed dwell time consumes transport capacity for stations with small passenger flows and often cannot meet the demand for boarding and alighting passengers at stations with large passenger flows, resulting in train delays. This paper correlates the train dwell time with the number of boarding and alighting passengers; see equation (5) in Section 2.5 for details.As well as the loading rate of train services, passenger satisfaction is influenced by the deviation of train departure intervals. Therefore, this paper constructs an irregular train-scheduling optimization model that jointly optimizes the maximum train loading rate and the average deviation of train departure intervals so as to match passenger demands more accurately.


## 2.2. Assumptions

Based on the practical operational situation of a URT line, the train-scheduling problem involves the following assumptions:(1)
All the service trains are of the same type and formation.(2)
Each train stops at each station, and there is no overtaking along sections or at stations.(3)
The origin-destination (O-D) matrix of passenger flow demand comes from recent Automatic Fare Collection System (AFC) data. The passenger arrival rate is obtained after sorting, screening, and other related preprocessing.(4)
After all passengers disembark at the turn-back platform, the train starts its turn-back operation.(5)
After each train completes one service in peak hours, it immediately starts the next service rather than returning to the depot.


## 2.3. Notation and Variables

Table1 lists the parameters and intermediate variables used in the model, and Table 2 lists the decision variables.Table 1
Parameters and intermediate variables.
NotationDefinitionKSet of train servicesZSet of stationsTSet of operation periodskIndex of train servicesi,r,jIndex of stationsδk,iTrain load factor between stationsi and i + 1 for train service ktk,iwDwell time at stationi for train service kβDwell-time coefficientnk,ialNumber of passengers that alight train servicek at station ink,ibNumber of passengers that board train servicek at station idiMinimal dwell time at stationitk,idDeparture time of train servicek at station itk,iaArrival time of train servicek at station iti,minrMinimal running time from stationi to station i + 1ti,maxrMaximal running time from stationi to station i + 1hi,minMinimal train departure interval at stationihi,maxMaximal train departure interval at stationitk,r1Train running time of full-length routingtr1,minMinimal train running time of full-length routingtr1,maxMaximal train running time of full-length routingtk,r2Train running time of short-turn routingtr2,minMinimal train running time of short-turn routingtr2,maxMaximal train running time of short-turn routingtr1Average train running time of full-length routingtr2Average train running time of short-turn routingNr1Number of trains for full-length routingNr2Number of trains for short-turn routingNNumber of trains availableηTrain operation proportion of full-length and short-turn routingshr1Average train departure interval of full-length routinghr2Average train departure interval of short-turn routinglktk,idNumber of passengers onboard train servicek at station i after the boarding process has completedlktk,iaNumber of passengers onboard train servicek at station i before the start of the boarding processnk,i,jbNumber of passengers onboard train servicek at station i with destination station jni,jt1,t2Number of passengers arriving at stationi with destination station j during time period t1,t2tk,icArrival time at stationi of last passenger to board train service klk,itNumber of passengers onboard train servicek at time tδmMaximum allowable train loading factorckCapacity of trains in terms of maximum number of onboard passengersnit1,t2Number of passengers arriving at stationi during time period t1,t2τi,jtPassenger arrival rate at stationi with destination station j at time tniptk,idNumber of passengers waiting at stationi after the boarding process has completed for train service k at station ini,jptk,idNumber of passengers waiting at stationi with destination station j after the boarding process has completed for train service k at station itturnback,iTrain turn-back time at reversal stationδmaxMaximum loading rate of all the trains passing through each stationtk,irRunning time from stationi to station i + 1 for train service kTable 2
Decision variables.
NotationDefinitionhk,iTrain departure interval at stationi between train services k and k + 1tk,irRunning time of train servicek from station i to station i + 1


## 2.4. Objective Function

The optimization objective is to minimize the maximum train loading rate and the average deviation in the train departure interval. The relevant equations are as follows:(1)minf=5λδmax+1−λhΔ,(2)δmax=maxδk,i,∀k∈K;∀i∈Z,(3)have=∑k=1K∑i=12Ihk,iK2I−2,(4)hΔ=∑k=1K∑i=12Ihk,i−haveK2I−2.Equation (1) is the objective function, where λ is a positive weight. In equation (2), δmax is the maximum loading rate of all the trains passing through each station. In equation (3), have is the average value of the departure intervals of all adjacent trains passing through each station. Equation (4) is the formula for the average deviation of the train departure interval.


## 2.5. Systematic Constraints

In this subsection, systematic constraints are formulated regarding train operation regulations and passenger capacity. In peak hours, the doors of a train usually open and close many times at each station because of excessive passenger flow, especially at transfer stations, resulting in delays to this and subsequent trains. The delayed train further increases the number of passengers gathered on the platform, putting additional pressure on the crew and causing potential safety hazards. Herein, the train dwell time is related to the number of passengers boarding and alighting the train at a station. The constraint on the train dwell timetk,iw is as follows:(5)tk,iw=βnk,ial+nk,ib+di,∀k∈K;∀i∈Z,which indicates that the dwell time of train servicek at station i is directly proportional to the total number of passengers boarding and alighting the train.The train running time and interval constraints are as follows:(6)tk,id=tk,ia+tk,iw,∀k∈K;∀i∈Z,(7)tk,i+1a=tk,id+tk,ir,∀k∈K;∀i∈Z,(8)tk,2I−1r=tturnback,1,∀k∈K,tk,Fr=tturnback,F,∀k∈K,tk,Ir=tturnback,I,∀k∈K,(9)ti,minr≤tk,ir≤ti,maxr∀k∈K;∀i∈Z,(10)hi,min≤hk,i≤hi,max,∀k∈K;∀i∈Z,(11)hk,i=tk+1,id−tk,id,∀k∈K;∀i∈Z,(12)tk,r1=∑i=12I−1tk,ir+tk,iw∀k∈K,(13)tr1,min≤tk,r1≤tr1,max,∀k∈K,(14)tk,r2=∑i=1Ftk,ir+tk,iw+∑i=2I−F+12I−1tk,ir+tk,iw,∀k∈K,(15)tr2,min≤tk,r2≤tr2,max,∀k∈K.Equation (6) indicates that the time at which train service k leaves station i is the time at which train service k arrives at station i plus the dwell time at station i. Equation (7) indicates that the time at which train service k arrives at station i + 1 is the time at which train service k leaves station i plus its running time in section i,i+1. Equation (8) defines the turn-back time as the train’s running time between the turn-back station and the reversal track. Equation (9) is the train’s running time constraint between stations, and Equation (10) is the train departure interval constraint. The departure interval of adjacent trains at the same station must be greater than the minimum train departure interval of the station and less than the maximum train departure interval of the station. Equation (11) is the formula for calculating the departure interval of adjacent trains at station i. Equations (12)–(15) are the running-time constraints of full-length and short-turn routings.In the following, equation (16) is the constraint for the number of trains required, and equations (17)–(19) are constraints on the average train departure interval for full-length and short-turn routings:(16)Nr1+Nr2≤N,(17)hr1=tr1Nr1,(18)hr2=tr2Nr2,(19)hr2hr1=η.The constraints in equations (20)–(28) are related to the train loading rate and passenger capacity, and when passenger demand exceeds the maximum loading capacity of the train, passengers will be unable to board the arriving train and will have to wait for subsequent trains:(20)lktk,id=lktk,ia−nk,ial+nk,ib,∀k∈K;∀i∈Z,(21)nk,ib=∑j=i+12Ink,i,jb=∑j=i+12Ini,jtk−1,i,ctk,ic,∀k∈K;∀i∈Z,(22)tk,ic=mintk,id,maxt|lk,it<δmaxck≤lk,it+nit,t+1,∀k∈K;∀i∈Z;∀t∈T,(23)nit,t+1=∑j=i+12Ini,jt,t+1,∀i∈Z;∀t∈T,(24)nit1,t2=∑j=i+12Ini,jt1,t2=∑j=i+12I∫t1t2τi,jtdt,∀i∈Z;∀t1,t2∈T,(25)nk,ial=∑r=1i−1nk,r,ib,∀k∈K;∀i∈Z,(26)niptk,id=niptk−1,id+nitk−1,id,tk,id−nk,ib=∑j=i+12Ini,jptk−1,id+ni,jtk−1,id,tk,id−nk,i,jb,∀k∈K;∀i∈Z,(27)nIptk,Id=nFptk,Fd=0,∀k∈K,(28)δk,i=lktk,idck≤δm,∀k∈K;∀i∈Z.Equation (20) indicates that the number of passengers onboard train service k at station i after the boarding process has been completed is related to the number of passengers onboard train service k when it arrives at station i and the number of passengers boarding and alighting at station i. Equation (21) is the formula for the number of passengers boarding train service k at station i. Equations (22) and (23) show that, under the condition of passenger flow saturation, only some of the passengers on the platform can board the train because of the limited train capacity; the other passengers have to wait for the next train, where tk,ic is the arrival time at station i of the last passenger to board train service k, tk,ic∈tk−1,ic,tk,id. Equation (24) indicates that the number of passengers arriving at station i is the total number of passengers starting off at station i within the corresponding time range. Equation (25) specifies that the number of passengers alighting train service k at station i comprises the number of passengers boarding at all stations prior to station i with station i as the destination. Equation (26) indicates that the number of passengers waiting at station i after the boarding process has been completed for train service k at station i is related to the number of passengers waiting at station i when the previous train left station i, the number of passengers arriving at station i before train service k departs station i, and the number of passengers boarding at station i. Equation (27) specifies that all passengers alight at turn-back platforms I and F, and no passengers board the train. Equation (28) is the constraint for the maximum loading rate of the train.


## 3. Solution Approach

In essence, this problem is a large-scale combinatorial optimization problem. Simulated-annealing algorithms are effective for solving such problems, offering satisfactory solutions in a reasonable time. Herein, a heuristic simulated-annealing algorithm is designed to solve the model.


### 3.1. Simulated-Annealing Algorithm

The current regular schedule is used as the initial solution. The O-D time-varying passenger flow is distributed to each scheduled train service, and the simulated-annealing algorithm is iterated to approach the minimum value of the objective function. Figure2 shows a flowchart of the simulated-annealing algorithm. The solution steps are as follows:Step 1. We initialize the algorithm parameters, including the initial temperaturets, termination temperature te, temperature attenuation coefficient a, Markov chain length m_l, current iteration number Ite, total number of individuals M, and current solved individual m.Step 2. We take the current regular train operation schemes0 as the initial train operation scheme and calculate the initial objective function value as fs0. The current global optimal objective function value is fsmin=fs0, and the individual optimal objective function value is fs=fs0.Step 3. For individualm and the corresponding operation plan, a new operation plan snew is generated using the multineighborhood moving criterion, and the objective function value is fsnew.Step 4. Iffsnew>fs, we accept the neighborhood solution Snew according to the Metropolis criterion; if fsnew≤fs, we record the neighborhood solution Snew as the optimal solution for individual m.Step 5. If all individuals have been traversed, we select the optimal solution from theM individuals and record it as the global optimal objective value fsmin, then set m = 1; otherwise, we return to step 3 and set m = m + 1.Step 6. We sett=at. If t<te, we terminate the algorithm; otherwise, we return to step 3.Figure 2
Flowchart of the parallel-simulated-annealing algorithm.


### 3.2. Adaptive Large Neighborhood Search Metaheuristic

An adaptive large neighborhood search (ALNS) metaheuristic is now proposed to search neighboring solutions efficiently and reasonably. The operators are chosen via the roulette-wheel mechanism at each iteration, with a probability that depends on their former performance. For a detailed formulation, see equation (29), in which pi represents the probability of operator i being selected, κi represents the weight of operator i and has an initial value of 1, and Nd represents the total number of operators that can be selected.(29)pi=κi∑j=1Ndκj,∀i,j≤N.Each search process is divided into segments ofψ iterations. Each operator i is assigned a score πi, with the initial score set to 0. After each iteration, the score of the selected operator increases by c1 if a new best solution is found, increases by c2 if a solution better than the previous one but worse than the best one is found, and increases by c3 if the solution is worse than the previous one but still accepted via the simulated-annealing acceptance criterion. At the end of each segment, the weights of the selected operators are calculated by considering the scores obtained in the last ψ iterations according to(30)κi=κi,ifnij=0,1−ωκi+ωπinij,ifnij≠0,where ω represents the weight reaction index, which controls the effect of past performance, and nij represents the number of times operator i has been used in segment j. At the end of each segment, the scores of all operators are reset to 0. In the proposed implementation, the length of segment ψ is set to 100, the weight reaction index ω is set to 0.8, and c1, c2, and c3 are set to 10, 6, and 3, respectively.As the train headwayhk,i and train running time between stations tk,ir are decision variables in the proposed model, their output datasets Ohk,i and Otk,ir constitute the solution of the model. The expressions of Ohk,i and Otk,ir are of the form(31)Ohk,i=h1,1h1,2h1,3...h1,2I−1h2,1h2,2h2,3...h2,2I−1⋮⋮⋮⋱⋮hk−1,1hk−1,2hk−1,3...hk−1,2I−1,Otk,ir=t1,1rt1,2rt1,3r...t1,2I−1rt2,1rt2,2rt2,3r...t2,2I−1r⋮⋮⋮⋱⋮tk,1rtk,2rtk,3r...tk,2I−1r.As shown in equation (32), the operators Δhk,i and Δtk,ir denote the offsets of train headway and running time, respectively. The values of these operators should be small enough to guarantee that the generated neighbors are feasible solutions. Thus, each Δhk,i and Δtk,ir are randomly defined as −1, 0, or 1; OΔhk,i and OΔtk,ir are datasets of Δhk,i and Δtk,ir, respectively.(32)OΔhk,i=Δh1,1Δh1,2Δh1,3...Δh1,2I−1Δh2,1Δh2,2Δh2,3...Δh2,2I−1⋮⋮⋮⋱⋮Δhk−1,1Δhk−1,2Δhk−1,3...Δhk−1,2I−1,OΔtk,ir=Δt1,1rΔt1,2rΔt1,3r...Δt1,2I−1rΔt2,1rΔt2,2rΔt2,3r...Δt2,2I−1r⋮⋮⋮⋱⋮Δtk,1rΔtk,2rΔtk,3r...Δtk,2I−1r.A new neighborsnew is generated via equation (33). If the generated neighbor is not a feasible solution, it is ignored, and a new neighbor is generated according to the previously mentioned rules.(33)Ohk,inew=Ohk,i+OΔhk,i,Otk,irnew=Otk,ir+OΔtk,ir,


### 3.3. Solution Procedure

The detailed procedure of the simulated-annealing algorithm with the ALNS metaheuristic is as follows:(1)
Initialize: we generate a regular schedule and take it as initial solutions0 with object function value fs0.(2)
For each operator, we set weight = 1 and score = 0.(3)
smin←s←s0,t←ts.(4)
We initialize the number of individuals1←m.(5)
We initialize the number of iterations1←Ite.(6)
We select operatorsOΔhk,i and OΔtk,ir via the roulette-wheel mechanism at each iteration based on their current weights and apply the operators to solution s to generate a neighbor solution snew according to equation (33).(7)
We check the feasibility of neighbor solutionsnew according to equations (5)–(28). If the neighbor solution is not feasible, we ignore it and return to step 6 to generate a new neighbor.(8)
We calculate the object valuefsnew for neighbor solution snew.(9)
Iffsnew≤fs≤fsmin, we go to step 10; otherwise, go to step 11.(10)
smin←s←snew, we update the score for the selected operator with c1.(11)
Iffsmin≤fsnew≤fs, we go to step 12; otherwise, go to step 13.(12)
s←snew, we update the score for the selected operator with c2.(13)
Iffsnew>fs but snew is accepted by the simulated-annealing criterion, we go to step 14.(14)
s←snew, we update the score for the selected operator with c3.(15)
Ite=Ite+1,m=m+1.(16)
IfIte≤ψ, go to step 6.(17)
IfIte has reached the defined length of segment ψ (Ite>ψ), we go to step 18.(18)
We update the weights for all involved operators according to equation (30), reset score = 0 for all operators.(19)
Ifm≤M, we go to step 5.(20)
Ifm>M, we go to step 21.(21)
t←at.(22)
Ift≥te, we go to step 4.(23)
Ift<te, we go to step 24.(24)
We returnsmin and the corresponding object function value, end.


## 3.1. Simulated-Annealing Algorithm

The current regular schedule is used as the initial solution. The O-D time-varying passenger flow is distributed to each scheduled train service, and the simulated-annealing algorithm is iterated to approach the minimum value of the objective function. Figure2 shows a flowchart of the simulated-annealing algorithm. The solution steps are as follows:Step 1. We initialize the algorithm parameters, including the initial temperaturets, termination temperature te, temperature attenuation coefficient a, Markov chain length m_l, current iteration number Ite, total number of individuals M, and current solved individual m.Step 2. We take the current regular train operation schemes0 as the initial train operation scheme and calculate the initial objective function value as fs0. The current global optimal objective function value is fsmin=fs0, and the individual optimal objective function value is fs=fs0.Step 3. For individualm and the corresponding operation plan, a new operation plan snew is generated using the multineighborhood moving criterion, and the objective function value is fsnew.Step 4. Iffsnew>fs, we accept the neighborhood solution Snew according to the Metropolis criterion; if fsnew≤fs, we record the neighborhood solution Snew as the optimal solution for individual m.Step 5. If all individuals have been traversed, we select the optimal solution from theM individuals and record it as the global optimal objective value fsmin, then set m = 1; otherwise, we return to step 3 and set m = m + 1.Step 6. We sett=at. If t<te, we terminate the algorithm; otherwise, we return to step 3.Figure 2
Flowchart of the parallel-simulated-annealing algorithm.


## 3.2. Adaptive Large Neighborhood Search Metaheuristic

An adaptive large neighborhood search (ALNS) metaheuristic is now proposed to search neighboring solutions efficiently and reasonably. The operators are chosen via the roulette-wheel mechanism at each iteration, with a probability that depends on their former performance. For a detailed formulation, see equation (29), in which pi represents the probability of operator i being selected, κi represents the weight of operator i and has an initial value of 1, and Nd represents the total number of operators that can be selected.(29)pi=κi∑j=1Ndκj,∀i,j≤N.Each search process is divided into segments ofψ iterations. Each operator i is assigned a score πi, with the initial score set to 0. After each iteration, the score of the selected operator increases by c1 if a new best solution is found, increases by c2 if a solution better than the previous one but worse than the best one is found, and increases by c3 if the solution is worse than the previous one but still accepted via the simulated-annealing acceptance criterion. At the end of each segment, the weights of the selected operators are calculated by considering the scores obtained in the last ψ iterations according to(30)κi=κi,ifnij=0,1−ωκi+ωπinij,ifnij≠0,where ω represents the weight reaction index, which controls the effect of past performance, and nij represents the number of times operator i has been used in segment j. At the end of each segment, the scores of all operators are reset to 0. In the proposed implementation, the length of segment ψ is set to 100, the weight reaction index ω is set to 0.8, and c1, c2, and c3 are set to 10, 6, and 3, respectively.As the train headwayhk,i and train running time between stations tk,ir are decision variables in the proposed model, their output datasets Ohk,i and Otk,ir constitute the solution of the model. The expressions of Ohk,i and Otk,ir are of the form(31)Ohk,i=h1,1h1,2h1,3...h1,2I−1h2,1h2,2h2,3...h2,2I−1⋮⋮⋮⋱⋮hk−1,1hk−1,2hk−1,3...hk−1,2I−1,Otk,ir=t1,1rt1,2rt1,3r...t1,2I−1rt2,1rt2,2rt2,3r...t2,2I−1r⋮⋮⋮⋱⋮tk,1rtk,2rtk,3r...tk,2I−1r.As shown in equation (32), the operators Δhk,i and Δtk,ir denote the offsets of train headway and running time, respectively. The values of these operators should be small enough to guarantee that the generated neighbors are feasible solutions. Thus, each Δhk,i and Δtk,ir are randomly defined as −1, 0, or 1; OΔhk,i and OΔtk,ir are datasets of Δhk,i and Δtk,ir, respectively.(32)OΔhk,i=Δh1,1Δh1,2Δh1,3...Δh1,2I−1Δh2,1Δh2,2Δh2,3...Δh2,2I−1⋮⋮⋮⋱⋮Δhk−1,1Δhk−1,2Δhk−1,3...Δhk−1,2I−1,OΔtk,ir=Δt1,1rΔt1,2rΔt1,3r...Δt1,2I−1rΔt2,1rΔt2,2rΔt2,3r...Δt2,2I−1r⋮⋮⋮⋱⋮Δtk,1rΔtk,2rΔtk,3r...Δtk,2I−1r.A new neighborsnew is generated via equation (33). If the generated neighbor is not a feasible solution, it is ignored, and a new neighbor is generated according to the previously mentioned rules.(33)Ohk,inew=Ohk,i+OΔhk,i,Otk,irnew=Otk,ir+OΔtk,ir,


## 3.3. Solution Procedure

The detailed procedure of the simulated-annealing algorithm with the ALNS metaheuristic is as follows:(1)
Initialize: we generate a regular schedule and take it as initial solutions0 with object function value fs0.(2)
For each operator, we set weight = 1 and score = 0.(3)
smin←s←s0,t←ts.(4)
We initialize the number of individuals1←m.(5)
We initialize the number of iterations1←Ite.(6)
We select operatorsOΔhk,i and OΔtk,ir via the roulette-wheel mechanism at each iteration based on their current weights and apply the operators to solution s to generate a neighbor solution snew according to equation (33).(7)
We check the feasibility of neighbor solutionsnew according to equations (5)–(28). If the neighbor solution is not feasible, we ignore it and return to step 6 to generate a new neighbor.(8)
We calculate the object valuefsnew for neighbor solution snew.(9)
Iffsnew≤fs≤fsmin, we go to step 10; otherwise, go to step 11.(10)
smin←s←snew, we update the score for the selected operator with c1.(11)
Iffsmin≤fsnew≤fs, we go to step 12; otherwise, go to step 13.(12)
s←snew, we update the score for the selected operator with c2.(13)
Iffsnew>fs but snew is accepted by the simulated-annealing criterion, we go to step 14.(14)
s←snew, we update the score for the selected operator with c3.(15)
Ite=Ite+1,m=m+1.(16)
IfIte≤ψ, go to step 6.(17)
IfIte has reached the defined length of segment ψ (Ite>ψ), we go to step 18.(18)
We update the weights for all involved operators according to equation (30), reset score = 0 for all operators.(19)
Ifm≤M, we go to step 5.(20)
Ifm>M, we go to step 21.(21)
t←at.(22)
Ift≥te, we go to step 4.(23)
Ift<te, we go to step 24.(24)
We returnsmin and the corresponding object function value, end.


## 4. Case Study

We consider a URT line of length 45.34 km with 25 stations. In total, 50 platforms are set for the up and down directions, and platform 19 is a turn-back platform for short-turn routing. All trains are six-car marshaling type-B trains. The trains turn back before the initial station and after the tail station. Figure3 shows the passenger numbers during peak hours. Because the passenger flow on each section of the line is unbalanced, long-length and short-turn routings with a 2 : 1 train operation proportion (η = 2) are used.Figure 3
Number of passengers during peak hours.The proposed algorithm was programmed in MATLAB R2019b on a personal computer with an Intel® Core™ i3–9100 3.60 GHz CPU with 8.00 GB of memory and the Windows 10 64-bit operating system. The current regular train operation plan was used as the initial solution, with a train operation proportion of 2 : 1 for full-length and short-turn routings (η = 2). The weight coefficient of the objective function was set to λ=0.5. The average train departure interval of adjacent trains have was set to 120–170 s, i.e., a fixed value for have is taken in equation (3) as a constraint. For each given average train departure interval have, the initial temperature ts was set to 500, the termination temperature te was set to 1, the temperature attenuation coefficient a was set to 0.85, and the Markov chain length m_l was set to 1000.


### 4.1. Results and Discussion

The simulated-annealing algorithm process terminated after running for 546 s, and the algorithm converged rapidly and tended to stabilize for the optimal solution after 3800 iterations. This indicates that the convergence behavior of the algorithm is good.The minimum value of the objective functionminf=4.02 with an average train departure interval of have = 120 s gives a maximum train loading rate of δmax = 0.844 and an average deviation of hΔ = 3.82 s in the train departure interval. Table 3 presents a detailed comparison of the optimized irregular schedule and the regular schedule.Table 3
Comparison of values under an optimized irregular schedule and the current regular schedule.
Station indexLength (m)DT1 (s)DT2 (s)Gap1 (%)LR1LR2Gap3 (%)16574038−5.00.1730.171−1.2213613028−6.70.3800.375−1.338573532−8.60.5060.498−1.6414253534−2.90.5780.561−2.9516025558+5.50.8720.844−3.2617443029−3.30.8180.789−3.5711465048−4.00.8020.775−3.4810743026−13.30.7740.746−3.6913033533−5.70.7490.725−3.21015874542−6.70.6470.629−2.81111833029−3.30.6320.613−3.01210853028−6.70.6250.606−3.013874303000.5880.569−3.21411994541−8.90.6050.587−3.0158603029−3.30.5930.574−3.21610233028−6.70.5600.541−3.41714354037−7.50.5410.523−3.31819083027−10.00.4870.472−3.11969245046−8.00.6290.611−2.92017843533−5.70.5070.489−3.62133612523−8.00.4550.440−3.32218943029−3.30.4010.389−3.02315404035−12.50.3290.319−3.02458953028−6.70.1860.181−2.7254374037−7.5———SUM44158900848−5.8———In Table3, DT1 refers to the train dwell time at different stations under the regular train schedule, while DT2 refers to that under the optimized irregular train schedule. As indicated in equation (5), the train dwell time under the optimization model is related to the number of passengers boarding and alighting this train at the station. Figure 4 shows that the up-track train dwell time under the optimized irregular schedule is lower than that under the regular schedule at most stations, although the dwell time at station 5 has increased. The reason for this increase is that station 5 is a transfer station and has the largest passenger flow over the whole line (as shown in Figure 3). The current dwell time of 55 s does not meet the passengers’ needs for boarding and alighting, whereas the optimized dwell time of 58 s accurately matches passenger demand. Table 3 indicates that the total train dwell time from station 1 to station 25 decreases from 900 s to 848 s under the optimized irregular schedule, thus reducing passenger travel times and improving operational efficiency.Figure 4
Train dwell times under optimized irregular schedule and current regular schedule.We now investigate the average waiting time and average travel time of passengers under the optimized schedule. The average waiting timeTave_wait and average travel time Tave_tra are calculated according to equations (34) and (35), respectively, where Twait is the total waiting time of all passengers, Ttra_train is the total travel time of passengers within the train, and Np is the total number of passengers. As shown in equation (36), the total waiting time of passengers Twait consists of the waiting time of passengers boarding the current train and the waiting time of passengers who remain on the platform. Ttra_train and Np are calculated according to equations (37) and (38), respectively.(34)Tave_wait=TwaitNp,(35)Tave_tra=Twait+Ttra_trainNp,(36)Twait=∑k=1K∑i=12I∑j>i2I∫tk−1,idtk,idτi,jt⋅tk,id−tdt+∑k=1K∑i=12Iniptk,id⋅tk+1,id−tk,id,(37)Ttra_train=∑k=1K∑i=12I−1lktk,id⋅tk,i+1a−tk,id,(38)Np=∑k=1K∑i=12I∑j>i2I∫tk−1,idtk,idτi,jtdt.The reductions in train dwell time and running time between stations mean that the average waiting time of passengers after optimization is 2.8 s less than that before optimization, an optimization ratio of 4.3%. The average travel time of passengers after optimization is reduced by 42 s, an optimization ratio of 5.7%, which shows that the optimization model established in this paper has a positive effect on improving travel efficiency.In Table3, LR1 refers to the maximum train loading rate at different stations under the regular schedule, while LR2 refers to that under the optimized irregular schedule. Figure 5 shows that, through accurate matching of the train timetable with the passenger flow under the optimized irregular schedule, the maximum train loading rate at each station has been reduced to varying degrees compared with the current regular schedule. Table 3 illustrates that the reduction ratio of the maximum train loading rate ranges from 1.2% to 3.6%.Figure 5
Maximum train loading rate under the optimized irregular schedule and current regular schedule.According to Table3, the maximum train loading rate is 0.844 at station 5 after optimization, with an optimization ratio of 3.2% compared with that before optimization. To clarify the root cause for this optimization, Figure 6 shows the train departure intervals under both the original and optimized schedules.Figure 6
Train departure intervals under the optimized irregular schedule and current regular schedule.Forty-five trains are dispatched from station 5 under both the current regular schedule and the optimized irregular schedule in the peak hours between 07:00 and 08:30, with the same average departure interval of 120 s. As shown in Figure6, the train departure interval under the current regular schedule is fixed at 120 s, whereas it ranges from 115 to 131 s under the optimized irregular schedule. The optimized train headway is relatively dense in the middle of the peak period and relatively sparse in other periods. The optimized train departure intervals gradually decrease from 131 s to 120 s between 07:00:00 and 07:23:54 and remain below 120 s from 07:23:55 to 08:06:47, with minimum departure intervals of 115 s between 07:43:28 and 07:49:13. The optimized train departure intervals then increase from 120 s to 128 s between 08:06:48 and 08:30:00.According to the passenger flow statistics, the passenger arrival rate at each station during peak hours does not obey a uniform or Poisson distribution. The passenger arrival at station 5 is concentrated between 07:25 and 08:05, reaching a maximum at 07:48. The passenger arrival rate increases gradually before this time and decreases gradually thereafter. The changes in the train departure interval and passenger arrival rate are clearly consistent with each other under the optimized irregular schedule. Thus, it can be concluded that the basic reason for the optimization of the maximum train loading rate is that the train departure intervals decrease during the period of maximum passenger arrival, but the total number of train services does not increase.Figure7 compares the optimized irregular schedule with the regular schedule under different average departure intervals have. Under the same have, the optimized irregular schedule reduces the maximum train loading rate significantly. Compared with the regular schedule, the maximum train loading rate of the collinear and noncollinear sections decreases by 3.21%–4.82% and 2.52%–3.64%, respectively, when have is set as 120–170 s. The optimization range of the maximum train loading rate of the collinear section is slightly higher than that of the noncollinear section. This is because the passenger flow of the collinear section is higher than that of the noncollinear section, while the optimization objective is the maximum train loading rate of each section.Figure 7
Comparison of results between an optimized irregular schedule and a regular schedule.At present, train schedule no. 92 is used for daily operation, with a regular interval of 170 s, a maximum train loading rate ofδmax = 123.8%, and an average train loading rate of δave = 82.3%. The optimized irregular train schedule gives the lowest train loading rate when the average departure interval have is set to 120 s; in this case, the maximum train loading rate δmax is 84.4% and the average train loading rate δave is 53.7%, reduction ratios of 31.8% and 34.8%, respectively, compared with regular train schedule no. 92.


### 4.2. Sensitivity Analysis

#### 4.2.1. Impact of Nonnegative Weight Coefficientλ

Figures8 and 9 show that as the coefficient weight λ increases from 0 to 1.0, the maximum train loading rate δmax gradually decreases from 0.872 to 0.809, and the average deviation in the train departure interval hΔ gradually increases from 0 s to 5.173 s. This is obviously consistent with the actual situation. In particular, when λ = 0, we have minf=5λδmax+1−λhΔ=0, in which case the optimized train schedule corresponds to the regular-interval schedule with a maximum loading rate of δmax = 0.872.Figure 8
Maximum train loading rate under different weightsλ.Figure 9
Average deviation in the train departure interval under different weightsλ.


#### 4.2.2. Impact of the Average Train Departure Intervalhave

As shown in Figure7, under the optimized irregular schedule, a smaller average train departure interval have produces a smaller maximum train loading rate δmax and average deviation in the train departure interval hΔ. Therefore, compressing the train departure interval is an important means of improving passenger comfort.Table4 and Figure 7 show that when the average train departure interval have is reduced from 170 s to 120 s, the maximum train loading rate of the whole line δmax decreases from 119.7% to 84.4%, that of the noncollinear section δmax_non−co decreases from 86.6% to 61.1%, and the average deviation of the train departure interval hΔ decreases from 6.45 s to 3.82 s. Table 4 also illustrates that a shorter average train departure interval have gives a smaller average train loading rate and requires more trains. When have is reduced from 170 s to 120 s, the average train loading rate of the whole line δave decreases from 76.9% to 53.7%, that of the noncollinear section δave_non−co decreases from 57.4% to 40.5%, and the number of trains required Nrequire increases from 40 to 56. Equation (39) gives the average train loading rate of the whole line, and equation (40) gives that for the noncollinear section:(39)δave=∑k=1K∑i=12Iδk,iK2I−2,(40)δave_non−co=∑k=1K∑i=F+12I−Fδk,iK2I−2F−1.Table 4
Optimization results with 2 : 1 train operation proportion of full-length and short-turn routings.
have (s)Number of trainsNrequireNumber of trains requiredMax. loading rate (%)Average loading rate (%)hΔ (s)Full-length routingNr1Short-turn routingNr2δmaxδmax_non−coδaveδave_non−co170403010119.786.676.957.46.45165413110116.284.174.655.66.14160423210112.581.272.254.25.86155443311109.178.970.152.35.61150453411105.276.467.950.45.35145473512102.173.665.248.95.1214048361298.671.363.247.34.8313550381295.368.860.145.64.6413052391391.566.157.843.84.3312554411388.163.755.242.14.0412056421484.461.153.740.53.82


#### 4.2.3. Impact of Train Operation Proportion of Full-Length and Short-Turn Routingsη

As shown in Figure10, the proportion of full-length and short-turn routings η has a significant impact on the required number of trains Nrequire and the average train loading rate of the whole line δave. A reduction in η reduces Nrequire under the same average train departure interval but increases the average train loading rate δave. Figure 10 shows that when the average train departure interval have is 120 s and η is 2 : 1, Nrequire = 56 and δave = 53.7%, whereas when η is 1 : 1, Nrequire decreases to 53 and δave increases to 57.7%.Figure 10
Optimization results for an irregular schedule with different train operation proportions.Under an average train departure intervalhave of 120 s, when the train operation proportion of full-length and short-turn routings η is reduced from 2 : 1 to 1 : 1, the average train loading rate at noncollinear sections δave_non−co increases from 40.5% to 54.2%, and the maximum train loading rate at noncollinear sections δmax_non−co increases from 61.1% to 81.5%. Therefore, compared with η = 2 : 1, η = 1 : 1 improves the equilibrium of the train loading rate between collinear and noncollinear sections. If η is reduced further (e.g., 1 : 2), the maximum train loading rate at noncollinear sections δmax_non−co becomes too high and passenger comfort is affected, which is not recommended.The previously mentioned sensitivity analysis results are consistent with expectations, which proves that the model in this paper has good usability and reliability, and can be applied to URT train schedule optimization.


## 4.1. Results and Discussion

The simulated-annealing algorithm process terminated after running for 546 s, and the algorithm converged rapidly and tended to stabilize for the optimal solution after 3800 iterations. This indicates that the convergence behavior of the algorithm is good.The minimum value of the objective functionminf=4.02 with an average train departure interval of have = 120 s gives a maximum train loading rate of δmax = 0.844 and an average deviation of hΔ = 3.82 s in the train departure interval. Table 3 presents a detailed comparison of the optimized irregular schedule and the regular schedule.Table 3
Comparison of values under an optimized irregular schedule and the current regular schedule.
Station indexLength (m)DT1 (s)DT2 (s)Gap1 (%)LR1LR2Gap3 (%)16574038−5.00.1730.171−1.2213613028−6.70.3800.375−1.338573532−8.60.5060.498−1.6414253534−2.90.5780.561−2.9516025558+5.50.8720.844−3.2617443029−3.30.8180.789−3.5711465048−4.00.8020.775−3.4810743026−13.30.7740.746−3.6913033533−5.70.7490.725−3.21015874542−6.70.6470.629−2.81111833029−3.30.6320.613−3.01210853028−6.70.6250.606−3.013874303000.5880.569−3.21411994541−8.90.6050.587−3.0158603029−3.30.5930.574−3.21610233028−6.70.5600.541−3.41714354037−7.50.5410.523−3.31819083027−10.00.4870.472−3.11969245046−8.00.6290.611−2.92017843533−5.70.5070.489−3.62133612523−8.00.4550.440−3.32218943029−3.30.4010.389−3.02315404035−12.50.3290.319−3.02458953028−6.70.1860.181−2.7254374037−7.5———SUM44158900848−5.8———In Table3, DT1 refers to the train dwell time at different stations under the regular train schedule, while DT2 refers to that under the optimized irregular train schedule. As indicated in equation (5), the train dwell time under the optimization model is related to the number of passengers boarding and alighting this train at the station. Figure 4 shows that the up-track train dwell time under the optimized irregular schedule is lower than that under the regular schedule at most stations, although the dwell time at station 5 has increased. The reason for this increase is that station 5 is a transfer station and has the largest passenger flow over the whole line (as shown in Figure 3). The current dwell time of 55 s does not meet the passengers’ needs for boarding and alighting, whereas the optimized dwell time of 58 s accurately matches passenger demand. Table 3 indicates that the total train dwell time from station 1 to station 25 decreases from 900 s to 848 s under the optimized irregular schedule, thus reducing passenger travel times and improving operational efficiency.Figure 4
Train dwell times under optimized irregular schedule and current regular schedule.We now investigate the average waiting time and average travel time of passengers under the optimized schedule. The average waiting timeTave_wait and average travel time Tave_tra are calculated according to equations (34) and (35), respectively, where Twait is the total waiting time of all passengers, Ttra_train is the total travel time of passengers within the train, and Np is the total number of passengers. As shown in equation (36), the total waiting time of passengers Twait consists of the waiting time of passengers boarding the current train and the waiting time of passengers who remain on the platform. Ttra_train and Np are calculated according to equations (37) and (38), respectively.(34)Tave_wait=TwaitNp,(35)Tave_tra=Twait+Ttra_trainNp,(36)Twait=∑k=1K∑i=12I∑j>i2I∫tk−1,idtk,idτi,jt⋅tk,id−tdt+∑k=1K∑i=12Iniptk,id⋅tk+1,id−tk,id,(37)Ttra_train=∑k=1K∑i=12I−1lktk,id⋅tk,i+1a−tk,id,(38)Np=∑k=1K∑i=12I∑j>i2I∫tk−1,idtk,idτi,jtdt.The reductions in train dwell time and running time between stations mean that the average waiting time of passengers after optimization is 2.8 s less than that before optimization, an optimization ratio of 4.3%. The average travel time of passengers after optimization is reduced by 42 s, an optimization ratio of 5.7%, which shows that the optimization model established in this paper has a positive effect on improving travel efficiency.In Table3, LR1 refers to the maximum train loading rate at different stations under the regular schedule, while LR2 refers to that under the optimized irregular schedule. Figure 5 shows that, through accurate matching of the train timetable with the passenger flow under the optimized irregular schedule, the maximum train loading rate at each station has been reduced to varying degrees compared with the current regular schedule. Table 3 illustrates that the reduction ratio of the maximum train loading rate ranges from 1.2% to 3.6%.Figure 5
Maximum train loading rate under the optimized irregular schedule and current regular schedule.According to Table3, the maximum train loading rate is 0.844 at station 5 after optimization, with an optimization ratio of 3.2% compared with that before optimization. To clarify the root cause for this optimization, Figure 6 shows the train departure intervals under both the original and optimized schedules.Figure 6
Train departure intervals under the optimized irregular schedule and current regular schedule.Forty-five trains are dispatched from station 5 under both the current regular schedule and the optimized irregular schedule in the peak hours between 07:00 and 08:30, with the same average departure interval of 120 s. As shown in Figure6, the train departure interval under the current regular schedule is fixed at 120 s, whereas it ranges from 115 to 131 s under the optimized irregular schedule. The optimized train headway is relatively dense in the middle of the peak period and relatively sparse in other periods. The optimized train departure intervals gradually decrease from 131 s to 120 s between 07:00:00 and 07:23:54 and remain below 120 s from 07:23:55 to 08:06:47, with minimum departure intervals of 115 s between 07:43:28 and 07:49:13. The optimized train departure intervals then increase from 120 s to 128 s between 08:06:48 and 08:30:00.According to the passenger flow statistics, the passenger arrival rate at each station during peak hours does not obey a uniform or Poisson distribution. The passenger arrival at station 5 is concentrated between 07:25 and 08:05, reaching a maximum at 07:48. The passenger arrival rate increases gradually before this time and decreases gradually thereafter. The changes in the train departure interval and passenger arrival rate are clearly consistent with each other under the optimized irregular schedule. Thus, it can be concluded that the basic reason for the optimization of the maximum train loading rate is that the train departure intervals decrease during the period of maximum passenger arrival, but the total number of train services does not increase.Figure7 compares the optimized irregular schedule with the regular schedule under different average departure intervals have. Under the same have, the optimized irregular schedule reduces the maximum train loading rate significantly. Compared with the regular schedule, the maximum train loading rate of the collinear and noncollinear sections decreases by 3.21%–4.82% and 2.52%–3.64%, respectively, when have is set as 120–170 s. The optimization range of the maximum train loading rate of the collinear section is slightly higher than that of the noncollinear section. This is because the passenger flow of the collinear section is higher than that of the noncollinear section, while the optimization objective is the maximum train loading rate of each section.Figure 7
Comparison of results between an optimized irregular schedule and a regular schedule.At present, train schedule no. 92 is used for daily operation, with a regular interval of 170 s, a maximum train loading rate ofδmax = 123.8%, and an average train loading rate of δave = 82.3%. The optimized irregular train schedule gives the lowest train loading rate when the average departure interval have is set to 120 s; in this case, the maximum train loading rate δmax is 84.4% and the average train loading rate δave is 53.7%, reduction ratios of 31.8% and 34.8%, respectively, compared with regular train schedule no. 92.


## 4.2. Sensitivity Analysis

### 4.2.1. Impact of Nonnegative Weight Coefficientλ

Figures8 and 9 show that as the coefficient weight λ increases from 0 to 1.0, the maximum train loading rate δmax gradually decreases from 0.872 to 0.809, and the average deviation in the train departure interval hΔ gradually increases from 0 s to 5.173 s. This is obviously consistent with the actual situation. In particular, when λ = 0, we have minf=5λδmax+1−λhΔ=0, in which case the optimized train schedule corresponds to the regular-interval schedule with a maximum loading rate of δmax = 0.872.Figure 8
Maximum train loading rate under different weightsλ.Figure 9
Average deviation in the train departure interval under different weightsλ.


### 4.2.2. Impact of the Average Train Departure Intervalhave

As shown in Figure7, under the optimized irregular schedule, a smaller average train departure interval have produces a smaller maximum train loading rate δmax and average deviation in the train departure interval hΔ. Therefore, compressing the train departure interval is an important means of improving passenger comfort.Table4 and Figure 7 show that when the average train departure interval have is reduced from 170 s to 120 s, the maximum train loading rate of the whole line δmax decreases from 119.7% to 84.4%, that of the noncollinear section δmax_non−co decreases from 86.6% to 61.1%, and the average deviation of the train departure interval hΔ decreases from 6.45 s to 3.82 s. Table 4 also illustrates that a shorter average train departure interval have gives a smaller average train loading rate and requires more trains. When have is reduced from 170 s to 120 s, the average train loading rate of the whole line δave decreases from 76.9% to 53.7%, that of the noncollinear section δave_non−co decreases from 57.4% to 40.5%, and the number of trains required Nrequire increases from 40 to 56. Equation (39) gives the average train loading rate of the whole line, and equation (40) gives that for the noncollinear section:(39)δave=∑k=1K∑i=12Iδk,iK2I−2,(40)δave_non−co=∑k=1K∑i=F+12I−Fδk,iK2I−2F−1.Table 4
Optimization results with 2 : 1 train operation proportion of full-length and short-turn routings.
have (s)Number of trainsNrequireNumber of trains requiredMax. loading rate (%)Average loading rate (%)hΔ (s)Full-length routingNr1Short-turn routingNr2δmaxδmax_non−coδaveδave_non−co170403010119.786.676.957.46.45165413110116.284.174.655.66.14160423210112.581.272.254.25.86155443311109.178.970.152.35.61150453411105.276.467.950.45.35145473512102.173.665.248.95.1214048361298.671.363.247.34.8313550381295.368.860.145.64.6413052391391.566.157.843.84.3312554411388.163.755.242.14.0412056421484.461.153.740.53.82


### 4.2.3. Impact of Train Operation Proportion of Full-Length and Short-Turn Routingsη

As shown in Figure10, the proportion of full-length and short-turn routings η has a significant impact on the required number of trains Nrequire and the average train loading rate of the whole line δave. A reduction in η reduces Nrequire under the same average train departure interval but increases the average train loading rate δave. Figure 10 shows that when the average train departure interval have is 120 s and η is 2 : 1, Nrequire = 56 and δave = 53.7%, whereas when η is 1 : 1, Nrequire decreases to 53 and δave increases to 57.7%.Figure 10
Optimization results for an irregular schedule with different train operation proportions.Under an average train departure intervalhave of 120 s, when the train operation proportion of full-length and short-turn routings η is reduced from 2 : 1 to 1 : 1, the average train loading rate at noncollinear sections δave_non−co increases from 40.5% to 54.2%, and the maximum train loading rate at noncollinear sections δmax_non−co increases from 61.1% to 81.5%. Therefore, compared with η = 2 : 1, η = 1 : 1 improves the equilibrium of the train loading rate between collinear and noncollinear sections. If η is reduced further (e.g., 1 : 2), the maximum train loading rate at noncollinear sections δmax_non−co becomes too high and passenger comfort is affected, which is not recommended.The previously mentioned sensitivity analysis results are consistent with expectations, which proves that the model in this paper has good usability and reliability, and can be applied to URT train schedule optimization.


## 4.2.1. Impact of Nonnegative Weight Coefficientλ

Figures8 and 9 show that as the coefficient weight λ increases from 0 to 1.0, the maximum train loading rate δmax gradually decreases from 0.872 to 0.809, and the average deviation in the train departure interval hΔ gradually increases from 0 s to 5.173 s. This is obviously consistent with the actual situation. In particular, when λ = 0, we have minf=5λδmax+1−λhΔ=0, in which case the optimized train schedule corresponds to the regular-interval schedule with a maximum loading rate of δmax = 0.872.Figure 8
Maximum train loading rate under different weightsλ.Figure 9
Average deviation in the train departure interval under different weightsλ.


## 4.2.2. Impact of the Average Train Departure Intervalhave

As shown in Figure7, under the optimized irregular schedule, a smaller average train departure interval have produces a smaller maximum train loading rate δmax and average deviation in the train departure interval hΔ. Therefore, compressing the train departure interval is an important means of improving passenger comfort.Table4 and Figure 7 show that when the average train departure interval have is reduced from 170 s to 120 s, the maximum train loading rate of the whole line δmax decreases from 119.7% to 84.4%, that of the noncollinear section δmax_non−co decreases from 86.6% to 61.1%, and the average deviation of the train departure interval hΔ decreases from 6.45 s to 3.82 s. Table 4 also illustrates that a shorter average train departure interval have gives a smaller average train loading rate and requires more trains. When have is reduced from 170 s to 120 s, the average train loading rate of the whole line δave decreases from 76.9% to 53.7%, that of the noncollinear section δave_non−co decreases from 57.4% to 40.5%, and the number of trains required Nrequire increases from 40 to 56. Equation (39) gives the average train loading rate of the whole line, and equation (40) gives that for the noncollinear section:(39)δave=∑k=1K∑i=12Iδk,iK2I−2,(40)δave_non−co=∑k=1K∑i=F+12I−Fδk,iK2I−2F−1.Table 4
Optimization results with 2 : 1 train operation proportion of full-length and short-turn routings.
have (s)Number of trainsNrequireNumber of trains requiredMax. loading rate (%)Average loading rate (%)hΔ (s)Full-length routingNr1Short-turn routingNr2δmaxδmax_non−coδaveδave_non−co170403010119.786.676.957.46.45165413110116.284.174.655.66.14160423210112.581.272.254.25.86155443311109.178.970.152.35.61150453411105.276.467.950.45.35145473512102.173.665.248.95.1214048361298.671.363.247.34.8313550381295.368.860.145.64.6413052391391.566.157.843.84.3312554411388.163.755.242.14.0412056421484.461.153.740.53.82


## 4.2.3. Impact of Train Operation Proportion of Full-Length and Short-Turn Routingsη

As shown in Figure10, the proportion of full-length and short-turn routings η has a significant impact on the required number of trains Nrequire and the average train loading rate of the whole line δave. A reduction in η reduces Nrequire under the same average train departure interval but increases the average train loading rate δave. Figure 10 shows that when the average train departure interval have is 120 s and η is 2 : 1, Nrequire = 56 and δave = 53.7%, whereas when η is 1 : 1, Nrequire decreases to 53 and δave increases to 57.7%.Figure 10
Optimization results for an irregular schedule with different train operation proportions.Under an average train departure intervalhave of 120 s, when the train operation proportion of full-length and short-turn routings η is reduced from 2 : 1 to 1 : 1, the average train loading rate at noncollinear sections δave_non−co increases from 40.5% to 54.2%, and the maximum train loading rate at noncollinear sections δmax_non−co increases from 61.1% to 81.5%. Therefore, compared with η = 2 : 1, η = 1 : 1 improves the equilibrium of the train loading rate between collinear and noncollinear sections. If η is reduced further (e.g., 1 : 2), the maximum train loading rate at noncollinear sections δmax_non−co becomes too high and passenger comfort is affected, which is not recommended.The previously mentioned sensitivity analysis results are consistent with expectations, which proves that the model in this paper has good usability and reliability, and can be applied to URT train schedule optimization.


## 5. Conclusions and Future Research

Taking the maximum train loading rate and average deviation in the departure interval as the cooperative optimization objectives, this paper has established an optimization model for an irregular train schedule that operates over peak hours to improve the passenger experience. A case study showed that, under the optimized irregular schedule, the train capacity can be better matched with the passenger flow. The minimum value of the objective function is obtained with an average train departure interval of 120 s. The total train dwell time from stations 1–25 decreases from 900 s under the existing regular schedule to 848 s under the optimized irregular schedule, and the maximum train loading rate decreases by 1.2%–3.6% at the various stations. Compared with the regular schedule, the maximum train loading rate of the collinear and noncollinear sections decreases by 3.21%–4.82% and 2.52%–3.64%, respectively, whenhave is set as 120–170 s.Sensitivity analysis was considered for the nonnegative weight coefficientλ, average train departure interval have, and proportion of full-length and short-turn routings η. Increasing λ from 0 to 1.0 produces a gradual decrease in δmax from 0.872 to 0.809, while hΔ gradually increases from 0 s to 5.173 s. When have is reduced from 170 s to 120 s, the maximum train loading rate decreases from 119.7% to 84.4%, the average train loading rate decreases from 76.9% to 53.7%, and the average deviation in the train departure interval decreases from 6.45 s to 3.82 s. The proportion of full-length and short-turn routings η has a significant impact on the number of trains required and the equilibrium of the train loading rate. Reducing η from 2 : 1 to 1 : 1 reduces the number of trains required by three for have = 120 s and improves the equilibrium of the train loading rate between collinear and noncollinear sections to make the capacity configuration more reasonable.The research object in this study was train-scheduling optimization for URT. It was assumed that all trains enter the next service after completing their turn-back operation, without considering the situation of trains entering and leaving the depot. To consider train scheduling for the whole day, it will be necessary to consider the train connection plan and carry out collaborative optimization of the train schedule and turnover plan.



---

*Source: 9604362-2022-12-17.xml*