Multiparameter weighting

[jakepruitt]

Ticket #77 is almost finished with #2399, which will allow an arbitrary weight value to be used for routing other than duration. The basic implementation details, like creating a new column for weights associated with every edge, could be extended to support a richer set of routing heuristics with more capabilities than directly replacing weight values.

#2399 will allow a weight column and a duration column to be associated with every edge where there was once just one weight column. Extending this idea further, we could think of multiple columns of data associated with each edge as new "layers" of information that could be used in routing. While we can't feasibly give an unlimited number of "layers" to the user, due to the way shared memory indexing works, we could specify a maximum number of layers and allow users to specify up to that number (for now let's say five).

These five layers could be combined to calculate the weight value used to perform routing. The specification of what these layers contain and initial values for those layers would happen in the lua profile, and the lua profile would also specify a global function that describes how the layers are combined to form the weight for routing. Initially, we were thinking of using a vector multiplication approach, specifying the coefficients that each layer was multiplied by and storing that vector from extraction time through all of the shared files to contraction time. After some more thought, we realized it could be possible to write a mathematical AST representation of the calculation, as long as we figured out how to parse that from the lua function and serialize it in the intermediate files.

For now, we should finish #2399 in an extensible way and flesh out how we could make the AST/formula easy for the user to specify.

cc/ @TheMarex @danpat @daniel-j-h @morganherlocker @lily-chai @nickcordella

[TheMarex]

One important aspect I want to highlight here is the separation of data and mechanism.

Every layer should be an quantifiable dataset like:

• duration
• distance
• safety
• fuel-consumption
• overrides for compliance (e.g. no-through traffic)

The profile would have the function of computing heuristics/values for each of those layers, as well as specifying how these are to be mixed to form the final routing weight. We can actually delay mixing these values until the update phase.

By only updating layers, the problem of compatible weighting becomes completely transparent to the data provider.

[emiltin]

This would still not allow choosing the routing parameters (duration/safety/etc) at run time, right?

[MoKob]

@emiltin as long as we have a CH, having multiple routing parameters is a difficult setting to incorporate directly. Since the routing graph changes based on how the weights are, we cannot simply switch them out.

The shortcut method (without having a Customizable CH) needs to throw away sub-optimal routes. But if you compare different metrics, optimal is not necessarily well defined.

It might be in our reach somewhere down the road, but right now we can only use a single weight but report additional parameters (e.g. correct ETA while avoiding specific settings).

[nickcordella]

One suggestion: I can think of a use case where one would want to quickly test out different weighting functions, but don't want to wait for an entire extract step to execute before being able to do so. For that reason, I think it would be useful to be able to specify the weighting function as an input to the update phase, rather than:

specifying how these are to be mixed to form the final routing weight

inside the lua profile

[github-actions]

This issue seems to be stale. It will be closed in 30 days if no further activity occurs.