The International Simutrans Forum

Development => Extension Requests => Topic started by: Dwachs on November 25, 2012, 07:19:59 PM

Title: Changes in routing of passengers
Post by: Dwachs on November 25, 2012, 07:19:59 PM
Please continue discussion here about changing routing of passengers.

Virtually split from here http://forum.simutrans.com/index.php?topic=10927.0

Quote from: Fifty on November 25, 2012, 04:16:48 PM
I have two suggestions in order to improve routing in Simutrans. I know these may be rather complex, but they would help gameplay quite a bit.
[...]
The second has to do with what the "better route" is. Currently, passengers and freight will first look for the route with the smallest number of transfers, and then if two routes have the same number of transfers, for the route with the shortest first leg. This makes non-circular passenger rail lines work rather poorly, as oftentimes passengers will choose a different route to their destination than they do home. Thus trains lines will be more heavily loaded in one direction than the other. I would suggest that if two routes have the same number of transfers, that pax/goods will take the one with a shorter total distance, and thus the same route in both directions.

Quote from: Fifty on November 25, 2012, 05:48:03 PM
[...]
It seems I'm confused about how routing works. Let's use a basic example: You have 2 tracks from A to E, one running A-C-E and the other A-B-D-E. A-B is shorter than A-C, E-C is shorter than E-B.

  /-B---D-\
A<          >E
  \-----C-/


Let's say that trains don't stop at D. How would passengers get from B to C? Would they take the same route back from C to B? Now what if trains do stop at D, how would pax get from B to C and back? How would pax get from A-E? would it matter if one route was shorter (fewer tiles)?

My biggest concern is that pax often do not take the same route to their destination as they do back, so it is difficult to balance flows with some setups.
Title: Re: Changes in routing of passengers
Post by: TurfIt on December 01, 2015, 10:27:24 PM
Finally got around to looking at this... Somewhat surprised at what was in the code; Not at all what was expected.

First, answering Fifty's three year old questions:
  From B to C: pax will either transfer at A or E; Whichever route is found first. Depends on internal order of the stations and lines in memory. Good chance of a save/reload changing which route is found first.
  From C to B: same answer. And this is not necessarily the same as the B to C route.
  After A-B-E train changed to A-B-D-E: All B to C and return C to B will transfer at A.
  From A to E: E is directly reachable from A with no transfer, pax will take whichever train arrives first to pick them up.
  Less tiles in the route makes no difference.


Quote from: Dwachs on November 25, 2012, 04:49:51 PM
Routing is now based on two facts:  Routes are chosen to have as less transfers as possible, while counting in-between halts.
From the code, I'd say the number of halts in a route is the determining factor, with a transfer counting as 8 halts. This is quite different from what I'd always thought where number of transfers was directly the determinant. It's quite easy to end up with pax taking a route with a transfer instead of a direct connection. But not easy to use this fact to control the chosen routes. And, it's almost inevitable to end up with ties which bring the asymmetric flows, and changes upon save/reload problem.
What is the rationale for using the number of halts?


Quote from: Fifty on November 25, 2012, 06:51:30 PM
Quote from: TurfIt on November 25, 2012, 06:11:22 PM
On my todo list is to try a hybrid approach -  number of hops with distance as a tie breaker. That way if there's two routes with the same number of hops, the one with the shortest distance will be prefered, but if there's a route with less hops, it will be taken even if longer. That should even the flows.
This is what I would very much like to see. Please feel free to split these topics, sorry for creating confusion!
Using transfer distance as a tie breaker was my original thought, but the code makes it trivially easy to use the cumulative distance between all halts on the schedule. I don't see a downside to this, so patch attached to do so.
The penalty for a transfer is set in the patch much higher than any route distance is likely to be. Is it preferred to maintain the current behaviour with low penalty? Meaning pax would select a route with a transfer if the direct route was too much longer. The penalty could be made configurable to cater both ways...
Any desire to optionally retain the current halt counting factor?
Or was the original idea to just use the transfer distance as a tie breaker better?
Title: Re: Changes in routing of passengers
Post by: Dwachs on December 02, 2015, 07:38:43 AM
I can't remember the discussion around this change. It was years ago, in the sourceforge forum.

Does your patch change anything in the routing? I mean, setting WEIGHT_WAIT to like 100 seems to be equivalent to your patch.
Title: Re: Changes in routing of passengers
Post by: TurfIt on December 02, 2015, 11:01:20 AM
WEIGHT_HALT becomes unused except for the binary heap heuristic.
replaced with distance in the actual connection weight calculation.
+// aggregate_weight += WEIGHT_HALT;
+ aggregate_weight += koord_distance( current_halt->get_basis_pos(), previous_halt_fpl->get_basis_pos() );
Title: Re: Changes in routing of passengers
Post by: TurfIt on December 10, 2015, 01:40:49 AM
So then, is everyone happy with the current routing mechanic? or with changing to use distance instead? You'd think there were be some opinions on routing with it being so fundamental to the game...
Title: Re: Changes in routing of passengers
Post by: Ters on December 10, 2015, 05:40:36 AM
I don't like the fact that there is no (stable) tie-breaker between routes with equal number of transfers in the current system. However, I haven't had the time to figure out what this patch does or how it might affect things.
Title: Re: Changes in routing of passengers
Post by: Dwachs on December 10, 2015, 07:46:15 AM
I am quite neutral against changing the routing to be distance based. I would like to hear other opinions, too.

Another idea would be to use estimates of travel time, based on distance and speed of assigned vehicles.
Title: Re: Changes in routing of passengers
Post by: Vladki on December 10, 2015, 07:59:11 AM
Counting stops would make sense, if pax would not take whatever convoy that takes them to their destination (next transfer). Preferring lines with less stops will improve usage of parallel express and commuter lines.
Title: Re: Changes in routing of passengers
Post by: Ters on December 10, 2015, 05:19:52 PM
Quote from: Dwachs on December 10, 2015, 07:46:15 AM
Another idea would be to use estimates of travel time, based on distance and speed of assigned vehicles.

It might perhaps be a bit non-intuitive, although logical in hindsight, that relatively minor changes to vehicles affect the routing profoundly.

Quote from: Vladki on December 10, 2015, 07:59:11 AM
Counting stops would make sense, if pax would not take whatever convoy that takes them to their destination (next transfer). Preferring lines with less stops will improve usage of parallel express and commuter lines.

As I understand it, the issue here is simply how goods choose which intermediate stations to change vehicle at. A possible problem with both these suggestions is that they make just as much sense for selecting which vehicle to board at all. Using Fifty's quoted example in the first post, Vladki's suggestion would make B-A-C preferable to B-D-E-C due to fewer stops. But fewer stops would not make A-C-E preferable to A-B-D-E, because that is not a routing question (the route is simply A-E, compared to a selection between B-A-C vs B-E-C). A distance based tie-breaker might have some of the same problems, but maybe less noticeable in practice.
Title: Re: Changes in routing of passengers
Post by: gauthier on December 10, 2015, 07:19:17 PM
QuoteI am quite neutral against changing the routing to be distance based. I would like to hear other opinions, too.
The current routing system has obvious drawbacks if you make networks with loops or even with some lines having an overall curved shape. A distance-based routing algorithm can't be worse.

QuoteAnother idea would be to use estimates of travel time, based on distance and speed of assigned vehicles.
This would be even better provided the travel time is estimated well. By the way, a good idea would be storing travel times in the lines'data, using total travel time of the line and number of convoys would be an easy way to implement automatic convoy spacing (yes, I'm pushing this again :p ).
Travel time can be simulated first, and then replaced by statistics (each time a convoy arrives at a stop, it updates this line's part's travel time, like computing a weighed average between old and new times to prevent local incidents from screwing up everything).
Title: Re: Changes in routing of passengers
Post by: prissi on December 10, 2015, 10:26:29 PM
Distance based will disfavour long-distance aircrafts; but those are such cash cows that that is probably even a good thing.
Title: Re: Changes in routing of passengers
Post by: captain crunch on December 10, 2015, 10:40:18 PM
The most realistic passenger routing would be that of choosing the shortest estimated travel time and shortest time to departure I think.
Title: Re: Changes in routing of passengers
Post by: DrSuperGood on December 10, 2015, 10:50:11 PM
Most realistic is weighing comfort, cost and travel time. People will rather take a 12 hour flight in a normal jumbo jet aircraft than a 3 hour or less flight in the concord because it costs a fraction of the price.
Title: Re: Changes in routing of passengers
Post by: gauthier on December 11, 2015, 06:57:15 PM
Taking so much parameters into account could be a performance issue for standard, and I'm not sure standard players want to be bothered with this additionnal complexity.
Title: Re: Changes in routing of passengers
Post by: isidoro on December 12, 2015, 12:35:10 PM
If one doesn't want to make deep calculations and statistics (à la Experimental), some good approximations can be done.

Comfort and price aren't simulated, at least in Standard, so time to reach destination is the real variable, at least for passengers.

One can estimate time adding two quantities:
1) Estimated travel time (distance/estimated speed)
2) Estimated waiting time at transfers

Number 2) can be made a constant (if I understand it correctly, now it's infinite).  Or a constant that depends on the date...

Number 1) needs estimated speed.  Whatever will do: average max speed of convoys leaving this station, some statistics...  If constant, those times can be precalculated and stored in the station's data for directly connected stops.

I guess that "time" was in the mind of developers when introduced a penalty for transfers.
Title: Re: Changes in routing of passengers
Post by: gauthier on December 14, 2015, 06:53:30 PM
QuoteNumber 2) can be made a constant (if I understand it correctly, now it's infinite).  Or a constant that depends on the date...
A constant will still lead to absurd results in some extreme cases. If statistics are made on lines themselves, computing convoys'frequency easily gives Number 2) (Average waiting time is half of the period between two convoys).