Improve Graph space performance

PhysicsOfMobility / ridepy

Simulates a dispatching algorithm serving exogenous transportation requests with a fleet of vehicles. Does not simulate the universe, unlike MATSim. Batteries are included.

https://ridepy.org

MIT License

7 stars 0 forks source link

Improve Graph space performance #272

Open fxjung opened 2 months ago

fxjung commented 2 months ago

Currently, large graph spaces are nowhere near as fast as continuous spaces. Examples:

Distance between random points

Euclidean 2D: 4.88 µs
10 x 10 grid graph: 4.7 µs
Manhattan Street network: 132 µs

Time interpolation between random points

Euclidean 2D: 4.91 µs
10 x 10 grid graph: 6.11 µs
Manhattan Street network: 147 µs

Additionally, caching distances between simulations runs might be sensible, see also #100.

pmarszal commented 2 months ago

I found, that often you also need distances and maybe even shortest paths for certain statistics, e.g. what are possible acceptable requests for a certain state of the system. Pre-computing both distances and Dijkstra-predecessors and being able to just give them to the simulator was quite nice for me.