How (not) to choose a route

Topic: How (not) to choose a route (Read 8682 times) previous topic - next topic

How (not) to choose a route

October 17, 2010, 03:00:42 pm

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, p****engers travelling from A to B travel will only travel on Line 2. Oddly, this behaviour is not always symmetric -- p****engers 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 p****engers 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, p****engers 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 p****enger 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. P****engers 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 p****engers 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 p****engers always choose Line 4 in this situation?

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

Re: How (not) to choose a route

Reply #1 – October 17, 2010, 03:07:03 pm

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 p****engers/goods take something other than the fastest line to their destinations; so, in your example, if p****engers at A have been waiting a long time, they may well take the stopping train to B instead of the fast train.

Re: How (not) to choose a route

Reply #2 – October 17, 2010, 05:50:08 pm

If I understand code correctly, p****engers 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 p****engers at stop.
If at stop C you have long-waiting p****engers to somewhere else, then line 3 will be 'slow'.

Re: How (not) to choose a route

Reply #3 – October 17, 2010, 06:51:34 pm

Quote from: inkelyad – on October 17, 2010, 05:50:08 pm

Worse, average waiting time is calculated over all p****engers at stop.
If at stop C you have long-waiting p****engers 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.

Re: How (not) to choose a route

Reply #4 – October 17, 2010, 07:59:17 pm

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 p****engers 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: p****engers 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 p****enger'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.

Re: How (not) to choose a route

Reply #5 – October 17, 2010, 08:39:45 pm

Aha.
From haltestelle_t::add_connexion

Code: [Select]

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

Re: How (not) to choose a route

Reply #6 – October 17, 2010, 09:14:31 pm

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

Re: How (not) to choose a route

Reply #7 – October 17, 2010, 09:34:00 pm

Jha - thank you for your input, which is always much appreciated :-) There is already something of a penalty in transferring, as waiting times are ****umed 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.

Re: How (not) to choose a route

Reply #8 – October 17, 2010, 09:56:12 pm

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).

Re: How (not) to choose a route

Reply #9 – October 17, 2010, 10:14:37 pm

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.

Re: How (not) to choose a route

Reply #10 – October 17, 2010, 10:31:06 pm

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 p****enger 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.

Re: How (not) to choose a route

Reply #11 – October 17, 2010, 10:34:40 pm

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

Re: How (not) to choose a route

Reply #12 – October 18, 2010, 01:12:36 am

Quote from: jamespetts – on October 17, 2010, 06:51:34 pm

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]

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

simhalt.cc:

Code: [Select]

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

It is not destination-specific.

Re: How (not) to choose a route

Reply #13 – October 18, 2010, 03:32:38 am

Quote from: jamespetts – on October 17, 2010, 10:34:40 pm

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 p****engers 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.

Re: How (not) to choose a route

Reply #14 – October 18, 2010, 12:11:42 pm

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".

Re: How (not) to choose a route

Reply #15 – October 18, 2010, 03:53:21 pm

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...

Re: How (not) to choose a route

Reply #16 – October 18, 2010, 09:12:45 pm

Quote from: skreyola – on October 18, 2010, 03:53:21 pm

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.

Re: How (not) to choose a route

Reply #17 – October 18, 2010, 09:17:11 pm

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.