How (not) to choose a route

[Carl]

I've been experiencing some odd behaviour on busy urban train routes, which I'll describe below. Partly this is just an exercise to help me understand the deep mechanics of the game better -- I play the game a lot, but have little knowledge of the code and calculations underlying it. But partly I hope to draw attention to some behaviour which seems to be undesirable. I hope you won't mind indulging my curiosity!

Two of my rail lines have the following stopping patterns:

Line 1: A----B----C----D----E----F----G----H
Line 2: A----B-------------------------G---------I----J----K----L

Both lines are operated by same kind of train -- think express vs. local services on the NY Subway. A is a major terminus, and B is a large suburban station which also has high traffic.

The behaviour I referred to above concerns traffic between A and B. As you'd expect, Line 2 has a higher average speed, since it runs express from B to G. But since both lines are run by the same vehicle, they take exactly the same amount of time to get from A to B. Nevertheless, passengers travelling from A to B travel will only travel on Line 2. Oddly, this behaviour is not always symmetric -- passengers seem to use both lines to get from B to A.

Working backwards from this, it seems that there is a close link between route selection and overall average speed of the various available lines. So passengers are noting that Line 2 is a "faster" train when choosing how to get from A to B. But they're mistaken, since Line 2 is only faster between B and G -- there is no difference on the A->B portion of the route. Ideally, passengers would only take into account the speed between the stations they're interested in, rather than the whole line. But I conjecture that the issue is deeper than this -- am I right in thinking that the journey times between stations are calculated using the distance and the overall average speed of the line? If passenger decisions are based on this calculation, that would explain the above behaviour. Are my conjectures correct here? Is there any way that journey times could be calculated by something more fine-grained than overall average speed, in order to avoid anomalies like these?


Related to this, I have a question about tolerance. Passengers will always choose the quickest route to their destinations. But how far will they tolerate taking different vehicles on those routes which vary in journey time only by a very small amount? Consider the following two stopping patterns:

Line 3: A----B----C----D----E----F----G
Line 4: A----B---------D---------F----G

All other things being equal, Line 4 will have a higher average speed. But the for journeys between A and D, the difference in journey time will presumably be negligible -- Line 3 only makes one more stop. In real life I'd expect passengers to be fairly indiscriminate between Line 3 and Line 4 when choosing a route from A to D -- a few minutes' difference is rarely taken into account into such decisions. Is this kind of tolerance modelled in Experimental, or will passengers always choose Line 4 in this situation?


I'd be interested to hear your thoughts on these and related issues!

[jamespetts]

Jha4ceb,

your conjecture is correct: the average speed of convoys on the line is used in the calculation of journey times. It is done that way to avoid excessive computational load: making the simulation more fine-grained, as you describe it, would actually add a very high level of complexity to the simulation, and, I suspect, make things run a great deal more slowly (not to mention that it would take a very long time to program initially and then iron out all the bugs).

There is a mechanism, though, written by others and added to Experimental, to make fairly sophisticated choices about when passengers/goods take something other than the fastest line to their destinations; so, in your example, if passengers at A have been waiting a long time, they may well take the stopping train to B instead of the fast train.

[inkelyad]

If I understand code correctly, passengers almost always choose faster route (not faster train). It includes waiting time and actual travel time. Sometimes they can wait for the next train to do it.

Worse, average waiting time is calculated over all passengers at stop.
If at stop C you have long-waiting passengers to somewhere else, then line 3 will be 'slow'.

[jamespetts]

Worse, average waiting time is calculated over all passengers at stop.
If at stop C you have long-waiting passengers to somewhere else, then line 3 will be 'slow'.

That is not correct: waiting time is destination dependent: see the "detail" display on the stations' dialogue boxes, which gives per-destination waiting and travelling times.

[Carl]

Thanks for your response. It's a shame that a more realistic alternative would be untenable for reasons of game speed. There will always be good points and bad points about using particular variables to calculate routes; on balance, average speed seems like it will get the right results most of the time, so is the right choice.

However, today I've come across a related problem which might be more easily solved without completely altering the current framework. Here's a simplified representation of two of my lines:

Line 1: A-B-C-D-----G-H
Line 2:       C-D-E-F

Again, these are operated by the same kind of train, but Line 1 has a higher average speed because the distance between A and B is large (= a long time spent at max speed). But this means that passengers from F to C will always change at D and wait for Line 1, even though the train they are on will take them straight to C. This always, without exception, results in them taking longer to reach their destinations than they otherwise would, because they have to wait at D for the next Line 1 train. (This behaviour is symmetric: passengers from C to F will refuse to take the 2-train, and will instead wait for a Line 1 train to D before waiting for the next Line 2 train.)

One way to eliminate this behaviour would be to attach a penalty to transfers between trains in the route calculation process. Is there a way to penalise each transfer an extra 5 minutes, say, in addition to the additional waiting time at the transfer station? This would model two aspects of realism: Firstly, a passenger's tendency to prefer to stay on the same train rather than change if the potential gain is small or zero. Secondly, it would model the fact that one has to allow a few minutes to transfer between trains anyway. I can't think of any unintended undesirable consequences of this off the top of my head.

Perhaps this is already programmed into the game in some degree. If so, perhaps its effect should be increased.

[inkelyad]

Aha.
From haltestelle_t::add_connexion

Code Select Expand


connexion* existing_connexion = connexions[category]->get(current_halt);
if(existing_connexion->journey_time > new_connexion->journey_time)
{
   // The new connexion is better - replace it.
   delete existing_connexion;
   connexions[category]->set(current_halt, new_connexion);
}

James, i think waiting time must be used here too.
EDIT: sorry, it will not help. It looks like current rounting code allow only one active direct line D->C

[Carl]

Hmm, that's odd -- I'm sure I've seen situations where passengers were willing to get on either of two different lines between two destinations. (When both lines had similar average speeds)

[jamespetts]

Jha - thank you for your input, which is always much appreciated :-) There is already something of a penalty in transferring, as waiting times are assumed to be at least two minutes whatever the actual figures. However, depending on the speed differential, this may be overcome by differences in average speed.

[Carl]

No problem, and thanks for humouring me in my ignorance -- I wish I was in a position to make informed comments about these features rather than just stabbing in the dark at what might be underlying the game's behaviour! But alas, my talents lie elsewhere than programming... :-)

It's good to hear that this feature is already coded into the game. I think five minutes could be a better value than two for the sake of route calculation. Not only would this eliminate some of the undesirable behaviour I described before, but it would also be a better across-the-board compromise between small stations (where it is feasible to transfer in only two minutes) and large stations (where you might need to allow ten minutes or more for a transfer).

[jamespetts]

Two minutes is more of a realistic figure: the problem with a higher figure is that it would overly discourage transfers on urban routes, giving direct but slow 'buses an excessive advantage over much faster urban rail/metro systems involving as little as one change. The figure of two minutes was taken from the London Underground, where the rule of thumb when calculating journey times is taken to be one minute per stop in central London, plus an additional two minutes for each interchange.

[Carl]

Interesting, thanks. I have two thoughts:

1. Even on the Tube, many transfers take longer than two minutes (as anyone who's had to change at King's Cross St Pancras, especially, will attest!). Normally it takes two minutes just to get from platform to platform, and (say) an average of two minutes to wait for the next train. So it looks as if one should usually budget for at least four minutes for a change on the Tube.

2. On most urban journeys a bus is *significantly* slower than urban rail, so I don't think a "five minute rule" would result in very many odd results. I take it that the extreme case is the very short journey. Say you want to go two stops on the tube with one change (i.e. one stop, change, one stop). That's two minutes' travelling time, but on my transfer rule the passenger would budget for seven minutes overall. A bus would only beat this if it could get there in six minutes or less. But even if the transfer only takes two minutes, rather than five, the bus has only taken two minutes extra. On longer journeys I think this won't be an issue at all -- given two points in London, the difference between the time it takes to cover that ground by bus on the one hand and by tube on the other hand is normally *far* more than five minutes.

[jamespetts]

Hmm, interesting. I'd be interested in any other thoughts as to a suitable minimum waiting time...

[inkelyad]

That is not correct: waiting time is destination dependent: see the "detail" display on the stations' dialogue boxes, which gives per-destination waiting and travelling times.

I don't understand. Said dialog box shows connexions.waiting_time field.
But all I can find is
path_explorer.cc:

Code Select Expand


new_connexion->waiting_time = halt_list[h]->get_average_waiting_time(halt_list[t], catg);

simhalt.cc:

Code Select Expand


new_connexion->waiting_time = get_average_waiting_time(current_halt, category);

It is not destination-specific.

[ӔO]

Hmm, interesting. I'd be interested in any other thoughts as to a suitable minimum waiting time...

That could depend on the time of the day, which I don't think is possible to replicate in simutrans, and how urban or rural the area is.

For rural areas, where it's 1hr or more for the train or bus out of town, it's about 8 to 10mins. Bus arrives 4mins before the train arrives and waits another 4mins for passengers from the train to board.

For urban areas, it's a bus every 10 to 15mins during rush hours, up to 20 to 30mins during day, and around 1 per hour for night time. A local transit connection usually takes no more than 10mins during the day.

speaking from a NA point of view.

[The Hood]

In a previous existence where I was involved in writing computer models of transport networks for real-life planning and investment decisions, it was fairly standard practice to incorporate a 10 minute interchange penalty.  It is also standard to apply a waiting penalty for each stop - this is usually taken as half of the time between trains on a route (so one train every 10 minutes gives a 5 minute penalty - this favours routes with frequent service, although it is usual to apply a cap of around 30-60 minutes as the maximum penalty as people will usually read the timetable when they know services are not frequent).  So the "generalised time" of a journey would be:
(in-vehicle time) + (waiting time at each stop) + (interchange penalty)  + (crowding penalties)
It is also standard to add on a cost component to these, but this is probably irrelevent to simutrans (or taken up by the comfort factor etc?).

Once you have worked out the generalised times for each journey, there are then two options. 
1) All-or-nothing: Everyone chooses the route with the minimum cost
2) Probabilistic choice: Most people choose the minimum cost, others choose slower routes.  The probability of route A is given by
P(a) = exp(-cost of route a)/(sum_for_all_i(exp(-cost of route i)))

I don't know if any of this helps in the simutrans-experimental world, but I thought I'd throw it out there as an example of how it's done "in the real world".

[skreyola]

Not sure about how the programming works, but I personally don't think most people would get off a train going to their destination to possibly have to wait for another train to get there, unless there were more intermediate stops...

[ӔO]

Not sure about how the programming works, but I personally don't think most people would get off a train going to their destination to possibly have to wait for another train to get there, unless there were more intermediate stops...

I agree, it's quite common in Japan, for instance. Some express trains are also used as a commuter for certain intervals, since they share the same tracks as the local commuter trains.

Japan's shinkansen for example, it's faster to ride on the express that takes you to A to Q, then ride one or two station from Q to O or R than it is to ride the train that does every single stop in the chart.

I think the best example is the Narita express. Lots of people use that train even though they aren't going to the airport at all.

[Carl]

I actually do this myself when I travel between Nottingham and Leeds. Changing at Chesterfield saves around fifteen minutes on most journeys, despite the fact that there is a direct train. But if it only saved five minutes, then I doubt I would bother changing -- because the connecting train is five minutes late as often as it is on time. This kind of reason is why I favour the five minute wait minimum.

[Carl]

Now that it's a few weeks after the initial discussion, I wondered if the developers (and others) had any further thoughts on this?

In the meantime I've spent significant hours building a UK network in Experimental, and my experiences there make me even more convinced that the "assumed minimum transfer time" needs to be increased. As things stand, it is almost impossible to successfully run lines whose routes overlap---even when those lines use identical vehicles. If the average speeds of the lines differ by just 3 or 4 km/h, then passengers will get off a train that is going straight to their destination, causing congestion at intermediate stations.

Some concrete examples from my UK map:

* Passengers from Nottingham to London will always board a London-bound train, and then change at Leicester to wait for a Derby-to-London train, even though the expected difference in travel time between Leicester and London on the two lines is very small---less than five minutes.

* Passengers from Bristol to London will always board a London-bound train, and then change at Reading to wait for a Cardiff-to-London train, even though the expected difference in travel time between Reading and London on the two lines is, again, very small. This is even more problematic in the other direction---London to Reading passengers will only board Cardiff-bound trains, even though Bristol-bound trains also go there non-stop. This means that Paddington is always crowded with Reading-bound passengers, and that Cardiff-bound passengers have huge waits for travel from Paddington.

Obviously this behaviour is very unrealistic---and this is down to the values which passengers in Simutrans Experimental use for calculating a route. If passengers had to allow at least five minutes for every transfer, then there would be far fewer routing anomalies like this. (Edit:) The point here is that passengers are currently acting against their own interest. Every single Nottingham to London passenger experiences a longer journey than they otherwise would, since they have to wait several minutes at Leicester. No Nottingham to London trains are overtaken by Derby to London trains, so every Nottingham to London passenger arrives later than they would if they hadn't changed.

(Footnote: In practice I have to counter this unrealistic effect by adopting unrealistic stopping patterns: So Derby-London and Nottingham-London trains do not stop at any of the same stations along their route. (Derby-Leicester-Luton-London and Nottingham-Kettering-Bedford-London respectively). This avoids the above problem because there is nowhere to change---but it requires extra measures to allow direct travel between, for example, Leicester and Kettering.)

[jamespetts]

Sorry for not having time to look at this much until now: on the 9.x branch, I have just increased the minimum waiting time from 1 minute to 4 minutes to see whether that assists. Anyone who can compile the code from source is encouraged to test this to see whether this helps.

Thank you for the report!

[jamespetts]

This change is now incorporated into 9.0 - I'd be very grateful for any feedback on whether this has solved the problem.