Take elevation into account

[Zebreu]

BACKGROUND: A user may service some neighborhoods that are very mountainous. In order for their collection vehicles to get up the mountain, they need to travel empty to the top and collect containers on their way down
REQUEST: Add a config option to optimize routes based on starting routes from maximum elevation and traveling downwards. Perhaps this might need a differential so that small hills in the zone aren’t impacted?

[Zebreu]

Tricky, the solver will try to minimize things in unexpected ways unless we are careful. We could build some support for ingesting extra columns and use those to split routes or modify cost calculations, and those parameters could be coming from a digital elevation model (I would be pleasantly surprised if open global datasets like the STRM were accurate enough for this use case) or the partner data (could be simply some strings or integers/enums). The issue is the “order dependence” of the problem: a path’s cost becomes asymmetric when a vehicle becomes loaded, which means we have a cost matrix that needs to be updated dynamically. We can probably model the transitions into high and low altitudes and pre-calculate a few matrices but or-tools might not like that, we’ll see. Most effort, a matter of weeks of experimentation probably.

[Zebreu]

Some locations in steep areas may not be well modeled in OSM and we'd want to be careful about the OSM data as well.

Talking of OSM, it would be possible to use https://wiki.openstreetmap.org/wiki/Key:incline but I suspect most roadways do not have this filled out by default so organizations may want to edit especially steep roads to let the tool know those may be avoided.

[Zebreu]

For integration of the data, we could use the lua profiles directly: https://github.com/Project-OSRM/osrm-backend/wiki/Integrating-third-party-raster-data and https://github.com/Project-OSRM/osrm-backend/blob/master/profiles/rasterbot.lua

Then we could have a "vehicle that cannot handle steep roads" profile.

The other way would be to update the osm data with the incline tag right after we download them: https://wiki.openstreetmap.org/wiki/Key:incline

and then use the tag as usual (without requiring the raster lookup in the lua file), https://github.com/Project-OSRM/osrm-backend/blob/master/docs/profiles.md (edited)

The easiest thing to do may be to compute elevation changes along the routes as a variable and minimizing it when we define trips, which will force trips to stay along stable elevation profiles, with the issue that no alternate road will be taken for "unavoidable steep roads" like going from the depot to a high point (i.e. osrm is not aware that the fastest path could actually be taking a longer way with a smaller incline) (edited)

[Zebreu]

Extra point to be made about minimizing it: ortools routing does not allow very customizable objective functions, so we'd have to change the arc cost (have a cost matrix that's [time + (factor * elevation_change)] or something similar) to have it minimized as expected.

[Zebreu]

We could also experiment with google/or-tools#1207 where they explain the use of AddVariableMinimizedByFinalizer

[Zebreu]

An interesting automation step could be to correlate the usage of incline tags and the DEM data from OpenTopography. This may allow us to investigate what are good threshold values for steep roads.

[Zebreu]

We added a profile that avoids any road with incline=steep tags, this should be sufficient for many use cases already.