search

conveyal / r5

Developed to power Conveyal's web-based interface for scenario planning and land-use/transport accessibility analysis, R5 is our routing engine for multimodal (transit/bike/walk/car) networks with a particular focus on public transit
https://conveyal.com/learn
MIT License
285 stars 73 forks source link

More efficient alternate linkages and distance tables #450

Open abyrd opened 6 years ago

abyrd commented 6 years ago

We build new distance tables whenever the streets change, and new linkages for each mode of transport. This wastes a lot of memory because almost the entire linkage is probably identical except for a few points.

Possible optimizations: linkages that wrap other linkages, with a read-through map instead of a full copy of the linkage arrays.

It also might be possible to do a walk and bike linkage at the same time - if in most cases the nearest road to a point is useable for both bike and walk or bike/walk/car, we can somehow record that fact and avoid re-linking it, or even perform the alternate bike linkage at the same time.

abyrd commented 5 years ago

Note that this ticket refers to a pure optimization - the current system works, it just copies a lot of data from the base linkage rather than wrapping and reading through to the existing base linkage. The copies are not that huge, they could be up to a few million references to vertices, distances, or distance table objects, so I'd estimate up to 10 megabytes or so. Maybe not worth worrying about for now.