search

NREL / routee-compass

The RouteE-Compass energy-aware routing engine
https://nrel.github.io/routee-compass/
BSD 3-Clause "New" or "Revised" License
9 stars 4 forks source link

K-Shortest Paths Solver #192

Closed robfitzgerald closed 2 months ago

robfitzgerald commented 2 months ago

Here is a draft of a ksp algorithm that could possibly work well at national scale. It requires running a bi-directional a* search tree algorithm and then selecting candidate spots from the intersecting vertices from where to join paths from each search. It does this until it can generate $k$ paths meeting some (dis-) similarity threshold.

This compiles but is not correct, but since my parental leave is imminent, I want to surface this in the condition it's in. Planning to wrap it up in the next few days. My current issue is a "search tree is missing linked vertex 413760" error, which may be due to how I'm building the two a* searches (one must be reverse-oriented) or how i collect the two routes into a new one.

In order to rule out mapping from edges to vertices, I am simply using the vertex rtree plugin and turning off road class filtering, since those could also cause connectivity issues.

robfitzgerald commented 2 months ago

@nreinicke i made this [pull request] a real thing because i'm getting ksp results:

Screenshot 2024-04-23 at 4 33 33 PM

but i forgot to do an important update at the end that propagates the state+cost from the first leg to the second. so, it's not actually ready :blush:

robfitzgerald commented 2 months ago

@nreinicke here we go, results from a k=30 search where the threshold for the similarity function was set to 90%:

Screenshot 2024-04-24 at 3 43 31 PM

image

robfitzgerald commented 2 months ago

oh, here's time, since that could be more meaningful at a glance

Screenshot 2024-04-24 at 3 50 30 PM

nreinicke commented 2 months ago

😲 Wow! This is amazing! So cool that you were able to put together so fast. I'm excited to review this but in the meantime the results look really promising

robfitzgerald commented 2 months ago

Sure, thanks for taking the time to review. I'm sick today and missed Friday due to VPN issues, but hope to be back tomorrow, possibly remote (no baby yet)