How does routing work?

[Milko]

Hi

I have been involved in some thread, I did not understand how simutrans calculates the routing of passengers (or goods) in "simutrans experimental." Let me explain what I understand, can you tell me if I'm wrong?
Considering the need to transfer from an "A" to "Z", the link between the two points can be made through two different routes (one that uses "B" and one that uses "C"):

  / B \
A      Z
  \ C /

When a passenger is generated in "A" simutrans evaluate the possible paths to reach "Z", simutrans gets 2 different routes: ABZ and ACZ.
At this point simutrans calculates the time (total travel time and waiting time at stations) for ABZ and ACZ, all passengers are routed to the path with the shortest time of transfer. If ABZ has a travel time less than ACZ all passengers will be routed to "B". When passengers arrive at "B" simutrans evaluate the possible paths to "B" to "Z" (using the same procedure of choice that was made when simutrans had to choose the path between "A" and "Z"), as if just downloaded the passengers had just been created in "B" and should go to "Z".

Giuseppe

[inkelyad]

Not exactly. It is not done on per-passenger basis. Simutrans gradually recalculate one big table <current stop, dst stop, cargo category> -> <next stop, best line >. If train from best line are available, passenger will use it. If it is not, he can wait or use currently available train to the same <next stop>. All passengers on A will use some next stop (B or C) until said table updated.

[jamespetts]

Milko,

the answer is: sort of. There is a table of best routes from everywhere to everywhere else. When passengers in A look up the best route from A to Z, they are told to go via B (assuming that that route is faster), and also which line/convoy is likely to get them to B the fastest (although if they wait too long, they'll take anything that gets them to B). At B, the same process occurs, except that the passengers are instructed that they are able to go straight to Z, and board the likely fastest (or, eventually, any) convoy to Z. These routes are recalculated periodically and also when the transport network is modified.

[Milko]

Hi

Thank you, now (finally) I understand. 

Transform the relationship between the triplet and the next station from "1 to 1" to "1 to many" would mean very heavy computation time?
I guess the possible paths (with all the travel time and waiting time) are still evaluated when the table is updated, you may keep track of the possible paths with their timing and route accordingly passengers broken down using the timing.

Giuseppe

[jamespetts]

Milko,

I am not sure that I follow: what do you mean by "triplet" here?

[Milko]

Hello

With triplets I mean: <current stop, dst stop, cargo category> (three parameters).

My idea was that every <current stop, dst stop, cargo category> has two or three different <next stop, best line >, every <next stop, best line > with a weight to subdivide pax.

Sorry for having revived an old thread.

Giuseppe

[Carl]

So to combine your old and new points, Giuseppe (in conjunction with what Omikron said in the other thread re planes), I take it one might suggest something like the following:

"As it stands, many possible routes are calculated in the routefinding process -- but currently the game only stores and keeps track of which connection is best between any two given points. But perhaps the game could also remember a "second best" connection between each two given points (at least in cases where second best is not drastically slower than best). Then it could be a matter of weighted chance whether passengers choose the best or second best connection."

This doesn't sound like it would require a complete routefinding code overhaul, but it would certainly make the routefinding process more computationally intense, as James mentioned. (Each time a new connection is found it would have to be checked against not only the existing best connection but also the existing second best, etc, so that's one aspect of the process that's already doubled. Also there would be an increased RAM load for storing more than one connection for each pair of points). The question is: just how big would the performance hit be?

[jamespetts]

Ahh, it's not as simple as that, I'm afraid: the routing system does not form multiple complete routes and then check which is the fastest - rather, the process of checking which is the fastest and forming the routes is one, as a result of which, there are no incomplete but slower routes that could simply be captured and stored. The routing system would need to be made massively more computationally intensive and less efficient to produce multiple complete routes.

[omikron]

But that would mean that there is no guarantee that what the pax choose as the fastest way actually is the fastest, because they never looked into other options?

There must be somewhere in the code, where the choice between route a, route b, route c .... and route x is made. This point could be expanded to choose not one but two routes, which are weighted percentually, depending on the travel time difference.

There is a table of best routes from everywhere to everywhere else. When passengers in A look up the best route from A to Z, they are told to go via B (assuming that that route is faster), and also which line/convoy is likely to get them to B the fastest (although if they wait too long, they'll take anything that gets them to B). [...] These routes are recalculated periodically and also when the transport network is modified.

If this is right, this would mean that the table ought to be twice as large, which would obviously eat away CPU and memory, but we won't know how much until we try.

Or have I got things completely wrong? I tried looking into the code yesterday, but was not successful. If someone gives me a hint, I'll continue to search.

omikron

[Carl]

If I'm getting this right, one section of central interest is in path_explorer.cc at around line 893:

Code Select Expand

// Check whether this is the best connexion so far, and, if so, add it.
                  if( !catg_connexions->put(halt_list[t], new_connexion) )
                  {
                     // The key exists in the hashtable already - check whether this entry is better.
                     haltestelle_t::connexion* existing_connexion = catg_connexions->get(halt_list[t]);
                     if( existing_connexion->journey_time > new_connexion->journey_time )
                     {
                        // The new connexion is better - replace it.
                        new_connexion->alternative_seats = existing_connexion->alternative_seats;
                        delete existing_connexion;
                        catg_connexions->set(halt_list[t], new_connexion);
                     }
                     else
                     {
                        delete new_connexion;
                     }

So my though was that the conditional process here could be made more complex as follows (pretend code):

Code Select Expand


Is new_connexion better than existing_connexion? If so, replace it.

Else:
Is new_connexion better than existing_second_best_connexion? If yes, replace it.

If not, discard new_connexion.

(Obviously you'd also need a clause to see whether existing_connection should be shifted into existing_second_connexion, and to check that new_connection is not drastically slower than existing_connection before storing at as an alternative option-- this is just a very basic schematic).

Now James's comments above seem to presuppose that nothing like this could work -- which makes me think that I've misunderstood what's going on with the code here. I'm interested in understanding what I've missed here.

[omikron]

I'm afraid that specific place in the code only looks for direct connections from a stop. The transit matrixes come a bit later, in line 1360 ff.

If I understand correctly, these loops recalculate the matrix of all connections on the map monthly. I think I understand James's reservations, as these tables are not created by looking up all origins and linking them individually to all targets, but rather proceed somewhat organically. But I don't understand them enough to say exactly how...

omikron

edit: the largest loop looks at each transfer stop, the second one at the general origin of the pax arriving at this transfer stop, the third one at the general direction they are going, then at their individual origins before their individual destinations are considered.  - Is that right?

[Carl]

I'm afraid that specific place in the code only looks for direct connections from a stop. The transit matrixes come a bit later, in line 1360 ff.

Ah yes -- I see that now. In fact, I think I had deduced this a couple of weeks ago and since forgotten it...

Notwithstanding my comments above, I think my general view on this issue is that the path-explorer works very, very well -- bracketing the issues with waiting times that I hope we're on the way to fixing -- and that it would be a mistake to tamper with it too much unless simulation can be improved drastically with few side effects. (And there would certainly be side effects to all of the alternatives suggested so far.) Also, insofar as there's a big computational cost to making the system more complex, the status quo looks even more appealling.

[jamespetts]

The routing code was written by Knightly some years ago now, and it is highly optimised. It uses the Floyd-Warshall algorithm simultaneously to find the best routes from all places to all other places. This is a highly performance sensitive area of the code, and very great caution indeed is required before changing it: Carl is entirely correct in this respect.

In any event, I am somewhat sceptical that simply picking the second and third best routes and randomly selecting them does indeed simulate anything real at all. To give an example - yesterday, I was travelling from Southend to London. There was a choice of two trains: one that went via Basildon, and one that went via Tilbury. The Basildon route is a more direct route, and is about 30-45 minutes faster than the Tilbury route, so, naturally, I chose the Basildon route. I think it very unlikely that any of the passengers waiting at Southend who actually wanted to go to London would have boarded the Tilbury train. For the people at Southend, the Tilbury train was for going to Tilbury (or Gray's or Chafford Hundred or any of the other stations on that route), not to London. It is only a London train for the people actually in Tilbury, etc.. With the change proposed, if this setup was simulated in Simutrans, a certain proportion of people would choose the Tilbury train, and this would not be realistic. The only circumstances in which people would choose the Tilbury train would be if the difference in journey time between the Basildon train and the Tilbury train is less than the difference in departure time between the Basildon train and the Tilbury train, and the Tilbury train leaves first, and this is already simulated (as best as can be done without introducing full timetables).

[omikron]

I see. I fear I am tempted to consider another feature of travel: cost difference, which is not in simutrans at all and would definitely overload the game. When travelling from Aberdeen to London, there are three ways: by plane, by train or by bus, and they differ vastly with regard to comfort, journey time and price. In simutrans, when I have a direct train link between the town halls, this would most likely always remain the preferred route, to travelling by bus to the airport and then plane and then by bus to one's destination. But in RL many people would choose this route, although the first lap would most likely be a private car and the last one maybe a taxi.

But I see that this kind of variation is way too much to ask for.

omikron

[Carl]

In any event, I am somewhat sceptical that simply picking the second and third best routes and randomly selecting them does indeed simulate anything real at all. To give an example - yesterday, I was travelling from Southend to London. There was a choice of two trains: one that went via Basildon, and one that went via Tilbury. The Basildon route is a more direct route, and is about 30-45 minutes faster than the Tilbury route, so, naturally, I chose the Basildon route.

Yes, I was assuming there'd be some kind of relative-journey-time check which would rule out the via-Tilbury routes here. The possibility of choosing multiple routes from Southend Central is, of course, simulated in this way in my recent patch for passengers choosing non-preferred routes (and this patch should have the desired result that pax won't travel via Tilbury).

The Southend example is useful, however, because it draws attention to something which isn't simulated: the possibility that passengers may instead travel from Southend Victoria to London Liverpool street, which seems to have an almost identical journey time to the Fenchurch Street route. For a given point in the centre of Southend, either every London passenger generated at that point will travel via Southend Central, or every London passenger will travel via Southend Victoria. (In practice it's a little more complicated than this -- but assume that we've pinned down a certain point in the centre of London as well as one in the centre of Southend, and my previous statements will be true).

Of course, I realise that there isn't an obvious way to do this in the current framework -- and that the framework itself is best not tampered with -- but it is good to be clear about where the limitations of the framework lie.

[jamespetts]

Yes, I think that you've both summed up the issues accurately: people do choose different and sometimes slightly (or even substantially) slower routes for specific reasons (such as price and comfort), but actually simulating these would undermine the optimisation of the existing framework computationally, and, in respect of price at least, vastly increase the complexity for players, and in potentially very tedious ways (imagine having to price optimise every single route by hand to make sure that a competitor did not take away passengers using its similarly timed and similarly comfortable competing route over and over again while a competitor does exactly the same thing...).

I did wonder about perhaps one day adding comfort to the routing system by using an amalgam of the journey time and comfort to produce the weight for each node in the Floyd-Warshall graph (thereby not materially interfering with the actual route calculations), but having to perform a computation for each retrieval of the value rather than simply accessing a memory location would in all probability dramatically impact on performance here.

[isidoro]

Price is definitively an issue when traveling.  Now that there is competition in multiplayer games, it should be taken into account.

But James is right that this can add too much micromanagement.  However, I have think about a  possibility to overcome this.

Now the price that one is payed for each km traveled depends on the type of element transported, the speed,...  In the new system, that would be the base price.  Each company can make a general discount on that for the sake of competition.

For example, Trikki Transports offer a 10% discount on buses.

This is easy to program, easy to advertise to others and easy to manage...

[omikron]

But then the routing needs to be equally taking price into account, and that's the real issue, I think. Otherwise, the only result of such a change would be less income for Trikki...

omikron

[isidoro]

Of course.  That's for granted.  Ticket price would be another ingredient when choosing your transportation.  That's not difficult either.