The International Simutrans Forum

 

Author Topic: Travel time based congestion  (Read 2030 times)

0 Members and 1 Guest are viewing this topic.

Online freddyhayward

  • Devotee
  • *
  • Posts: 224
  • Languages: EN
Travel time based congestion
« on: February 13, 2020, 11:26:46 AM »
https://github.com/freddyhayward/simutrans-extended/tree/travel-time-congestion

I created a new branch with an early implementation of travel time based congestion as proposed by Freahk. At this stage, the core mechanics for private cars now work, but not yet for player vehicles. I would be grateful if some of our more experienced coders could review the changes as they are now and after player vehicle congestion is implemented.

Essentially, the algorithm calculates the additional travel time per tile based on the time taken for vehicles to pass over them: a 100% congestion rating represents double the travel time, while 500% represents four times the travel time.

Offline Freahk

  • Devotee
  • *
  • Posts: 1055
  • Languages: DE, EN
Re: Travel time based congestion
« Reply #1 on: February 13, 2020, 11:56:19 AM »
Nice one, I will give it a try. As discussed, additional time per tile perfectly makes sense, it will save a little memory whilst not losing any required information.

I will give it a try, may I ask what does not work about player cars? Don't you measure their times at all currently or is it about calculating the guessed travel times?
In the latter case, I would just assume a player car can travel at min(vehicle_speed, road_speed) on any tile if uncongested. This is not entirely true, for sure, but this guess should not pretty negatively affect the calculations.
In case of curves, this speed restriction does not depend on the actual type of player vehicle, so it's also kind of congestion.
Slopes are more difficult but both types of slowdowns are not a local thing, they depend on where the vehicle came from, thus likely complicated to calculate.

Edit: Speed limits, including curve slowdown can be read from the route_info_t

Online freddyhayward

  • Devotee
  • *
  • Posts: 224
  • Languages: EN
Re: Travel time based congestion
« Reply #2 on: February 13, 2020, 12:18:30 PM »
Player vehicles (buses etc.) are a separate class to private cars. They share a vehicle_base_t but this extends to airplanes/trains etc, and they also use different speed measurements (i think?) etc. It's just a matter of duplicating over the code and changing a few things, which I'm in the process of doing. Or, perhaps there's a more elegant way of merging the two. Since there are multiple ways of traversing the same tile (e.g. moving straight through a junction or turning left), expected travel times are based on the distance traveled by the vehicle, measured at each hop. This also stops prevents 'instant' hops by private cars distorting the data.

As for the maximum speed of vehicles, I'm not sure how complicated it is getting the current top speed limited by curves/slopes/power/weight (edit: get_min_top_speed(), I think? or maybe this measures something else.) compared to the actual top speed defined by the pakset. From what I've seen the first might actually be simpler, but we shall have to see.

EDIT: I have now updated the branch with the implementation for player vehicles, which remains duplicate code for the time being.
« Last Edit: February 13, 2020, 11:15:18 PM by freddyhayward »

Offline Freahk

  • Devotee
  • *
  • Posts: 1055
  • Languages: DE, EN
Re: Travel time based congestion
« Reply #3 on: February 13, 2020, 02:10:56 PM »
Ah, so you simply don't measure their times at all yet and there is no player vehicle specific issues, fine, that's all I wanted to know :P

It's just a matter of duplicating over the code
Please, don't repeat yourself!
You should implement a more general stopwatch (measuring in ticks) or something like that to do the measurement and a general calc_max_speed_journey_time(way, vehicle, enter_direction, exit_direction) or something like that to calculate the estimation.

I had just found 4 (!) different implementations of ticks_to_seconds spread around the code, just in addition to the 4 different measures of time we have ingame already... this made it (and still is) a hassle to work on the seconds_per_month feature, which itself is quite simple but taking care of all these spread around code parts and different time, distance and speed units is really a hassle.

As for the maximum speed of vehicles, I'm not sure how complicated it is getting the current top speed limited by curves/slopes/power/weight
Except for curve limitations I am also not quite sure. (curve) Speed limitations are already stored as mentioned.
Slopes and even acceleration/deceleration sections around changes in speed limit however, would most likely require "simulating" the vehicles movement along these tiles assuming the road is free, also storing that data (per tile) in route_info_t, as that behavior is closely tied to the physics engine.

So if we really only need this to calculate the congestion slightly better, I don't think we should go for it. However, this is roughly the kind of information already discussed in another thread, so if we were implementing the "expected journey times" feature, to support line specific vehicle decision-making, we could "simply" use that calculated data if stored in the vehicle per tile instead of per route between stops.
In any case, this is another feature, as long as it's not implemented, we should simply assume any player vehicle can immediately accelerate to maximum speed.

get_min_top_speed() will simply return min(vehicle1.max_speed, ..., vehiclen.max_speed), thus the slowest maximum speed of all vehicles in the convoy or simply convoys max speed, so that's the one you should query when calculating expected travel time but it won't include information about any of the other mentioned aspects.
« Last Edit: February 13, 2020, 02:32:19 PM by Freahk »

Online freddyhayward

  • Devotee
  • *
  • Posts: 224
  • Languages: EN
Re: Travel time based congestion
« Reply #4 on: February 14, 2020, 09:43:38 AM »
With some help from Freahk, I have now refactored these changes into a new class: traffic_vehicle_t inherited by both private_car_t and road_vehicle_t. I believe the branch is now ready to be merged into the main game, hence this pull request: https://github.com/jamespetts/simutrans-extended/pull/141.

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19823
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Travel time based congestion
« Reply #5 on: February 14, 2020, 10:59:40 AM »
Thank you for this. Can I check whether this has been tested on a local client/server pair to see whether a network game will remain in sync with this feature?

Online freddyhayward

  • Devotee
  • *
  • Posts: 224
  • Languages: EN
Re: Travel time based congestion
« Reply #6 on: February 14, 2020, 11:08:59 AM »
Thank you for this. Can I check whether this has been tested on a local client/server pair to see whether a network game will remain in sync with this feature?
No, it hasn't, but I will do that now.

Online freddyhayward

  • Devotee
  • *
  • Posts: 224
  • Languages: EN
Re: Travel time based congestion
« Reply #7 on: February 14, 2020, 11:37:23 AM »
After testing for about 20 minutes, including over a new month, there don't seem to be any outstanding issues apart from versioning, which I believe I have just fixed.

Offline Freahk

  • Devotee
  • *
  • Posts: 1055
  • Languages: DE, EN
Re: Travel time based congestion
« Reply #8 on: February 14, 2020, 11:55:37 AM »
Great!
There is something I did not mention yesterday when we did the inheritance stuff, I was just terribly tired.
traffic_vehicle_t is not a vehicle anymore as it does not inherit from any vehicle. It should get a name better expressing what it is.
Again, I'm not a native speaker, so namefinding is always hard to me. We need something that expresses "I am an object that measures and protocols additional travel times aka congestion".
Something like congestion_measurer_t could work out, maybe there is a better term for something that measures congestion.
« Last Edit: February 14, 2020, 12:27:48 PM by Freahk »

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19823
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Travel time based congestion
« Reply #9 on: February 16, 2020, 03:33:17 PM »
Thank you for your work on this - I have now had chance to test this. I have identified two issues so far: first of all, the congestion data do not seem to be saved, but rather reset to zero when saving and loading a game. This will need to be dealt with before this feature can be integrated into the master branch.

Secondly, the measurement seems to expect too high a speed from many vehicles: I have observed on a number of occasions a private car passing an entirely uncongested road and the congestion percentage increases from 0% before the car passes to a higher number (e.g. 16%) afterwards. I have not fully parsed the code, but may I ask whether in your ideal speed calculation you take into account the speed limit of the road itself? In any event, this issue will need to be looked into and fixed before this can be integrated.

I should note that I have not yet tested memory consumption and computational intensity on large maps with this feature, and this will need to be done before this can be integrated.

Thank you again for your work on this: this is much appreciated.

Online freddyhayward

  • Devotee
  • *
  • Posts: 224
  • Languages: EN
Re: Travel time based congestion
« Reply #10 on: February 17, 2020, 03:07:12 AM »
I have just updated the branch, which hopefully fixes both of these issues. The second problem was caused by the unnecessary conversion of yards to meters and ticks to seconds, which caused rounding errors.

As for performance, I couldn't measure a significant increase in CPU usage. There was however a significant increase in memory usage. On a map with 256 towns, my branch used about 7.0GB compared to about 6.8GB on the base game, roughly an additional 200MB.

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19823
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Travel time based congestion
« Reply #11 on: February 19, 2020, 09:26:05 AM »
Thank you for that. I think that I will have to test this on a very large map after I have dealt with the other memory consumption issues relating to private car routing discussed elsewhere.

Offline Freahk

  • Devotee
  • *
  • Posts: 1055
  • Languages: DE, EN
Re: Travel time based congestion
« Reply #12 on: April 15, 2020, 01:45:08 PM »
Had this been incorporated already?
I noticed congestion values that don't match to the way how "Travel time based congestion" should measure congestion, so I don't think it is incorporated but somehow i had in mind it was incorporated, so I'm a little confused now.

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19823
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Travel time based congestion
« Reply #13 on: April 15, 2020, 04:42:39 PM »
No, this has not been integrated yet; I think that I got distracted with the memory usage issue and the various fixes to that necessary.

Freddy - can I check whether this branch is compatible with the current master (with its modified private car routing algorithm)?

Online freddyhayward

  • Devotee
  • *
  • Posts: 224
  • Languages: EN
Re: Travel time based congestion
« Reply #14 on: April 16, 2020, 12:16:52 AM »
No, this has not been integrated yet; I think that I got distracted with the memory usage issue and the various fixes to that necessary.

Freddy - can I check whether this branch is compatible with the current master (with its modified private car routing algorithm)?

No, I can't guarantee it, since there have been many changes to the master since I worked on this patch. I will have to test, but I suspect there will be several pain points around loading/saving and versions. Are you familiar with these parts of the code?

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19823
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Travel time based congestion
« Reply #15 on: May 11, 2020, 05:45:02 PM »
No, I can't guarantee it, since there have been many changes to the master since I worked on this patch. I will have to test, but I suspect there will be several pain points around loading/saving and versions. Are you familiar with these parts of the code?

Apologies for not having responded to this hitherto: I have been preoccupied with other matters, and, in the world of Simutrans, had been prioritising the loss of synchronisation.

When you refer to "these parts of the code", do you mean loading/saving generally, or the particular parts of the loading/saving code that you have modified? I am familiar with the loading/saving code generally; is there a particular question that you have about this?

Thank you again for your work on this feature.

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19823
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Travel time based congestion
« Reply #16 on: May 16, 2020, 12:34:50 PM »
I have attempted to merge this and resolve the numerous merge conflicts. However, there are significant compile errors which are difficult to resolve without knowing the intention of various parts of the code.

I have pushed the merged version to the travel-time-congestion branch. It would be helpful if you could take a look at this with a view to assisting in the resolution of the compile errors so that I can test this.

Online freddyhayward

  • Devotee
  • *
  • Posts: 224
  • Languages: EN
Re: Travel time based congestion
« Reply #17 on: May 16, 2020, 10:31:35 PM »
Apologies for not having responded to this hitherto: I have been preoccupied with other matters, and, in the world of Simutrans, had been prioritising the loss of synchronisation.

When you refer to "these parts of the code", do you mean loading/saving generally, or the particular parts of the loading/saving code that you have modified? I am familiar with the loading/saving code generally; is there a particular question that you have about this?

Thank you again for your work on this feature.

I mean the load/save functions found in each class, in particular the ones i was modifying (roads, vehicles, etc).

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19823
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Travel time based congestion
« Reply #18 on: May 16, 2020, 11:03:42 PM »
I mean the load/save functions found in each class, in particular the ones i was modifying (roads, vehicles, etc).

I am familiar with them to an extent, but the code is so huge that I am not intimately familiar with all of it and how everything relates to everything else, especially those parts of the code that have remained unchanged from Standard.

May I ask what specific thing that you wanted to know?

Online freddyhayward

  • Devotee
  • *
  • Posts: 224
  • Languages: EN
Re: Travel time based congestion
« Reply #19 on: May 17, 2020, 05:32:11 AM »
I am familiar with them to an extent, but the code is so huge that I am not intimately familiar with all of it and how everything relates to everything else, especially those parts of the code that have remained unchanged from Standard.

May I ask what specific thing that you wanted to know?
There was nothing I wanted to know specifically, except for whether any changes made are safe. Thus any relevant changes I'd make would have to be scrutinised. From memory, when I was working on this, I had to increment the version number and add yet another if-branch to avoid crashes.

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19823
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Travel time based congestion
« Reply #20 on: May 18, 2020, 11:10:05 AM »
Thank you. This may take some time to review/test in that case.

In the meantime, I had pushed on Saturday an interim change that doubled the reported congestion values - I should be grateful for people's feedback as to how well that this represents congestion.

Offline Freahk

  • Devotee
  • *
  • Posts: 1055
  • Languages: DE, EN
Re: Travel time based congestion
« Reply #21 on: May 18, 2020, 11:21:30 AM »
I should be grateful for people's feedback as to how well that this represents congestion.
In some cases it will over-estimate, in others under-estimate.
On average, doubled congestion should represent the actual situation a little better.
« Last Edit: May 18, 2020, 11:47:52 AM by Freahk »

Online freddyhayward

  • Devotee
  • *
  • Posts: 224
  • Languages: EN
Re: Travel time based congestion
« Reply #22 on: May 20, 2020, 07:41:35 AM »
I've now updated the branch. It compiles and runs, but seems to stop passengers from being generated at all. I'm not sure how this happened, since nothing in the branch directly changes passenger generation and the effects of congestion shouldn't be enough to reduce it to zero.

EDIT: This also occurs on the latest build, so it isn't related to my patch at all.
EDIT: Solved by https://github.com/jamespetts/simutrans-extended/commit/ca1f2d7fa4799dea65ad4b4b1ba038fc01b2ac20
EDIT: There is another remaining issue where buses are routed incorrectly compared to the latest master build.
EDIT: This issue has also been resolved.
« Last Edit: May 20, 2020, 02:19:18 PM by freddyhayward »

Online freddyhayward

  • Devotee
  • *
  • Posts: 224
  • Languages: EN
Re: Travel time based congestion
« Reply #23 on: May 20, 2020, 02:50:16 PM »
As far as I can tell, the branch is ready to be merged.

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19823
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Travel time based congestion
« Reply #24 on: May 22, 2020, 03:47:27 PM »
Thank you for your work on this. Unfortunately, this does not compile in Visual Studio: I get the following error:

Code: [Select]
Severity Code Description Project File Line Suppression State
Error C4716 'traffic_vehicle_t::get_max_speed': must return a value Simutrans-Extended C:\Users\James E. Petts\Documents\Development\Simutrans\simutrans-extended-sources\vehicle\simvehicle.h 48

I have pushed your branch merged with the current Simutrans-Extended master to the travel-time-congestion-2 branch. I should be grateful if you could look into this so that I can work on testing it. Thank you.

Online freddyhayward

  • Devotee
  • *
  • Posts: 224
  • Languages: EN
Re: Travel time based congestion
« Reply #25 on: May 23, 2020, 12:15:14 AM »
Thanks for pointing this out. I committed a fix on my branch which adds a default return value to that virtual function.

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19823
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Travel time based congestion
« Reply #26 on: May 23, 2020, 11:27:02 AM »
Thank you for fixing this: it now compiles. However, it fails on attempting to load saved games; the saved game format appears to have been changed incorrectly. For this reason, I have not been able to test the congestion feature itself. I should be grateful if you could look into this.

Online freddyhayward

  • Devotee
  • *
  • Posts: 224
  • Languages: EN
Re: Travel time based congestion
« Reply #27 on: May 23, 2020, 12:00:51 PM »
Thank you for fixing this: it now compiles. However, it fails on attempting to load saved games; the saved game format appears to have been changed incorrectly. For this reason, I have not been able to test the congestion feature itself. I should be grateful if you could look into this.
Thanks, I've just fixed this as well by incrementing the revision number again. The revision number will must always be one higher than current at the time of merging.

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19823
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Travel time based congestion
« Reply #28 on: May 23, 2020, 05:12:56 PM »
Thank you for this. I have spent several hours testing this. The latest version, merged with the latest master branch, and with some changes - explained below - is on my travel-time-congestion-2 branch.

This is looking good so far: testing shows sensible congestion numbers measuring over several months (aside from one issue: see below), no recorded adverse effect on performance according to profiling and the ability to remain in sync in a network game for an extended period of time.

There is one bug that I have noticed, however: dead end roads in cities, which are very common on their periphery, show an unreasonably high congestion number. This interferes with the accuracy of one of the new additions that I have made described below.

I have made two changes consequent upon this feature. The first is to recalibrate the congestion display in the minimap to show 250% instead of 100% as the most intense colour, as 100% is not a maximum given how we measure congestion. This produces more granularity of information and is thus more useful.

The second change that I have made is to change the city's congestion measurement (shown on the graph in the city information window) to use the congestion measured in actual tiles rather than a heuristic system that I developed a few years ago. The heuristic system is retained for use when assume_everywhere_connected_by road is enabled. However, this system now records unreasonably high numbers in cities owing to the bug described above.

Once the dead end roads bug has been fixed, this looks as though it will be ready to integrate. Thank you very much for your work on this: this is a significant enhancement.

Offline Freahk

  • Devotee
  • *
  • Posts: 1055
  • Languages: DE, EN
Re: Travel time based congestion
« Reply #29 on: May 23, 2020, 06:57:14 PM »
Just a guess on the dead-end congestion: Cars will enter the tile, move in one direction, "reverse" quickly and move back before leaving the tile again, so twice the expected time is spent on that tile. Just an idea what I would check first, might be I am entirely wrong.

Offline Milko

  • Devotee
  • *
  • Posts: 868
Re: Travel time based congestion
« Reply #30 on: May 23, 2020, 07:11:50 PM »
Hello

This effect, however, should not occur, it is true that the car goes back but it is also true that there is no traffic from the opposite direction.

Giuseppe

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19823
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Travel time based congestion
« Reply #31 on: May 23, 2020, 07:29:18 PM »
Indeed - this is a bug; but I think that Freahk meant that this was the most likely cause of the bug.

Online freddyhayward

  • Devotee
  • *
  • Posts: 224
  • Languages: EN
Re: Travel time based congestion
« Reply #32 on: May 24, 2020, 12:49:35 AM »
I have an idea of how to fix this, along with another problem, but I need help. The solution is simply to call flush_travel_times() whenever a citycar reverses on a tile, so that the travel time will be recorded twice for that tile - once when it reverses, and once when it leaves the tile. I just need help to find where exactly in the code this reversal occurs for buses and cars.

Another problem will be that buses record high amounts of congestion at stops because it takes them much more time than usual to cross a tile they stop at. This should be recorded by vehicles delayed by buses but not buses themselves. I'll attempt to fix this soon.

Online freddyhayward

  • Devotee
  • *
  • Posts: 224
  • Languages: EN
Re: Travel time based congestion
« Reply #33 on: May 24, 2020, 03:31:55 AM »
Actually, the congestion values on dead-ends are so absurdly high that it can't be explained by the extra time spent reversing. It could potentially related to the issue of signed/unsigned integers and over/underflows. I'll have to look into this more.

Online freddyhayward

  • Devotee
  • *
  • Posts: 224
  • Languages: EN
Re: Travel time based congestion
« Reply #34 on: May 24, 2020, 09:36:27 AM »
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.

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19823
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Travel time based congestion
« Reply #35 on: May 24, 2020, 10:56:38 AM »
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.

Offline Freahk

  • Devotee
  • *
  • Posts: 1055
  • Languages: DE, EN
Re: Travel time based congestion
« Reply #36 on: May 24, 2020, 02:40:17 PM »
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.

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19823
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Travel time based congestion
« Reply #37 on: May 24, 2020, 03:35:26 PM »
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).

Online freddyhayward

  • Devotee
  • *
  • Posts: 224
  • Languages: EN
Re: Travel time based congestion
« Reply #38 on: May 24, 2020, 10:33:08 PM »
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.

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19823
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Travel time based congestion
« Reply #39 on: May 25, 2020, 01:28:19 PM »
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.

Offline Freahk

  • Devotee
  • *
  • Posts: 1055
  • Languages: DE, EN
Re: Travel time based congestion
« Reply #40 on: June 13, 2020, 05:07:31 PM »
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.

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19823
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Travel time based congestion
« Reply #41 on: June 13, 2020, 07:14:35 PM »
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?

Offline Vladki

  • Devotee
  • *
  • Posts: 3328
    • My addons, mostly roadsigns, pak128.cs
  • Languages: EN, CS
Re: Travel time based congestion
« Reply #42 on: June 13, 2020, 11:11:12 PM »
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?

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19823
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Travel time based congestion
« Reply #43 on: June 13, 2020, 11:16:59 PM »
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.

Online freddyhayward

  • Devotee
  • *
  • Posts: 224
  • Languages: EN
Re: Travel time based congestion
« Reply #44 on: June 14, 2020, 12:25:43 AM »
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.

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19823
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Travel time based congestion
« Reply #45 on: June 14, 2020, 10:41:14 AM »
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.

Online freddyhayward

  • Devotee
  • *
  • Posts: 224
  • Languages: EN
Re: Travel time based congestion
« Reply #46 on: June 14, 2020, 10:57:53 AM »
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.

Offline Freahk

  • Devotee
  • *
  • Posts: 1055
  • Languages: DE, EN
Re: Travel time based congestion
« Reply #47 on: June 14, 2020, 01:07:35 PM »
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.

Offline Vladki

  • Devotee
  • *
  • Posts: 3328
    • My addons, mostly roadsigns, pak128.cs
  • Languages: EN, CS
Re: Travel time based congestion
« Reply #48 on: June 14, 2020, 07:18:54 PM »
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).

Online freddyhayward

  • Devotee
  • *
  • Posts: 224
  • Languages: EN
Re: Travel time based congestion
« Reply #49 on: June 15, 2020, 12:44:51 AM »
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.

Offline Freahk

  • Devotee
  • *
  • Posts: 1055
  • Languages: DE, EN
Re: Travel time based congestion
« Reply #50 on: June 15, 2020, 01:15:38 AM »
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.

Offline Vladki

  • Devotee
  • *
  • Posts: 3328
    • My addons, mostly roadsigns, pak128.cs
  • Languages: EN, CS
Re: Travel time based congestion
« Reply #51 on: June 15, 2020, 03:12:05 PM »
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.

Online freddyhayward

  • Devotee
  • *
  • Posts: 224
  • Languages: EN
Re: Travel time based congestion
« Reply #52 on: June 16, 2020, 12:34:53 AM »
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

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 19823
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Travel time based congestion
« Reply #53 on: June 16, 2020, 11:05:56 AM »
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.