The International Simutrans Forum

 

Author Topic: Path Explorer and Convoy recombination  (Read 2019 times)

0 Members and 1 Guest are viewing this topic.

Offline ACarlotti

  • *
  • Posts: 237
Path Explorer and Convoy recombination
« on: February 12, 2018, 09:46:18 PM »
From discussions elsewhere on the forum it seems that one of the bigger issues surrounding convoy recombination is in its relation to the path explorer. I have not yet seen presented a clear resolution of all of the relevant issues. So, regardless of my following suggestions, I think it would be helpful to have more discussion about the path explorer (and related code) will be modified to accommodate the addition of convoy recombination.

I have not yet been able to explore the existing code for loading and the path explorer in depth, but I think I have a good idea of the overall algorithm and its place in the code, even though I don't yet know the details of every feature of it. From that perspective, I would like to make some suggestions which will resolve some (as I see it) outstanding issues, and allow for more flexibility in the convoy recombination feature.

The proposal:
At the moment I believe routing is done using the Floyd-Warshall, with input given (very roughly) by the journey statistics per line or convoy, and waiting times at each stop for each journey leg from that stop.
To allow for the possibility of convoys recombining, I think that the following changes ought to be made:
  • As a preliminary, for a given convoy and stop, all the uncouple orders should precede all the coupling orders. This means that the number of possible pairs of incoming/outcoming schedules a vehicle could follow is linear in the number of schedules + (un)coupling orders. Without such a constraint, the number of possibilities could be quadratic (e.g. N convoys merge in to one 'superconvoy' and then split into a different N convoys, giving N2 possibilities.
  • Then, for each coupling/uncoupling crossing between schedules, we track and store how long it takes goods between arriving on one schedule and departing on the other. Whether or not the goods stayed in the same vehicle throughout is not relevant to this record; obviously if they do remain in the vehicle then this waiting time will probably be fairly low. There are subtleties here if passengers change to a different route to that originally planned, but these subtleties appear similar to those that already exist in calculating expected waiting times.
  • Incorporating this additional data into the routing algorithm may require an additional step in the computation before running Floyd-Warshall,
     but this is unlikely to be performance-critical, and can probably be added without changing those parts of the path explorer that do not already need changing.

Based on my understanding of ideas already expressed in this forum, I think the above idea compares in the following ways:
  • The main idea I have heard mentioned previously regarding modifying the path explorer is to treat convoy recombination as introducing additional parallel schedules. (E.g. convoys departing from A and B, merging at C, splitting at D and running to E and F are effectively input as 4 schedules from A/B to E/F). This, I think, could perform badly (in terms of running time) when running on particularly complicated combinations of schedules. I don't think 'cloning' the overlapping portions of schedules is a feasible way of handling recombination.
  • I have heard it said several times that there is a need to ensure that vehicles transferred through coupling/uncoupling events must always, in aggregate, be able to hold the same types of goods. This seems to me to be a difficult criteria to enforce, and one which actively hinders a freight network where some flows only need to be catered for occasionally (i.e. <1 vehicle per train). With my suggestion, such constraints would be unnecessary.
  • It is also unclear to me that any account had been made for schedules of differing frequencies being linked (even with vehicles being transferred every time). For example, consider a light locomotive transporting a few wagons at a time from a branch line, which are then combined into a longer but less frequent train running on the mailine. Again, this is handle automatically in my above suggestion.

I am aware that there is still some vagueness in my suggestions, but I think that arises either in areas where the existing algorithms can be reused (and I haven't yet learnt what those algorithms are), or where I have perhaps explained things poorly.

I intend to investigate the existing path explorer in detail in the future, along with its relation to the vehicle loading/unloading code, and hope to be able to make some improvements there (and maybe pin down some existing bugs too). I think I would be able to learn the relevant parts of the codebase and then implement my above suggestions within a month or two.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 17636
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Path Explorer and Convoy recombination
« Reply #1 on: February 12, 2018, 11:01:55 PM »
Thank you very much for this contribution. This issue is without a doubt the most difficult issue for convoy re-combination, and is one of the reasons that this feature has not been implemented before now. The solution upon which I had alighted originally, as you correctly surmise, is a parallel system in which each couple/uncouple operation would be deemed to create Y or X shaped schedules, each requiring independent computation. I had hoped that this would be feasible, and it might well be given the way in which the path explorer works as described more below, but I can see that it may well be sub-optimal.

A little background on the path explorer might assist (and my apologies if you already know this or have inferred this). This system does indeed use the Floyd-Warshall algorithm. It was written in circa 2010, not by me, but by a developer of considerably advanced talents compared to mine who went by the name of Knightly. I had previously developed a system based on Djekstra's algorithm, which worked to find the optimum path for passengers, mail and goods based on timings, but was horribly slow in comparison. The path explorer was written before a number of the features that are now important to Simutrans-Extended, such as passengers walking between stops, transfer time at stations, passenger and mail classes and multi-threading, and has had to be adapted each time that those (and possibly other) features were added. Knightly himself retired from all Simutrans development in around 2011/2012, and I have had to modify the path explorer myself to add the new features.

As you have probably inferred, the path explorer was originally designed to run in a single-threaded application by doing a fraction of its calculation every step, and saving its state to wait for the next calculation. Other than when the game first loads, and the path exploring is done all at once, the path explorer thus works incrementally to update the paths without impacting on responsiveness. As a result of this, the path explorer algorithm having to process more routes will not make the game any less responsive to user input or have a slower framerate, but it will mean that it takes longer for the paths to update (this was the consequence of adding the passenger and mail classes feature that quintripled the number of passenger routes and doubled the number of mail routes needing to be calculated in games running in Pak128.Britain-Ex).

Originally, the path explorer worked on the basis of calculating the actual time spent by the calculations on a user's local machine to work out how many computations that it should perform in a step. However, when the multi-player networking was introduced, Knightly amended the system so that, when the game is in network multi-player mode, it will instead use a fixed number of path explorer computations (I cannot remember how these are individuated). I increased this number recently to take account of better computer performance compared with that in 2010.

When I added multi-threading support in 2016, I did not change this basic way of working. Instead, I gave the path explorer a single thread and let it run concurrently with a lot of the processes (especially sync_step) that are critical to user responsiveness but do not do anything that could conflict with the path explorer running. In some cases, where there is a specific thing done during a sync_step that might conflict (e.g. a user action), the game at the point of the conflict calls stop_path_explorer(), which actually just waits until the path explorer has finished its current iteration (and thus will not start again until the main thread next calls step()) and continues on its way.

I hope that the above is helpful in your understanding of this important part of the code.

Returning to your proposal, I find this very interesting. Just one or two questions, if I may, to make sure that I have understood what you suggest.  Firstly, do I understand correctly that what you propose would, so far as the internal workings of the path explorer is concerned, be very similar algorithmically in the case of a dividing/combining convoy to passengers/mail/goods alighting at the stop where the split/combine takes place and boarding again after the split/combine? If so, this is a very interesting idea, and I can see that this could readily be more efficient if it can be made to work than what I had imagined.

Secondly, as to preventing coupling before uncoupling, how had you imagined this working in cases where players specify multiple consecutive stops at the same halt (which is currently not possible because the schedule editing algorithm will automatically delete the second stop, but which may need to be added as part of my current works)?

Thirdly, I note the reference to the possibility of not needing strictly to specify the type of cargo to be carried on each specific vehicle in the consist order. If your system could achieve this flexibility without cost, that would certainly be an advantage. As you probably know, I am currently working on the data structures for the schedule features, including the convoy re-combination. Do you think that that it would be better to remove the data member that specifies this in anticipation of this feature?

Finally, more generally, are there any other aspects of the data structures for consist orders that you think would need or benefit from adapting in order to fit your planned implementation of the interface between the path explorer and convoy re-combination? I should like to get the data structures written first so that the work on the user interface and multiple aspects of the logic that rely on those data structures can continue in parallel.

In any event, thank you again for your willingness to contribute on this issue: I am extremely grateful to have assistance on the single most difficult issue in relation to the current major project's features.

Incidentally, I should be very grateful if any contributions that you make in relation to this be made in a branch from the vehicle-management branch on Github.

Offline ACarlotti

  • *
  • Posts: 237
Re: Path Explorer and Convoy recombination
« Reply #2 on: February 13, 2018, 12:01:37 AM »
A little background on the path explorer might assist (and my apologies if you already know this or have inferred this).
...
I hope that the above is helpful in your understanding of this important part of the code.

I was aware of most of this (having encountered serveral of the relevant threads during an unrelated search of the forum). However, this is a helpful summary of the history. It also suggests that there may be room to optimise the path explorer to better incorporate the more recent changes (e.g. incorporating 5 passenger classes shouldn't need 5 times as much computation).

Quote
Returning to your proposal, I find this very interesting. Just one or two questions, if I may, to make sure that I have understood what you suggest.  Firstly, do I understand correctly that what you propose would, so far as the internal workings of the path explorer is concerned, be very similar algorithmically in the case of a dividing/combining convoy to passengers/mail/goods alighting at the stop where the split/combine takes place and boarding again after the split/combine? If so, this is a very interesting idea, and I can see that this could readily be more efficient if it can be made to work than what I had imagined.

That is indeed what I mean. I think I read a comment on an old thread indicating that per-connection waiting time was not implemented due to some combination of more storage requirements and more time to accummulate sufficient data; this proposal is effectively to add per-connection waiting time in a limited number of cases.

Quote
Secondly, as to preventing coupling before uncoupling, how had you imagined this working in cases where players specify multiple consecutive stops at the same halt (which is currently not possible because the schedule editing algorithm will automatically delete the second stop, but which may need to be added as part of my current works)?

I have not yet considered how this would be implemented, but it seems to be largely a UI problem. One possibility could to automatically reorder entries when closing the schedule window.

This restriction came to mind after spending a few days wondering how to deal with the issues of vehicles transferring between convoys multiple times at a single stop; the best way to deal with that seems to be to just disallow it.

Quote
Thirdly, I note the reference to the possibility of not needing strictly to specify the type of cargo to be carried on each specific vehicle in the consist order. If your system could achieve this flexibility without cost, that would certainly be an advantage. As you probably know, I am currently working on the data structures for the schedule features, including the convoy re-combination. Do you think that that it would be better to remove the data member that specifies this in anticipation of this feature?

If this is a data member to enforce this *regardless* of what a player specifies in a consist order, then I think it should be removed. (If it's removal will make it impossible or much harder to specify vehicles by cargo type, then that's another matter, but I don't think that's what you mean.)

An analogy to existing systems can also be made here - suppose you have a line which has separate passenger and mail convoys with one station set to wait for a full load. But mail never arrives at that station, so the mail convoys get stuck and never follow the full line schedule. I don't see any substantial difference in how routing should behave regarding that situation, and how it should behave regarding optional vehicles in consist orders.

Quote
Finally, more generally, are there any other aspects of the data structures for consist orders that you think would need or benefit from adapting in order to fit your planned implementation of the interface between the path explorer and convoy re-combination? I should like to get the data structures written first so that the work on the user interface and multiple aspects of the logic that rely on those data structures can continue in parallel.

I cannot think of any others right now, although I do not remember all the details of what has been written so far. However, I still support the idea (mentioned elsewhere) of being able to route (some) vehicles in a consist according to their contents, along with a flag (per vehicle, or maybe convoy or schedule entry) to indicate that vehicles should only carry loads sharing a common destination or transfer station. This received little comment when I mentioned it before, but perhaps your view of it changes in light of the above?

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 17636
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Path Explorer and Convoy recombination
« Reply #3 on: February 13, 2018, 01:25:41 AM »
I was aware of most of this (having encountered serveral of the relevant threads during an unrelated search of the forum). However, this is a helpful summary of the history. It also suggests that there may be room to optimise the path explorer to better incorporate the more recent changes (e.g. incorporating 5 passenger classes shouldn't need 5 times as much computation).

That is a most interesting idea. If you are able to do this, that would be most welcome.

Quote
That is indeed what I mean. I think I read a comment on an old thread indicating that per-connection waiting time was not implemented due to some combination of more storage requirements and more time to accummulate sufficient data; this proposal is effectively to add per-connection waiting time in a limited number of cases.

This is definitely interesting - if this were possible more widely, it would be possible more realistically to simulate the logistical consequences of having larger stations, allowing passengers/mail/goods to transfer more quickly between arrival and departure points that are closer inside the station than farther away - although this may introduce more complexities than are manageable.

Quote
I have not yet considered how this would be implemented, but it seems to be largely a UI problem. One possibility could to automatically reorder entries when closing the schedule window.

This restriction came to mind after spending a few days wondering how to deal with the issues of vehicles transferring between convoys multiple times at a single stop; the best way to deal with that seems to be to just disallow it.

Yes, I see. Ves - if you are reading this thread, have you any views on the UI aspect of this?

Quote
If this is a data member to enforce this *regardless* of what a player specifies in a consist order, then I think it should be removed. (If it's removal will make it impossible or much harder to specify vehicles by cargo type, then that's another matter, but I don't think that's what you mean.)

An analogy to existing systems can also be made here - suppose you have a line which has separate passenger and mail convoys with one station set to wait for a full load. But mail never arrives at that station, so the mail convoys get stuck and never follow the full line schedule. I don't see any substantial difference in how routing should behave regarding that situation, and how it should behave regarding optional vehicles in consist orders.

The idea was rather that the data member enforced what type of vehicle may be specified in other parts of the consist order; but the main reason for this was to enable my planned system of interaction with the path explorer to work properly. If your system does not require this, then removing it seems sensible.

Quote
I cannot think of any others right now, although I do not remember all the details of what has been written so far. However, I still support the idea (mentioned elsewhere) of being able to route (some) vehicles in a consist according to their contents, along with a flag (per vehicle, or maybe convoy or schedule entry) to indicate that vehicles should only carry loads sharing a common destination or transfer station. This received little comment when I mentioned it before, but perhaps your view of it changes in light of the above?

I did add data structures for the tags. Did I comment explicitly on routing by contents? I recall thinking that it was not practical, but that may have been in the light of my planned implementation of the path explorer interaction, and so this may need reconsideration if your implementation removes those practical limits.

Can you elaborate a little on how this feature would work? Suppose that we have a passenger line with a schedule as follows:

A > B > C > D > E > F > G > H [SPLIT]

First part after split J > K > L > M > N
Second part after split W > V > X > Y > Z

Presumably, when passengers board at A, any vehicle is suitable for travelling to B, C, D, E, F, G or H. Then, one set of vehicles is also suitable for J, K, L, M and N and another set for W, V, X, Y and Z. So, passengers need to know when boarding a vehicle whether (1) it matters what portion of the train that they are in; and (2), if it matters, whether they are in the right portion of the train.

Does your suggestion here mean that, if some passengers bound for N got on one carriage at A, no passengers for any destination/transfer other than N could board that same carriage, even if they were bound for B, C, D... K, L, M and could thus travel in the same carriage without difficulty? If so, this would be problematic in operation and would probably not be workable. If you mean something else, can you elaborate a little on what that something else might be?

In any event, thank you again for your assistance with this.

Offline ACarlotti

  • *
  • Posts: 237
Re: Path Explorer and Convoy recombination
« Reply #4 on: February 13, 2018, 04:46:49 PM »
This is definitely interesting - if this were possible more widely, it would be possible more realistically to simulate the logistical consequences of having larger stations, allowing passengers/mail/goods to transfer more quickly between arrival and departure points that are closer inside the station than farther away - although this may introduce more complexities than are manageable.

I can't presently see how that would work, as with choose signals it is possible for specific convoys to arrive or depart from anywhere in a station. More realistic transfer times may be possble, however, so this is something I will try to keep in mind.

Quote
I did add data structures for the tags. Did I comment explicitly on routing by contents? I recall thinking that it was not practical, but that may have been in the light of my planned implementation of the path explorer interaction, and so this may need reconsideration if your implementation removes those practical limits.

Can you elaborate a little on how this feature would work? Suppose that we have a passenger line with a schedule as follows:

A > B > C > D > E > F > G > H [SPLIT]

First part after split J > K > L > M > N
Second part after split W > V > X > Y > Z

Presumably, when passengers board at A, any vehicle is suitable for travelling to B, C, D, E, F, G or H. Then, one set of vehicles is also suitable for J, K, L, M and N and another set for W, V, X, Y and Z. So, passengers need to know when boarding a vehicle whether (1) it matters what portion of the train that they are in; and (2), if it matters, whether they are in the right portion of the train.

Does your suggestion here mean that, if some passengers bound for N got on one carriage at A, no passengers for any destination/transfer other than N could board that same carriage, even if they were bound for B, C, D... K, L, M and could thus travel in the same carriage without difficulty? If so, this would be problematic in operation and would probably not be workable. If you mean something else, can you elaborate a little on what that something else might be?

To clarify, I imagine routing according to contents being used solely for freight, and not for passengers. So when loading freight wagons, you ensure that the entire contents of a wagon is going to the same transfer point (being on one of the possible schedules for vehicles in a given convoy). Then at the uncoupling point, the portion that the vehicle ends up in is determined according to its contents. So this is taking the approach of "load it up, and then work out which way it's going when it reaches the divide point", and matches how small amounts of freight are typically moved by rail.

An alternative approach, which would be more realistic for passengers, is "work out which way it will go, and then load up accordingly". It is not yet clear to me whether such an approach is feasible for an entire journey, but it should be possible to work out which schedule each vehicle will end up until the first uncouple order following a future coupling order. With uncoupling always preceding coupling at a given stop, this is likely to allow accurate prediction for most realistic schedules (at least in the absence of routing by contents).

In both these cases unloading and reloading goods at the dividing point is always available as a last resort, if things go wrong or the loads are unbalanced. A simpler algorithm would apply a fudge of shuffling stuff internally, or defaulting to unloading/reloading; however I think it is feasible and helpful to avoid those fudges where we can. I suppose the main complication in the above is what happens the "route by loading" and "load by routing" schemes collide; I shall have to consider this further.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 17636
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Path Explorer and Convoy recombination
« Reply #5 on: February 14, 2018, 12:23:03 AM »
I can't presently see how that would work, as with choose signals it is possible for specific convoys to arrive or depart from anywhere in a station. More realistic transfer times may be possble, however, so this is something I will try to keep in mind.

Yes, I see the difficulty. We may have to leave that unless one of us or someone else thinks of a sensible solution to this. (One might possibly ignore the effect of choose signals, and assume that the convoy always arrives at its intended point; that would at least then give an approximation of transfer times, especially if, for example, one has a station with four platforms attached to a huge airport).

Quote
To clarify, I imagine routing according to contents being used solely for freight, and not for passengers. So when loading freight wagons, you ensure that the entire contents of a wagon is going to the same transfer point (being on one of the possible schedules for vehicles in a given convoy). Then at the uncoupling point, the portion that the vehicle ends up in is determined according to its contents. So this is taking the approach of "load it up, and then work out which way it's going when it reaches the divide point", and matches how small amounts of freight are typically moved by rail.

An alternative approach, which would be more realistic for passengers, is "work out which way it will go, and then load up accordingly". It is not yet clear to me whether such an approach is feasible for an entire journey, but it should be possible to work out which schedule each vehicle will end up until the first uncouple order following a future coupling order. With uncoupling always preceding coupling at a given stop, this is likely to allow accurate prediction for most realistic schedules (at least in the absence of routing by contents).

In both these cases unloading and reloading goods at the dividing point is always available as a last resort, if things go wrong or the loads are unbalanced. A simpler algorithm would apply a fudge of shuffling stuff internally, or defaulting to unloading/reloading; however I think it is feasible and helpful to avoid those fudges where we can. I suppose the main complication in the above is what happens the "route by loading" and "load by routing" schemes collide; I shall have to consider this further.

Thank you for your thoughts on this. I can see that what you suggest makes more sense for freight than passengers (to have realistic freight loading/unloading, we are going to have to increase drastically the wagon loading times, I think, at least for the older types of wagons loaded by hand, so that the player has to use the convoy re-combination features to run an efficient service (i.e., loading taking much longer than shunting); if anyone has any data on freight loading times of old railway goods wagons, that would be much appreciated). However, a player might in principle use piece goods wagons in a similar way to passengers (think of a newspaper van, for instance), so this approach might still produce behaviour that players may find perplexing.

A system for loading wagons/carriages based on where they end up would be optimum, but the current plans for the convoy re-combination feature will not allow a simple determination of which specific vehicle will go to which specific portion, given that: (1) the vehicles to form each new portion are specified in consist orders; (2) the consist orders choose which vehicles to add on the basis of a list of various factors in order of priority; and (3) if there are any loose vehicles to be added, it is practically indeterministic (given that one would need to know where any other vehicle on the network is at any given time in the future to work this out) which other vehicles might be available for coupling in priority over those in the current train.

Offline Ves

  • Devotee
  • *
  • Posts: 1520
  • Languages: EN, SV, DK
Re: Path Explorer and Convoy recombination
« Reply #6 on: February 14, 2018, 11:54:21 PM »
Quote
I have not yet considered how this would be implemented, but it seems to be largely a UI problem. One possibility could to automatically reorder entries when closing the schedule window.

This restriction came to mind after spending a few days wondering how to deal with the issues of vehicles transferring between convoys multiple times at a single stop; the best way to deal with that seems to be to just disallow it.
Yes, I see. Ves - if you are reading this thread, have you any views on the UI aspect of this?
I had an idea of automating this process:

The player only ever select the stop once in the schedule, but extra stops is created automatically if the player chooses to make more consist orders, a button would be somwhere "add consist order" or similar which would be the actual trigger for the mechanism.
This way the player dont have to press multiple times on the map as wella as the game could have control of, say in which order the extra stops is made by reschedule it self if the player makes the coupling/uncoupling decisions in the wrong order.

The extra stops in the schedule could either be listed as normal, but could also be listed differently, so as to emphazise that it is the same stop the entries apply to.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 17636
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Path Explorer and Convoy recombination
« Reply #7 on: February 15, 2018, 09:33:06 PM »
Thank you for the suggestion. I am not sure whether this would be a workable way of doing it or not - I am wary of a UI that misrepresents what is actually happening in order in effect to fudge the fact that the underlying code does not behave differently.

ACarlotti - do you have any views on this?