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

1. IntroductionAs 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-andcut 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 fcL-List [tau] 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), Sama 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. Sama et al. [14] proposed an integer linear program model to address the realtime 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 Section 2, 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.

(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.

(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 time-table 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.

Let [x.sub.a,i] be the decision variable, [x.sub.a,i] [member of] {0,1}; that is, [x.sub.a,i] = 1 if the operation chain i is assigned to train a; otherwise, [x.sub.a,i] = [degrees].

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 train a and train b be assigned to operation chains that stop on the same track i; a precedes b, if

[mathematical expression not reproducible] (1)

where [t.sup.arrival.sub.b] denotes the arrival time of train b, [t.sup.depart.sub.a] denotes the departure time of train a, and [t.sub.release] denotes the release time. We can say that this pair of assignments conflicts on the track.

Let E denote the set of assignment pairs that are conflicting on tracks where trains stop on; that is, {[x.sub.a,i], [x.sub.b,i]} [member of] 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 Figure 3. 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 [t.sub.slot] 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.

Let train a be assigned to the operation chain i and train b be assigned to the operation chain j. Route [r.sub.i] in operation chain i may conflict with route rj in operation chain j, and [r.sub.i] precedes [r.sub.j]. The sequence of switches and intersections in route [r.sub.i] is [s.sub.i,1], [s.sub.i,2], [s.sub.i,3], ... , [s.sub.i,n], and the index of the conflict section is k. Therefore, the distance covered by train a before it releases the conflict section is

[L.sub.conflict] = [k.summation over (c=l)] L ([s.sub.i,c]) + [L.sub.train], (2)

where L([s.sub.i,c]) denotes the length of [s.sub.i,c] and [L.sub.train] denotes the length of the train.

Therefore, the time train a takes to release the conflict section after requesting is

[t.sub.release] = [L.sub.conflict]/v, (3)

where v denotes the average train velocity through the routes.

If the route is inbound, the request time is

[t.sub.request] = [t.sub.arrival] - 1 [t.sup.in.sub.advance]. (4)

If the route is outbound, the request time is

[t.sub.request] = [t.sub.depart] - [t.sup.out.sub.advance],

where the values of [t.sup.in.sub.advance] and [t.sup.out.sub.advance] depend on the signaling system.

Therefore, if

[t.sup.b.sub.request] [less than or equal to] [t.sup.a.sub.request] + [t.sub.release] (6)

where [t.sup.a.sub.request] denotes the request time of train b and [t.sup.a.sub.request] denotes the request time of train a, thus, we can say this pair of assignments is in conflict in the routes.

Let t denote the set of assignment pairs that is in conflict in the routes; that is, {[x.sub.a,i], [x.sub.b,j]} [member of] [tau] 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 maybe 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 sets E and t 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

[mathematical expression not reproducible] (7)

where Z is the maximum number of conflict-free trains, [absolute value of A] denotes the total number of trains in the saturated timetable, and [mathematical expression not reproducible] denotes the number of trains that must be assigned to the virtual operation chain.

Subject to the Following

Group I: Station Interlocking Constraints. The operation chain assignment constraints are as follows:

[mathematical expression not reproducible]. (8)

The track conflict constraint is as follows:

[mathematical expression not reproducible]. (9)

The route conflict constraint is as follows:

[x.sub.a,i] + [x.sub.b,j]- [less than or equal to] 1, [for all]{[x.sub.a,i], [x.sub.b,j]} [member of] [tau]. (10)

Group II: Train Set Utilization Constraints. The maintenance capacity of the depot constraint is as follows:

[summation over (a[member of]A, i[not equal to]null] [I.sub.a] [x.sub.a,i] [less than or equal to] [C.sub.depot]. (11)

The number of allocated train sets constraint is as follows:

[summation over (a[member of]A, i[not equal to]null] [O.sub.a] [x.sub.a,i] [less than or equal to] [C.sub.allocate] (12)

The train set balance utilization constraint is as follows:

[mathematical expression not reproducible] (13)

The minimum connecting time constraint is as follows:

[T.sup.min] [less than or equal to] [t.sup.depart.sub.b] - [t.sup.arrival.sub.a] when f (a, b) = 1. (14)

Group III: Some Basic Constraints

[for all]a [member of] A

[I.sub.a] [member of] {0,1,2}

[O.sub.a] [member of] {0,1,2}

f (a, b) [member of] {0,1}. (15)

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 Figure 4.

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.

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 train a 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 Section 5.

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 Figure 6.

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: [absolute value of 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 of [T.sup.min] 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 [T.sup.min] 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 [T.sup.min] 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 different [T.sup.min] values in the station module of the IATPS. The generation results are shown in Table 1.

The M 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 [x.sub.a,i] indicates a possible operation chain that may be arranged to train a. The value of [absolute value of M] influences the computational scale. The values [absolute value of E] and [absolute value of [tau]] are directly related to the number of constraint (9) and constraint (10) in the mathematic model. Taking the ratio of [absolute value of E] and [absolute value of M] as e, the indicator [member of] means that there are [member of] assignments, on average, that are incompatible with one assignment due to conflicts on the tracks. Similarly, taking the ratio of [absolute value of [tau]] and [absolute value of 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 [member of] and t are introduced to indicate the degree of mutual influence between the operation chain assignments.

From Table 1, we can see that the values of [member of] and t increased by 134% and 12%, respectively, when the [T.sup.min] value increased from 20 min to 60 min. The values of [member of] and t increase as the [T.sup.min] value increases. This is because the increasing [T.sup.min] 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 different [T.sup.min] values were obtained, as shown in Figure 7 (in terms of capacity, we count one train couple as two trains).

The computational results above show that the practical carrying capacity decreased by 24% when the [T.sup.min] value increased from 20 min to 60 min. The capacity decreased as the [T.sup.min] value increased, and the decreasing rate accelerated significantly when the [T.sup.min] value was larger than 40 min.

We can explain this phenomenon using Table 1. When the [T.sup.min] value increased, the [member of] 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 [T.sup.min]) is an effective method.

5.3. Impact of [C.sub.depot] and [C.sub.allocate] 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 exceed [C.sub.depot]. 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 [C.sub.allocate].

We propose a series of [C.sub.depot] and [C.sub.adocate] values to study their impacts on the station carrying capacity. Using a [T.sup.min] 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 [C.sub.depot] and [C.sub.allocate] values were obtained, as shown in Figures 8 and 9, respectively.

The computational results above show that the practical carrying capacity has a roughly linear relationship to [C.sub.depot] and to [C.sub.allocate] when the two parameters are smaller than a critical value. The practical carrying capacity increases as the value of [C.sub.depot] or [C.sub.allocate] increases within a particular range. However, when the two parameters exceed certain values ([C.sub.depot] = 45, [C.sub.allocate] = 40 in this example) the practical carrying capacity remains the same.

Figures 8 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 [C.sub.depot] and [C.sub.allocate]); however, when [C.sub.depot] and [C.sub.allocate] 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, using [T.sup.min] = 20 min, [C.sub.depot] = 35, and [C.sub.allocate] = 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).

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 Figure 10, 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 Table 2.

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 when [C.sub.depot] and [C.sub.allocate] exceed certain values ([C.sub.depot] = 45 and [C.sub.allocate] = 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.

Definitions of Symbols in the Model

A: The generated saturated timetable

M: The operation chain set, which contains all the possible operation chains for every train in the saturated timetable

null: The virtual operation chain

M(a): The set of all the operation chains that are suitable for train a including the virtual one; null [member of] (a)--for the generation of (a), see Section 3.1

E: The set of assignment pairs that are in conflict on the tracks where the trains stop--for the generation of E, see Section 3.2

[tau]: The set of assignment pairs that are in conflict on the routes--for the generation of [tau], see Section 3.2

[C.sub.depot]: The maintenance capacity of the depot--when the depot serves multiple railway lines, [C.sub.depot] denotes the subcapacity allocated to the studied station

[C.sub.allocate]: The number of train sets that are allocated to this station

[I.sub.a]: The condition of whether the train set of train a is assigned to be shunted to the depot--if not, the coefficient is set to 0; otherwise, the coefficient is set to 2 or 1, depending on whether the train set is coupled or not

[O.sub.a]: The condition of whether the train set of train a is assigned to be shunted from depot--if not, the coefficient is set to 0; otherwise, the coefficient is set to 2 or 1, depending on whether the train set is coupled or not

f(a, b) [member of] {0,1}: f(a, b) = 1 if train a and b are served by the same train set; otherwise, f(a, b) = 0

[f.sup.arrival.sub.a]: The arrival time of terminal train a

[f.sub.depart.sub.b]: The departure time of original train b

[T.sup.min]: The minimum connecting time for train sets of terminally arriving trains departing as original trains without shunting.

http://dx.doi.org/10.1155/2016/2741479

Competing Interests

The grants do not lead to any conflict of interests regarding the publication of this manuscript. The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

This work is financially supported by two Science and Technology Research Programs of China Railway Corporation (Grants 2014X001-B, 2016X005-D) and two Fundamental Research Funds of the Central Universities (Grants 2015JBM057, 2014JBZ008).

References

[1] L. Zhou, Study on the Optimization Technology of Train Timetabling under the Circumstances of the High-Speed and the Normal-Speed Railway is Forming into a Network in China, China Railway Corporation, Beijing, China, 2013.

[2] X. Delorme, J. Rodriguez, and X. Gandibleux, "Heuristics for railway infrastructure saturation," Electronic Notes in Theoretical Computer Science, vol. 50, no. 1, pp. 39-53, 2001.

[3] R. M. Lusby, J. Larsen, M. Ehrgott, and D. Ryan, "Railway track allocation: models and methods," OR Spectrum, vol. 33, no. 4, pp. 843-883, 2011.

[4] P. J. Zwaneveld, L. G. Kroon, H. E. Romeijn et al., "Routing trains through railway stations: model formulation and algorithms," Transportation Science, vol. 30, no. 3, pp. 181-194, 1996.

[5] P. J. Zwaneveld, L. G. Kroon, and S. P. M. Van Hoesel, "Routing trains through a railway station based on a node packing model," European Journal of Operational Research, vol. 128, no. 1, pp. 14-33, 2001.

[6] X. Delorme, X. Gandibleux, and J. Rodriguez, "Stability evaluation of a railway timetable at station level," European Journal of Operational Research, vol. 195, no. 3, pp. 780-790, 2009.

[7] X. Gandibleux, X. Delorme, and V. T'Kindt, "An ant colony optimisation algorithm for the set packing problem," in Ant Colony Optimization and Swarm Intelligence, pp. 49-60, Springer, Berlin, Germany, 2004.

[8] D. De Luca Cardillo and N. Mione, "k L-list [lambda] colouring of graphs," European Journal of Operational Research, vol. 106, no. 1, pp. 160-164, 1998.

[9] X. Jie, D. Wen, C. Jun-qianget al., "The genetic based algorithms optimization plan of using the arrival and departure track at railway sectional station," China Railway Science, vol. 22, no. 2, 2003.

[10] A. Billionnet, "Using integer programming to solve the train-platforming problem," Transportation Science, vol. 37, no. 2, pp. 213-222, 2003.

[11] M. Liu, B.-M. Han, and D.-W. Li, "Calculation and evaluation of carrying capacities at high-speed railway stations," Journal of the China Railway Society, vol. 34, no. 4, pp. 9-15, 2012.

[12] R. M. P. Goverde, F. Corman, and A. D'Ariano, "Railway line capacity consumption of different railway signalling systems under scheduled and disturbed conditions," Journal of Rail Transport Planning and Management, vol. 3, no. 3, pp. 78-94, 2013.

[13] M. Sama, P. Pellegrini, A. DAriano, J. Rodriguez, and D. Pacciarelli, "Ant colony optimization for the real-time train routing selection problem," Transportation Research Part B: Methodological, vol. 85, pp. 89-108, 2016.

[14] M. Sama, A. D'Ariano, F. Corman, and D. Pacciarelli, "A variable neighbourhood search for fast train scheduling and routing during disturbed railway traffic situations," Computers & Operations Research, vol. 78, pp. 480-499, 2017

[15] T. Dollevoet, F. Corman, A. DAriano, and D. Huisman, "An iterative optimization framework for delay management and train scheduling," Flexible Services & Manufacturing Journal, vol. 26, no. 4, pp. 490-515, 2014.

[16] P Pellegrini, G. Marliere, and J. Rodriguez, "Optimal train routing and scheduling for managing traffic perturbations in complex junctions," Transportation Research Part B: Methodological, vol. 59, pp. 58-80, 2014.

[17] F. Corman, A. DAriano, A. D. Marra, D. Pacciarelli, and M. Sama, "Integrating train scheduling and delay management in real-time railway traffic control," Transportation Research Part E: Logistics & Transportation Review, 2016.

[18] Y.-C. Lai and S.-H. Wang, "Development of analytical capacity models for conventional railways with advanced signaling systems," Journal of Transportation Engineering, vol. 138, no. 7, pp. 961-974, 2012.

[19] C.-G. Wang and J. Yan, "Research on the influence of the carrying capacity at station by the change of train composition," China Railway Science, vol. 26, no. 5, pp. 128-131, 2005.

[20] Y. Wei, H. Zhang, and H. Yang, "Impact of turnout type selection on station carrying capacity of heavy haul railway," China Railway Science, vol. 34, no. 4, pp. 95-98, 2013.

[21] UIC. UIC code 406: Capacity, Paris-France: UIC, 2004.

[22] Z. Wang and W. Du, "Adjusting model and algorithm for application of arrival and departure lines in technical stations," Journal of Southwest Jiaotong University, vol. 41, no. 2, pp. 202-205, 2006.

[23] F. Xue, "Collaborative optimization model and algorithm for wagon-flow allocation in railway marshalling station," System Engineering Theory & Practice, vol. 33, no. 11, pp. 2930-2936, 2013.

[24] B.-S. Wang, L.-X. Hou, and H.-D. Liu, "Optimized utilization of arrival and departure tracks in dedicated passenger lines," Journal of Transportation Systems Engineering and Information Technology, vol. 12, no. 2, pp. 105-110, 2012.

[25] Z. Qianrui and Z. Qi, "Optimization of High-speed railway station operation plan based on across-platform transfer," Journal of Railway Science and Engineering, vol. 13, no. 1, pp. 20-27, 2016.

Bin Guo, Leishan Zhou, Yixiang Yue, and Jinjin Tang

School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China

Correspondence should be addressed to Leishan Zhou; lshzhou@bjtu.edu.cn

Received 13 July 2016; Revised 19 November 2016; Accepted 1 December 2016

Academic Editor: Xavier Delorme

Caption: Figure 1: The minimum connecting time affects the station carrying capacity.

Caption: Figure 2: Lack of allocated train sets affects the station carrying capacity.

Caption: Figure 3: A conflict between trains in operation chains.

Caption: Figure 4: The main interface of the station module of the IATPS.

Caption: Figure 5: Flowchart of the genetic algorithm in the IATPS.

Caption: Figure 6: The track map of the BS station yard for the Beijing-Shanghai HSR.

Caption: Figure 10: Convergence processes of CPLEX and IATPS.

Table 1: The generation of relevant data. [T.sup.min] 20 min 30 min 40 min Number of trains 347 351 354 after connecting [absolute value of M] 4,511 4,563 4,602 [absolute value of E] 60,000 85,104 103,680 e 13.30 18.65 22.53 [absolute value of [tau]] 64,796 67,802 70,057 t 14.36 14.86 15.22 [T.sup.min] 50 min 60 min Number of trains 357 361 after connecting [absolute value of M] 4,641 4,693 [absolute value of E] 122,040 146,184 e 26.30 31.15 [absolute value of [tau]] 72,314 75,321 t 15.58 16.05 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-Track10-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 ... ... Figure 7: Practical carrying capacity corresponding to different [T.sup.min] values. [T.sup.min] Capacity Integer capacity Upper bound 20 444 446.69 30 438 441.68 40 430 437.86 50 400 410.98 60 340 361.58 Note: Table made from line graph. Figure 8: Practical carrying capacity corresponding to different [C.sub.depot] values [C.sub.depot] Capacity Integer capacity Upper bound 0 401 5 407 403.56 10 411 408.59 15 416 413.59 20 422 418.67 25 426 423.58 30 431 428.63 35 436 433.63 40 442 438.56 45 444 443.52 50 444 446.71 55 444 446.71 60 444 446.71 65 444 446.71 70 444 446.71 75 444 446.71 80 444 446.71 85 444 446.71 90 444 446.71 95 444 446.71 100 444 446.71 Note: Table made from line graph. Figure 9: Practical carrying capacity corresponding to different [C.sub.allocate] values [C.sub.allocate] Capacity Integer capacity Upper bound 0 404 404 5 409 409 10 414 414 15 419 419 20 424 424 25 429 429 30 434 434 35 439 439 40 444 444 45 444 446.71 50 444 446.71 55 444 446.71 60 444 446.71 65 444 446.71 70 444 446.71 75 444 446.71 80 444 446.71 85 444 446.71 90 444 446.71 95 444 446.71 100 444 446.71 Note: Table made from line graph.

Printer friendly Cite/link Email Feedback | |

Title Annotation: | Research Article |
---|---|

Author: | Guo, Bin; Zhou, Leishan; Yue, Yixiang; Tang, Jinjin |

Publication: | Mathematical Problems in Engineering |

Date: | Jan 1, 2017 |

Words: | 7542 |

Previous Article: | Sparse Signal Inversion with Impulsive Noise by Dual Spectral Projected Gradient Method. |

Next Article: | On Best Corrected Mixture Problems in Metallurgy: A Case Study. |

Topics: |