Topic: Travel time based congestion

[jamespetts]

The general problem I've found is that cars coming out of dead-ends are reported as either driving 0 yards or 4096 yards by the do_drive() function. For comparison, driving across a straight tile is ~100,000 yards and a diagonal or corner is ~70,000.

Perhaps this is because the distance from vehicles leaving the tile just before the dead end and coming back to that tile again is, in effect, zero? One might infer that this is what is being measured. If so, you need a means of detecting this case specifically and dealing with it.

[Freahk]

Simply refuse implausibly small values should work.

Yards unit is not related to meters per tile and stuff like that.

Code: [Select]

#define YARDS_PER_TILE_SHIFT (VEHICLE_STEPS_PER_TILE_SHIFT + YARDS_PER_VEHICLE_STEP_SHIFT)Currently, 4096yd is a single vehicle step.

[jamespetts]

I have merged Freddy's fix and also attempted to implement Freahk's fix, but neither solve this problem (although they seem to reduce it slightly).

[freddyhayward]

My previous fix was only intended to affect player-owned road vehicles such as buses. I have just pushed another fix that sets the threshold to 128 << YARDS_PER_VEHICLE_STEP_SHIFT, or half a tile length. By comparison a full tile length is ~255 and a diagonal is ~180. This seems to fix the issue, although it might be worthwhile to look into the root cause in the future.

[jamespetts]

Splendid, thank you for this. Testing shows that this now seems to work, so I have now incorporated this. I should be grateful for feedback on how this is working in practice on the Stephenson-Seimens server as of to-morrow.

[Freahk]

I should be grateful for feedback on how this is working in practice on the Stephenson-Seimens server as of to-morrow.

At first, the measurement of congestion works really great! There are huge congestions reported in places that do actually increase journey times by quite alot.

As always, there's also a downside:
The recorded congestion does not qork quite well with the way route calculations consider congestion. Once a road is congested quite a lot, at the next reroutes all routes will ignore that road. If a (motorway) bypass was too congested, all cars will be routed through the city center. No need to mention this will cause even more congestion.
In the next route calculation run, cars will be rerouted to another route through the city and so on, until a) all city roads are that much congested, it's better to use the motorway again, or b) congestion data reset by month change.

The congested motorway cannot recover itself, because no cars are routed via it, so nobody can report "I passed that road in time" decreasing the congestion count.


I had a short discussion with Freddy in the past about this:
His idea was to implement some periodical decay of congestion on roads that are reported congested, so roads will recover automatically if there are no cars pasing (i.e. no cars causing further congestion)
I had agreed with the idea at that time, but in later thoughts noticed this won't solve the issue. Routes will still be routed via city centers once the motorway is too congested and it will take some time until the motorway recovered and routes were recalculated, in which time the motorway will not be used at all.


I just came up with a different idea:
What we actually need to know and consider when calculating private car routes is:
- How much throughput does a road have? I.e. how many cars can pass without causing excessive congestion?
- How much time do cars need to travel along a road? I.e. how much congestion caused delay should they expect on top of what the road could handle?

The bad news:
We cannot say this in general, it needs to be balanced out.

The good news:
We got all most data required to balance this out stored in the world already.

So what's the idea?
Roads do already store how many cars had passed by in the previous month.
They do also store the congestion.
Routes need to store the amount of cars that used the route. That means for example, if there had been 50 car journeys generated from Town A to B, that number is remembered.

A congested road is considered to be over-capacity. By how much depends on the level of congestion.

Route calculations will now need to keep track of how many cars there are expected to be sent along a road.

The recorded congestion level can then be applied partially, according to how much more cars than infered capacity there will be on a road: If there are up to as many cars as expected capacity expected, no penalty will be applied. If there are more cars than expected capacity, recorded congestion will be interpolated in between expected capacity and the actual number of cars that caused the congestion.

[jamespetts]

Thank you for that feedback. This is an interesting idea, but I am not sure how the suggested algorithm of "apply[ing] partially" the congestion would work. For any given road tile, how would we calculate the time to traverse that tile to use as the edge weight in the Dijekstra's algorithm from the two data of a congestion percentage and a total number of vehicles? What would the algorithm actually be to get from those data to the time value for that tile?

[Vladki]

Just a brainstorming idea - how do crossings affect journey time calculations? Would a penalty for each crossing be helpful to keep cars on bypasses instead of going through cities?

[jamespetts]

Just a brainstorming idea - how do crossings affect journey time calculations? Would a penalty for each crossing be helpful to keep cars on bypasses instead of going through cities?

Crossings are dealt with just as any other road tile; a non-reality based treatment of crossings would be likely to create intractable anomalies, as with all non-reality based mechanisms, however, and should be avoided at almost all costs.

[freddyhayward]

The effects of congestion are currently arbitrarily divided by 2. This was intended to soften the effect to avoid over-reactive routing effects.
This is the current code:

Code: [Select]

const uint32 congestion_percentage = w->get_congestion_percentage();
if (congestion_percentage)
{
speed -= (speed * congestion_percentage) / 200;
speed = max(4, speed);
}
This is what I propose to change it to:

Code: [Select]

const uint32 congestion_percentage = w->get_congestion_percentage();
const uint32 congestion_effect_percentage = welt->get_settings().get_congestion_effect_percentage();
if (congestion_percentage && congestion_effect_percentage)
{
speed -= (speed * congestion_percentage * congestion_effect_percentage) / 10000;
speed = max(4, speed);
}
This would require adding a new setting, where to achieve the same result would be setting congestion_effect_percentage to 50. It's possible that the problem can only be fixed with fundamental changes to congestion mechanics. Then again, it's also possible that experimenting with the setting yields an optimal value that fixes the problem enough.

[jamespetts]

Your suggested code change will certainly be beneficial, as this will give better customisation, and it is always better for values such as this to be user selectable. However, one must be cautious in excessively reducing the extent to which the simulation is reality based, as this inevitably introduces intractable anomalies.

[freddyhayward]

However, one must be cautious in excessively reducing the extent to which the simulation is reality based, as this inevitably introduces intractable anomalies.

That's true. One possible case is that if congestion is under-estimated, more cars will use the road, making it even more congested than if it was correctly estimated. It could equally be the case that increasing the percentage towards reality (100) would yield better behaviour.

[Freahk]

how would we calculate the time to traverse that tile to use as the edge weight in the Dijekstra's algorithm from the two data of a congestion percentage and a total number of vehicles?

I don't think a good guess can be placed based on only these two numbers.
We will also need to know how many cars each route is expected to generate and, how many of these (expected) cars are already routed along a specific road. (as mentioned above)

With this information, we can guess on how much traffic a road can handle and how much journey time it will cost to exceed that guessed capacity.
The latter should ensure that
expected_number_of_cars=expected_road_capacity => no additional journey time,
expected_number_of_cars=measured_number_of_cars  => measured_additional_journey_time.
In different words: It's an interpolation in between expected capacity assuming 0 congestion and measured capacity assuming measured congestion.

How the exact guess is best placed will need empirical testing and observation of different guesses.
Just to get started, a linear guess with linear interpolation:
- assume every 10% congestion indicate 1% too many cars.
- assume linear interpolation and extrapolation.

In numbers this means:
congestion_factor := measured_car_pass_time/expected_car_pass_time (that's de definition as-is)
expected_capacity=numbers_of_cars_passed / (1 + (congestion_factor-1)/10)

In case of expected_number_of_cars > expected_capacity:
 y = y0 + (x-x0) * (y1-y0)/(x1-x0)
 increase_factor = 1 + (expected_number_of_cars - expected_capacity) * (measured_congestion - 1) / (measure_numer_of_cars - expected_capacity)
This is nothing special, just liear interpolation.

otherwise:
 increase_factor=1 We don't expect any congestion below the expected capacity.

[Vladki]

Just some thoughts about how real world route finding works/worked...

Until wide spread of smart GPS navigation that uses real time congestion values (waze), people used maps, road signs, and "static navigation". All these did not know anything about the road being congested or not. Just could make more or less informed guesses based on experience or long time patterns, which could be generally summed up in simple rule - avoid towns. Why - beacause of speed limits, lots of crossings and higher potential for congestion.  Even now, not everybody is using waze, and even then does not always obey its suggestions, and instead takes the route that seems to be faster using map (ignoring real-time congestion). 

I thing the route finding algorithm, would prefer bypasses, if not looking at congestion. At least if they are built using roads faster than city roads.
I'm not sure if waze could intentionally send you on a path from which they do not have enough data, to find out how congested it is.

So how about modifying the algorithm, this way:
a) some drivers will go on the shortest route (in km)
b) some drivers will go on the fastest route - distance and top speed of road (no congestion)
c) some drivers will use smart navigation (or previous experience) that takes congestion in account.

The proportion of drivers using each algorithm, could be configurable, or even variable in time. IMHO up to 1940-50's there was not much difference between shortest and fastest route (there were no bypasses and motorways), and the last option became available only recently.

Also in real world drivers may decide not to use the best route for reasons we cannot simulate in game. (E.g. a good restaurant or cheap petrol station on the way - which is not their primary destination).

[freddyhayward]

The trouble is that drivers don't store or calculate routes themselves - this is done by towns and ways. Towns can only store a single route to any given destination, and cars can only follow that route. Using multiple routefinding methods would multiply the number of routes that are calculated and stored.

Also, the current calculation congestion and route-finding isn't supposed to be 'real-time' - congestion is an average of the current and previous month (though, maybe it should be the previous month and the one before?), and routing is done periodically, from a few times per month to once every few months. It is less a measure of "how congested is the road now?" and more a measure of "how congested is this road usually?". That is consistent with word-of-mouth information even in the 1700s.

I guess that the cause of many problems is that all cars on the same journey will use the same route, but I don't know how this could be addressed without several times more storage and computation used.

[Freahk]

I guess that the cause of many problems is that all cars on the same journey will use the same route, but I don't know how this could be addressed without several times more storage and computation used.

It's even worse: Once two routes to the same destination merged, they cannot diverge again and will use the same route to the destination.
So routes A -> C and B -> C cannot use two different motorway exists around C if both share the same section of motorway.
They could indeed calculate two different motorway exists, but the one that writes last will win in that case.

The only thing we can distinuish without any problem are routes to different destinations. Distribiuting these to different roads in a way that will hopefully minimise overall congestions is what the above is about.

As Freddy said, the data this is based on is not live, so this is rather word-of-mouth information than a real live system.
To get a real live system, we had to record congestion data in much shorter timeframes and calculate routes much more often, which is not feasible.

Recording shorter timeframes of congestion might, however be feasible and useful, so route calculations are based on more recent congestion data.
For example preparing the congestion record before each rote calculation run and then only calculatating a single (or a few) all-to-one routings per run might already give better results.
For example, a congested motorway would report it's free much earlier when it's not used by anyone and that situation would very likely occour much less frequently.

So this might be another good option, although that is indeed rather a live congestion system than a word-of-mouth information system.

[Vladki]

It's even worse: Once two routes to the same destination merged, they cannot diverge again and will use the same route to the destination.

I do not see a problem with that. Quite the contrary, it would be weird if cars arriving from A would use different motorway exit that drivers form B. What I see as a problem is that you have single route for each town. So people going to town C will always use the same motorway exit, even if they have multiple choices. In the end the area aroud the exit will be congested. And building more exits will not help (only to attract cars from opposite direction).

I would prefer more static word-of-mouth or roadsign navigation style. So averaging congestions since last route calculation, or for last 2 moths, or whatewer is used now should be fine. Maybe just deal specially with the case when a route has no traffic, that there is no congestion as well.  I just don't know how to avoid flip-flops.

And one more thing - it would be nice to be able to inspect the stored routes in road tiles. That would better explain, why cars take unexpcted routes.

[freddyhayward]

And one more thing - it would be nice to be able to inspect the stored routes in road tiles. That would better explain, why cars take unexpcted routes.

I made a pull request for this: https://github.com/jamespetts/simutrans-extended/pull/196

[jamespetts]

I made a pull request for this: https://github.com/jamespetts/simutrans-extended/pull/196

Splendid, thank you for that: now incorporated. I should be grateful if you could add the translation text to Simutranslator.