Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Query-time conditional edge-weights #2377

Closed
danpat opened this issue May 5, 2016 · 6 comments
Closed

Query-time conditional edge-weights #2377

danpat opened this issue May 5, 2016 · 6 comments

Comments

@danpat
Copy link
Member

danpat commented May 5, 2016

This ticket is to discuss our options with CH for implement conditional edge weights - the ability to adjust some edge weights at query time.

The implication here is that we would not contract nodes involved in these edges. This will obviously hit query performance on two fronts:

  • slower queries because of shorter short-cuts and more time spent on core (uncontracted) routing
  • additional cost of evaluating the query-time weight calculations

Why are we considering this:

  • on-the-fly traffic data lookup
  • time-dependent turn restrictions
  • road-class avoidance (avoid ferries, toll roads, etc)

The basic idea would be this:

  • identify edges that require conditional evaluation, do not contract them
  • at query time, if we examine one of these edges, calculate its weight on-the-fly

I can currently picture four conditional operators we might want to support:

  • a time-dependent yes/no evaluation - to support conditional turn restrictions
  • a time-dependent weight adjustment - to support a historical model of traffic data on certain roads
  • user-supplied "avoid" parameter - add weight to certain edges that the user wants to avoid, per-query (we would only support a limited set of possible edge classes to avoid)
  • a simple weight-lookup function - keep a separate traffic lookup table in memory and adjust it on-the-fly from a separate data-loading tool

For relatively small numbers of conditional edges (example: conditional turn restrictions) this might work fairly well - routing would only touch the core (uncontracted) network occasionally. We would lose the benefits of a full CH, and add some additional query overhead, but we would not need to re-process the data in order to change routing behaviour over time. As long as the number of conditional edges remains fairly low, the performance penalty may not be too great. This would need to be measured to be sure, but is likely similar to the current --core feature.

@MoKob @TheMarex Feasibility?

@danpat danpat changed the title Conditional edge-weights Query-time conditional edge-weights May 5, 2016
@danpat
Copy link
Member Author

danpat commented May 5, 2016

This should probably be considered along with #77 - if it seems feasible to do, we may want to "avoid tolls", but not affect ETAs if a toll road is forced.

@MoKob
Copy link

MoKob commented May 9, 2016

This approach is very problematic in my view. I will try and elaborate using the example to avoid highways.

If we want to avoid highways, we are looking at a pretty important part of the hierarchy. Not contracting the highway network, could be suitable, since we are removing unnecessary roads and keep the important part of the network.
In general the CH tries to remove unimportant stuff first (local neighbourhoods and similar regions) that do not contribute to a lot of shortest path.
So in the first instance it looks good.
Now here comes the big BUT:

In the contraction process, we need to construct shortcuts. Whether to omit a shortcut depends on the actual search parameters and whether a setting exists in which we can say the potential path is a shortcut.

Consider the following simple graph:

a ----------- b
|             |
c ----------- d

(a,b) and (b,d) are local streets. (a,c) and (a,d) is a highway.
In a normal CH, we could contract b and not add a shortcut, since the highway will have the much faster travelling speed.

Now if we consider the desire to avoid highways. The shortest path without highways between a and d is suddenly a,b,d instead of a,c,d. Therefore we have to add the shortcut that was not necessary in the pure shortest path setting, even though the local view at b (only considering the edges (a,b) and (b,d) does not see any highways.
We would need to adjust the witness search process (the search for other shortest paths) to a state where we consider all possible combinations of searches we want to allow in the end, making the process incredible complicated and slow.
Also we would end up with a lot of shortcuts that are only necessary for specific settings (in this case only usable for avoid highways) that blow up the hierarchy.

For some parts we can use the mechanism, e.g. adjust travel time on the fly. In these cases we can use the lowest possible travel time for shortcut computations. I don't think it can reasonably work for avoid/other possible flags though.

@SuberFu
Copy link

SuberFu commented Jun 23, 2016

@MoKob Am I correct in assuming the CH just add "short cut" edges with said "short cut" know which edges it's actually short cut over (so in your example, the a->d shortcuts "knows" it's shortcutting over a->c->d)?
If so, perhaps the algorithm can make a concession that says "If any edge segment in the 'shortcut' is effected by cost adjustment (whether infinite cost to indicate "do not route over" or increase cost due to, say, traffic congestion), the shortcut itself is treated as invalid for routing purpose and route on the underlying edges as normal"?
In short, if you want to avoid highway, or traffic adjustment, you loses CH speed up for certain section in the network. In worst case scenario, you essentially fall back to raw A* routing (every CH-edges is deemed invalid).

@MoKob
Copy link

MoKob commented Jun 23, 2016

@SuberFu while it only adds shortcuts, it also doesn't add shortcuts that might be needed.

So lets look at the most simple example here:

a - b
|   |
c - d

Lets say a - c - d is faster than a - b - d

So if we contract in the order b, a, d, c we end up with the hierarchy:

    c
 /     \
a       d
 \     /
    b

So you can see, not even a shortcut is added, but we only know that if we search from a to d, we can ignore b. A can only reach c, the same for d. Only b can reach all vertices.
Now if a - c - d gets slower, we need to find out about this and re-order the hierarchy.

In addition, it is not an easy question to define affected. Because in the moment when you add a penalty to any shortcut, next to any location in the graph can be affected.
Possible examples for wide range effects would be a complete blockage of the golden gate bridge. Suddenly the shortest path has to take quite the detour and you need to update all of the affected region.

TLDR; no, its sadly not that simple.

@MoKob
Copy link

MoKob commented Jun 23, 2016

One addition here: the CH does not load all edges into memory. The routing graph only contains edges that are directed upwards. So a does not know about b. It does not filter it, the edge is simply not in the graph.

Copy link

github-actions bot commented Jul 8, 2024

This issue seems to be stale. It will be closed in 30 days if no further activity occurs.

@github-actions github-actions bot added the Stale label Jul 8, 2024
@github-actions github-actions bot closed this as not planned Won't fix, can't repro, duplicate, stale Aug 8, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

3 participants