News:

Simutrans.com Portal
Our Simutrans site. You can find everything about Simutrans from here.

Pull Request: Private Car Routing Adjustment

Started by PJMack, April 30, 2021, 12:49:24 AM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

PJMack

This pull request, already on GitHub (https://github.com/jamespetts/simutrans-extended/pull/374), adjusts the car routing to give preference to one way roads, and avoid cities, crossing, and intersections.  This would hypothetically reduce private car driving calculations by steering private cars away from situations where more calculations are needed, however there would be a slight increase in private car routing calculations, which do not need to be done in real-time. The positive side effects of this is the reduction of in-city congestion, as well as encouraging the placement of "ring-roads" or "beltways" around cities.

Mariculous

#1
First, I'd like to welcome you to Simutrans (extended)

Improving this situation had been considered but coding ressoources in simutrans are quite limited, thus any work on this is appreciated.
Your approach seems quite simple and I like the idea of attracting more cars to use two-lane roads and to get cars out of town as we all know towns are usually rather congested due to many cars moving around in heuristics mode and two-lane roads can carry more cars in the same time than normal roads can do.

However, I see a big issue in here: The journey time of cars is quite important to decide if a passenger will take the car or public transport, so we should never advert a speed that in practice cannot be reached!
Otherwise, this false promise will move even more passengers on the road causing even more jams although the road capacities might be used more optimally.

So my personal conclusion:
I like the idea of a (simple) road capacity estimation, but we have to ensure that we never promise speeds that cannot be reached, not even in theory.

One solution might be to split route costs from journey times, where costs are used to calculate the "best" (not anymore the fastest) route and the (expected) journey time of that calculated route is then used to decide if a passenger will go by car or public transport.
The same might be used to at least reduce the flip-flop effect of congested roads by considering congestion only by a small factor when calculating routes, but using the full recored congestion when calculating the expected journey times.
Both are just estimations, so we'll have to test in practice if this works well or not.

PJMack

Thank You.  I did not realize the potential effects on the transit vs private car decision.  Such effect may not be unrealistic as the Eisenhower highway system did have an effect on rail in the United States, however it may not be desirable to have in simutrans-extended.  My original intent was model the (not un-)common overestimate of the speed boost provided by divided highways. 

In the meantime, I did do some benchmarks with a mature single player game with a 1280x1280 map, 45 cities totaling to 1.3 Million inhabitants, timeline year 2003.  After 3 in-game months of with vs without the pull request (loading from the same savegame, which is too large to post), there was a negligible increase (1.99M vs 1.93M) in global private car usage, negligible effect on my largest hub station, but a 30% decrease (42 vs 63) in congestion in the largest central city, as well as a ~20-30% increase in overall performance (based on simloops during fast-forward).

In any case, the constants in the pull request could be adjusted.

jamespetts

Thank you very much for your work on this: this is much appreciated. This will need, I think, some careful thought before it can be integrated. One of the important principles in Simutrans-Extended is that passengers route by journey time. Thus, if there is a situation in which the fastest journey by car is faster than the fastest journey by public transport, players will take the car; whereas, if the fastest journey by public transport is faster, passengers will take public transport (unless they have been randomised always to prefer to travel by car when the journey time is within their tolerance). Likewise, passengers will not travel at all if the journey time is outside their tolerance.

Therefore, any system that does not choose the fastest journey time for private cars risks distorting economics in the game. I note that the overall assessment on a larger map is that private car usage was reduced by circa 4% when implementing this feature; but that might mask very large reductions in some localised areas where a non-time-based routing system might create perverse incentives.

Given that the game mechanics already do encourage the use of ring roads (on the basis that these should be less congested, and therefore the travel time lower, than city roads), it would helpful to have a little more detail on why it is that you think that the current mechanics (a purely time based routing) do not allow for this?

Thank you again for your work on this.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

PJMack

My original intent was to decrease traffic in a manner that does not make it too unrealistic.  I noticed that a side effect of the caching of the cost in the private_car_destination_finder_t::get_cost() function, is that intersection congestion was not being taking into account.  The simplest solution to that was to simply add a general speed penalty to intersections.  (Looking at the code again now, it appears that the caching may cause the routing to only takes into account the congestion of the first tile in the city, and it looks like it may use the congestion of the previous city if the entrance is a diagonal?)  Additionally, I wanted to compensate for the speed lost by railroad crossings.  For the other two adjustments, I wanted to model the assumptions that cities tend to be congested, and divided highways fast, even though such assumptions tend to be false, however I may have overdone it with the constants.

At this point, would it be more appropriate to move this into a feature request, rather than a pull request?  Either way, hopefully this helps with the discussion.  Thanks.

freddyhayward

Are you familiar with the existing congestion system? Though it is certainly flawed, it still accounts for everything you have mentioned here.

Mariculous

#6
I guess I get the point of the adjustment.

The congestion stats are quite preciese data, but that data is from the past, given a specific private car route network and the route calculation does not take any care of "how many cars a road can hold" before it will be seriously congested.
In different words, the route calculation assumes that changing routes does not have an effect on congestion.
This assumption is fine if there are rather continous recalculations, but it causes the flip-flop effect when recalculations are rather rare and the whole route network is flipped at once.

The above adjustment seems to aim at guessing where it's rather likely to support huge traffic flows and where it's not.
A simple guess might work, but in any case it should not adjust the jorney time expectation in a way that is not at all represented by the infrastructures.

In the very first place, we should attempt to reduce the flip-flop effect by itself, instead of placing guesses on which routes might work best.


freddyhayward

What I'm trying to ask is whether the adjustments are made with improving the existing congestion system in mind, or whether it was made without knowing about it at all.

PJMack

Yes, I was aware of the existing route-around-congestion code, and was attempting to supplement it.

To start from the beginning, about a month ago, when I was playing simutrans-extended on a map with some large cities, I found the congestion in the cities made the game nearly unplayable.  I had placed divided beltways (ring-roads) around cities, however, in a cyclic pattern, the beltways would become overcrowded, and traffic would divert to the cities, making traffic even worst.  I had also noticed that given equal choice in route between a crossing and a bridge over it, the cars were choosing the crossing.  At that point I started looking at the existing code (starting with the diff for the private_car_memory_saving pull request, good job by the way) and noticed that, as Freahk noted, it only takes into account the traffic of the previous month, and due to the caching of the get_cost function, did not appear to me to be handling intersections properly.  About three weeks ago, I added code into the get_cost function to increase the cost of crossings and cities, and reduce the cost of freeways.  (It was upon implementing the latter that I realized that I could speed up ribi_t a bit, hence the other pull request) About a week ago, I had considered making this a feature request with an attached patch file, however I had, at that point already planned the other pull request while I still had some free time; and the code was already tested.

One option I did consider, but thought may decrease routing performance too much, was to have the city avoidance be based on the congestion, population, and/or area of the city in question.  Another would be having the constants set-able in the simuconf.tab file, but again, may cause a larger impact on routing performance.

jamespetts

Thank you all for your contributions to this, and apologies again for not having been able to respond sooner.

QuoteI had placed divided beltways (ring-roads) around cities, however, in a cyclic pattern, the beltways would become overcrowded, and traffic would divert to the cities, making traffic even worst.

The real underlying issue, I think, is the reference to the cyclic pattern. The problem currently is that, every time that a new road decreases congestion somewhere, one the decreased congestion is recorded, all the routes will go through the formerly congested area again as it has now been recorded as having low congestion, leading to a constant oscillation without ever reaching an equilibrium. This means, in turn, that crowded city centres fail half the time to be relieved by bypasses, ringroads, etc. whereas they should be relieved all of the time.

The correct solution to this, I think, is not to add extra heuristics for city avoidance on top of the existing model (which is liable to cause distortions and problems of its own), but rather refine the existing model so that it can reach an equilibrium state.

Thus, what needs to happen is that the decay period for congestion data needs to synchronise with the refresh period for private car routes, and old congestion data, instead of being discarded completely, need to be downgraded gradually in prominence as new congestion data are added. To avoid using unreasonable amounts of memory, I suggest that this be done by new congestion data being averaged with current congestion data to produce the new congestion datum instead of simply replacing the old congestion data, which will thus cause old congestion values to decay away slowly. When combined with synchronising the replacement of congestion data with the timing of the route refresh, this should allow the congestion responsiveness of the private vehicle pathfinding algorithm to reach an equilibrium, solving the underlying problem.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

PJMack

#10
Thank You. I have implemented the synchronization and rolling average and am testing it now.  I created a draft pull request, however I also included the patch file below to make it more accessible.  In the meantime, I have closed the other pull request as I agree that this should be tried first, and it can be reopened if needed.

diff --git a/boden/wege/weg.cc b/boden/wege/weg.cc
index 6febd933f..1edebc89a 100644
--- a/boden/wege/weg.cc
+++ b/boden/wege/weg.cc
@@ -1658,15 +1658,19 @@ void weg_t::new_month()
                statistics[0][type] = 0;
        }

-       for (int type=0; type<MAX_WAY_TRAVEL_TIMES; type++) {
-               for (int month=MAX_WAY_STAT_MONTHS-1; month>0; month--) {
-                       travel_times[month][type] = travel_times[month-1][type];
-               }
-               travel_times[0][type] = 0;
-       }
+
        wear_way(desc->get_monthly_base_wear());
}

+void weg_t::step_travel_times(){
+       for (int type=0; type<MAX_WAY_TRAVEL_TIMES; type++) {
+               for (int month=MAX_WAY_STAT_MONTHS-1; month>0; month--) {
+                       travel_times[month][type] /= 2;
+                       travel_times[month][type] += travel_times[month-1][type] / 2;
+               }
+               travel_times[0][type] = 0;
+       }
+}

// correct speed and maintenance
void weg_t::finish_rd()
diff --git a/boden/wege/weg.h b/boden/wege/weg.h
index 431393791..7759f4e53 100644
--- a/boden/wege/weg.h
+++ b/boden/wege/weg.h
@@ -574,6 +574,8 @@ public:
        runway_directions get_runway_directions() const;
        uint32 get_runway_length(bool is_36_18) const;

+       void step_travel_times();
+
        //void increment_traffic_stopped_counter() { statistics[0][WAY_STAT_WAITING] ++; }
        inline void update_travel_times(uint32 actual, uint32 ideal)
        {
diff --git a/simworld.cc b/simworld.cc
index ad2a5061c..6fe10936f 100644
--- a/simworld.cc
+++ b/simworld.cc
@@ -6142,6 +6142,9 @@ void karte_t::refresh_private_car_routes() {
        for(auto & city : stadt) {
                cities_awaiting_private_car_route_check.insert(city);
        }
+       for(auto & w : weg_t::get_alle_wege()){
+               w->step_travel_times();
+       }
}

void karte_t::clear_private_car_routes() {

edit: fixed typo in code

PJMack

Upon testing, with my map, the synchronization and rolling averaging appeared to make the issue of traffic worst.  I therefore closed the second pull request.

I updated the original pull request, changing the assumption of one-way roads being 50% faster to two-way roads being 25% slower, which appears to be a medium to what I had originally and the master branch for traffic and performance.  Nonetheless, I left it in the closed state to give the situation a little more thought.

freddyhayward

I am beginning to agree with Freahk's assessment. It might be impossible to achieve an 'equilibrium' so long as the algorithm finds the single best route to a destination, since all traffic will use the best route and exceed its capacity, even if comparable routes exist. I don't see how any combination of synchronisation, rolling averages, or heuristics could solve the problem. The same problem affects the path explorer for public transport through increasing wait times, especially for freight, though its impact is less severe given its higher capacity compared to private traffic.

Ranran(retired)

In master branch, even excluding the camera rotation, I think it sometimes causes a crash.
ひめしという日本人が開発者達の助言を無視して自分好みの機能をextendedに"強引に"実装し、
コードをぐちゃぐちゃにしてメンテナンスを困難にし(とりわけ道路と建物関連)、
挙句にバグを大量に埋め込み、それを知らんぷりして放置し(隠居するなどと言って)別のところに逃げ隠れて自分のフォーク(OTRP)は開発を続けている
その事実と彼の無責任さに日本人プレイヤーは目を向けるべき。らんらんはそれでやる気をなくした(´・ω・`)
他人の振り見て我が振り直せ。ひめしのようにならないために、らんらんが生み出したバグや問題は自分で修正しなくちゃね(´・ω・`)

PJMack

Though some un-equilibrium may be inevitable, I believe there is still some room for improvement. 

After going through the existing algorithms again, I found two potential problems.  For the first of which, I confirmed my suspicion before in that the caching of the cost information is incorrect.  After temporarily moving the congestion percentage calculation to the top of the get_cost function (just below checking that the way still exists), and running with breakpoints at the return statements for that function, I found that even when using the same cached cost, the congestion percentages ranged from 70 to 750!  The second issue is that the speed calculation in the get_cost function produces nonlinear results relative to the inverse of the recorded times ratio.  Although that may be deliberate, the non-linearity is also dependent on the speed limit for the road in such way that if the average speed on a city road (48kmh limit) is 40kmh and the average speed on a highway (96kmh limit) is also 40kmh, the speed variable in the get_cost function is 42kmh for the city road and 28 for the highway, which puts more weight on cities than country highways.  I put a GNU Octave program that charts the speed graph as existing below, and have confirmed these with the breakpoints as described above.  I am assuming that the unit conversions are correct as existing.

I am trying out on a new (not yet pushed) branch with the caching of costs removed from the get_cost function, and the speed calculation linear excepting the 4kmh minimum. 



GNU Octave graph of average speed recorded vs speed used by current routing algorithm for various road speed limits.
x=0:(0.01):1;
p=100 ./ x - 100;
s=1 - p ./ 200;
plot(l .* x', max (l .* s', 4))
xlabel ("Speed Recorded")
ylabel ("Speed Used by Cost Function")
legend({"Speed Limit 15","Speed Limit 48", "Speed Limit 50", "Speed Limit 64", "Speed Limit 80", "Speed Limit 96", "Speed Limit 115"},"location","southeast")



Ranran, It looks like the error is in a different thread, as no pthread function is accessed in that function. After a partially successful attempt at Google Translate's handwriting feature, it appears that the dll referred to may be missing from your system.  I do not think the error is related to this or the previous pull request (The forum discussion for that moved to the incorporated pull requests section of the forum in https://forum.simutrans.com/index.php/topic,20901.0.html); you may want to file a general bug report.

PJMack

After testing, it appears that traffic is flowing smoothly, and I have made a new pull request with the aforementioned changes. Furthermore, the behavior is as originally intended; without the heuristics.



An afterthought on the synchronization attempted before: I believe, from observations, that the reason it made traffic worst is that it resulted in the routes of several cities being the same for several sections of map (particularly places where only a few roads connected continents) whereas allowing the congestion calculations to change during routing results in a higher variety of routes chosen.

Ranran(retired)

#16
Quote from: PJMack on May 26, 2021, 09:03:02 PMI do not think the error is related to this or the previous pull request
EDIT:
227befa2a0a4530fa2f84450f8aef5dbbc20f498
d61a1a9bda0261a36d261c65090b4d6466427506
I have confirmed that if revert these two commits, the crash no longer occurs.
I accidentally reverted only #227befa at first, but then the crash occurred. So I think it's due to your previous pull request.
This crash is 100% caused by camera rotation in demo.sve, so you need to make sure that this crash can be reproduced with a new pull request too.
ひめしという日本人が開発者達の助言を無視して自分好みの機能をextendedに"強引に"実装し、
コードをぐちゃぐちゃにしてメンテナンスを困難にし(とりわけ道路と建物関連)、
挙句にバグを大量に埋め込み、それを知らんぷりして放置し(隠居するなどと言って)別のところに逃げ隠れて自分のフォーク(OTRP)は開発を続けている
その事実と彼の無責任さに日本人プレイヤーは目を向けるべき。らんらんはそれでやる気をなくした(´・ω・`)
他人の振り見て我が振り直せ。ひめしのようにならないために、らんらんが生み出したバグや問題は自分で修正しなくちゃね(´・ω・`)

PJMack

Ranran, I must apologize as it seams you are correct in the rotation causing an error with my previous pull request.  It also appears that I had mistranslated the the debugging information; as such could you please translate the last lines of the screenshot into English?

As this error is not related to this new proposed pull request, we can continue this conversation in the bug report.

jamespetts

#18
PJMack - thank you very much for your work on this: this is most interesting. Can I check what pull request that I should be looking for here? The private car routing improvements branch seems to contain all of the original heuristic systems, but it is not immediately clear whether the later changes have removed these. Can you clarify? Thank you.

Edit: I notice that you have removed the diagonal cost adjustment. This will mean that each diagonal route will have too high a cost (i.e. the Manhattan distance). May I ask what the reason for this is?

Edit 2: I have now isolated and incorporated just the adjustment/correction to the congestion percentage timing after having tested this and found it to be stable. Can I ask you to check whether there is any critical part of this patch that I have missed? Otherwise, I should be interested in others' views on how this plays out in operation from to-morrow's nightly build.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

PJMack

Rather than making a third pull request for this topic, I removed the heuristics from the original pull request and added the new changes.  For the diagonals, I am not sure where you are looking at, but the code to handle diagonals (weg.cc lines 6028-6036 originally, weg.cc lines 6006-6014 in the Pull Request) were not touched in the pull request. The other critical part of the pull request was the removal of the caching of the cost, as that lead to erroneous (almost random) costs relative to the actual congestion percentages.

jamespetts

Quote from: PJMack on May 29, 2021, 04:40:40 PM
Rather than making a third pull request for this topic, I removed the heuristics from the original pull request and added the new changes.  For the diagonals, I am not sure where you are looking at, but the code to handle diagonals (weg.cc lines 6028-6036 originally, weg.cc lines 6006-6014 in the Pull Request) were not touched in the pull request. The other critical part of the pull request was the removal of the caching of the cost, as that lead to erroneous (almost random) costs relative to the actual congestion percentages.

I was looking at the files changed interface, which I thought to be a summary of the cumulative effect of all the commits. Is that not the case?
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

PJMack

Yes that is the case.  The heuristics are not there, and the diff does not indicate a change lines handling the diagonals.  (The lines are hidden the the diff, expanding where it says "@@ -6047,14 +6025,6 @@" will show the diagonals still there).

jamespetts

Quote from: PJMack on May 29, 2021, 08:00:25 PM
Yes that is the case.  The heuristics are not there, and the diff does not indicate a change lines handling the diagonals.  (The lines are hidden the the diff, expanding where it says "@@ -6047,14 +6025,6 @@" will show the diagonals still there).

I am very confused: if you click the link, you will see that the only change apart from the one that I made is removing all of the diagonal cost adjustment. Can you recheck?
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

PJMack

This may clear things up.  Following is the get_cost function in the branch that I made the pull request with. 
int private_car_destination_finder_t::get_cost(const grund_t* gr, sint32 max_speed, koord)
{
const weg_t *w = gr->get_weg(road_wt);
if(!w)
{
return 0xFFFF;
}

const sint32 max_tile_speed = w->get_max_speed(); // This returns speed in km/h.
const bool is_diagonal = w->is_diagonal();

sint32 speed = min(max_speed, max_tile_speed);

#ifndef FORBID_CONGESTION_EFFECTS
const sint32 congestion_percentage = w->get_congestion_percentage();
if (congestion_percentage)
{
speed = speed * 100 / (100 + congestion_percentage);
speed = max(4, speed);
}
#endif

// Time = distance / speed
int mpt;

if(is_diagonal)
{
// Diagonals are a *shorter* distance.
mpt = ((int)meters_per_tile_x100 * 5) / 7;
}
else
{
mpt = (int)meters_per_tile_x100;
}

// T = d / (1000 / h)
// T = d / (h * 1000)
// T = d / ((h / 60) * (1000 / 60)
// m == h / 60
// T = d / (m * 16.67)
// (m / 100)
// T = d / ((m / 100) * (16.67 / 100)
// T = d / ((m / 100) * 0.167)
// T = (d * 100) / (m * 16.67) -- 100THS OF A MINUTE PER TILE

const int cost = mpt / ((speed * 167) / 10);

return cost;
}

Are the diagonals not taken care of in the lines:
if(is_diagonal)
{
// Diagonals are a *shorter* distance.
mpt = ((int)meters_per_tile_x100 * 5) / 7;
}
else
{
mpt = (int)meters_per_tile_x100;
}

jamespetts

None of those parts of the code are changed by the code in the pull request if the "show files" dialogue correctly summarises the changes - all that it does other than change the congestion speed reduction calculation is remove some lines specifically relating to the diagonal cost.

Nothing in this page appears to have anything to do with caching the congestion data. Can you elaborate on which lines of which file is affected by this?
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

jamespetts

Actually, is the caching in this part of the code?


if(city == last_city && max_tile_speed == last_tile_speed)
{
// Need not redo the whole calculation if nothing has changed.
if(is_diagonal && last_tile_cost_diagonal > 0)
{
return last_tile_cost_diagonal;
}
else if(last_tile_cost_straight > 0)
{
return last_tile_cost_straight;
}
}


And is the removal of the diagonal cost calculation removing it insofar as it affects this part of the code?
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

PJMack

Our messages seam to be crossing, as I was just about to send the message below when I saw yours.  Yes that is what I am referring to as caching.  As it was causing an error of a factor of 10, diagonals verse straight was not the issue of discrepancy in what is saved in last_tile_cost_* within the if statement verses what the calculated cost should have been.  I am still not sure where you are seeing that I removed the diagonal adjustment, as the lines regarding it are still in it as described below.


Now I see the confusion, and must apologize as I could have made myself clearer. Caching was probably the wrong term to use, though I am not exactly sure what the right term is.  The get_cost function was saving the last cost returned in either last_tile_cost_diagonal or last_tile_cost_straight (as appropriate) for reuse on the next call to such function assuming the city is the same one.  The code for saving
if(is_diagonal)
{
last_tile_cost_diagonal = cost;
}
else
{
last_tile_cost_straight = cost;
}

uses the last cost calculated for diagonal or straight.  This code I removed since the code for reusing
if(city == last_city && max_tile_speed == last_tile_speed)
{
// Need not redo the whole calculation if nothing has changed.
if(is_diagonal && last_tile_cost_diagonal > 0)
{
return last_tile_cost_diagonal;
}
else if(last_tile_cost_straight > 0)
{
return last_tile_cost_straight;
}
}

assumed that the cost was the same throughout the entire city or entire countryside, which is not the case.  I also removed those lines, as well as the city, last_city, last_tile_speed, last_tile_cost_diagonal, and last_tile_cost_straight definitions and assignments as they are no longer needed.  I did not touch the lines that correlate to the diagonal verses strait calculations:

const bool is_diagonal = w->is_diagonal();
...
if(is_diagonal)
{
// Diagonals are a *shorter* distance.
mpt = ((int)meters_per_tile_x100 * 5) / 7;
}
else
{
mpt = (int)meters_per_tile_x100;
}
const int cost = mpt / ((speed * 167) / 10);
return cost;


jamespetts

Ahh, I understand now. My apologies for the misunderstanding. I have now incorporated this. Thank you.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.