Speedup route search algorithm in RouteChoice class by ~60x

[EwoutH]

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]

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]

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.

[toruseo]

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.

[EwoutH]

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]

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?

[toruseo]

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]

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