# Time Coordination of Periodic Passenger Train Connections in Conditions of Single-Track Lines

Authors: Filip Lorenz; Vit Janos; Dusan Teichmann; Michal Dorda
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

The article addresses creation of a mathematical model for a real problem regarding time coordination of periodic train connections operated on single-track lines. The individual train connections are dispatched with a predefined tact, and their arrivals at and departures to predefined railway stations (transfer nodes) need to be coordinated one another. In addition, because the train connections are operated on single-track lines, trains that pass each other in a predefined railway stations must be also coordinated. To optimize the process, mathematical programming methods are used. The presented article includes a mathematical model of the given task, and the proposed model is tested with real data. The calculation experiments were implemented using optimization software Xpress-IVE.


---

## Body

## 1. Introduction: Motivation to Solve the Given Problem

The main objective of the transport processes in passenger transportation is to make them as short as possible. We need to start with an assumption than the moving time, for example, [1], is usually unproductive time. That is why we insist on making it as short as possible. This formulation is expressed by the following formula:(1)T=t1+tw+tt+ttr+t2,where T is the total transport time (min), t1 is the walking time from the moving source to the given train stop (min), tw is the waiting time for the train (min), tt is the time spent on the train (transport time) (min), ttr is the transfer time (including waiting time at the transfer nodes) (min), and t2 is the walking time from the train stop to the given moving destination (min).As it is clear from the above-stated formula, one of the possibilities of how to shorten the total transport time is to minimize the waiting time for connections at the transfer nodes.The motivation for solving the problem is to find an approach that would allow for a maximal transportation fluency by shortening the waiting times at the transfer nodes.Time coordination of the transport processes is then based on the principle of proposing such time positions of the given connections that will allow for minimizing time losses of the passengers from the moment they board the first train on their transport route until the moment they get off the last connection on their way.


## 2. Analysis of the Current State of the Art

A thorough summary of coordination optimization models is provided in [2]. This relatively extensive work deals with multimodal transport networks, individual connections (lines) of which meet in transfer terminals, which means that passengers transfer there from one line to another. The author claims that the main motivation for solving the issue is the necessity to make public transport more attractive for passengers by making the transfers among individual connections more efficient. The author approaches the topic in two ways:(i)
Connection coordination by timetable modifications (Schedule Coordination)(ii)
Connection coordination in real time (Connection Protection)The work includes an optimization model for generating timetables and minimizing transfer times among individual connections. The objective of the model is to find an optimal timetable by shifting existing connections to a new time position and/or by delaying a given connection, i.e., waiting for a subsequent connection, thus minimizing the overall delay of both connections. The model considers waiting time of the transferring passengers as well as delay times of the people who use one of the two connections, but who do not transfer. The model has been validated by case studies and the positive results are demonstrated by concrete time savings. Furthermore, the author concludes that even if a timetable is modified based on the corresponding mathematical model output, it is still necessary to pay attention to the stochastic character of the transport, i.e., occurrence of extraordinary situations and delays, which disrupt the transfer relations. That is why the work also included development of a CP model (Connection Protection). The objective function of the model considers probability of the implementation of the transfer relations and optimizes expenses. This model is evaluated and compared with previous models with the objective to demonstrate it as a tool for improving the efficiency of the transfer relations and for reducing waiting times of the passengers.Ciaffi et al. [3] focus on transfer relations between a secondary public transport network in the cities (primarily bus transport) and the main transport network (metro and railway). The objective is to develop a procedure that simultaneously generates routes and frequencies (time intervals) in the bus transport network, making sure it is applicable for solving problems of a size that corresponds to the extent of real cities.Sun et al. [4] address classification of bus routes and their relations to the main transit (railway) transport. The objective of the proposed solution is to maximize the use of the transit (railway) routes by passengers and to optimize the existing bus lines from the perspective of their contribution to the given transit (railway) route. The article also presents an algorithm that is used for defining the relation between bus lines and main transit routes.Authors of study [5] address coordination of the transfer relations among individual transit routes in real time. They realize the advantages of coordinated transfers, i.e., shortening of the passengers’ waiting time, while also considering the risks of delays of the passengers who are on the given line, passengers who intend to travel on that line, and accumulation of the transport means at the coordination nodes. In the first part of their study, the authors developed a dynamic management strategy, which is based on the given management theory and thanks to an optimal management strategy which was determined (delays of individual connections at the coordinated nodes). A maximal delay is thus determined by the estimates of arrivals of individual connections and passengers in real time and by uncertainty of these estimates.Gkiotsalitis et al. [6] explore a robust coordination of connection times, including public transport, for the purpose of the given network coordination. The authors focus on analyzing the robustness of the synchronization results in two limit situations. The first limit situation occurs under standard operation conditions and the second limit situation under extreme operation conditions (extreme operation conditions are represented by significant disruptions of the planned timetable). The optimization approach proposed in their article is based on evolution algorithms. The authors execute the corresponding calculation experiments using real data obtained from the bus transport system in the city of Hague, Netherlands.The objective of [7] was to identify individual bus connections and their mutual relations from the perspective of their competitiveness, complementarity, or independency. Next, the authors decided about time changes of individual bus connections, which were servicing a given unified area based on a calculation of the travel cost of the passengers, walking time, and waiting time related to each individual bus route. Furthermore, the authors explored passenger behavior when they choose suitable bus connections, and they incorporate the given survey results in their solution.Omar and Yasmin [8] focus on the creation of timetables of the bus lines operated by several private bus companies in the city of Monterrey, Mexico. The following are the objectives of the study:(1)
Preventing cumulation of bus connections of various bus lines in individual transfer nodes(2)
Increasing potential transfer linksBased on the above-stated objectives, the authors developed a suitable model, which is able to fulfil the defined objectives.The study carried out by Almasi et al. [9] looks into the timetable proposal of individual bus connections and their intensity, with the objective to conveniently interlink them with the railway transit system. The authors created an improved metaheuristic approach based on the Imperialist Competitive Algorithm and Water Cycle Algorithm. The optimization criterion here is the cost function, which includes expenses of the networks users, expenses related to the operation of technical equipment, and also social expenses, such as the cost of the network operation and cost related to the pollution caused by individual vehicles. The developed metaheuristic approach was tested on an actual network of the city of Petaling Jaya in Kuala Lumpur, Malaysia.Wong et al. [10] present a proposal of a coordination of public transport timetables, which allow for smooth transfers with minimal delays for all passengers based on mixed-integer programming. The approach focuses on nonperiodic timetables. The authors tested the proposed approach in the conditions of the city railway transport in Hong Kong on a network that consisted of six railway lines and a significant number of transfer stations. The authors also explore the options of searching for compromises between waiting times and the operation parameters of a given public transport system.Liu et al. [11] explore time coordination of metro train connections in southern China. The authors developed a heuristic approach based on the simulated annealing method. Only riding times among individual metro stops and the current timetable of the train connections were used for the needs of the developed heuristic approach. Using an experimental case, the authors found a solution with time savings for passengers and without an impact on the number of the operated trains and infrastructure changes.The study carried out by Xiaopeng and Huimin [12] looks into a proposal of a timetable of train connections at a single transfer node using nonlinear integer programming. The optimization criterion was an exponential utility function. The developed mathematical model was tested on real input data.Xueping et al. [13] explore the creation of transfer links between bus and train connections. In the first part of the research, the authors developed a mixed-integer nonlinear model, which ensures minimization of the number of unexecuted transfers between bus and train connections. In the second part of the research, the authors use integer linear programming for the creation of a timetable of bus connections.Authors of article [14] focus on minimizing time losses of the passengers, caused by timetable reserves. Moreover, they also emphasize behavior of the passengers. Based on the above, the authors developed an integer, bi-objective, and bi-level mathematical model, functionality and effectiveness of which were tested on a small model network.In [15], a mathematical programming method for the time coordination of public transport connections is used. The main contribution of the article is a proposal of optimization approaches that work with the dynamically changing demand for transfers. The authors of the article propose a nonlinear mixed-integer mathematical model amended by the heuristic method and a linear mixed-integer model for the coordination. The authors test both proposed approaches on a real metro line in Teheran, Iran.To coordinate the given timetables, the classic heuristic method is used in [16]. The authors of the study particularly focus on the coordination of public transport connections in the networks with lines operated in a parallel way, which join in certain transfer hubs. A characteristic feature of the lines serviced in a parallel way is the fact that the travel times between two identical transfer hubs are different. The proposed heuristic method is tested not only on model networks but also in the conditions of a real bus transport network, which consists of 7 bus lines and 3 transfer hubs.Authors of [17] explore maximization of the number of the current connection arrivals to a transfer hub, with the objective to minimize transfer waiting times and thus also the expenses related to the waiting of the transferring passengers. The intention is to propose the so-called robust timetables of individual connections, which allow for considering extraordinary situations along the given connection routes (traffic congestions, etc.). The instrument for increasing the robustness of the timetables is represented by the so-called slack times, which allow for incorporating sufficient times into the given transport times for eliminating the consequences of the corresponding extraordinary situations. The work includes a proposal of a stochastic optimization model. Its solution is implemented using the method of branches and limits and amended by a strategy that leads to an improved efficiency of the calculation procedure. The presented calculation experiments with the given proposed approach are implemented on model situations.Authors of [18] propose a nonlinear optimization model that shortens the transfer waiting times by the means of timetable modifications. The study also includes a proposal of a heuristic approach based on the Tabu Search method. The proposed approach was tested on real data in the conditions of the city of Copenhagen, Denmark.Authors of [19] explore the issue of synchronization of train day timetables, when significant changes in the demand of passengers occur. A nonlinear programming model is proposed for the optimization. The actual solution utilizes metaheuristics based on the particle swarm, combined with the simulated annealing method. The case study from the real world explores the situation in the conditions of the metro system in Beijing, China.Technical literature often uses optimization approaches based on genetic algorithms for time coordination of individual connections in transfer hubs.Jiaqing et al. [20] analyze coordination of the time schedule between fast transit bus connections (buses and frequency of stops of which is lower than of the city public transportation buses, which have a dedicated traffic lane available to them) and other related bus connections of the city public transportation in Beijing. The authors analyze coordination of these systems from the perspective of being increasingly used by passengers and their negative impacts on the integrated public transportation when the degree of coordination is low. The first part of the article focuses on the study of operation characteristics and determines an optimization criterion, which is represented by the total cost of the operation of the given systems. When doing so, the authors also consider the overall transportation time of the passengers.In the next part of the study, the authors create a coordinated operation model. The last part of the work is devoted to the creation of a genetic algorithm and its application on the analyzed coordinated operation, with the objective to optimize the values of the specified criteria.Two results were obtained by the application of the abovementioned algorithm:(1)
The total cost related to the operation of the coordinated systems was reduced based on the coordination of individual timetables(2)
The total waiting time of the passengers was reduced based on the coordination of fast transit buses and city public transportation busesDissertation [21] explores time coordination of bus connections using genetic algorithms in combination with the Monte Carlo method. The proposed genetic algorithm must be tested on real input data, thus demonstrating its functionality. A disadvantage of the genetic algorithm is a long calculation time for solving the task.Authors of [22] explore the creation of a train transportation timetable based on a genetic algorithm. While developing the given mathematical model, they also took into account the corresponding infrastructure elements and used railway cars. The final genetic algorithm was tested on model data. The achieved results seemed very satisfactory considering the problem complexity. Almost optimal results were achieved in a very short time.Authors of [23] combine genetic algorithms with another heuristic method. The authors focus on minimizing the waiting times in periodically serviced public transport networks. They use a two-stage approach for their solution. The optimization criterion is the waiting time. The first stage of the solution is based on the principles on a manual construction of timetables, using the greedy algorithm. The result of the first stage is an initial solution. As a part of the second stage, possibilities of its improvement are tested using genetic algorithms. The calculation experiments were applied to a real railway network of German railway lines serviced by long-distance and important regional trains.In [24], genetic algorithms for optimizing the transfer relations in metropolitan networks of individual lines are also used. As a part of the optimization approach, the authors of the article use the summation of the transfer waiting time for all pairs of lines and all stations as a criterion. The authors applied the proposed approach on a network of bus lines in the city of Mashhad, Iran. The network is serviced by 139 two-way bus lines and 278 one-way lines. The network incorporates 3,618 bus stops, 841 of which are transfer stops.Moreover, genetic algorithms in the conditions of public transport are also used by authors of [25], who explore solutions of the coordination problem of individual lines, for which irregular travel times among individual stops are expected. The objective is to minimize the total waiting time cost for three types of passengers (i.e., transferring passengers, boarding passengers, and through passengers). The authors publish a stochastic integer linear model, amended by an approach based on genetic algorithms, utilizing classic operators and the local search strategy. The authors implement the calculation experiments for verifying the effectivity of the proposed optimization model on ten types of randomly selected, generated instances of practical environments.The topic of the abovementioned study is further explored in [26]. The authors present a two-criterial mathematical model that can be used for modifying timetables, implemented with the objective to improve transfer fluency. As a part of the first criterion, the number of passengers who experience fluent transfers is maximized. As a part of the second criterion, the maximal deviations of the new connection times from the existing connection times are minimized. Genetic algorithms are used again for the actual practical solutions. Functionality and effectiveness of the approach are validated on a real network serviced by seven lines, which included three transfer hubs.The potential of genetic algorithms is also utilized in publication [27]. The article explores a proposal of an optimization approach for the public transport system with variable demand during the planned period. The optimization approach allows for considering symmetric timetables. The optimization criterion is the total waiting time of the passengers, transferring in all directions. The optimization approach is verified in the conditions of a transfer hub in the city of Beijing, China.Yin et al. [28] explore the issue of a synchronization of timetables in the conditions of the metro transport system in Beijing, utilizing genetic algorithms. The optimization process focuses on the synchronization of the time positions of the last night train connections. Corresponding weights are assigned to individual connections. The connections running from the city center are assigned higher weights than the connections running to the city center. The presented solution also takes into account the amount of the operation expenses related to the last night trains and the subsidies provided to the metro operator. The actual synchronization of the timetables is implemented simultaneously in 17 transfer hubs.The available analyzed results obviously address the topic from various points of view and from the perspective of individual transport types (passenger transport and cargo transport), as well as the interaction between individual transport modes (railway transport-road transport, bus transport-tram transport, bus transport-bus transport, city bus transport-long-distance bus transport, etc.). Time coordination is conducted in a sectional, point, or multipoint manner at the network locations.From the perspective of individual approaches, the authors use exact as well as heuristic (and especially metaheuristic) methods.The below proposed procedure will thus be particularly linked to works [2, 8, 12]. It will develop the issue of a network coordination (i.e., time coordination at multiple locations simultaneously) based on exact tools among the connections of several transportation companies. Furthermore, the specifics of a single-track operation, which is particularly common for regional networks around the entire world, will be also taken into account.


## 3. Mathematical Model Proposal

In this section, we will propose a linear mathematical model for optimizing the timetable implemented for the single-track railway route in question. It will represent a coordination task with a compact part of a railway network, in which time changes of the trains that service the network will be possible to make (hereinafter referred to as the “network in question”). The network in question will be connected to other parts of the railway network via a defined set of nodes. At the connection locations (nodes), passengers will transfer between the train connections that service the network in question and other train connections, which will be marked by the names of the train connections of the given external transportation providers. Apart from that, there will also be transfer nodes inside of the network in question. The objective will be to propose such time positions of individual train connections that service the network in question, which will ensure that the overall time losses of the transfer passengers are minimal.


### 3.1. Problem Formulation

TheK set of nodes is defined in the transport network in question. Passenger transfers are planned at these nodes. Moreover, the D set of nodes, at which passing of trains can occur, is also defined. The K node set consists of two subsets marked as KG and KC, for which it holds that K=KG∪KC and, at the same time, KG∩KC=∅. Subset KC is a subset of transfer nodes, in which passengers transfer between train connections of the transportation provider that services the railway network in question and train connections of other railway transportation providers (transfer nodes, by the means of which the network in question is connected to other railway networks of the given country). Subset KG is a subset of transfer nodes inside of the network in question, in which passengers transfer between train connections of the railway transportation provider that services the network in question.Apart from that, theKVset of initial nodes of train connections, which are operated by the railway carrier on the railway network, is defined. It applies that an initial node can belong to set KG or KC, or it does not have to belong to any of these sets.The minimal necessary transfer timetktrthat includes exit of the passenger from the given train, his/her transfer to the platform of the connecting train, and his/her boarding of this connecting train is defined for each transfer node k∈K. For each transfer node k∈K, the Sk set of train directions passengers transfer to is given. The Jsk set of departing connections is defined for each direction s∈Sk.For each nodek∈KC, the IkCA set of train connections of external transport providers is defined. In addition, for each node k∈KC, the set IkP of train connections entering the node from the network being optimized is given. It holds for the set of transfer nodes k∈KC that if i∈IkCA and j∈Jsk, where s∈Sk, then Sk=1. If it holds that i∈IkP and j∈Jsk, then Sk≥1.For each nodek∈KG, set of train connections IkP, which arrive to this node, is defined. There is a set of train connections IGWoperated, within the given network, and a set of connections, with which these connections, are coordinated at the outer nodes of the railway network in question ICA.For each train connectioni∈IGW, the Ki set of nodes is defined. These nodes will be used by passengers for transfer from the given train connection. Moreover, another set of nodes Di is also defined. In these nodes, the given train connection can pass a train connection from the opposite direction. The earliest possible departure time of a train connection from initial node Tidep, trip time from the initial node to transfer node k∈Ki marked as tik, and trip time from the initial node to node d∈Di (∪i∈IGWDi=D) with possible passing, marked as τid, are also defined.For each train connectioni∈IGW, maximal permitted change N is defined in relation to the earliest possible time position of the given train connection (it is constant for all train connections). Train connections within set IGW in individual directions run in regular intervals, which we mark by the symbol INT.For each train connection of an external transportation provideri∈IkCA, we know the time of its arrival to node k∈KC and the time of its departure from node k∈KC (for simplification purposes, we consider the arrival time to node k∈KC and the departure time from node k∈KC to be identical). The values of the maximal permitted time changes for all connections from set ICA are equal to zero.The objective is to determine departure and arrival time changes at the coordination nodes, making sure the time loss of the transferring passengers is as minimal as possible.


### 3.2. Mathematical Model Proposal

First, we specify the earliest possible departure times of the train connections from the initial nodes. It is required that train connectionsIGW run in a predefined cycle. In order to make the modelling easier, connections departing in the same directions from individual initial nodes will be grouped together.If we mark the number of connections leaving from initial nodek∈KV as nk, then the earliest possible departure times of connections j=1,2,…,nk from the initial node (marked with index 1) can be calculated pursuant to the following formula:(2)Tjdep=T1dep+j−1⋅INT,and the earliest possible departure times of connections j=1,2,…,nk from node k∈KV\1 will be calculated pursuant to the following formula:(3)Tn0+…+nk−1+jdep=Tn0+…+nk−1+1dep+j−1⋅INT,where Tn0+⋯+nk−1+jdep is the earliest possible departure time of train connection j=1,2,…,nk from initial node k∈KV, Tn0+…+nk−1+1dep is the earliest possible departure time of the 1st train connection from initial node k∈KV, and INT is the defined value of the interval between departing train connections.For initial nodes of train connections heading in multiple directions, individual train connections can be grouped pursuant to individual directions.In order to define the set of train connections that can pass one another in the opposite directions, incidence matrixA was established. When passing of trains i∈IGW and j∈IGW is possible, then aij=1, if not, then aij=0.Table1 presents a summary of notation used in the mathematical model.Table 1
Summary of mathematical model notation.
SymbolMeaningUnitAThe incidence matrix representing whether train connections from the setIGW can pass one another in the opposite directions or notaijThe element of the incidence matrixA; when passing of trains i∈IGW and j∈IGW is possible, then aij=1, if not, then aij=0DThe set of nodes where passing train connections from the setIGW one another is possibleDiThe set of nodes where passing the train connectioni∈IGW with the train connection in the opposite direction is possiblefijskVolume of the transfer passengers who arrived to coordination nodek∈K by train connection i∈IkP∪IkCA and who are transferring to train connection j∈Jsk that is departing in direction s∈SkhijskNonnegative variable that models the time loss of passengers who are transferring in transfer nodek∈KG from train connection i∈IkP∪IkCA to train connection j∈Jsk that is departing in direction s∈Sk(min)IkPSet of train connections arriving to nodek∈KIGWSet of train connections operated within the network in questionICASet of train connections, with which connection included inIGW are coordinated in the set of nodes KCIkCASet of train connections of external transportation providers that service nodek∈KJskSet of train connections departing from nodek∈K in direction s∈SkKSet of nodes, in which transfer of passengers among train connections are plannedKCSubset of transfer nodes of setK, in which transfers of passengers between train connections of the transportation provider in question and train connections of external transportation providers are plannedKGSubset of transfer nodes of setK, in which transfers of passengers among train connections of the transportation provider in question are plannedKVSet of the initial nodes of individual train connectionsKiSet of nodes, in which passengers will transfer from train connectioni∈IGWmijdBinary variable that models the passing plan of the train connections coming from opposite directionsi∈IGW and j∈IGW; aij=1 in node d∈DNMaximal permitted change of individual train connections(min)nkNumber of train connections leaving from initial nodek∈IGWqijdNonnegative variable that models the time loss incurred due to two train connections passing each other in the opposite directioni∈IGW and j∈IGW; aij=1 in node d∈DR0+Set of nonnegative numbersSkSet of the directions, in which individual train connections leave from transfer nodek∈KINTRegular time interval among connections that service the routes within the network in question(min)TidepEarliest possible departure time of train connectioni∈IGW from its initial node(min)tktrTransfer time for nodek∈K(min)tikTrip time of train connectioni∈IGW from its initial node to transfer node k∈Ki(min)xiNonnegative variable that models the time change of the departure of train connectioni∈I from the initial node(min)zijskBinary variable that models the origin of a transfer relation between train connectioni∈IkP∪IkCA and train connection j∈Jsk that departs in direction s∈Sk in node k∈KτidTrip time of train connectioni∈IGW from the initial node to node d∈Di(min)The mathematical model will then have the following :(4)minfx,z,h,m,q=∑i∈IkP∑j∈Jsk∑s∈Sk∑k∈KChijskfijsk+∑i∈IkCA∑j∈Jsk∑s∈Sk∑k∈KChijskfijsk++∑i∈IkP∑j∈Jsk∑s∈Sk∑k∈KGhijskfijsk+∑i∈IGW∑j∈Jsk∑d∈Daijqijdsubject to(5)Tjdep+xj−Tidep+tktr≥Mzijsk−1,fori∈IkCA,j∈Jsk,k∈KC,s∈Sk,(6)Tjdep+xj−Tidep+tktr≤hijsk+M1−zijsk,fori∈IkCA,j∈Jsk,k∈KC,s∈Sk,(7)∑j∈Jskzijsk=1,fori∈IkCA,k∈KC,s∈SkG,(8)Tjdep−Tidep+tik+xi+tktr≥Mzijsk−1,fori∈IkP,j∈Jsk,k∈KC,s∈Sk,(9)Tjdep−Tidep+tik+xi+tktr≤hijsk+M1−zijsk,fori∈IkP,j∈Jsk,k∈KC,s∈Sk,(10)∑j∈Jskzijsk=1,fori∈IkP,k∈KC,s∈SkCA,(11)Tjdep+tjk+xj−Tidep+tik+xi+tktr≥Mzijsk−1,fori∈IkP,j∈Jsk,k∈KG,s∈Sk,(12)Tjdep+tjk+xj−Tidep+tik+xi+tktr≤hijsk+M1−zijsk,fori∈IkP,j∈Jsk,k∈KG,s∈Sk,(13)∑j∈Jskzijsk=1,fori∈IkP,k∈KG,s∈Sk,(14)Tjdep+τjd+xj−Tidep+τid+xi≥Mmijd−1,fori∈IGW,j∈IGW,aij=1,d∈D,(15)Tjdep+τjd+xj−Tidep+τid+xi≤qijd+M1−mijd,fori∈IGW,j∈IGW,aij=1,d∈D,(16)∑d∈Dmijd=1,fori∈IGW,j∈IGW,aij=1,(17)xi≤N,fori∈IGW,(18)xi∈R0+,fori∈IGW,(19)hijsk∈R0+,fori∈IkCA,j∈Jsk,k∈KC,s∈Skand,i∈IkP,j∈Jsk,k∈KC,s∈Skand,i∈IkP,j∈Jsk,k∈KG,s∈Sk,(20)qijd∈R0+,fori∈IGW,j∈IGW,aij=1,d∈D,(21)zijsk∈0,1,fori∈IkCA,j∈Jsk,k∈KC,s∈Skand,i∈Ikp,j∈Jsk,k∈KC,s∈Skand,i∈IkP,j∈Jsk,k∈KG,s∈Sk,(22)mijd∈0,1,fori∈IGW,j∈IGW,aij=1,d∈D.Function (4) represents an optimization criterion of the overall time loss arising from the creation of the transfer relations between individual train connections and the overall time loss arising from passing of train connections running in the opposite directions. Constraints (5), (8), and (11) ensure that if it is not possible to link an arriving train connection to a departing train connection at the given node, no transfer relation is formed between these train connections. Constraints (6), (9), and (12) ensure that when a transfer relation between two train connections is formed, the corresponding time loss is incorporated in the given function. Constraints in pairs (5) and (6), (8) and (9), and (11) and (12) represent the so-called constraints of the “either-or” type, which means that only one of the stated constraints is always active. Constraints (7), (10), and (13) ensure that each arriving train connection is assigned precisely to one connecting connection for each direction of transfer. Constraints (14) and (16) ensure that if passing can be implemented at a suitable node for the given train connections running in opposite directions, this passing is implemented and the time loss arising from waiting for the train connection running in the opposite direction will be included into the value of the optimization criterion. Constraint (16) ensures that one node suitable for passing will be determined for each pair of the train connections running in opposite directions, provided passing is required for this pair of the train connections (this fact is given by the incidence matrix). Constraint (17) defines the maximal possible time change of the corresponding train connections. Constraints (18)–(22) specify domains of definition of the variables used in the model.


## 3.1. Problem Formulation

TheK set of nodes is defined in the transport network in question. Passenger transfers are planned at these nodes. Moreover, the D set of nodes, at which passing of trains can occur, is also defined. The K node set consists of two subsets marked as KG and KC, for which it holds that K=KG∪KC and, at the same time, KG∩KC=∅. Subset KC is a subset of transfer nodes, in which passengers transfer between train connections of the transportation provider that services the railway network in question and train connections of other railway transportation providers (transfer nodes, by the means of which the network in question is connected to other railway networks of the given country). Subset KG is a subset of transfer nodes inside of the network in question, in which passengers transfer between train connections of the railway transportation provider that services the network in question.Apart from that, theKVset of initial nodes of train connections, which are operated by the railway carrier on the railway network, is defined. It applies that an initial node can belong to set KG or KC, or it does not have to belong to any of these sets.The minimal necessary transfer timetktrthat includes exit of the passenger from the given train, his/her transfer to the platform of the connecting train, and his/her boarding of this connecting train is defined for each transfer node k∈K. For each transfer node k∈K, the Sk set of train directions passengers transfer to is given. The Jsk set of departing connections is defined for each direction s∈Sk.For each nodek∈KC, the IkCA set of train connections of external transport providers is defined. In addition, for each node k∈KC, the set IkP of train connections entering the node from the network being optimized is given. It holds for the set of transfer nodes k∈KC that if i∈IkCA and j∈Jsk, where s∈Sk, then Sk=1. If it holds that i∈IkP and j∈Jsk, then Sk≥1.For each nodek∈KG, set of train connections IkP, which arrive to this node, is defined. There is a set of train connections IGWoperated, within the given network, and a set of connections, with which these connections, are coordinated at the outer nodes of the railway network in question ICA.For each train connectioni∈IGW, the Ki set of nodes is defined. These nodes will be used by passengers for transfer from the given train connection. Moreover, another set of nodes Di is also defined. In these nodes, the given train connection can pass a train connection from the opposite direction. The earliest possible departure time of a train connection from initial node Tidep, trip time from the initial node to transfer node k∈Ki marked as tik, and trip time from the initial node to node d∈Di (∪i∈IGWDi=D) with possible passing, marked as τid, are also defined.For each train connectioni∈IGW, maximal permitted change N is defined in relation to the earliest possible time position of the given train connection (it is constant for all train connections). Train connections within set IGW in individual directions run in regular intervals, which we mark by the symbol INT.For each train connection of an external transportation provideri∈IkCA, we know the time of its arrival to node k∈KC and the time of its departure from node k∈KC (for simplification purposes, we consider the arrival time to node k∈KC and the departure time from node k∈KC to be identical). The values of the maximal permitted time changes for all connections from set ICA are equal to zero.The objective is to determine departure and arrival time changes at the coordination nodes, making sure the time loss of the transferring passengers is as minimal as possible.


## 3.2. Mathematical Model Proposal

First, we specify the earliest possible departure times of the train connections from the initial nodes. It is required that train connectionsIGW run in a predefined cycle. In order to make the modelling easier, connections departing in the same directions from individual initial nodes will be grouped together.If we mark the number of connections leaving from initial nodek∈KV as nk, then the earliest possible departure times of connections j=1,2,…,nk from the initial node (marked with index 1) can be calculated pursuant to the following formula:(2)Tjdep=T1dep+j−1⋅INT,and the earliest possible departure times of connections j=1,2,…,nk from node k∈KV\1 will be calculated pursuant to the following formula:(3)Tn0+…+nk−1+jdep=Tn0+…+nk−1+1dep+j−1⋅INT,where Tn0+⋯+nk−1+jdep is the earliest possible departure time of train connection j=1,2,…,nk from initial node k∈KV, Tn0+…+nk−1+1dep is the earliest possible departure time of the 1st train connection from initial node k∈KV, and INT is the defined value of the interval between departing train connections.For initial nodes of train connections heading in multiple directions, individual train connections can be grouped pursuant to individual directions.In order to define the set of train connections that can pass one another in the opposite directions, incidence matrixA was established. When passing of trains i∈IGW and j∈IGW is possible, then aij=1, if not, then aij=0.Table1 presents a summary of notation used in the mathematical model.Table 1
Summary of mathematical model notation.
SymbolMeaningUnitAThe incidence matrix representing whether train connections from the setIGW can pass one another in the opposite directions or notaijThe element of the incidence matrixA; when passing of trains i∈IGW and j∈IGW is possible, then aij=1, if not, then aij=0DThe set of nodes where passing train connections from the setIGW one another is possibleDiThe set of nodes where passing the train connectioni∈IGW with the train connection in the opposite direction is possiblefijskVolume of the transfer passengers who arrived to coordination nodek∈K by train connection i∈IkP∪IkCA and who are transferring to train connection j∈Jsk that is departing in direction s∈SkhijskNonnegative variable that models the time loss of passengers who are transferring in transfer nodek∈KG from train connection i∈IkP∪IkCA to train connection j∈Jsk that is departing in direction s∈Sk(min)IkPSet of train connections arriving to nodek∈KIGWSet of train connections operated within the network in questionICASet of train connections, with which connection included inIGW are coordinated in the set of nodes KCIkCASet of train connections of external transportation providers that service nodek∈KJskSet of train connections departing from nodek∈K in direction s∈SkKSet of nodes, in which transfer of passengers among train connections are plannedKCSubset of transfer nodes of setK, in which transfers of passengers between train connections of the transportation provider in question and train connections of external transportation providers are plannedKGSubset of transfer nodes of setK, in which transfers of passengers among train connections of the transportation provider in question are plannedKVSet of the initial nodes of individual train connectionsKiSet of nodes, in which passengers will transfer from train connectioni∈IGWmijdBinary variable that models the passing plan of the train connections coming from opposite directionsi∈IGW and j∈IGW; aij=1 in node d∈DNMaximal permitted change of individual train connections(min)nkNumber of train connections leaving from initial nodek∈IGWqijdNonnegative variable that models the time loss incurred due to two train connections passing each other in the opposite directioni∈IGW and j∈IGW; aij=1 in node d∈DR0+Set of nonnegative numbersSkSet of the directions, in which individual train connections leave from transfer nodek∈KINTRegular time interval among connections that service the routes within the network in question(min)TidepEarliest possible departure time of train connectioni∈IGW from its initial node(min)tktrTransfer time for nodek∈K(min)tikTrip time of train connectioni∈IGW from its initial node to transfer node k∈Ki(min)xiNonnegative variable that models the time change of the departure of train connectioni∈I from the initial node(min)zijskBinary variable that models the origin of a transfer relation between train connectioni∈IkP∪IkCA and train connection j∈Jsk that departs in direction s∈Sk in node k∈KτidTrip time of train connectioni∈IGW from the initial node to node d∈Di(min)The mathematical model will then have the following :(4)minfx,z,h,m,q=∑i∈IkP∑j∈Jsk∑s∈Sk∑k∈KChijskfijsk+∑i∈IkCA∑j∈Jsk∑s∈Sk∑k∈KChijskfijsk++∑i∈IkP∑j∈Jsk∑s∈Sk∑k∈KGhijskfijsk+∑i∈IGW∑j∈Jsk∑d∈Daijqijdsubject to(5)Tjdep+xj−Tidep+tktr≥Mzijsk−1,fori∈IkCA,j∈Jsk,k∈KC,s∈Sk,(6)Tjdep+xj−Tidep+tktr≤hijsk+M1−zijsk,fori∈IkCA,j∈Jsk,k∈KC,s∈Sk,(7)∑j∈Jskzijsk=1,fori∈IkCA,k∈KC,s∈SkG,(8)Tjdep−Tidep+tik+xi+tktr≥Mzijsk−1,fori∈IkP,j∈Jsk,k∈KC,s∈Sk,(9)Tjdep−Tidep+tik+xi+tktr≤hijsk+M1−zijsk,fori∈IkP,j∈Jsk,k∈KC,s∈Sk,(10)∑j∈Jskzijsk=1,fori∈IkP,k∈KC,s∈SkCA,(11)Tjdep+tjk+xj−Tidep+tik+xi+tktr≥Mzijsk−1,fori∈IkP,j∈Jsk,k∈KG,s∈Sk,(12)Tjdep+tjk+xj−Tidep+tik+xi+tktr≤hijsk+M1−zijsk,fori∈IkP,j∈Jsk,k∈KG,s∈Sk,(13)∑j∈Jskzijsk=1,fori∈IkP,k∈KG,s∈Sk,(14)Tjdep+τjd+xj−Tidep+τid+xi≥Mmijd−1,fori∈IGW,j∈IGW,aij=1,d∈D,(15)Tjdep+τjd+xj−Tidep+τid+xi≤qijd+M1−mijd,fori∈IGW,j∈IGW,aij=1,d∈D,(16)∑d∈Dmijd=1,fori∈IGW,j∈IGW,aij=1,(17)xi≤N,fori∈IGW,(18)xi∈R0+,fori∈IGW,(19)hijsk∈R0+,fori∈IkCA,j∈Jsk,k∈KC,s∈Skand,i∈IkP,j∈Jsk,k∈KC,s∈Skand,i∈IkP,j∈Jsk,k∈KG,s∈Sk,(20)qijd∈R0+,fori∈IGW,j∈IGW,aij=1,d∈D,(21)zijsk∈0,1,fori∈IkCA,j∈Jsk,k∈KC,s∈Skand,i∈Ikp,j∈Jsk,k∈KC,s∈Skand,i∈IkP,j∈Jsk,k∈KG,s∈Sk,(22)mijd∈0,1,fori∈IGW,j∈IGW,aij=1,d∈D.Function (4) represents an optimization criterion of the overall time loss arising from the creation of the transfer relations between individual train connections and the overall time loss arising from passing of train connections running in the opposite directions. Constraints (5), (8), and (11) ensure that if it is not possible to link an arriving train connection to a departing train connection at the given node, no transfer relation is formed between these train connections. Constraints (6), (9), and (12) ensure that when a transfer relation between two train connections is formed, the corresponding time loss is incorporated in the given function. Constraints in pairs (5) and (6), (8) and (9), and (11) and (12) represent the so-called constraints of the “either-or” type, which means that only one of the stated constraints is always active. Constraints (7), (10), and (13) ensure that each arriving train connection is assigned precisely to one connecting connection for each direction of transfer. Constraints (14) and (16) ensure that if passing can be implemented at a suitable node for the given train connections running in opposite directions, this passing is implemented and the time loss arising from waiting for the train connection running in the opposite direction will be included into the value of the optimization criterion. Constraint (16) ensures that one node suitable for passing will be determined for each pair of the train connections running in opposite directions, provided passing is required for this pair of the train connections (this fact is given by the incidence matrix). Constraint (17) defines the maximal possible time change of the corresponding train connections. Constraints (18)–(22) specify domains of definition of the variables used in the model.


## 4. Calculation Experiments with Proposed Model: Case Study

The given coordination problem is solved within the frame of a real railway network in the South Bohemian Region in the Czech Republic, see Figures1 and 2.Figure 1
Position of the Czech Republic in Europe [29].Figure 2
Position of the South Bohemian region in the Czech Republic [30].The actual railway network is formed by three railway routes, numbered 194 (Ceske Budejovice-Nove Udoli), 197 (Cicenice-Nove Udoli), and 198 (Strakonice-Volary).Route number 194 starts at the Ceske Budejovice train station, passes through Cesky Krumlov, and ends in Cerny Kriz. Some trains that run along this line continue all the way to Nove Udoli.Route number 197 starts at the Cicenice train station, passes through Prachatice, Volary, and Cerny Kriz, and ends in Nove Udoli.The last route, number 198, starts at the Strakonice train station, passes through Vimperk, and ends in Volary.The explored railway network is shown on Figure3.Figure 3
The railway network in question with transfer links.It is a single-track railway network. All its routes are serviced by GWTR, a railway transportation provider. Time changes of the connections of this transportation provider can be adopted. The network is connected to other railway routes and serviced by other (external) transportation providers, at the Ceske Budejovice, Cicenice, and Strakonice train stations. Time changes of the connections of external transportation providers are not possible (due to, for example, establishing transfer connections in other transfer nodes, which do not form a subject of the coordination process).Because all railway lines of the network in question are single-track, passing of trains going in opposite directions thus have to be ensured at intermediate railway stations.Figure3 shows directions, to which train connection time changes can be implemented. These connections are marked purple, yellow, and green. Directions, to which such time changes cannot be implemented, are the orange and blue directions. The orange and blue directions in Figure 3 represent transfers among connections of railway carrier GETR and connections of external transport providers. The purple directions in Figure 3 represent transfers among train lines on route number 198 (Strakonice-Volary). The yellow directions represent transfers among train lines on route number 197 (Cicenice-Nove Udoli) and the green directions represent transfers among train lines on routes 194 and 197 (Ceske Budejovice-Nove Udoli and Cicenice-Nove Udoli).From the perspective of functions, there are two types of nodes (train stations) in the network. The first type is represented by nodes where train connections are coordinated (passengers can transfer there). The other type is represented by nodes, in which passing of individual train connections occurs (trains that run in opposite directions meet at these nodes). Some nodes have both functions, i.e., passengers transfer there and passing of train running in opposite directions occurs there as well. A list of all nodes pursuant to individual types is attached below.Nodes, at which train connections are coordinated:Strakonice, Cicenice, Ceske Budejovice, Volary, and Cerny Kriz.Nodes, at which passing of train connections occur:Strunkovice n. Vol., Ckyne, Bohumilice v C., Vimperk, Lenora, Vodnany, Bavorov, Strunkovice nad Blanici, Prachatice, Chroboly, Zbytiny, Volary, Cerny Kriz, Borsov nad Vltavou, Kremze, Zlata Koruna, Cesky Krumlov, Kajov, Horice na Sumave, Polna na Sumave, Cerna v Posumavi, Horni Plana, and Nova Pec.Operation at the characterized railway network is periodical. Train connections along all routes in question are operated in both directions in the same interval. It is required for the planned schedule that individual train connections depart the corresponding initial train station in a 2-hour cycle.In case of the presented case study, the model considers a total of 38 periodic train connections, time positions of which can be changed. Furthermore, the model also considers a total of 299 train connections for which it holds that their time positions cannot be changed.The number of the train connections arriving to the Ceske Budejovice train station amounts to 70, while for the Cicenice train station the number is 43 and for the Strakonice train station 30. In this case, the directions, from which these train connections arrive, are not considered since the model ensures that exactly one transfer relation to a departing connection is created for each of the abovementioned train connection.However, such a simplification cannot be applied to departing connections since the departing direction, in which the given connection is departing, must be also considered for every departing connection. The total number of the train connections departing from the Ceske Budejovice train station amounts to 70. Their directional structure is as follows: 10 connections depart in the direction of Horni Dvoriste, 8 connections depart in the direction of Ceske Velenice, 27 connections depart in the direction of Veseli nad Luznici, and 25 connections depart in the direction of Cicenice. The total number of the train connections departing from the Strakonice train station is 35. Their directional structure is as follows: 19 connections depart in the direction of Razice, 8 connections depart in the direction of Horazdovice, and 8 connections depart in the direction of Blatna. The total number of the train connections departing from the Cicenice train station is 51. Their directional structure is as follows: 26 connections depart in the direction of Protivin and 25 connections depart in the direction of Divcice.Train connections for which it holds that their time positions can be changed are divided in the following manner. The route Ceske Budejovice-Nove Udoli has a total of 12 starting train connections (the Ceske Budejovice train station is the initial node for 6 of them, while the Nove Udoli train station is the initial node for the remaining 6 train connections).The route Cícenice-Nove Udoli has a total of 14 starting train connections (the Cicenice train station is the initial node for 7 of them, while the Nove Udoli train station is the initial node for the remaining 7 train connections).The route Strakonice-Volary has a total of 12 starting train connections (Strakonice train station is the initial node for 6 of them, while the Volary train station is the initial node for the remaining 6 train connections).The initial time positions of the train connections related to individual coordination nodes and to individual nodes, at which trains running in the opposite directions can pass one another (see Tables2–4), represent necessary input data. Yet other input data are formed by the earliest possible time positions of the departures of individual train connections (see Tables 5–8). Other input data include the volumes of the transfer passengers for individual coordination nodes (see Table 9). The transfer time defined for individual nodes amounts to 3 minutes.Table 2
Travel time for the Ceske Budejovice-Nove Udoli route.
Coordination node suitable for passing-DTravel time from Ceske Budejovice in the direction of Nove Udoli (hh : mm)-τidTravel time from Ceske Budejovice in the direction of Nove Udoli (mm)-τidTravel time from Nove Udoli in the direction of Ceske Budejovice (hh : mm)-τidTravel time from Nove Udoli in the direction of Ceske Budejovice (mm)-τidCeske Budejovice0 : 0002 : 21141Borsov nad Vltavou0 : 0992 : 09129Kremze0 : 23231 : 55115Zlata Koruna0 : 36361 : 42102Ceský Krumlov0 : 52521 : 3191Kajov1 : 00601 : 2080Horice na Sumave1 : 14741 : 0666Polna na Sumave1 : 24840 : 5656Cerna v Posumavi1 : 38980 : 4242Horni Plana1 : 501100 : 3535Nová Pec1 : 591190 : 2323Cerny Kriz2 : 171370 : 055Nove Udoli2 : 281480 : 000Table 3
Travel time for the Cicenice-Nove Udoli route.
Coordination node suitable for passing-DTravel time from Cicenice in the direction of Nove Udoli (hh : mm)-τidTravel time from Cicenice in the direction of Nove Udoli (mm)-τidTravel time from Nove Udoli in the direction of Cicenice (hh : mm)-τidTravel time from Nove Udoli in the direction of Cicenice (mm)-τidCicenice0 : 0002 : 04124Vodnany0 : 0771 : 58118Bavorov0 : 22221 : 45105Strunkovice nad Blanici0 : 32321 : 3393Prachatice0 : 55551 : 2080Chroboly1 : 08681 : 0161Zbytiny1 : 23830 : 4747Volary1 : 471070 : 3030Cerny Kriz1 : 561160 : 1212Nove Udoli2 : 071270 : 000Table 4
Strakonice–Volary travel times.
Coordination node suitable for passing-DTravel time from Strakonice in the direction of Volary (hh : mm)-τidTravel time from Strakonice in the direction of Volary (mm)-τidTravel time from Volary in the direction of Strakonice (hh : mm)-τidTravel time from Volary in the direction of Strakonice (mm)-τidStrakonice0 : 0001 : 53113Strunkovice nad Volynkou0 : 11111 : 41101Ckyne0 : 37371 : 1575Bohumilice v Cechach0 : 43431 : 0868Vimperk0 : 53531 : 0060Lenora1 : 37970 : 1515Volary1 : 421020 : 000Table 5
Earliest possible arrival times of the train connections to the Ceske Budejovice, Cicenice, and Strakonice coordination nodes, train connections for which no time changes are possible, belonging to setIkCA.
Arrival time at Ceske Budejovice (hh : mm)Arrival time at Ceske Budejovice (mm)Arrival time at Strakonice (hh : mm)Arrival time at Strakonice (mm)Arrival time at Cicenice (hh : mm)Arrival time at Cicenice (mm)7 : 504708 : 515318 : 184987 : 514719 : 055458 : 255057 : 544749 : 505908 : 425227 : 5647610 : 326329 : 105508 : 0248210 : 456459 : 325728 : 0548510 : 516519 : 395798 : 3051011 : 0566510 : 186188 : 4152111 : 5071010 : 256258 : 4552512 : 3275210 : 396398 : 5153112 : 4576510 : 416418 : 5253212 : 5177111 : 006608 : 5853813 : 0578511 : 106709 : 1155113 : 2180111 : 326929 : 4958913 : 5083011 : 396999 : 5459414 : 3287212 : 187389 : 5659614 : 4588512 : 257459 : 5859814 : 5189112 : 3975910 : 0260215 : 0590512 : 4176110 : 4164115 : 4594513 : 0078010 : 4864815 : 4794713 : 1079010 : 5165116 : 1897813 : 3281211 : 0266216 : 3299213 : 3581511 : 0966916 : 50101014 : 1885811 : 2968916 : 51101114 : 2586511 : 4970917 : 04102414 : 3987911 : 5171117 : 05102514 : 4188111 : 5471417 : 48106815 : 0090011 : 5671618 : 32111215 : 0990911 : 5771718 : 45112515 : 3293212 : 0272218 : 51113115 : 3593512 : 4176116 : 1897812 : 4576516 : 2598512 : 5177116 : 40100012 : 5777716 : 41100113 : 0978917 : 15103513 : 2780717 : 17103713 : 4982917 : 32105213 : 5283217 : 35105513 : 5483418 : 18109813 : 5683618 : 25110514 : 0284218 : 40112014 : 4188118 : 41112114 : 4488419 : 10115014 : 4888814 : 5189114 : 5889815 : 0790715 : 2192115 : 2792715 : 4994915 : 5195115 : 5495415 : 5695615 : 5895816 : 0296216 : 3099016 : 41100116 : 48100816 : 49100916 : 51101116 : 57101716 : 58101817 : 02102217 : 06102617 : 27104717 : 48106817 : 49106917 : 52107217 : 54107417 : 561076Table 6
Earliest possible departure times of the train connections from the Ceske Budejovice coordination node, train connections for which no time changes are possible, belonging to setIskO.
Departure time from Ceske Budejovice in the direction of Horni Dvoriste (hh : mm)Departure time from Ceske Budejovice in the direction of Horni Dvoriste (mm)Departure time from Ceske Budejovice in the direction of Ceske Velenice (hh : mm)Departure time from Ceske Budejovice in the direction of Ceske Velenice (mm)Departure time from Ceske Budejovice in the direction of Veseli n. Luznici (hh : mm)Departure time from Ceske Budejovice in the direction of Veseli n. Luznici (mm)Departure time from Ceske Budejovice in the direction of Cicenice (hh : mm)Departure time from Ceske Budejovice in the direction of Cicenice (mm)12 : 0672612 : 1073011 : 5771712 : 0472413 : 0278214 : 1085012 : 0272212 : 1373314 : 0384315 : 1091013 : 0278212 : 4276215 : 0190116 : 1097013 : 0878813 : 1279216 : 0696617 : 10103013 : 1279214 : 0484417 : 02102218 : 10109013 : 5783714 : 1385318 : 03108320 : 10121014 : 0284214 : 2786720 : 06120623 : 02138214 : 0884814 : 4288221 : 10127014 : 5789715 : 1291222 : 59137915 : 0290215 : 2992915 : 0890816 : 0496415 : 1291216 : 1397315 : 5795716 : 3399316 : 0296216 : 52101216 : 0896817 : 12103217 : 02102217 : 38105817 : 08102818 : 04108417 : 14103418 : 13109317 : 57107718 : 42112218 : 02108219 : 12115219 : 08114820 : 04120419 : 12115220 : 13121320 : 08120821 : 07126720 : 57125722 : 08132821 : 10127022 : 57137722 : 02132223 : 021382Table 7
Earliest possible departure times of the train connections from the Strakonice coordination node–, train connections for which no time changes are possible, belonging to setIskO.
Departure time from Strakonice in the direction of Razice (hh : mm)Departure time from Strakonice in the direction of Razice (mm)Departure time from Strakonice in the direction of Horazdovice (hh : mm)Departure time from Strakonice in the direction of Horazdovice (mm)Departure time from Strakonice in the direction of Blatna (hh : mm)Departure time from Strakonice in the direction of Blatna (mm)11 : 0666610 : 5365311 : 1067011 : 1967912 : 5377313 : 1079012 : 0772713 : 5583515 : 1591513 : 0678614 : 5389316 : 2198113 : 2280216 : 53101317 : 10103014 : 0284217 : 51107119 : 10115014 : 3687618 : 53113321 : 10127015 : 0690620 : 53125322 : 40136015 : 1991916 : 0296217 : 06102617 : 19103917 : 32105218 : 07108719 : 06114619 : 19115921 : 06126621 : 20128022 : 301350Table 8
Earliest possible departure times of the train connections from the Cicenice coordination node, train connections for which no time changes are possible, belonging to setIskO.
Departure time from Cicenice in the direction of Protivin (hh : mm)Departure time from Cicenice in the direction of Protivin (mm)Departure time from Cicenice in the direction of Divcice (hh : mm)Departure time from Cicenice in the direction of Divcice (mm)8 : 265068 : 194999 : 115518 : 425229 : 405809 : 3357310 : 2662610 : 1961910 : 4164110 : 4164111 : 1167111 : 0066011 : 4070011 : 3369312 : 2674612 : 1973912 : 4176112 : 4176113 : 1179113 : 0078013 : 3681613 : 3381314 : 2686614 : 1985914 : 4188114 : 4188115 : 1091015 : 0090015 : 3693615 : 3393316 : 2698616 : 1997916 : 41100116 : 41100117 : 18103817 : 21104117 : 36105617 : 33105318 : 26110618 : 19109918 : 41112118 : 41112119 : 11115119 : 33117319 : 36117619 : 59119920 : 26122620 : 19121921 : 36129621 : 33129323 : 261406Table 9
Volumes of transfer passengers.
Number of transfer passengers in the direction Cesky Krumlov > CB > Horni Dvoriste41021201715919123Number of transfer passengers in the direction Cesky Krumlov > CB > Ceske Velenice6190170201820Number of transfer passengers in the direction Cesky Krumlov > CB > Veseli nad L.2020961212333113241022061818211821112110125Number of transfer passengers in the direction Cesky Krumlov > CB > Cicenice2113471017121720161823200248918192131421Number of transfer passengers in the direction CB > Cesky Krumlov1591912361901702018202020961212333113241022061818211821112110125211347101712172016182320024891819213142133242325Number of transfer passengers in the direction Vimperk > Strakonice > Razice61513511220619720347010231622Number of transfer passengers in the direction Vimperk > Strakonice > Horazdovice5121731311242Number of transfer passengers in the direction Vimperk > Strakonice > Blatna2499219777Number of transfer passengers in the direction Strakonice > Vimperk15125020159154162281318212511319107801948127617Number of transfer passengers in the direction Prachatice > Cicenice > Protivin7122413192221121219982314221713221613133174Number of transfer passengers in the direction Prachatice > Cicenice > Divcice12251421118412253201742111521197632221714Number of transfer passengers in the direction Cicenice > Prachatice192151531291618196131918121810222111724168990466241352364102221223Number of transfer passengers in the direction Vimperk > Volary > Cerny Kriz253764Number of transfer passengers in the direction Cerny Kriz > Volary > Vimperk7834946Number of transfer passengers in the direction Volary > Cerny Kriz > Cesky Krumlov8232528Number of transfer passengers in the direction Cesky Krumlov > Cerny Kriz > Volary528757For the train connections running in opposite directions that serve routes 194, 197, and 198, passing must be implemented at the given intermediate stations. The necessity to solve passing of trains running in opposite directions is defined in the incidence matrix, a fragment of which is presented in Table10. When it is necessary to solve passing between train connections i and j, the incidence matrix shows value aij=1; in the opposite case, the value is 0. Passing of the train connections in their initial nodes (train stations) is not considered since in these situations train units could accumulate in the given initial train stations.Table 10
Fragment of the incidence matrix, which demonstrates the necessity of passing of train connections running in opposite directions.
ADeparture time (hh : mm)194-departure from Ceske Budejovice194-departure from Nove Udoli8 : 0010 : 0012 : 0014 : 0016 : 0018 : 009 : 0011 : 0013 : 0015 : 0017 : 0019 : 00Departure time (hh : mm)Sequence123456789101112194-departure from ceske Budejovice8 : 001x0000010000010 : 0020x000011000012 : 00300x00001100014 : 004000x0000110016 : 0050000x000011018 : 00600000x000011194-departure from nove udoli9 : 007110000x0000011 : 0080110000x000013 : 00900110000x00015 : 0010000110000x0017 : 00110000110000x019 : 001200000100000xUpon substituting the input values to the proposed mathematical model, the following results were achieved, see Table11.Table 11
Results achieved by optimization.
DirectionDeparture time prior to optimization (mm), (hh : mm)Earliest possible departure time prior to optimization (mm), (hh : mm)-TjodjChange (mm)-xDeparture time after optimization (mm), (hh : mm)Passing train stationsCeske Budejovice > Nove Udoli8 : 138 : 0048058 : 05485Horni Plana, Cesky Krumlov10 : 0710 : 00600510 : 0560512 : 1312 : 00720512 : 0572514 : 2614 : 00840514 : 0584516 : 1316 : 00960516 : 0596518 : 1318 : 001080518 : 051085Nove Udoli > Ceske Budejovice9 : 159 : 00540309 : 3057011 : 2211 : 006603011 : 3069013 : 1913 : 007803013 : 3081015 : 2315 : 009003015 : 3093017 : 2117 : 0010203017 : 30105019 : 1819 : 0011403019 : 301170Cicenice > Nove Udoli7 : 397 : 3045057 : 35455Bavorov, Zbytiny9 : 429 : 3057059 : 3557511 : 4211 : 30690511 : 3569513 : 4013 : 30810513 : 3581515 : 4015 : 30930515 : 3593517 : 4017 : 301050517 : 35105519 : 4019 : 301170519 : 351175Nove Udoli > Cicenice6 : 146 : 00360246 : 243848 : 008 : 00480248 : 2450410 : 1510 : 006002410 : 2462412 : 1512 : 007202412 : 2474414 : 1514 : 008402414 : 2486416 : 1916 : 009602416 : 2498418 : 1618 : 0010802418 : 241104Strakonice > Volary9 : 259 : 0054089 : 08548Bohumilice v C., Lenora11 : 2511 : 00660811 : 0866813 : 2513 : 00780813 : 0878815 : 2515 : 00900815 : 0890817 : 2517 : 001020817 : 08102819 : 2519 : 001140819 : 081148Volary > Strakonice8 : 478 : 30510278 : 5753710 : 4710 : 306302710 : 5765712 : 4712 : 307502712 : 5777714 : 4714 : 308702714 : 5789716 : 4716 : 309902716 : 57101718 : 4718 : 3011102718 : 571137It is clear from the achieved results that individual train connection times changed and, moreover, nodes suitable for passing of individual train connections were also determined.Based on the results of the mathematical model and on subsequent conversion of the achieved values to a projected timetable, we can compare the operation characteristics along individual routes with the current situation.Periodical operation was introduced along route Ceske Budejovice-Nove Udoli. As a part of it, passing occurs at the Horni Plana and Cesky Krumlov train stations, while the departures of individual train connections are of a periodical character. The train connections currently depart only in approximately similar time positions and the passing nodes of individual train units are not unified.Periodical operation along route Cicenice-Nove Udoli was preserved, so were the passing nodes, i.e., the Bavorov and Zbytiny train stations. Only the time positions of the train connections were changed.Periodical operation along route Strakonice-Volary was also preserved. Along this route, one passing node was changed, specifically from the Ckyne train station to the Bohumilice v Cechach train station. Furthermore, time positions of the train connections were also changed.Yet another output of the mathematical model is represented by the creation of transfer relations. A total of 222 relations were created at the Strakonice, Cicenice, Ceske Budejovice, Cerny Kriz, and Volary nodes. The time loss arising from the transfers among individual train connections amounts to 83 357 minutes. The time loss arising from the transfers among individual train connections in the current situation amounts to 112 262 minutes, based on which we can see that the optimization process resulted in a reduction of the time loss by 28 905 minutes.


## 5. Conclusions

The objective of the presented work was to develop an optimization tool, which will be used for reducing the time losses arising from transfers among individual passenger train connections. In the introduction of the article, we discuss the importance of the issue in question and we talk about the analysis of the state of the art and individual solutions related to the time coordination of the connections in various transportation systems.The main part of the article deals with the proposal and detailed description of the general mathematical model which enables to coordinate train connections operated on single-track railway networks. The proposed mathematical model was tested in conditions of the selected railway network of the Czech Republic. The railway network used in the case study is in the South Bohemian Region and is operated by the railway carrier GWTR.In the conclusion of the article, we assess the results of the time coordination of the given train connections at the Ceske Budejovice, Cicenice, Strakonice, Volary, and Cerny Kriz coordination nodes. The outputs of the mathematical model are presented in the table form, and they show time changes of the train connections based on the result of the optimization calculation and the passing locations of the given train connections.The model proposed in this article is very general and can be easily modified based on particular conditions at other railway networks (the number of the transfer nodes or the number of train stations suitable for passing train connections running in opposite directions can be increased or reduced). The model can also be used for coordinating transfers among train connections in transfer nodes as well as multitrack and two-track railway routes, which are characterized by the fact that individual tracks are used only by train connections running in one direction (in that case, the input values, groups of conditions, and components of the purposeful function related to passing at en route stations are removed). The model can also be used for optimizing transfer relations during railway network operation or modernization outages, when the number of tracks between two train stations, etc., is temporarily reduced.



---

*Source: 3876561-2021-03-09.xml*