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.

Sign up for GitHub

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

Jump to bottom

Speedup route search algorithm in RouteChoice class by ~60x #55

Closed
wants to merge 2 commits into from
Closed

Speedup route search algorithm in RouteChoice class by ~60x #55

wants to merge 2 commits into from

Conversation

EwoutH
Copy link
Contributor

@EwoutH EwoutH commented Apr 1, 2024

This pull request introduces a significant optimization to the RouteChoice class's route_search_all method. By shifting from the Floyd-Warshall algorithm to Dijkstra's algorithm and employing vectorized operations for matrix updates, performance is sped up by ~60x for a medium sized graph. These changes are particularly effective for sparse graphs, which are common in road network simulations.

Changes

  1. Algorithm update (1b9df13): Replaced the Floyd-Warshall algorithm with Dijkstra's algorithm using scipy.sparse.csgraph.dijkstra. This change leverages the sparsity of the road network graphs, reducing computational complexity from (O(V^3)) to (O((V + E) \log V)), where (V) is the number of vertices and (E) is the number of edges.
  2. Vectorization of matrix updates (e93a4ab): Replaced nested loops for updating the next matrix with NumPy's vectorized operations and boolean indexing. This optimization reduces the overhead associated with Python loops and utilizes efficient low-level operations for array manipulations (this was originally a very slow part of the graph).

Performance Implications

In a benchmark involving a real-world road graph with 3275 links and 1552 nodes, the execution time of route_search_all was reduced from approximately 19 seconds to just about 0.3 seconds. This demonstrates the significant efficiency gains achieved through these optimizations.

If route search will be a bottleneck in the future again, it might be worth investigating the potential for leveraging C-optimized libraries like graph-tool or igraph for even more performance.

If merged, this PR closes #53.

@EwoutH
Speedup route_search_all ~20x with Dijkstra's algorithm for sparse gr…
1b9df13 
…aphs

Replaced the Floyd-Warshall algorithm in `route_search_all` with Dijkstra's algorithm using scipy's sparse matrix representation for improved performance in sparse graphs. This change addresses the performance bottleneck by leveraging Dijkstra's inherent efficiency for such structures and direct path reconstruction capabilities, significantly reducing computation time for shortest path routing. Updated relevant data structures and removed unnecessary post-processing steps for next node determination.

In a real-world road graph with 3275 links and 1552 nodes, it reduced the time route_search_all from ~19 seconds to ~0.85 seconds, an over 20x speedup.
@EwoutH
Speedup route_search_all ~3x with vectorized updates of next matrix
34a3b42 
Refactor the route_search_all method in RouteChoice to utilize NumPy's vectorized operations and boolean indexing, eliminating nested loops for updating the next matrix. This significantly enhances performance by reducing Python loop overhead in sparse graph computations.

In a real-world road graph with 3275 links and 1552 nodes, it reduced the time route_search_all from ~0.85 seconds to ~0.30 seconds, a ~3x speedup.

Together with the previous commit, it reduced the time route_search_all from ~19 seconds to ~0.3 seconds, a ~60x speedup.
@EwoutH
Copy link
Contributor Author

EwoutH commented Apr 1, 2024

While manual inspection of a graph looks okay, a few of the tests are failing:

(136 durations < 0.005s hidden.  Use -vv to show these durations.)
=========================== short test summary info ============================
FAILED tests/test_verification_route_choice.py::test_2route_equal_but_different_structure - assert False
 +  where False = equal_tolerance(391.445, 27.34375)
 +    where 391.445 = <function average at 0x7fc3bf90c2f0>([394.125, 367.325, 394.125, 394.125, 394.125, 394.125, ...])
 +      where <function average at 0x7fc3bf90c2f0> = np.average
 +    and   27.34375 = <function average at 0x7fc3bf90c2f0>([-3.0, 300.4375, -3.0, -3.0, -3.0, -3.0, ...])
 +      where <function average at 0x7fc3bf90c2f0> = np.average
FAILED tests/test_verification_node.py::test_diverge_lesscapacity_nocongestion - assert False
 +  where False = equal_tolerance(142.0, 200)
 +    where 142.0 = <function average at 0x7fc3bf90c2f0>([145, 140, 140, 145, 150, 125, ...])
 +      where <function average at 0x7fc3bf90c2f0> = np.average
FAILED tests/test_verification_node.py::test_diverge_lesscapacity_congestion - assert False
 +  where False = equal_tolerance(58.54875, 333, rel_tol=0.2)
 +    where 58.54875 = <function average at 0x7fc3bf90c2f0>([56.0625, 55.4625, 61.2125, 59.0875, 56.1625, 55.7375, ...])
 +      where <function average at 0x7fc3bf90c2f0> = np.average
FAILED tests/test_verification_node.py::test_2to2_no_flow_to_one_dest - assert False
 +  where False = equal_tolerance(54.95, 250, rel_tol=0.2)
 +    where 54.95 = <function average at 0x7fc3bf90c2f0>([55.85, 54.3375, 54.725, 55.5875, 54.5125, 54.625, ...])
 +      where <function average at 0x7fc3bf90c2f0> = np.average
FAILED tests/test_verification_sioux_falls.py::test_sioux_falls - assert False
 +  where False = equal_tolerance(12600.0, 33287.75)
 +    where 12600.0 = <function average at 0x7fc3bf90c2f0>([12600])
 +      where <function average at 0x7fc3bf90c2f0> = np.average
============== 5 failed, 47 passed, 32 rerun in 329.17s (0:05:29) ==============

Summarized:

  1. test_2route_equal_but_different_structure: Expected average travel time is 149.4525, but the actual is 382.99.
  2. test_diverge_lesscapacity_nocongestion: Expected average travel time is 200, but the actual is 145.0.
  3. test_diverge_lesscapacity_congestion: Expected average travel time is 333, but the actual is 57.02625.
  4. test_2to2_no_flow_to_one_dest: Expected average travel time is 250, but the actual is 56.0825.
  5. test_sioux_falls: Expected total system travel time is 33287.75, but the actual is 12240.0.

Here are the calculated percentage differences between the expected and actual values for each of the failed tests:

  1. test_2route_equal_but_different_structure: The actual value is 156.26% higher than expected.
  2. test_diverge_lesscapacity_nocongestion: The actual value is 27.50% lower than expected.
  3. test_diverge_lesscapacity_congestion: The actual value is 82.88% lower than expected.
  4. test_2to2_no_flow_to_one_dest: The actual value is 77.57% lower than expected.
  5. test_sioux_falls: The actual value is 63.23% lower than expected.

The differences could be due to a number of sources, including potentially noise. @toruseo, could you help me interpret these test failures and give guidance on how to resolve them?

@EwoutH
Copy link
Contributor Author

EwoutH commented Apr 1, 2024

One interesting thing is that on my computer locally, only one of the tests fails (test_2route_equal_but_different_structure), while the others pass.

image

@toruseo
Copy link
Owner

toruseo commented Apr 2, 2024

test_2route_equal_but_different_structure() tests whether two routes with identical free-flow travel time were used evenly or not. If the route choice element is correct, they must be used evenly. In the other words, np.average(tt1s) and np.average(tt2s) must be almost equal. Thus, this failure suggests that this implementation has critical issues.

And,

  • and 27.34375 = <function average at 0x7fc3bf90c2f0>([-3.0, 300.4375, -3.0, -3.0, -3.0, -3.0, ...])

this negative values are also strange. I am not sure, but this may mean initial placeholder value (-1) was not properly overwritten???

It is quite strange that this one passed the other tests in your local computer. I have no idea why.

I recommend you to verify your implementation by using test_verification_route_choice.py which focuses on the route choice element.

toruseo
toruseo reviewed Apr 2, 2024
View reviewed changes
uxsim/uxsim.py

# Vectorized operation to copy `s.pred` into `s.next` where pred != -9999
valid_pred = s.pred != -9999
s.next[valid_pred] = s.pred[valid_pred]
Copy link
Owner

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Is this correct? I think pred and next are different concept and cannot be mapped like this.

EwoutH
EwoutH commented Apr 2, 2024
View reviewed changes
uxsim/uxsim.py Show resolved Hide resolved
@EwoutH
Copy link
Contributor Author

EwoutH commented Apr 2, 2024

Thanks for the review. It's informative and I'm exploring different alternative options to speed it up. It's a hard problem to crack.

this negative values are also strange.

My suspicion is that's due to noise.

@EwoutH
Copy link
Contributor Author

EwoutH commented Apr 4, 2024

Closing this for now. Maybe I will do another attempt, but if anyone has an idea on to how to speed this up that would be greatly appreciated.

@toruseo, it might be useful to split the shortest path finding and the actual route selection (either in separate classes or separate methods) functionally, instead doing both in one method. What do you think of that?

@EwoutH EwoutH closed this Apr 4, 2024
@toruseo
Copy link
Owner

toruseo commented Apr 5, 2024

Thanks for trying.

It is a kind of separated already. RouteChoice.route_search_all finds the shortest paths, whereas RouteChoice.homogeneous_DUO_update updates the travel path for vehicles whose route choice principle is DUO. Then, each vehicle chooses their own path by Vehicle.route_pref_update and Vehicle.route_next_link_choice given the results of RouteChoice.homogeneous_DUO_update.

Additionally, if you set Vehicle.links_prefer list, the vehicle will use links in the list, ignoring the shortest path. You can set this list by __init__ or update during simulation. I havent documented this feature in detail, but I believe it is functional.

@toruseo
Copy link
Owner

toruseo commented Apr 5, 2024

Maybe the class name RouteChoice is not appropriate. Might be renamed to RouteSearch or something in the future.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@toruseo toruseo toruseo left review comments

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

Speed up route_search_all by using priority queue optimized Dijkstra's
2 participants
@EwoutH @toruseo