# A Study on the Practical Carrying Capacity of Large High-Speed Railway Stations considering Train Set Utilization

Authors: Bin Guo; Leishan Zhou; Yixiang Yue; Jinjin Tang
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

Methods for solving the carrying capacity problem for High-Speed Railways (HSRs) have received increasing attention in the literature in the last few years. As important nodes in the High-Speed Railway (HSR) network, large stations are usually the carrying capacity bottlenecks of the entire network due to the presence of multiple connections in different directions and the complexity of train operations at these stations. This paper focuses on solving the station carrying capacity problem and considers train set utilization constraints, which are important influencing factors that have rarely been studied by previous researchers. An integer linear programming model is built, and the CPLEX v12.2 software is used to solve the model. The proposed approach is tested on a real-world case study of the Beijing South Railway Station (BS), which is one of the busiest and most complex stations in China. Studies of the impacts of different train set utilization constraints on the practical station carrying capacity are carried out, and some suggestions are then presented for enhancing the practical carrying capacity. Contrast tests indicate that both the efficiency of the solving process and the quality of the solution show huge breakthroughs compared with the heuristic approach.


---

## Body

## 1. Introduction

As important nodes in the High-Speed Railway (HSR) network, large stations are usually the carrying capacity bottlenecks of the entire network due to the presence of multiple connections in different directions and the complexity of train operations at these stations. The China Railway Corporation (CRC), which owns the entire network and is also responsible for railway operation in China, has paid considerable attention to solving the carrying capacity problem of large stations to run more trains and satisfy the greatly increasing travel demands. However, the corporation currently lacks an accurate and effective approach for assessing the station carrying capacity of HSRs. From 2013 to 2014, we developed a software system named the “Intelligent Aided Train Timetable Programing Network Collaboration System” (IATPS), which was financially supported by the CRC [1]. The IATPS was developed to deal with a series of problems in the train timetable programing, and one of the core functions of the station module is calculating the carrying capacity of HSR stations. The approach used by the software is based on the genetic algorithm and needs to be improved.Many studies have been carried out worldwide to explore the calculation of the station carrying capacity problem. In Europe, this problem is also defined as the railway infrastructure saturation problem [2]. To assign each train to a conflict-free route through the railway station in the tentative saturated timetable, there are two typical types of routing methods: one is to model the problem as a node packing problem and the other is to model the problem based on the graph coloring problem [3]. Zwaneveld et al. [4] used the node packing model to solve train routing issues in the station module of the “DONS” system, which was codeveloped by the railway company “Nederlandse Spoorwegen.” During an extensional study of [4], Zwaneveld et al. [5] noticed the preference of a train for certain routes and modeled the problem as a weighted node packing problem; the branch-and-cut approach has been implemented to conquer this model. Delorme et al. [6] and Gandibleux et al. [7] also studied the problem based on the node packing problem and used the GRASP and ant colony algorithms to solve the problem, respectively. Using graph coloring approaches to route trains through stations, De Luca Cardillo and Mione [8] defined a special graph coloring problem, the kL-Listτ coloring problem and presented an efficient heuristic algorithm to solve it. Similar to De Luca Cardillo and Mione [8], Jie et al. [9] modeled the routing problem as a coloring problem, and the GA algorithm was applied to solve it. Unlike De Luca Cardillo and Mione [8] and Jie et al. [9], Billionnet [10] solved the problem using an integer programming solver that was more efficient and exact. Liu et al. [11] classified the carrying capacities at stations into different levels and suggested the theoretical utility method, the simulation method, and the compression and enrichment method to calculate carrying capacities at these different levels.Some examples in the literature focus on estimating the infrastructure capacity under disturbed conditions. Goverde et al. [12] used the train dispatching system ROMA (Railway traffic Optimization by Means of Alternative graphs) and proposed a dynamic timetable compression method for calculating infrastructure occupation. The results of the Dutch railway case study show that the scheduled infrastructure occupation decreases considerably between the Dutch speed signal system NS’54/ATB and ETCS Level 2. To address the real-time railway traffic management problem (rtRTMP), Samà et al. [13] started from the real-time train routing selection problem (rtTRSP) that was formulated as an integer linear programming formulation and solved via an ant colony optimization. The computational results of the two French case studies show that solving the rtTRSP reduces the number of routing subsets to be managed in the rtRTMP and improves the performance of the heuristic. Samà et al. [14] proposed an integer linear program model to address the real-time traffic management problem of scheduling and routing trains in complex and busy railway networks. Computational experiments indicated that the improved algorithms often outperformed a tabu search algorithm and a commercial solver in terms of reduced computation times and/or train delays. Dollevoet et al. [15] presented an iterative optimization framework that combined the macroscopic delay management model and the microscopic train scheduling model in an integrated approach. The macroscopic model determined which connections to maintain and proposed a disposition timetable. The disposition timetable was then validated microscopically for a bottleneck station of the network. Pellegrini et al. [16] proposed a mixed-integer linear programming formulation to address the real-time railway traffic management problem; this formulation seeks the best train routing and scheduling options in case of perturbations. In the experimental analysis, they assessed the impact of the granularity of the representation of the infrastructure on the optimal solution. The results indicated that the solution chosen with rough granularity implies longer delays suffered by trains compared with the solutions chosen with the fine granularity. Corman et al. [17] integrated train scheduling and delay management approaches into a microscopic delay management model to control railway traffic in real time with the objective of minimizing passenger travel time. An MILP approach was proposed, and real-world computational experiments showed that good quality solutions and lower bounds can be found within a limited computation time.Other researchers studied some other factors that affect the railway capacity. Lai and Wang [18] studied the railway capacity benefits from advanced signaling systems. The results from the case study indicated that the advanced signaling systems generally had positive capacity effects, but the benefits were not substantial. They also suggested some other capacity improvement alternatives, such as improving track layouts. Wang [19] considered the alteration of train categories to be the main factor affecting the carrying capacity at stations, and he studied the influence of changing the train composition; this research focused on freight railways. Wei [20] studied the station carrying capacity from an infrastructural point of view. He calculated the additional time from starting and stopping, the interval time, and the train diagram cycle time corresponding to different turnout types; then, he suggested the turnout type selection for different train traction weights. The study is also focused on freight railways.From the above literature review, the following conclusions were observed:(1)
Previous researchers have proposed many meaningful approaches, considering various factors or under different situations. However, they rarely considered the train set utilization constraints. These are important factors that greatly influence the station carrying capacity.(2)
The majority of the studies solved the problem using stochastic event simulation methods or heuristic algorithms, and the accuracy and efficiency of these methods cannot meet the current demands of HSR operations.This paper offers the following contributions to the growing body of research work on the station carrying capacity problem:(1)
The obtained practical station carrying capacity refers to a carrying capacity value that can be put into practice; it is not merely a theoretical number. Additionally, we study the influence of the train set utilization constraints on the station carrying capacity.(2)
We propose an integer linear programming approach that is more accurate and efficient than the genetic algorithm approach applied in the IATPS. The performance of the IATPS station carrying capacity calculation function is improved.(3)
A real-world case study is carried out to verify the feasibility of our approach.The paper is organized as follows. In Section2, the problem of calculating the station carrying capacity is introduced, and some train set utilization constraints that may affect the station carrying capacity are proposed. In Section 3, the station carrying capacity model is developed. In Section 4, a brief introduction of the software system IATPS is made. Then, we apply the model to a busy complex station and discuss the computational results in Section 5. Finally, we conclude this paper and discuss further research issues in Section 6.


## 2. Statement of the Station Carrying Capacity Problem

The goal of solving the station carrying capacity problem is to calculate the maximum number of trains that the station can possibly serve within 24 hours [11]. The capacity does not exist in absolute terms; the railway infrastructure capacity depends on the way it is utilized [21]. The following train set utilization constraints, which were rarely considered in previous studies, may affect the station carrying capacity of an HSR, and we attempt to study their influence on the station carrying capacity.(  1) The Minimum Train Set Connecting Time. To improve the efficiency of the train set utilization, many train sets of terminally arriving trains will depart as original trains without shunting. However, the connecting time will be longer than the minimum time limit, considering passenger boarding, alighting, and other issues. It is obvious that shorter minimum connecting times enable more trains to be served in the station, as shown in Figure 1. However, the numerical relationship between the minimum connecting time and the practical station carrying capacity is not clear.Figure 1
The minimum connecting time affects the station carrying capacity.(  2) The Number of Allocated Train Sets. All the train sets are allocated to the large stations along the HSR line. The number of train sets shunted from the depot to serve as original trains should not be larger than the number of train sets allocated to that station. Allocating more train sets will increase the number of trains operating at that station, as shown in Figure 2. However, whether this approach is helpful all the time needs to be studied.Figure 2
Lack of allocated train sets affects the station carrying capacity.(  3) The Depot Capacity. The number of train sets of terminally arriving trains that should be shunted towards the depot should not exceed the maintenance capacity of the depot because the maintenance capacity is limited. The impact of the depot capacity on the practical station carrying capacity needs to be studied.


## 3. Mathematic Model

### 3.1. Saturated Timetable and Train Operation Chain Set Generation

The saturated timetable is the foundation of this approach because it limits the solution space within a reasonable range. If we generate an oversized timetable, the solving time of the model will increase; if the scale of the timetable is too small, the potentially realizable carrying capacity of the station will not be achieved even though the solving time may be short.The generation principles of the saturated timetable are as follows:(1)
Set a reasonable interval time for trains intensively arriving and departing the station, according to the minimum headway of the railway signaling system.(2)
Set a reasonable station service time for trains arriving and departing considering the infrastructure maintenance during the late night period.(3)
To satisfy the passenger travel demand as much as possible, the train companies pay attention to designing a good passenger train service plan and to scheduling a good train timetable. To ensure that the eventual capacity meets the passenger demand, reasonable proportions of different types of trains should be made available according to the current timetables or according to the passenger demand forecasts for newly built railway lines.All the possible operation chains for every train in the saturated timetable should be generated, and they will make up the operation chain set. A complete operation chain for a train contains the following: get-in, stop or nonstop, and get-out. The inbound route and the outbound route must connect to the same track that the train stops at or runs through. The operation chain set contains all the possible operation chains of every train at the station. Generating a proper operation chain set is the premise of route conflict checking.The generation principles of the operation chain set are as follows:(1)
Generate all the possible operation chains for every train in the saturated timetable, referred to as the “train-track,” according to the track utilization rules at the station and the train running directions.(2)
In some cases, multiple routes exist that connect one point to one track; all the feasible choices should be generated and referred to as “train-track-a,” “train-track-b,” and so forth.(3)
Some trains are scheduled to add water or discharge sewerage at the station, while only a few tracks run near the relevant facilities. In such circumstances, we only generate the corresponding choices in the operation chain set.(4)
Only generate the feasible operation chains for certain trains due to some other special operational rules. In this way, the operational constraints in the model are effectively reduced; because the optional operation chains that do not meet the rules are not generated, the corresponding constraints can be ignored.


### 3.2. Station Interlocking

The practical carrying capacity requires every train counted towards the capacity to be assigned to a conflict-free operation chain, so that the station operation plan can be put into practice. In the process of generating an operation chain set, there are usually multiple operation chains that are suitable for one train. The interaction between the routes in the operation chains is so high that many pairs of operation chain assignments lead to conflicts. Whenever two trains request the same infrastructure equipment (track, switch, intersection, etc.) at the same time, the two trains are defined as conflicting according to interlocking rules, and at least one of the trains should be rerouted or cancelled for safety reasons. We classify the conflicts into two groups: one contains the conflicts that occur on the tracks that trains stop on and the other contains the conflicts that occur in routes.Letxa,i be the decision variable, xa,i∈{0,1}; that is, xa,i=1 if the operation chain i is assigned to train a; otherwise, xa,i=0.When trains stop at platforms for passenger boarding and alighting, it is easy to check whether they are conflicting with other trains present on the track. Let both traina and train b be assigned to operation chains that stop on the same track i; a precedes b, if (1)tbarrival≤tadepart+treleaseifxa,i=1,xb,i=1,where tbarrival denotes the arrival time of train b, tadepart denotes the departure time of train a, and trelease denotes the release time. We can say that this pair of assignments conflicts on the track.LetE denote the set of assignment pairs that are conflicting on tracks where trains stop on; that is, {xa,i,xb,i}∈E in the above case.This is different from the above method for checking whether the routes in the operation chains are conflicting. Before arriving at or departing from a station, a train usually requests the use of several track sections before occupying them. While passing through the route, the train will release the appropriate track sections along the route successively after the tail of the train has left these sections. When two routes request the same switches or intersections, there may be a conflict, as shown in Figure3. Among the same requested switches or intersections, we call the last one released by the previous train “the conflict section.” For the case presented in Figure 3, switch S5 is the conflict section. It is important to calculate the time slot tslot on the conflict section between the release time by the previous train and the request time by the following train, as shown in Figure 3.Figure 3
A conflict between trains in operation chains.Let traina be assigned to the operation chain i and train b be assigned to the operation chain j. Route ri in operation chain i may conflict with route rj in operation chain j, and ri precedes rj. The sequence of switches and intersections in route ri is si,1,si,2,si,3,…,si,n, and the index of the conflict section is k. Therefore, the distance covered by train a before it releases the conflict section is(2)Lconflict=∑c=1kLsi,c+Ltrain,where L(si,c) denotes the length of si,c and Ltrain denotes the length of the train.Therefore, the time traina takes to release the conflict section after requesting is(3)trelease=Lconflictv,where v denotes the average train velocity through the routes.If the route is inbound, the request time is(4)trequest=tarrival-tadvancein.If the route is outbound, the request time is(5)trequest=tdepart-tadvanceout,where the values of tadvancein and tadvanceout depend on the signaling system.Therefore, if(6)trequestb≤trequesta+trelease,where trequestb denotes the request time of train b and trequesta denotes the request time of train a, thus, we can say this pair of assignments is in conflict in the routes.Letτ denote the set of assignment pairs that is in conflict in the routes; that is, xa,i,xb,j∈τ in the above case.


### 3.3. Model Building

To build an integer linear programming mathematical model, we make the following assumptions:(1)
To ensure that we will always obtain a feasible solution, we propose a virtual operation chain that can be assigned to any train. Trains running though the virtual operation chain will not conflict with any train, but they will not be counted in the station carrying capacity.(2)
Different from the real-time railway traffic management model, in which the trains may be rescheduled, we treat the arrival and the departure times of the trains in the saturated timetable as unalterable. This means the trains in the saturated timetable will be either rerouted or assigned to the virtual operation chain due to route conflicts, but the arrival and the departure times of the trains cannot be changed.(3)
The setsE and τ can be generated by the station module of the IATPS or by other railway station software systems as described in Section 3.2.The notations for the proposed formulation are introduced in Definitions of Symbols in the Model, including their descriptions.A 0-1 integer linear programming model was built as follows.Objective Function. The maximum number of trains that can be assigned to a conflict-free operation chain in the saturated timetable is the optimization objective. Every train counted towards the carrying capacity can be assigned to a conflict-free operation chain; therefore, the obtained carrying capacity can be put into practice and has more practical meaning than merely representing a number for railway companies. Equation (7) is represented by(7)Max⁡Z=A-∑a∈A,i=nullxa,i,where Z is the maximum number of conflict-free trains, |A| denotes the total number of trains in the saturated timetable, and ∑a∈A,i=nullxa,i denotes the number of trains that must be assigned to the virtual operation chain.Subject to the FollowingGroup I: Station Interlocking Constraints. The operation chain assignment constraints are as follows:(8)∑i∈Maxa,i=1∑i∉Maxa,i=0.The track conflict constraint is as follows:(9)xa,i+xb,i≤1,∀xa,i,xb,i∈E,i∈Ma,i∈Mb.The route conflict constraint is as follows:(10)xa,i+xb,j≤1,∀xa,i,xb,j∈τ.Group II: Train Set Utilization Constraints. The maintenance capacity of the depot constraint is as follows:(11)∑a∈A,i≠nullIaxa,i≤Cdepot.The number of allocated train sets constraint is as follows:(12)∑a∈A,i≠nullOaxa,i≤Callocate.The train set balance utilization constraint is as follows:(13)∑a∈A,i≠nullIaxa,i=∑a∈A,i≠nullOaxa,i.The minimum connecting time constraint is as follows:(14)Tmin⁡≤tbdepart-taarrivalwhenfa,b=1.Group III: Some Basic Constraints (15) ∀ a ∈ A I a ∈ 0,1 , 2 O a ∈ 0,1 , 2 f a , b ∈ 0,1 .In Group I, constraints (8) ensure that each train receives one and only one suitable operation chain. Constraint (9) ensures that any pair of trains will not be assigned to operation chains that can lead to conflicts on tracks where trains stop. Constraint (10) ensures that any pair of trains will not be assigned to operation chains that can lead to route conflicts.In Group II, constraint (11) guarantees that the total number of train sets that will be shunted to the depot will not be greater than the maintenance capacity of the depot. Constraint (12) ensures that the total number of train sets that will be shunted from the depot will not be greater than the number of train sets that are allocated to this station. Constraint (13) indicates that the number of train sets shunted to and from the depot should be equal. On some HSR lines, the train set utilization rule may require this condition to balance the train set utilization. Constraint (14) ensures that the connecting time for train sets of terminally arriving trains departing as original trains without shunting will be longer than the minimum limit.Because the model we built is a 0-1 integer linear programming model, after generating all the related data in the station module of the IATPS, we can directly solve the model using the integer programming solver CPLEX.


## 3.1. Saturated Timetable and Train Operation Chain Set Generation

The saturated timetable is the foundation of this approach because it limits the solution space within a reasonable range. If we generate an oversized timetable, the solving time of the model will increase; if the scale of the timetable is too small, the potentially realizable carrying capacity of the station will not be achieved even though the solving time may be short.The generation principles of the saturated timetable are as follows:(1)
Set a reasonable interval time for trains intensively arriving and departing the station, according to the minimum headway of the railway signaling system.(2)
Set a reasonable station service time for trains arriving and departing considering the infrastructure maintenance during the late night period.(3)
To satisfy the passenger travel demand as much as possible, the train companies pay attention to designing a good passenger train service plan and to scheduling a good train timetable. To ensure that the eventual capacity meets the passenger demand, reasonable proportions of different types of trains should be made available according to the current timetables or according to the passenger demand forecasts for newly built railway lines.All the possible operation chains for every train in the saturated timetable should be generated, and they will make up the operation chain set. A complete operation chain for a train contains the following: get-in, stop or nonstop, and get-out. The inbound route and the outbound route must connect to the same track that the train stops at or runs through. The operation chain set contains all the possible operation chains of every train at the station. Generating a proper operation chain set is the premise of route conflict checking.The generation principles of the operation chain set are as follows:(1)
Generate all the possible operation chains for every train in the saturated timetable, referred to as the “train-track,” according to the track utilization rules at the station and the train running directions.(2)
In some cases, multiple routes exist that connect one point to one track; all the feasible choices should be generated and referred to as “train-track-a,” “train-track-b,” and so forth.(3)
Some trains are scheduled to add water or discharge sewerage at the station, while only a few tracks run near the relevant facilities. In such circumstances, we only generate the corresponding choices in the operation chain set.(4)
Only generate the feasible operation chains for certain trains due to some other special operational rules. In this way, the operational constraints in the model are effectively reduced; because the optional operation chains that do not meet the rules are not generated, the corresponding constraints can be ignored.


## 3.2. Station Interlocking

The practical carrying capacity requires every train counted towards the capacity to be assigned to a conflict-free operation chain, so that the station operation plan can be put into practice. In the process of generating an operation chain set, there are usually multiple operation chains that are suitable for one train. The interaction between the routes in the operation chains is so high that many pairs of operation chain assignments lead to conflicts. Whenever two trains request the same infrastructure equipment (track, switch, intersection, etc.) at the same time, the two trains are defined as conflicting according to interlocking rules, and at least one of the trains should be rerouted or cancelled for safety reasons. We classify the conflicts into two groups: one contains the conflicts that occur on the tracks that trains stop on and the other contains the conflicts that occur in routes.Letxa,i be the decision variable, xa,i∈{0,1}; that is, xa,i=1 if the operation chain i is assigned to train a; otherwise, xa,i=0.When trains stop at platforms for passenger boarding and alighting, it is easy to check whether they are conflicting with other trains present on the track. Let both traina and train b be assigned to operation chains that stop on the same track i; a precedes b, if (1)tbarrival≤tadepart+treleaseifxa,i=1,xb,i=1,where tbarrival denotes the arrival time of train b, tadepart denotes the departure time of train a, and trelease denotes the release time. We can say that this pair of assignments conflicts on the track.LetE denote the set of assignment pairs that are conflicting on tracks where trains stop on; that is, {xa,i,xb,i}∈E in the above case.This is different from the above method for checking whether the routes in the operation chains are conflicting. Before arriving at or departing from a station, a train usually requests the use of several track sections before occupying them. While passing through the route, the train will release the appropriate track sections along the route successively after the tail of the train has left these sections. When two routes request the same switches or intersections, there may be a conflict, as shown in Figure3. Among the same requested switches or intersections, we call the last one released by the previous train “the conflict section.” For the case presented in Figure 3, switch S5 is the conflict section. It is important to calculate the time slot tslot on the conflict section between the release time by the previous train and the request time by the following train, as shown in Figure 3.Figure 3
A conflict between trains in operation chains.Let traina be assigned to the operation chain i and train b be assigned to the operation chain j. Route ri in operation chain i may conflict with route rj in operation chain j, and ri precedes rj. The sequence of switches and intersections in route ri is si,1,si,2,si,3,…,si,n, and the index of the conflict section is k. Therefore, the distance covered by train a before it releases the conflict section is(2)Lconflict=∑c=1kLsi,c+Ltrain,where L(si,c) denotes the length of si,c and Ltrain denotes the length of the train.Therefore, the time traina takes to release the conflict section after requesting is(3)trelease=Lconflictv,where v denotes the average train velocity through the routes.If the route is inbound, the request time is(4)trequest=tarrival-tadvancein.If the route is outbound, the request time is(5)trequest=tdepart-tadvanceout,where the values of tadvancein and tadvanceout depend on the signaling system.Therefore, if(6)trequestb≤trequesta+trelease,where trequestb denotes the request time of train b and trequesta denotes the request time of train a, thus, we can say this pair of assignments is in conflict in the routes.Letτ denote the set of assignment pairs that is in conflict in the routes; that is, xa,i,xb,j∈τ in the above case.


## 3.3. Model Building

To build an integer linear programming mathematical model, we make the following assumptions:(1)
To ensure that we will always obtain a feasible solution, we propose a virtual operation chain that can be assigned to any train. Trains running though the virtual operation chain will not conflict with any train, but they will not be counted in the station carrying capacity.(2)
Different from the real-time railway traffic management model, in which the trains may be rescheduled, we treat the arrival and the departure times of the trains in the saturated timetable as unalterable. This means the trains in the saturated timetable will be either rerouted or assigned to the virtual operation chain due to route conflicts, but the arrival and the departure times of the trains cannot be changed.(3)
The setsE and τ can be generated by the station module of the IATPS or by other railway station software systems as described in Section 3.2.The notations for the proposed formulation are introduced in Definitions of Symbols in the Model, including their descriptions.A 0-1 integer linear programming model was built as follows.Objective Function. The maximum number of trains that can be assigned to a conflict-free operation chain in the saturated timetable is the optimization objective. Every train counted towards the carrying capacity can be assigned to a conflict-free operation chain; therefore, the obtained carrying capacity can be put into practice and has more practical meaning than merely representing a number for railway companies. Equation (7) is represented by(7)Max⁡Z=A-∑a∈A,i=nullxa,i,where Z is the maximum number of conflict-free trains, |A| denotes the total number of trains in the saturated timetable, and ∑a∈A,i=nullxa,i denotes the number of trains that must be assigned to the virtual operation chain.Subject to the FollowingGroup I: Station Interlocking Constraints. The operation chain assignment constraints are as follows:(8)∑i∈Maxa,i=1∑i∉Maxa,i=0.The track conflict constraint is as follows:(9)xa,i+xb,i≤1,∀xa,i,xb,i∈E,i∈Ma,i∈Mb.The route conflict constraint is as follows:(10)xa,i+xb,j≤1,∀xa,i,xb,j∈τ.Group II: Train Set Utilization Constraints. The maintenance capacity of the depot constraint is as follows:(11)∑a∈A,i≠nullIaxa,i≤Cdepot.The number of allocated train sets constraint is as follows:(12)∑a∈A,i≠nullOaxa,i≤Callocate.The train set balance utilization constraint is as follows:(13)∑a∈A,i≠nullIaxa,i=∑a∈A,i≠nullOaxa,i.The minimum connecting time constraint is as follows:(14)Tmin⁡≤tbdepart-taarrivalwhenfa,b=1.Group III: Some Basic Constraints (15) ∀ a ∈ A I a ∈ 0,1 , 2 O a ∈ 0,1 , 2 f a , b ∈ 0,1 .In Group I, constraints (8) ensure that each train receives one and only one suitable operation chain. Constraint (9) ensures that any pair of trains will not be assigned to operation chains that can lead to conflicts on tracks where trains stop. Constraint (10) ensures that any pair of trains will not be assigned to operation chains that can lead to route conflicts.In Group II, constraint (11) guarantees that the total number of train sets that will be shunted to the depot will not be greater than the maintenance capacity of the depot. Constraint (12) ensures that the total number of train sets that will be shunted from the depot will not be greater than the number of train sets that are allocated to this station. Constraint (13) indicates that the number of train sets shunted to and from the depot should be equal. On some HSR lines, the train set utilization rule may require this condition to balance the train set utilization. Constraint (14) ensures that the connecting time for train sets of terminally arriving trains departing as original trains without shunting will be longer than the minimum limit.Because the model we built is a 0-1 integer linear programming model, after generating all the related data in the station module of the IATPS, we can directly solve the model using the integer programming solver CPLEX.


## 4. A Brief Introduction of the IATPS

To deal with a series of problems in train timetable programing, we developed the software system named the “Intelligent Aided Train Timetable Programing Network Collaboration System” (IATPS), which was financially supported by the CRC. The core functions of the station module are as follows: station carrying capacity calculation; automatic scheduling of the station operation plan, given the station timetable; operation plan conflict detection and robustness optimization; and operation plan simulation based on station interlocking. The main interface of the station module is shown in Figure4.Figure 4
The main interface of the station module of the IATPS.The genetic algorithm is widely applied in the field of railway station operation optimization [22–25]. As mentioned in the Introduction, the station carrying capacity calculation function of the IATPS is also based on a genetic algorithm approach, and the algorithm flowchart is shown in Figure 5.Figure 5
Flowchart of the genetic algorithm in the IATPS.In general, the trains in the saturated station timetable are ordered chronologically. Each chromosome is encoded to a one-dimensional string; that is, every gene gets an operation chain index, which means that the corresponding traina is assigned an operation chain from M(a). During the iterative process, every chromosome in the population should be checked by the station module of the IATPS according to the station interlocking rules. The trains conflicting with others will not be counted in the carrying capacity represented by the chromosome. After iterative optimization, the greatest carrying capacity obtained is taken as the station carrying capacity. For further details of the genetic algorithm design, readers may refer to Jie et al. [9], which presents algorithm procedures that are very similar to those of the IATPS.Because of the heavy mutual influences among train routes, the algorithm is so time-consuming that the software performance needs improvements. Comparative experiments between the genetic algorithm approach applied in the IATPS and the integer linear programming approach proposed by this paper were carried out, and the comparison results are shown in Section5.


## 5. Case Study

### 5.1. Basic Information

To verify the feasibility of our approach, the Beijing South Railway Station (BS) on the Beijing-Shanghai HSR was used as an example. The BS also serves the Beijing-Tianjin intercity railway, and the track map for the BS Beijing-Shanghai HSR yard is shown in Figure6.Figure 6
The track map of the BS station yard for the Beijing-Shanghai HSR.The BS is a dead-end station; both arriving and departing trains run through the left side. There are 4 borders in the yard named B1 to B4. B2 and B3 lead to Shanghai and are used by trains arriving or departing, respectively. B1 and B4 connect to the same depot, and the connecting lines are isolated from each other and from other railway lines. Train sets scheduled to be shunted to or from the depot can run in either of the two directions through B1 or B4 without influencing other trains. The 12 tracks in the yard are named track 8 to track 19. Because the BS is a dead-end station, the track utilization rule is simple: regardless of whether they are arriving or departing, trains can stop on any track in this yard.The station infrastructure maintenance time interval is 0:00–7:00. Trains can arrive between 9:00 and 24:00 and depart between 7:00 and 22:00. The interval time for arriving and departing is 3 min.The current actual timetable shows that there are only two train direction types at the BS: “terminally arrived” and “originally departed.” Therefore, the generated saturated timetable for the BS contains 300 terminal trains and 300 original trains:A=600.


### 5.2. Impact of Minimum Connecting Time on the Station Carrying Capacity

After one train has terminally arrived at the station, the train set will be shunted to the depot or depart without shunting according to the “train set circulation scheme.” Because there is no train set circulation scheme corresponding to the generated saturated timetable, we propose a series ofTmin values to study the impact of the minimum connecting time on the station carrying capacity.Connect Train Rule. We can connect a terminally arriving train A and an original train B, if train B is the first unconnected originally departing train, within Tmin min after the arrival of train A. Consider trains A and B as one train that stopped at the station for a certain time. If no unconnected train leaves Tmin minutes after the arrival of train A, train A should be shunted to the depot to release the track. Each couple of connected trains is served by the same train set.We generate all the relevant data corresponding to differentTmin values in the station module of the IATPS. The generation results are shown in Table 1.Table 1
The generation of relevant data.
T m i n 20 min 30 min 40 min 50 min 60 min Number of trains after connecting 347 351 354 357 361 | M | 4,511 4,563 4,602 4,641 4,693 | E | 60,000 85,104 103,680 122,040 146,184 e 13.30 18.65 22.53 26.30 31.15 | τ | 64,796 67,802 70,057 72,314 75,321 t 14.36 14.86 15.22 15.58 16.05TheM variable is the set of all the suitable operation chains for all trains. It also corresponds to the set of decision variables in the mathematical model because every decision variable xa,i indicates a possible operation chain that may be arranged to train a. The value of |M| influences the computational scale. The values |E| and |τ| are directly related to the number of constraint (9) and constraint (10) in the mathematic model. Taking the ratio of |E| and |M| as e, the indicator e means that there are e assignments, on average, that are incompatible with one assignment due to conflicts on the tracks. Similarly, taking the ratio of |τ| and |M| as t, the indicator t means that there are t assignments, on average, that are incompatible with one assignment due to routing conflicts. Indicators e and t are introduced to indicate the degree of mutual influence between the operation chain assignments.From Table1, we can see that the values of e and t increased by 134% and 12%, respectively, when the Tmin value increased from 20 min to 60 min. The values of e and t increase as the Tmin value increases. This is because the increasing Tmin value means that the standstill time of the connected trains on the track is becoming longer. There will be fewer unrequested tracks for a newly arriving train, on average, so the degree of mutual influence between operation chain assignments increases, as shown in Figure 1.The CPLEX v12.2 was used for problem solving, and the solving time limit was set to 300 seconds. After running in the PC (Core E3, Frequency 3.30 GHz, Memory 8 GB), the integer solutions and the upper bounds of the practical carrying capacity corresponding to differentTmin values were obtained, as shown in Figure 7 (in terms of capacity, we count one train couple as two trains).Figure 7
Practical carrying capacity corresponding to differentTmin values.The computational results above show that the practical carrying capacity decreased by 24% when theTmin value increased from 20 min to 60 min. The capacity decreased as the Tmin value increased, and the decreasing rate accelerated significantly when the Tmin value was larger than 40 min.We can explain this phenomenon using Table1. When the Tmin value increased, the e and t values increased, which means that the mutual influence between operation chain assignments increased greatly. Figure 7 shows that to increase the practical carrying capacity of a station improving the efficiency of the train set utilization (decreasing the minimum connecting time Tmin) is an effective method.


### 5.3. Impact ofCdepot and Callocate on the Station Carrying Capacity

The maintenance capacity of the depot is limited, so the number of train sets of terminally arriving trains shunted to the depot cannot exceedCdepot. Because of the high acquisition cost of a train set, the number of train sets that are allocated to the station is also limited; the number of train sets shunted from the depot to serve as original trains cannot exceed Callocate.We propose a series ofCdepot and Callocate values to study their impacts on the station carrying capacity. Using a Tmin value of 20 min as an example, the solving procedure is similar to that in Section 5.2 but with the addition of constraint (11) or constraint (12). Using the software CPLEX, the integer solutions and the upper bounds of the practical carrying capacity corresponding to different Cdepot and Callocate values were obtained, as shown in Figures 8 and 9, respectively.Figure 8
Practical carrying capacity corresponding to differentCdepot values.Figure 9
Practical carrying capacity corresponding to differentCallocate values.The computational results above show that the practical carrying capacity has a roughly linear relationship toCdepot and to Callocate when the two parameters are smaller than a critical value. The practical carrying capacity increases as the value of Cdepot or Callocate increases within a particular range. However, when the two parameters exceed certain values (Cdepot=45,Callocate=40 in this example) the practical carrying capacity remains the same.Figures8 and 9 show that to increase the practical carrying capacity of a station we can increase the maintenance capacity of the depot or allocate more train sets to the station (increase the values of Cdepot and Callocate); however, when Cdepot and Callocate exceed certain thresholds, the two values become meaningless. The results provide good references for railway companies that are considering increasing the practical carrying capacity of a station.The above results show the effectiveness of two measures for enhancing the carrying capacity of the only studied station. Considering the train set circulation on the rail network, they could provide more train services from the network point of view, but this is beyond the scope of this article.


### 5.4. Computational Results and Comparison with Traditional Approach

To verify the high efficiency of this approach, two groups of comparative experiments were carried out in the CPLEX and the IATPS software based on the same data, usingTmin=20min, Cdepot=35, and Callocate=40 as example values. The IATPS solves the practical carrying capacity calculating problem based on a genetic algorithm. Considering the user’s operational experience with the software, the algorithm will be terminated after it has run for 8 min, and the highest capacity value obtained is taken as the station carrying capacity. Two experiments were carried out using the same computer. After solving with CPLEX, an optimal value of 435 was obtained, while the IATPS approach obtained a local optimal value of 385. The convergence processes of the two experiments are shown in Figure 10. The horizontal axis denotes computation time (in seconds), and the vertical axis denotes the practical carrying capacity (number of trains).Figure 10
Convergence processes of CPLEX and IATPS.The convergence process of CPLEX was faster than IATPS. It required 54 seconds, while IATPS was much more time-consuming and required approximately 180 seconds. Moreover, the capacity obtained by our approach was 435 (optimal), which is much better than the value obtained by IATPS (385).Comparing the two curves in Figure10, we can see that the proposed approach in this paper is much better than the genetic algorithm approach that is applied in the IATPS. The calculation time decreased by 126 seconds, and the solution value increased by 22%: both the efficiency of the solving process and the quality of the solution were significantly improved.Because calculating the practical station carrying capacity problem is a large-scale combinatorial optimization problem and due to the heavy mutual influence between train routes, the solving efficiency of the genetic algorithm is low.Part of the station operation plan corresponding to a capacity of 435 is shown in Table2.Table 2
Part of the corresponding station operation plan.
Train name Operation chain X32 B4-Track 9-B3 X31 B4-Track 11-B3 X33 B1-Track 15-B3 X35 B1-Track 14-B3 X34 B1-Track 16-B3 X30 B4-Track 10-B3 X26 B1-Track 16-B3 X25 B1-Track 19-B3 X27 B1-Track 17-B3 X29 B4-Track 8-B3 X36 B1-Track 17-B3 ⋯ ⋯ Y1-X48 B2-Track 16-B3 Y2-X49 B2-Track 15-B3 Y3-X50 B2-Track 14-B3 Y4-X51 B2-Track 12-B3 Y5-X52 B2-Track 8-B3 Y6-X53 B2-Track 11-B3 Y7-X54 B2-Track 9-B3 Y8-X55 B2-Track 10-B3 Y11-X58 B2-Track 15-B3 Y12-X59 B2-Track 17-B3 Y13-X60 B2-Track 19-B3 ⋯ ⋯


## 5.1. Basic Information

To verify the feasibility of our approach, the Beijing South Railway Station (BS) on the Beijing-Shanghai HSR was used as an example. The BS also serves the Beijing-Tianjin intercity railway, and the track map for the BS Beijing-Shanghai HSR yard is shown in Figure6.Figure 6
The track map of the BS station yard for the Beijing-Shanghai HSR.The BS is a dead-end station; both arriving and departing trains run through the left side. There are 4 borders in the yard named B1 to B4. B2 and B3 lead to Shanghai and are used by trains arriving or departing, respectively. B1 and B4 connect to the same depot, and the connecting lines are isolated from each other and from other railway lines. Train sets scheduled to be shunted to or from the depot can run in either of the two directions through B1 or B4 without influencing other trains. The 12 tracks in the yard are named track 8 to track 19. Because the BS is a dead-end station, the track utilization rule is simple: regardless of whether they are arriving or departing, trains can stop on any track in this yard.The station infrastructure maintenance time interval is 0:00–7:00. Trains can arrive between 9:00 and 24:00 and depart between 7:00 and 22:00. The interval time for arriving and departing is 3 min.The current actual timetable shows that there are only two train direction types at the BS: “terminally arrived” and “originally departed.” Therefore, the generated saturated timetable for the BS contains 300 terminal trains and 300 original trains:A=600.


## 5.2. Impact of Minimum Connecting Time on the Station Carrying Capacity

After one train has terminally arrived at the station, the train set will be shunted to the depot or depart without shunting according to the “train set circulation scheme.” Because there is no train set circulation scheme corresponding to the generated saturated timetable, we propose a series ofTmin values to study the impact of the minimum connecting time on the station carrying capacity.Connect Train Rule. We can connect a terminally arriving train A and an original train B, if train B is the first unconnected originally departing train, within Tmin min after the arrival of train A. Consider trains A and B as one train that stopped at the station for a certain time. If no unconnected train leaves Tmin minutes after the arrival of train A, train A should be shunted to the depot to release the track. Each couple of connected trains is served by the same train set.We generate all the relevant data corresponding to differentTmin values in the station module of the IATPS. The generation results are shown in Table 1.Table 1
The generation of relevant data.
T m i n 20 min 30 min 40 min 50 min 60 min Number of trains after connecting 347 351 354 357 361 | M | 4,511 4,563 4,602 4,641 4,693 | E | 60,000 85,104 103,680 122,040 146,184 e 13.30 18.65 22.53 26.30 31.15 | τ | 64,796 67,802 70,057 72,314 75,321 t 14.36 14.86 15.22 15.58 16.05TheM variable is the set of all the suitable operation chains for all trains. It also corresponds to the set of decision variables in the mathematical model because every decision variable xa,i indicates a possible operation chain that may be arranged to train a. The value of |M| influences the computational scale. The values |E| and |τ| are directly related to the number of constraint (9) and constraint (10) in the mathematic model. Taking the ratio of |E| and |M| as e, the indicator e means that there are e assignments, on average, that are incompatible with one assignment due to conflicts on the tracks. Similarly, taking the ratio of |τ| and |M| as t, the indicator t means that there are t assignments, on average, that are incompatible with one assignment due to routing conflicts. Indicators e and t are introduced to indicate the degree of mutual influence between the operation chain assignments.From Table1, we can see that the values of e and t increased by 134% and 12%, respectively, when the Tmin value increased from 20 min to 60 min. The values of e and t increase as the Tmin value increases. This is because the increasing Tmin value means that the standstill time of the connected trains on the track is becoming longer. There will be fewer unrequested tracks for a newly arriving train, on average, so the degree of mutual influence between operation chain assignments increases, as shown in Figure 1.The CPLEX v12.2 was used for problem solving, and the solving time limit was set to 300 seconds. After running in the PC (Core E3, Frequency 3.30 GHz, Memory 8 GB), the integer solutions and the upper bounds of the practical carrying capacity corresponding to differentTmin values were obtained, as shown in Figure 7 (in terms of capacity, we count one train couple as two trains).Figure 7
Practical carrying capacity corresponding to differentTmin values.The computational results above show that the practical carrying capacity decreased by 24% when theTmin value increased from 20 min to 60 min. The capacity decreased as the Tmin value increased, and the decreasing rate accelerated significantly when the Tmin value was larger than 40 min.We can explain this phenomenon using Table1. When the Tmin value increased, the e and t values increased, which means that the mutual influence between operation chain assignments increased greatly. Figure 7 shows that to increase the practical carrying capacity of a station improving the efficiency of the train set utilization (decreasing the minimum connecting time Tmin) is an effective method.


## 5.3. Impact ofCdepot and Callocate on the Station Carrying Capacity

The maintenance capacity of the depot is limited, so the number of train sets of terminally arriving trains shunted to the depot cannot exceedCdepot. Because of the high acquisition cost of a train set, the number of train sets that are allocated to the station is also limited; the number of train sets shunted from the depot to serve as original trains cannot exceed Callocate.We propose a series ofCdepot and Callocate values to study their impacts on the station carrying capacity. Using a Tmin value of 20 min as an example, the solving procedure is similar to that in Section 5.2 but with the addition of constraint (11) or constraint (12). Using the software CPLEX, the integer solutions and the upper bounds of the practical carrying capacity corresponding to different Cdepot and Callocate values were obtained, as shown in Figures 8 and 9, respectively.Figure 8
Practical carrying capacity corresponding to differentCdepot values.Figure 9
Practical carrying capacity corresponding to differentCallocate values.The computational results above show that the practical carrying capacity has a roughly linear relationship toCdepot and to Callocate when the two parameters are smaller than a critical value. The practical carrying capacity increases as the value of Cdepot or Callocate increases within a particular range. However, when the two parameters exceed certain values (Cdepot=45,Callocate=40 in this example) the practical carrying capacity remains the same.Figures8 and 9 show that to increase the practical carrying capacity of a station we can increase the maintenance capacity of the depot or allocate more train sets to the station (increase the values of Cdepot and Callocate); however, when Cdepot and Callocate exceed certain thresholds, the two values become meaningless. The results provide good references for railway companies that are considering increasing the practical carrying capacity of a station.The above results show the effectiveness of two measures for enhancing the carrying capacity of the only studied station. Considering the train set circulation on the rail network, they could provide more train services from the network point of view, but this is beyond the scope of this article.


## 5.4. Computational Results and Comparison with Traditional Approach

To verify the high efficiency of this approach, two groups of comparative experiments were carried out in the CPLEX and the IATPS software based on the same data, usingTmin=20min, Cdepot=35, and Callocate=40 as example values. The IATPS solves the practical carrying capacity calculating problem based on a genetic algorithm. Considering the user’s operational experience with the software, the algorithm will be terminated after it has run for 8 min, and the highest capacity value obtained is taken as the station carrying capacity. Two experiments were carried out using the same computer. After solving with CPLEX, an optimal value of 435 was obtained, while the IATPS approach obtained a local optimal value of 385. The convergence processes of the two experiments are shown in Figure 10. The horizontal axis denotes computation time (in seconds), and the vertical axis denotes the practical carrying capacity (number of trains).Figure 10
Convergence processes of CPLEX and IATPS.The convergence process of CPLEX was faster than IATPS. It required 54 seconds, while IATPS was much more time-consuming and required approximately 180 seconds. Moreover, the capacity obtained by our approach was 435 (optimal), which is much better than the value obtained by IATPS (385).Comparing the two curves in Figure10, we can see that the proposed approach in this paper is much better than the genetic algorithm approach that is applied in the IATPS. The calculation time decreased by 126 seconds, and the solution value increased by 22%: both the efficiency of the solving process and the quality of the solution were significantly improved.Because calculating the practical station carrying capacity problem is a large-scale combinatorial optimization problem and due to the heavy mutual influence between train routes, the solving efficiency of the genetic algorithm is low.Part of the station operation plan corresponding to a capacity of 435 is shown in Table2.Table 2
Part of the corresponding station operation plan.
Train name Operation chain X32 B4-Track 9-B3 X31 B4-Track 11-B3 X33 B1-Track 15-B3 X35 B1-Track 14-B3 X34 B1-Track 16-B3 X30 B4-Track 10-B3 X26 B1-Track 16-B3 X25 B1-Track 19-B3 X27 B1-Track 17-B3 X29 B4-Track 8-B3 X36 B1-Track 17-B3 ⋯ ⋯ Y1-X48 B2-Track 16-B3 Y2-X49 B2-Track 15-B3 Y3-X50 B2-Track 14-B3 Y4-X51 B2-Track 12-B3 Y5-X52 B2-Track 8-B3 Y6-X53 B2-Track 11-B3 Y7-X54 B2-Track 9-B3 Y8-X55 B2-Track 10-B3 Y11-X58 B2-Track 15-B3 Y12-X59 B2-Track 17-B3 Y13-X60 B2-Track 19-B3 ⋯ ⋯


## 6. Conclusions and Further Work

In this paper, we proposed an integer linear programming model for calculating the practical carrying capacity of railway stations. A real-world case study showed that, compared with the IATPS, the solution time decreased by 126 seconds, and the solution value increased by 22%; both the efficiency of the solving process and the quality of the solution were significantly improved.Moreover, we studied the impacts of different train set utilization constraints on the practical carrying capacity of the station. The results show that to enhance the practical carrying capacity of the station increasing the efficiency of the train set utilization (decreasing the minimum connecting time) is a good approach. Enhancing the maintenance capacity of the depots and allocating more train sets to the station are also helpful in certain ranges, but whenCdepot and Callocate exceed certain values (Cdepot=45 and Callocate=40, resp., in the current case), the two measures become meaningless.Our future research will focus on two major areas. First, we will study the impact of different types of saturated timetables (such as cyclic timetable and acyclic timetable) on station practical carrying capacity. Second, we will extend our approach from a station to a railway network, the solving scale will be larger, and it will be more challenging.



---

*Source: 2741479-2016-12-29.xml*