The International Simutrans Forum

 

Author Topic: re-routing  (Read 2890 times)

0 Members and 1 Guest are viewing this topic.

Offline asaphxiix

  • *
  • Posts: 723
re-routing
« on: December 15, 2012, 09:38:38 PM »
I know that for a new line, in the absence of travel time data, pax generation is determined using a default waiting time for time tolerance purposes, so it counts as if waiting time is very low (1-2 mins?).


current state - pax learn of a new "fast" train line with very small waiting times and drastically increase generation. quickly,one or more bottlenecks on the way is jammed by overcrowding, and waiting times soar. Dismayed, pax look for other ways to get to their destination, and start waiting in their masses for a bus line (often, the very same line in the same direction they were heading) to a close-by stop which has a small waiting time going from this stop  - where they will mass and try to advance to their destination(since waiting time are registered per connected stop, the 'via' stop can have very long wait while other stops on the same line register as very short). This often leads to pax going long trips in the opposite direction and everywhere on the map trying to get to their destination. Also, since they keep finding new unused routes to get there which have low waiting times - they continue to generate, at which point, the mess has gone out of hand and there is little hope to correct it without going all the way back to square one and starting again.

so the core of this issue is I think in the alternate route finding, but there is also a problem which I don't really understand well, that pax keep generating - even when the bottleneck is jammed and they need to go around the map to get to where they need to get. I'm guessing this is due to the problem discussed on the forum about time tolerance.

so if default waiting time would be high, pax wouldn't try immediately to travel to destination, but rather wait to hear for good service to be running throughout their trip, only then go. This, together with solving the alternate route (especially on the same line) and the time tolerance issues, and other measures discussed (more realistic travel distance proportions), could help mitigate the refund risks taken by fast expanding players, while still requiring consistently good through service  to work, and also allow for more realistic behavior of pax.



« Last Edit: December 16, 2012, 08:40:05 PM by asaphxiix »

Offline Carl

  • Devotee
  • *
  • Posts: 1574
    • Website
  • Languages: EN
Re: alternate route finding
« Reply #1 on: December 16, 2012, 09:24:29 AM »
Default waiting time is definitely one aspect here, but there is another which may contribute just as much. When a new line is built, the game "guesses" what the journey times on it will be -- I think by assuming that convoys will be averaging half of their maximum speed. In my experience this is overly optimistic in almost all cases, meaning that passengers think that a new line is faster than it actually is -- leading to overcrowding as a wide range of passengers incorporate the new line into their journey. This only settles down the following month once real journey times have been registered -- but by then the overcrowding has taken its toll and very high waiting times have been registered on this new line, too.

I would be in favour of making the initial estimate of journey time less optimistic. As far as I can see, there is nothing to be lost by erring on the slow side with these times -- it will not interfere with the network in the way that erring on the fast side does.

Offline greenling

  • Lounger
  • *
  • Posts: 1728
  • Simutransarchology it my hobby!
  • Languages: DE,EN
Re: alternate route finding
« Reply #2 on: December 16, 2012, 03:06:56 PM »
Hello
Do the alternate route finding consider the quantity of vehicles on a line?

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18619
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: alternate route finding
« Reply #3 on: December 16, 2012, 07:42:38 PM »
The ultimate problem here, I think, is the excess of passengers for what can sensibly be built in a given era, which needs to be addressed with the work on passenger/mail calibration. I looked into the issue that Carl described - I found that half maximum speed for a convoy was rather pessimistic rather than optimistic as a default. It could be changed to a third, but I don't think that this would help.

The trouble with making pessimistic assumptions about waiting time is that waiting time data are only created when people use a service. If the waiting time for a particular service really is two minutes, and it is that service frequency alone that makes the route faster than some competing route, passengers will never use the better service because they will always assume that the waiting times are higher, and the real waiting times will never be set.

Offline asaphxiix

  • *
  • Posts: 723
Re: alternate route finding
« Reply #4 on: December 16, 2012, 08:09:53 PM »
I fear I must disagree. On a general note, I think that the over-abundance of pax, while it is indeed problematic to play with and unrealistic - it is not the problem itself, but rather a window to show us some of the more serious underlying problems of pax routing in the game, by exacerbating them.

Perhaps for an experienced player in an advanced era, when creating an efficient network in a balanced game that doesn't have an excess of pax, these problems will not manifest - but even if pax numbers are balanced enough, less experienced players, and other various scenarios do require a logical routing system that can be learned and corrected using trial and error (or other methods). The current system does not really allow this, or only to a limited extent, in my mind.

As for default waiting time - that makes sense, of course, as a way to make pax use a new line - but maybe another way could be found, like setting more moderate waiting times, so pax will board the line, but not in masses...?

Also I should note again that the default waiting and travel time are only a slight part of the problem - the way I see it, alternate route finding and the fact that pax keep generating on busy lines are the core of the issue.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18619
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: alternate route finding
« Reply #5 on: December 16, 2012, 08:24:44 PM »
Hmm, I'm not sure what you mean by "alternate route finding" here. Do you mean the alternative destinations system? Passengers do not switch between possible destinations once they have been generated: they simply choose between one and X alternative destinations (where X is a figure between 0 and 7 that can be set in simuconf.tab) when they are first setting out. The passenger packet will generate, determine how many alternative destinations that it will generate, then try to see whether it can reach its primary destination within the journey time tolerance that it has been assigned. If it can, it goes to that destination. If it cannot, then it will see whether it can find a route to its secondary destination within its journey time tolerance, and so on until it exhausts its number of destinations, and, if it still cannot find a route, will record as "no route" or "too slow" as appropriate. Once passengers start their journey with one destination, they do not change destinations.

This is different to re-routing, which is an inherent and necessary part of the routing system (and is equally present in Standard, although the mechanics are slightly different there because of the different routing system). Re-routing occurs when the path tables are refreshed and passengers/goods waiting to go to a particular destination find that what is calculated to be the optimum route to that destination has changed, so the passengers/goods already en route switch to taking the new, better route.  If this were not done, then passengers/goods would for ever be stuck if the route that they were planning to use was withdrawn entirely. (The routing system does not seek to distinguish between non-existent and merely inferior routes because to do so would greatly increase the computational load on this CPU-intensive and performance critical part of the code).

What exactly do you mean when you refer to passengers keeping generating "on busy lines"? Passengers are generated at a constant rate, because how busy that lines are does not fundamentally change how many people ultimately want to go places. If a route is overcrowded, this will affect how long that it takes passengers to get where they are going; but this ought not prevent the passengers from going there at all, not least because this would create wild fluctuations between routes being overcrowded and deserted. Passengers do not generate "on" a line at all, but rather generate in town buildings, then see whether they can get to where they are going within their journey time tolerance, and, if they can, take the fastest route that will get them there. What change would you imagine could solve this issue?

As to the default waiting time, it is hard to see how a higher figure could avoid the problem that I outlined above, as a significant number of urban light rail services have two minute intervals.

Offline asaphxiix

  • *
  • Posts: 723
Re: alternate route finding
« Reply #6 on: December 16, 2012, 08:39:06 PM »
sorry for not being clear. I meant the re-routing system. I'm afraid I don't have answers here as to how to correct it, but I was pointing out a major problem with it.

I didn't mean it should be discarded of course - but I would attempt to change or work around it somehow to correct or mitigate this problem, other than reducing pax numbers. like I said at first, in the current (extreme) situation - you will find pax trying to get from Edinburgh to Glasgow trough London , when the direct line is too busy.


About busy lines - I mean that in the state described above (Edinburgh-London-Glasgow), pax will continue to tolerate it (that is, 'generate', find this bad route, and not be discarded as 'too slow'), and you will see more and more pax in and near Edinburgh wanting to go to Glasgow, even though they have to do it through London (or Exeter, or Moscow). My guess is that this is due to some problem with the time tolerance system, which I think you mentioned in some thread.

Also there's the problem I mentioned earlier with re-routing, that pax are re-routed on the same line to an intermediate stop - which of course makes no sense.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18619
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: re-routing
« Reply #7 on: December 16, 2012, 08:44:58 PM »
This may well indeed be related to the issue with journey time tolerances that I am presently looking into that results in far too high a proportion of passengers being generated with a high journey time tolerance of tens of hours. It might be best to see whether the fix for that problem fixes this issue.

Offline shi4stone

  • *
  • Posts: 18
Re: re-routing
« Reply #8 on: April 26, 2013, 11:55:00 AM »
I have some observation regarding this re-routing, or pax choose a 'better, quicker' route en mass and resulting some other lines completely un-utilized.
I admit I am not a very experienced player, and it took me a whole night-a frustrating night- to figure out why the following is happening:

Basically, I first connected two major city A and C, with a fast train line 1, then there is a smaller town B in between A and C. I connected it with a slower line 2 which goes A-B-C
At the beginning, everything was fine, pax in A and B would go to B via line 2. but after a while the waiting time for the trip A-B gets longer (which admittedly is partially due to the insufficient capacity of line 2), and suddenly all pax decided that it would be faster to reach B by taking the express train line 1 from A to C and then take line 2 from C to B!

This eventually lead to the disastrous congestion in station B and the waiting time for the trip  C to B sky rocketed.  and then everyone would change their mind an prefer to take a train from C to A and then A to B.

This phenomena would keep bouncing back and forth and leave line 2 only utilized up to 50%!! This is very unrealistic, because this under utilization of line 2 is caused  by the relatively high demand and insufficient capacity of that line!  In the end I have to set up very frequent and equally fast service on line 2 to somewhat levitate the situation. But it defeat the purpose of differentiating high speed express service and low speed regional services.

The problem I see here is the fact that all PAX behaves the same and all make the same decision at once. otherwise, some pax should hop on the slower line 2 whenever possible, and others who are impatient, could try to take a detour. I guess this s something related to the limits of the game engine. But to achieve the realistic simulation the game is aiming for, it is feels necessary to find a work around to differentiate the routing choices made by the pax going to the same destination. Or at least, not make routing decision purely based on speed. Instead the metric for decision making should based a utility function that combines both time and cost factors, e.g.

U =1/( a*Time+b*Cost)  where 'a' and 'b' are weighting parameters

I understand ticket pricing is out of the picture at this moment, but since we are already differentiating the revenue based on speed bonuses, can't we simply apply that bonouses as different cost? If the weighting factor are the same constant for all pax, then possibly this would not help to make PAX have multiple decisions, but it does make it possible for them to choose the slower but direct service and thus make the traffic more stable and realistic.

Offline Junna

  • Devotee
  • *
  • Posts: 1081
Re: re-routing
« Reply #9 on: April 26, 2013, 04:37:07 PM »
What version are you playing, shi4stone? I have had not much trouble with the re-routing pax in the latest RC's.

Offline shi4stone

  • *
  • Posts: 18
Re: re-routing
« Reply #10 on: April 26, 2013, 06:53:23 PM »
I was playing 10.27 with Brit-ex 0.84. but if the underline philosophy of the travel+waiting time based routing is not changed, wouldn't this kind of instable situation persist?

Offline Junna

  • Devotee
  • *
  • Posts: 1081
Re: re-routing
« Reply #11 on: April 26, 2013, 07:35:39 PM »
Newer releases change occasional pathfinding and there's also an additional transfer time to change at stations determined by the size of the station, as well as other fixes and changes. You should try it and see how it plays out for your travel patterns.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18619
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: re-routing
« Reply #12 on: April 27, 2013, 12:51:04 PM »
The behaviour of passengers when the waiting time is very high is not inherently unrealistic. Suppose that you were waiting at a railway station for a service from A to B, and the demand for the service so exceeded the supply that there was a three hour wait before you would be able to get onto the train; however, there was a train going to C where you could change to get back to B, and you could get on the next train to C, and you were aware that the waiting time to go from C to B was nothing like it was from A to B, and the journey from A to B took one hour, and from C to B half an hour - what would you do?

The real issue is that things get that crowded in the first place. Some work has already been done on this in the RCs, as Junna points out, including fixing a bug whereby journey time tolerances were disregarded for return journeys, which is capable of making a substantial difference. Further work is planned to ensure that the number of passengers generated is realistic.

It is not possible within reasonable limits of performance to have different passengers taking different routes, as the system works (in outline) by calculating in the abstract the best route to get from each place to each other place, and refreshing that calculation every so often. An agent based system (where each passenger calculates which route to take afresh) would not work within reasonable limits of performance.

Offline shi4stone

  • *
  • Posts: 18
Re: re-routing
« Reply #13 on: April 29, 2013, 01:16:22 PM »
Thanks for the explanation!! Tried the new RC, has not tried to intentionally recreate the same situation as mentioned earlier, but the no weird traffic pattern were noticed either.  8),
I could imagine an agent based simulation would be too demanding, but would it be possible to have just 2-3 social groups of PAX that has sufficiently distinguishing preference over time or cost? because that I guess would be enough to justify the existence of slower services, without needing an agent based system.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18619
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: re-routing
« Reply #14 on: April 29, 2013, 01:20:49 PM »
Very glad that the new version seems to be working for you.

Even having multiple social groups would require very significant changes to the code - and exactly how those groups be distinguished is not clear, especially if one is having a game covering 300 years.