# Synchronous Optimization for Demand-Driven Train Operation Plan in Rail Transit Network Using Nondominated Sorting Coevolutionary Memetic Algorithm

Authors: Zhenyu Han; Dewei Li; Baoming Han; Han Gao
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

In many cities and regions, decision makers independently develop Train Operation Plan (TOP) for each line in the rail transit network, resulting in a lack of TOP Synchronization (TOPS). Considering the entire network as a whole, researchers have realized that synchronous optimization is of great significance. In this paper, we formulate two Mixed-Integer Linear Programming (MILP) models to optimize demand-driven TOP in the network. The former is an Asynchronous TOP Optimization (ATOPO) model, while the latter is a Synchronous TOP Optimization (STOPO) model. The bi-objective models simultaneously determine train frequency, train timetable, and rolling stock circulation under small-granularity passenger demand to minimize trains’ total cost and passengers’ total time. Then, we propose the Nondominated Sorting Coevolutionary Memetic Algorithm (NSCMA) to solve the combinatorial optimization problems. The hybrid heuristic algorithm incorporates Coevolutionary Memetic Algorithm (CMA) into Advanced and Adaptive Nondominated Sorting Genetic Algorithm II (AANSGA-II) to ameliorate the evolution process for elite individuals. On this basis, we study the case of Shenyang Metro to verify the models and the algorithm. The results demonstrate that the STOPO model is better than the ATOPO model in reducing trains’ total cost and passengers’ total time. In addition, NSCMA is better than AANSGA-II in obtaining elite individuals.


---

## Body

## 1. Introduction

As carbon emissions become a global issue, governments have paid more and more attention to energy consumption [1]. In recent decades, rail transit has developed rapidly around the world as an environmentally friendly mode of public transport. The rail transit systems in many cities and regions have entered the network era. However, lines in most networks are connected only by transfer stations, and trains on most lines are organized independently.Since researchers know the independence of lines, ATOPO has become a hot issue. In these problems, lines are separated from the network, and TOPs are separately optimized for each line. Several studies have made significant progresses on demand-driven ATOPO problems [2–11]. These studies considered nontransfer passengers but omitted transfer passengers. Therefore, the asynchronously optimized TOPs are probably optimal for nontransfer passengers but probably not optimal for transfer passengers.Since researchers understand the importance of transfer passengers, TOPS has become another hot issue. In these problems, transfer stations are separated from the network, and TOPs are synchronized for the network. Several studies have made many contributions to TOPS problems. Wong et al. [12] combined a heuristic algorithm with CPLEX to solve a TOPS model aiming at minimizing passengers’ transfer waiting time. Wu et al. [13] presented a TOPS model to minimize the maximal transfer waiting time while limiting passengers’ transfer waiting time equitably over any transfer station. Guo et al. [14] constructed a TOPS model to maximize the number of transfer synchronization events for the transitional period (from peak to off-peak hours or vice versa). A hybrid heuristic algorithm combined particle swarm optimization with simulated annealing to obtain near-optimal solutions efficiently. Liu et al. [15] built a TOPS model for minimizing passengers’ transfer waiting time. Tian and Niu [16] developed a TOPS model to minimize passengers’ transfer waiting time and maximize the number of connections. A novel sequential search algorithm solved the bi-objective model. Cao et al. [17] proposed a Genetic Algorithm (GA for short) with a Local Search (LS for short) strategy to solve a TOPS model by maximizing the number of connections. These studies considered transfer passengers but omitted nontransfer passengers. Therefore, the synchronized TOPs are probably optimal for transfer passengers but probably not optimal for nontransfer passengers.Since researchers realize the importance of all passengers, STOPO has become an acknowledged challenge. STOPO overcomes the drawbacks of ATOPO and TOPS. In these problems, the network is seen as a whole, and TOPs are simultaneously optimized for the network. Several studies have made some attempts at STOPO problems. Niu et al. [18] presented a demand-driven STOPO model aimed at minimizing passengers’ waiting time and crowding disutility. Robenek et al. [19] constructed a demand-driven STOPO model to maximize companies’ profit and passengers’ satisfaction. Shang et al. [20] built a demand-driven STOPO model for minimizing passengers’ travel time. Wang et al. [21] developed a demand-driven STOPO model to minimize passengers’ waiting time and the number of passengers with failed transfers. Han et al. [22] formulated a demand-driven STOPO model to minimize trains’ operation cost and passengers’ total time. AANSGA-II obtained an approximate Pareto Optimal Solution Set (POSS for short) efficiently. These studies considered train formation, train frequency, and train timetable but omitted rolling stock circulation. Therefore, the synchronously optimized TOPs lack practicality.This paper focuses on an integrated demand-driven TOP Optimization (TOPO for short) problem in the rail transit network. Two bi-objective MILP models called the ATOPO model and the STOPO model simultaneously determine train frequency, train timetable, and rolling stock circulation under small-granularity passenger demand to minimize trains’ total cost and passengers’ total time. A hybrid heuristic algorithm called NSCMA efficiently solves the bi-objective problem by ameliorating the evolution process for elite individuals based on AANSGA-II. A case study of Shenyang Metro verifies that the STOPO model is better than the ATOPO model and that NSCMA is better than AANSGA-II.This paper is organized as follows: Section2 states the demand-driven TOPO problem. Section 3 formulates the ATOPO and STOPO models. Section 4 proposes NSCMA. Section 5 studies the case of Shenyang Metro. Section 6 presents the conclusions.


## 2. Problem Statement

We focus on a network formed by a set of bidirectional linesSl1,2,⋯,L. Each line l∈Sl contains a set of stations Sil1,2,⋯,Il,⋯,2Il and a set of transfer stations Sjl1,2,⋯,Jl,⋯,2Jl, as illustrated in Figure 1. Each physical station on line l refers to il and 2Il+1−il in both directions, and each physical transfer station on line l refers to jl and 2Jl+1−jl in both directions.Figure 1
Sketch map of each line.We use stationijl to reindex transfer station jl. Each transfer station jl∈Sjl refers to station ijl∈Sil. On this basis, the set of transfer stations Sjl1,2,⋯,Jl,⋯,2Jl corresponds to a set of stations Sli0i1,i2,⋯,iJl,⋯,i2Jl. Binary parameter qjj′ll′ equals to one if transfer corridor jl,jl′′ is valid.We schedule a set of trainsSkl1,2,⋯,Kl0,⋯,Kl with capacity cl on each line l∈Sl. Limited by the maximum transport capacity, at most Kl trains run on line l with headways of at least hminl. Required by the minimum service level, at least Kl0 trains run on line l with headways of at most hmaxl. Each active train kl∈Skl on line l runs from station 1 to station 2Il. We preset dwell time djl (at transfer station jl), travel time eil (from station 1 to station il), the earliest departure time gminlk and the latest departure time gmaxlk of each train, essential cycle time el0 (on line l) of each connection as well as transfer walking time fjj′ll′ (in transfer corridor jl,jl′′) of each transfer passenger.Assumption 1.
We assume that no line adopts overtaking, skip-stop, cross-line, multi-routing, and multi-marshalling strategies.
We construct a set of time slicesStlTl0,Tl0+1,⋯,Tl (also known as a set of time points) with length τ to express the time period of line l. Combining the time periods of all lines, the time period of the network is expressed as StT0,T0+1,⋯,T. Notably, the time periods of all stations on line l are normalized. The normalization of time periods reduces the dimension of variables effectively [22].
We describe dynamic passenger demand as small-granularity cumulative number of arriving passengerspitl (at station il at time t), alighting ratio of loaded passengers aitl (at station il at time t) and transferring ratio of alighting passengers ojj′tll′ (to transfer corridor jl,jl′′ at time t). The data are processed from small-granularity origin-destination matrices for simplicity [22].Assumption 2.
We assume that passengers from the outside arrive evenly during each time slice.
We design three binary variables and three integer variables for the demand-driven TOPO problem, as represented in formulas (1)–(6). Binary variable xktl equals to one if train kl departs at time t. Binary variable wkk′l equals to one if train kl connects train kl′. Binary variable yjj′ktll′ equals to one if transfer passengers in transfer corridor jl,jl′′ from train kl arrive at time t. Integer variable uikl indicates the number of loaded passengers on train kl in section il,il+1. Integer variable bitl denotes the number of boarding passengers at station il at time t. Integer variable vjj′tll′ represents the number of transfer passengers in transfer corridor jl,jl′′ at time t.(1)xktl∈0,1,∀l∈Sl,∀kl∈Skl,∀t∈Stl,(2)wkk′l∈0,1,∀l∈Sl,∀kl∈Skl,∀kl′∈Skl,(3)yjj′ktll′∈0,1,∀l∈Sl,∀l′∈Sl,∀jl∈Sjl,∀jl′′∈Sjl′,∀kl∈Skl,∀t∈St,(4)uikl∈N,∀l∈Sl,∀il∈Sil,∀kl∈Skl,(5)bitl∈N,∀l∈Sl,∀il∈Sil,∀t∈Stl,(6)vjj′tll′∈N,∀l∈Sl,∀l′∈Sl,∀jl∈Sjl,∀jl′′∈Sjl′,∀t∈St.


## 3. Mathematical Models

### 3.1. Asynchronous Train Operation Plan Optimization Model

The ATOPO model separately optimizes the TOP for each line in the network. It is formulated as a MILP model. Although binary variables are more than integer variables in formulating the same problem, the MILP model is linear without processing [23].


#### 3.1.1. Objective Function

The ATOPO model aims to minimize generalized costZl of line l for companies and passengers in (7). On the one hand, we select trains’ total cost ZTTCl to express companies’ cost of line l. On the other hand, we select passengers’ total time ZPTTl under weight μ to represent passengers’ cost of line l.(7)minZl=ZTTCl+μ∗ZPTTl,∀l∈Sl.Trains’ total costZTTCl of line l includes trains’ operation cost ZTOCl and trains’ depreciation cost ZTDCl, as represented in (8).(8)ZTTCl=ZTOCl+ZTDCl,∀l∈Sl.Trains’ operation costZTOCl of line l equals to unit operation cost ml multiplied by the number of trains, as shown in (9). The number of trains on line l is accumulated by binary variable xktl.(9)ZTOCl=∑kl∈Skl∑t∈Stlml∗xktl,∀l∈Sl.Trains’ depreciation costZTDCl of line l equals to unit depreciation cost ml0 multiplied by the number of rolling stocks, as displayed in (10). The number of rolling stocks on line l equals to the number of trains minus the number of connections. The number of connections on line l is accumulated by binary variable wkk′l.(10)ZTDCl=∑kl∈Skl∑t∈Stlml0∗xktl−∑kl∈Skl∑kl′∈Sklml0∗wkk′l,∀l∈Sl.Passengers’ total timeZPTTl of line l includes passengers’ waiting time ZPWTl and passengers’ penalty time ZPPTl, as represented in (11).(11)ZPTTl=ZPWTl+ZPPTl,∀l∈Sl.Passengers’ waiting timeZPWTl of line l consists of passengers’ basic waiting time and passengers’ additional waiting time, as shown in (12). Passengers’ basic waiting time of line l equals to half τ multiplied by the number of arriving passengers from the outside. Passengers’ additional waiting time of line l equals to τ multiplied by the number of waiting passengers.(12)ZPWTl=τ∗12∑il∈SilpiTl+∑il∈Sil∑t=Tl0Tl−1pitl−∑il∈Sil∑t=Tl0Tl−1∑t′=Tl0tbit′l,∀l∈Sl.Passengers’ penalty timeZPPTl of line l equals to unit penalty time ε multiplied by the number of finally stranded passengers, as displayed in (13).(13)ZPPTl=ε∗∑il∈SilpiTl−∑il∈Sil∑t∈Stlbitl,∀l∈Sl.


#### 3.1.2. Constraints

The ATOPO model is subject to train constraints, connection constraints, and passenger constraints.(1) Train Constraints. Train constraints stipulate the uniqueness, priority, departure time, and headway of each train, as well as the number of trains.Constraints (14) and (15) specify the uniqueness of each train. Each time point can only correspond to at most one active train. Meanwhile, each train can only correspond to at most one time point.(14)∑kl∈Sklxktl≤1,∀l∈Sl,∀t∈Stl,(15)∑t∈Stlxktl≤1,∀l∈Sl,∀kl∈Skl.Constraint (16) states the priority of each train. A train should be inactive if the previous train is inactive.(16)∑t∈Stlxktl≤∑t∈Stlxk−1,tl,∀l∈Sl,∀kl∈Skl\1.Constraints (17) and (18) limit that the departure time of each active train should be between gminlk and gmaxlk.(17)∑t∈Stlt∗xktl≥gminlkτ∗∑t∈Stlxktl,∀l∈Sl,∀kl∈Skl,(18)∑t∈Stlt∗xktl≤gmaxlkτ∗∑t∈Stlxktl,∀l∈Sl,∀kl∈Skl.Constraints (19) and (20) limit that the headway of each active train should be between hminl and hmaxl.(19)∑t∈Stlt∗xktl−∑t∈Stlt∗xk−1,tl≥hminlτ−2Tl∗1−∑t∈Stlxktl,∀l∈Sl,∀kl∈Skl\1,(20)∑t∈Stlt∗xktl−∑t∈Stlt∗xk−1,tl≤hmaxlτ+2Tl∗1−∑t∈Stlxktl,∀l∈Sl,∀kl∈Skl\1.Constraints (21) and (22) limit that the number of trains should be between Kl0 and Kl.(21)∑kl∈Skl∑t∈Stlxktl≥Kl0,∀l∈Sl,(22)∑kl∈Skl∑t∈Stlxktl≤Kl,∀l∈Sl.(2) Connection Constraints. Connection constraints stipulate the uniqueness and cycle time of each connection.Constraints (23) and (24) clarify the uniqueness of each connection. Each active train can only connect at most one active train. Meanwhile, each active train can only be connected by at most one active train.(23)∑kl′∈Sklwkk′l≤∑t∈Stlxktl,∀l∈Sl,∀kl∈Skl,(24)∑kl′∈Sklwk′kl≤∑t∈Stlxktl,∀l∈Sl,∀kl∈Skl.Constraint (25) claims that the cycle time of each connection should be at least el0.(25)∑t∈Stlt∗xktl−∑t∈Stlt∗xk′tl≥el0τ−2Tl∗1−wkk′l,∀l∈Sl,∀kl∈Skl,∀kl′∈Skl.(3) Passenger Constraints. Passenger constraints stipulate the number of loaded and boarding passengers.Constraint (26) limits that the number of loaded passengers should not exceed cl if the train is active and equals to zero otherwise.(26)uikl≤cl∗∑t∈Stlxktl,∀l∈Sl,∀il∈Sil,∀kl∈Skl.Constraint (27) limits that the number of boarding passengers should not exceed cl if an active train departs at the time point and equals to zero otherwise.(27)bitl≤cl∗∑kl∈Sklxktl,∀l∈Sl,∀il∈Sil,∀t∈Stl.Constraints (28)–(31) declare the quantitative relationship between loaded passengers and boarding passengers. Constraints (28) and (29) are only for station 1, while Constraints (30) and (31) are only for the other stations. The number of loaded passengers should correspond to the number of boarding passengers and the number of alighting passengers. The number of alighting passengers should be equal to the alighting ratio multiplied by the number of loaded passengers.(28)u1kl≥b1tl−cl∗1−xktl,∀l∈Sl,∀kl∈Sil,∀t∈Stl,(29)u1kl≤b1tl+cl∗1−xktl,∀l∈Sl,∀kl∈Sil,∀t∈Stl,(30)uikl≥bitl+ui−1,kl∗1−aitl−cl∗1−xktl,∀l∈Sl,∀il∈Skl\1,∀kl∈Skl,∀t∈Stl,(31)uikl≤bitl+ui−1,kl∗1−aitl+cl∗1−xktl,∀l∈Sl,∀il∈Skl\1,∀kl∈Skl,∀t∈Stl.Constraint (32) specifies the quantitative relationship between boarding passengers and arriving passengers. The cumulative number of boarding passengers should not exceed the cumulative number of arriving passengers.(32)∑t′=Tl0tbit′l≤pitl,∀l∈Sl,∀il∈Sil,∀t∈Stl.In summary, the ATOPO model consists of the objective function and constraints as follows:(33)ATOPO modelObjective function:7−13;Train constraints:14−22;Connection constraints:23−25;Passenger constraints:26−32;Variable definitions:1−2,4−5..


### 3.2. Synchronous Train Operation Plan Optimization Model

The STOPO model simultaneously optimizes the TOPs for all lines in the network. It is also formulated as a MILP model.


#### 3.2.1. Objective Function

The STOPO model aims to minimize generalized costZ of the network in (34).(34)minZ=ZTTC+μ∗ZPTT.Trains’ total costZTTC of the network includes trains’ operation cost ZTOC and trains’ depreciation cost ZTDC, which are accumulated by trains’ operation cost ZTOCl and trains’ depreciation cost ZTDCl of each line, respectively, as represented in (35)-(37).(35)ZTTC=ZTOC+ZTDC,(36)ZTOC=∑l∈SlZTOCl,(37)ZTDC=∑l∈SlZTDCl.Passengers’ total timeZPTT of the network includes passengers’ waiting time ZPWT and passengers’ penalty time ZPPT, which are accumulated by passengers’ waiting time ZPWTl and passengers’ penalty time ZPPTl of each line, respectively, as represented in (38)–(40). Since arriving passengers from the transfer corridors also wait for trains, passengers’ waiting time ZPWT and passengers’ penalty time ZPPT should also consider arriving passengers from the transfer corridors.(38)ZPTT=ZPWT+ZPPT,(39)ZPWT=∑l∈SlZPWTl+τ∗∑l∈Sl∑l′∈Sl∑jl∈Sjl∑jl′′∈Sjl′∑t=Tl0Tl−1∑t′=Tl0tvjj′t′ll′,(40)ZPPT=∑l∈SlZPPTl+ε∗∑l∈Sl∑l′∈Sl∑jl∈Sjl∑jl′′∈Sjl′∑t∈Stlvjj′tll′.


#### 3.2.2. Constraints

The STOPO model not only inherits all the constraints in the ATOPO model but also supplements several new constraints.Constraints (41) and (42) declare the quantitative relationship between boarding passengers and arriving passengers to replace constraint (32). Constraint (41) is only for the nontransfer stations, while constraint (42) is only for the transfer stations.(41)∑t′=Tl0tbit′l≤pitl,∀l∈Sl,∀il∈Sil\Sli0,∀t∈Stl,(42)∑t′=Tl0tbijt′l≤pijtl+∑l′∈Sl∑jl′′∈Sjl′∑t′=Tl0tvj′jt′l′l,∀l∈Sl,∀jl∈Sjl,∀t∈Stl.In addition, passenger constraints also stipulate the uniqueness and arriving time of each transfer passenger, and the number of transfer passengers.Constraint (43) states the uniqueness of each transfer passenger. Each transfer passenger should alight from an active train, walk in a valid transfer corridor, and arrive at a time point.(43)∑t∈Styjj′ktll′=qjj′ll′∗∑t∈Stlxktl,∀l∈Sl,∀l′∈Sl,∀jl∈Sjl,∀jl′′∈Sjl′,∀kl∈Skl.Constraint (44) clarifies that the arrival time of each transfer passenger should correspond to the departure time of the train from which the transfer passenger alights.(44)∑t∈Stt∗yjj′ktll′=qjj′ll′∗∑t∈Stlt∗xktl+eijl−eij′l′+fjj′ll′−djlτ∗∑t∈Stlxktl,∀l∈Sl,∀l′∈Sl,∀jl∈Sjl,∀jl′′∈Sjl′,∀kl∈Skl.Constraint (45) limits that the number of transfer passengers should not exceed cl if an active train departs at the time point and equals to zero otherwise.(45)vjj′tll′≤cl∗qjj′ll′∗∑kl∈Sklyjj′ktll′,∀l∈Sl,∀l′∈Sl,∀jl∈Sjl,∀jl′′∈Sjl′,∀l∈St.Constraints (46) and (47) claim the quantitative relationship between transfer passengers and loaded passengers. The number of transfer passengers should be equal to the transferring ratio multiplied by the number of alighting passengers.(46)vjj′t′ll′≥uij−1,kl∗aijtl∗ojj′tll′−cl∗1−yjj′kt′ll′,∀l∈Sl,∀l′∈Sl,∀jl∈Sjl,∀jl′′∈Sjl′,∀kl∈Skl,∀t∈Stl,∀t′∈St,t′=t+eijl−eij′l′+fjj′ll′−djlτ,(47)vjj′t′ll′≤uij−1,kl∗aijtl∗ojj′tll′+cl∗1−yjj′kt′ll′,∀l∈Sl,∀l′∈Sl,∀jl∈Sjl,∀jl′′∈Sjl′,∀kl∈Skl,∀t∈Stl,∀t′∈St,t′=t+eijl−eij′l′+fjj′ll′−djlτ.In summary, the STOPO model consists of the objective function and constraints as follows:(48)STOPOmodelObjective function:9−10,12−13,34−40;Train constraints:14−22;Connection constraints:23−25;Passenger constraints:26−31,41−47;Variable definitions:1−6..


## 3.1. Asynchronous Train Operation Plan Optimization Model

The ATOPO model separately optimizes the TOP for each line in the network. It is formulated as a MILP model. Although binary variables are more than integer variables in formulating the same problem, the MILP model is linear without processing [23].


### 3.1.1. Objective Function

The ATOPO model aims to minimize generalized costZl of line l for companies and passengers in (7). On the one hand, we select trains’ total cost ZTTCl to express companies’ cost of line l. On the other hand, we select passengers’ total time ZPTTl under weight μ to represent passengers’ cost of line l.(7)minZl=ZTTCl+μ∗ZPTTl,∀l∈Sl.Trains’ total costZTTCl of line l includes trains’ operation cost ZTOCl and trains’ depreciation cost ZTDCl, as represented in (8).(8)ZTTCl=ZTOCl+ZTDCl,∀l∈Sl.Trains’ operation costZTOCl of line l equals to unit operation cost ml multiplied by the number of trains, as shown in (9). The number of trains on line l is accumulated by binary variable xktl.(9)ZTOCl=∑kl∈Skl∑t∈Stlml∗xktl,∀l∈Sl.Trains’ depreciation costZTDCl of line l equals to unit depreciation cost ml0 multiplied by the number of rolling stocks, as displayed in (10). The number of rolling stocks on line l equals to the number of trains minus the number of connections. The number of connections on line l is accumulated by binary variable wkk′l.(10)ZTDCl=∑kl∈Skl∑t∈Stlml0∗xktl−∑kl∈Skl∑kl′∈Sklml0∗wkk′l,∀l∈Sl.Passengers’ total timeZPTTl of line l includes passengers’ waiting time ZPWTl and passengers’ penalty time ZPPTl, as represented in (11).(11)ZPTTl=ZPWTl+ZPPTl,∀l∈Sl.Passengers’ waiting timeZPWTl of line l consists of passengers’ basic waiting time and passengers’ additional waiting time, as shown in (12). Passengers’ basic waiting time of line l equals to half τ multiplied by the number of arriving passengers from the outside. Passengers’ additional waiting time of line l equals to τ multiplied by the number of waiting passengers.(12)ZPWTl=τ∗12∑il∈SilpiTl+∑il∈Sil∑t=Tl0Tl−1pitl−∑il∈Sil∑t=Tl0Tl−1∑t′=Tl0tbit′l,∀l∈Sl.Passengers’ penalty timeZPPTl of line l equals to unit penalty time ε multiplied by the number of finally stranded passengers, as displayed in (13).(13)ZPPTl=ε∗∑il∈SilpiTl−∑il∈Sil∑t∈Stlbitl,∀l∈Sl.


### 3.1.2. Constraints

The ATOPO model is subject to train constraints, connection constraints, and passenger constraints.(1) Train Constraints. Train constraints stipulate the uniqueness, priority, departure time, and headway of each train, as well as the number of trains.Constraints (14) and (15) specify the uniqueness of each train. Each time point can only correspond to at most one active train. Meanwhile, each train can only correspond to at most one time point.(14)∑kl∈Sklxktl≤1,∀l∈Sl,∀t∈Stl,(15)∑t∈Stlxktl≤1,∀l∈Sl,∀kl∈Skl.Constraint (16) states the priority of each train. A train should be inactive if the previous train is inactive.(16)∑t∈Stlxktl≤∑t∈Stlxk−1,tl,∀l∈Sl,∀kl∈Skl\1.Constraints (17) and (18) limit that the departure time of each active train should be between gminlk and gmaxlk.(17)∑t∈Stlt∗xktl≥gminlkτ∗∑t∈Stlxktl,∀l∈Sl,∀kl∈Skl,(18)∑t∈Stlt∗xktl≤gmaxlkτ∗∑t∈Stlxktl,∀l∈Sl,∀kl∈Skl.Constraints (19) and (20) limit that the headway of each active train should be between hminl and hmaxl.(19)∑t∈Stlt∗xktl−∑t∈Stlt∗xk−1,tl≥hminlτ−2Tl∗1−∑t∈Stlxktl,∀l∈Sl,∀kl∈Skl\1,(20)∑t∈Stlt∗xktl−∑t∈Stlt∗xk−1,tl≤hmaxlτ+2Tl∗1−∑t∈Stlxktl,∀l∈Sl,∀kl∈Skl\1.Constraints (21) and (22) limit that the number of trains should be between Kl0 and Kl.(21)∑kl∈Skl∑t∈Stlxktl≥Kl0,∀l∈Sl,(22)∑kl∈Skl∑t∈Stlxktl≤Kl,∀l∈Sl.(2) Connection Constraints. Connection constraints stipulate the uniqueness and cycle time of each connection.Constraints (23) and (24) clarify the uniqueness of each connection. Each active train can only connect at most one active train. Meanwhile, each active train can only be connected by at most one active train.(23)∑kl′∈Sklwkk′l≤∑t∈Stlxktl,∀l∈Sl,∀kl∈Skl,(24)∑kl′∈Sklwk′kl≤∑t∈Stlxktl,∀l∈Sl,∀kl∈Skl.Constraint (25) claims that the cycle time of each connection should be at least el0.(25)∑t∈Stlt∗xktl−∑t∈Stlt∗xk′tl≥el0τ−2Tl∗1−wkk′l,∀l∈Sl,∀kl∈Skl,∀kl′∈Skl.(3) Passenger Constraints. Passenger constraints stipulate the number of loaded and boarding passengers.Constraint (26) limits that the number of loaded passengers should not exceed cl if the train is active and equals to zero otherwise.(26)uikl≤cl∗∑t∈Stlxktl,∀l∈Sl,∀il∈Sil,∀kl∈Skl.Constraint (27) limits that the number of boarding passengers should not exceed cl if an active train departs at the time point and equals to zero otherwise.(27)bitl≤cl∗∑kl∈Sklxktl,∀l∈Sl,∀il∈Sil,∀t∈Stl.Constraints (28)–(31) declare the quantitative relationship between loaded passengers and boarding passengers. Constraints (28) and (29) are only for station 1, while Constraints (30) and (31) are only for the other stations. The number of loaded passengers should correspond to the number of boarding passengers and the number of alighting passengers. The number of alighting passengers should be equal to the alighting ratio multiplied by the number of loaded passengers.(28)u1kl≥b1tl−cl∗1−xktl,∀l∈Sl,∀kl∈Sil,∀t∈Stl,(29)u1kl≤b1tl+cl∗1−xktl,∀l∈Sl,∀kl∈Sil,∀t∈Stl,(30)uikl≥bitl+ui−1,kl∗1−aitl−cl∗1−xktl,∀l∈Sl,∀il∈Skl\1,∀kl∈Skl,∀t∈Stl,(31)uikl≤bitl+ui−1,kl∗1−aitl+cl∗1−xktl,∀l∈Sl,∀il∈Skl\1,∀kl∈Skl,∀t∈Stl.Constraint (32) specifies the quantitative relationship between boarding passengers and arriving passengers. The cumulative number of boarding passengers should not exceed the cumulative number of arriving passengers.(32)∑t′=Tl0tbit′l≤pitl,∀l∈Sl,∀il∈Sil,∀t∈Stl.In summary, the ATOPO model consists of the objective function and constraints as follows:(33)ATOPO modelObjective function:7−13;Train constraints:14−22;Connection constraints:23−25;Passenger constraints:26−32;Variable definitions:1−2,4−5..


## 3.1.1. Objective Function

The ATOPO model aims to minimize generalized costZl of line l for companies and passengers in (7). On the one hand, we select trains’ total cost ZTTCl to express companies’ cost of line l. On the other hand, we select passengers’ total time ZPTTl under weight μ to represent passengers’ cost of line l.(7)minZl=ZTTCl+μ∗ZPTTl,∀l∈Sl.Trains’ total costZTTCl of line l includes trains’ operation cost ZTOCl and trains’ depreciation cost ZTDCl, as represented in (8).(8)ZTTCl=ZTOCl+ZTDCl,∀l∈Sl.Trains’ operation costZTOCl of line l equals to unit operation cost ml multiplied by the number of trains, as shown in (9). The number of trains on line l is accumulated by binary variable xktl.(9)ZTOCl=∑kl∈Skl∑t∈Stlml∗xktl,∀l∈Sl.Trains’ depreciation costZTDCl of line l equals to unit depreciation cost ml0 multiplied by the number of rolling stocks, as displayed in (10). The number of rolling stocks on line l equals to the number of trains minus the number of connections. The number of connections on line l is accumulated by binary variable wkk′l.(10)ZTDCl=∑kl∈Skl∑t∈Stlml0∗xktl−∑kl∈Skl∑kl′∈Sklml0∗wkk′l,∀l∈Sl.Passengers’ total timeZPTTl of line l includes passengers’ waiting time ZPWTl and passengers’ penalty time ZPPTl, as represented in (11).(11)ZPTTl=ZPWTl+ZPPTl,∀l∈Sl.Passengers’ waiting timeZPWTl of line l consists of passengers’ basic waiting time and passengers’ additional waiting time, as shown in (12). Passengers’ basic waiting time of line l equals to half τ multiplied by the number of arriving passengers from the outside. Passengers’ additional waiting time of line l equals to τ multiplied by the number of waiting passengers.(12)ZPWTl=τ∗12∑il∈SilpiTl+∑il∈Sil∑t=Tl0Tl−1pitl−∑il∈Sil∑t=Tl0Tl−1∑t′=Tl0tbit′l,∀l∈Sl.Passengers’ penalty timeZPPTl of line l equals to unit penalty time ε multiplied by the number of finally stranded passengers, as displayed in (13).(13)ZPPTl=ε∗∑il∈SilpiTl−∑il∈Sil∑t∈Stlbitl,∀l∈Sl.


## 3.1.2. Constraints

The ATOPO model is subject to train constraints, connection constraints, and passenger constraints.(1) Train Constraints. Train constraints stipulate the uniqueness, priority, departure time, and headway of each train, as well as the number of trains.Constraints (14) and (15) specify the uniqueness of each train. Each time point can only correspond to at most one active train. Meanwhile, each train can only correspond to at most one time point.(14)∑kl∈Sklxktl≤1,∀l∈Sl,∀t∈Stl,(15)∑t∈Stlxktl≤1,∀l∈Sl,∀kl∈Skl.Constraint (16) states the priority of each train. A train should be inactive if the previous train is inactive.(16)∑t∈Stlxktl≤∑t∈Stlxk−1,tl,∀l∈Sl,∀kl∈Skl\1.Constraints (17) and (18) limit that the departure time of each active train should be between gminlk and gmaxlk.(17)∑t∈Stlt∗xktl≥gminlkτ∗∑t∈Stlxktl,∀l∈Sl,∀kl∈Skl,(18)∑t∈Stlt∗xktl≤gmaxlkτ∗∑t∈Stlxktl,∀l∈Sl,∀kl∈Skl.Constraints (19) and (20) limit that the headway of each active train should be between hminl and hmaxl.(19)∑t∈Stlt∗xktl−∑t∈Stlt∗xk−1,tl≥hminlτ−2Tl∗1−∑t∈Stlxktl,∀l∈Sl,∀kl∈Skl\1,(20)∑t∈Stlt∗xktl−∑t∈Stlt∗xk−1,tl≤hmaxlτ+2Tl∗1−∑t∈Stlxktl,∀l∈Sl,∀kl∈Skl\1.Constraints (21) and (22) limit that the number of trains should be between Kl0 and Kl.(21)∑kl∈Skl∑t∈Stlxktl≥Kl0,∀l∈Sl,(22)∑kl∈Skl∑t∈Stlxktl≤Kl,∀l∈Sl.(2) Connection Constraints. Connection constraints stipulate the uniqueness and cycle time of each connection.Constraints (23) and (24) clarify the uniqueness of each connection. Each active train can only connect at most one active train. Meanwhile, each active train can only be connected by at most one active train.(23)∑kl′∈Sklwkk′l≤∑t∈Stlxktl,∀l∈Sl,∀kl∈Skl,(24)∑kl′∈Sklwk′kl≤∑t∈Stlxktl,∀l∈Sl,∀kl∈Skl.Constraint (25) claims that the cycle time of each connection should be at least el0.(25)∑t∈Stlt∗xktl−∑t∈Stlt∗xk′tl≥el0τ−2Tl∗1−wkk′l,∀l∈Sl,∀kl∈Skl,∀kl′∈Skl.(3) Passenger Constraints. Passenger constraints stipulate the number of loaded and boarding passengers.Constraint (26) limits that the number of loaded passengers should not exceed cl if the train is active and equals to zero otherwise.(26)uikl≤cl∗∑t∈Stlxktl,∀l∈Sl,∀il∈Sil,∀kl∈Skl.Constraint (27) limits that the number of boarding passengers should not exceed cl if an active train departs at the time point and equals to zero otherwise.(27)bitl≤cl∗∑kl∈Sklxktl,∀l∈Sl,∀il∈Sil,∀t∈Stl.Constraints (28)–(31) declare the quantitative relationship between loaded passengers and boarding passengers. Constraints (28) and (29) are only for station 1, while Constraints (30) and (31) are only for the other stations. The number of loaded passengers should correspond to the number of boarding passengers and the number of alighting passengers. The number of alighting passengers should be equal to the alighting ratio multiplied by the number of loaded passengers.(28)u1kl≥b1tl−cl∗1−xktl,∀l∈Sl,∀kl∈Sil,∀t∈Stl,(29)u1kl≤b1tl+cl∗1−xktl,∀l∈Sl,∀kl∈Sil,∀t∈Stl,(30)uikl≥bitl+ui−1,kl∗1−aitl−cl∗1−xktl,∀l∈Sl,∀il∈Skl\1,∀kl∈Skl,∀t∈Stl,(31)uikl≤bitl+ui−1,kl∗1−aitl+cl∗1−xktl,∀l∈Sl,∀il∈Skl\1,∀kl∈Skl,∀t∈Stl.Constraint (32) specifies the quantitative relationship between boarding passengers and arriving passengers. The cumulative number of boarding passengers should not exceed the cumulative number of arriving passengers.(32)∑t′=Tl0tbit′l≤pitl,∀l∈Sl,∀il∈Sil,∀t∈Stl.In summary, the ATOPO model consists of the objective function and constraints as follows:(33)ATOPO modelObjective function:7−13;Train constraints:14−22;Connection constraints:23−25;Passenger constraints:26−32;Variable definitions:1−2,4−5..


## 3.2. Synchronous Train Operation Plan Optimization Model

The STOPO model simultaneously optimizes the TOPs for all lines in the network. It is also formulated as a MILP model.


### 3.2.1. Objective Function

The STOPO model aims to minimize generalized costZ of the network in (34).(34)minZ=ZTTC+μ∗ZPTT.Trains’ total costZTTC of the network includes trains’ operation cost ZTOC and trains’ depreciation cost ZTDC, which are accumulated by trains’ operation cost ZTOCl and trains’ depreciation cost ZTDCl of each line, respectively, as represented in (35)-(37).(35)ZTTC=ZTOC+ZTDC,(36)ZTOC=∑l∈SlZTOCl,(37)ZTDC=∑l∈SlZTDCl.Passengers’ total timeZPTT of the network includes passengers’ waiting time ZPWT and passengers’ penalty time ZPPT, which are accumulated by passengers’ waiting time ZPWTl and passengers’ penalty time ZPPTl of each line, respectively, as represented in (38)–(40). Since arriving passengers from the transfer corridors also wait for trains, passengers’ waiting time ZPWT and passengers’ penalty time ZPPT should also consider arriving passengers from the transfer corridors.(38)ZPTT=ZPWT+ZPPT,(39)ZPWT=∑l∈SlZPWTl+τ∗∑l∈Sl∑l′∈Sl∑jl∈Sjl∑jl′′∈Sjl′∑t=Tl0Tl−1∑t′=Tl0tvjj′t′ll′,(40)ZPPT=∑l∈SlZPPTl+ε∗∑l∈Sl∑l′∈Sl∑jl∈Sjl∑jl′′∈Sjl′∑t∈Stlvjj′tll′.


### 3.2.2. Constraints

The STOPO model not only inherits all the constraints in the ATOPO model but also supplements several new constraints.Constraints (41) and (42) declare the quantitative relationship between boarding passengers and arriving passengers to replace constraint (32). Constraint (41) is only for the nontransfer stations, while constraint (42) is only for the transfer stations.(41)∑t′=Tl0tbit′l≤pitl,∀l∈Sl,∀il∈Sil\Sli0,∀t∈Stl,(42)∑t′=Tl0tbijt′l≤pijtl+∑l′∈Sl∑jl′′∈Sjl′∑t′=Tl0tvj′jt′l′l,∀l∈Sl,∀jl∈Sjl,∀t∈Stl.In addition, passenger constraints also stipulate the uniqueness and arriving time of each transfer passenger, and the number of transfer passengers.Constraint (43) states the uniqueness of each transfer passenger. Each transfer passenger should alight from an active train, walk in a valid transfer corridor, and arrive at a time point.(43)∑t∈Styjj′ktll′=qjj′ll′∗∑t∈Stlxktl,∀l∈Sl,∀l′∈Sl,∀jl∈Sjl,∀jl′′∈Sjl′,∀kl∈Skl.Constraint (44) clarifies that the arrival time of each transfer passenger should correspond to the departure time of the train from which the transfer passenger alights.(44)∑t∈Stt∗yjj′ktll′=qjj′ll′∗∑t∈Stlt∗xktl+eijl−eij′l′+fjj′ll′−djlτ∗∑t∈Stlxktl,∀l∈Sl,∀l′∈Sl,∀jl∈Sjl,∀jl′′∈Sjl′,∀kl∈Skl.Constraint (45) limits that the number of transfer passengers should not exceed cl if an active train departs at the time point and equals to zero otherwise.(45)vjj′tll′≤cl∗qjj′ll′∗∑kl∈Sklyjj′ktll′,∀l∈Sl,∀l′∈Sl,∀jl∈Sjl,∀jl′′∈Sjl′,∀l∈St.Constraints (46) and (47) claim the quantitative relationship between transfer passengers and loaded passengers. The number of transfer passengers should be equal to the transferring ratio multiplied by the number of alighting passengers.(46)vjj′t′ll′≥uij−1,kl∗aijtl∗ojj′tll′−cl∗1−yjj′kt′ll′,∀l∈Sl,∀l′∈Sl,∀jl∈Sjl,∀jl′′∈Sjl′,∀kl∈Skl,∀t∈Stl,∀t′∈St,t′=t+eijl−eij′l′+fjj′ll′−djlτ,(47)vjj′t′ll′≤uij−1,kl∗aijtl∗ojj′tll′+cl∗1−yjj′kt′ll′,∀l∈Sl,∀l′∈Sl,∀jl∈Sjl,∀jl′′∈Sjl′,∀kl∈Skl,∀t∈Stl,∀t′∈St,t′=t+eijl−eij′l′+fjj′ll′−djlτ.In summary, the STOPO model consists of the objective function and constraints as follows:(48)STOPOmodelObjective function:9−10,12−13,34−40;Train constraints:14−22;Connection constraints:23−25;Passenger constraints:26−31,41−47;Variable definitions:1−6..


## 3.2.1. Objective Function

The STOPO model aims to minimize generalized costZ of the network in (34).(34)minZ=ZTTC+μ∗ZPTT.Trains’ total costZTTC of the network includes trains’ operation cost ZTOC and trains’ depreciation cost ZTDC, which are accumulated by trains’ operation cost ZTOCl and trains’ depreciation cost ZTDCl of each line, respectively, as represented in (35)-(37).(35)ZTTC=ZTOC+ZTDC,(36)ZTOC=∑l∈SlZTOCl,(37)ZTDC=∑l∈SlZTDCl.Passengers’ total timeZPTT of the network includes passengers’ waiting time ZPWT and passengers’ penalty time ZPPT, which are accumulated by passengers’ waiting time ZPWTl and passengers’ penalty time ZPPTl of each line, respectively, as represented in (38)–(40). Since arriving passengers from the transfer corridors also wait for trains, passengers’ waiting time ZPWT and passengers’ penalty time ZPPT should also consider arriving passengers from the transfer corridors.(38)ZPTT=ZPWT+ZPPT,(39)ZPWT=∑l∈SlZPWTl+τ∗∑l∈Sl∑l′∈Sl∑jl∈Sjl∑jl′′∈Sjl′∑t=Tl0Tl−1∑t′=Tl0tvjj′t′ll′,(40)ZPPT=∑l∈SlZPPTl+ε∗∑l∈Sl∑l′∈Sl∑jl∈Sjl∑jl′′∈Sjl′∑t∈Stlvjj′tll′.


## 3.2.2. Constraints

The STOPO model not only inherits all the constraints in the ATOPO model but also supplements several new constraints.Constraints (41) and (42) declare the quantitative relationship between boarding passengers and arriving passengers to replace constraint (32). Constraint (41) is only for the nontransfer stations, while constraint (42) is only for the transfer stations.(41)∑t′=Tl0tbit′l≤pitl,∀l∈Sl,∀il∈Sil\Sli0,∀t∈Stl,(42)∑t′=Tl0tbijt′l≤pijtl+∑l′∈Sl∑jl′′∈Sjl′∑t′=Tl0tvj′jt′l′l,∀l∈Sl,∀jl∈Sjl,∀t∈Stl.In addition, passenger constraints also stipulate the uniqueness and arriving time of each transfer passenger, and the number of transfer passengers.Constraint (43) states the uniqueness of each transfer passenger. Each transfer passenger should alight from an active train, walk in a valid transfer corridor, and arrive at a time point.(43)∑t∈Styjj′ktll′=qjj′ll′∗∑t∈Stlxktl,∀l∈Sl,∀l′∈Sl,∀jl∈Sjl,∀jl′′∈Sjl′,∀kl∈Skl.Constraint (44) clarifies that the arrival time of each transfer passenger should correspond to the departure time of the train from which the transfer passenger alights.(44)∑t∈Stt∗yjj′ktll′=qjj′ll′∗∑t∈Stlt∗xktl+eijl−eij′l′+fjj′ll′−djlτ∗∑t∈Stlxktl,∀l∈Sl,∀l′∈Sl,∀jl∈Sjl,∀jl′′∈Sjl′,∀kl∈Skl.Constraint (45) limits that the number of transfer passengers should not exceed cl if an active train departs at the time point and equals to zero otherwise.(45)vjj′tll′≤cl∗qjj′ll′∗∑kl∈Sklyjj′ktll′,∀l∈Sl,∀l′∈Sl,∀jl∈Sjl,∀jl′′∈Sjl′,∀l∈St.Constraints (46) and (47) claim the quantitative relationship between transfer passengers and loaded passengers. The number of transfer passengers should be equal to the transferring ratio multiplied by the number of alighting passengers.(46)vjj′t′ll′≥uij−1,kl∗aijtl∗ojj′tll′−cl∗1−yjj′kt′ll′,∀l∈Sl,∀l′∈Sl,∀jl∈Sjl,∀jl′′∈Sjl′,∀kl∈Skl,∀t∈Stl,∀t′∈St,t′=t+eijl−eij′l′+fjj′ll′−djlτ,(47)vjj′t′ll′≤uij−1,kl∗aijtl∗ojj′tll′+cl∗1−yjj′kt′ll′,∀l∈Sl,∀l′∈Sl,∀jl∈Sjl,∀jl′′∈Sjl′,∀kl∈Skl,∀t∈Stl,∀t′∈St,t′=t+eijl−eij′l′+fjj′ll′−djlτ.In summary, the STOPO model consists of the objective function and constraints as follows:(48)STOPOmodelObjective function:9−10,12−13,34−40;Train constraints:14−22;Connection constraints:23−25;Passenger constraints:26−31,41−47;Variable definitions:1−6..


## 4. Nondominated Sorting Coevolutionary Memetic Algorithm

### 4.1. Algorithm Scheme

With the progress in artificial intelligence, machine learning algorithms have been widely used in transportation research [24–26]. However, heuristic algorithms are still the most common method to solve TOPO problems as they have been proven to be NP-hard problems [27].The demand-driven TOPO models in this paper aim to minimize generalized cost for companies and passengers, in which weightμ is undetermined. Since decision makers expect different μ in different situations, a novel heuristic algorithm that can obtain an approximate POSS is appropriate. We select AANSGA-II to build the algorithm scheme.AANSGA-II originates from NSGA-II. NSGA-II is a classical heuristic algorithm for solving multi-objective problems [28]. AANSGA-II improves NSGA-II in three aspects for TOPO problems. In local sorting, AANSGA-II proposes neighborhood distance instead of crowding distance to sequence the individuals in each frontier appropriately. In crossover and mutation, AANSGA-II introduces a scoring mechanism and alternative operators to produce the offspring population effectively. In population initialization, AANSGA-II adopts boundary individuals to generate the initial population reasonably. [22].Despite these improvements, AANSGA-II also shows a drawback. Due to the nature of local sorting, AANSGA-II tends to pursue the first frontier rather than the elite individuals. We select CMA to improve the algorithm mechanism.CMA originates from MA. MA combines GA with LS to improve computation efficiency and solution quality. Excellent individuals generated by LS participate in GA instead of original individuals [29, 30]. CMA improves MA by encoding LS settings (i.e., position, direction, step, strategy, and other parameters) as memes for coevolution [31, 32].Inspired by MA based on NSGA-II, NSCMA incorporates CMA into AANSGA-II [33, 34]. It consists of population initialization, local search, nondominated sorting, local sorting, tournament selection, crossover and mutation, population combination, population replacement, POSS extraction, operator scoring, and termination judgement, as demonstrated in Table 1.Table 1
Pseudo code of NSCMA.
Nondominated sorting coevolutionary memetic algorithm1Start2Number of generations for final termination:Λ;3Number of generations for early termination:Λ′;4Number of generations for operator scoring:Λ0;5Size of population:Θ;6Representative weights of passengers’ total time:μ;7Probabilities of operators:Ρ, Ρπ, Ρϖ;8Tolerance factor of reference point:γ;9Objective values of benchmark individual:ZTTC0, ZPTT0;10Index of current generation:λ←1;11Sparent←Population initialization ();12Sparent←Local search (Sparent, μ);13Sparent←Nondominated sorting (Sparent);14Sparent←Local sorting (Sparent, γ, ZTTC0, ZPTT0);15Whileλ≤Λdo16Selite←Tournament selection (Sparent);17Soffspring←Crossover and mutation (Selite, Ρ, Ρπ, Ρϖ);18Shybrid←Population combination (Sparent, Soffspring);19Shybrid←Local search (Shybrid, μ);20Shybrid←Nondominated sorting (Shybrid);21Shybrid←Local sorting (Shybrid, γ, ZTTC0, ZPTT0);22Sparent←Population replacement (Shybrid);23SParetoλ←POSS extraction (Sparent);24Ρ, Ρπ, Ρϖ←Operator scoring (Sparent, Shybrid, Λ0);25IfSParetoλ=SParetoλ−Λ′then26Break;27End if28λ←λ+1;29End while30ReturnSParetoλ;31End


### 4.2. Algorithm Improvements

We only focus on the improvements in NSCMA since AANSGA-II was introduced comprehensively in our previous work [22]. The improvements are reflected in chromosome construction, local search, and local sorting.


#### 4.2.1. Improvements in Chromosome Construction

AANSGA-II encodes real variableshkl (i.e., headway of train kl) instead of binary variables xktl as genes to express the GA information. The chromosome in AANSGA-II is h11,h21,⋯,hK1,h12,h22,⋯,hK2,⋯,h1L,h2L,⋯,hKL.Differing from AANSGA-II, NSCMA encodes integer variablen1 and binary variables n2, n3, and n4 as memes to express the LS settings. Integer variable n1 represents the position (i.e., line) of LS, which is between 1 and L. Binary variable n2 expresses the direction of LS. n2=0 means to broad the headway, while n2=1 means to narrow the headway. Binary variable n3 represents the step of LS. n3=0 means to move τ, while n3=1 means to move 2τ. Binary variable n4 expresses the strategy of LS. n4=0 means overall movement, while n4=1 means local movement. The chromosome in NSCMA is h11,h21,⋯,hK1,h12,h22,⋯,hK2,⋯,h1L,h2L,⋯,hKL,n1,n2,n3,n4, as illustrated in Figure 2.Figure 2
Structure of chromosome.As a module of the chromosome, the LS settings participate in crossover and mutation just like the GA information. In each crossover operation, the LS settings of the two individuals are partially exchanged. In each mutation operation, the LS settings of the individual are partially replaced.


#### 4.2.2. Improvements in Local Search

AANSGA-II adopts all individuals in the hybrid population without processing. Due to the nature of crossover and mutation, the child population is generated without an optimization guarantee. The optimization mechanism in AANSGA-II is entirely nondeterministic.Differing from AANSGA-II, NSCMA introduces LS to enhance the optimization guarantee. Several representative weightsμ are preset to obtain all elite individuals in the first frontier since only elite individuals are valuable for decision makers. Each elite individual performs LS according to its LS settings. The processed individual is accepted if an improvement is achieved, and the original individual is retained otherwise. As the nature of LS, the processed population is optimized with an optimization guarantee. The optimization mechanism in NSCMA is partially deterministic.


#### 4.2.3. Improvements in Local Sorting

AANSGA-II sequences all individuals in each frontier by local sorting. Local sorting is based on neighborhood distance. The individuals in AANSGA-II have descending original neighborhood distances.Differing from AANSGA-II, NSCMA proposes a reference point to improve local sorting. The reference point is composed of the maximum acceptable objective values for decision makers. An individual is valid if it dominates the reference point and invalid otherwise. On this basis, all individuals in each frontier are classified into valid individuals and invalid individuals. Since valid individuals are more valuable than invalid individuals, the neighborhood distances of valid individuals are retained, while the neighborhood distances of invalid individuals are cleared. The individuals in NSCMA have descending processed neighborhood distances.Since the benchmark individual with trains’ total costZTTC0 and passengers’ total time ZPTT0 may be too excellent to serve as the reference point, NSCMA proposes tolerance factor γ to expend the maximum acceptable objective values to ZTTC0∗1+γ and ZPTT0∗1+γ, as illustrated in Figure 3.Figure 3
Classification of valid and invalid solutions.


## 4.1. Algorithm Scheme

With the progress in artificial intelligence, machine learning algorithms have been widely used in transportation research [24–26]. However, heuristic algorithms are still the most common method to solve TOPO problems as they have been proven to be NP-hard problems [27].The demand-driven TOPO models in this paper aim to minimize generalized cost for companies and passengers, in which weightμ is undetermined. Since decision makers expect different μ in different situations, a novel heuristic algorithm that can obtain an approximate POSS is appropriate. We select AANSGA-II to build the algorithm scheme.AANSGA-II originates from NSGA-II. NSGA-II is a classical heuristic algorithm for solving multi-objective problems [28]. AANSGA-II improves NSGA-II in three aspects for TOPO problems. In local sorting, AANSGA-II proposes neighborhood distance instead of crowding distance to sequence the individuals in each frontier appropriately. In crossover and mutation, AANSGA-II introduces a scoring mechanism and alternative operators to produce the offspring population effectively. In population initialization, AANSGA-II adopts boundary individuals to generate the initial population reasonably. [22].Despite these improvements, AANSGA-II also shows a drawback. Due to the nature of local sorting, AANSGA-II tends to pursue the first frontier rather than the elite individuals. We select CMA to improve the algorithm mechanism.CMA originates from MA. MA combines GA with LS to improve computation efficiency and solution quality. Excellent individuals generated by LS participate in GA instead of original individuals [29, 30]. CMA improves MA by encoding LS settings (i.e., position, direction, step, strategy, and other parameters) as memes for coevolution [31, 32].Inspired by MA based on NSGA-II, NSCMA incorporates CMA into AANSGA-II [33, 34]. It consists of population initialization, local search, nondominated sorting, local sorting, tournament selection, crossover and mutation, population combination, population replacement, POSS extraction, operator scoring, and termination judgement, as demonstrated in Table 1.Table 1
Pseudo code of NSCMA.
Nondominated sorting coevolutionary memetic algorithm1Start2Number of generations for final termination:Λ;3Number of generations for early termination:Λ′;4Number of generations for operator scoring:Λ0;5Size of population:Θ;6Representative weights of passengers’ total time:μ;7Probabilities of operators:Ρ, Ρπ, Ρϖ;8Tolerance factor of reference point:γ;9Objective values of benchmark individual:ZTTC0, ZPTT0;10Index of current generation:λ←1;11Sparent←Population initialization ();12Sparent←Local search (Sparent, μ);13Sparent←Nondominated sorting (Sparent);14Sparent←Local sorting (Sparent, γ, ZTTC0, ZPTT0);15Whileλ≤Λdo16Selite←Tournament selection (Sparent);17Soffspring←Crossover and mutation (Selite, Ρ, Ρπ, Ρϖ);18Shybrid←Population combination (Sparent, Soffspring);19Shybrid←Local search (Shybrid, μ);20Shybrid←Nondominated sorting (Shybrid);21Shybrid←Local sorting (Shybrid, γ, ZTTC0, ZPTT0);22Sparent←Population replacement (Shybrid);23SParetoλ←POSS extraction (Sparent);24Ρ, Ρπ, Ρϖ←Operator scoring (Sparent, Shybrid, Λ0);25IfSParetoλ=SParetoλ−Λ′then26Break;27End if28λ←λ+1;29End while30ReturnSParetoλ;31End


## 4.2. Algorithm Improvements

We only focus on the improvements in NSCMA since AANSGA-II was introduced comprehensively in our previous work [22]. The improvements are reflected in chromosome construction, local search, and local sorting.


### 4.2.1. Improvements in Chromosome Construction

AANSGA-II encodes real variableshkl (i.e., headway of train kl) instead of binary variables xktl as genes to express the GA information. The chromosome in AANSGA-II is h11,h21,⋯,hK1,h12,h22,⋯,hK2,⋯,h1L,h2L,⋯,hKL.Differing from AANSGA-II, NSCMA encodes integer variablen1 and binary variables n2, n3, and n4 as memes to express the LS settings. Integer variable n1 represents the position (i.e., line) of LS, which is between 1 and L. Binary variable n2 expresses the direction of LS. n2=0 means to broad the headway, while n2=1 means to narrow the headway. Binary variable n3 represents the step of LS. n3=0 means to move τ, while n3=1 means to move 2τ. Binary variable n4 expresses the strategy of LS. n4=0 means overall movement, while n4=1 means local movement. The chromosome in NSCMA is h11,h21,⋯,hK1,h12,h22,⋯,hK2,⋯,h1L,h2L,⋯,hKL,n1,n2,n3,n4, as illustrated in Figure 2.Figure 2
Structure of chromosome.As a module of the chromosome, the LS settings participate in crossover and mutation just like the GA information. In each crossover operation, the LS settings of the two individuals are partially exchanged. In each mutation operation, the LS settings of the individual are partially replaced.


### 4.2.2. Improvements in Local Search

AANSGA-II adopts all individuals in the hybrid population without processing. Due to the nature of crossover and mutation, the child population is generated without an optimization guarantee. The optimization mechanism in AANSGA-II is entirely nondeterministic.Differing from AANSGA-II, NSCMA introduces LS to enhance the optimization guarantee. Several representative weightsμ are preset to obtain all elite individuals in the first frontier since only elite individuals are valuable for decision makers. Each elite individual performs LS according to its LS settings. The processed individual is accepted if an improvement is achieved, and the original individual is retained otherwise. As the nature of LS, the processed population is optimized with an optimization guarantee. The optimization mechanism in NSCMA is partially deterministic.


### 4.2.3. Improvements in Local Sorting

AANSGA-II sequences all individuals in each frontier by local sorting. Local sorting is based on neighborhood distance. The individuals in AANSGA-II have descending original neighborhood distances.Differing from AANSGA-II, NSCMA proposes a reference point to improve local sorting. The reference point is composed of the maximum acceptable objective values for decision makers. An individual is valid if it dominates the reference point and invalid otherwise. On this basis, all individuals in each frontier are classified into valid individuals and invalid individuals. Since valid individuals are more valuable than invalid individuals, the neighborhood distances of valid individuals are retained, while the neighborhood distances of invalid individuals are cleared. The individuals in NSCMA have descending processed neighborhood distances.Since the benchmark individual with trains’ total costZTTC0 and passengers’ total time ZPTT0 may be too excellent to serve as the reference point, NSCMA proposes tolerance factor γ to expend the maximum acceptable objective values to ZTTC0∗1+γ and ZPTT0∗1+γ, as illustrated in Figure 3.Figure 3
Classification of valid and invalid solutions.


## 4.2.1. Improvements in Chromosome Construction

AANSGA-II encodes real variableshkl (i.e., headway of train kl) instead of binary variables xktl as genes to express the GA information. The chromosome in AANSGA-II is h11,h21,⋯,hK1,h12,h22,⋯,hK2,⋯,h1L,h2L,⋯,hKL.Differing from AANSGA-II, NSCMA encodes integer variablen1 and binary variables n2, n3, and n4 as memes to express the LS settings. Integer variable n1 represents the position (i.e., line) of LS, which is between 1 and L. Binary variable n2 expresses the direction of LS. n2=0 means to broad the headway, while n2=1 means to narrow the headway. Binary variable n3 represents the step of LS. n3=0 means to move τ, while n3=1 means to move 2τ. Binary variable n4 expresses the strategy of LS. n4=0 means overall movement, while n4=1 means local movement. The chromosome in NSCMA is h11,h21,⋯,hK1,h12,h22,⋯,hK2,⋯,h1L,h2L,⋯,hKL,n1,n2,n3,n4, as illustrated in Figure 2.Figure 2
Structure of chromosome.As a module of the chromosome, the LS settings participate in crossover and mutation just like the GA information. In each crossover operation, the LS settings of the two individuals are partially exchanged. In each mutation operation, the LS settings of the individual are partially replaced.


## 4.2.2. Improvements in Local Search

AANSGA-II adopts all individuals in the hybrid population without processing. Due to the nature of crossover and mutation, the child population is generated without an optimization guarantee. The optimization mechanism in AANSGA-II is entirely nondeterministic.Differing from AANSGA-II, NSCMA introduces LS to enhance the optimization guarantee. Several representative weightsμ are preset to obtain all elite individuals in the first frontier since only elite individuals are valuable for decision makers. Each elite individual performs LS according to its LS settings. The processed individual is accepted if an improvement is achieved, and the original individual is retained otherwise. As the nature of LS, the processed population is optimized with an optimization guarantee. The optimization mechanism in NSCMA is partially deterministic.


## 4.2.3. Improvements in Local Sorting

AANSGA-II sequences all individuals in each frontier by local sorting. Local sorting is based on neighborhood distance. The individuals in AANSGA-II have descending original neighborhood distances.Differing from AANSGA-II, NSCMA proposes a reference point to improve local sorting. The reference point is composed of the maximum acceptable objective values for decision makers. An individual is valid if it dominates the reference point and invalid otherwise. On this basis, all individuals in each frontier are classified into valid individuals and invalid individuals. Since valid individuals are more valuable than invalid individuals, the neighborhood distances of valid individuals are retained, while the neighborhood distances of invalid individuals are cleared. The individuals in NSCMA have descending processed neighborhood distances.Since the benchmark individual with trains’ total costZTTC0 and passengers’ total time ZPTT0 may be too excellent to serve as the reference point, NSCMA proposes tolerance factor γ to expend the maximum acceptable objective values to ZTTC0∗1+γ and ZPTT0∗1+γ, as illustrated in Figure 3.Figure 3
Classification of valid and invalid solutions.


## 5. Case Study

### 5.1. Case Setup

Shenyang Metro in Northeast China operated a cruciform rail transit network from December 30, 2013, to April 7, 2018, as illustrated in Figure4.Figure 4
Sketch map of Shenyang Metro.Dynamic passenger demand is strictly processed from the historical data on December 9, 2016. The distribution of passenger demand is bimodal, as illustrated in Figure5.Figure 5
Distribution of passenger demand on December 9, 2016.The actual TOPs of the two lines are encoded together as the Benchmark Solution (BS for short). The time period of each line is normalized to [4 : 50, 22 : 20]. Table2 demonstrates the parameters of the case.Table 2
Parameters of the case.
ParameterDescriptionValueLThe number of lines2IlThe number of stations in each direction22 (line 1, line 2), 44 (total)JlThe number of transfer stations in each direction1 (line 1, line 2), 2 (total)Kl0The minimum number of trains153 (line 1), 136 (line 2), 289 (total)KlThe maximum number of trains180 (line 1), 160 (line 2), 340 (total)Tl0The start time of the time period1 (line 1, line 2)TlThe end time of the time period2100 (line 1, line 2)clThe capacity of each train2016 (line 1, line 2)hminlThe minimum headway of each train (min)4 (line 1, line 2)hmaxlThe maximum headway of each train (min)10 (line 1, line 2)el0The essential cycle time of each connection (min)112 (line 1), 111 (line 2)τThe length of each time slice (min)0.5mlThe unit operation cost of each train (CNY)852 (line 1), 834 (line 2)ml0The unit depreciation cost of each rolling stock (CNY)3696 (line 1, line 2)εThe unit penalty time of each finally stranded passenger (min)1000The case focuses on the approximate POSS based on the STOPO model (SS for short) and the approximate POSS based on the ATOPO model (AS for short). Notably, AS of Line 1 (AS-1 for short) and AS of Line 2 (AS-2 for short) are optimized independently. Each solution in AS-1 and each solution in AS-2 form an integrated solution together. AS refers to the POSS in all integrated solutions.The case applies NSCMA and AANSGA-II for comparisons. Both heuristic algorithms are encoded in MATLAB R2019a. All computations were performed on a personal computer. Table3 demonstrates the parameters of the heuristic algorithms.Table 3
Parameters of the heuristic algorithms.
ParameterDescriptionValueΛThe number of generations for final termination10000Λ′The number of generations for early termination50Λ0The number of generations for operator scoring50ΘThe size of population50 (SS), 20 (AS)μThe representative weights of passengers’ total time{0.05, 0.072, 0.1037, 0.1493, 0.215, 0.3096}ΡThe initial probability of crossover operation0.5ΡπThe initial probability of each crossover operator0.5ΡϖThe initial probability of each mutation operator0.0625γThe tolerance factor of reference point0.03ZTTC0The trains’ total cost of benchmark individual (CNY)447552ZPTT0The passengers’ total time of benchmark individual (min)3163228.25


### 5.2. Case Results

Firstly, we solve the STOPO model with NSCMA and AANSGA-II. NSCMA obtains SS at generation 8491 within 123 min, while AANSGA-II obtainsSS∗ at generation 9773 within 127 min. We use trains’ total cost ZTTC and passengers’ total time ZPTT as indicators to compare the performances of SS, SS∗, and BS, as illustrated in Figure 6. Notably, only the solutions better than BS in both costs, also known as the valid solutions, are drawn in Figure 6.Figure 6
Performances of SS,SS∗, and BS.According to Figure6, SS outperforms SS∗ in progressiveness, while SS does not outperform SS∗ in diversity. SS dominates SS∗, which means that NSCMA is better than AANSGA-II in the evolution process for the elite individuals. However, SS∗ presents more small cracks but fewer large cracks than SS, which means that NSCMA is not better than AANSGA-II in the evolution process for the first frontier.Secondly, we solve the ATOPO model by NSCMA. NSCMA obtains AS-1 at generation 1142 within 7 min and AS-2 at generation 304 within 2 min. AS is selected from all combinations of AS-1 and AS-2 within 1 min. We use trains’ total costZTTC and passengers’ total time ZPTT as indicators to compare the performances of SS, AS, and BS, as illustrated in Figure 7.Figure 7
Performances of SS, AS, and BS.In the light of Figure7, SS contains thirty-four solutions, while AS contains fifteen solutions. SS dominates AS, obviously, which means that the STOPO model is better than the ATOPO model.Thirdly, we list the Elite Solutions in SS (SS-Es for short) and the Elite Solutions in AS (AS-Es for short) under specific weights. Inspired by our previous work, the representative weights areμ∈0.05,0.072,0.1037,0.1493,0.215,0.3096 [22]. These six numbers form a proportional sequence with a common ratio of 1.44. We use trains’ total cost ZTTC, passengers’ total time ZPTT, generalized cost Z, and improvement rates over BS ΔTTC, ΔPTT, and ΔZ as indicators to compare the performances of SS-Es, AS-Es, and BS under different μ, as demonstrated in Table 4. Notably, all elitist solutions are marked in Figure 7.Table 4
Performances of SS-Es, AS-Es and BS under differentμ.
μSolutionZTTCΔTTCZPTTΔPTTZΔZ0.05SS-E-14132447.67%3139740.250.74%570231.015.86%AS-E-14372982.29%3147741.750.49%594685.091.82%BS447552—3163228.25—605713.41—0.072SS-E-24174686.72%3058919.753.30%637710.225.57%AS-E-14372982.29%3147741.750.49%663935.411.68%BS447552—3163228.25—675304.43—0.1037SS-E-24174686.72%3058919.753.30%734616.805.27%AS-E-24390021.91%3125601.251.19%763064.341.61%BS447552—3163228.25—775515.50—0.1493SS-E-34330383.24%2926909.257.47%870023.215.41%AS-E-34415581.34%3107683.751.76%905532.701.55%BS447552—3163228.25—919819.45—0.215SS-E-44401241.66%2888932.258.67%1061217.995.89%AS-E-44431900.97%3097419.752.08%1109106.901.64%BS447552—3163228.25—1127617.12—0.3096SS-E-54471920.08%2860860.259.56%1332876.636.59%AS-E-54448940.59%3089543.752.33%1401376.031.79%BS447552—3163228.25—1426845.78—AverageSS-E4280894.35%2989046.925.51%867779.315.86%AS-E4405401.57%3119288.671.39%906283.411.68%BS447552—3163228.25—921802.62—According to Table4, both elite solution sets consist of five distinct solutions, respectively. Compared with BS, SS-Es improve ZTTC by 4.35% and ZPTT by 5.51% on average, while AS-Es improve ZTTC by 1.57% and ZPTT by 1.39% on average. Compared with AS-Es, SS-Es improve ZTTC by 2.83% and ZPTT by 4.18% on average.Fourthly, we use the load factor of each train as an indicator to analyze the utilization of trains in SS-Es and BS, as illustrated in Figure8.Figure 8
Utilization of trains in SS-Es and BS.In the light of Figure8, most SS-Es utilize trains more effectively than BS. Overall, SS-E-1 uses twenty-three fewer trains than BS, SS-E-2 uses eighteen fewer trains than BS, SS-E-3 uses four fewer trains than BS, SS-E-4 uses the same number of trains as BS, and SS-E-5 uses four more trains than BS. Specifically, no SS-E uses more trains on Line 1 than BS, while three SS-Es use more trains on Line 2 than BS. The difference demonstrates that the actual TOP of Line 1 has more space for optimization than that of Line 2. Besides, fewer trains generally mean higher average load factors.Fifthly, we use the task order of each rolling stock as an indicator to analyze the utilization of rolling stocks in SS-Es and BS, as illustrated in Figure9.Figure 9
Utilization of rolling stocks in SS-Es and BS.According to Figure9, all SS-Es utilize rolling stocks more effectively than BS. Overall, SS-E-1 and SS-E-2 use four fewer rolling stocks than BS, SS-E-3 uses three fewer rolling stocks than BS, SS-E-4 uses two fewer rolling stocks than BS, and SS-E-5 uses one fewer rolling stocks than BS. Specifically, all SS-Es use fewer rolling stocks on Line 1 than BS, while no SS-E uses fewer rolling stocks on Line 2 than BS. The difference proves again that the actual TOP of Line 2 matches passenger demand better than that of Line 1. Besides, fewer rolling stocks generally mean more tasks per rolling stock.In summary, the superiority of the STOPO model over the ATOPO model explains that TOPS is an important element in TOPO for the network. Besides, the superiority of NSCMA over AANSGA-II suggests that LS is a powerful complement to evolutionary algorithms.


## 5.1. Case Setup

Shenyang Metro in Northeast China operated a cruciform rail transit network from December 30, 2013, to April 7, 2018, as illustrated in Figure4.Figure 4
Sketch map of Shenyang Metro.Dynamic passenger demand is strictly processed from the historical data on December 9, 2016. The distribution of passenger demand is bimodal, as illustrated in Figure5.Figure 5
Distribution of passenger demand on December 9, 2016.The actual TOPs of the two lines are encoded together as the Benchmark Solution (BS for short). The time period of each line is normalized to [4 : 50, 22 : 20]. Table2 demonstrates the parameters of the case.Table 2
Parameters of the case.
ParameterDescriptionValueLThe number of lines2IlThe number of stations in each direction22 (line 1, line 2), 44 (total)JlThe number of transfer stations in each direction1 (line 1, line 2), 2 (total)Kl0The minimum number of trains153 (line 1), 136 (line 2), 289 (total)KlThe maximum number of trains180 (line 1), 160 (line 2), 340 (total)Tl0The start time of the time period1 (line 1, line 2)TlThe end time of the time period2100 (line 1, line 2)clThe capacity of each train2016 (line 1, line 2)hminlThe minimum headway of each train (min)4 (line 1, line 2)hmaxlThe maximum headway of each train (min)10 (line 1, line 2)el0The essential cycle time of each connection (min)112 (line 1), 111 (line 2)τThe length of each time slice (min)0.5mlThe unit operation cost of each train (CNY)852 (line 1), 834 (line 2)ml0The unit depreciation cost of each rolling stock (CNY)3696 (line 1, line 2)εThe unit penalty time of each finally stranded passenger (min)1000The case focuses on the approximate POSS based on the STOPO model (SS for short) and the approximate POSS based on the ATOPO model (AS for short). Notably, AS of Line 1 (AS-1 for short) and AS of Line 2 (AS-2 for short) are optimized independently. Each solution in AS-1 and each solution in AS-2 form an integrated solution together. AS refers to the POSS in all integrated solutions.The case applies NSCMA and AANSGA-II for comparisons. Both heuristic algorithms are encoded in MATLAB R2019a. All computations were performed on a personal computer. Table3 demonstrates the parameters of the heuristic algorithms.Table 3
Parameters of the heuristic algorithms.
ParameterDescriptionValueΛThe number of generations for final termination10000Λ′The number of generations for early termination50Λ0The number of generations for operator scoring50ΘThe size of population50 (SS), 20 (AS)μThe representative weights of passengers’ total time{0.05, 0.072, 0.1037, 0.1493, 0.215, 0.3096}ΡThe initial probability of crossover operation0.5ΡπThe initial probability of each crossover operator0.5ΡϖThe initial probability of each mutation operator0.0625γThe tolerance factor of reference point0.03ZTTC0The trains’ total cost of benchmark individual (CNY)447552ZPTT0The passengers’ total time of benchmark individual (min)3163228.25


## 5.2. Case Results

Firstly, we solve the STOPO model with NSCMA and AANSGA-II. NSCMA obtains SS at generation 8491 within 123 min, while AANSGA-II obtainsSS∗ at generation 9773 within 127 min. We use trains’ total cost ZTTC and passengers’ total time ZPTT as indicators to compare the performances of SS, SS∗, and BS, as illustrated in Figure 6. Notably, only the solutions better than BS in both costs, also known as the valid solutions, are drawn in Figure 6.Figure 6
Performances of SS,SS∗, and BS.According to Figure6, SS outperforms SS∗ in progressiveness, while SS does not outperform SS∗ in diversity. SS dominates SS∗, which means that NSCMA is better than AANSGA-II in the evolution process for the elite individuals. However, SS∗ presents more small cracks but fewer large cracks than SS, which means that NSCMA is not better than AANSGA-II in the evolution process for the first frontier.Secondly, we solve the ATOPO model by NSCMA. NSCMA obtains AS-1 at generation 1142 within 7 min and AS-2 at generation 304 within 2 min. AS is selected from all combinations of AS-1 and AS-2 within 1 min. We use trains’ total costZTTC and passengers’ total time ZPTT as indicators to compare the performances of SS, AS, and BS, as illustrated in Figure 7.Figure 7
Performances of SS, AS, and BS.In the light of Figure7, SS contains thirty-four solutions, while AS contains fifteen solutions. SS dominates AS, obviously, which means that the STOPO model is better than the ATOPO model.Thirdly, we list the Elite Solutions in SS (SS-Es for short) and the Elite Solutions in AS (AS-Es for short) under specific weights. Inspired by our previous work, the representative weights areμ∈0.05,0.072,0.1037,0.1493,0.215,0.3096 [22]. These six numbers form a proportional sequence with a common ratio of 1.44. We use trains’ total cost ZTTC, passengers’ total time ZPTT, generalized cost Z, and improvement rates over BS ΔTTC, ΔPTT, and ΔZ as indicators to compare the performances of SS-Es, AS-Es, and BS under different μ, as demonstrated in Table 4. Notably, all elitist solutions are marked in Figure 7.Table 4
Performances of SS-Es, AS-Es and BS under differentμ.
μSolutionZTTCΔTTCZPTTΔPTTZΔZ0.05SS-E-14132447.67%3139740.250.74%570231.015.86%AS-E-14372982.29%3147741.750.49%594685.091.82%BS447552—3163228.25—605713.41—0.072SS-E-24174686.72%3058919.753.30%637710.225.57%AS-E-14372982.29%3147741.750.49%663935.411.68%BS447552—3163228.25—675304.43—0.1037SS-E-24174686.72%3058919.753.30%734616.805.27%AS-E-24390021.91%3125601.251.19%763064.341.61%BS447552—3163228.25—775515.50—0.1493SS-E-34330383.24%2926909.257.47%870023.215.41%AS-E-34415581.34%3107683.751.76%905532.701.55%BS447552—3163228.25—919819.45—0.215SS-E-44401241.66%2888932.258.67%1061217.995.89%AS-E-44431900.97%3097419.752.08%1109106.901.64%BS447552—3163228.25—1127617.12—0.3096SS-E-54471920.08%2860860.259.56%1332876.636.59%AS-E-54448940.59%3089543.752.33%1401376.031.79%BS447552—3163228.25—1426845.78—AverageSS-E4280894.35%2989046.925.51%867779.315.86%AS-E4405401.57%3119288.671.39%906283.411.68%BS447552—3163228.25—921802.62—According to Table4, both elite solution sets consist of five distinct solutions, respectively. Compared with BS, SS-Es improve ZTTC by 4.35% and ZPTT by 5.51% on average, while AS-Es improve ZTTC by 1.57% and ZPTT by 1.39% on average. Compared with AS-Es, SS-Es improve ZTTC by 2.83% and ZPTT by 4.18% on average.Fourthly, we use the load factor of each train as an indicator to analyze the utilization of trains in SS-Es and BS, as illustrated in Figure8.Figure 8
Utilization of trains in SS-Es and BS.In the light of Figure8, most SS-Es utilize trains more effectively than BS. Overall, SS-E-1 uses twenty-three fewer trains than BS, SS-E-2 uses eighteen fewer trains than BS, SS-E-3 uses four fewer trains than BS, SS-E-4 uses the same number of trains as BS, and SS-E-5 uses four more trains than BS. Specifically, no SS-E uses more trains on Line 1 than BS, while three SS-Es use more trains on Line 2 than BS. The difference demonstrates that the actual TOP of Line 1 has more space for optimization than that of Line 2. Besides, fewer trains generally mean higher average load factors.Fifthly, we use the task order of each rolling stock as an indicator to analyze the utilization of rolling stocks in SS-Es and BS, as illustrated in Figure9.Figure 9
Utilization of rolling stocks in SS-Es and BS.According to Figure9, all SS-Es utilize rolling stocks more effectively than BS. Overall, SS-E-1 and SS-E-2 use four fewer rolling stocks than BS, SS-E-3 uses three fewer rolling stocks than BS, SS-E-4 uses two fewer rolling stocks than BS, and SS-E-5 uses one fewer rolling stocks than BS. Specifically, all SS-Es use fewer rolling stocks on Line 1 than BS, while no SS-E uses fewer rolling stocks on Line 2 than BS. The difference proves again that the actual TOP of Line 2 matches passenger demand better than that of Line 1. Besides, fewer rolling stocks generally mean more tasks per rolling stock.In summary, the superiority of the STOPO model over the ATOPO model explains that TOPS is an important element in TOPO for the network. Besides, the superiority of NSCMA over AANSGA-II suggests that LS is a powerful complement to evolutionary algorithms.


## 6. Conclusion

This paper researched the demand-driven TOPO problem in the rail transit network. The bi-objective MILP models, the ATOPO model, and the STOPO model minimize trains’ total cost and passengers’ total time by simultaneously determining train frequency, train timetable, and rolling stock circulation. The hybrid heuristic algorithm, NSCMA, ameliorates the evolution process for elite individuals by incorporating CMA into AANSGA-II.According to the case of Shenyang Metro, the STOPO model is better than the ATOPO model. The elite synchronous TOPs reduce trains’ total cost by 2.83% and passengers’ total time by 4.18% on average compared to the elite asynchronous TOPs. Besides, NSCMA is better than AANSGA-II. NSCMA outperforms AANSGA-II in obtaining the elite individuals, while NSCMA does not outperform AANSGA-II in obtaining the first frontier.In the future, we will focus on the difficulties as follows. Firstly, the weight of passengers’ total time is discussed with an alternative set. It is meaningful to integrate all objectives into a unified dimension. Secondly, NSCMA does not show comprehensive improvement over AANSGA-II. It is optional to apply other heuristic algorithms.



---

*Source: 4092011-2022-10-05.xml*