Technology INTERNATIONAL Internationales Verkehrswesen (74) 1 | 2022 43 Generating robust dispatching solutions Taking into account block sections’ operational risk Dispatching, Rescheduling, Risk mapping, Operational risk analysis Not least because of the increasing demand for transport and limited possibilities to expand railway infrastructures, efficient dispatching approaches gain in importance. The Institute of Railway and Transportation Engineering at the University of Stuttgart developed a proactive dispatching algorithm, which automatically generates robust dispatching solutions while taking random disturbances in dynamic circumstances into account. Ullrich Martin, Markus Tideman, Weiting Zhao N ot least because of the increasing demand for transport and limited possibilities to expand railway infrastructures, efficient dispatching approaches gain in importance. Hence and thankfully funded within the framework of a German Research Foundation (DFG) project, the Institute of Railway and Transportation Engineering at the University of Stuttgart developed a proactive dispatching algorithm, which automatically generates robust dispatching solutions while taking random disturbances in dynamic circumstances into account [1]. Therefore, the proposed algorithm consists of two major processes as depicted in figure 1: The operational risk analysis, which is performed in offline mode and the generation of dispatching solutions in online mode-[2]. The main idea behind this dispatching approach is that the negative impact of disturbances on the operational quality strongly depends on the points of their appearance. By dividing the infrastructure into block sections and by disturbing railway operation on every block section separately in offline mode as shown in figure 2, the resulting operational risk index of every block section of the studied network can be calculated based on the resulting average total weighted waiting time. Finally, an operational risk map can be obtained. This risk map remains valid as long as neither significant changes in infrastructure nor in railway operations program occur [3]. According to figure 3 and based on the findings of the operational risk analysis, the dispatching solutions are generated in online mode, which means during real time operation. To ensure a lasting effect of the generated solutions, the investigated time span is divided into stages (1 st task). At the beginning of every stage, the train runs of the current timetable are artificially prolonged according to the risk levels of the block sections a train passes (2 nd task). Regarding this linkage, a detailed description is made in the next section. The underlying idea is, to add implicitly especially for high-risk block section larger additional recovery times, whereby the timetable is more robust against potential disturbances. Then, it is checked whether the modified timetable contains blocking time conflicts. If no conflicts are detected, the current timetable will be maintained until the beginning of the next stage. Otherwise, the conflicts are solved by retiming or reordering as it is described in [4] and partly in the next section (3 rd task). Methods The proposed dispatching algorithm is based on several widespread used scientific methods such as Tabu Search algorithm as well as Monte Carlo method. The latter one is used for creating sufficient disturbance scenarios during the operational risk analysis (see [3]). In addition, the inverse cumulative distribution function is utilized in connection with the aforementioned linkage between the risk index of a specific block section and the prolonging of the train runs along this section. Depending on the characteristics of the investigated railway network, the block sections are classified according to their risk index into so-called risk level (L). To prolong the train runs, it is necessary to establish a functional relationship between the risk level of a block section and the additional recovery times (x) to be added in the 2 nd task (see figure 3). Those additional recovery times represent potential disturbances like dwell time extensions, departure time extensions, running time extensions and entry delays. Unfavorably, it is difficult to directly link x to L, which is why a cumulative distribution function (P) serves as a bridge that linearly relates P to L Figure 1: General workflow of the dispatching algorithm INTERNATIONAL Technology Internationales Verkehrswesen (74) 1 | 2022 44 with maximum-minimum normalization [1,-4]. Concerning this, the underlying mathematical derivation is given in formula 1: (1) It can easily been seen that x depends on P max (maximum value of cumulative probability function), P min (minimum value of cumulative probability function), L max (maximum value of operational risk level), and L min (minimum value of operational risk level) as well as L. While L represents the individual risk level of a specific block section, the four other variables are predefined by the user before using the dispatching algorithm. As described in the introduction and according to figure 3, it is investigated whether these prolonged train runs are coming into conflict with each other. If they do so and a user-defined threshold that represents a maximum allowable total weighted waiting time is exceeded, the conflicts are rated as significant conflicts. In this case, the train runs are reordered with the help of Tabu Search algorithm. At this, neighboring train orders starting with the current train order are generated and the corresponding total weighted waiting time is calculated iteratively, until a user-defined aspiration and/ or termination criteria is satisfied. In this way, a balance between the quality of the solution and the computation time is ensured [4]. Results In this paper, special attention is paid to the linkage between the calculated risk index or rather risk level of a block section and the additional recovery times that are added on the trains passing through this block section. In the framework of a case study, a reference railway network was utilized that consists out of 35 block sections. Under the assumption of L max = 5 (maximum value of operational risk level) and L min = 1 (minimum value of operational risk level), the operational risk analysis revealed the classification shown in table 1 [2]. To obtain the additional recovery times based on the shown risk classification and by utilizing the formula shown in figure 4 a few more assumptions had to be made in the case study [4]: •• The maximum value of cumulative probability function P max is set 0,95 •• The maximum value of cumulative probability function P min is set 0,05 •• The negative exponential distribution with rate parameter β = 10 minutes Figure 2: Workflow of the operational risk analysis Figure 3: Workflow of the generation of dispatching solutions Technology INTERNATIONAL Internationales Verkehrswesen (74) 1 | 2022 45 serves as the probability distribution function f(x) All these things considered, the resulting additional recovery times for the train runs can be obtained. As an instance, table 2 shows the additional recovery times imposed on freight train runs depending on the risk level of the block sections. It should be noted that entry delays are only relevant for block sections functioning as an entrance to the investigated railway network and that dwell time extensions and departure time extensions are only relevant, if the timetable of a specific train run contains a stop in the specific block section. Modifying the current timetable according to the obtained, partly very large additional recovery times and continuing the workflow of the generation of dispatching solutions as depicted in figure 3, it might be assumed that the resulting maximum throughput capacity of the investigated railway network would be compared to other widely used dispatching principles significantly lower. In fact, extensive testing within the case study proved for 1,650 assumed disturbed timetables that the proposed dispatching algorithm offers even a 2.68 or rather 4.46 percent higher maximum throughput capacity than greedy algorithm and first come first serve-principle [1]. Conclusions and Contributions The dispatching algorithm described in this paper possesses considerable advantages. First, railway dispatchers can effectively be relieved. This can be traced back to the automatic generation of dispatching solutions as well as to their increased robustness against potential disturbances. Second, the first major algorithm process, which is the operational risk analysis, can be utilized for effective timetable planning by disclosing high-risk block sections long before real time railway operation. Building on this, recovery times can be spread more efficient along the train runs. This supports a good balance between capacity utilization and operation quality. Furthermore, the algorithm is capable to solve various conflict types such as following, crossing, merging and opposing conflicts and it is basically possible to adapt the algorithm to any other railway network implemented in RailSys software. Moreover, the proposed dispatching approach provides further flexibility. On the one hand, the length of the stages (see Figure 3, 1st task) can be adjusted depending on the application case. On the other hand, the probability distribution function, which is used to link the risk level of a specific block section to the additional recovery times, can be set individually. Concluding all, the proposed dispatching algorithm is a promising approach to raise railway operation quality in the event of disturbances. Not least because of the algorithms’ high flexibility, one of the current research work of the Institute of Railway and Transportation Engineering at the University of Stuttgart deals with its adaption in the field of other transport modes. ■ REFERENCES [1] Martin, U.; Tideman, W.; Zhao, W. (2018): Risk Oriented Dispatching of Railway Operation under the Consideration of Random Disturbances in Dynamic Circumstances (DICORD). DFG-project (MA 2326/ 22-1) - in progress, Institute of Railway and Transportation Engineering, Stuttgart [2] Tideman, W.; Martin, U.; Zhao, W. (2019): Proactive Dispatching of Railway Operation. Proceedings to 8th International Conference on Railway Operations Modelling and Analysis (ICROMA) - Rail- Norrköping 2019, Norrköping, Sweden, June 17th - 20th, 2019, pp. 1605-1614 [3] Zhao, W. (2017): Hybrid Model for Proactive Dispatching of Railway Operation under the Consideration of Random Disturbances in Dynamic Circumstances, vol. 22, Books on Demand, Norderstedt, Neues verkehrswissenschaftliches Journal [4] Zhao, W. ; Martin, U.; Cui, Y.; Liang, J. (2017): Operational risk analysis of block sections in the railway network. In: Journal of Rail Transport Planning & Management, 7 (4), pp. 245-262, DOI: 10.1016/ j. jrtpm.2017.09.003 Markus Tideman, M.Sc. Former research assistant, Institute of Railway and Transportation Engineering (IEV), University of Stuttgart (DE) post@ievvwi.uni-stuttgart.de Weiting Zhao, Dr.-Ing. Former research assistant, Institute of Railway and Transportation Engineering (IEV), University of Stuttgart (DE) post@ievvwi.uni-stuttgart.de Ullrich Martin, Prof. Dr.-Ing. Director, Institute of Railway and Transportation Engineering (IEV), University of Stuttgart (DE) ullrich.martin@ievvwi.uni-stuttgart. de AUF EINEN BLICK Nicht zuletzt aufgrund des steigenden Transportbedarfs und eingeschränkter Möglichkeiten zum Ausbau von Bahninfrastrukturen gewinnen effiziente Dispositionsansätze an Bedeutung. Daher hat das Institut für Eisenbahn- und Verkehrswesen der Universität Stuttgart im Rahmen eines von der Deutschen Forschungsgemeinschaft (DFG) geförderten Projekts einen proaktiven Dispositionsalgorithmus entwickelt, der unter Berücksichtigung zufälliger Störungen bei sich dynamisch ändernden Situationen automatisch robuste Dispositionslösungen generiert. Der entwickelte Algorithmus besteht aus zwei Hauptprozessen: Der betrieblichen Risikoanalyse, die im Offline- Modus durchgeführt wird, und der Generierung von Dispositionslösungen im Online- Modus. Besonderes Augenmerk wird in diesem Beitrag auf die Verknüpfung dieser beiden Prozesse gelegt, indem in einer sogenannten betrieblichen Risk Map die Beförderungszeiten der Zugfahrten entsprechend der in dieser Risk Map enthaltenen Risikostufen der einzelnen Blockabschnitte verlängert werden. Darüber hinaus gibt dieser Artikel eine kurze Einführung in den vorgeschlagenen Dispositionsalgorithmus im Allgemeinen. Außerdem werden kurze Auszüge einer Fallstudie beschrieben, die die Wirksamkeit des Algorithmus belegen. Risk level Block section designation 1 (lowest risk) B18, B24, B29, B32, B33, B34, B35 2 B1, B2, B15, B16, B17, B30, B31 3 B3, B5, B9, B10, B22, B23, B25 4 B4, B11, B13, B14, B26, B27, B28 5 (highest risk) B6, B7, B8, B12, B19, B20, B21 Table 1: Operational risk levels of the block sections in the context of the case study Additional recovery time [min] to compensate … Risk level … dwell time extensions … running time extensions … departure time extensions … entry delays 1 (lowest risk) 0.26 0.51 0.26 1.03 2 1.04 2.08 1.04 4.15 3 1.97 3.93 1.97 7.86 4 3.10 6.21 3.10 12.42 5 (highest risk) 4.58 9.16 4.58 18.33 Table 2: Additional recovery times imposed on freight train runs on the specific block sections