High waiting times can be permanent

[Carl]

I've discovered another routing anomaly that occurs in complex networks with respect to the "expected waiting time" value. As I understand it, this value is calculated by working out the average time which passengers who have travelled directly from A and B had to wait between turning up at the station and getting on a vehicle. This value is then used in route-calculation to work out the quickest way of getting from destination to destination.

However, this suffers from the following weakness: when an expected time becomes large, it will sometimes be impossible to get this value down again---no amount of making the network more efficient will change the value. For the longest time I couldn't work out why this was the case, but now I think I've figured it out. Let me explain.

The problem
Imagine that a train runs between A and B. Now imagine that there is temporary a problem somewhere on the line that causes congestion for a month or so (perhaps I messed up some signals, or something). Passengers at A are queueing up to get to B, and they are having to wait a long time -- let's say the expected wait time rises to 30 minutes. But now passengers at A will realise that, given this 30 minute wait time, they would be better off taking an alternative route---say, travelling to C and then changing to a B-bound train there. If A-to-B trains are subject to a 30-minute wait, then this alternative route might be quicker.

But if this happens, then as long as the A-C-B route doesn't suffer any of its problems, there will be no new data to work out the average waiting time for A-to-B services. (In order for the waiting time to decrease, the game needs to transport some people directly from A to B and log how long they had to wait at A.) So the waiting time will remain at 30 minutes forever---even once the network problem has been resolved. So nobody will ever travel directly from A to B again, because of a one-off isolated problem.

This anomaly makes it very difficult to make networks "recover" after a problem or a mistake on behalf of the player. The only way to resolve this in the current system is to erase a station altogether and build another in its place. This resets all waiting times to and from that station, but is a highly unsatisfactory solution.


Proposed solutions
I can think of two solutions:

-- Have all wait-time values reset themselves (i.e. return to "waiting time unknown") at a certain interval, say once a year or once every three months. Perhaps this is using a sledgehammer to crack a nut---but it would ensure that all values remain at least minimally accurate. And perpetual network issues will still be punished in this framework.

-- Alternatively: have all wait-time values above a certain level reset themselves at a certain interval---preferably a short interval. So every wait-time value over, say 15 minutes, should reset itself regularly to be sure that the value reflects a perpetual problem rather than simply a one-off problem. I have no idea whether this is possible, but it avoids some of the worries about the previous solution.


Any thoughts?

[Milko]

Hi

I have another idea (which weighs a little more computationally): I propose to associate to any "waiting time" the instant update. When the update time exceeds a certain threshold the "waiting time" is made unknown.

Giuseppe

[Carl]

So the idea is that any "waiting time" that hasn't updated for X period of time will automatically reset itself? If it's possible, that would definitely be better than the solutions I propose.

[megasycophant]

This issue makes Experimental all but unplayable when it comes to passenger networks. Rather than some arbitrary reset, though, I would think the real solution would be to calculate waiting and travel times regardless of whether a passenger is loaded (since it seems these are recalculated only when a passenger actually makes the journey). In other words, if a route goes from A -> B -> C -> D, its A to D travel and wait times would be recalculated regardless of whether any passengers traveled from A to D.

[Carl]

While that would be ideal, it seems that this would require a rewrite of the feature---at the moment the only way the game knows about waiting times is by averaging the waits of passengers who actually made the journey between A and D. Milko's suggested solution stays within this existing framework whilst also having the desired result of keeping the data up to date---and importantly, it's not an *arbitrary* reset.

[inkelyad]

Please test my fix. Github link. Here waiting time will eventually(10-15 min real-time) fade out to 9 'minutes'.

[Milko]

Hi

(Sorry for my bad English)

I'm looking at the modified code, I'm not very expert in C + +, but I do not know if the fade out to "9 minutes" is made for the waiting time of all possible routes or only those that are not used for some time.
Instead of 9 minutes would not be better to put "unknown time" so that simutrans worry to evaluate the waiting time of the route (as if the path was just released)?

10-15 minutes of real time means that even if I fast forward the game will still have to wait 15 minutes?

Giuseppe

[inkelyad]

I'm looking at the modified code, I'm not very expert in C + +, but I do not know if the fade out to "9 minutes" is made for the waiting time of all possible routes or only those that are not used for some time.

For used routes change will do almost nothing -- dummy waiting_times samples will be replaced with real one.

Instead of 9 minutes would not be better to put "unknown time" so that simutrans worry to evaluate the waiting time of the route

We have no timetables, so we can't use "there is train every 30min" as predicted waiting time. I can invent something, but I think it is unnecessary complicated.

10-15 minutes of real time means that even if I fast forward the game will still have to wait 15 minutes?

That I don't know. It depends on how often step() is called in fast-forward mode.

[Milko]

Hi

Sorry, but before I can not understand what makes the fix.
Correct me if I'm wrong.
For now, I understand that your changes set to 9 minutes waiting time for the paths not taken.
But I do not understand what you mean by "10-15 min real-time", it means that the waiting time of 10-15 minutes is equivalent to "not wait" or that the setting "9 minutes" occurs every 10-15 minutes of real time?

Giuseppe

[inkelyad]

Now average waiting time on station calculated from 16 samples -- real waiеng times from transported goods/passengers.
If there is no transported goods, my patch will replace all samples with 9 'min' in about 10-15 min real time ( 16 * 256 simutrans steps, step is about 170-250 ms).

[Milko]

Hi

Perfect, so it seems ok.

In the future I think will be better to provide a more robust system. The patch fixes the problem of refresh of the lines are not used but may add a new problem.
We have two lines of the "A" and "B": the "B" is refreshed with the waiting time of 9 minutes.
In conjunction with the setting at 9 minutes the line "B" will be better than "A", then the passengers will pass all on the line "A". After 15 minutes the line "A" (which at this point will not have multiple users) will be refreshed to 9 minutes (so all the passengers on the line "A"). You can thus create an intermittent flow of people moving from one line to another.
I still think that having 100% of people who choose the fastest line-only approach is not very fair.
As the calculation of the time taken in the absence of people is too much trouble, I was thinking of a way of routing that provide for the division of users on different lines, using a percentage split that favors the fastest routes to the detriment of the slowest.
Even in reality not all choose the shortest way, in Italy it is possible to travel from Milan to Rome by train (4 hours) or the plane (2 hours), not everyone uses the plane in fact some prefer the train even if slower.
By dividing the people we have people on the various lines on all possible routes and then be constantly updated waiting times.
AscoltaTrascrizione fonetica
Dizionario - Visualizza dizionario dettagliatoGoogle Traduttore per miei elementi quali:RicercheVideoEmailTelefonoChatAttivitàGiuseppe

[inkelyad]

I was thinking of a way of routing that provide for the division of users on different lines, using a percentage split that favors the fastest routes to the detriment of the slowest.

You want to calculate all possible paths for every <start stop, end stop, good category>? It is more or less impossible.

Edit:
Waiting time is not line property. It is stop property.
Here

Code Select Expand


A--B--C (line 1, direct connection A->C)
A  --- C (line 2, direct connection A->C)

there is only one waiting time(A->C) at stop A.

[Banksie_82]

How about a concept of "ghost passengers"

I have no idea about programming, so this may be quite fanciful, but...

Imagine there is another class of passenger, completely unseen by the player, takes no space on a convoy, no space in a station and has no weight (while in the convoy). The only thing they affect is the waiting time. There is one of these passengers wanting to go to every directly connected stop for which there are no real passengers, even starting/ending at stops that don't have a population catchment.

I think this would be resource friendly, as there is no complex routing and it ensures that there is always someone travelling and therefore calculating the waiting time. When this entity would appear, I don't know, perhaps randomly (like normal passengers) or at specified intervals.

I don't know, but this could take a lot of programming skill and time, the former of which I have none and the latter I have very little of.

[sdog]

banksie, you're playing simutrans now? any chance we'll get some good aditional artwork for pak britain soon

[Milko]

Hi

@Banksie_82

In this thread (http://forum.simutrans.com/index.php?topic=6227.0) you talk about how simutrans handles the routing, adding passengers even "ghost" no improvements could be expected because all passengers must go from "A" to "Z" made a series of subsequent choices at each station where stop. In practice there is a table (updated regularly) that combines the triple <"station where I am," "Final Destination Station", "goods type"> the next station at which to arrive. The problem is that the relationship between the triplet and the next station is 1 to 1, so if I'm in a station I have one and only one direction I can take independently that there are other possible ways. Passengers "ghost" then continue to pass on the same roads for "usual" passengers.
Change the relationship between the triplet and the next station from 1 - 1 to 1 - MANY, however, seems to have a high computational burden and cause a sharp slowdown in the game.

Giuseppe

[Banksie_82]

Sorry Milko, I think you might have misinterpreted what I was trying to say.

I only called them "ghost passengers" because I thought it sounded cool. What I had in mind was a thing, not a passenger, not mail, not a good, yet all three at the same time.

This thing would be completely unseen to the player. It would be able to travel on any convoy, regardless of type and if the convoy is full. It would be able to originate at any station, regardless of what is in the station's catchment, even if nothing is in the catchment. It will want to go to any station regardless of what is in the station's catchment, as long as it is directly connected to the starting stop.

Most importantly, it will only want to go to a "directly connected stop" for the station it is waiting/appeared at. Under no circumstances will it try to be smart and try to find a quicker route if it means changing convoy. It will get on the next convoy that will take it directly to its intended destination without a change. Programming wise, it would not even need to look at other possible routes. It just looks at all the lines that will take it directly to the destination, get on the next one and record the waiting time.

Hence, it ignores the table you describe in your post above.

But like I said, this may involve a lot of programming, I don't know. Also, I could have completely misunderstood what you were trying to tell me. In which case, I'm sorry for my ignorance.

[jamespetts]

I have now had the opportunity to work on a fix for this, building on the fix produced by Inkelyad here. The system will check whether any particular waiting time has not been updated for more than two months, and, if it has not, will gradually add very low waiting times to the list of waiting times each month, reducing the average, until, eventually, the waiting time is back to its minimum level again. Please note that this has required adding a parameter to the save game data, so anyone using the 9.x branch previously will not be able to load games saved with that version (unless one changes the save version to 8 before saving them).

[jamespetts]

The fix for this is now incorporated into 9.0. Thank you for the report and analysis!