feat: time tracking in Bidirectional A* by chrstnbwnkl · Pull Request #5640 · valhalla/valhalla

chrstnbwnkl · 2025-10-24T18:25:11Z

I wasn't happy with the refactoring I did over in #5638, so I tried again. This time I decided to just go for it and try to find a simple heuristic for estimating the time of arrival/departure on the "far-end" tree.

What this PR does:

adds time tracking to the time aware branch (depending whether it's arrive_by or depart_at/current)
for the non time aware expansion, there are now two options, and we let the user choose:
- invalid, the more conservative option; assumes no time on this expansion, just like in CostMatrix
- heuristic, uses a simple calculation based on costing's top_speed/fixed_speed parameters, the bee-line distance between the path edge snapped locations closest to origin/destination and a constant factor

What this PR doesn't include:

proper recosting logic, i.e. detect if recosting failed because of a timed access restriction and retry but without all the other relaxed parameters of a regular second pass. I figure this could happen in a future PR

The Factor

It's impossible to come up with something perfect of course, and maybe we can have an array of factors based on e.g. the flow mask or the rough bee line distance. I wrote a little program in Python that went over hundreds of routes in the de_benchmark_routes.txt, trying out factors in the range [1.0,5.0]. I used scipy.optimize.minimize_scalar to try to minimize the average difference between the estimation and the actual time, once with plain OSM and once with tiles built from a commercial provider, loaded with predicted speeds, and ran this for auto and truck.

I landed somewhere in the range of 1.49 - 1.89, but note that this was using inter-city routes in a not so small country (Germany). I assume the ideal factor will be higher for larger distances, so for now my first estimate is 2.1.

Note: 1713d97 lets you play around with this factor, it returns time_estimated in the route summary

…to cb-bidir-route-time

chrstnbwnkl · 2025-10-25T07:43:32Z

+                                                              kReverseTTHeuristicFactor,
+                                                              forward_time_info, costing_, arrive_by)
+                                   : TimeInfo::invalid());
+  }


on the "forward" expansion simply make a regular timeinfo object, and on the other one either

make a regular one if invariant

make in invalid one

or make one based on a heuristic

chrstnbwnkl · 2025-10-25T07:45:15Z

+    offset_time = time_info.forward(seconds_offset, static_cast<int>(nodeinfo->timezone()));
+  } else {
+    offset_time = time_info.reverse(seconds_offset, static_cast<int>(nodeinfo->timezone()));
+  }


This actually doesn't change at all, only the offset seconds may be 0 if the time isn't valid in the first place.

chrstnbwnkl · 2025-10-25T07:47:04Z

 | `admin_crossings` | When present and `true`, the successful route summary will include the two keys `admins` and `admin_crossings`. `admins` is an array of administrative regions the route lies within. `admin_crossings` is an array of objects that contain `from_admin_index` and `to_admin_index`, which are indices into the `admins` array. They also contain `from_shape_index` and `to_shape_index`, which are start and end indices of the edge along which an administrative boundary is crossed. |
-| `turn_lanes` | When present and `true`, each maneuver in the route response can include a `lanes` array describing lane-level guidance. The lanes array details possible `directions`, as well as which lanes are `valid` or `active` for following the maneuver.
+| `turn_lanes` | When present and `true`, each maneuver in the route response can include a `lanes` array describing lane-level guidance. The lanes array details possible `directions`, as well as which lanes are `valid` or `active` for following the maneuver. |
+| `reverse_time_tracking` | Which time tracking strategy to use on the non-time aware expansion in the bidirectional routing algorithm: `invalid` will assume no time, `heuristic` will try a best guess based on the bee line distance between origin and destination. Default `heuristic` |


As long as we don't have a battle tested heuristic, users should be able to opt out of it and choose the more conservative method.

should we mark it BETA? IMO ideally we'd remove this at some point when we either have a good feeling with a simpler heuristic or, less likely, make a more sophisticated one.

kevinkreiser · 2025-10-25T19:21:31Z

+    heuristic = 0;
+    invalid = 1;


did you do this on purpose to make the default (unset) value be new behavior? once upon a time i would be against this to avoid breaking existing users but honestly i feel like sometimes we have to move forward.

also nit: invalid seems a strange word choice, why not disabled or none or something along those lines

Well both options are new behavior. If someone wants old behavior, they can set date_time type to invariant.

Good point about naming, will change it to something more fitting.

nilsnolde · 2025-10-26T19:02:32Z

+    nodeinfo = endtile->node(directededge->endnode());
+    return time_info.forward(seconds, static_cast<int>(nodeinfo->timezone()));
+  } else {
+    // in case of depart_at, we want the start node of our correlated edge


Not sure we need differentiate which node we take, unless we do better guessing based on the percent_along. TBH I'm ok with leaving a comment and simply take the first or last node no matter if fwd/rev

I think you might be right, using percent along would be the best we could do probably.

nilsnolde · 2025-10-26T19:11:12Z

+               : distance_meters / (fixed_speed_ * midgard::kKPHtoMetersPerSec) * factor *
+                     0.85; // if fixed speed, the factor should be lowered


can you comment why it's lower? somehow I don't quite get it

a vehicle likely won't travel much at top speed, so the actual time will differ from the ideal time both in distance traveled and speed. If fixed speed is set, we know the exact speed and just have to correct the estimate based on bee-line vs real distance, so the difference (what we're trying to correct for using the factor) won't be as large. I can leave a comment above that line.

nilsnolde

looks like a good start! just a few suggestions, and pls some docstrings :)

…to cb-bidir-route-time

…flow/predicted

chrstnbwnkl · 2025-10-29T12:37:47Z

+        second_of_week = 28800; // arbitrary time to land us within the constrained time window
+      } else if (initial_flow_mask & kFreeFlowMask) {
+        second_of_week = 0; // ... or within the free flow window
+      }


this was necessary to keep getting free flow/constrained speeds. This is because of the change in GraphTile::GetSpeed: before, passing an invalid time and the respective mask would give you the one you wanted, faded with live speed. Now you can only fade them with live speed if the time is valid, so it would use that time to see in which time window you are (either free flow or constrained), so you could only get either one or the other. So we just set it to a value here to make the time fall into the window we want.

chrstnbwnkl · 2025-10-29T12:43:58Z

+  EXPECT_NEAR(edges[1]["speeds_faded"]["predicted_flow"].GetInt(),
+              current * multiplier_inverse + predicted * multiplier, 1);
+  EXPECT_NEAR(edges[1]["speeds_faded"]["no_flow"].GetInt(),
+              current * multiplier_inverse + base * multiplier, 1);


The only thing that changed here are the multipliers, which I am pretty sure is due to meili/trace_attributes being non-time aware: before, it would always use live speeds, regardless of the date time, but now it will just fall back to constrained/free_flow if available.

chrstnbwnkl · 2025-10-29T12:53:25Z

@janusz-anue Just a heads-up: I had to tweak the logic for getting faded/non-faded speed attributes a little to not break that functionality. Would appreciate it if you could have a quick look at some point!

The only change that made this necessary is that we'd now require a valid time to get live speeds:

valhalla/valhalla/baldr/graphtile.h

Lines 665 to 667 in bd81efc

    
           auto invalid_time = seconds == kInvalidSecondsOfWeek; 
        
           if (!invalid_time && (flow_mask & kCurrentFlowMask) && traffic_tile() && 
        
               live_traffic_multiplier != 0.) {

nilsnolde

looks good, other than possibly having spotted a bug. but I might have a knot in my brain as well..

nilsnolde · 2025-11-02T16:44:53Z

 | `admin_crossings` | When present and `true`, the successful route summary will include the two keys `admins` and `admin_crossings`. `admins` is an array of administrative regions the route lies within. `admin_crossings` is an array of objects that contain `from_admin_index` and `to_admin_index`, which are indices into the `admins` array. They also contain `from_shape_index` and `to_shape_index`, which are start and end indices of the edge along which an administrative boundary is crossed. |
-| `turn_lanes` | When present and `true`, each maneuver in the route response can include a `lanes` array describing lane-level guidance. The lanes array details possible `directions`, as well as which lanes are `valid` or `active` for following the maneuver.
+| `turn_lanes` | When present and `true`, each maneuver in the route response can include a `lanes` array describing lane-level guidance. The lanes array details possible `directions`, as well as which lanes are `valid` or `active` for following the maneuver. |
+| `reverse_time_tracking` | Which time tracking strategy to use on the non-time aware expansion in the bidirectional routing algorithm: `disabled` will assume no time, `heuristic` will try a best guess based on the bee line distance between origin and destination. Default `heuristic` |


I asked about labeling it maybe BETA but maybe you didn't see that: #5640 (comment). WDYT?

nilsnolde · 2025-11-02T16:55:52Z

  }

+  enum ReverseTimeTracking {
+    heuristic = 0;


maybe prefix the members with rtt_ or so. a very annoying thing in pbf is that enum members are children of the parent, i.e. this is Options::disabled etc, where disabled is a bit generic for the whole Options object

nilsnolde · 2025-11-02T17:27:15Z

+    nodeinfo = tile->node(opp_edge->endnode());
+  }
+
+  return arrive_by ? time_info.forward(seconds, static_cast<int>(nodeinfo->timezone()))


shouldn't this be the other way around? if we're on arrive_by, the time_info here is somewhere in the future (at the destination) and we want to go back in time to propose an origin date_time, no?

ah yes, obviously 😄

nilsnolde · 2025-11-02T17:56:02Z

 }

-TEST_F(MatrixTrafficTest, TDMatrixWithLiveTraffic) {
+TEST_F(MatrixTrafficTest, DISABLED_TDMatrixWithLiveTraffic) {


why disable these?

Currently rewriting these because the ones testing CostMatrix are not working as expected anymore: we used to test live traffic with type set to "current" and would also get the current live speed on the reverse branch, but now we won't, so CostMatrix does not find the optimal path for that particular scenario.

nilsnolde · 2025-11-02T17:57:50Z

+  if (arrive_by) {
+    reverse_time_info = TimeInfo::make(destination, graphreader, &tz_cache_);
+    forward_time_info =
+        reverse_time_tracking == Options_ReverseTimeTracking_heuristic


personally I prefer Options::heuristic notation, I find these really hard to read.

…to cb-bidir-route-time

chrstnbwnkl · 2025-11-20T14:40:25Z

+        second_of_week = 0;
+      }
+      if (initial_flow_mask == kConstrainedFlowMask) {
+        second_of_week = 28800; // arbitrary time to land us within the constrained time window


make this a constant (or see if there is one)

chrstnbwnkl · 2025-11-20T14:51:16Z

+        {"DE", {{"highway", "primary"}, {"maxspeed", "100"}}},
+        {"EF", {{"highway", "primary"}, {"maxspeed", "100"}}},
+        {"FG", {{"highway", "primary"}, {"maxspeed", "100"}}},
+    };


see if I can somehow snoop on what the algorithm is actually doing to make sure time is forwarded/reversed correctly.

kevinkreiser

maybe a constant for the constrained week time and maybe see if refactoring the testing to see inside about what its doing with the time tracking is possible but dont let it stop you from merging

…to cb-bidir-route-time

chrstnbwnkl · 2025-11-25T11:22:31Z

I couldn't find an easy way to really snoop on what the algorithm's doing, but I modified the fake costing class so that we record time info objects passed to EdgeCost only when an edge is first reached to make sure we're not looking at time info passed via recosting.

chrstnbwnkl added 2 commits October 24, 2025 19:55

use this commit to tune factor

1713d97

reverted all the param tuning code

de59d19

chrstnbwnkl mentioned this pull request Oct 24, 2025

Add proper time tracking to Bidirectional A* forward expansion #5638

Closed

chrstnbwnkl added 3 commits October 24, 2025 20:25

Merge branch 'master' into cb-bidir-route-time

70bfc94

changelog, docs, change default

c7efbf2

Merge branch 'cb-bidir-route-time' of github.com:valhalla/valhalla in…

68cf91e

…to cb-bidir-route-time

chrstnbwnkl commented Oct 25, 2025

View reviewed changes

some small oversights

5c26f4e

kevinkreiser reviewed Oct 25, 2025

View reviewed changes

nilsnolde reviewed Oct 26, 2025

View reviewed changes

chrstnbwnkl added 7 commits October 27, 2025 16:25

address comments

2b52003

temporarily disable matrix tests

157d20c

fix speed attributes test

4b181e7

Merge branch 'master' into cb-bidir-route-time

c313821

more concise...

591527d

Merge branch 'cb-bidir-route-time' of github.com:valhalla/valhalla in…

242579d

…to cb-bidir-route-time

really only mess with the time if we're sure we only care about free_…

81ab95a

…flow/predicted

chrstnbwnkl commented Oct 29, 2025

View reviewed changes

get current flow even if no date time is set in the request

bd81efc

chrstnbwnkl added 2 commits October 29, 2025 22:21

change this to what it was before

8f2821f

Merge branch 'master' into cb-bidir-route-time

9260a70

nilsnolde reviewed Nov 2, 2025

View reviewed changes

chrstnbwnkl added 2 commits November 4, 2025 11:19

minimal matrix test

dd51fc4

somethings definitely fishy with live traffic in tdmatrix

affb31a

chrstnbwnkl mentioned this pull request Nov 11, 2025

add flow_sources to expansion properties #5697

Merged

chrstnbwnkl added 10 commits November 11, 2025 21:59

Merge branch 'master' into cb-bidir-route-time

6a153db

merge master

6bfa187

Merge branch 'cb-bidir-route-time' of github.com:valhalla/valhalla in…

61610cf

…to cb-bidir-route-time

Merge branch 'master' into cb-bidir-route-time

6e5179c

merge master

420ffc0

merge master

a6d04f3

Merge branch 'cb-bidir-route-time' of github.com:valhalla/valhalla in…

69aabee

…to cb-bidir-route-time

fix test after merging master

4c0e573

whoops

6aea87c

merge master

3ac9acf

chrstnbwnkl commented Nov 20, 2025

View reviewed changes

kevinkreiser previously approved these changes Nov 20, 2025

View reviewed changes

chrstnbwnkl added 4 commits November 20, 2025 23:04

Merge branch 'master' into cb-bidir-route-time

ace016e

merge master

7be3e3b

improve tests

da9e8a3

Merge branch 'master' into cb-bidir-route-time

7b5f48f

chrstnbwnkl dismissed kevinkreiser’s stale review via 7b5f48f November 25, 2025 11:20

Merge branch 'cb-bidir-route-time' of github.com:valhalla/valhalla in…

59f5a6c

…to cb-bidir-route-time

Merge branch 'master' into cb-bidir-route-time

7607507

kevinkreiser approved these changes Dec 2, 2025

View reviewed changes

chrstnbwnkl added 2 commits December 2, 2025 16:55

Merge branch 'master' into cb-bidir-route-time

05e340e

Merge branch 'master' into cb-bidir-route-time

13175b7

chrstnbwnkl enabled auto-merge (squash) December 2, 2025 19:45

chrstnbwnkl merged commit 5b66049 into master Dec 2, 2025
18 checks passed

chrstnbwnkl deleted the cb-bidir-route-time branch December 2, 2025 20:35

chrstnbwnkl mentioned this pull request May 29, 2026

Bidirectional A* will use live traffic on the reverse expansion, regardless of date time #5616

Closed

azime pushed a commit to hove-io/valhalla that referenced this pull request Jun 4, 2026

feat: time tracking in Bidirectional A* (valhalla#5640)

ce4e479

		: distance_meters / (fixed_speed_ * midgard::kKPHtoMetersPerSec) * factor *
		0.85; // if fixed speed, the factor should be lowered

Conversation

chrstnbwnkl commented Oct 24, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

What this PR does:

What this PR doesn't include:

The Factor

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

nilsnolde Oct 26, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

nilsnolde left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

chrstnbwnkl commented Oct 29, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

nilsnolde left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

kevinkreiser left a comment

Choose a reason for hiding this comment

Uh oh!

chrstnbwnkl commented Nov 25, 2025

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

chrstnbwnkl commented Oct 24, 2025 •

edited

Loading

nilsnolde Oct 26, 2025 •

edited

Loading

chrstnbwnkl commented Oct 29, 2025 •

edited

Loading