Using Decision Intelligence to Increase Productivity: The Conflict Resolver
Microscopic conflict analysis in medium-term planning with Viriato using MoD
An important goal of timetable planners working in the medium-term planning phase is to create timetables that are conflict-free or are perhaps nearly conflict-free. At this point in the planning process, although there is still a period ranging from perhaps five years to three years before operation, the basic state of the timetable structure is becoming clear and having confidence that the planned trains will work without structural delays from the base timetable is important.
When working on this time horizon, a typical workflow involves using a planning tool such as Viriato. This tool's basic planning premise is permissive, and the planner is free to create trains that meet the high-level output specifications of the train operators and the infrastructure managers' planning rules. At this point, the infrastructure details are firming up, and the planned volume of trains is becoming close to the final levels. It is then important to be able to test the created paths with a finer level of detail, and we have described our approach to this in articles about our Microscopy-on-Demand (“MoD”) service in previous annual reports. In summary, MoD is a method for testing macroscopically planned timetables in Viriato using an external microscopic tool, which can select the microscopic routes the train uses, compute the running times on this infrastructure, and test whether trains are conflict-free at the microscopic level. All of this occurs without the user leaving the Viriato planning view. Regardless of how well individual trains have been planned macroscopically, it is inevitable that there will be conflicts between trains which need to be handled before the plan can be delivered.
Increased productivity through automatic resolution of basic conflicts
When timetable planners are presented with a large set of these, a natural question is: can these conflicts be removed, or at least minimised, using the inherent flexibility that is in a timetable from the various reserve times that are added for operational, engineering or commercial purposes? By manipulating the location and magnitude of these reserve times, it is possible to eliminate many of these conflicts without changing the structure of the planned timetable. If this process can be automated, the bulk of these issues can be removed from the proposed timetable, leaving the planner to concentrate on the more difficult conflicts thus increasing their productivity. This leads to the focus of this article, the Conflict Resolver.
The Conflict Resolver is an approach to provide the user with a productivity tool to help them solve this problem. It builds on the MoD framework for bridging the meso-microscopic model gap, with previous research into decision support methods for elimination of conflicts and algorithmic improvements to reduce the number of calls needed to the expensive (in terms of time) microscopic services.
What's under the hood?
The principle of the Conflict Resolver is to select a corridor along which the user wishes to eliminate conflicts from their planned services. This may only be a portion of the whole network, and the user can work on this area knowing that the selected trains will be unaffected in other parts of the network. From the user’s perspective, using the Conflict Resolver is as simple as pressing a button from within the Viriato planning tool which starts the process. This apparent simplicity hides a complex mathematical process in the background.
The Viriato tool itself has no knowledge of the underlying microscopic infrastructure for the conflict evaluation step, and even if it did the block occupation times are still needed for the state of the trains that may have a conflict between them, and these have to be transformed into a mathematical model (assuming that solution isn’t going to be a brute force method within a microscopic tool itself). In principle, it would be possible to simulate the progress of each train through each signal block repeatedly to find the complete set of block occupation times that may occur when the train comes into conflict with other trains and their block occupation times, and then undertake the conflict resolution portion of the task. However, it is immediately clear that with the large possible degrees of freedom for each train, this pre-calculation task would balloon into a step with a potentially very long running time. However, the design principles of railway infrastructure and train dynamics here provide a method for unlocking a good approximation of the block reservation and release times which can be used by us to generate a model. It has been observed that in practice, due to the dimensioning of signal blocks, and the relatively small changes to running times using realistic planning reserve times, the release and reservation times change approximately linearly with these times. This means that with a small number of calls to the microscopic tool, typically four per train run, each using different planning reserve times a linear regression provides a statistically good model of the relationship. With this model of the relationship between the signalling system and the train's times, we can construct a mathematical model where the trains can be retimed and rerouted while maintaining the essential structure of the overall timings, using only the redistribution of the various reserve times available and local rerouting within stations. A series of mixed integer linear programs (“MILP”) are constructed and passed to a commercial mathematic solver, in this case Gurobi. This solver attempts to minimise the conflicts between trains, represented by overlapping signal block times that were approximated using the linear regression earlier, and given that there is sufficient capacity available will be able to eliminate the conflicts. As with any railway question, there are always a set of additional constraints that can be very domain-specific, for example there may be rules about how many seconds of the minimum amount of reserve times must be kept between any two nodes and which are not available to the mathematical model for conflict resolution, or other operation rules which are not immediately obvious to the naïve observer. Once the solver has found its solution, this is passed back to the user who then has a set of updated trains, which when tested in the microscopic simulation via MoD will have many of the smaller conflicts eliminated, and potentially the large conflicts reduced. This offers a major productivity increase, recalling that the users themselves never left the macroscopic Viriato planning world, even though they constructed a microscopic approximation model, solved it, and then validated it in a microscopic tool.
From research to practical applications
As with all projects of this character, the important thing is to test it in action against real-world problems and data configurations. This method has grown from several academic research projects, including in a paper published at the ICROMA conference “RailDresden” in collaboration with the TU Dresden, which were tested by SMA timetable planning experts and which showed the potential of the method, and is now undergoing an industrialisation phase where the algorithmic code and the methods are rewritten using standardised software engineering processes and SMA’s Algorithm Platform within Viriato to ensure that it is fit for purpose when used in normal projects. This includes the incorporation of additional insights and requirements being revealed in the real-world work of SMA consultant’s daily business, ensuring that it remains more than just an academic experiment and instead becomes software that has been tested in industrial practice.