# A Line Planning Approach for High-Speed Rail Networks with Time-Dependent Demand and Capacity Constraints

Authors: Huanyin Su; Wencong Tao; Xinlei Hu
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

In high-speed rail networks, trains are operated with high speeds and high frequencies, which can satisfy passenger demand with different expected departure times. Given time-dependent demand, this paper proposes a line planning approach with capacity constraints for high-speed rail networks. In this paper, a bilevel optimization model is formulated and the constraints include track section capacity per unit time, train seat capacity, and the gap between the number of starting trains and that of ending trains at a station. In the upper level, the objective is to minimize train operational cost and passenger travel cost, and the decision variables include the line of each train, carriage composition of each train, train stop patterns, train start times, and train arrival and departure times at stops in the line plan. In the lower level, a schedule-based passenger assignment method, which assigns time-varying demand on trains with seat capacity constraints by simulating the ticket-booking process, is used to evaluate the line plan obtained in the upper level. A simulated annealing algorithm is developed to solve the model in which some strategies are designed to search for neighborhood solutions, including reducing train carriages, deleting trains, adding trains, increasing train carriages, and adjusting train start times. Finally, an application to the Chinese high-speed rail network is presented. The numerical results show that (i) the average time deviations between the expected departure times and the actual boarding times of passengers are within 30 min, (ii) the unserved passengers are less than 200, and (iii) the average load factors of trains are about 70%. Hence, line plan solutions meet time-dependent demand well and satisfy the capacity constraints for high-speed rail networks.


---

## Body

## 1. Introduction

In the past few years, high-speed rail (HSR) has a rapid development in the world, especially China. According to the “Mid-Long Term Railway Network Plan” issued by the National Development and Reform Commission [1] in China on July 13, 2016, the length of the operational HSR will be up to 30,000 km in 2020 and “eight vertical and eight horizontal” HSR network will be built in China. The line planning plays an important role in optimizing the resource allocation for the HSR system. In HSR networks, trains are operated with high speeds and high frequencies, and passengers hope that trains satisfy their expected departure times; that is, the travel demand of HSR passengers is time-dependent. Besides, line planning is restricted by capacity constraints of HSR networks. With time-dependent demand and capacity constraints, line planning for HSR networks is a new challenging problem.As studied by many authors [2–7], the line planning problem is to determine trains with given rail infrastructure and passenger demand, particularly including line frequencies, the origin station and destination station of each train, train routes, train stop patterns, and train carriage compositions. Schöbel [8] reviewed the line planning approaches in public transportation, in which discrete integer scale models are usually proposed with cost-oriented or service-oriented objective functions. The solving methods typically include the branch-and-cut approach [4], the branch and bound approach [3], and the column-generation approach [6]. Heuristic algorithms are also used to solve the models. For example, Fu and Nie et al. [7] proposed a hierarchical line planning approach for a HSR network, in which the iterative computation algorithm was developed to solve the problem. The above studies were based on daily passenger demand, not considering the time-dependent demand.Given time-varying demand, Chang and Yeh et al. [9] developed a multiobjective programming model for passenger train services planning on a single intercity HSR line, in which service frequencies at each operating interval, train stop patterns, and fleet size were determined. This approach decomposed the problem into several interval subproblems and did not reflect the movement of passengers and trains on the HSR line in temporal and spatial dimensions, which made the demand and train service not consistent. Kaspi and Raviv [10], based on time-dependent demand, proposed an integrated line planning and timetabling approach for passenger trains with the objective of minimizing both user inconvenience and operational costs, solved using a cross-entropy metaheuristic. Their experiment was based on a middle-size rail network (consisting of 1,000 km rail tracks and 77 stations) and the integrated approach was actually conducted in a single cycle (one hour). However, for large-scale rail networks, for example, the HSR network in China (consisting of more than 20,000 km rail tracks and 400 stations by far), it is relatively more difficult to conduct the integrated approach in the planning horizon (about 18 hours in China). It is known that line planning and timetabling are both NP-hard problems [11]. Besides, the seat capacity of the trains was not binding in the passenger assignment approach of Kaspi and Raviv [10]. The above two papers both do not consider the ticket-booking process in the passenger assignment, which is a key character in travel choice behaviors of passengers.This paper proposes a line planning approach aiming to better meet time-dependent demand and apply to the large-scale HSR networks. Hence, in this paper, the lines of trains, carriage compositions of trains, and train stop patterns are determined in the line planning; what is more, train start times and train arrival and departure times at stops are also estimated, which prepare well for timetabling in the next planning phase [12]. But the time conflict problems of operation lines are not considered in this paper, which are solved in the stage of timetabling.In the line planning, the constraints typically include frequency requirements for the stations or the tracks, budget constraints, and train seat capacity constraints. Safe headway between trains and the delivery capacity per unit time at stations are usually involved in timetabling [13–16]. With the time-dependent demand, the line planning is to optimize the space-time allocation of trains, so it can be constrained by the delivery capacities of station and section in the time axis. In this line planning approach, the constraints of track section capacity per unit time, which are the upper bounds on the numbers of running trains per unit time for track sections, are specified to confine the start times of trains. These constraints can avoid too many trains passing a track section in a certain period and prepare the line planning well for later timetabling.In summary, this paper proposes a line planning approach with time-dependent demand and capacity constraints for HSR networks to optimize synthetically the lines of trains, carriage compositions of trains, train stop patterns, train start times, and train arrival and departure times at stops. The constraints include the following:(1) lines and train stop patterns in the candidate sets, (2) carriage compositions of trains, (3) the seat capacity of trains, (4) the start and end times of trains within the horizon time, (5) train arrival and departure times at mid-stops specified by the start time, (6) capacity constraints of running trains per unit time for track sections, and (7) the gap between the numbers of starting trains and ending trains at each station. The optimization objective considers both train operational cost and passenger travel cost, where the former is represented by total engine time of trains and the latter is represented by total journey time of passengers. A bilevel optimization model is formulated. In the lower level, a schedule-based passenger assignment method, which assigns time-varying demand on trains with seat capacity constraints by simulating the ticket-booking process, is used to evaluate the line plan obtained in the upper level. Further, a simulated annealing algorithm is developed to solve the model in which some strategies are designed to search for neighborhood solutions, including reducing train carriages, deleting trains, adding trains, increasing train carriages, and adjusting train start times. An application to the Chinese HSR network is presented and analyzed.In Table1, the main notations used in the paper are listed in the order of appearance. The reminder of this paper is organized as follows. A detailed problem statement and notations are presented in Section 2. A bilevel optimization model of the line planning with time-dependent demand and capacity constraints for HSR networks is developed in Section 3. A simulated annealing algorithm is designed to solve the model in Section 4. Numerical experiment on the Chinese HSR network is presented to verify the feasibility and validity of this method in Section 5. The last section concludes the paper and discusses future research topics.Table 1
The main notations used.
V the set of stations u, v stations E the set of track sections e track section T a train l T a line traversed by trainT v i T theith station on line lT M ( T ) the number of stations on linelT l s T the train stop pattern on linelT η i T a 0-1 variable, the stop sign of train at stationviT, L S l a set consisting of all possible train stop patterns on linel Ω = T a line plan d i T the departure time of trainT at station viT a i T the arrival time of trainT at station viT D T the sequence of departure times of trainT A T the sequence of arrival times of trainT B T the carriage composition of trainT C T the seat capacity of trainT T ( i , j ) the segment of trainT running between two neighborhood stop stations viT and vjT, 1≤i<j≤M(T) SPAM-TBP a schedule-based passenger assignment method for high-speed rail networks considering the ticket-booking process T ( i , j ) the length ofT(i,j) t 1 , t 2 the horizon time t - , 0 the ticket pre-sale period R S set of passenger origin-destination pairs r , s an O-D pair f r s x , y time-dependent demand of the O-D pairr,s for x∈t1,t2 and y∈t-,0 F the set of time-dependent demand for all O-D pairs J T 1 time deviation between the expected departure time and the actual boarding time J T 2 time on trains J T 3 transfer time ω 1, ω2, ω3 the value weights ofJT1, JT2 and JT3 respectively G T r s m i n x , y the minimum travel cost of passengers for O-D pairr,s with expected departure time x and ticket-booking time y t r s the time when there is no seat capacity for the passengers of O-D pairr,s in the pre-sale period t e r u n the train running time on track sectione t v s t o p the sum of dwell time and additional time for engine starting and stopping at stationv F T , i , j the number of passengers assigned on train segmentT(i,j) C p H e the upper bound on the number of running trains per unit time for track sectione ∆ t unit time δ T e , k a 0-1 variable, labeling whether trainT enters track section e within the kth time interval W u , v a 0-1 function telling if stationu is same as station v Δ w The maximum gap between the number of starting trains and that of ending trains at a station ζ T weight of trainT in operational cost Z 1 the operational cost of all trains Z 2 travel cost for passengers who are served Z 3 the penalty cost for passengers who are unserved Z Ω the objective function α, β the weights in the objective function for trains and passengers respectively L F T the load factor of trainT


## 2. Problem Statement and Notations

The line planning problem in this paper is defined as follows: given the HSR track network and time-dependent demand, the lines of trains, carriage compositions of trains, train stop patterns, train start times, and train arrival and departure times at stops are optimized synthetically. The optimizing objective is to minimize both train operational cost and passenger travel cost.(  1  ) HSR Network, Line, and Train Stop Pattern. A HSR network is represented by V,E, where V is the set of stations and E is the set of track sections, and a track section is the link between two neighboring stations on a rail track. A train is represented by T. A line defines a sequence of stations and track sections traversed by train T, and it is denoted as lT=v1T,v2T,…,vM(T)T, where viT(1≤i≤M(T)) is the ith station on line lT and M(T) is the number of stations on line lT. Then a set consisting of all possible lines is constructed and denoted as L, called a candidate line set.For a given linelT=v1T,v2T,…,vM(T)T, the train stop pattern on this line is denoted by lsT=η1T,η2T,…,ηM(T)T, where if the train stops at viT(1≤i≤M(T)) station, then ηiT=1; otherwise ηiT=0. Obviously, a train on the line must stops at the first station and the last station; that is, η1T=1 and ηM(T)T=1.For convenience of describing train stop patterns, stations are classified into three levels according to the scales of cities where they locate. The first level stations locate in the megalopolis, and the second level stations locate in the provincial cities or important cities, and the third level stations locate in the smaller cities. The train stop patterns are also classified into three types (see Figure1). The first type is that the trains stop only at the first- and second-level stations on the lines, and the third-level stations are not stop stations. The second type is that the first- and second-level stations on the lines are all stop stations, and the third-level stations are also stop stations but not all. The third type is that all the stations on the line are stop stations.Figure 1
Three types of train stop patterns.Then a set consisting of all possible train stop patterns on linel is constructed and denoted as LSl. The candidate line sets and the corresponding train stop pattern sets can be generated based on the HSR network and passenger travel demand characteristics. The specific generation method of the candidate sets is similar to the study of Fu and Nie et al. [17].(  2  ) Line Plan. Let Ω=T be the set of trains running on the network V,E, and Ω represents a line plan. For each train T∈Ω, it consists of the line, the stop pattern, train arrival and departure times at stations, and the carriage composition. The line lT is selected from L and the stop pattern lsT is selected from LSlT. Let diT and aiT be the departure time and arrival time, respectively, at station viT(2≤i≤M(T)-1). Let d1T be the start time at station v1T and aM(T)T be the end time at station vM(T)T. Let DT=d1T,d2T,…,dM(T)-1T be the sequence of departure times and AT=a2T,a3T,…,aM(T)T be the sequence of arrival times. The carriage composition and seat capacity of train T are denoted as BT and CT, respectively. Then a line plan in this paper can be expressed as Ω=T=(lT,lsT,DT,AT,BT).LetT(i,j) be the segment of train T running between two neighborhood stop stations viT and vjT, 1≤i<j≤M(T), called “train segment” here. The length of T(i,j) is represented by T(i,j), representing the length of line lT between station viT and vjT.(  3  ) Passenger Assignment. The purpose of line planning is to satisfy time-dependent demand. For a given line plan, passenger assignment method is usually used to estimate the path choices of passengers and the assignment results are used to evaluate the line plan about the service for passengers.In the studies of line planning, simplified passenger assignment methods are usually employed, for example, system split method [18, 19], which was also analyzed by Borndörfer and Grötschel et al. [6]. Some other authors [7, 10] simplified the passenger assignment process by not binding train seat capacity. In HSR networks, passengers book tickets and reserve seats during the presale period, and train seat capacity is occupied in the order of the passengers’ ticket-booking time, and the crowding effect can be ignored. These features are essential differences from other public transit networks. Based on the above features, Su and Shi et al. [20] proposed a schedule-based passenger assignment method for high-speed rail networks considering the ticket-booking process (SPAM-TBP). In the ticket-booking process, as time continues, the number of passengers having booked tickets increases; then some train segments become filled to their capacities and the travel paths with minimum cost change; hence subsequent passengers booking tickets may have to face higher travel costs. In this method, the ticket-booking process of passengers was simulated for passenger assignment with time-dependent demand and train seat capacity constraints. In the line planning of this paper, the departure and arrival times at stations for trains are designed; hence,SPAM-TBPcan be used directly to estimate the path choices of passengers in this paper and evaluate the line plan.The horizon time is denoted byt1,t2. The ticket presale period is denoted as t-,0 (t- is negative. t- is the maximum presale time ahead of the travel day, and 0 means the travel day). The set of passenger origin-destination (O-D) pairs is denoted as RS⊂V×V. For a given O-D pair r,s, time-dependent demand can be expressed as frsx,y,x∈t1,t2,y∈t-,0, which is a function depending on the expected departure time x and the ticket-booking time y. Let F=frsx,y∣r,s∈RS,x∈t1,t2,y∈t-,0.Given the ticket-booking time, passengers book tickets to choose the paths with minimum travel cost. The travel cost is represented by the journey time of passengers, which includes time deviation (JT1) between the expected departure time and the actual boarding time, time on trains (JT2), and transfer time (JT3) to switch trains at stations. Cost values of the above times are different [21] and the value weights are denoted as ω1, ω2, and ω3, respectively. Then, given the ticket-booking time y and O-D pair r,s, the minimum travel cost of passengers with expected departure time x can be expressed as follows:(1)GTrsminx,y=ω1∙JT1+ω2∙JT2+ω3∙JT3where the time deviation JT1 can be used to evaluate how well train start times meet the expected departure times of passengers. As the ticket-booking time y continues (closing to 0), some train segments become filled to their capacities and then the minimum travel cost GTrsminx,y becomes higher.The transport capacity of the line plan is constrained by the seat capacity of trains. Hence, in the presale period, the tickets some passengers want to book may be sold out and then those passengers cannot get the service of this line plan and be met. UsingSPAM-TBP, the time when there is no seat capacity for the passengers of O-D pair r,s in the presale period can be obtained and denoted as trs≤0. When trs<0, it means that there are some passengers of O-D pair r,s unserved by this line plan; when trs=0, it means that all passengers of O-D pair r,s are served.


## 3. Model Formulation

### 3.1. Modeling Assumptions

Some assumptions are made in the line planning as follows:(i)
There are two types of carriage composition for trains, i.e., 8 carriages and 16 carriages, and the seat capacities are 600 passengers and 1100 passengers, respectively.(ii)
Train classes are not considered and the train running time on each track section is given asterun  (e∈E).(iii)
The sum of dwell time and additional time for engine starting and stopping at a station for trains is given astvstop  (v∈V).(iv)
The departure and arrival times at stations of trains are designed without considering the time conflicts in operation lines.


### 3.2. Constraints

Line planning is restricted by capacity constraints of HSR networks. In particular, constraints in line planning include the following:(1) lines and train stop patterns in the candidate sets, (2) carriage compositions of trains, (3) the seat capacity of trains, (4) the start and end times of trains within the horizon time, (5) train arrival and departure times at mid-stops specified by the start time, (6) capacity constraints of running trains per unit time for track sections, and (7) the gap between the numbers of starting trains and ending trains at each station.The formulations of constraints for line planΩ are shown as follows.(  1  ) Lines and Train Stop Patterns (2) l T = v 1 T , v 2 T , … , v M T T ∈ L (3) l s T = η 1 T , η 2 T , … , η M T T ∈ L S l TFor each train T∈Ω, the line lT is selected from candidate set L and the stop pattern lsT is selected from candidate set LS(lT).(  2  ) Carriage Compositions of Trains (4) B T ∈ 8  carriages,  16  carriages ,  T ∈ ΩEach train T consists of 8 carriages or 16 carriages.(  3  ) Seat Capacity of Trains (5) F T , i , j ≤ C T ,  1 ≤ i < j ≤ M T ,  T ∈ Ωwhere FT,i,j is the number of passengers assigned on train segment T(i,j) obtained bySPAM-TBP and is not larger than the seat capacity of train T.(  4  ) Start and End Times of Trains (6) t 1 ≤ d 1 T ≤ t 2 ,  t 1 ≤ a M T T ≤ t 2 ,  T ∈ ΩThe start and end times of train T are within the horizon time t1,t2.(  5  ) Arrival and Departure Times at Mid-Stops of Trains (7) a j T = d 1 T + ∑ g = 2 j - 1 η g T t v g T s t o p + ∑ g = 1 , e = v g T , v g + 1 T j - 1 t e r u n ,  2 ≤ j ≤ M T ,  T ∈ Ω (8) d j T = d 1 T + ∑ g = 2 j η g T t v g T s t o p + ∑ g = 1 , e = v g T , v g + 1 T j - 1 t e r u n ,  2 ≤ j ≤ M T - 1 ,  T ∈ ΩFor each train T, the computations of the arrival and departure times at mid-stops on line lT are specified based on the train running times on track sections and the stop times at stations.(  6  ) Capacity Constraints of Running Trains per Unit Time for Track Sections (9) ∑ T ∈ Ω δ T e , k ≤ C p H e ,  e ∈ E ,  k = 1,2 , … , t 2 - t 1 / ∆ twhere CpHe is the upper bound on the number of running trains per unit time for track section e. Unit time is denoted as ∆t and the horizon time t1,t2 is partitioned into (t2-t1)/∆t time intervals by length ∆t (∆t is usually set to be one hour). t1+(k-1)∆t,t1+k∆t is called the kth time interval. Let δTe,k=1 if train T enters track section e within the kth time interval; otherwise δTe,k=0. This constraint can avoid too many trains passing a track section in a certain period.(  7  ) The Gap between the Numbers of Starting Trains and Ending Trains at Each Station (10) ∑ T ∈ Ω W v 1 T , v - ∑ T ∈ Ω W v M T T , v ≤ Δ w ,  T ∈ Ω ,  v ∈ Vwhere Δw≥0 is a nonnegative integer. The maximum gap between the numbers of starting trains and ending trains at a station is Δw. For any two stations u,v∈V, if station u and v are the same station, then Wu,v=1; otherwise Wu,v=0. In (10), v1T is the first station of train T and vM(T)T is the last station of train T; if v1T is the same as station v, then Wv1T,v=1. Hence ∑T∈ΩWv1T,v means the number of starting trains at station v, and similarly ∑T∈ΩWvM(T)T,v means the number of ending trains at station v. This constraint is set for convenience of rolling stock circulation by controlling the gap between the number of starting trains and that of ending trains at a station.


### 3.3. A Bilevel Optimization Model

The optimization objective in the line planning includes two parts: minimizing train operational cost and minimizing passenger travel cost. Train operational cost is represented by engine time of trains. For the trains with same engine time, the operational cost of the train with 16 carriages is higher than that of the train with 8 carriages. Hence, the engine time of the train with different carriage compositions is weighted byζT. For trains with 8 carriages, let ζT=1, and for trains with 16 carriages, let 1<ζT<2. For line plan Ω, the operational cost of all trains is expressed as follows:(11)Z1=∑T∈ΩζTaMTT-d1TPassenger travel cost consists of two parts. The first one is specified for passengers who are served and the travel cost is expressed as follows:(12)Z2=∑r,s∈RS∫t-trs∫t1t2GTrsminx,yfrsx,ydxdyThe second one is the penalty cost specified for passengers who are unserved due to the limited transport capacity. i.e.,(13)Z3=ξ∑r,s∈RS∫trs0∫t1t2GTrsminx,t-frsx,ydxdywhere ξ>1 is the penalty coefficient and is set to a large value usually. GTrsmin(x,t-) is the minimum travel cost for passengers with expected departure time x of O-D pair r,s in the ticket presale period, which is used to distinguish that the penalty cost is different for unserved passengers of different O-D pairs. Eqs. (12)-(13) can be calculated bySPAM-TBP(for more details see Su and Shi et al. [20]).Given HSR networkV,E and time-dependent demand F, a line plan Ω=T=(lT,lsT,DT,AT,BT) is optimized, satisfying constraints Eqs. (2)-(10), with the goal of minimizing a weighted sum of train operational cost Z1, passenger travel cost Z2, and penalty cost Z3. The weights are α and β for trains and passengers, respectively. Then the objective function is expressed as ZΩ=αZ1+βZ2+Z3.Based on the above description, a bilevel optimization model of the line planning with time-dependent demand and capacity constraints for HSR networks is expressed as follows.Upper Level (14) min ⁡ Z Ω = α Z 1 + β Z 2 + Z 3s.t. (2)~(10).Lower Level SPAM-TBPA line planΩ=T=(lT,lsT,DT,AT,BT) is solved in the above bilevel optimization model by determining the line lT, stop pattern lsT, arrival time sequence AT, departure time sequence DT, and carriage composition BT for each train T.


## 3.1. Modeling Assumptions

Some assumptions are made in the line planning as follows:(i)
There are two types of carriage composition for trains, i.e., 8 carriages and 16 carriages, and the seat capacities are 600 passengers and 1100 passengers, respectively.(ii)
Train classes are not considered and the train running time on each track section is given asterun  (e∈E).(iii)
The sum of dwell time and additional time for engine starting and stopping at a station for trains is given astvstop  (v∈V).(iv)
The departure and arrival times at stations of trains are designed without considering the time conflicts in operation lines.


## 3.2. Constraints

Line planning is restricted by capacity constraints of HSR networks. In particular, constraints in line planning include the following:(1) lines and train stop patterns in the candidate sets, (2) carriage compositions of trains, (3) the seat capacity of trains, (4) the start and end times of trains within the horizon time, (5) train arrival and departure times at mid-stops specified by the start time, (6) capacity constraints of running trains per unit time for track sections, and (7) the gap between the numbers of starting trains and ending trains at each station.The formulations of constraints for line planΩ are shown as follows.(  1  ) Lines and Train Stop Patterns (2) l T = v 1 T , v 2 T , … , v M T T ∈ L (3) l s T = η 1 T , η 2 T , … , η M T T ∈ L S l TFor each train T∈Ω, the line lT is selected from candidate set L and the stop pattern lsT is selected from candidate set LS(lT).(  2  ) Carriage Compositions of Trains (4) B T ∈ 8  carriages,  16  carriages ,  T ∈ ΩEach train T consists of 8 carriages or 16 carriages.(  3  ) Seat Capacity of Trains (5) F T , i , j ≤ C T ,  1 ≤ i < j ≤ M T ,  T ∈ Ωwhere FT,i,j is the number of passengers assigned on train segment T(i,j) obtained bySPAM-TBP and is not larger than the seat capacity of train T.(  4  ) Start and End Times of Trains (6) t 1 ≤ d 1 T ≤ t 2 ,  t 1 ≤ a M T T ≤ t 2 ,  T ∈ ΩThe start and end times of train T are within the horizon time t1,t2.(  5  ) Arrival and Departure Times at Mid-Stops of Trains (7) a j T = d 1 T + ∑ g = 2 j - 1 η g T t v g T s t o p + ∑ g = 1 , e = v g T , v g + 1 T j - 1 t e r u n ,  2 ≤ j ≤ M T ,  T ∈ Ω (8) d j T = d 1 T + ∑ g = 2 j η g T t v g T s t o p + ∑ g = 1 , e = v g T , v g + 1 T j - 1 t e r u n ,  2 ≤ j ≤ M T - 1 ,  T ∈ ΩFor each train T, the computations of the arrival and departure times at mid-stops on line lT are specified based on the train running times on track sections and the stop times at stations.(  6  ) Capacity Constraints of Running Trains per Unit Time for Track Sections (9) ∑ T ∈ Ω δ T e , k ≤ C p H e ,  e ∈ E ,  k = 1,2 , … , t 2 - t 1 / ∆ twhere CpHe is the upper bound on the number of running trains per unit time for track section e. Unit time is denoted as ∆t and the horizon time t1,t2 is partitioned into (t2-t1)/∆t time intervals by length ∆t (∆t is usually set to be one hour). t1+(k-1)∆t,t1+k∆t is called the kth time interval. Let δTe,k=1 if train T enters track section e within the kth time interval; otherwise δTe,k=0. This constraint can avoid too many trains passing a track section in a certain period.(  7  ) The Gap between the Numbers of Starting Trains and Ending Trains at Each Station (10) ∑ T ∈ Ω W v 1 T , v - ∑ T ∈ Ω W v M T T , v ≤ Δ w ,  T ∈ Ω ,  v ∈ Vwhere Δw≥0 is a nonnegative integer. The maximum gap between the numbers of starting trains and ending trains at a station is Δw. For any two stations u,v∈V, if station u and v are the same station, then Wu,v=1; otherwise Wu,v=0. In (10), v1T is the first station of train T and vM(T)T is the last station of train T; if v1T is the same as station v, then Wv1T,v=1. Hence ∑T∈ΩWv1T,v means the number of starting trains at station v, and similarly ∑T∈ΩWvM(T)T,v means the number of ending trains at station v. This constraint is set for convenience of rolling stock circulation by controlling the gap between the number of starting trains and that of ending trains at a station.


## 3.3. A Bilevel Optimization Model

The optimization objective in the line planning includes two parts: minimizing train operational cost and minimizing passenger travel cost. Train operational cost is represented by engine time of trains. For the trains with same engine time, the operational cost of the train with 16 carriages is higher than that of the train with 8 carriages. Hence, the engine time of the train with different carriage compositions is weighted byζT. For trains with 8 carriages, let ζT=1, and for trains with 16 carriages, let 1<ζT<2. For line plan Ω, the operational cost of all trains is expressed as follows:(11)Z1=∑T∈ΩζTaMTT-d1TPassenger travel cost consists of two parts. The first one is specified for passengers who are served and the travel cost is expressed as follows:(12)Z2=∑r,s∈RS∫t-trs∫t1t2GTrsminx,yfrsx,ydxdyThe second one is the penalty cost specified for passengers who are unserved due to the limited transport capacity. i.e.,(13)Z3=ξ∑r,s∈RS∫trs0∫t1t2GTrsminx,t-frsx,ydxdywhere ξ>1 is the penalty coefficient and is set to a large value usually. GTrsmin(x,t-) is the minimum travel cost for passengers with expected departure time x of O-D pair r,s in the ticket presale period, which is used to distinguish that the penalty cost is different for unserved passengers of different O-D pairs. Eqs. (12)-(13) can be calculated bySPAM-TBP(for more details see Su and Shi et al. [20]).Given HSR networkV,E and time-dependent demand F, a line plan Ω=T=(lT,lsT,DT,AT,BT) is optimized, satisfying constraints Eqs. (2)-(10), with the goal of minimizing a weighted sum of train operational cost Z1, passenger travel cost Z2, and penalty cost Z3. The weights are α and β for trains and passengers, respectively. Then the objective function is expressed as ZΩ=αZ1+βZ2+Z3.Based on the above description, a bilevel optimization model of the line planning with time-dependent demand and capacity constraints for HSR networks is expressed as follows.Upper Level (14) min ⁡ Z Ω = α Z 1 + β Z 2 + Z 3s.t. (2)~(10).Lower Level SPAM-TBPA line planΩ=T=(lT,lsT,DT,AT,BT) is solved in the above bilevel optimization model by determining the line lT, stop pattern lsT, arrival time sequence AT, departure time sequence DT, and carriage composition BT for each train T.


## 4. Algorithm

As the simulated annealing algorithm has a good adaptability and strong robustness [22, 23], it is used to solve the above optimization model. The general structure of the solution algorithm is developed as shown in Algorithm 1.Algorithm 1
Inputhigh-speed rail network V,E, and candidate sets L and LS(l),l∈L, time-dependent demand F. Outputan optimized line plan Ω∗=T=(lT,lsT,DT,AT,BT). Begin Generate an initial solution (seeDetail 1), denoted as Ω0; Check the constraints and adjustΩ0 (see Detail 2); Assign passengers onΩ0 by SPAM-TBP; Calculate the objectiveZΩ0; Let the current solution beΩ and Ω←Ω0; Let the optimized solution beΩ∗ and Ω∗←Ω0; Generate the initial temperature, denoted asT0 K←0; While the outer loop condition is satisfied do Begin1 While the inner loop condition is satisfied do Begin2 Search for a neighborhood solutionΩ′ of the current solution Ω (see Detail 3); Check the constraints and adjustΩ′ (see Detail 2); Assign passengers onΩ′ by SPAM-TBP; Calculate the objectiveZΩ′; IfZΩ′<ZΩ∗, then let Ω∗←Ω′; If “accepting condition” is satisfied, then letΩ←Ω′; End2 Drop the temperature, letTK+1←update(TK), K←K+1; End1 End(  1  ) Accepting Condition and Dropping the Temperature. In the Kth outer loop iteration, the accepting condition for the neighborhood solution Ω′ in the inner loop is expressed as follows:(15)exp⁡ZΩ-ZΩ′TK>random0,1where exp⁡(∙) is an exponential function with the natural base e and random0,1 is a random value within 0,1.The value of initial temperatureT0 needs meets the fact that the accepting probability is higher than a threshold (usually within 0.8,0.9) in the first outer loop iteration. The temperature is updated as TK+1=ϖTK, where 0<ϖ<1.(  2  ) Outer and Inner Loop Condition. The inner loop condition is a fixed number of iterations, denoted as Numiner. While the number of inner loop iterations is not larger than Numiner, repeat the inner loop. The outer loop condition includes two parts shown as follows, and the outer loop repeats while both of them are satisfied.(a)
The objective function valueZΩ∗ decreases once at least in successive θ outer loop iterations, where θ is a parameter.(b)
The number of outer loop iterations is not larger than a fixed number, denoted asNumout, i.e., K≤Numout.Some details in Algorithm1 are shown as follows.Detail 1. Generate an initial solution Ω0.The steps of generating an initial solution are shown as follows.Step 1.
For each linel∈L and each time interval with length ∆t, we construct a train with the start time within this time interval if the end time is within the horizon time t1,t2 (checking constraints Eqs. (6)-(7)). The stop pattern of each train is selected randomly from LS(l).Step 2.
For each station, if there are trains starting from here, then the start times of these trains are distributed evenly within each time interval. Then, for each train, the arrival and departure times at stops are calculated by (7)-(8).Step 3.
From Step 1 to Step 2, the line, stop pattern, arrival time sequence, and departure time sequence of each train are determined. These trains constitute a line plan without considering train carriage compositions, denoted asΩ0′.Step 4.
Passengers are assigned onΩ0′ bySPAM-TBPassuming that the seat capacity for each train is infinity and FT,i,j,1≤i<j≤M(T), T∈Ω0′ are obtained.Step 5.
Train carriage compositions are determined in this step. For each trainT∈Ω0′, if the seat capacity of 8 carriages can satisfy the passengers assigned on train T, then let train T be with 8 carriages; else if the seat capacity of 16 carriages can satisfy the passengers assigned on train T, then let train T be with 16 carriages; else, let train T with 16 carriages and new trains are added with the start times within the same time interval as train T. The required numbers of new added trains with 8 carriages and 16 carriages, respectively, are calculated as follows:(a)
Find the maximum of passenger volumes on segments of trainT, denoted as FT,i,jmax=maxFT,i,j,1≤i<j≤M(T).(b)
Let the quotient of(FT,i,jmax-CT) divided by the seat capacity of trains with 16 carriages be the number of new added trains with 16 carriages and the remainder is denoted as LFF.(c)
IfLFF exceeds the seat capacity of trains with 8 carriages, another train with 16 carriages is added.(d)
IfLFF is between 50% and 100% of the seat capacity of trains with 8 carriages, another train with 8 carriages is added.All the trains constructed in the above steps constitute a line plan, denoted asΩ0.Step 6.
For each station, if there are trains ofΩ0 starting from here, then the start times of these trains are distributed evenly within each time interval. Then, for each train of Ω0, the arrival and departure times at stops are calculated by (7)-(8).Step 7.
For each trainT of Ω0, the line l, stop pattern lsl, arrival time sequence AT and departure time sequence DT, and the carriage composition BT are all determined. Hence, let Ω0 be the initial solution.Detail 2. Check the constraints and adjust the solution.Line planning is restricted by constraints Eqs. (2)-(10). Constraints Eqs. (2)-(8) are satisfied in the constructing process of trains and constraints Eqs. (9)-(10) are checked after a solution is obtained. If some constraints are not satisfied, then some trains in the solution need adjustments to satisfy all the constraints. For adjusting the solution, we first define an index, i.e., the load factor, to evaluate the trains, and denote it as LF, which refers to the number of on-board passenger kilometers divided by the number of seat kilometers of a train. The load factor of train T is expressed as follows:(16)LFT=∑1≤i<j≤MTFT,i,jTi,j∑1≤i<j≤MTCTTi,jThe larger the load factor of a train, the higher the operational efficiency of the train.The specific adjustment method is shown as follows.Step 1.
Check constraint Eq. (9) and adjust the solution.For each track sectione∈E and the kth time interval (k=1,2,…,t2-t1/∆t), if ∑T∈ΩδTe,k>CpH(e), then select ∑T∈ΩδTe,k-CpHe trains with the lowest load factors from the trains entering track section e within this time interval. For these selected trains, we adjust the start times by putting ahead or putting off randomly. The adjustment process is shown as follows.Without loss of generality, we assume that constraints Eq. (9) is not satisfied for track section e and the kth time interval, and train T is selected to be adjusted. The time adjustment of the start time of train T is denoted as adjT and the time train T entering track section e is denoted as deT. Then the start time after adjustment is d1T+adjT. If adjT>0, the start time is put off; otherwise, if adjT<0, the start time is put ahead.Time adjustmentadjT needs to meet the following conditions:(a)
The start time after adjustment is within horizon timet1,t2:(17)t1≤d1T+adjT≤t2(b)
The end time after adjustment is within horizon timet1,t2:(18)t1≤aMTT+adjT≤t2(c)
TrainT enters track section e not within the kth time interval after adjustment:(19)deT+adjT<t1+k-1∆tordeT+adjT>t1+k∆tIf there does not exist a time adjustmentadjT meeting the above conditions, then delete the selected train T; otherwise, we define adjT=m∙∆t and search adjT in the order of m=±1,±2,⋯ with meeting the above conditions. If an adjT is searched, for the new starttime  d1T+adjT, the arrival and departure times at stops are recalculated by (7)-(8) for train T. Then, check whether constraint Eq. (9) is satisfied for other track sections and the relevant time intervals train T traversing. If they are satisfied, then the adjustment is feasible; otherwise, search adjT again and repeat the above steps. The repeat times are less than RM, which is a parameter. If they are also not satisfied after repeating RM times, then delete train T.Step 2.
Check constraint Eq. (10) and adjust the solution.For each stationv, without loss of generality, we assume that ∑T∈ΩWv1T,v≥∑T∈ΩWvM(T)T,v, and let ∆τ=∑T∈ΩWv1T,v-∑T∈ΩWvM(T)T,v.Constraint Eq. (10) requests that ∆τ≤Δw. If ∆τ=0, it is best for rolling stock circulation. Hence, the smaller ∆τ, the better from the point of rolling stock circulation. Considering that passenger demands of back and forth directions on a line are usually asymmetric, it may turn out that ∆τ>0 to satisfy the very asymmetric passenger demands. If ∆τ>Δw by checking, select ∆τ-Δw trains with the lowest load factors starting from station v, and delete them.Detail 3. Search for a neighborhood solution.A neighborhood solutionΩ′ is obtained by conducting some strategies on the current solution Ω according to the following steps.(1)
Reduce carriages of trainsFor each train with 16 carriages, if the load factor is lower than a threshold (45%, for example), then the composition of the train reduces to 8 carriages.(2)
Delete trainsFor each train with 8 carriages, if the load factor is lower than a threshold (50%, for example), then delete the train.(3)
Add trains
(a)
If there are unserved passengers after passenger assignment on solutionΩ, these passengers are taken as new passenger demand. New trains are constructed to satisfy these demands using the method of generating an initial solution and then added.(b)
For each linel∈L, if the average load factor of trains on line l is higher than a threshold (80%, for example), then add a train with 8 carriages on this line. The train with the highest load factor on this line is denoted as T∗. For the added train, its stop pattern is same as train T∗, and the start time is set randomly within the time interval where train T∗ starts.(4)
Increase carriages of trainsFor each train with 8 carriages, if the load factor is higher than a threshold (90%, for example), then the composition of the train increases to 16 carriages according to a certain probability (10%, for example).(5)
Adjust the start time of trainsFor each train of the line planΩ, put ahead or put off randomly the start time by some time (5 min, for example) with a certain probability (30%, for example). And then the arrival and departure times at stops of the train are recalculated by (7)-(8).According to the above implementation details, the simulated annealing method is quite suitable for solving the model. The core of the simulated annealing method is the search of neighborhood solution and the search process is designed to adjust the components of trains, which matches well with the feature of the line plan structure and meets the corresponding constraints. Although the neighborhood solution is not certainly better than the current solution, some positive improvements based on the train load factors are done on the current solution in the search process. Hence, after finite iterations, well-behaved solutions can be obtained.


## 5. Application to the Chinese HSR Network

In this section, we adopt the HSR network in China in 2014 to test our optimization model and algorithm. The line planning algorithm was coded by C# and implemented on a 3.20 GHz PC with 8 GB of RAM.


### 5.1. Case Data and Parameters

The HSR network in China in 2014 is shown in Figure2 and 13 HSR corridors are included in the HSR network used in this experiment, shown in Table 2. There are 337 stations and 363 track sections with length 16,449 km in this HSR network. The train running time terun on each track section (e∈E) was estimated based on the actual timetable. Let parameters tvstop=6 min (v∈V) and ∆t=1h.Table 2
HSR corridors.
Corridor Origin-Destination station Length (km) Beijing-Shanghai Beijingnan-Shanghaihongqiao 1318 Beijing-Shenzhen Beijingxi-Shenzhenbei 2400 Beijing-Ha’erbin-Dalian Beijingnan- Haerbinxi-Dalian 2461 Shanghai-Hangzhou-Shenzhen Shanghaihongqiao - Shenzhenbei 1864 Nanjing-Hangzhou Nanjingnan-Hangzhou 304 Wuhan-Nanchang-Fuzhou Wuhan-Fuzhou 1028 Shanghai-Kunming (partial) Shanghaihongqiao -Xinhuangxi 1503 Hengyang-Liuzhou Hengyangdong-Beihai 1088 Shanghai-Nanjing-Chengdu Shanghaihongqiao -Chengdudong 2438 Zhengzhou-Xi’an Zhengzhou-Baojinan 779 Jinan-Qingdao Jinan-Qingdao 475 Hefei-Bengbu Hefei-Bengbu 132 Shijiazhuang-Taiyuan-Xi’an Shijiazhuang-Xi’anbei 811Figure 2
HSR network of China in 2014.Time-dependent demand was obtained based on the historical statistical data of the railway passenger ticketing system in China. The total number of passengers used in this experiment is 1,830,650. Passengers with the origin and destination on the same HSR corridor are called corridor passengers. There are 1,621,224 corridor passengers, accounting for 88.56% of the total demand. Hence, most of the demands are corridor passengers. Passengers with the origin and destination on different HSR corridors are called over-line passengers.Let weightω1=3, weight ω2=1, and weight ω3=2 for passenger travel cost. Let ζT=1 for trains with 8 carriages and ζT=1.5 for trains with 16 carriages. Let the penalty coefficient ξ=10000. Let the gap in (10) Δw=2. Based on the analysis of the numerical experiment and the study of Kaspi and Raviv [10], let the objective function weight β=1, and the objective function weight α was set to three different values: 5,000, 10,000, and 15,000.


### 5.2. Result Analysis

The generation of the initial solution has a certain randomness. To reduce the influences of the initial solution to the optimized solution, multiple initial solutions were constructed and Algorithm1 was implemented for each one of them. For three different weight values α=5,000, α=10,000, and α=15,000, three optimized solutions were obtained, denoted as Ω1∗, Ω2∗, and Ω3∗, respectively. For contrastive analysis, the actual line plan of the HSR network used in China in 2014 is denoted as Ωa. 20 initial solutions were used in this experiment, shown in Table 3, and the optimized solutions are shown in Table 4.Table 3
Initial solutions.
Index Z 1 Z 2 Z 3 unserved passengers (passenger) Number of trains (train) Average time deviation (min) 1 395,547 1.88 × 10 9 1.45 × 10 10 12,421 1,762 30.69 2 392,444 1.99 × 10 9 1.12 × 10 10 7,386 1,772 32.62 3 394,468 1.89 × 10 9 1.02 × 10 10 7,822 1,746 30.93 4 389,144 2.01 × 10 9 1.72 × 10 10 10,022 1,744 33.02 5 392,257 2.05 × 10 9 1.95 × 10 10 10,819 1,768 33.69 6 393,521 2.05 × 10 9 1.37 × 10 10 7,982 1,768 33.67 7 393,016 2.01 × 10 9 1.12 × 10 10 6,098 1,766 32.97 8 395,370 1.82 × 10 9 1.23 × 10 10 8,594 1,770 29.68 9 392,905 1.92 × 10 9 1.29 × 10 10 8,099 1,748 31.36 10 387,881 1.98 × 10 9 2.51 × 10 10 13,955 1,732 32.58 11 396,681 1.96 × 10 9 1.22 × 10 10 8,751 1,772 32.09 12 394,944 1.91 × 10 9 1.34 × 10 10 7,944 1,778 31.30 13 396,061 1.92 × 10 9 8.90 × 10 9 6,921 1,764 31.43 14 391,837 1.93 × 10 9 1.60 × 10 10 7,616 1,748 31.57 15 395,064 1.97 × 10 9 1.59 × 10 10 9,422 1,770 32.28 16 395,436 1.96 × 10 9 1.63 × 10 10 9,502 1,768 32.11 17 392,703 2.02 × 10 9 1.37 × 10 10 9,422 1,750 33.06 18 392,403 1.91 × 10 9 9.69 × 10 9 7,215 1,764 31.22 19 395,106 1.95 × 10 9 1.81 × 10 10 13,532 1,764 31.92 20 391,706 2.00 × 10 9 1.44 × 10 10 9,727 1,738 32.85  Average value 393,424 1.96 × 10 9 1.43 × 10 10 9,163 1,760 32.00Table 4
Optimized solutions.
Solution Z 1 Z 2 Z 3 unserved passengers(passenger) Number of Trains (train) Average time deviation (min) Average load factor Ω 1 ∗ 419,487 1.42 × 10 9 2.10 × 10 8 70 1,836 22.40 69.85% Ω 2 ∗ 404,862.5 1.50 × 10 9 2.20 × 10 8 73 1,734 23.45 72.51% Ω 3 ∗ 389,167 1.61 × 10 9 2.84 × 10 8 157 1,652 25.89 76.02% Ω a - - - - 1,746 - 72.32%(  1  ) Comparison between the Initial Solution and the Optimized Solutions. According to Tables 3 and 4, the initial solutions and the optimized solutions are compared and analyzed. According to Table 3, we find the following for the initial solutions: (i) the average number of trains is 1,760 and the average train operational cost is 393,424, (ii) the average time deviation of passengers is 32 min and the average travel cost of passengers is 1.96×109, and (iii) there are 9,163 average unserved passengers and the average penalty cost is 1.43×1010. The results of the 20 initial solutions are similar according to the evaluation indexes and this is because they need to meet the same time-dependent demand. But they also have diversity for the randomness in the generating process.Comparing with the initial solutions, some changes of the optimized solutions according to Table4 are found as follows: (i) the number of trains of Ω1∗ is 1,836 and the train operational cost is 419,487, which are more than those of the initial solutions, (ii) the number of trains of Ω3∗ is 1,652 and the train operational cost is 389,167, which are less than those of the initial solutions, (iii) for the three cases, travel cost of passengers reduces evidently, and the unserved passengers are less than 200 which results in the fact that the penalty cost reduces over two orders of magnitude.In summary, forΩ1∗, Ω2∗, and Ω3∗, with weight α increasing, the change rules of evaluation indexes are shown as follows:(a)
Train operational cost reduces gradually, and the number of trains decreases gradually, and the average load factor of trains becomes higher gradually.(b)
Travel cost of passengers increases gradually and the average time deviation of passengers increases gradually.Hence, we can obtain an optimized solution with lower train operational cost by increasing weightα and an optimized solution with less travel cost of passengers by reducing weight α. Based on the actual needs, we can obtain different optimized line plans by adjusting weight α.(  2  ) Trains on HSR Corridors. In HSR network, the distributions of main passenger demands are regional; i.e., their travel paths are usually within each single HSR corridor. Hence we analyze the optimized line plans through the trains on different HSR corridors. For ease of description, a train with the start station and end station on two different HSR corridors is called an over-line train and the corridors over-line trains traversing are denoted asOL. The number of trains, average load factor (see (16)), and average time deviation on HSR corridors are shown in Table 5. The numbers of trains with different carriage compositions on HSR corridors are shown in Table 6. According to Tables 5 and 6, the results are analyzed as follows.Table 5
The number of trains (train)/average load factor/average time deviation (min) on HSR corridors.
Corridor Ω 1 ∗ Ω 2 ∗ Ω 3 ∗ Ωa OL 362/68.64%/39.45 352/70.52%/39.73 348/73.17%/41.77 389/73.10%/- Beijing-Shanghai 116/77.17% /14.17 108/77.62%/14.64 104/79.14%/17.05 106/76.66%/- Beijing-Shenzhen 232/66.47% /19.66 194/72.78%/21.12 164/75.31%/24.70 269/50.98%/- Beijing-Ha’erbin-Dalian 302/64.08% /18.84 290/66.99%/19.71 250/74.34%/22.82 360/60.25%/- Shanghai-Hangzhou-Shenzhen 320/73.24%/17.59 306/75.38%/18.16 304/78.64%/20.02 222/83.93%/- Nanjing-Hangzhou 12/76.95%/13.31 14/76.68%/13.73 12/77.15%/13.86 13/39.33%/- Wuhan-Nanchang-Fuzhou 34/54.31%/70.73 32/52.72%/63.73 28/62.91%/73.02 7/57.67%/- Shanghai-Kunming (partial) 22/64.61%/61.03 20/69.79%/68.85 28/66.75%/81.97 11/64.15%/- Hengyang-Liuzhou 42/64.53%/41.51 40/66.15%/42.37 40/70.98%/41.39 33/74.51%/- Shanghai-Nanjing-Chengdu 284/70.03%/22.07 276/71.45%/21.25 270/77.84%/24.29 237/73.10%/- Zhengzhou-Xi’an 40/62.96%/36.95 36/63.71%/35.50 36/68.37%/43.89 28/44.01%/- Jinan-Qingdao 46/78.27%/27.90 46/78.76%/26.11 46/79.59%/28.10 44/77.02%/- Hefei-Bengbu 8/59.77%/29.76 6/69.69%/29.97 8/71.08%/29.72 6/81.48%/- Shijiazhuang-Taiyuan-Xi’an 16/53.10%/25.72 14/52.34%/25.31 14/56.45%/28.47 21/75.03%/-Table 6
The number of trains with different carriage compositions on HSR corridors (train).
Corridor Ω 1 ∗ Ω 2 ∗ Ω 3 ∗ Ω a 8 carriages 16 carriages 8carriages 16carriages 8carriages 16carriages 8carriages 16carriages OL 241 121 230 122 235 113 201 188 Beijing-Shanghai 47 69 38 70 38 66 30 76 Beijing-Shenzhen 168 64 127 67 92 72 123 146 Beijing-Ha’erbin-Dalian 265 37 264 26 233 17 360 - Shanghai-Hangzhou-Shenzhen 225 95 217 89 249 55 164 58 Nanjing-Hangzhou 5 7 7 7 8 4 8 5 Wuhan-Nanchang-Fuzhou 33 1 30 2 28 0 7 - Shanghai-Kunming (partial) 15 7 13 7 25 3 4 7 Hengyang-Liuzhou 34 8 33 7 36 4 33 - Shanghai-Nanjing-Chengdu 221 63 222 54 240 30 219 18 Zhengzhou-Xi’an 32 8 29 7 32 4 19 9 Jinan-Qingdao 24 22 24 22 26 20 23 21 Hefei-Bengbu 7 1 5 1 7 1 4 2 Shijiazhuang-Taiyuan-Xi’an 16 0 14 0 14 0 20 1  Sum 1,333 503 1,253 481 1,263 389 1215 531(a) Over-Line Trains. Over-line passengers are widely distributed on the HSR network and it is complicated to organize over-line trains to satisfy these passengers. For Ω1∗, Ω2∗, and Ω3∗, the numbers of trains are about 350, and trains with 8 carriages are almost twice the trains with 16 carriages. The average load factors are about 70%, and the average time deviations are about 40 min. Comparing with Ωa, the numbers of over-line trains in optimized line plans reduce slightly and the ratios of trains with 8 carriages increase. This adjustment can apply to scattered passenger demand in space and time-varying demand for each OD pair and reduce the waste of transport capacity and decrease the departure time deviation of demands.(b) Trains on Beijing-Shanghai Corridor. Beijing-Shanghai corridor lies on the wealthy eastern seaboard of China and these areas are densely populated. For Ω1∗, Ω2∗, and Ω3∗, the numbers of trains on this corridor are 116, 108, and 104, respectively, and more than half of them are trains with 16 carriages. The average load factors of trains are above 77%. The average time deviations are within 20 min, which show that the start times of trains are rational and satisfy the time-dependent demand well.(c) Trains on Beijing-Shenzhen Corridor. Beijing-Shenzhen corridor lies in central China from the north to the south, which is large-span and long-haul. The numbers of trains on this corridor are 232, 194, and 164 for Ω1∗, Ω2∗, and Ω3∗, respectively. It is 269 for Ωa, which is higher than that of the optimized solutions.Comparing withΩa, the numbers of trains with 16 carriages on this corridor reduce by more than half for Ω1∗ and Ω2∗, but trains with 8 carriages increase. In Ω3∗, trains with 8 carriages and 16 carriages on this corridor both decrease. The average load factor of Ωa on this corridor is a little low, but the average load factors of trains for the three optimized solutions all increase to an acceptable level. The average time deviations are within 25 min on this corridor for Ω1∗, Ω2∗, and Ω3∗, which shows that the start times of trains are rational and satisfy the time-dependent demand well.(d) Trains on Shanghai-Hangzhou-Shenzhen Corridor.Shanghai-Hangzhou-Shenzhen corridor is on the wealthy southeastern seaboard. These areas are densely populated, similar to Beijing-Shanghai corridor. For Ωa, the number of trains on this corridor is 222 and average load factor of trains is 83.93%. More trains with 8 carriages in the three optimized solutions can decrease the departure time deviation of passengers, especially for the dense demands, and the average load factors for the three optimized solutions are above 73%, which are suitable levels. The average time deviations are about 20 min, which shows that the start times of trains are rational and satisfy the time-dependent demand well.(  3  ) Train Distribution with Line Length. By the line length, trains of Ω1∗, Ω2∗, and Ω3∗ are classified into several groups, respectively, shown in Figure 3. The number of trains with line lengths within 1,200 km accounts for more than 80% for each optimized solution and the journey time of those trains is usually less than 5 h. In this time range, the HSR service has great competitive advantages in the transport markets, and if the journey time is longer, passengers prefer to travel by air [24]. Comparing with Ωa, the ratio of trains with line lengths less than 300 km is low and the ratio of medium and long-haul trains is high for the optimized solutions, which can reduce transfers and increase direct passengers and then decrease the travel cost of passengers.Figure 3
Train distribution according to the line length.


### 5.3. Detail Presentation of the Results on Beijing-Shenzhen Corridor

Some details of the optimized solutions are too large to show for the whole large-scale HSR network; hence we take Beijing-Shenzhen corridor (see Figure4) as a representation. There are actually 40 stations and 39 track sections on this corridor, but for simplicity small stations are not shown in Figure 4. The details of the optimized solutions on this corridor are shown and analyzed as follows.Figure 4
Beijing-Shenzhen corridor.(  1  ) The Number of Running Trains per Unit Time on Each Track Section. For each optimized solution, given track section e and the kth time interval, ∑T∈ΩδTe,k is the number of running trains and is calculated to check constraint Eq. (9). The upper bound CpH(e) is set as 12 for track sections of this corridor. And the numbers on each track section of this corridor are shown in Table 7. From Table 7, the numbers of running trains per unit time for track sections on this corridor are less than 12, which shows constraint Eq. (9) is satisfied strictly.Table 7
The number of running trains per unit time for track sections on Beijing-Shenzhen corridor ofΩ1∗/Ω2∗/Ω3∗ (train).
(a) Track section Number of trains per unit time [7:00,7:59] [8:00,8:59] [9:00,9:59] [10:00,10:59] [11:00,11:59] [12:00,12:59] [13:00,13:59] [14:00,14:59] Beijingxi - Baodingdong 9/9/8 2/4/3 6/6/5 6/4/6 5/4/4 4/5/4 5/4/3 8/6/7 Baodingdong - Shijiazhuang 5/5/5 5/7/6 3/3/4 7/6/5 5/4/3 5/5/6 5/4/3 5/4/4 Shijiazhuang - Handandong 1/0/0 3/4/3 3/2/3 3/3/3 5/5/5 1/1/1 3/2/2 4/3/3 Handandong - Anyangdong 1/0/0 2/1/2 4/5/4 1/1/1 5/6/6 2/1/1 2/2/2 4/3/3 Anyangdong - Zhengzhoudong 0/0/0 0/0/0 2/2/2 3/3/3 3/3/3 4/4/4 1/0/1 3/3/2 Zhengzhoudong - Xuchangdong 1/2/2 1/1/1 0/0/0 5/4/6 2/3/0 5/5/7 5/5/4 4/5/5 Xuchangdong - Zhumadianxi 1/1/1 1/2/2 0/0/0 3/3/2 3/3/4 4/5/5 7/6/5 3/2/6 Zhumadianxi - Xinyangdong 0/1/1 1/1/1 1/1/1 1/1/1 5/5/5 1/2/2 5/6/5 5/4/4 Xinyangdong - Xiaoganbei 0/0/0 0/1/2 1/3/1 1/0/1 3/2/2 3/4/4 4/4/4 6/5/4 Xiaoganbei - Wuhan 0/0/0 0/1/1 1/2/2 1/1/1 2/1/2 4/5/4 1/4/2 6/4/6 Wuhan - Xianningbei 4/5/4 4/1/1 5/7/6 6/7/8 3/1/2 8/8/7 5/3/3 6/6/5 Xianningbei - Yueyangdong 3/3/2 2/3/3 5/5/6 7/6/5 4/4/4 6/4/5 7/6/5 4/6/6 Yueyangdong - Changshanan 0/2/2 4/5/3 4/2/3 8/6/5 6/6/7 1/2/3 9/7/8 4/4/1 Changshanan - Hengyangdong 7/5/4 2/3/2 5/4/4 4/5/5 10/5/5 6/7/5 4/3/5 9/7/6 Hengyangdong - Chenzhouxi 2/1/1 4/4/2 4/4/2 4/4/4 5/5/6 8/7/5 5/3/4 6/5/5 Chenzhouxi - Guangzhounan 0/0/0 4/4/2 2/2/2 5/5/3 6/3/4 6/5/5 8/8/7 3/2/2 Guangzhounan - Shenzhenbei 5/4/2 2/3/2 5/4/3 6/5/4 4/2/4 4/5/3 2/2/4 5/5/4  (b) Track section Number of trains per unit time [15:00,15:59] [16:00,16:59] [17:00,17:59] [18:00,18:59] [19:00,19:59] [20:00,20:59] [21:00,21:59] [22:00,22:59] [23:00,23:59] Beijingxi - Baodingdong 4/6/4 4/4/5 2/2/1 6/6/5 4/3/4 1/1/1 2/1/1 1/1/1 0/0/0 Baodingdong - Shijiazhuang 5/6/5 5/5/6 3/3/2 5/5/5 5/4/4 2/2/1 3/2/2 0/0/0 1/1/1 Shijiazhuang - Handandong 3/3/4 1/1/0 5/5/5 0/0/0 4/4/4 2/1/1 0/1/1 0/0/0 0/0/0 Handandong - Anyangdong 3/2/2 3/3/3 2/1/1 3/4/4 2/2/3 2/3/2 2/1/1 0/0/0 0/0/0 Anyangdong - Zhengzhoudong 4/3/3 2/2/3 1/1/0 4/4/4 0/0/0 4/4/4 1/1/1 0/0/0 0/0/0 Zhengzhoudong - Xuchangdong 8/5/4 3/3/3 6/5/4 1/1/2 3/3/3 1/1/1 0/0/0 0/0/0 0/0/0 Xuchangdong - Zhumadianxi 7/7/3 4/3/3 5/3/5 2/3/1 4/4/4 0/0/1 1/1/0 0/0/0 0/0/0 Zhumadianxi - Xinyangdong 5/4/5 7/6/5 4/3/2 5/4/5 2/1/1 2/3/3 1/1/1 0/0/0 0/0/0 Xinyangdong - Xiaoganbei 4/3/5 6/7/5 4/3/3 5/2/5 2/4/1 3/4/3 1/0/1 1/1/1 0/0/0 Xiaoganbei - Wuhan 4/3/3 7/6/5 6/5/5 3/2/2 4/4/4 2/1/2 2/3/2 1/1/1 0/0/0 Wuhan - Xianningbei 8/9/9 5/3/5 6/4/2 4/4/4 4/4/2 1/1/1 1/0/1 0/0/0 0/0/0 Xianningbei - Yueyangdong 8/7/7 6/4/5 5/4/3 6/5/4 4/3/3 2/2/1 1/1/1 0/0/0 0/0/0 Yueyangdong - Changshanan 6/6/7 8/8/8 7/5/5 5/3/3 7/5/4 1/3/1 2/1/2 0/0/0 0/0/0 Changshanan - Hengyangdong 2/5/4 7/6/7 7/4/4 7/6/5 6/4/4 5/4/2 0/0/0 0/0/0 0/0/0 Hengyangdong - Chenzhouxi 6/4/5 5/4/4 7/7/6 5/4/6 7/6/4 5/4/3 4/3/2 0/0/0 0/0/0 Chenzhouxi - Guangzhounan 6/5/7 5/4/2 5/5/7 8/7/6 6/5/5 6/4/3 7/5/4 0/1/0 0/0/0 Guangzhounan - Shenzhenbei 5/5/3 4/3/3 5/5/5 2/2/2 6/5/5 3/2/2 4/3/2 0/1/1 0/0/0(  2  ) The Starting and Ending Trains at Each Station with Starting Capacity. The numbers of starting and ending trains at each station with starting capacity for the optimized solutions are shown in Table 8. Constraint Eq. (10) requests that the gap between the number of starting trains and that of ending trains at a station is not larger than Δw (Δw=2). From Table 8, for each optimized solution, the number of starting trains is equal to that of ending trains at most stations except for Guangzhounan station and Shenzhenbei station (the gap is 1 for them and the data are underlined), and they all meet constraint Eq. (10) strictly.Table 8
The numbers of starting and ending trains at each station with starting capacity on Beijing-Shenzhen corridor (train).
Station Ω 1 ∗ Ω 2 ∗ Ω 3 ∗ Ω a Starting Ending Starting Ending Starting Ending Starting Ending Beijingxi 69 69 66 66 62 62 78 76 Shijiazhuang 8 8 6 6 3 3 9 11 Handandong 6 6 5 5 5 5 6 6 zhengzhoudong 16 16 16 16 16 16 13 16 Xinyangdong 3 3 1 1 1 1 2 2 Wuhan 80 80 78 78 70 70 62 64 Yueyangdong 2 2 2 2 2 2 2 2 Changshanan 25 25 19 19 16 16 32 34 Guangzhounan 75 75 63 63 54 53 90 91 Shenzhenbei 98 98 91 91 82 83 90 90(  3  ) Line Plan Diagram. The space-time line plan diagrams of trains in Ω1∗, Ω2∗, and Ω3∗ on Beijing-Shenzhen corridor are shown in Figures 5–7, respectively. Every line in the diagrams represents a train. For simplicity, the median between the arrival time and the departure time of each train at each intermediate stop is marked in the diagrams. From Figures 5–7, the train distributions on the diagram become less dense, which results in fewer choices for passengers. Such law also can be shown in the data of this corridor in Table 5, i.e., decreasing trains and increasing time deviation and load factor from Ω1∗ to Ω3∗.Figure 5
Space-time diagram of trains inΩ1∗ on Beijing-Shenzhen corridor (from Beijing to Shenzhen).Figure 6
Space-time diagram of trains inΩ2∗ on Beijing-Shenzhen corridor (from Beijing to Shenzhen).Figure 7
Space-time diagram of trains inΩ3∗ on Beijing-Shenzhen corridor (from Beijing to Shenzhen).


## 5.1. Case Data and Parameters

The HSR network in China in 2014 is shown in Figure2 and 13 HSR corridors are included in the HSR network used in this experiment, shown in Table 2. There are 337 stations and 363 track sections with length 16,449 km in this HSR network. The train running time terun on each track section (e∈E) was estimated based on the actual timetable. Let parameters tvstop=6 min (v∈V) and ∆t=1h.Table 2
HSR corridors.
Corridor Origin-Destination station Length (km) Beijing-Shanghai Beijingnan-Shanghaihongqiao 1318 Beijing-Shenzhen Beijingxi-Shenzhenbei 2400 Beijing-Ha’erbin-Dalian Beijingnan- Haerbinxi-Dalian 2461 Shanghai-Hangzhou-Shenzhen Shanghaihongqiao - Shenzhenbei 1864 Nanjing-Hangzhou Nanjingnan-Hangzhou 304 Wuhan-Nanchang-Fuzhou Wuhan-Fuzhou 1028 Shanghai-Kunming (partial) Shanghaihongqiao -Xinhuangxi 1503 Hengyang-Liuzhou Hengyangdong-Beihai 1088 Shanghai-Nanjing-Chengdu Shanghaihongqiao -Chengdudong 2438 Zhengzhou-Xi’an Zhengzhou-Baojinan 779 Jinan-Qingdao Jinan-Qingdao 475 Hefei-Bengbu Hefei-Bengbu 132 Shijiazhuang-Taiyuan-Xi’an Shijiazhuang-Xi’anbei 811Figure 2
HSR network of China in 2014.Time-dependent demand was obtained based on the historical statistical data of the railway passenger ticketing system in China. The total number of passengers used in this experiment is 1,830,650. Passengers with the origin and destination on the same HSR corridor are called corridor passengers. There are 1,621,224 corridor passengers, accounting for 88.56% of the total demand. Hence, most of the demands are corridor passengers. Passengers with the origin and destination on different HSR corridors are called over-line passengers.Let weightω1=3, weight ω2=1, and weight ω3=2 for passenger travel cost. Let ζT=1 for trains with 8 carriages and ζT=1.5 for trains with 16 carriages. Let the penalty coefficient ξ=10000. Let the gap in (10) Δw=2. Based on the analysis of the numerical experiment and the study of Kaspi and Raviv [10], let the objective function weight β=1, and the objective function weight α was set to three different values: 5,000, 10,000, and 15,000.


## 5.2. Result Analysis

The generation of the initial solution has a certain randomness. To reduce the influences of the initial solution to the optimized solution, multiple initial solutions were constructed and Algorithm1 was implemented for each one of them. For three different weight values α=5,000, α=10,000, and α=15,000, three optimized solutions were obtained, denoted as Ω1∗, Ω2∗, and Ω3∗, respectively. For contrastive analysis, the actual line plan of the HSR network used in China in 2014 is denoted as Ωa. 20 initial solutions were used in this experiment, shown in Table 3, and the optimized solutions are shown in Table 4.Table 3
Initial solutions.
Index Z 1 Z 2 Z 3 unserved passengers (passenger) Number of trains (train) Average time deviation (min) 1 395,547 1.88 × 10 9 1.45 × 10 10 12,421 1,762 30.69 2 392,444 1.99 × 10 9 1.12 × 10 10 7,386 1,772 32.62 3 394,468 1.89 × 10 9 1.02 × 10 10 7,822 1,746 30.93 4 389,144 2.01 × 10 9 1.72 × 10 10 10,022 1,744 33.02 5 392,257 2.05 × 10 9 1.95 × 10 10 10,819 1,768 33.69 6 393,521 2.05 × 10 9 1.37 × 10 10 7,982 1,768 33.67 7 393,016 2.01 × 10 9 1.12 × 10 10 6,098 1,766 32.97 8 395,370 1.82 × 10 9 1.23 × 10 10 8,594 1,770 29.68 9 392,905 1.92 × 10 9 1.29 × 10 10 8,099 1,748 31.36 10 387,881 1.98 × 10 9 2.51 × 10 10 13,955 1,732 32.58 11 396,681 1.96 × 10 9 1.22 × 10 10 8,751 1,772 32.09 12 394,944 1.91 × 10 9 1.34 × 10 10 7,944 1,778 31.30 13 396,061 1.92 × 10 9 8.90 × 10 9 6,921 1,764 31.43 14 391,837 1.93 × 10 9 1.60 × 10 10 7,616 1,748 31.57 15 395,064 1.97 × 10 9 1.59 × 10 10 9,422 1,770 32.28 16 395,436 1.96 × 10 9 1.63 × 10 10 9,502 1,768 32.11 17 392,703 2.02 × 10 9 1.37 × 10 10 9,422 1,750 33.06 18 392,403 1.91 × 10 9 9.69 × 10 9 7,215 1,764 31.22 19 395,106 1.95 × 10 9 1.81 × 10 10 13,532 1,764 31.92 20 391,706 2.00 × 10 9 1.44 × 10 10 9,727 1,738 32.85  Average value 393,424 1.96 × 10 9 1.43 × 10 10 9,163 1,760 32.00Table 4
Optimized solutions.
Solution Z 1 Z 2 Z 3 unserved passengers(passenger) Number of Trains (train) Average time deviation (min) Average load factor Ω 1 ∗ 419,487 1.42 × 10 9 2.10 × 10 8 70 1,836 22.40 69.85% Ω 2 ∗ 404,862.5 1.50 × 10 9 2.20 × 10 8 73 1,734 23.45 72.51% Ω 3 ∗ 389,167 1.61 × 10 9 2.84 × 10 8 157 1,652 25.89 76.02% Ω a - - - - 1,746 - 72.32%(  1  ) Comparison between the Initial Solution and the Optimized Solutions. According to Tables 3 and 4, the initial solutions and the optimized solutions are compared and analyzed. According to Table 3, we find the following for the initial solutions: (i) the average number of trains is 1,760 and the average train operational cost is 393,424, (ii) the average time deviation of passengers is 32 min and the average travel cost of passengers is 1.96×109, and (iii) there are 9,163 average unserved passengers and the average penalty cost is 1.43×1010. The results of the 20 initial solutions are similar according to the evaluation indexes and this is because they need to meet the same time-dependent demand. But they also have diversity for the randomness in the generating process.Comparing with the initial solutions, some changes of the optimized solutions according to Table4 are found as follows: (i) the number of trains of Ω1∗ is 1,836 and the train operational cost is 419,487, which are more than those of the initial solutions, (ii) the number of trains of Ω3∗ is 1,652 and the train operational cost is 389,167, which are less than those of the initial solutions, (iii) for the three cases, travel cost of passengers reduces evidently, and the unserved passengers are less than 200 which results in the fact that the penalty cost reduces over two orders of magnitude.In summary, forΩ1∗, Ω2∗, and Ω3∗, with weight α increasing, the change rules of evaluation indexes are shown as follows:(a)
Train operational cost reduces gradually, and the number of trains decreases gradually, and the average load factor of trains becomes higher gradually.(b)
Travel cost of passengers increases gradually and the average time deviation of passengers increases gradually.Hence, we can obtain an optimized solution with lower train operational cost by increasing weightα and an optimized solution with less travel cost of passengers by reducing weight α. Based on the actual needs, we can obtain different optimized line plans by adjusting weight α.(  2  ) Trains on HSR Corridors. In HSR network, the distributions of main passenger demands are regional; i.e., their travel paths are usually within each single HSR corridor. Hence we analyze the optimized line plans through the trains on different HSR corridors. For ease of description, a train with the start station and end station on two different HSR corridors is called an over-line train and the corridors over-line trains traversing are denoted asOL. The number of trains, average load factor (see (16)), and average time deviation on HSR corridors are shown in Table 5. The numbers of trains with different carriage compositions on HSR corridors are shown in Table 6. According to Tables 5 and 6, the results are analyzed as follows.Table 5
The number of trains (train)/average load factor/average time deviation (min) on HSR corridors.
Corridor Ω 1 ∗ Ω 2 ∗ Ω 3 ∗ Ωa OL 362/68.64%/39.45 352/70.52%/39.73 348/73.17%/41.77 389/73.10%/- Beijing-Shanghai 116/77.17% /14.17 108/77.62%/14.64 104/79.14%/17.05 106/76.66%/- Beijing-Shenzhen 232/66.47% /19.66 194/72.78%/21.12 164/75.31%/24.70 269/50.98%/- Beijing-Ha’erbin-Dalian 302/64.08% /18.84 290/66.99%/19.71 250/74.34%/22.82 360/60.25%/- Shanghai-Hangzhou-Shenzhen 320/73.24%/17.59 306/75.38%/18.16 304/78.64%/20.02 222/83.93%/- Nanjing-Hangzhou 12/76.95%/13.31 14/76.68%/13.73 12/77.15%/13.86 13/39.33%/- Wuhan-Nanchang-Fuzhou 34/54.31%/70.73 32/52.72%/63.73 28/62.91%/73.02 7/57.67%/- Shanghai-Kunming (partial) 22/64.61%/61.03 20/69.79%/68.85 28/66.75%/81.97 11/64.15%/- Hengyang-Liuzhou 42/64.53%/41.51 40/66.15%/42.37 40/70.98%/41.39 33/74.51%/- Shanghai-Nanjing-Chengdu 284/70.03%/22.07 276/71.45%/21.25 270/77.84%/24.29 237/73.10%/- Zhengzhou-Xi’an 40/62.96%/36.95 36/63.71%/35.50 36/68.37%/43.89 28/44.01%/- Jinan-Qingdao 46/78.27%/27.90 46/78.76%/26.11 46/79.59%/28.10 44/77.02%/- Hefei-Bengbu 8/59.77%/29.76 6/69.69%/29.97 8/71.08%/29.72 6/81.48%/- Shijiazhuang-Taiyuan-Xi’an 16/53.10%/25.72 14/52.34%/25.31 14/56.45%/28.47 21/75.03%/-Table 6
The number of trains with different carriage compositions on HSR corridors (train).
Corridor Ω 1 ∗ Ω 2 ∗ Ω 3 ∗ Ω a 8 carriages 16 carriages 8carriages 16carriages 8carriages 16carriages 8carriages 16carriages OL 241 121 230 122 235 113 201 188 Beijing-Shanghai 47 69 38 70 38 66 30 76 Beijing-Shenzhen 168 64 127 67 92 72 123 146 Beijing-Ha’erbin-Dalian 265 37 264 26 233 17 360 - Shanghai-Hangzhou-Shenzhen 225 95 217 89 249 55 164 58 Nanjing-Hangzhou 5 7 7 7 8 4 8 5 Wuhan-Nanchang-Fuzhou 33 1 30 2 28 0 7 - Shanghai-Kunming (partial) 15 7 13 7 25 3 4 7 Hengyang-Liuzhou 34 8 33 7 36 4 33 - Shanghai-Nanjing-Chengdu 221 63 222 54 240 30 219 18 Zhengzhou-Xi’an 32 8 29 7 32 4 19 9 Jinan-Qingdao 24 22 24 22 26 20 23 21 Hefei-Bengbu 7 1 5 1 7 1 4 2 Shijiazhuang-Taiyuan-Xi’an 16 0 14 0 14 0 20 1  Sum 1,333 503 1,253 481 1,263 389 1215 531(a) Over-Line Trains. Over-line passengers are widely distributed on the HSR network and it is complicated to organize over-line trains to satisfy these passengers. For Ω1∗, Ω2∗, and Ω3∗, the numbers of trains are about 350, and trains with 8 carriages are almost twice the trains with 16 carriages. The average load factors are about 70%, and the average time deviations are about 40 min. Comparing with Ωa, the numbers of over-line trains in optimized line plans reduce slightly and the ratios of trains with 8 carriages increase. This adjustment can apply to scattered passenger demand in space and time-varying demand for each OD pair and reduce the waste of transport capacity and decrease the departure time deviation of demands.(b) Trains on Beijing-Shanghai Corridor. Beijing-Shanghai corridor lies on the wealthy eastern seaboard of China and these areas are densely populated. For Ω1∗, Ω2∗, and Ω3∗, the numbers of trains on this corridor are 116, 108, and 104, respectively, and more than half of them are trains with 16 carriages. The average load factors of trains are above 77%. The average time deviations are within 20 min, which show that the start times of trains are rational and satisfy the time-dependent demand well.(c) Trains on Beijing-Shenzhen Corridor. Beijing-Shenzhen corridor lies in central China from the north to the south, which is large-span and long-haul. The numbers of trains on this corridor are 232, 194, and 164 for Ω1∗, Ω2∗, and Ω3∗, respectively. It is 269 for Ωa, which is higher than that of the optimized solutions.Comparing withΩa, the numbers of trains with 16 carriages on this corridor reduce by more than half for Ω1∗ and Ω2∗, but trains with 8 carriages increase. In Ω3∗, trains with 8 carriages and 16 carriages on this corridor both decrease. The average load factor of Ωa on this corridor is a little low, but the average load factors of trains for the three optimized solutions all increase to an acceptable level. The average time deviations are within 25 min on this corridor for Ω1∗, Ω2∗, and Ω3∗, which shows that the start times of trains are rational and satisfy the time-dependent demand well.(d) Trains on Shanghai-Hangzhou-Shenzhen Corridor.Shanghai-Hangzhou-Shenzhen corridor is on the wealthy southeastern seaboard. These areas are densely populated, similar to Beijing-Shanghai corridor. For Ωa, the number of trains on this corridor is 222 and average load factor of trains is 83.93%. More trains with 8 carriages in the three optimized solutions can decrease the departure time deviation of passengers, especially for the dense demands, and the average load factors for the three optimized solutions are above 73%, which are suitable levels. The average time deviations are about 20 min, which shows that the start times of trains are rational and satisfy the time-dependent demand well.(  3  ) Train Distribution with Line Length. By the line length, trains of Ω1∗, Ω2∗, and Ω3∗ are classified into several groups, respectively, shown in Figure 3. The number of trains with line lengths within 1,200 km accounts for more than 80% for each optimized solution and the journey time of those trains is usually less than 5 h. In this time range, the HSR service has great competitive advantages in the transport markets, and if the journey time is longer, passengers prefer to travel by air [24]. Comparing with Ωa, the ratio of trains with line lengths less than 300 km is low and the ratio of medium and long-haul trains is high for the optimized solutions, which can reduce transfers and increase direct passengers and then decrease the travel cost of passengers.Figure 3
Train distribution according to the line length.


## 5.3. Detail Presentation of the Results on Beijing-Shenzhen Corridor

Some details of the optimized solutions are too large to show for the whole large-scale HSR network; hence we take Beijing-Shenzhen corridor (see Figure4) as a representation. There are actually 40 stations and 39 track sections on this corridor, but for simplicity small stations are not shown in Figure 4. The details of the optimized solutions on this corridor are shown and analyzed as follows.Figure 4
Beijing-Shenzhen corridor.(  1  ) The Number of Running Trains per Unit Time on Each Track Section. For each optimized solution, given track section e and the kth time interval, ∑T∈ΩδTe,k is the number of running trains and is calculated to check constraint Eq. (9). The upper bound CpH(e) is set as 12 for track sections of this corridor. And the numbers on each track section of this corridor are shown in Table 7. From Table 7, the numbers of running trains per unit time for track sections on this corridor are less than 12, which shows constraint Eq. (9) is satisfied strictly.Table 7
The number of running trains per unit time for track sections on Beijing-Shenzhen corridor ofΩ1∗/Ω2∗/Ω3∗ (train).
(a) Track section Number of trains per unit time [7:00,7:59] [8:00,8:59] [9:00,9:59] [10:00,10:59] [11:00,11:59] [12:00,12:59] [13:00,13:59] [14:00,14:59] Beijingxi - Baodingdong 9/9/8 2/4/3 6/6/5 6/4/6 5/4/4 4/5/4 5/4/3 8/6/7 Baodingdong - Shijiazhuang 5/5/5 5/7/6 3/3/4 7/6/5 5/4/3 5/5/6 5/4/3 5/4/4 Shijiazhuang - Handandong 1/0/0 3/4/3 3/2/3 3/3/3 5/5/5 1/1/1 3/2/2 4/3/3 Handandong - Anyangdong 1/0/0 2/1/2 4/5/4 1/1/1 5/6/6 2/1/1 2/2/2 4/3/3 Anyangdong - Zhengzhoudong 0/0/0 0/0/0 2/2/2 3/3/3 3/3/3 4/4/4 1/0/1 3/3/2 Zhengzhoudong - Xuchangdong 1/2/2 1/1/1 0/0/0 5/4/6 2/3/0 5/5/7 5/5/4 4/5/5 Xuchangdong - Zhumadianxi 1/1/1 1/2/2 0/0/0 3/3/2 3/3/4 4/5/5 7/6/5 3/2/6 Zhumadianxi - Xinyangdong 0/1/1 1/1/1 1/1/1 1/1/1 5/5/5 1/2/2 5/6/5 5/4/4 Xinyangdong - Xiaoganbei 0/0/0 0/1/2 1/3/1 1/0/1 3/2/2 3/4/4 4/4/4 6/5/4 Xiaoganbei - Wuhan 0/0/0 0/1/1 1/2/2 1/1/1 2/1/2 4/5/4 1/4/2 6/4/6 Wuhan - Xianningbei 4/5/4 4/1/1 5/7/6 6/7/8 3/1/2 8/8/7 5/3/3 6/6/5 Xianningbei - Yueyangdong 3/3/2 2/3/3 5/5/6 7/6/5 4/4/4 6/4/5 7/6/5 4/6/6 Yueyangdong - Changshanan 0/2/2 4/5/3 4/2/3 8/6/5 6/6/7 1/2/3 9/7/8 4/4/1 Changshanan - Hengyangdong 7/5/4 2/3/2 5/4/4 4/5/5 10/5/5 6/7/5 4/3/5 9/7/6 Hengyangdong - Chenzhouxi 2/1/1 4/4/2 4/4/2 4/4/4 5/5/6 8/7/5 5/3/4 6/5/5 Chenzhouxi - Guangzhounan 0/0/0 4/4/2 2/2/2 5/5/3 6/3/4 6/5/5 8/8/7 3/2/2 Guangzhounan - Shenzhenbei 5/4/2 2/3/2 5/4/3 6/5/4 4/2/4 4/5/3 2/2/4 5/5/4  (b) Track section Number of trains per unit time [15:00,15:59] [16:00,16:59] [17:00,17:59] [18:00,18:59] [19:00,19:59] [20:00,20:59] [21:00,21:59] [22:00,22:59] [23:00,23:59] Beijingxi - Baodingdong 4/6/4 4/4/5 2/2/1 6/6/5 4/3/4 1/1/1 2/1/1 1/1/1 0/0/0 Baodingdong - Shijiazhuang 5/6/5 5/5/6 3/3/2 5/5/5 5/4/4 2/2/1 3/2/2 0/0/0 1/1/1 Shijiazhuang - Handandong 3/3/4 1/1/0 5/5/5 0/0/0 4/4/4 2/1/1 0/1/1 0/0/0 0/0/0 Handandong - Anyangdong 3/2/2 3/3/3 2/1/1 3/4/4 2/2/3 2/3/2 2/1/1 0/0/0 0/0/0 Anyangdong - Zhengzhoudong 4/3/3 2/2/3 1/1/0 4/4/4 0/0/0 4/4/4 1/1/1 0/0/0 0/0/0 Zhengzhoudong - Xuchangdong 8/5/4 3/3/3 6/5/4 1/1/2 3/3/3 1/1/1 0/0/0 0/0/0 0/0/0 Xuchangdong - Zhumadianxi 7/7/3 4/3/3 5/3/5 2/3/1 4/4/4 0/0/1 1/1/0 0/0/0 0/0/0 Zhumadianxi - Xinyangdong 5/4/5 7/6/5 4/3/2 5/4/5 2/1/1 2/3/3 1/1/1 0/0/0 0/0/0 Xinyangdong - Xiaoganbei 4/3/5 6/7/5 4/3/3 5/2/5 2/4/1 3/4/3 1/0/1 1/1/1 0/0/0 Xiaoganbei - Wuhan 4/3/3 7/6/5 6/5/5 3/2/2 4/4/4 2/1/2 2/3/2 1/1/1 0/0/0 Wuhan - Xianningbei 8/9/9 5/3/5 6/4/2 4/4/4 4/4/2 1/1/1 1/0/1 0/0/0 0/0/0 Xianningbei - Yueyangdong 8/7/7 6/4/5 5/4/3 6/5/4 4/3/3 2/2/1 1/1/1 0/0/0 0/0/0 Yueyangdong - Changshanan 6/6/7 8/8/8 7/5/5 5/3/3 7/5/4 1/3/1 2/1/2 0/0/0 0/0/0 Changshanan - Hengyangdong 2/5/4 7/6/7 7/4/4 7/6/5 6/4/4 5/4/2 0/0/0 0/0/0 0/0/0 Hengyangdong - Chenzhouxi 6/4/5 5/4/4 7/7/6 5/4/6 7/6/4 5/4/3 4/3/2 0/0/0 0/0/0 Chenzhouxi - Guangzhounan 6/5/7 5/4/2 5/5/7 8/7/6 6/5/5 6/4/3 7/5/4 0/1/0 0/0/0 Guangzhounan - Shenzhenbei 5/5/3 4/3/3 5/5/5 2/2/2 6/5/5 3/2/2 4/3/2 0/1/1 0/0/0(  2  ) The Starting and Ending Trains at Each Station with Starting Capacity. The numbers of starting and ending trains at each station with starting capacity for the optimized solutions are shown in Table 8. Constraint Eq. (10) requests that the gap between the number of starting trains and that of ending trains at a station is not larger than Δw (Δw=2). From Table 8, for each optimized solution, the number of starting trains is equal to that of ending trains at most stations except for Guangzhounan station and Shenzhenbei station (the gap is 1 for them and the data are underlined), and they all meet constraint Eq. (10) strictly.Table 8
The numbers of starting and ending trains at each station with starting capacity on Beijing-Shenzhen corridor (train).
Station Ω 1 ∗ Ω 2 ∗ Ω 3 ∗ Ω a Starting Ending Starting Ending Starting Ending Starting Ending Beijingxi 69 69 66 66 62 62 78 76 Shijiazhuang 8 8 6 6 3 3 9 11 Handandong 6 6 5 5 5 5 6 6 zhengzhoudong 16 16 16 16 16 16 13 16 Xinyangdong 3 3 1 1 1 1 2 2 Wuhan 80 80 78 78 70 70 62 64 Yueyangdong 2 2 2 2 2 2 2 2 Changshanan 25 25 19 19 16 16 32 34 Guangzhounan 75 75 63 63 54 53 90 91 Shenzhenbei 98 98 91 91 82 83 90 90(  3  ) Line Plan Diagram. The space-time line plan diagrams of trains in Ω1∗, Ω2∗, and Ω3∗ on Beijing-Shenzhen corridor are shown in Figures 5–7, respectively. Every line in the diagrams represents a train. For simplicity, the median between the arrival time and the departure time of each train at each intermediate stop is marked in the diagrams. From Figures 5–7, the train distributions on the diagram become less dense, which results in fewer choices for passengers. Such law also can be shown in the data of this corridor in Table 5, i.e., decreasing trains and increasing time deviation and load factor from Ω1∗ to Ω3∗.Figure 5
Space-time diagram of trains inΩ1∗ on Beijing-Shenzhen corridor (from Beijing to Shenzhen).Figure 6
Space-time diagram of trains inΩ2∗ on Beijing-Shenzhen corridor (from Beijing to Shenzhen).Figure 7
Space-time diagram of trains inΩ3∗ on Beijing-Shenzhen corridor (from Beijing to Shenzhen).


## 6. Conclusions and Future Studies

This paper proposes a line planning approach with time-dependent demand and capacity constraints for HSR networks. The lines of trains, carriage compositions of trains, train stop patterns, train start times, and train arrival and departure times at stops are optimized synthetically in the line planning.A bilevel optimization model is formulated. In the upper level, the objective is to minimize the train operational cost and the passenger travel cost, and the compositions and numbers of trains are restricted by the constraints. In the lower level, a schedule-based passenger assignment method for HSR networks is used. In this method, passengers are assigned on trains with seat capacity constraints by simulating the ticket-booking process. A simulated annealing algorithm is developed to solve the model in which some strategies are designed to search for neighborhood solutions, including reducing train carriages, deleting trains, adding trains, increasing train carriages, and adjusting train start times.An application to the Chinese HSR network is presented. The results shows the following: (i) the average time deviations between the expected departure times and the actual boarding times of passengers are within 30 min, (ii) the numbers of unserved passengers are less than 200, and (iii) the average load factors of trains are about 70%. The above results show that this method has the application value in line planning for HSR networks.In further research, we will study the train schedule planning problem based on the line plan in the paper, which is a more challenging work.



---

*Source: 7509586-2019-03-17.xml*