# Simultaneous Optimization of Train Timetabling and Platforming Problems for High-Speed Multiline Railway Network

Authors: Qin Zhang; Xiaoning Zhu; Li Wang; Shuai Wang
Journal: Journal of Advanced Transportation
 (2021)

---

## Abstract

The optimization problems of train timetabling and platforming are two crucial problems in high-speed railway operation; these problems are typically considered sequentially and independently. With the construction of high-speed railways, an increasing number of interactions between trains on multiple lines have led to resource assignment difficulties at hub stations. To coordinate station resources for multiline train timetables, this study fully considered the resources of track segments, station throat areas, and platforms to design a three-part space-time (TPST) framework from a mesoscopic perspective to generate a train timetable and station track assignment simultaneously. A 0-1 integer programming model is proposed, whose objective is to minimize the total weighted train running costs. The construction of a set of incompatible vertexes and links facilitates the expression of difficult constraints. Finally, example results verify the validity and practicability of our proposed method, which can generate conflict-free train timetables with a station track allocation plan for multiple railway lines at the same time.


---

## Body

## 1. Introduction

High-speed railways play a significant role in modern transportation systems. In China, the length of a high-speed railway has reached 35,000 km after 12 years of operation, which makes China the country with the longest running mileage of high-speed railway.The train timetabling problem, also called the train scheduling problem, is a fundamental problem in railway operation; the aim is to determine the station arrival and departure times for every train. A train timetable provides a reference for different departments in a train operation system to ensure successful service implementation. Train timetable quality influences not only the utilization of railway capacity but also the work of train dispatchers. A good train schedule can rapidly reduce modification during actual operation, making the service provided by a railway company reliable and competitive.The train platforming problem is a procedure following the design of a train timetable; the aim for this problem is to assign a specific conflict-free platform in every station to trains that are scheduled in the train timetable. Stations are a complicated component of a railway network. The track resources in a station can be divided into platform tracks and tracks in the throat area; note that the throat area is also sometimes referred to as the bottleneck area. The path connecting one platform and the station boundary may occupy some track resources in the throat area the same as a path connecting another platform and the station boundary. Thus, a reasonable track allocation plan in a station must be conflict-free, not only in the platform area but also in the throat area.In China, train timetables are generated sequentially as follows: First, a timetable is generated for each direction on each single line. Then, resource utilization in the hub stations that connect different lines is coordinated. If there is no feasible platform plan in one of the stations, the procedure is repeated. With the construction of new railway lines, networks are becoming increasingly complicated, and the interaction between all trains from different directions on different railway lines makes hub station capacity a limiting factor for the whole network. The sequential scheduling method cannot solve the train timetabling and platforming problems effectively and efficiently. As a result, there have recently been urgent calls to construct a framework that is suitable for the simultaneous optimization of the two problems.As shown in Figure1, a high-speed railway network is divided into two parts: stations and track segments (track between two stations). The resources in a station include tracks in the bottleneck area and several platform tracks. A solution framework that integrates timetabling and platforming must guarantee that the utilization of all resources, including track segments, platforms, and tracks at the throat area, is conflict-free.Figure 1
Railway network representation.Our paper addresses the integrated optimization of the train timetabling and train platforming problems at the planning level from a mesoscopic perspective. The goal of this study was to design a modeling framework for this integrated problem. Under the framework, trains from different directions can be simultaneously optimized using a flexible track utilization rule, where one train can use all platforms if the station layout allows for it. The current issues in developing such a framework are as follows:(i)
For the train timetabling problem at the planning level, railway networks are mostly modeled from a macroscopic perspective. As noted in Zhang et al. [1]; only a few studies have solved this problem microscopically. Accuracy cannot be guaranteed by the former, while the latter perspective will dramatically increase the number of variables and constraints.(ii)
Specific platform allocation is ignored in the train timetabling problem. As mentioned earlier, timetabling and platforming are treated as separate and sequential procedures. A feasible solution may be difficult and sometimes impossible to find by the sequential scheduling method, especially for a network connecting several railway lines through some complex high-speed railway hub stations.(iii)
For the train platforming issue in the train scheduling problem, in many works, trains have been considered independently if their running directions are different, such as Zhang et al. [2] and Zhou et al. [3]. This method is feasible for most single railway lines. However, in a hub station, trains cannot be separated by their directions. Meanwhile, the track resources in the throat area are sometimes ignored, leading to infeasible or unreliable train platform plans.This study presents a solution framework to address the three abovementioned issues and simultaneously optimize train timetabling and platforming. The contributions of this work can be summarized as follows:(i)
First, we model the railway network with multiple railway lines from a mesoscopic perspective. The track segments between two stations are considered as a whole at the macroscopic level. In a station, the resources in the station bottleneck area are modeled in terms of routes, and station platform resources are also considered.(ii)
Second, we design a three-part (segment-bottleneck-platform) framework to allow the integration of timetabling and platforming. The three-part framework extends the previous two-part one (segment-station) and divides the station resources into a bottleneck area and platform.(iii)
Third, we schedule all trains at the same time. We generate all possible paths within a station in our proposed space-time network and preprocess the incompatible link set for all links according to the microscopic physical station layout.The remainder of this paper is organized as follows: Section2 provides a literature review on the train timetabling and platforming problems. Section 3 describes the construction of the space-time network under the three-part solution framework. Section 4 proposes a 0-1 integer programming model to simultaneously optimize the two problems. Section 5 presents computational results by the commercial CPLEX solver. Conclusions and future research directions are presented in Section 6.


## 2. Literature Review

### 2.1. Train Timetabling Problem

Train timetabling is a classical problem in railway operation. Caprara et al. [4] proved that the train scheduling problem is NP-hard, and they timetabled trains in a single-line one-way railway network. The objective was to maximize train profit, and a Lagrangian relaxation method was proposed to obtain their results. Carey and Crawford [5] designed a heuristic algorithm for a railway network with multiple complex stations linked by multiple one-way lines in each direction by extending the one-way single-station method in Carey and Carville [6]. A multiobjective model was constructed, and the objectives were sequenced by a lexicographic rule. Tian and Niu [7] proposed a biobjective integer programming model to maximize train connections while minimizing the passenger transfer waiting time. In the present study, overtaking was ignored in all stations, and trains from different directions were scheduled independently.D’ariano et al. [8] modeled a railway network in terms of track sections from a microscopic perspective and proposed an alternative graph representation, which was solved by a branch-and-bound method. Sama et al. [9] formulated an integer programming and proposed an ant-colony based method to address the train route section problem in a microscopic network. Zhou and Zhong [10] analyzed the train timetabling problem for a single railway line and designed a resource-constrained scheduling model to minimize the total travel time. Their results were obtained by branch-and-bound and Lagrangian relaxation methods. Sotskov and Gholami [11] used a shifting bottleneck algorithm to design a single-line train schedule. However, every resource of the railway could be occupied only once by every train, which is not reasonable for a railway network connecting several lines. Brannlund et al. [12] constructed an integer programming model and developed a Lagrangian relaxation method to maximize the train profit on a single-line railway network. The static station capacity, that is, the number of platforms, was considered in this model. Nillson and Chen [13] simultaneously optimized the train timetabling and train platforming problems, but the resource utilization in the bottleneck area in a station was ignored.For a highly congested railway line, Jiang et al. [14] proposed a heuristic method to simultaneously optimize the additional train schedule and the choice of the train stops. To solve the cyclic train timetable problem, Zhang et al. [15] extended the time-space network and then introduced the alternating direction method of multipliers. Luan et al. [16] proposed a mixed-integer linear programming model based on cumulative flow variables to optimize train scheduling as well as the tracking maintenance tasks from a microscopic perspective and used the Lagrangian relaxation method to obtain the revised timetable. Zhang et al. [17] optimized the train timetabling problem considering the detailed track assignment on a double-track railway corridor from a mesoscopic level and the running time on the segment as a constant value. The track utilization within a hub station, where more kinds of conflicts, such as those originating due to arrival and departure of two trains from two different railway lines, occur than those in a normal intermediate station, was not considered in Zhang et al. [17].Trains from different directions are always considered separately, which is not possible for some complex stations. Gao et al. [18] addressed the scheduling problem for adding the additional trains on a high-speed rail corridor by designing a three-stage optimization method and Zhang et al. [19] integrated the maintenance planning and train night timetable on the high-speed railway. However, both papers independently treated the inbound and outbound trains.


### 2.2. Train Platforming Problem

The train platforming problem, which is also known as the track allocation problem within a station, has attracted much attention. There are four common methods currently used to solve this problem.Cardillo et al. [20] first applied the graph-coloring approach to the train platforming problem, where the same color cannot be assigned to two trains with conflicting routes. Similarly, Zwaneveld et al. [21] and Zwaneveld et al. [22] proposed a node-packing method to allocate two trains without conflicting routes to the same platform. Carey and Carville [6] introduced a manual rescheduling technique to simulate the process of track allocation modification. This simulation allowed the authors to take advantage of the practical experience of dispatchers, which is easy to understand.The most common way to obtain a train platform plan is to construct a single-objective or multiobjective model, such as to minimize the total train running time or maximize passenger convenience in a station. Billionnet [23] formulated a 0-1 integer programming model to represent the track allocation problem in Cardillo et al. [20]; and a heuristic algorithm was introduced to generate the results. Wu et al. [24] proposed a mean-variance optimization model based on Markowitz’s portfolio theory to minimizes resource occupation cost, and they used the simulated annealing algorithm to solve this programming. Pellegrini et al. [25] constructed mixed-integer programming to address the route management in complex junctions under traffic perturbations. A track allocation problem for multidirection high-speed railway stations was proposed in Zhang et al. [26] and Zhang et al. [27]. They considered a typical Chinese high-speed railway station layout, and they noted that the dependency between trains from different directions made resource utilization in the bottleneck area of one station difficult but important.


## 2.1. Train Timetabling Problem

Train timetabling is a classical problem in railway operation. Caprara et al. [4] proved that the train scheduling problem is NP-hard, and they timetabled trains in a single-line one-way railway network. The objective was to maximize train profit, and a Lagrangian relaxation method was proposed to obtain their results. Carey and Crawford [5] designed a heuristic algorithm for a railway network with multiple complex stations linked by multiple one-way lines in each direction by extending the one-way single-station method in Carey and Carville [6]. A multiobjective model was constructed, and the objectives were sequenced by a lexicographic rule. Tian and Niu [7] proposed a biobjective integer programming model to maximize train connections while minimizing the passenger transfer waiting time. In the present study, overtaking was ignored in all stations, and trains from different directions were scheduled independently.D’ariano et al. [8] modeled a railway network in terms of track sections from a microscopic perspective and proposed an alternative graph representation, which was solved by a branch-and-bound method. Sama et al. [9] formulated an integer programming and proposed an ant-colony based method to address the train route section problem in a microscopic network. Zhou and Zhong [10] analyzed the train timetabling problem for a single railway line and designed a resource-constrained scheduling model to minimize the total travel time. Their results were obtained by branch-and-bound and Lagrangian relaxation methods. Sotskov and Gholami [11] used a shifting bottleneck algorithm to design a single-line train schedule. However, every resource of the railway could be occupied only once by every train, which is not reasonable for a railway network connecting several lines. Brannlund et al. [12] constructed an integer programming model and developed a Lagrangian relaxation method to maximize the train profit on a single-line railway network. The static station capacity, that is, the number of platforms, was considered in this model. Nillson and Chen [13] simultaneously optimized the train timetabling and train platforming problems, but the resource utilization in the bottleneck area in a station was ignored.For a highly congested railway line, Jiang et al. [14] proposed a heuristic method to simultaneously optimize the additional train schedule and the choice of the train stops. To solve the cyclic train timetable problem, Zhang et al. [15] extended the time-space network and then introduced the alternating direction method of multipliers. Luan et al. [16] proposed a mixed-integer linear programming model based on cumulative flow variables to optimize train scheduling as well as the tracking maintenance tasks from a microscopic perspective and used the Lagrangian relaxation method to obtain the revised timetable. Zhang et al. [17] optimized the train timetabling problem considering the detailed track assignment on a double-track railway corridor from a mesoscopic level and the running time on the segment as a constant value. The track utilization within a hub station, where more kinds of conflicts, such as those originating due to arrival and departure of two trains from two different railway lines, occur than those in a normal intermediate station, was not considered in Zhang et al. [17].Trains from different directions are always considered separately, which is not possible for some complex stations. Gao et al. [18] addressed the scheduling problem for adding the additional trains on a high-speed rail corridor by designing a three-stage optimization method and Zhang et al. [19] integrated the maintenance planning and train night timetable on the high-speed railway. However, both papers independently treated the inbound and outbound trains.


## 2.2. Train Platforming Problem

The train platforming problem, which is also known as the track allocation problem within a station, has attracted much attention. There are four common methods currently used to solve this problem.Cardillo et al. [20] first applied the graph-coloring approach to the train platforming problem, where the same color cannot be assigned to two trains with conflicting routes. Similarly, Zwaneveld et al. [21] and Zwaneveld et al. [22] proposed a node-packing method to allocate two trains without conflicting routes to the same platform. Carey and Carville [6] introduced a manual rescheduling technique to simulate the process of track allocation modification. This simulation allowed the authors to take advantage of the practical experience of dispatchers, which is easy to understand.The most common way to obtain a train platform plan is to construct a single-objective or multiobjective model, such as to minimize the total train running time or maximize passenger convenience in a station. Billionnet [23] formulated a 0-1 integer programming model to represent the track allocation problem in Cardillo et al. [20]; and a heuristic algorithm was introduced to generate the results. Wu et al. [24] proposed a mean-variance optimization model based on Markowitz’s portfolio theory to minimizes resource occupation cost, and they used the simulated annealing algorithm to solve this programming. Pellegrini et al. [25] constructed mixed-integer programming to address the route management in complex junctions under traffic perturbations. A track allocation problem for multidirection high-speed railway stations was proposed in Zhang et al. [26] and Zhang et al. [27]. They considered a typical Chinese high-speed railway station layout, and they noted that the dependency between trains from different directions made resource utilization in the bottleneck area of one station difficult but important.


## 3. Problem Description

A typical space-time network representation of a train timetable, as shown in Figure2, is a common solution framework currently used by researchers. The space-time path describes train locations in the time dimension. Under the segment-station framework (framework 1), each station is treated as a node, which trains can dwell at or directly pass through. Framework 2 in Figure 2 is a segment-arrival-departure space-time network, where every station node in framework 1 is replaced with arrival and departure events at the station. These two common railway network modeling methods separate trains from different directions and solve them independently. As described in Zhang et al. [17], frameworks 1 and 2 cannot provide a good way to integrate specific track allocation in a station and the utilization of track resources in the throat area into a train timetabling problem.Figure 2
Three railway network frameworks.In China, each platform in a station can typically only be occupied by one train at a time. To address the integration problem of timetabling and platforming, we, therefore, stretch each platform in every station in framework 1, and the train stop point on each platform track is denoted by a physical node. In addition, the arrival and departure boundaries are illustrated as physical nodes to allow the occupation of bottleneck resources to be considered. In practice, there is one basic route that connects one station boundary and one station platform; thus, we assume there exists at most one path between each station boundary and platform. We can extend every physical node along the time dimension and construct a segment-bottleneck-platform space-time network, as shown in Figure2, which provides the possibility of representing trains running in the station. The utilization of station resources by trains from different directions can be further constrained to be conflict-free. In conclusion, this TPST framework can simultaneously optimize train timetables and station resource utilization for all trains.The physical railway network in the proposed framework consists of three types of links and four types of node sets. The physical node setN includes the station arrival boundary node set Na, station departure boundary node set Nd, station platform node set Nst, and segment node set Nse. Node in the segment node set represents the location where convergence or divergence happens, which is different from the node representation from the microscopic perspective. Meanwhile, the platform node set includes the nonstop platform node set Nnsst and stop platform node set Nstst. A stop platform track is sometimes referred to as a siding track, and a nonstop platform track represents the mainline or main track in the station. The physical link set E includes the arrival link set Ea, departure link set Ed, and segment link set Ese. i,j represents a link from nodes i to j. For simplicity of expression, we define e=i,j and oe=i,de=j.In the TPST network, we extend the nodes and links in the physical network along the time dimension.t,τ denote the time index. The vertex set in this space-time network can be defined as V=Va∪Vd∪Vst∪Vse, where Va, Vd, Vst, and Vse correspond to the time extensions of Na, Nd, Nst, and Nse, respectively. Similarly, the space-time platform vertex set can be categorized into a nonstop platform vertex set Vnsst and stop platform vertex set Vstst. v=i,t is the vertex index, and nv=i,tv=t.As shown in Figure3, we use A to denote the arc set of the TPST network, and this set consists of several arc subsets, which are mainly extensions from the physical link set. i,j,t,τ represents the arc from vertex i,t to vertex j,τ. In the same manner, we use g to represent the arc i,j,t,τ, and og=i,dg=j,og^=t,andd^g=τ for simplicity. Aa denotes the set of station arrival arcs from the arrival vertex to the platform vertex, and Ad denotes the set of station departure arcs from the platform vertex to the departure vertex. To model the dwelling of a train within a station, we introduce the station dwell arc set Ast to represent the arcs connecting i,t and i,t+1, where i∈Nstst, which represents a stop train waiting on a siding track. Train movement on a track segment is illustrated by the segment running arc set Ase. The source waiting arc set Ao and sink waiting arc set Ae represent the waiting time at the source node from the earliest available train time and that at the sink node until the latest available train time, respectively. F is the train arc set. In this study, we allowed the cancelation of trains. Therefore, the virtual path set Avi is constructed, and for each train f∈F, a corresponding virtual path is chosen from source vertex δf to the sink vertex γf if it is canceled.Figure 3
Space-time arc in the TPST network.For each trainf∈F, the available node set, link set, vertex set, and arc set can be represented as Nf=Nfa∪Nfd∪Nfst∪Nfse, Ef=Efa∪Efd∪Efse, Vf=Vfa∪Vfd∪Vfst∪Vfse, and Af=Afa∪Afd∪Afst∪Afse∪Afo∪Afe∪Afvi, respectively. The attributes of all types of space-time arcs for one train are listed in Table 1. For each train, nfo and nfd are defined as its source and sink nodes, respectively. The last column in Table 1 presents the cost of each kind of arc. The cost of the segment running arc and the station dwell arc are equal to their respective running times. For the station arrival and departure arcs, αij represents the train preference for station route i,j. For the preferred arrival and departure routei,j, the weight αij can be small. If routei,j is not preferred, we can set the value of αij to be large.Table 1
Attributes of train available arcs in the space-time network.
Train arcFrom vertexTo vertexDescriptionArc costAfoi,ti,t+1i=nfo1Afai,tj,τi,j∈Efaαij∗τ−tAfdi,tj,τi,j∈Efdαij∗τ−tAfsti,ti,t+1i∈Nfst1Afsei,tj,τi,j∈Efseτ−tAfei,ti,t+1i=nfd1Afviσfγf—T (time horizon)


## 4. Problem Formulation and Methods

### 4.1. Assumptions

Without loss of generality, we make the following assumptions to facilitate the construction of our proposed model:(1)
Railway infrastructure information, train information (including train route, departure time window at train source node, and minimum and maximum dwell time at all stations for every train), and all safety time criteria are given(2)
The interlocking system in a station is assumed to be route-lock route-release(3)
The running time of arrival and departure routes in one station is assumed to be constant for every train(4)
A train is considered as a node; train length is ignored(5)
The granularity of time is one minute


### 4.2. Train Timetabling and Platforming Model (TTAPM)

#### 4.2.1. Notations and Decision Variables

The notations and binary decision variables used in the model are listed in Tables2 and 3.Table 2
Model notations.
NotationDefinitionkStation index∈KKfStations for trainfTkrRunning time of arriving or departing route at stationk∈KTrHeadway for utilization of track resources in the throat areanklNumber of railway lines that merge or disjoin at stationkcgfCost of arcg for train fδf+v,δf−vArcs of trainf that flow out of/into vertex vσf,γfOrigin and destination vertex for trainfDkfMinimum dwell time of trainf∈F at station k∈KDkfmMaximum dwell time of trainf∈F at station k∈KAksStation dwell arcs at stationkTsUsage headway of a stop platform trackTable 3
Model decision variables.
VariableDefinitionxgfBinary decision variable that indicates whether trainf∈F uses arc g (=1) or not (=0)ygfBinary decision variable that indicates whether trainf∈F implicitly uses waiting arc g∈Ast (=1) or not (=0)


#### 4.2.2. Objective Function

Objective functions for the train timetabling problem typically minimize the total weighted running time of trains [2, 28] or maximize the satisfaction of passengers [29]. For the train platforming problem, the objective function typically minimizes the occupation time of station resources [24, 26]. In our model, the objective function aims to minimize the total weighted train running costs:(1)minZ1=∑f∈F∑g∈Afcgf⋅xgf.


#### 4.2.3. Constraints

(1) Train Flow Balance Constraints.(2)∑g∈δf+σfxgf=1,∀f∈F,∑g∈δf−vxgf−∑g∈δf+vxgf=0,∀v∈Vf\σf,γf,∀f∈F.(2) Minimum and Maximum Train Dwell Time Constraints.(3)1−∑g∈Afvixgf⋅Dkf≤∑g∈Aks∩Afxgf≤1−∑g∈Afvixgf⋅Dkfm,∀f∈F,∀k∈Kf.(3) Train Headway Constraint on a Track Segment. The headway constraints on a track segment include arrival headway constraints, departure headway constraints, and overtaking constraints. The overtaking constraints can be processed as the arrival and departure headway constraints, and we refer the reader to Kroon and Peeters [30] for more details on this.To build a model considering the headway constraints on a track segment, Zhang et al. [17] assumed the running time of all trains on a single track segment to be the same and constructed the incompatible arc set for each segment running arc. Cacchiani et al. [31] allowed the running time on the segment arcs to vary and constructed the incompatible vertex set for each station arrival or departure node. In this paper, we present the construction of an incompatible vertex set for each departure vertex, segment vertex, and arrival vertex. As depicted in Figure 4, for each vertex v∈Vd∪Vse, we define the incompatible vertex set for the departure headway constraints as ψv1=v′|tv′∈tv,tv+Td,nv′=nv; for each vertex v∈Va∪Vse, we define the incompatible vertex set for arrival headway constraints as ψv2=v′|tv′∈tv,tv+Ta,nv′=nv. Notably, Td and Ta are the departure and arrival headway times on the track segment, respectively. We introduce the auxiliary decision variable xvf to denote that train f occupies vertex v (=1) or not (=0). The connection between arc occupation and vertex occupation can be expressed as the following equations:(4)xvf=∑g∈δf−v−Afe−Afvixgf,∀v∈Vfd∪Vfse,∀f∈F,(5)xvf=∑g∈δf+v−Afo−Afvixgf,∀v∈Vfa,∀f∈F.Figure 4
Illustration of the arrival and departure constraints on a track segment.Therefore, the arrival and departure headway constraints on a track segment can be represented as follows:(6)∑v′∈ψv1∑f:v′∈Vfxv′f≤1,∀v∈Vd∪Vse,∑v′∈ψv2∑f:v′∈Vfxv′f≤1,∀v∈Vse∪Va.(4) Headway Constraints at a Station Bottleneck Area. The headway constraints at a station throat area involve the receiving-receiving headway, departure-departure headway, and receiving-departure headway. The first two in a station on a single railway line can be guaranteed by the segment headway for all trains.For a station connecting more than one railway line, the receiving-receiving headway for trains from the same arrival boundary node and departure-departure headway for trains to the same departure boundary node can also be guaranteed by the arrival and departure headways on a track segment, respectively. However, the receiving-receiving and departure-departure headways between two trains from two different railway lines in a hub station, as shown in Figure5, should be enforced.Figure 5
Illustration of receiving-receiving and departure-departure conflicts in a hub station.Different from Zhang et al. [17], in this paper, we consider the railway network rather than a railway corridor. According to the microscopic network view of a certain hub station k, we can enumerate the incompatible receiving-receiving physical link pair set ψkaa and incompatible departure-departure physical link pair set ψkdd for two arrival links or two departure links that connect two different railway lines. As shown in Figure 5, the physical link 1,11 conflicts with physical link 9,6 because these two routes occupy the same track resource in the bottleneck area. Similarly, the physical departure link 11,7 is incompatible with link 6,15. Accordingly, given the layout of this station, we have(7)ψ1aa=1,11,9,6,1,6,9,6,1,11,9,11,ψ1dd=11,7,6,15,6,7,6,15,11,7,11,15.When we have the topology for all multiline stations from the microscopic perspective, we can preprocess the incompatible physical link pair set, and then the arrival-arrival and departure-departure headway constraints for different railway lines at the throat area in the multiline stations can be expressed as follows:(8)∑g:og,dg∈ξ,o^g∈t,t+Tkr+Tr∑f:g∈Afxgf≤1,∀t,∀ξ∈ψkaa∪ψkdd,∀k:nkl>1.For all stations, because we allow trains to use all possible platform tracks so that we can schedule all trains simultaneously, we must construct headway constraints to avoid conflicts between an arrival physical link and departure physical link. In the same manner, from the topology for all stations, we can enumerate the incompatible receiving-departure physical link pair set for all trainsψkad, and then the arrival-departure headway can be constrained as follows:(9)∑g:og,dg∈ξ,o^g∈t,t+Tkr+Tr∑f:g∈Afxgf≤1,∀t,∀ξ∈ψkad,∀k.(5) Headway Constraints on a Stop Platform Track. When two trains occupy the same siding track, there should be headway time between the two occupations. To facilitate a model of this type of headway, we introduce the auxiliary decision variable ygf to represent train f having already left the siding track og but still occupying this siding track implicitly due to safety requirements. The map between the implicit and actual occupations of the station dwell arcs can be expressed as equation (10). Then, the headway constraints on the siding tracks can be transformed into a unique occupation of the siding track, whether implicit or actual, as shown by equation (11):(10)∑g′∈Afd|o^g′∈o^g−Ts,o^gxg′f=ygf,∀g∈Afst,∀f∈F,(11)∑f:g∈Afxgf+ygf≤1,∀g∈Ast.(6) Domain of Variables. The domains of variables are given as follows:(12)xgf∈0,1,∀f∈F,∀g∈Af,ygf∈0,1,∀f∈F,∀g∈Afst,xvf∈0,1,∀f∈F,∀v∈Vfd∪Vfse∪Vfa.


### 4.3. Solution Method

The TPST network can reduce not only the number of variables compared to modeling from a microscopic perspective but also the number of constraints. Some constraints that can be satisfied when constructing the network are listed as follows:(1)
No dwelling at the mainline of a station: no train can dwell at the main track in a station in our model because there is no dwell arc extended from a nonstop platform track.(2)
No change of a siding track can occur when a train dwells on it. A train cannot move to other siding tracks in the same station it is dwelling at, and there is no transfer arc from one siding track to another.In addition, the construction of the incompatible link and arc sets facilitates the modeling of difficult headway constraints in the train timetabling and platforming problems.Based on the above improvements in previous studies, we used the CPLEX solver to obtain our results. All instances presented in this paper were implemented in Python 3.7 and tested on a personal Windows computer with a 2.80 GHz processor and 16 GB RAM.


## 4.1. Assumptions

Without loss of generality, we make the following assumptions to facilitate the construction of our proposed model:(1)
Railway infrastructure information, train information (including train route, departure time window at train source node, and minimum and maximum dwell time at all stations for every train), and all safety time criteria are given(2)
The interlocking system in a station is assumed to be route-lock route-release(3)
The running time of arrival and departure routes in one station is assumed to be constant for every train(4)
A train is considered as a node; train length is ignored(5)
The granularity of time is one minute


## 4.2. Train Timetabling and Platforming Model (TTAPM)

### 4.2.1. Notations and Decision Variables

The notations and binary decision variables used in the model are listed in Tables2 and 3.Table 2
Model notations.
NotationDefinitionkStation index∈KKfStations for trainfTkrRunning time of arriving or departing route at stationk∈KTrHeadway for utilization of track resources in the throat areanklNumber of railway lines that merge or disjoin at stationkcgfCost of arcg for train fδf+v,δf−vArcs of trainf that flow out of/into vertex vσf,γfOrigin and destination vertex for trainfDkfMinimum dwell time of trainf∈F at station k∈KDkfmMaximum dwell time of trainf∈F at station k∈KAksStation dwell arcs at stationkTsUsage headway of a stop platform trackTable 3
Model decision variables.
VariableDefinitionxgfBinary decision variable that indicates whether trainf∈F uses arc g (=1) or not (=0)ygfBinary decision variable that indicates whether trainf∈F implicitly uses waiting arc g∈Ast (=1) or not (=0)


### 4.2.2. Objective Function

Objective functions for the train timetabling problem typically minimize the total weighted running time of trains [2, 28] or maximize the satisfaction of passengers [29]. For the train platforming problem, the objective function typically minimizes the occupation time of station resources [24, 26]. In our model, the objective function aims to minimize the total weighted train running costs:(1)minZ1=∑f∈F∑g∈Afcgf⋅xgf.


### 4.2.3. Constraints

(1) Train Flow Balance Constraints.(2)∑g∈δf+σfxgf=1,∀f∈F,∑g∈δf−vxgf−∑g∈δf+vxgf=0,∀v∈Vf\σf,γf,∀f∈F.(2) Minimum and Maximum Train Dwell Time Constraints.(3)1−∑g∈Afvixgf⋅Dkf≤∑g∈Aks∩Afxgf≤1−∑g∈Afvixgf⋅Dkfm,∀f∈F,∀k∈Kf.(3) Train Headway Constraint on a Track Segment. The headway constraints on a track segment include arrival headway constraints, departure headway constraints, and overtaking constraints. The overtaking constraints can be processed as the arrival and departure headway constraints, and we refer the reader to Kroon and Peeters [30] for more details on this.To build a model considering the headway constraints on a track segment, Zhang et al. [17] assumed the running time of all trains on a single track segment to be the same and constructed the incompatible arc set for each segment running arc. Cacchiani et al. [31] allowed the running time on the segment arcs to vary and constructed the incompatible vertex set for each station arrival or departure node. In this paper, we present the construction of an incompatible vertex set for each departure vertex, segment vertex, and arrival vertex. As depicted in Figure 4, for each vertex v∈Vd∪Vse, we define the incompatible vertex set for the departure headway constraints as ψv1=v′|tv′∈tv,tv+Td,nv′=nv; for each vertex v∈Va∪Vse, we define the incompatible vertex set for arrival headway constraints as ψv2=v′|tv′∈tv,tv+Ta,nv′=nv. Notably, Td and Ta are the departure and arrival headway times on the track segment, respectively. We introduce the auxiliary decision variable xvf to denote that train f occupies vertex v (=1) or not (=0). The connection between arc occupation and vertex occupation can be expressed as the following equations:(4)xvf=∑g∈δf−v−Afe−Afvixgf,∀v∈Vfd∪Vfse,∀f∈F,(5)xvf=∑g∈δf+v−Afo−Afvixgf,∀v∈Vfa,∀f∈F.Figure 4
Illustration of the arrival and departure constraints on a track segment.Therefore, the arrival and departure headway constraints on a track segment can be represented as follows:(6)∑v′∈ψv1∑f:v′∈Vfxv′f≤1,∀v∈Vd∪Vse,∑v′∈ψv2∑f:v′∈Vfxv′f≤1,∀v∈Vse∪Va.(4) Headway Constraints at a Station Bottleneck Area. The headway constraints at a station throat area involve the receiving-receiving headway, departure-departure headway, and receiving-departure headway. The first two in a station on a single railway line can be guaranteed by the segment headway for all trains.For a station connecting more than one railway line, the receiving-receiving headway for trains from the same arrival boundary node and departure-departure headway for trains to the same departure boundary node can also be guaranteed by the arrival and departure headways on a track segment, respectively. However, the receiving-receiving and departure-departure headways between two trains from two different railway lines in a hub station, as shown in Figure5, should be enforced.Figure 5
Illustration of receiving-receiving and departure-departure conflicts in a hub station.Different from Zhang et al. [17], in this paper, we consider the railway network rather than a railway corridor. According to the microscopic network view of a certain hub station k, we can enumerate the incompatible receiving-receiving physical link pair set ψkaa and incompatible departure-departure physical link pair set ψkdd for two arrival links or two departure links that connect two different railway lines. As shown in Figure 5, the physical link 1,11 conflicts with physical link 9,6 because these two routes occupy the same track resource in the bottleneck area. Similarly, the physical departure link 11,7 is incompatible with link 6,15. Accordingly, given the layout of this station, we have(7)ψ1aa=1,11,9,6,1,6,9,6,1,11,9,11,ψ1dd=11,7,6,15,6,7,6,15,11,7,11,15.When we have the topology for all multiline stations from the microscopic perspective, we can preprocess the incompatible physical link pair set, and then the arrival-arrival and departure-departure headway constraints for different railway lines at the throat area in the multiline stations can be expressed as follows:(8)∑g:og,dg∈ξ,o^g∈t,t+Tkr+Tr∑f:g∈Afxgf≤1,∀t,∀ξ∈ψkaa∪ψkdd,∀k:nkl>1.For all stations, because we allow trains to use all possible platform tracks so that we can schedule all trains simultaneously, we must construct headway constraints to avoid conflicts between an arrival physical link and departure physical link. In the same manner, from the topology for all stations, we can enumerate the incompatible receiving-departure physical link pair set for all trainsψkad, and then the arrival-departure headway can be constrained as follows:(9)∑g:og,dg∈ξ,o^g∈t,t+Tkr+Tr∑f:g∈Afxgf≤1,∀t,∀ξ∈ψkad,∀k.(5) Headway Constraints on a Stop Platform Track. When two trains occupy the same siding track, there should be headway time between the two occupations. To facilitate a model of this type of headway, we introduce the auxiliary decision variable ygf to represent train f having already left the siding track og but still occupying this siding track implicitly due to safety requirements. The map between the implicit and actual occupations of the station dwell arcs can be expressed as equation (10). Then, the headway constraints on the siding tracks can be transformed into a unique occupation of the siding track, whether implicit or actual, as shown by equation (11):(10)∑g′∈Afd|o^g′∈o^g−Ts,o^gxg′f=ygf,∀g∈Afst,∀f∈F,(11)∑f:g∈Afxgf+ygf≤1,∀g∈Ast.(6) Domain of Variables. The domains of variables are given as follows:(12)xgf∈0,1,∀f∈F,∀g∈Af,ygf∈0,1,∀f∈F,∀g∈Afst,xvf∈0,1,∀f∈F,∀v∈Vfd∪Vfse∪Vfa.


## 4.2.1. Notations and Decision Variables

The notations and binary decision variables used in the model are listed in Tables2 and 3.Table 2
Model notations.
NotationDefinitionkStation index∈KKfStations for trainfTkrRunning time of arriving or departing route at stationk∈KTrHeadway for utilization of track resources in the throat areanklNumber of railway lines that merge or disjoin at stationkcgfCost of arcg for train fδf+v,δf−vArcs of trainf that flow out of/into vertex vσf,γfOrigin and destination vertex for trainfDkfMinimum dwell time of trainf∈F at station k∈KDkfmMaximum dwell time of trainf∈F at station k∈KAksStation dwell arcs at stationkTsUsage headway of a stop platform trackTable 3
Model decision variables.
VariableDefinitionxgfBinary decision variable that indicates whether trainf∈F uses arc g (=1) or not (=0)ygfBinary decision variable that indicates whether trainf∈F implicitly uses waiting arc g∈Ast (=1) or not (=0)


## 4.2.2. Objective Function

Objective functions for the train timetabling problem typically minimize the total weighted running time of trains [2, 28] or maximize the satisfaction of passengers [29]. For the train platforming problem, the objective function typically minimizes the occupation time of station resources [24, 26]. In our model, the objective function aims to minimize the total weighted train running costs:(1)minZ1=∑f∈F∑g∈Afcgf⋅xgf.


## 4.2.3. Constraints

(1) Train Flow Balance Constraints.(2)∑g∈δf+σfxgf=1,∀f∈F,∑g∈δf−vxgf−∑g∈δf+vxgf=0,∀v∈Vf\σf,γf,∀f∈F.(2) Minimum and Maximum Train Dwell Time Constraints.(3)1−∑g∈Afvixgf⋅Dkf≤∑g∈Aks∩Afxgf≤1−∑g∈Afvixgf⋅Dkfm,∀f∈F,∀k∈Kf.(3) Train Headway Constraint on a Track Segment. The headway constraints on a track segment include arrival headway constraints, departure headway constraints, and overtaking constraints. The overtaking constraints can be processed as the arrival and departure headway constraints, and we refer the reader to Kroon and Peeters [30] for more details on this.To build a model considering the headway constraints on a track segment, Zhang et al. [17] assumed the running time of all trains on a single track segment to be the same and constructed the incompatible arc set for each segment running arc. Cacchiani et al. [31] allowed the running time on the segment arcs to vary and constructed the incompatible vertex set for each station arrival or departure node. In this paper, we present the construction of an incompatible vertex set for each departure vertex, segment vertex, and arrival vertex. As depicted in Figure 4, for each vertex v∈Vd∪Vse, we define the incompatible vertex set for the departure headway constraints as ψv1=v′|tv′∈tv,tv+Td,nv′=nv; for each vertex v∈Va∪Vse, we define the incompatible vertex set for arrival headway constraints as ψv2=v′|tv′∈tv,tv+Ta,nv′=nv. Notably, Td and Ta are the departure and arrival headway times on the track segment, respectively. We introduce the auxiliary decision variable xvf to denote that train f occupies vertex v (=1) or not (=0). The connection between arc occupation and vertex occupation can be expressed as the following equations:(4)xvf=∑g∈δf−v−Afe−Afvixgf,∀v∈Vfd∪Vfse,∀f∈F,(5)xvf=∑g∈δf+v−Afo−Afvixgf,∀v∈Vfa,∀f∈F.Figure 4
Illustration of the arrival and departure constraints on a track segment.Therefore, the arrival and departure headway constraints on a track segment can be represented as follows:(6)∑v′∈ψv1∑f:v′∈Vfxv′f≤1,∀v∈Vd∪Vse,∑v′∈ψv2∑f:v′∈Vfxv′f≤1,∀v∈Vse∪Va.(4) Headway Constraints at a Station Bottleneck Area. The headway constraints at a station throat area involve the receiving-receiving headway, departure-departure headway, and receiving-departure headway. The first two in a station on a single railway line can be guaranteed by the segment headway for all trains.For a station connecting more than one railway line, the receiving-receiving headway for trains from the same arrival boundary node and departure-departure headway for trains to the same departure boundary node can also be guaranteed by the arrival and departure headways on a track segment, respectively. However, the receiving-receiving and departure-departure headways between two trains from two different railway lines in a hub station, as shown in Figure5, should be enforced.Figure 5
Illustration of receiving-receiving and departure-departure conflicts in a hub station.Different from Zhang et al. [17], in this paper, we consider the railway network rather than a railway corridor. According to the microscopic network view of a certain hub station k, we can enumerate the incompatible receiving-receiving physical link pair set ψkaa and incompatible departure-departure physical link pair set ψkdd for two arrival links or two departure links that connect two different railway lines. As shown in Figure 5, the physical link 1,11 conflicts with physical link 9,6 because these two routes occupy the same track resource in the bottleneck area. Similarly, the physical departure link 11,7 is incompatible with link 6,15. Accordingly, given the layout of this station, we have(7)ψ1aa=1,11,9,6,1,6,9,6,1,11,9,11,ψ1dd=11,7,6,15,6,7,6,15,11,7,11,15.When we have the topology for all multiline stations from the microscopic perspective, we can preprocess the incompatible physical link pair set, and then the arrival-arrival and departure-departure headway constraints for different railway lines at the throat area in the multiline stations can be expressed as follows:(8)∑g:og,dg∈ξ,o^g∈t,t+Tkr+Tr∑f:g∈Afxgf≤1,∀t,∀ξ∈ψkaa∪ψkdd,∀k:nkl>1.For all stations, because we allow trains to use all possible platform tracks so that we can schedule all trains simultaneously, we must construct headway constraints to avoid conflicts between an arrival physical link and departure physical link. In the same manner, from the topology for all stations, we can enumerate the incompatible receiving-departure physical link pair set for all trainsψkad, and then the arrival-departure headway can be constrained as follows:(9)∑g:og,dg∈ξ,o^g∈t,t+Tkr+Tr∑f:g∈Afxgf≤1,∀t,∀ξ∈ψkad,∀k.(5) Headway Constraints on a Stop Platform Track. When two trains occupy the same siding track, there should be headway time between the two occupations. To facilitate a model of this type of headway, we introduce the auxiliary decision variable ygf to represent train f having already left the siding track og but still occupying this siding track implicitly due to safety requirements. The map between the implicit and actual occupations of the station dwell arcs can be expressed as equation (10). Then, the headway constraints on the siding tracks can be transformed into a unique occupation of the siding track, whether implicit or actual, as shown by equation (11):(10)∑g′∈Afd|o^g′∈o^g−Ts,o^gxg′f=ygf,∀g∈Afst,∀f∈F,(11)∑f:g∈Afxgf+ygf≤1,∀g∈Ast.(6) Domain of Variables. The domains of variables are given as follows:(12)xgf∈0,1,∀f∈F,∀g∈Af,ygf∈0,1,∀f∈F,∀g∈Afst,xvf∈0,1,∀f∈F,∀v∈Vfd∪Vfse∪Vfa.


## 4.3. Solution Method

The TPST network can reduce not only the number of variables compared to modeling from a microscopic perspective but also the number of constraints. Some constraints that can be satisfied when constructing the network are listed as follows:(1)
No dwelling at the mainline of a station: no train can dwell at the main track in a station in our model because there is no dwell arc extended from a nonstop platform track.(2)
No change of a siding track can occur when a train dwells on it. A train cannot move to other siding tracks in the same station it is dwelling at, and there is no transfer arc from one siding track to another.In addition, the construction of the incompatible link and arc sets facilitates the modeling of difficult headway constraints in the train timetabling and platforming problems.Based on the above improvements in previous studies, we used the CPLEX solver to obtain our results. All instances presented in this paper were implemented in Python 3.7 and tested on a personal Windows computer with a 2.80 GHz processor and 16 GB RAM.


## 5. Experiment Results and Discussion

In this section, we report several computational experiments to verify the validity of our proposed TPST network and model based on a small-sized and a medium-sized railway networks with three and nine stations, respectively. We test the performance of our model with the change of some parameters. The benefits of the railway network modeling method from the mesoscopic perspective compared with the microscopic and macroscopic perspective are also given.


### 5.1. Small-Sized Rail Network and Performance Analysis

The small rail network in this section consists of three stations with 37 nodes and 66 physical links, as shown in Figure6. The running time of each track segment between two stations is 4 min, and the running time of two track segments that connect two railway lines (i.e., physical links 36,34 and 35,37) is 2 min. The running time of an arrival or departure route at Station 1 is 2 min, while that at Stations 2 and 3 is 1 min. The time horizon T is set to 120 min in all cases. The cost for every virtual path is set to the same value with time horizon.Figure 6
Three-station network with 37 nodes and 66 physical links.All basic train data are listed in Table4. In the table, the second and third columns give information on the train source and sink nodes. The trains’ station sequences are listed in the fourth column. We also limit the train start time window at its source node in the fifth column. In the last column, the minimum train dwell time at each station is shown.Table 4
Train data for small railway network.
Train IDFrom nodeTo nodeStationStart time windowMin dwell12522; 1(4, 9)1; 123321; 3(11, 16)1; 0325322; 1;3(7, 12)0; 1;141241; 2(1, 6)1; 151321; 3(2, 7)1; 1633243; 1;2(2, 7)1; 1;173241; 2(4, 9)1; 083321; 3(6, 11)0; 093323; 1(7, 12)0; 1103343; 1(10, 15)1; 0112522; 1(10, 15)1; 0122542; 1(14, 19)0; 1131241; 2(7, 12)1; 1141241; 2(8, 13)0; 11525322; 1;3(17, 22)0; 1;0161241; 2(13, 18)0; 1171241; 2(17, 22)1; 0182522; 1(25, 30)1; 11925322; 1;3(33, 38)1; 1;1203343; 1(14, 19)0; 12133243; 1;2(17, 22)1; 1;0221321; 3(15, 20)1; 0233321; 3(20, 25)1; 02433243; 1;2(21, 26)0; 1;0253323; 1(24, 29)1; 1263343; 1(30, 35)0; 0273321; 3(24, 29)0; 02833243; 1;2(35, 40)1; 1;1293321; 3(28, 33)1; 1302522; 1(30, 35)0; 0311241; 2(20, 25)1; 03225322; 1;3(37, 42)1; 1;1331241; 2(24, 29)0; 0343321; 3(32, 37)0; 0353343; 1(37, 42)1; 13633243; 1;2(40, 45)0; 1;0371241; 2(39, 44)1; 1381241; 2(43, 48)1; 0393321; 3(44, 49)1; 1403343; 1(44, 49)0; 14133243; 1;2(47, 52)1; 1;04225322; 1;3(44, 49)0; 1;1433321; 3(50, 55)1; 0441241; 2(47, 52)1; 0


#### 5.1.1. Performance Comparison with an Increase in the Number of Trains

In this subsection, we report the CPU running time of our model by CPLEX with an increase in the number of trains. The length of the start time window for each train maintains a value of 5. The maximum dwell time for each train at each station is 4 min more than the minimum dwell time. We consider 9 scenarios with the number of trains increasing from 5 to 44, as shown in Table5. Under each scenario, 10 instances were tested and the CPU running time is given as the mean value of all instances in one scenario.Table 5
Performance comparison with an increase in the number of trains.
ScenarioNumber of trainsObjectiveCPU time (s)1-1595.90.11-210205.91.31-315306.161-420417.16.31-525553.2123.01-630667.0116.41-735782.8163.21-840888.2366.11-944997.9429.8As can be seen from the table, the amount of CPU time required to obtain a result by the CPLEX solver generally increases when the number of trains increases from 5 to 44, except in scenarios 1-6. However, all results can be obtained within a reasonable time.We also illustrate the optimal timetable and platform plan in scenarios 1-9 for Line 1 and Line 2 in Figures7 and 8, respectively. In total, two trains (Trains 3 and 6) are not scheduled into this railway network. All scheduled trains satisfy the safety requirements, which verifies the validity of our proposed model.Figure 7
Train timetabling and platforming result for Line 1.Figure 8
Train timetabling and platforming result for Line 2.


#### 5.1.2. Performance Comparison with an Increase in the Number of Train Paths

In this subsection, we report the difference in solving performance when the number of train paths increases and the number of trains is fixed to be 30. For each train, the number of paths depends on the lengths of the start time and dwelling time windows in each station. We consider two environments. In the first environment, the length of the start time window is variable, and the length of the station dwell time window is fixed, and in the second environment, the contrary is true. We constructed 6 and 5 scenarios for each environment, as shown in Table6.Table 6
Performance comparison with an increase in the number of train paths.
ScenarioLength of start time window (min)Length of station dwell time window (min)ObjectiveCPU time (s)2-124902.845.32-25760.3116.42-310692.2177.72-415691.3379.72-520691.1820.62-625691.11041.62-742902.617.42-85775.3285.42-910708.6231.62-1015703.5402.12-1120703.51566As listed in Table6, in scenarios 2-1 to 2-6, the start time window varies from 2 min to 25 min, while the station dwell time window is fixed at 4 min. Further, in scenarios 2-7 to 2-11, the station dwell time window varies from 2 min to 20 min, while the start time window is fixed at 4 min. Additionally, the CPU running time increases rapidly when the start time window or the station dwell time window widens. This indicates that an increase in the number of train paths leads to model complexity and longer solving times. Meanwhile, extending the length of the start time window leads to an improvement in the quality of the result and a reduction in the CPU running time, as compared with the case when the length of the station dwell time window is increased.


#### 5.1.3. Benefit of Mesoscopic Network Compared with Microscopic Network

In the TPST network, we do not divide the track resources of a track segment into block sections, which is the modeling unit from the microscopic perspective. Instead, we split the platform track and consider the track resources in a station bottleneck area in terms of station route, which allows us to assign station resources, as opposed to the case in the macroscopic solving framework. Therefore, the TPST network can be seen as a modeling method from the mesoscopic perspective. We assume that there are 10 extra block sections of a track segment at each direction between two stations, and every place that will be used for trains to change the route in the throat area is marked as a node from the microscopic perspective.Table7 provides a comparison of network scale from the microscopic and mesoscopic perspectives. As can be seen, the number of nodes can be reduced by at least 70% from 132 in the microscopic framework to 37 in our proposed framework, and the number of physical links can be reduced by almost 80% from 320 to 66. When we extend the physical network along the time dimension, the differences between the numbers of vertices and arcs from the two perspectives will be even larger. Therefore, the number of decision variables in our proposed model is also decreased sharply compared to the microscopic model.Table 7
Network size comparison from the microscopic and mesoscopic perspectives.
PerspectiveNode numberPhysical link numberMicroscopic132>320Mesoscopic3766


#### 5.1.4. Benefit of Mesoscopic Network Compared with Macroscopic Network

As described in Cacchiani et al. [31], in the macroscopic method, only the arrival and departure time constraints enforce train headway within a station. Further, as explained in Zhang et al. [2], the maximum number of trains within a station at a time should not exceed the station capacity. The station track capacity generally refers to the total number of station platform tracks. As we mentioned earlier, in the mesoscopic railway network, the detailed station layout can be considered, which reduces the difficulty of separating trains according to the train direction in a complex hub station. The constraints within a station are enforced by not only the arrival (departure) headway but also the platform usage and bottleneck resources.Figure9 represents the results within Station 1 between 48 min and 65 min in Figure 7. The solid line denotes the train paths solved by our proposed model from the mesoscopic perspective. Train 32 cannot arrive at the arrival boundary of Station 1 earlier than 48 min because of other train path constraints (such as minimum dwell time, start time at the origin node, and running time). According to the station layout, if train 32 arrives at the station through node 15 and departs from node 16, only platforms 8 and 9 can be used.Figure 9
Comparison of the results from the mesoscopic and macroscopic perspectives.(1) If the Station Capacity Is Set as the Total Number of Platforms for Station 1. Train 32 will arrive at Station 1 at 51 min constrained by the arrival headway from the macroscopic perspective, and, no platform is available for this train at 53 min.(2) If the Station Capacity Is Set as 2 (Platforms 8, 9) for Station 1. Train 32 will arrive at Station 1 at 53 min constrained by the arrival headway from the macroscopic perspective. Path 1 and Path 2 can be chosen as the local route for this train. However, the receiving route of both paths will conflict with the departure route of Train 28.Consequently, the mesoscopic modeling framework, which considers the station resource, can generate a train timetable as well as a feasible train platform plan.


### 5.2. Medium-Sized Rail Network and Performance Analysis

To further verify the validity of our model, we modify our small-sized rail network to a medium-sized one comprising nine stations on two railway lines with 97 nodes and 188 physical links, as shown in Figure10. The running time of each track segment on each railway line is either 3 or 4 min. The running time of a single-station route is 2 min at Stations 1, 4, 5, 8, 9, and 1 min at the remaining stations. The other parameters can be set as those in the cases of a small-sized railway network.Figure 10
Medium-sized rail network.The train data are listed in Table8. In total, 48 trains having conflicting routes are planned to be scheduled. The maximum dwell time for every train at each station is 5 min more than its minimum dwell time.Table 8
Train data for medium-sized railway network.
Train IDFrom nodeTo nodeStationStart time windowMin dwell186468; 6;1; 2;4(1, 6)1; 0;1; 0;0247874; 2;1; 6;8(2, 7)1; 0;0; 1;1396569; 7;1; 3;5(2, 7)1; 0;0; 0;0457465; 3;1; 2;4(3, 8)1; 0;1; 1;1586568; 6;1; 3;5(4, 9)1; 1;1; 0;1647564; 2;1; 3;5(5, 10)1; 1;1; 1;1796469; 7;1; 2;4(5, 10)0; 0;1; 0;1857875; 3;1; 6;8(6, 11)1; 1;1; 0;1986468; 6;1; 2;4(7, 12)0; 0;0; 1;11047874; 2;1; 6;8(8, 13)0; 1;1; 0;11196879; 7;6; 8(8, 13)1; 1;0; 01257975; 3;1; 7;9(9, 14)1; 1;1; 1;11386468; 6;1; 2;4(10, 15)1; 1;0; 1;01496569; 7;1; 3;5(11, 16)1; 1;1; 1;01547974; 2;1; 7;9(11, 16)0; 1;1; 1;11657975; 3;1; 7;9(12, 17)1; 1;1; 1;11786468; 6;1; 2;4(13, 18)1; 1;1; 0;11847564; 2;1; 3;5(14, 19)1; 1;1; 1;11996569; 7;1; 3;5(14, 19)0; 1;1; 1;02057465; 3;1; 2;4(15, 20)1; 1;1; 0;12186978; 6;7; 9(16, 21)1; 1;1; 12247874; 2;1; 6;8(17, 22)0; 0;0; 0;02396569; 7;1; 3;5(17, 22)0; 1;1; 0;12457465; 3;1; 2;4(18, 23)0; 0;1; 1;12586468; 6;1; 2;4(19, 24)1; 1;1; 1;12647564; 2;1; 3;5(20, 25)1; 1;1; 1;12796569; 7;1; 3;5(20, 25)0; 0;1; 1;12857875; 3;1; 6;8(21, 26)1; 0;1; 0;12986568; 6;1; 3;5(22, 27)0; 1;1; 1;13047874; 2;1; 6;8(23, 28)1; 0;1; 1;03196569; 7;1; 3;5(23, 28)1; 1;1; 1;13257975; 3;1; 7;9(24, 29)1; 0;1; 1;03386468; 6;1; 2;4(25, 30)0; 0;1; 0;13447564; 2;1; 3;5(26, 31)1; 1;1; 0;13596569; 7;1; 3;5(26, 31)1; 1;1; 1;13657465; 3;1; 2;4(27, 32)1; 1;1; 0;13786468; 6;1; 2;4(28, 33)1; 0;1; 1;13847564; 2;1; 3;5(29, 34)0; 1;1; 1;13996569; 7;1; 3;5(29, 34)1; 1;1; 1;14057975; 3;1; 7;9(30, 35)0; 1;0; 1;04186468; 6;1; 2;4(31, 36)1; 1;1; 1;14296879; 7;6; 8(32, 37)1; 1;1; 14357465; 3;1; 2;4(33, 38)0; 1;1; 1;14486468; 6;1; 2;4(34, 39)1; 1;1; 1;04557975; 3;1; 7;9(36, 41)0; 1;1; 0;14686468; 6;1; 2;4(37, 42)1; 1;1; 0;14757465; 3;1; 2;4(39, 44)1; 1;1; 0;14886978; 6;7; 9(40, 45)0; 1;0; 1In this section, we also discuss the efficiency of problem solving when the number of trains is increased, as presented in Table9. The solving time for each case is limited to 1 hour. The upper and lower bounds are listed in the second and third columns. The GAP in the fourth column is the difference between the upper and lower bounds divided by the upper bound. In general, for a medium-sized rail network, the greater the number of trains, the bigger the gap. Moreover, the gap is still acceptable in the case with 48 trains. The final results for 48 trains are represented in Figures 11 and 12. A total of 11 trains cannot be scheduled into the timetable due to the conflicting routes, and the paths of all the scheduled trains satisfy all the constraints. Based on these results, it can be said that our proposed modeling method can successfully solve relatively large-scale cases.Table 9
Performance comparison with an increase in the number of trains for medium-sized cases.
Number of trainsUpper boundLower boundGAP (%)CPU time (s)1-15700691.11.2836001-20959.5951.70.8136001-2512071186.41.1736001-301598.71513.65.3236001-352040.41837.69.9436001-402424.82203.69.1236001-482983.62622.512.063600Figure 11
Train timetabling and platforming result for Line 1 for medium-sized rail network.Figure 12
Train timetabling and platforming result for Line 2 for medium-sized rail network.


## 5.1. Small-Sized Rail Network and Performance Analysis

The small rail network in this section consists of three stations with 37 nodes and 66 physical links, as shown in Figure6. The running time of each track segment between two stations is 4 min, and the running time of two track segments that connect two railway lines (i.e., physical links 36,34 and 35,37) is 2 min. The running time of an arrival or departure route at Station 1 is 2 min, while that at Stations 2 and 3 is 1 min. The time horizon T is set to 120 min in all cases. The cost for every virtual path is set to the same value with time horizon.Figure 6
Three-station network with 37 nodes and 66 physical links.All basic train data are listed in Table4. In the table, the second and third columns give information on the train source and sink nodes. The trains’ station sequences are listed in the fourth column. We also limit the train start time window at its source node in the fifth column. In the last column, the minimum train dwell time at each station is shown.Table 4
Train data for small railway network.
Train IDFrom nodeTo nodeStationStart time windowMin dwell12522; 1(4, 9)1; 123321; 3(11, 16)1; 0325322; 1;3(7, 12)0; 1;141241; 2(1, 6)1; 151321; 3(2, 7)1; 1633243; 1;2(2, 7)1; 1;173241; 2(4, 9)1; 083321; 3(6, 11)0; 093323; 1(7, 12)0; 1103343; 1(10, 15)1; 0112522; 1(10, 15)1; 0122542; 1(14, 19)0; 1131241; 2(7, 12)1; 1141241; 2(8, 13)0; 11525322; 1;3(17, 22)0; 1;0161241; 2(13, 18)0; 1171241; 2(17, 22)1; 0182522; 1(25, 30)1; 11925322; 1;3(33, 38)1; 1;1203343; 1(14, 19)0; 12133243; 1;2(17, 22)1; 1;0221321; 3(15, 20)1; 0233321; 3(20, 25)1; 02433243; 1;2(21, 26)0; 1;0253323; 1(24, 29)1; 1263343; 1(30, 35)0; 0273321; 3(24, 29)0; 02833243; 1;2(35, 40)1; 1;1293321; 3(28, 33)1; 1302522; 1(30, 35)0; 0311241; 2(20, 25)1; 03225322; 1;3(37, 42)1; 1;1331241; 2(24, 29)0; 0343321; 3(32, 37)0; 0353343; 1(37, 42)1; 13633243; 1;2(40, 45)0; 1;0371241; 2(39, 44)1; 1381241; 2(43, 48)1; 0393321; 3(44, 49)1; 1403343; 1(44, 49)0; 14133243; 1;2(47, 52)1; 1;04225322; 1;3(44, 49)0; 1;1433321; 3(50, 55)1; 0441241; 2(47, 52)1; 0


### 5.1.1. Performance Comparison with an Increase in the Number of Trains

In this subsection, we report the CPU running time of our model by CPLEX with an increase in the number of trains. The length of the start time window for each train maintains a value of 5. The maximum dwell time for each train at each station is 4 min more than the minimum dwell time. We consider 9 scenarios with the number of trains increasing from 5 to 44, as shown in Table5. Under each scenario, 10 instances were tested and the CPU running time is given as the mean value of all instances in one scenario.Table 5
Performance comparison with an increase in the number of trains.
ScenarioNumber of trainsObjectiveCPU time (s)1-1595.90.11-210205.91.31-315306.161-420417.16.31-525553.2123.01-630667.0116.41-735782.8163.21-840888.2366.11-944997.9429.8As can be seen from the table, the amount of CPU time required to obtain a result by the CPLEX solver generally increases when the number of trains increases from 5 to 44, except in scenarios 1-6. However, all results can be obtained within a reasonable time.We also illustrate the optimal timetable and platform plan in scenarios 1-9 for Line 1 and Line 2 in Figures7 and 8, respectively. In total, two trains (Trains 3 and 6) are not scheduled into this railway network. All scheduled trains satisfy the safety requirements, which verifies the validity of our proposed model.Figure 7
Train timetabling and platforming result for Line 1.Figure 8
Train timetabling and platforming result for Line 2.


### 5.1.2. Performance Comparison with an Increase in the Number of Train Paths

In this subsection, we report the difference in solving performance when the number of train paths increases and the number of trains is fixed to be 30. For each train, the number of paths depends on the lengths of the start time and dwelling time windows in each station. We consider two environments. In the first environment, the length of the start time window is variable, and the length of the station dwell time window is fixed, and in the second environment, the contrary is true. We constructed 6 and 5 scenarios for each environment, as shown in Table6.Table 6
Performance comparison with an increase in the number of train paths.
ScenarioLength of start time window (min)Length of station dwell time window (min)ObjectiveCPU time (s)2-124902.845.32-25760.3116.42-310692.2177.72-415691.3379.72-520691.1820.62-625691.11041.62-742902.617.42-85775.3285.42-910708.6231.62-1015703.5402.12-1120703.51566As listed in Table6, in scenarios 2-1 to 2-6, the start time window varies from 2 min to 25 min, while the station dwell time window is fixed at 4 min. Further, in scenarios 2-7 to 2-11, the station dwell time window varies from 2 min to 20 min, while the start time window is fixed at 4 min. Additionally, the CPU running time increases rapidly when the start time window or the station dwell time window widens. This indicates that an increase in the number of train paths leads to model complexity and longer solving times. Meanwhile, extending the length of the start time window leads to an improvement in the quality of the result and a reduction in the CPU running time, as compared with the case when the length of the station dwell time window is increased.


### 5.1.3. Benefit of Mesoscopic Network Compared with Microscopic Network

In the TPST network, we do not divide the track resources of a track segment into block sections, which is the modeling unit from the microscopic perspective. Instead, we split the platform track and consider the track resources in a station bottleneck area in terms of station route, which allows us to assign station resources, as opposed to the case in the macroscopic solving framework. Therefore, the TPST network can be seen as a modeling method from the mesoscopic perspective. We assume that there are 10 extra block sections of a track segment at each direction between two stations, and every place that will be used for trains to change the route in the throat area is marked as a node from the microscopic perspective.Table7 provides a comparison of network scale from the microscopic and mesoscopic perspectives. As can be seen, the number of nodes can be reduced by at least 70% from 132 in the microscopic framework to 37 in our proposed framework, and the number of physical links can be reduced by almost 80% from 320 to 66. When we extend the physical network along the time dimension, the differences between the numbers of vertices and arcs from the two perspectives will be even larger. Therefore, the number of decision variables in our proposed model is also decreased sharply compared to the microscopic model.Table 7
Network size comparison from the microscopic and mesoscopic perspectives.
PerspectiveNode numberPhysical link numberMicroscopic132>320Mesoscopic3766


### 5.1.4. Benefit of Mesoscopic Network Compared with Macroscopic Network

As described in Cacchiani et al. [31], in the macroscopic method, only the arrival and departure time constraints enforce train headway within a station. Further, as explained in Zhang et al. [2], the maximum number of trains within a station at a time should not exceed the station capacity. The station track capacity generally refers to the total number of station platform tracks. As we mentioned earlier, in the mesoscopic railway network, the detailed station layout can be considered, which reduces the difficulty of separating trains according to the train direction in a complex hub station. The constraints within a station are enforced by not only the arrival (departure) headway but also the platform usage and bottleneck resources.Figure9 represents the results within Station 1 between 48 min and 65 min in Figure 7. The solid line denotes the train paths solved by our proposed model from the mesoscopic perspective. Train 32 cannot arrive at the arrival boundary of Station 1 earlier than 48 min because of other train path constraints (such as minimum dwell time, start time at the origin node, and running time). According to the station layout, if train 32 arrives at the station through node 15 and departs from node 16, only platforms 8 and 9 can be used.Figure 9
Comparison of the results from the mesoscopic and macroscopic perspectives.(1) If the Station Capacity Is Set as the Total Number of Platforms for Station 1. Train 32 will arrive at Station 1 at 51 min constrained by the arrival headway from the macroscopic perspective, and, no platform is available for this train at 53 min.(2) If the Station Capacity Is Set as 2 (Platforms 8, 9) for Station 1. Train 32 will arrive at Station 1 at 53 min constrained by the arrival headway from the macroscopic perspective. Path 1 and Path 2 can be chosen as the local route for this train. However, the receiving route of both paths will conflict with the departure route of Train 28.Consequently, the mesoscopic modeling framework, which considers the station resource, can generate a train timetable as well as a feasible train platform plan.


## 5.1.1. Performance Comparison with an Increase in the Number of Trains

In this subsection, we report the CPU running time of our model by CPLEX with an increase in the number of trains. The length of the start time window for each train maintains a value of 5. The maximum dwell time for each train at each station is 4 min more than the minimum dwell time. We consider 9 scenarios with the number of trains increasing from 5 to 44, as shown in Table5. Under each scenario, 10 instances were tested and the CPU running time is given as the mean value of all instances in one scenario.Table 5
Performance comparison with an increase in the number of trains.
ScenarioNumber of trainsObjectiveCPU time (s)1-1595.90.11-210205.91.31-315306.161-420417.16.31-525553.2123.01-630667.0116.41-735782.8163.21-840888.2366.11-944997.9429.8As can be seen from the table, the amount of CPU time required to obtain a result by the CPLEX solver generally increases when the number of trains increases from 5 to 44, except in scenarios 1-6. However, all results can be obtained within a reasonable time.We also illustrate the optimal timetable and platform plan in scenarios 1-9 for Line 1 and Line 2 in Figures7 and 8, respectively. In total, two trains (Trains 3 and 6) are not scheduled into this railway network. All scheduled trains satisfy the safety requirements, which verifies the validity of our proposed model.Figure 7
Train timetabling and platforming result for Line 1.Figure 8
Train timetabling and platforming result for Line 2.


## 5.1.2. Performance Comparison with an Increase in the Number of Train Paths

In this subsection, we report the difference in solving performance when the number of train paths increases and the number of trains is fixed to be 30. For each train, the number of paths depends on the lengths of the start time and dwelling time windows in each station. We consider two environments. In the first environment, the length of the start time window is variable, and the length of the station dwell time window is fixed, and in the second environment, the contrary is true. We constructed 6 and 5 scenarios for each environment, as shown in Table6.Table 6
Performance comparison with an increase in the number of train paths.
ScenarioLength of start time window (min)Length of station dwell time window (min)ObjectiveCPU time (s)2-124902.845.32-25760.3116.42-310692.2177.72-415691.3379.72-520691.1820.62-625691.11041.62-742902.617.42-85775.3285.42-910708.6231.62-1015703.5402.12-1120703.51566As listed in Table6, in scenarios 2-1 to 2-6, the start time window varies from 2 min to 25 min, while the station dwell time window is fixed at 4 min. Further, in scenarios 2-7 to 2-11, the station dwell time window varies from 2 min to 20 min, while the start time window is fixed at 4 min. Additionally, the CPU running time increases rapidly when the start time window or the station dwell time window widens. This indicates that an increase in the number of train paths leads to model complexity and longer solving times. Meanwhile, extending the length of the start time window leads to an improvement in the quality of the result and a reduction in the CPU running time, as compared with the case when the length of the station dwell time window is increased.


## 5.1.3. Benefit of Mesoscopic Network Compared with Microscopic Network

In the TPST network, we do not divide the track resources of a track segment into block sections, which is the modeling unit from the microscopic perspective. Instead, we split the platform track and consider the track resources in a station bottleneck area in terms of station route, which allows us to assign station resources, as opposed to the case in the macroscopic solving framework. Therefore, the TPST network can be seen as a modeling method from the mesoscopic perspective. We assume that there are 10 extra block sections of a track segment at each direction between two stations, and every place that will be used for trains to change the route in the throat area is marked as a node from the microscopic perspective.Table7 provides a comparison of network scale from the microscopic and mesoscopic perspectives. As can be seen, the number of nodes can be reduced by at least 70% from 132 in the microscopic framework to 37 in our proposed framework, and the number of physical links can be reduced by almost 80% from 320 to 66. When we extend the physical network along the time dimension, the differences between the numbers of vertices and arcs from the two perspectives will be even larger. Therefore, the number of decision variables in our proposed model is also decreased sharply compared to the microscopic model.Table 7
Network size comparison from the microscopic and mesoscopic perspectives.
PerspectiveNode numberPhysical link numberMicroscopic132>320Mesoscopic3766


## 5.1.4. Benefit of Mesoscopic Network Compared with Macroscopic Network

As described in Cacchiani et al. [31], in the macroscopic method, only the arrival and departure time constraints enforce train headway within a station. Further, as explained in Zhang et al. [2], the maximum number of trains within a station at a time should not exceed the station capacity. The station track capacity generally refers to the total number of station platform tracks. As we mentioned earlier, in the mesoscopic railway network, the detailed station layout can be considered, which reduces the difficulty of separating trains according to the train direction in a complex hub station. The constraints within a station are enforced by not only the arrival (departure) headway but also the platform usage and bottleneck resources.Figure9 represents the results within Station 1 between 48 min and 65 min in Figure 7. The solid line denotes the train paths solved by our proposed model from the mesoscopic perspective. Train 32 cannot arrive at the arrival boundary of Station 1 earlier than 48 min because of other train path constraints (such as minimum dwell time, start time at the origin node, and running time). According to the station layout, if train 32 arrives at the station through node 15 and departs from node 16, only platforms 8 and 9 can be used.Figure 9
Comparison of the results from the mesoscopic and macroscopic perspectives.(1) If the Station Capacity Is Set as the Total Number of Platforms for Station 1. Train 32 will arrive at Station 1 at 51 min constrained by the arrival headway from the macroscopic perspective, and, no platform is available for this train at 53 min.(2) If the Station Capacity Is Set as 2 (Platforms 8, 9) for Station 1. Train 32 will arrive at Station 1 at 53 min constrained by the arrival headway from the macroscopic perspective. Path 1 and Path 2 can be chosen as the local route for this train. However, the receiving route of both paths will conflict with the departure route of Train 28.Consequently, the mesoscopic modeling framework, which considers the station resource, can generate a train timetable as well as a feasible train platform plan.


## 5.2. Medium-Sized Rail Network and Performance Analysis

To further verify the validity of our model, we modify our small-sized rail network to a medium-sized one comprising nine stations on two railway lines with 97 nodes and 188 physical links, as shown in Figure10. The running time of each track segment on each railway line is either 3 or 4 min. The running time of a single-station route is 2 min at Stations 1, 4, 5, 8, 9, and 1 min at the remaining stations. The other parameters can be set as those in the cases of a small-sized railway network.Figure 10
Medium-sized rail network.The train data are listed in Table8. In total, 48 trains having conflicting routes are planned to be scheduled. The maximum dwell time for every train at each station is 5 min more than its minimum dwell time.Table 8
Train data for medium-sized railway network.
Train IDFrom nodeTo nodeStationStart time windowMin dwell186468; 6;1; 2;4(1, 6)1; 0;1; 0;0247874; 2;1; 6;8(2, 7)1; 0;0; 1;1396569; 7;1; 3;5(2, 7)1; 0;0; 0;0457465; 3;1; 2;4(3, 8)1; 0;1; 1;1586568; 6;1; 3;5(4, 9)1; 1;1; 0;1647564; 2;1; 3;5(5, 10)1; 1;1; 1;1796469; 7;1; 2;4(5, 10)0; 0;1; 0;1857875; 3;1; 6;8(6, 11)1; 1;1; 0;1986468; 6;1; 2;4(7, 12)0; 0;0; 1;11047874; 2;1; 6;8(8, 13)0; 1;1; 0;11196879; 7;6; 8(8, 13)1; 1;0; 01257975; 3;1; 7;9(9, 14)1; 1;1; 1;11386468; 6;1; 2;4(10, 15)1; 1;0; 1;01496569; 7;1; 3;5(11, 16)1; 1;1; 1;01547974; 2;1; 7;9(11, 16)0; 1;1; 1;11657975; 3;1; 7;9(12, 17)1; 1;1; 1;11786468; 6;1; 2;4(13, 18)1; 1;1; 0;11847564; 2;1; 3;5(14, 19)1; 1;1; 1;11996569; 7;1; 3;5(14, 19)0; 1;1; 1;02057465; 3;1; 2;4(15, 20)1; 1;1; 0;12186978; 6;7; 9(16, 21)1; 1;1; 12247874; 2;1; 6;8(17, 22)0; 0;0; 0;02396569; 7;1; 3;5(17, 22)0; 1;1; 0;12457465; 3;1; 2;4(18, 23)0; 0;1; 1;12586468; 6;1; 2;4(19, 24)1; 1;1; 1;12647564; 2;1; 3;5(20, 25)1; 1;1; 1;12796569; 7;1; 3;5(20, 25)0; 0;1; 1;12857875; 3;1; 6;8(21, 26)1; 0;1; 0;12986568; 6;1; 3;5(22, 27)0; 1;1; 1;13047874; 2;1; 6;8(23, 28)1; 0;1; 1;03196569; 7;1; 3;5(23, 28)1; 1;1; 1;13257975; 3;1; 7;9(24, 29)1; 0;1; 1;03386468; 6;1; 2;4(25, 30)0; 0;1; 0;13447564; 2;1; 3;5(26, 31)1; 1;1; 0;13596569; 7;1; 3;5(26, 31)1; 1;1; 1;13657465; 3;1; 2;4(27, 32)1; 1;1; 0;13786468; 6;1; 2;4(28, 33)1; 0;1; 1;13847564; 2;1; 3;5(29, 34)0; 1;1; 1;13996569; 7;1; 3;5(29, 34)1; 1;1; 1;14057975; 3;1; 7;9(30, 35)0; 1;0; 1;04186468; 6;1; 2;4(31, 36)1; 1;1; 1;14296879; 7;6; 8(32, 37)1; 1;1; 14357465; 3;1; 2;4(33, 38)0; 1;1; 1;14486468; 6;1; 2;4(34, 39)1; 1;1; 1;04557975; 3;1; 7;9(36, 41)0; 1;1; 0;14686468; 6;1; 2;4(37, 42)1; 1;1; 0;14757465; 3;1; 2;4(39, 44)1; 1;1; 0;14886978; 6;7; 9(40, 45)0; 1;0; 1In this section, we also discuss the efficiency of problem solving when the number of trains is increased, as presented in Table9. The solving time for each case is limited to 1 hour. The upper and lower bounds are listed in the second and third columns. The GAP in the fourth column is the difference between the upper and lower bounds divided by the upper bound. In general, for a medium-sized rail network, the greater the number of trains, the bigger the gap. Moreover, the gap is still acceptable in the case with 48 trains. The final results for 48 trains are represented in Figures 11 and 12. A total of 11 trains cannot be scheduled into the timetable due to the conflicting routes, and the paths of all the scheduled trains satisfy all the constraints. Based on these results, it can be said that our proposed modeling method can successfully solve relatively large-scale cases.Table 9
Performance comparison with an increase in the number of trains for medium-sized cases.
Number of trainsUpper boundLower boundGAP (%)CPU time (s)1-15700691.11.2836001-20959.5951.70.8136001-2512071186.41.1736001-301598.71513.65.3236001-352040.41837.69.9436001-402424.82203.69.1236001-482983.62622.512.063600Figure 11
Train timetabling and platforming result for Line 1 for medium-sized rail network.Figure 12
Train timetabling and platforming result for Line 2 for medium-sized rail network.


## 6. Conclusion and Future Research

In this study, we developed a framework to simultaneously optimize the train timetabling and platforming problems. First, we proposed the TPST network from a mesoscopic perspective. Compared to the railway network modeled from the macroscopic perspective, our proposed framework considers station track resources, including not only the platform track resources but also the track resources in the station bottleneck area. Compared to the microscopic network, the TPST network reduces the network scale by 70% and therefore decreases the number of decision variables. We also highlighted the performance difference with increases in the numbers of trains and train paths. Meanwhile, extending the length of the start time window leads to an improvement in the quality of the result and a reduction in the CPU running time, as compared with the case when the length of the station dwell time window is increased. In future research, a new algorithm should be developed to obtain an optimal or near-optimal solution for a large-scale railway network.



---

*Source: 6679008-2021-03-17.xml*