The International Simutrans Forum

 

Author Topic: [Bug] Journey times sometimes calculated incorrectly on non-linear routes  (Read 4037 times)

0 Members and 1 Guest are viewing this topic.

Offline Carl

  • Devotee
  • *
  • Posts: 1600
    • Website
  • Languages: EN
This is demonstrated in the following savegame:
http://www.mediafire.com/?3yim5ip187ocfn3
(pak folder included; apologies that it's the huge map, but this bug does not seem to appear reliably in isolation.)


Check out Gravesend. One linethat serves this station is non-linear, in the sense that it travels the following route:

London ->Gravesend-> London-> (Gravesend)-> Gillingham-> (Gravesend)-> London

So it visits Gravesend on both parts of its route. However, presumably because of this, some of the journey times from Gravesend to stations on the slower route into London are mistaken. In the stop detail dialog you can see that times to Northfleet, Stone Crossing and stations via Sidcup are all over one hour -- when it can be observed that these journeys are made in a few minutes. These are all  stations which only feature on *one* of the routes into London from Gravesend on this line. At first I thought that these times were instead the time it takes to go (e.g.) Gravesend->London->Northfleet, but that doesn't seem to be right. One hypothesis is that the times give are the average of Gravesend->Northfleet times and Gravesend->London->Northfleet times, though -- but I can't confirm this. I've run the game for a few months to see if these times would shake out, but they instead seem to have all settled down between the 70-80 minute mark.

In fact, this also seems to affect stations which only occur on the other, faster route into London from Gravesend on this line too, e.g. Woolwich, Charlton and Blackheath have very similar (and inflated) journey times of 45-50 minutes.

Offline greenling

  • Lounger
  • *
  • Posts: 1728
  • Simutransarchology it my hobby!
  • Languages: DE,EN
Re: [Bug] Journey times sometimes calculated incorrectly on non-linear routes
« Reply #1 on: November 03, 2012, 09:33:45 AM »
Carl
It's possible that those bug came from overloaded Railwayline?
I can me remember that Simutrans Exp search a another way then the original line be overloaded it.

Offline Carl

  • Devotee
  • *
  • Posts: 1600
    • Website
  • Languages: EN
Re: [Bug] Journey times sometimes calculated incorrectly on non-linear routes
« Reply #2 on: November 03, 2012, 09:34:40 AM »
Hi greenling,

The routes in question aren't overloaded -- and at any rate, overloading tends to distort only waiting times, rather than journey times themselves.

Offline greenling

  • Lounger
  • *
  • Posts: 1728
  • Simutransarchology it my hobby!
  • Languages: DE,EN
Re: [Bug] Journey times sometimes calculated incorrectly on non-linear routes
« Reply #3 on: November 03, 2012, 09:53:34 AM »
Carl
Please make Photos and Videos from those Problems.
I must at 11:15 jump on a Job and i come from those at 16:00 back :o.

Offline Carl

  • Devotee
  • *
  • Posts: 1600
    • Website
  • Languages: EN
Re: [Bug] Journey times sometimes calculated incorrectly on non-linear routes
« Reply #4 on: November 03, 2012, 01:47:21 PM »
James -- if you're looking at that savegame, would you be kind enough to also check Dover Eastern Docks? Something strange has happened to that stop, with the name label going white and being accompanied by another "Unknown" label which seems to have taken over the stop. The white label can't be removed, and the "Unknown" label remains even if the stop is deleted. I've never seen this before, and I think it must be a bug of some kind.

Edit: It's possible that this is a corrupted ground label of the kind Kieron described here -- in which case the cause is the size of the map. If so, it would be good to be able to remove the label...

Offline greenling

  • Lounger
  • *
  • Posts: 1728
  • Simutransarchology it my hobby!
  • Languages: DE,EN
Re: [Bug] Journey times sometimes calculated incorrectly on non-linear routes
« Reply #5 on: November 03, 2012, 02:10:13 PM »
Carl
gives in the railwaynetwork often the info: "wait on free route" by the trains?

Offline Carl

  • Devotee
  • *
  • Posts: 1600
    • Website
  • Languages: EN
Re: [Bug] Journey times sometimes calculated incorrectly on non-linear routes
« Reply #6 on: November 03, 2012, 02:17:10 PM »
Greenling -- I've sent you a PM.

Offline Carl

  • Devotee
  • *
  • Posts: 1600
    • Website
  • Languages: EN
Re: [Bug] Journey times sometimes calculated incorrectly on non-linear routes
« Reply #7 on: November 03, 2012, 11:05:10 PM »
I've managed to reproduce the journey times bug in a simple savegame which mirrors the same line structure:

https://dl.dropbox.com/u/61716/nonlinearroutes.sve (pak128.britain.ex 0.8.4)

The eastern-most station is the place to look here. The travel time to the next few stops along (which are only served by the single line on one of its trips there) is around 30 minutes, despite observably only taking a few minutes. The non-linearity of the line (!) is obviously messing with the calculation somehow, though I can't quite see how just by observation.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: [Bug] Journey times sometimes calculated incorrectly on non-linear routes
« Reply #8 on: November 04, 2012, 12:41:25 AM »
Thank you very much for the saved game: that is most helpful.

I think that I have worked out what is going on in principle: how to solve it I am not yet sure. The way in which journey times are calculated is by recording departure times from stops and calculating the point-to-point journey times from each stop from which the convoy is recorded as having departed when the convoy arrives at each stop. Where a convoy departs from the same stop twice before arriving at another stop, the old departure data are simply overwritten with the new. On a simple route such as this:

A--B--C

The convoy will visit stop A, then B, then C. On arriving at C, the departure times from A and B will be logged and the journeys calculated. On returning from C to A, the departure times from C and B will be logged; when the convoy reverses direction and again passes through B, the previous departure time for B (when the convoy was going from C to A) will be over-written with the new, so that the shorter, B>C direct route timing is used.

However, in your map, you have a diagram in which trains will in some cases not over-write the wrong departure data before arriving because of their convoluted route: trains going via Haw Tor Woods heading for Harlingvale, for example, will record a departure from Haw Tor Road, but will not stop at Haw Tor Road on the return, so when the train arrives at Haw Tor Junction, it will record the journey time based on the last departure from Haw Tor Woods heading for Harlingville, rather than the last departure heading for Haw Tor Junction directly. It is equivalent in the simple example to:

A>B>C>B>A>C>A>B>C

in which the B>A journey time will be recorded via C because the convoy does not stop at B on the way back to update the departure data.

I have included specific algorithms to deal with circular routes and Y shaped routes, but I had not thought of this particular configuration. Any ideas as to how programatically to implement a means of handling this sort of route to get accurate/optimum timings would be appreciated. For reference, the code in question is to be found in void convoi_t::laden() in simconvoi.cc.

Offline Carl

  • Devotee
  • *
  • Posts: 1600
    • Website
  • Languages: EN
Re: [Bug] Journey times sometimes calculated incorrectly on non-linear routes
« Reply #9 on: November 04, 2012, 08:17:51 AM »
Thanks for looking at this, James, and for your clear explanation of the problem.

Here is my thought about the most logical way to fix this in principle -- the question is whether it can be implemented in practice.

Here is an analogy. Where two different lines both serve a route A-B, it does not matter if one of them travels a convoluted route between A and B: the journey time displayed at each station will correspond only to the travelling time of the faster line between the two stations. Ideally, this principle should be extended to different instances of A-B journeys on the same line: so that if a convoy travels from A-B twice in the course of its route, only the fastest of these two instances counts as A-B journey time.

In the savegame above, the line has two journeys from Haw Tor Jn to Haw Tor Road: referencing point numbers in the schedule window, these are 7-19 and 20-21. The game ideally needs to be able to differentiate between these and know that the journey time from Haw Tor Jn to Haw Tor Rd corresponds to the 20-21 journey, and that the 7-19 journey should be disregarded as it is slower. In sum, some way to separate and compare these two separate Jn-Road journeys is required.

It is possible that this solution could in itself also account for some of the other problematic cases which currently require their own algorithm.

Do let me know whether you think this kind of idea would be feasible. I will take a look at the code in simconvoi.cc, but this is an area I haven't looked at before, and I have no idea how one would go about implementing the above, so I think it would be safest to assume that I will be unsuccessful!
« Last Edit: November 04, 2012, 08:28:51 AM by Carl »

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: [Bug] Journey times sometimes calculated incorrectly on non-linear routes
« Reply #10 on: November 04, 2012, 11:21:30 AM »
Hmm, I had considered something like this, but I think that the results that it would produce are too optimistic: variations between different timings might well be caused by varying traffic conditions rather than by taking a different route, and where differences are caused by varying traffic conditions, an average ought be taken, as is presently the case. There needs to be a way of distinguishing between the two, I think.

Offline greenling

  • Lounger
  • *
  • Posts: 1728
  • Simutransarchology it my hobby!
  • Languages: DE,EN
Re: [Bug] Journey times sometimes calculated incorrectly on non-linear routes
« Reply #11 on: November 04, 2012, 11:25:04 AM »
I Think that waiting time for clear routes train let exchanges her route.

Offline Carl

  • Devotee
  • *
  • Posts: 1600
    • Website
  • Languages: EN
Re: [Bug] Journey times sometimes calculated incorrectly on non-linear routes
« Reply #12 on: November 04, 2012, 11:48:23 AM »
Hmm, I had considered something like this, but I think that the results that it would produce are too optimistic: variations between different timings might well be caused by varying traffic conditions rather than by taking a different route, and where differences are caused by varying traffic conditions, an average ought be taken, as is presently the case. There needs to be a way of distinguishing between the two, I think.

This may be a small cost, but I don't think that it is a large enough drawback to undermine the considerable utility of the solution under discussion here.

First, a clarification: I'm not suggesting that we only take the fastest *single* journey posted from A-B to determine the journey time, but rather that the average of the fastest *set* of times (i.e. in the above example, the average of point 20-point 21 trips in the schedule rather than point 7-point 19 trips) to determine the journey time. This already accounts for some deviation due to varying traffic.

Beyond this, odd cases would only come up where there are two separate A-B route on the same line, and both have similar journey times. In these cases, I would appeal to the analogy drawn in my previous post again. If multiple lines make the A-B trip, only the fastest of these determines the displayed journey time from A-B, and no consideration is given to whether these times differ only due to traffic levels. A single line which has more than one A-B trip in its route is effectively an amalgamation of multiple routes, and so it should not behave differently in this regard -- there should not be a distinction without a difference. As such, the fastest of the multiple sets of A-B journey times posted by that line should represent the displayed A-B journey time.

Even so, the problem could be alleviated, if one wished, by adding an extra step into the calculation. Where a single line makes the A-B journey more than once in its route, one could ask the program to compare the two sets of journey times, and then merge them all into a single set if they fall within a certain margin of each other (i.e. 10-20%?). This would account for differences which result from differing traffic levels, or just from routes between A and B which only differ slightly. If the difference is greater than this margin, only the fastest set of times will be taken to determine the A-B journey time. Deviations based on traffic levels which fall outside this tolerance level should not, arguably, drag down journey times anyway.
« Last Edit: November 08, 2012, 02:24:15 PM by Carl »

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: [Bug] Journey times sometimes calculated incorrectly on non-linear routes
« Reply #13 on: November 09, 2012, 10:58:56 AM »
Hmm - this is a very complicated area. I shall have to give full consideration to this area once I have finished fixing some of the other bugs, I think. In the meantime - may I ask for clarification as to what you mean by,

Quote
(i.e. in the above example, the average of point 20-point 21 trips in the schedule rather than point 7-point 19 trips)

I am a little confused, I am afraid.

Offline Carl

  • Devotee
  • *
  • Posts: 1600
    • Website
  • Languages: EN
Re: [Bug] Journey times sometimes calculated incorrectly on non-linear routes
« Reply #14 on: November 09, 2012, 11:04:21 AM »
Yes, apologies, I could have been clearer there. In the savegame, the numbers (7, 19, 20, 21) refer to the line numbers in the list of stops in the schedule window. So both 7 and 20 are Haw Tor Jn, and Both 19 and 21 are Haw Tor Rd.  As such, "7 to 19" and "20 to 21" represent the two distinct journies from Haw Tor Jn to Haw Tor Rd contained within the single route.

Thank you for looking into this -- I certainly appreciate that it is a tricky area.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: [Bug] Journey times sometimes calculated incorrectly on non-linear routes
« Reply #15 on: December 10, 2012, 11:13:45 AM »
I have not had much chance to look into this particular area recently, but I have thought of a possible interim workaround that might be of some assistance here. If a line/convoy attempts to book a journey time that is more than x% (suggestions on what x should be are more than welcome) or less than 1/x% of the existing journey time average and that line/convoy has the place at which it is stopping more than once in its timetable manually (i.e., more than one actual entries, not more than one call due to reversing), then the higher journey time should be ignored/cleared and replaced with the lower journey time, as appropriate, on the basis that, when those two conditions are met, it is a fair assumption that the reason for the discrepancy is a non-standard calling pattern.

Any thoughts on this proposed workaround?

Offline Carl

  • Devotee
  • *
  • Posts: 1600
    • Website
  • Languages: EN
Re: [Bug] Journey times sometimes calculated incorrectly on non-linear routes
« Reply #16 on: December 10, 2012, 11:19:29 AM »
That sounds like a potentially useful solution. One question: would this only work in the second month of a line's operation, i.e. after an incorrect average time had already been posted at the beginning of the month? If so, the equations (1/x% etc) would need to take account of the fact that we may be dealing with an errant average of high and low times rather than merely a particularly high time.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: [Bug] Journey times sometimes calculated incorrectly on non-linear routes
« Reply #17 on: December 10, 2012, 11:32:42 AM »
Hmm - the number of months for which a line has been operating is not stored, so this cannot be confined to the second and subsequent months of a line's operation. The idea of the percentages is to ensure that only values a long way out of the range that one would usually expect for natural fluctuations would be recorded, although this system is a somewhat approximate one, and therefore might register a false positive if there was a long hold-up at a specific point, for example. It should average out over time, however.

Any thoughts on what the value x should be?

Offline Carl

  • Devotee
  • *
  • Posts: 1600
    • Website
  • Languages: EN
Re: [Bug] Journey times sometimes calculated incorrectly on non-linear routes
« Reply #18 on: December 10, 2012, 11:35:45 AM »
I'll give some thought to the value of x and will go back to look at how it applies to the specific example in the map above.

With the right value, it sounds like this could indeed lead to the relevant problems shaking out within a month or two -- which would certainly be progress.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: [Bug] Journey times sometimes calculated incorrectly on non-linear routes
« Reply #19 on: December 10, 2012, 07:20:35 PM »
Thank you - that is helpful. I know that the solution proposed could be improved upon, but this will be much quicker to implement than a more comprehensive alternative, and so such a compromise is probably necessary at present given the rather large queue of things waiting to be done.

Do let me know when you have a suggested value for x!

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: [Bug] Journey times sometimes calculated incorrectly on non-linear routes
« Reply #20 on: December 11, 2012, 01:57:25 AM »
I have pushed a fix for this to my 10.x branch, where x = 2.0. I have done some brief testing with your saved game and it seems to do the trick. Would you be able to re-test to see whether you can reproduce these results? (I am right in remembering that you are able to compile from source, aren't I?)

Offline Carl

  • Devotee
  • *
  • Posts: 1600
    • Website
  • Languages: EN
Re: [Bug] Journey times sometimes calculated incorrectly on non-linear routes
« Reply #21 on: December 19, 2012, 09:06:46 AM »
Hi James,

I completely missed your last post -- sorry. I gather that this has been incorporated into a release now, so I'll do my best to test the change shortly. Many thanks for looking into this!

---

Edit: This does seem to alleviate the main problem -- many thanks for coming up with a solution to this difficult issue! I'll let you know if any need for refinements to the formula arises in further testing.
« Last Edit: December 19, 2012, 10:30:18 AM by Carl »

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: [Bug] Journey times sometimes calculated incorrectly on non-linear routes
« Reply #22 on: December 19, 2012, 11:19:45 AM »
Splendid - thank you very much for checking!