# Investigation of Railway Network Capacity by Means of Dynamic Flows
## 2 Literature Review
Network flow problems in general are a well-known class of combinatorial optimization problems. Within such a problem, a so-called flow network is used to map the flow of objects such as vehicles or goods in a network consisting of vertices and directed arcs. There are numerous types and applications of network flow problems. In the most general maximum flow problem, the goal is to transport as many flow units as possible from one certain vertex to another while capacity restrictions on the arcs are respected and flow conservation in the network holds. Applications of maximum flow problems range from capacity assessments (e.g., of an oil pipeline network or an urban street network) to more abstract issues like scheduling or matching problems. There are excellent surveys in the literature of the various formulations and applications of network flows. Two examples are given by [14] and [15]. The first reference especially examines the vast area of static network flows, while the latter focuses on the topic of dynamic network flows. To calculate the network capacity using network flows in the railway context, the underlying flow network is defined in such a way that vertices correspond to the stations or junctions, and arcs represent the line sections in between. An important and practice-oriented part of the flow network in the railway context is the existence of travel times assigned to the arcs. Since the travel time of an arc depends on which train is running on it, another important aspect of the study is the distinction between different trains. To map these properties, for the application in the railway context, the standard maximum flow problem is extended to a dynamic multicommodity maximum flow problem. Among the previous applications of dynamic multicommodity flow problems or of optimization methods in general, there are examples where capacity studies in railway networks have been conducted. The most relevant approaches for this study are described in more detail below. In [16], a study on the topological features of transportation networks is conducted. Since insights into network structure provide clear indications of flow properties, this approach establishes a solid graph theoretical foundation for flow analysis. A direct application of flow analysis to a railway network is presented in [17]. It estimates the network capacity by finding the maximum flow through the network applying the Ford-Fulkerson [18] and Gomory-Hu methods. However, a notable limitation is the lack of accounting for time dependency such as travel times on the edges. In [19], a model is developed in the form of an integer linear program whose binary decision variables are defined based on the arcs of a time-expanded network. If the value of a variable for a specific line at a specific time or for a certain station at a certain time equals one, then a train is running on this line or stopping at this station at that time. Maximizing the sum over these variables calculates the maximum number of trains that can run on a sequence of line sections with stations in between. In this way, the capacity of an entire railway line is examined. Various limiting aspects are considered by the restrictions defined in the linear program. These include, for example, that a certain train mix must be maintained on the line, and that the number of station tracks that can be used in parallel by stopping trains is never exceeded. The methodical approach of [20] is similar. Again, the capacity is calculated for a single railway line, which consists of a sequence of line sections with stations in between. However, compared to [19], further railway-specific restrictions are considered. Minimum headway times applicable to the line sections, and the minimum and maximum dwell times of the trains in the stations are modeled as additional influencing factors on the capacity. The level of the calculated capacity is also affected by the specification of temporary disruptions on individual line sections for specific time intervals.