crowdAI is shutting down - please read our blog post for more information
Optimizing train schedules
By SBB CFF FFS
over 1 year ago
I was wondering if there are shared route sections on different routes. For example in 01_dummy 18823 and 18825 have a route section with identical sequence number, resources and other properties. I don’t know if this is because they are the same route section or just because it is a dummy example. If the route sections can be shared between different routes what is property to asses that they are the same
over 1 year ago |
Yes, 18823 and 18825 are two trains from the same line, the latter is just half an hour later. They also use the same type of rolling stock (speed, weight, etc.) such that everything is identical apart from the times in the section_requirements in the service_intention. When the routes are exact duplicates, they could just as well be merged into one entry in the input data, both service_intentions referencing the same route.
We usually use one seperate route for each service_intention, because they are likely to have not exactly the same rolling stock properties and the minimum_running_times will vary from hour to hour.
Important is to avoid conflicting resource occupations. Those are the abstraction of the phyical track sections and switches which we use to model conflicts, i.e. to define whether route sections of two trains can be occupied simultaneously.
over 1 year ago |
Hi @kaspar, thank you for your reply. It answers my first question (if 2 route sections from different routes can be the same), but I am still not sure how I can determine that two route sections are the same.
Since the route ids are different and sequence_number is just a parameter to order the route sections in our algorithm each route section is treated as a unique one for the moment. Thus we need a criteria to identify which route sections are the same. If the route sections had ids, it would be the easiest way to handle this. However the input data should be modified for that. If such a modification is not planned could you please tell me what is the criteria to decide that the route sections are the same? Having the same set of resources?
What do you mean by ‘route sections are the same’? And what is the purpose of this eqality definition?
Note again that the conflict definition in the planning rules depends on the resource occupations in the route sections, and there it is resource.id which defines which resources are ‘the same’
If I go back to 01_dummy as an example, in our algorithm route sections 18823#1 and 18825#1 will be treated as 2 different route sections although they are the same, resulting in creating double the amount of variables than what is actually required.
So if two route sections are the same when they have the exact set of resources, we can just assign them the same id which will reduce the number of variables created. In theory this should reduce the solution time which is a problem for us for the moment.
For us, they are two different route sections, as they belong to different trains and as the entry/exit times in the solution will have to differ to fulfill each trains section requirements.
If you manage to reduce the search space by using properties like periodicity, equal routes, etc that can certainly be interesting to reduce computation time.
The definition of equality for route sections then depends on your approach and their detection will need to be implemented on your side.
Regarding periodicity, note however that there is no guarantee that the inputs are exactly periodic, there can be cargo and peak-hour passenger trains that do not follow the typical hourly pattern.