Question about routing

[Jando]

Hello! I have a question about routing, this is in Standard Simutrans, with pak128, no changes to config files.

2 cities, let's call them X and Y that are not connected directly, but can be reached via towns A or B. Both routes (via A or B) require one change of line, thus possible routings are X-A-Y and X-B-Y. As far as I know (but that's not very far!) Simutrans Standard uses the route with the least changes of line.

First question thus: if there is more than 1 routing with the same amount of change of lines, which one gets chosen? X-A-Y or X-B-Y in the above example? Is this somehow predictable or is it just whatever the algorithm finds first or last?
Second question: is it possible (because it seems to happen to my current game) that in the above example traffic from X to Y gets routed via A but traffic in the opposite direction Y to X gets routed via B?

Thanks in advance.

[An_dz]

1. The shortest distance TurfIt is right.
2. It depends on where people want to go later. If people from X want to go somewhere where taking X-B-Y first will result in the minimal number of transfers they will choose it. While people from Y may find taking Y-A-X has less transfers on the rest of their journeys, and so they will choose it.

[Ters]

In my experience, the answers are:

1. "Random". (It even tends to change which line is mostly used. I'm not sure what exactly triggers such a change in preference.)
2. Yes, you may find that passengers from X to Y go via A, while passengers from Y to X go via B. For this reason, I try to ensure that circles of lines (not circular lines) in my intercity network have an odd number of transfers.

[TurfIt]

1. Whatever the algorithm finds first/last. It is predictable for the simple case, but as more possible routes are created, becomes too much for a human to easily track. The route found first depends upon the order the stations are stored internally in memory by the program. So you can build some stations, setup a line, add enough convois to handle the traffic, then save/reload the game, and observe all the traffic decide to take a different route - 'wrecking' the line you just setup.
2. It's almost guaranteed that return traffic will take the other route. Given the typical economic balance requiring >50% average load to make a profit, better hope there's enough other traffic to balance the convoi loadings out. Or, you need to design the network so there's never two equal paths...

1. The shortest distance
2. It depends on where people want to go later. If people from X want to go somewhere where taking X-B-Y first will result in the minimal number of transfers they will choose it. While people from Y may find taking Y-A-X has less transfers on the rest of their journeys, and so they will choose it.

2. Travel onwards has no influence for this. X-A-Y-C-D or X-B-Y-C-D is the same. Via A or B depends solely on their position in memory.
1. Number of transfers is the only factor. In case of a tie - position in memory.  I'd looked at using distance as a tie breaker, but something changed making it impractical before I finished... (the larger maps??)

[DrSuperGood]

I do not see why something like Manhattan distance would not be a good tie breaker. You compute it with an int which can handle impossibly big maps. For every hop along a route (between boarding and alighting stops only, ignore other stops between possibly) compute the Manhattan distance. If a tie is found then use the one with the lowest Manhattan distance sum.

Another solution would be to allow players to assign priorities to lines. In that case the line priorities are used to determine tie breaker situations. This would allow people to force traffic to take one line rather than the other in a predictable way.

It might even be a good idea to revise "number of hops" being the optimum routing mechanic. Although I am not sure how, having the ability to force passengers to take extra hops (eg transfer to an express service) might allow more efficient networks in that passengers could force passengers off slow services onto faster services.

In any case leaving anything to internal ordering that can vary between save and load is not a good idea. Ultimately in games like Simutrans one wants a save to be such that upon reload the game state is restored exactly.

[Ters]

I do not see why something like Manhattan distance would not be a good tie breaker. You compute it with an int which can handle impossibly big maps. For every hop along a route (between boarding and alighting stops only, ignore other stops between possibly) compute the Manhattan distance. If a tie is found then use the one with the lowest Manhattan distance sum.

I can see this cause some strange routing in some cases, but it's probably better than what we have now. The biggest question is how much more extra information the routing must keep track of during the process. In the end, I think it only remembers the next hop. If the tie-breaking happens there, it might cause strange routing much more often (first hop is short, but the next are very long). On the other hand, such strange routing can arise form just couting hops as well.

It might even be a good idea to revise "number of hops" being the optimum routing mechanic. Although I am not sure how, having the ability to force passengers to take extra hops (eg transfer to an express service) might allow more efficient networks in that passengers could force passengers off slow services onto faster services.

I haven't really had any situations where getting off a bus to switch to a train would get passengers to their goal faster, but I have had problems where passengers had the choice between a slow and crowded bus and a faster, more spacious train, and routinely select the former. I understand that Experimental has dealt with this, but in a very computationally expensive way (perhaps intermingled with other concepts)?

[An_dz]

2. Travel onwards has no influence for this. X-A-Y-C-D or X-B-Y-C-D is the same. Via A or B depends solely on their position in memory.

I was talking about X-A-Y-C-D vs X-B-Y-C-E-D

[Bear789]

I haven't really had any situations where getting off a bus to switch to a train would get passengers to their goal faster, but I have had problems where passengers had the choice between a slow and crowded bus and a faster, more spacious train, and routinely select the former. I understand that Experimental has dealt with this, but in a very computationally expensive way (perhaps intermingled with other concepts)?

Last time I tried it (it was at least a year ago, probably more) Experimental factored total travel time and went for the faster route irregardless of the number of transfers and the actual lenght of the trip. Sometimes this caused an opposit problem: you  build a faster route and you may kill all the other options (for example as soon as you set up planes, intercity train ridership plummets).

[Jando]

... I understand that Experimental has dealt with this, but in a very computationally expensive way (perhaps intermingled with other concepts)?

Most of my games have been in Experimental before, it uses estimated travel time and assumed waiting time at stations to decide on the routing. Sadly the Experimental release currently has a pretty game-breaking bug in the calculation of travel times causing a complete routing mayhem - that's why I started a Standard game and thus wanted to know more about how Standard calculates routing.

Thanks for all the answers in this thread!