News:

Want to praise Simutrans?
Your feedback is important for us ;D.

Improving Waiting Times [Patch]

Started by Carl, February 28, 2012, 10:08:24 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

Carl


In a nutshell: this patch (attached at the end of the post) reduces unwanted variation and increases accuracy in passenger waiting times, and so improves passenger routeing.


The route-finding system of Experimental has evolved into a really excellent set of features. However, I've been noticing recently that the weak link in this area is waiting times -- and that many common routeing problems can be traced back to problems with waiting times.

Here are four very closely related symptoms and diagnoses of these problems:

1. High variation between waiting times, even on a single line
There is often huge variation between waiting times at a one stop, even for convoys on the same line. I did some analysis and found that the waiting times for the destinations of one line at a terminus station had a coefficient of variation of 40%. That means that the typical waiting time was 40% away from the mean, and indicates very large variation -- especially when you'd expect the figures to all be broadly identical! Although you'd expect these differences to "iron themselves out" over time, my analysis suggests that they do not.

2. Passengers sometimes make bad connection decisions
This is partly a result of the above. Because of variation between waiting times on a single line, passengers try to make illogical connections. One example is as follows: On a line which goes A-B-C, passengers who wish to travel from A to C will sometimes try to change trains at B. That is, they will get off the train and then immediately get back onto the same train again. Why would they do this? Imagine that (A to B waiting time + B to C waiting time) < A to C waiting time, because of some anomaly. If this is the case, the routeing engine will tell passengers to change at B. These and other similar bad decisions can be observed on any well-developed network.

3. These Anomalies Perpetuate Themselves
Anomalies like the above will reinforce their own existence. If passengers regularly get off and then immediately back on a convoy at station B, many waiting times of zero minutes will be recorded for that stop --- so the waiting time will stay low (or get even lower), and passengers will continue to be routed via B on what should be a through service, ad infinitum.

4. Some waiting times are "obviously wrong"
This is a more general observation which cuts across the first three. For example, sometimes one looks at the waiting times for stops on a route with a half-hourly frequency, and sees that the average waiting time for one of the stops is just two minutes. This should not be right given the half-hourly frequency of the line -- and we should want to find and eliminate the source of such obvious anomalies.


So, what to do about this? I've been experimenting with various changes. This patch makes four main changes which reduce the above problems (though of course they do not solve everything!). I've listed them in descending order of importance (i.e. most important first).


Change 1. Store more waiting times.
I've increased the amount of waiting times for each connection from 16 to 32. It's a statistical platitude that increasing the amount of data will increase its accuracy, and this change does a huge amount of work in reducing the coefficient of variation discussed above to sensible levels. (I can provide data and savegames if anyone's interested). This has no noticeable performance hit.

Change 2. Don't register waiting times of under 1 minute.
I've inserted a condition that no waiting time of under 1 minute should be registered in the database. This is designed to stop anomalies perpetuating themselves: if someone gets off a train and then immediately boards it again, their waiting time of zero minutes will not count towards the waiting time for that connection. This should help to eliminate anomalies.

Change 3. Repeal the reduction of waiting times.
The existing code (as I understand it) reduces waiting times by 1/3 from their actual values. The rationale for this is that real-life transport networks have timetables, so we simulate the idea that connections would be more optimised than in fact they are. This is true, but I think this feature leads to passengers making more "bad decisions" than they otherwise would (see the "silly connections" problem above). Making passengers base their decisions on how a more optimised network should work -- rather than based on the actual features of the network before them -- is bound to lead to them making bad decisions. It's not clear what this feature adds to gameplay, since bad passenger decisions are frustrating for a network-builder. (Another point here: since many people run networks with much higher frequencies than real networks anyway (as demonstrated by the online game) it's not clear that waiting times need to be reduced from their often already-very-low levels.)

In testing, this change reduced the amount of passengers attempting illogical connections.

Change 4. Flush differently.
Currently, waiting times are flushed once they become stale. This is a necessary feature, because otherwise one-off high wait times will discourage travel over a connection indefinitely. However, the currently implementation has unwanted side-effects, since it artificially reduces any waiting time which has not been altered for over two months. This means that rarely-travelled connections (i.e. between two insignificant stops on a long route -- think Thetford to Widnes on the Norwich to Liverpool trains) will have their waiting times artificially reduced every few months, since the flushing process involves adding multiple entries of 1.9 minutes to the list of recorded waiting times. Eventually, some little-travelled connections have 2-minute waiting times. This contributes to the "obviously wrong" problem above, since these low times are often out-of-step with the line as a whole, and also leads to anomalies like those discussed above.

Now this is a tricky problem to solve completely, but I've taken the following initial steps. Firstly, I've increased the threshold for "staleness" from two months to four months. This should mean that fewer rarely-travelled connections will get their waiting times flushed. Secondly, I've changed the "flushing value" from 1.9 minutes to 10 minutes. This means that unusually high waiting times will still be gradually flushed out -- but also means that rarely-travelled connections will not see their waiting times reduced to the lowest possible values, but rather to a more sensible intermediate value.


Effects:
I've tested this patch extensively, and found it has the following effects:
-- Reduces variation between waiting times on a single line (coefficient of variation down from 40% to 19%)
-- Reduces illogical routeing decisions
-- Reduces anomalies

jamespetts

Carl,

thank you very much for your extensive work on this - it is much appreciated! I am very sorry that I have not had more time to integrate your previous patches to date - I have been working on merging the latest changes from Standard, which has been very time consuming: the new iterators are somewhat painstaking to implement, but probably important in avoiding memory corruption (which I think was their purpose). The plan is to update the -devel branch once the merge work has finished.

Your testing in particular is much appreciated and very useful. I had wondered before about whether it would be worth reversing the waiting time reduction feature as you have done in light of high frequency services and the ability of players now in effect to co-ordinate schedules as was not possible before.

Two small things in the interim: can you specifically test the memory consumption effects of your increase of waiting time storage on a very large map (such as that on the current online server)? I should be very grateful if you could run a test and post before and after memory consumption figures (leaving the game to run three or four game months after applying your patch to ensure that all halts are filled with data).

Secondly, would you be able to update the code comments to reflect your changes (such as the two/four months thing and the removal of the waiting time reduction)?

Thank you again for all your work on this.

It might well take me a week or two before I am able to get around to testing/integrating this; in the meantime, if anyone else has any comments on this set of new features and the proposed implementation, I should be very grateful.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Milko

Hello Carl

Quote from: carlbaker on February 28, 2012, 10:08:24 PM


3. These Anomalies Perpetuate Themselves
Anomalies like the above will reinforce their own existence. If passengers regularly get off and then immediately back on a convoy at station B, many waiting times of zero minutes will be recorded for that stop --- so the waiting time will stay low (or get even lower), and passengers will continue to be routed via B on what should be a through service, ad infinitum.


I remember (if my memory serves me correctly) that James had already noticed this problem, I also remember that James had already entered a waiting time of 5 minutes extra. I think your patch should (if you have not already done) to eliminate the 5 minutes added to James to get the correct result.

Giuseppe

Carl


Quote from: jamespetts on February 28, 2012, 10:46:47 PM
I am very sorry that I have not had more time to integrate your previous patches to date - I have been working on merging the latest changes from Standard, which has been very time consuming: the new iterators are somewhat painstaking to implement, but probably important in avoiding memory corruption (which I think was their purpose). The plan is to update the -devel branch once the merge work has finished.
No problem at all! I know those things take priority, and there's certainly no hurry! I thought that in the meantime I should get on with creating more work for you at the end of the bug-fixing tunnel  ;)

QuoteTwo small things in the interim: can you specifically test the memory consumption effects of your increase of waiting time storage on a very large map (such as that on the current online server)? I should be very grateful if you could run a test and post before and after memory consumption figures (leaving the game to run three or four game months after applying your patch to ensure that all halts are filled with data).

I've run two tests, one with the network save and one with a different (not quite so large) map.


With the network save running in 10.10 for 4 months, memory consumption was 687MB. With this patch applied, memory consumption was 691MB -- so a pretty negligible difference of 0.5%.

On the other save, four months in 10.10 led to a 287MB memory consumption, whereas four months with the patch applied led to 285MB memory consumption -- so actually a reduction in that case. I conclude that the effects on memory consumption are close to zero.

Quote
Secondly, would you be able to update the code comments to reflect your changes (such as the two/four months thing and the removal of the waiting time reduction)?

I've done this and attached a new version of the patch to this post.


Quote
Thank you again for all your work on this.

It might well take me a week or two before I am able to get around to testing/integrating this; in the meantime, if anyone else has any comments on this set of new features and the proposed implementation, I should be very grateful.
It's my pleasure! And, once again, no hurry on integration :)




Quote from: Milko on February 29, 2012, 08:50:41 AMHello Carl

I remember (if my memory serves me correctly) that James had already noticed this problem, I also remember that James had already entered a waiting time of 5 minutes extra. I think your patch should (if you have not already done) to eliminate the 5 minutes added to James to get the correct result.

Giuseppe

Hi Giuseppe,

The function you're thinking of has a subtly different effect to my code here. No average waiting time can be under two minutes -- and if the average value is under two minutes in the database then the game will replace it with a two-minute value. But this doesn't stop individual values of under two minutes being recorded in the database. So if there were ten times of five minutes and ten times of zero minutes registered, this would still average out at a 2.5-minute waiting time -- even given the two-minute minimum. But with my changes made, none of the zero-minute waiting times would be recorded at all (since those only arise in anomalous situations) and so the average waiting time would be five minutes in the case I described. I hope this makes sense!

omikron

I don't know if this is a real problem with this patch:

After playing several months, the anomalies start again, even stronger. As far as I can see, this is due to the stations recording a 'waiting time unknown' for some stops, which the passengers then prefer. Could this be a result of your patch, carl?

omikron

Carl

The only change in the patch which could increase the tendency for waiting times to be "unknown" is the "don't register waiting times of under 1 minute" change. If the only departures at a stop involve waiting times of under 1 minute, then no waiting times would be recorded for that stop. But that's a pretty extreme scenario, and I can't imagine that it would ever occur in a real game. So if the patch is genuinely increasing the tendency for waiting times to be unknown, then there may be a problem with the code of this second change. (For what it's worth, I haven't observed this in my own testing.)

Note that if a connection is being used -- so long as some of the waiting times are over 1 minute, as they should be for all connections -- then the connection should eventually display a waiting time, and therefore the anomaly should disappear. In theory, after a few months, things should iron out....

However, I have to admit to being rather confused as to how "waiting times unknown" works. With or without this patch, I see connections that are relatively regularly travelled but which nevertheless display "waiting times unknown". One would have thought that this would only be displayed if there were no waiting times in the database for the connection in question -- but this appears not to be the case.


Do you have a savegame I could look at?

omikron

You're welcome:

http://simutrans-germany.com/files/upload/Sebrim_4_-_1912b.sve

Have a look at Darworth Railway station: The passengers there seem to choose a place to interchange, even though there are more direct routes. Then at the start of every month, this interchange switches. From Eveford North in September, to Appleingford in October, until they all want to go via Rustbrook (the terminus of the three lines going through Darworth) in November.

omikron

jamespetts

Carl,

thank you for testing and updating your patch - very helpful! As to how "waiting time unknown" works - if there are no entries in the table, the waiting time will be deemed to be 1.9 minutes. If the actual average waiting time is less than 1.9 minutes, the waiting time will be deemed to be 1.9 minutes in any event. This gives a 1.9 minute minimum waiting time for stops, to simulate the fact that changing from one form of transport to another is always a time consuming affair.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Carl

#8

Having run that map for about 12 in-game months -- and analysed the lines around Darworth -- here are my findings. First, waiting times for all connections at Darworth were populated by November, so there doesn't seem to be a problem with "waiting times unknown". Second, as you say, passengers at Darworth eventually settle on travelling via Rustbrook -- even (for example) passengers for Curlden, which is in the other direction, and indeed has its own direct service.

The problems begin because there there are quite a lot of unhappy passengers at these stations -- and when a passenger leaves unhappy, they register 4x the time they actually waited, so this leads to very high waiting times. More frequent trains would help to alleviate some of these problems, since some of the intervals between trains seem to be around two hours at the moment, and such high waiting times can lead to unpredictable passenger behaviour. However, the savegame also reveals problems with the "flushing" mechanism in the code-- that is, the feature which ensures that large waiting times are reduced when they become stale.

The problem is as follows: many waiting times at Rustbrook stay much lower than they should be (and in many cases 10:00, the "flushing" value) even though those connections are regularly used. So either flushing is being activated when it should not be -- that is, data which is not stale is being replaced -- or something is going wrong with the recording of the real data. (Incidentally, these low times explain why everybody keeps going via Rustbrook).

However, since the only part of the "flushing" mechanism I've changed is the value which stale data is replaced with, I don't think this error can be just a result of my patch. Indeed, the same kind of thing seems to happen at Rustbrook to an even worse degree when I ran this savegame in 10.10 for comparison, suggesting that this problem is not specifically related to the patch.

So the upshot is that there are problems with the flushing system which are not fixed by my patch -- but the patch itself does not appear to have introduced any extra error into the system.

James -- if you get a chance, it may be worth you having a look at this problem in 10.10, since this seems to be independent of the patch.

jamespetts

Carl,

thank you very much for your analysis - that is most helpful! Further investigation will have to wait until I have integrated the latest changes from Standard into the code, but this does merit looking at in more detail.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Carl

#10
An updated version of the patch is attached to this message. Two changes:

A. The "1 minute threshold" ("change 2" in the OP) wasn't doing the required work in eliminating anomalies, so I've raised it to two minutes. One minute wasn't enough because if lots of passengers alight and then board again, the loading process may take over a minute -- and loading seems to count as part of waiting time. Of course, two minutes will still not be enough in cases where loading takes longer than this -- but I don't think that the threshold can be set higher without also discarding lots of legitimate waiting times. (If there were a way to simply ignore the waiting times of all pax who alight and immediately re-board, this would be cleaner, but I don't know if that's even possible).

B. I've changed the "flushing" system for stale waiting times. Adding times to the list was adding noise into the mix, so instead I've set the code to simply clear the waiting times for a connection when they are more than four months old. They will then display "waiting times unknown" until they are repopulated. This seems to be much cleaner. I've also reduced the staleness threshold from four months down to twp, since the increase was mainly motivated by the shortcomings of the old system.


This iteration has the cleanest performance yet on omikron's map -- although things are still rather chaotic at Rustbrook due to overcrowding etc, there aren't nearly so many anomalies now.


Note that I've had to manually update the old patch file in Notepad++ since I've been having problems with git. If you have trouble applying it, it should be easy enough to see the few lines that have changed since the last iteration.




Edit: I've also noticed that this patch makes the get_waiting_minutes() function redundant, since it now represents the same function as ticks_to_tenths_of_minutes().

jamespetts

I have now integrated this into my -devel branch, but have not had time to test it - any testing would be much appreciated! Apologies for not having done this sooner.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Carl

The tweaks to waiting times seem to be working exactly as I intended on the -devel branch. Whether that's what's required is, I suppose, for everyone else to judge :)

jamespetts

That's a good start - I'd be interested in feedback from any others as to how well that these refinements work in practice.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.