Multi-metric support

[TheMarex]

Multi-Metric Overlays

Goal

Currently we only allow one metric per profile, for example fastest or shortest. We want to be able to support multiple metrics per profile and select between them at query-time. This will for example allow to run a single OSRM instance and support both queries for fastest and shortest.

API changes

Lua profile

With #77 we introduced the notion of arbitrary weights. We now need to extend this to be able to set multiple ones per way.

Below is a sketch of what the new lua API could look like.

function way_function(way, result)
   result.forward_rate['routabiliy'] = 50.0
   result.forward_rate['distance'] = 30
end

function turn_function(turn)
    turn.weight['distance'] = 0
    turn.weight['routability'] = turn.angle / 360. * 2
end

We also need to configure the notion of a default metric. profile.weight_name might serve here.

HTTP/node

At query time we need to select which metric the query should use:

• metric String Can be a string that identifies a metric like distance or routability or default.

This would only allow for one metric per query. The ration for this would be to keep the worst-case query time low. The same behavior can be achieved by running multiple queries.

We need to also adapt the the JSON response:

• route[i].weight_name will refer to metric
• route[i].weight, route[i].legs[i].weight, route[i].legs[i].annotations.weight, and route[i].legs[i].steps[i].weight will contain the weight of the specific metric that was used for routing.

osrm-contract/osrm-customize

Both tools need to know which metric they are operating on an create a unique file for each metric.

• --metric= (-m) String name of the metric to process. Default: default (used the default metric selected in the profile)

Example: osrm-customize --metric=distance data.osrm

This would create files data.osrm.{ch,mld}_metric_{metric_name}, e.g. data.osrm.mld_metric_distance in this case.

osrm-datastore

The datastore need to know which metric it is supposed to load into memory. To be consistent with osmr-contract and osrm-customize this would work over multiple --metric options.

• --metric= (-m) String name of the metric to load. Default: default (used the default metric selected in the profile)

Example: osrm-datastore --metric=distance --metric=routability data.osrm

This would look for files data.osrm.{ch,mld}_metric_distance and data.osrm.{ch,mld}_metric_routability.

Implementation changes

1. All data structures involved with weights need to be extended/split:

   • SegmentDataContainer: Split out the segment weights

   • MultiLevelGraph: Split out the turn weights

   • Graph compression, EdgeBasedGraphFactory need to know about every weight

   • For MLD:

     • Cell arc weights (currently part of .osrm.cells)
     • Base graph weights (currently part of .osrm.mldgr)
     • Segment weights (currently part of .osrm.geometries)

   • For CH:

     • Contracted graph and weights (currently .osrm.hsgr)
     • Segment weights (currently part of .osrm.geometries)

2. Algorithm specific tools osrm-customize and osrm-contract need to know which metric to read/update/process.

3. Extend osrm-datastore to load all metric files specified, depending on algorithm type.

4. Extent engine to select metric at query time:

   • Dataface needs to be extended to retrieve the corresponding graph (CH) and cell overlay (MLD)
   • PhantomNode generation (geospatial_index.hpp) needs to know for which metric it should generate offsets
   • Search functions need to be parametrized to take: For CH: graph with shortcuts and weights For MLD: base graph with weight, cellstorage with weights

[emiltin]

this will be a great new feature! much easier than running multiple instances of osrm. what about weight on nodes? i guess that should also be included.

[oxidase]

as per chat with @TheMarex: before doing data storage refactoring and continue with issues #1353, #3116, #3983, #4158 and #4406 a new data memory layout must be proposed.

The described above approach requires benchmarking of path unpacking and annotations computation in the table plugin, because duration values will be removed from the edge data and values will not be precomputed during customization or contraction.

[TheMarex]

One major problem with having multiple weights with the same base graph, is the current directional compression we use. If an edge has the same weight in both forward and backward direction, we only save one edge and mark it as forward=true, backward=true.

If we have multiple weights per edge some edges might have different weights in each direction, depending on the metric. That means we need to think about a different encoding that does not suffer from this problem. The downside here is that this might increase memory consumption, but we would need to check how effective this encoding is right now on an edge-based-graph (since we have turn penalties there is actually a high chance that forward and backward weight don't match right now anyway).

A few things to consider:

• We could divide the edge array into a forward section and a backward section, that would ensure continuous EdgeID values for all edges
• We could duplicate the node array, having one for outgoing edges and one for incoming edges
• Our graph interface would need to change: GetAdjacentEdges() -> GetOutgoingEdges() + GetIncomingEdges()

A simple work-around would be to keep the current edge flags but always split the edge. That would have the upside that we don't really need to change any interfaces.

[emiltin]

does this issue cover running different profiles in one osrm instance, e.g. bicycle and foot? or only different metrics for a single profile?

[TheMarex]

@emiltin only different metric for a single profile. Multiple profiles per OSRM instance would require how we handle profiles in the first place. But good point, I'll try to add a ticket for that as well.