Simulation-Based Rail Traffic Optimizations Applying Multicriterial Evaluations of Variants

SIMULATION-BASED RAIL TRAFFIC OPTIMISATIONS APPLYING MULTICRITERIAL EVALUATIONS OF VARIANTS Michael Bažant1, Antonín Kavička1,, Roman Diviš1, Michal Varga2 1Faculty of Electrical Engineering and Informatics, University of Pardubice, Czech Republic 2Faculty of Informatics and Management Science, University of Zilina, Slovakia [email protected], [email protected], [email protected], Michal[email protected]niza.sk Abstract The contribution pays attention to assessing a selected method related to multicriterial evaluations of variants. That method is exploited for supporting automatized decision-making processes related to special operational situations, which emerge within rail traffic simulators. The relevant case study resolves an optimisation task related to minimizations of total increments of train delays within passenger railway stations. Different optimisation approaches are combined and exploited, and their consequences are investigated by means of numerous simulation experiments. The outcomes of those experiments are processed, and recommendations for the use of appropriate decision-making supports in rail simulators are formulated. Keywords: traffic optimisation, multicriteria decision making, computer simulation. Received: 0 9 April 2019 Accepted: 31 May 2019 Published: 24 June 2019 1 Introduction Traffic optimisations of railway systems can be focused on a quite wide class of problems, which are supposed to be solved. Operative decision-making processes, which are related to problematic/crisis traffic situations, play an important role in those systems. Enhanced decision-making strategies usually cause better traffic quality from the viewpoint of traffic fluency and compliance with the timetable. For the needs of investigations and optimisations related to rail traffic a lot of different methods and approaches are utilized. In this context, computer simulation method is used, which investigates different traffic scenarios/variants applying occurrences of random phenomena (e.g. random train delays). Thus, computer simulation is able to include selected optimisation method for making relevant automatized solutions during simulation experiments. Application of different optimisation methods can be tested within simulating systems before their potential exploitation in the real operation. The contribution pays attention to automatized assignments of platform tracks to potentially delayed trains approaching passenger railway stations. The minimization of total increments of train delays (within relevant railway station) is exploited as a suitable optimisation criterion. Assignments of platform tracks to arriving trains were theoretically resolved namely by means of artificial neural networks [1], integer linear programming [2,3], nested simulations [4] and alternative graphs [5]. In addition, the methods applying multicriterial evaluation of variants (e.g. Saaty’s method) were considered as well. However, the mentioned approaches were not routinely utilized within any relevant commercial traffic simulation tool. The use of Saaty’s method recently implemented in the specialized component of Villon simulation tool [8] is described below. The results of relevant simulation experiments employing that method (as a supplement to static priority train routes) are compared with results of other scenarios which did not apply multicriterial solutions. 2 Assignments of Platform Tracks to Delayed Trains As mentioned above the contribution is focused on automatized optimisations of allocating platform tracks to delayed trains. The originally planned tracks for those trains (specified in the official station document: Track occupation plan) can be potentially occupied by other trains. The adduced optimisations should correspond to routine decision-making processes carried out by experienced dispatchers. Their decisions lead to solutions which guarantee acceptable degree of traffic disturbances. https://doi.org/10.13164/mendel.2019.1.139 ISSN: 1803-3814 (Printed), 2571-3701 (Online) MENDEL — Soft Computing Journal, Volume 25, No.1, June 2019, Brno, Czech RepublicX 139 The next subsections briefly describe original criteria for assignments of substitutional platform tracks to delayed trains. The detailed explanations of calculations related to relevant criterial values were published in [1]. 2.1 Criteria for Selecting Substitutional Platform Tracks In order to select a substitutional platform track to a delayed train approaching railway station, at first the real station operation is supposed to be considered. In the case that a delayed train arrives to a station the dispatcher has to assign the most appropriate track from the viewpoint of several aspects. The first step of selecting platform track is connected with a determination of admissible sets of tracks for incoming train. Those sets are constructed with regard to relevant topological positions of a planned reception track and a departing track in the studied station. The mentioned sets are denoted as 𝐾𝐿𝑖,𝐿𝑗, where 𝐿𝑖 represents the given reception track and 𝐿𝑗 relevant departing track. The illustrative sets of admissible tracks are depicted in Fig. 1. The following predefined sets of admissible tracks are presented as examples: 𝐾𝐿1,𝐿1={𝑘4,𝑘2,𝑘1,𝑘5,𝑘7},𝐾𝐿1,𝐿2={𝑘4,𝑘2,𝑘1,𝑘5,𝑘7},…,𝐾𝐿5,𝐿5={𝑘7,𝑘9,𝑘11}. Those sets can be potentially further reduced (e.g. tracks of insufficient lengths are supposed to be eliminated). Figure 1: Track layout of an illustrative passenger railway station If a delayed train approaches the observed station the most appropriate platform track (from a relevant set of admissible tracks) is assigned. The track suitability, at the time of a real train arrival, is evaluated by means of following criteria (derived from the knowledge of dispatchers): Criterion A: Track availability at the moment of the train’s arrival. Criterion B: Track availability period regarding the planned dwell time of a given arriving train. Criterion C: Occupation of the neighbouring track by a given connecting train at the same platform. Criterion D: Other technical and technological track advantages related to a given arriving train. The problem of platform track assignments represents a task of multicriteria evaluation of variants [6]. The set of variants (i.e. the set of admissible tracks), denoted as 𝐾={𝑘𝑗 | 𝑗=1…,𝑚}, disposes of finite number of elements. If the criteria (A, B, C, D) are specified and the methods of getting criterial values for individual variants are at disposal, the task is described by criterial matrix Y. The element 𝑦𝑖𝑗 of matrix Y expresses the value of criterion 𝑖 (where 𝑖 = 1,…,4 reflects criteria A, ..., D) for the given variant/track 𝑘𝑗∈𝐾. The mentioned matrix Y can be specified in the form: 𝑘 1 𝑘 2 … 𝑘 𝑚 𝐴 𝐵 𝐶 𝐷 ⎝ ⎜ ⎜ ⎛ 𝑦 11 𝑦 12 … 𝑦 1 𝑚 𝑦 21 𝑦 22 … 𝑦 2𝑚 𝑦 31 𝑦 32 … 𝑦 3𝑚 𝑦 41 𝑦 42 … 𝑦 4 𝑚 ⎠ ⎟ ⎟ ⎞ (1) The process of evaluating individual tracks applies maximization principle related to the rating 𝑂𝑗 of each track 𝑘𝑗(𝑗 = 1,…,𝑚): 𝑂 𝑗 = ∑ 𝑦 𝑖 , 𝑗 𝐷 𝑖 = 𝐴 ⋅ 𝑤 𝑖 (2) The values 𝑤𝑖 represent the weights of relevant criteria which can be calculated on the basis of Saaty’s method [7]. That method utilizes so called preference relations for the pairs of criteria (defined in Saaty’s matrix). The track with the maximum rating value 𝑂𝑗 is then assigned to a relevant train. Simulation-Based Rail Traffic Optimizations Applying Multicriterial Evaluations of Variants MENDEL — Soft Computing Journal, Volume 25, No.1, June 2019, Brno, Czech RepublicX 140 The calculations of criterial values associated with criteria A and B exploit so called Track occupation plan available for each passenger railway station. The data about occupations of each platform track (with the time step of one minute) are at disposal in that plan. 2.2 Track Availability at the Moment of the Train’s Arrival The criterion value evaluating the track availability at an instant of time could logically reflect either the status free or occupied. However, that concept would not be able to distinguish between tracks which will be occupied for a long time period or for a short time interval (and they could be potentially used by other trains arriving in a few moments). Because of that reason the criterion is suitable to be extended with regard to a given lookahead time. The calculation of A-criterion value for the delayed arriving train j and for the given track k (currently occupied by the train i) is carried out as follows: 𝑣𝑎𝑙 ( 𝐴 , 𝑘 ) = max ( 0 , 1 − 𝑇 𝑖 𝑟𝑙𝑠 𝑇 𝑖 𝑎 ℎ 𝑑 ) (3) here 𝑇 𝑖𝑟𝑙𝑠 represents a portion of time remaining to a release of the track k by the train i and 𝑇 𝑖𝑎ℎ𝑑 expresses a maximum considered lookahead time window related to the potential release of the track k by the train i. 2.3 Track Availability at the Moment of the Train’s Arrival The B-criterion value is related to the planned dwell time of the (potentially delayed) arriving train j on the platform track k in the investigated railway station. The value can be from the interval ⟨0,1⟩. The computation utilizes the time 𝑇𝑓𝑟𝑒𝑒 which corresponds to the availability period of the considered track k till the next train arrives. Another portion of time 𝑇 𝑗𝑜𝑐𝑐 represents the planned sojourn of the train j on the track k. The following formula expresses the mentioned value related to the delayed arriving train j assigned to the given track k: 𝑣𝑎𝑙 ( 𝐵 , 𝑘 ) = min ( 1 ,   𝑇 𝑗 𝑜𝑐𝑐 ) (4) The planned train dwell time is applied as a constant period. However, it can be dynamically shortened (e.g. in case of delayed arrival) especially for the trains where relevant technological service processes would not be disrupted. Another potential modification allows employing a longer dwell time than it is defined in the Track occupation plan. Such an approach enables that a given train can wait for the delayed connecting trains. 2.4 Occupation of the Neighbouring Track by a Given Connecting Train at the Same Platform If the connecting train i waits (on the track l) for the delayed arriving train j and that waiting could cause a delay (or a delay increment) of the train i, it is suitable to assign the train j to the same platform in order to shorten the needed change times (transfer times) of passengers. The mentioned reasons lead to establishing criterion C. The C-criterion value is selected from the interval ⟨0,1⟩. The C-criterion value for the given track k is determined as follows: 𝑣𝑎𝑙 ( 𝐶 , 𝑘 ) = 𝑇 𝑃 𝑚𝑎𝑥 − 𝑇 𝑃𝑘𝑙 𝑇 𝑃𝑚𝑎𝑥 − 𝑇 𝑃𝑚𝑖𝑛 (5) where 𝑇𝑃𝑚𝑎𝑥 represents a maximum period of time needed for passenger transfers between trains within a given station, 𝑇𝑃𝑚𝑖𝑛 denotes a minimum possible time of those transfers and 𝑇𝑃𝑘𝑙 quantifies a duration of transfers between the tracks k and l (it reflects the distance of those tracks). It means in fact that the track k, belonging to the same platform as the track l (where the connecting train i waits for the delayed train j), obtains the highest criterial value of all platform tracks in the investigated station. 2.5 Other Technical and Technological Track Advantages Related to a Given Arriving Train The last criterion (denoted as D) reflects other technical and technological advantages related to an assignment of the considered track to a given delayed arriving train j. The value can be from the interval ⟨0,1⟩. The track k regularly determined for a certain train can be associated with the following assignment: 𝑣𝑎𝑙(𝐷,𝑘) = 1. The track k, which is inappropriate for an arriving train, is linked with the assignment 𝑣𝑎𝑙(𝐷,𝑘) = 0. Other tracks obtain the values from the interval (0,1). M. Bazant et al. MENDEL — Soft Computing Journal, Volume 25, No.1, June 2019, Brno, Czech RepublicX 141 The D-criterion values are proposed according to knowledge of the investigated station. Those values can reflect for example the following facts: • The distance of the considered track for an assignment from the originally planned track for a given arriving train (the mentioned distance influences the change times of passengers). • The occupation rate of the reception switches section. That occupation can have a negative effect on the rides of other trains utilizing the same section of switches (within the same time window). 3 Simulation Experiments The automatized support of decision-making processes (described in the previous section) was tested in the project of the applied research New methodologies for determining capacities of the railway stations using computer simulation. That project was solved for the state company SŽDC –Rail Infrastructure Administration (the Czech Republic). The main attention was paid to the potential of traffic optimisation measures (and the related increase of infrastructure capacity). The proposed optimisations were tested within several simulation tools applied to selected railway stations in the Czech Republic. The dynamic multicriterial evaluations of variants, applied to selections of platform tracks for arriving trains, were investigated (as a supplementary support) within simulated traffic of the passenger station Lysá nad Labem. 3.1 Software Tool Villon Simulation software tool Villon [8] is specialized in microscopic simulations reflecting the rail traffic namely in railway nodes and restricted segments of railway networks. The above-mentioned problem of platform tracks assignments to (delayed) arriving trains is resolved by applying static priority lists of alternative train routes leading to different admissible target platform tracks. The sorting of those priority lists reflects a suitability degree of target platform tracks with regard to substitutional assignments to incoming trains. The highest priority is always related to the route which ends on the platform track originally planned for a given train (in the Track occupation plan). The mentioned lists are formed by railway experts within relevant editor. Thus, during simulation experiments dynamic allocations of platform tracks are carried out utilizing predefined priority lists. However, the construction of the mentioned lists applies the optimisation criterion mainly based on minimisations of occupation rates of the reception switches sections in order to support a reasonable throughput of those infrastructure segments. Application of that single-purpose approach is not able to reflect other traffic needs and therefore further optimisation procedures are supposed to be considered 3.2 Decision-Making Supplementary Support In order to enhance the current way of assigning platform tracks the supplementary optimisation support was implemented in simulation tool Villon. That supplement component utilizes the discussed concept of multicriterial evaluations of variants and it is currently tested. During the testing stage the principle of assessing proposed solutions by two methods (i.e. multicriterial evaluations as well as priority lists) is carried out. Each individual act of making decision during simulation is associated with a selection of better solution related to a platform assignment. The solution quality is measured by optimisation criterion expressed as minimisation of total increment of train delays. It means in fact, that two provided competitive solutions are rated by corresponding two different internal simulation lookaheads. The perspective implementation is supposed to utilize just one software component that does not make any simulation lookahead. 3.3 Simulation Scenarios As mentioned above simulation experiments reflected rail traffic within the passenger station Lysá nad Labem. Before presenting the current outcomes from simulations (applying supplementary method of dynamic multicriterial evaluations of variants) it is needed to describe the features of implemented simulating system and relevant scenarios of experiments: • Track infrastructure is interconnected with 4 railway lines. There are 7 platform tracks in the station (see Fig. 2). The infrastructure involves also restricted sections of adjacent railway lines. • Timetable concentrates on the morning peak hours (8 a.m. – 10 a.m.) and it is composed of 29 trains (see Fig. 3). • Trains involved in simulation experiments are of the following categories: stopping trains, express trains and freight trains. Simulation trials calculate with randomly delayed arriving trains. The utilized train delays match to demands, which are involved in the forthcoming directive of SŽDC: Determining the Simulation-Based Rail Traffic Optimizations Applying Multicriterial Evaluations of Variants MENDEL — Soft Computing Journal, Volume 25, No.1, June 2019, Brno, Czech RepublicX 142 capacity of railway systems. In this context, each arriving train in the simulating system disposes of two following data items: o The probability of a delay occurrence associated with the considered train (the relevant decisions are carried out by the generator of pseudorandom numbers conforming to the uniform probability distribution). o The delay value which is obtained from the generator corresponding to the exponential probability distribution. • Warming up period of each simulation run (applied before collecting data items for relevant statistical analysis) takes 2 hours of simulation time. • Scenarios/experiments are focused on different traffic parameterisations. There are carried out 6 simulation experiments (i.e. 6 different scenarios: Sc00, Sc01, Sc02, Sc03, Sc04a, Sc04b). Scenario Sc00 corresponds to simulation exploiting static priority lists only. Other scenarios combine utilization of both strategies: static priority lists and also dynamic multicriterial evaluations of variants. Table 1 describes parameterizations in detail. • Replications of one simulation experiment are always identically parameterized except of the seeds of pseudorandom number generators which differs from each other. There are calculated 200 replications for each scenario/experiment. • Traffic optimisation criterion corresponds to minimisation of total average increment of train delay within observed railway node. 3.4 Elaborations of Outcomes Produced by Simulation Experiments The results of simulation experiments (executed in the environment of the tool Villon) applying different scenarios are summarized below. For each scenario several characteristics are calculated and presented in the Table 1: Table 1: Results of simulation experiments Sc00 Sc01 Sc02 Sc03 Sc04a Sc04b 1 PL exclusively or MCEV ∧ PL – weights: ( 𝑤 𝐴 , 𝑤 𝐵 , 𝑤 𝐶 , 𝑤 𝐷 ) PL only (43,43,10,4) (33,33,9,25) (10,8,68,5) (4,4,69,23) (4,4,69,23) 2 Number of replications 200 200 200 200 200 200 3 Number of trains where: MCEV reached better or the same results as PL – 4675 5087 4555 4759 4265 4 Total number of simul. trains 5800 5800 5800 5800 5800 5800 5 Trains from the 3rd row as a percentage of all trains – 80 . 6 % 87 . 7 % 78 . 5 % 82 . 1 % 73 . 5 % 6 The average decreases of train delay increments (for the trains from the 3rd row) – 56.2 s 54.9 s 55.1 s 58.2 s 49.2 s 7 𝟗𝟓 % confidence intervals (the half widths) of the arithmetic means from the 6th row – 7.4 s 9.0 s 7.0 s 8.0 s 6.2 s The structure and contents of the presented table can be commented as follows: (Row 1) Applied optimization strategy. The exclusive utilization of static priority lists (PL) is associated with the scenario Sc00. The exploitation of static priority lists as well as dynamic multicriterial evaluations of variants (MCEV) is applied in scenarios Sc01, Sc02, Sc03, Sc04a and Sc04b (the better solution from both approaches is taken for continuing simulation run). The vector of utilized weights of individual criterions is specified for MCEV. The weights employed in scenario Sc01, Sc04a were determined on the basis of calculations using Saaty’s matrix. Further scenarios (Sc02 and Sc03) exploited the modified weight values which were set up by an expert after assessing selected operational situations occurred during simulation experiments. The difference between scenarios Sc04a and Sc04b is based on resetting D-criterion values (as mentioned in the subsection 2.5) related to platform tracks. M. Bazant et al. MENDEL — Soft Computing Journal, Volume 25, No.1, June 2019, Brno, Czech RepublicX 143 Figure 2: The part of the track layout of the station Lysá nad Labem Simulation-Based Rail Traffic Optimizations Applying Multicriterial Evaluations of Variants MENDEL — Soft Computing Journal, Volume 25, No.1, June 2019, Brno, Czech RepublicX 144 Figure 3: The timetable of rail traffic (peak hours: 8 a.m. – 10 a.m.) related to the station Lysá nad Labem M. Bazant et al. MENDEL — Soft Computing Journal, Volume 25, No.1, June 2019, Brno, Czech RepublicX 145 The scenario Sc04b operated with the increased D-criterion values for the most technologically advantageous platform tracks (from the viewpoint of minimal blocking of reception switches section) and with the decreased relevant values for less suitable tracks. (Row 2) Number of replications carried out for the given scenario. (Row 3) The sum of arriving trains (demanding assignments of platform tracks), where MCEV method reached better or the same results as PL method. The “better result” means that the total increment of train delays achieved by MCEV reached lower value than result attained by PL. (Row 4) The total number of simulated trains within all executed replications. (Row 5) The amount of trains from the 3rd row expressed as a percentage of all trains. (Row 6) The average decrease of train delay increments specified in the 3rd row. That decrease is caused by taking more efficient decisions (regarding assignments of platform track) based on MCEV method instead of PL method. The statistical elaboration filtered out the cases which correspond to equal results of MCEV and PL methods. (Row 7) The accuracy of the mean from the 6th row presented by a half width of 95 % confidence interval (of the arithmetic mean). Presented results are namely focused on quantifications of the trains, which are connected with better results achieved by MCEV method versus results reached by PL method. The quality of results is measured by the above-mentioned optimisation criterion. 4 Conclusions and Perspectives The current testing of simulation-based rail traffic optimisations within railway stations brings quite encouraging results for further research. It was tested the dynamic optimisation method MCEV – multicriterial evaluation of variants. That method was focused on selecting platform tracks for the trains approaching an investigated station. The dynamic method of MCEV – in comparison with static priority list (PL method), currently applied in several commercial simulation tools, reached better results on average in 80 percent of cases occurred in simulation experiments. The further research will pay attention to (i) experimental modifications of the weights of criterions and (ii) potential involvement of PL method into criterion D belonging to MCEV method. Acknowledgement: The research presented within this contribution was supported from ERDF/ESF project: “Cooperation in Applied Research between the University of Pardubice and companies, in the Field of Positioning, Detection and Simulation Technology for Transport Systems (PosiTrans)” – No. CZ.02.1.01/0.0/0.0/17_049/0008394. References [1] Bazant, M. and Kavicka, A. 2009. Artificial neural network as a support of platform track assignment within simulation models reflecting passenger railway stations. Journal of Rail and Rapid Transit 223, 5, 505–515. DOI: 10.1243/09544097JRRT268 [2] Janosikova, L., Kavicka, A., and Bazant, M. 2014. Optimal operation scheduling and platform track assignment in a passenger railway station. Journal of Rail and Rapid Transit 228, 3, 271–284. DOI: 10.1177/0954409712472275 [3] Chakroborty, P. and Vikram, D. 2008. Optimum assignment of trains to platforms under partial schedule compliance. Transportation Research Part B: Methodological 42, 2, 169–184. DOI: 10.1016/j.trb.2007.07.003 [4] Diviš, R. and Kavicka, A. 2018. Complex nested simulations within simulators reflecting railway traffic. In: Y. Merkuryev, M. A. Piera, F. Longo, A.G. Bruzzone, M. Affenzeller, E. Jimenez (ed.) Proceedings of the 30th European Modeling and Simulation Symposium – EMSS 2018. University of Genova, Dime University of Genova, Genova, 178–186. [5] Corman F., D’Ariano, A., Pranzo, M., and Hansen, I. 2011. Effectiveness of dynamic reordering and rerouting of trains in a complicated and densely occupied station area. Transportation Planning and Technology 34, 4, 341–362. DOI: 10.1080/03081060.2011.577152 [6] Ishizaka, A. and Nemery, P. 2013. Multi-criteria decision analysis: methods and software. Wiley, Chichester, West Sussex, United Kingdom. [7] Fiala, P., Manas, M., and Jablonsky, J. 1994. Multicriteria decision-making. University of Economics, Prague [in Czech]. [8] Adamko, N. and Klima, V. 2018. Optimisation of railway terminal design and operations using Villon generic simulation model. Transport 23, 4, 335–340. DOI: 10.3846/1648-4142.2008.23.335-340 Simulation-Based Rail Traffic Optimizations Applying Multicriterial Evaluations of Variants MENDEL — Soft Computing Journal, Volume 25, No.1, June 2019, Brno, Czech RepublicX 146