Urban/Rural

Background

This article is an insight to the implementation of the Urban/Rural slider - an important axis in the Zikes route parametrisation. The slider's utility is in allowing users express their preference for either rural or urban character of the resulting route.

This seemingly common-sense distinction comes with lurking caveats:

• is it continuous or discrete? Namely: how many shades of urban/rural there are in between the Southern Pole and central Hong Kong? As this is in essence about managing user expectations (and not getting them ponder why one seemingly quiet route turns out more rural than another that looks just as quiet) the assumption I took is that it's only useful when coarsely discrete. And for the first-cut simplicity, i decided to narrow it down to the binary distinction. i.e.: a town becomes urban at some reasonable "size" threshold.
• how much (how far) does a city radiate its urban-nes? Can you have a rural corridor running through its centre? I don't know what my expectation is, let alone of an average cyclist, so instead I allow the answer emerge from the method (that I describe below).

Input

A common sense expectation is that one should find road/path segments generally shorter in the city than in the country side (the road network is denser in cities). The major challenge for Zikes was to offer a useful urban/rural slider that only has road segment lengths as input and works that input in real-time - as it traverses the graph in search of a route. This is not to pollute the graph data with cost function intricacies - and quite ephemeral ones in this specific case (what's the size threshold beyond which a city is urban?).

With the unverified hope that the south-western Poland stands a chance of being globally representative, the above graph shows data captured over the city of Wroclaw (for urban) and some 50km north-west from it (for rural) where there are no big cities in sight (it's non-trivial to subtract a city from a body of data). Segments below the arbitrary 30mts of length have been filtered out as they are thought to be indicative of junction design rather than convey useful statistics. Apart from the general orders of magnitude, the graph shows two important, albeit not awfully crisp data points:

• a segment of 80mts (or less) is at least twice as likely to be in a city;
• a segment of 300mts (or more) is at least twice as likely to be in a country side;

Should we use these thresholds for a binary urban/rural filter we will get this:

Promising, but not good enough when applied directly to the punish/reward function as it will (undesirably) strive to go around small villages and (equally undesirably) find 'rural corridors' within what is undeniably a city. Colloquially speaking, its effect has been too local.

Method

It seemed, to de-localise and spread the effect of this rudimentary (2/3rds of the time accurate) filter, was to let its judgement accumulate. To only pay attention to a sustained barrage of it triggering. After many wrong turns, examining economies of debt and credit, i found a useful metaphor in a capacitor (heat or electric or call it a decision buffer). Above all, and after some calibration, i found it working well in the field.

Path-finding is typically implemented as a breadth-first-search on the map graph. It is also said to have a fringe - the OpenSet - prioritising best candidates to be evaluated next. Each such candidate looks back pointing where it came from and thus, when one of them is found matching the destination it can be backtracked to re-construct this most successful (cheapest) route. There is therefore clear state preserved for each candidate (and each predecessor and each run of the algorithm) which can be used to preserve the charge of the capacitor.

    /**

     * JunctionCostCapacitor is much like a (electric/heat) capacitor for the cost. When the routing algorithm

     * encounters a qualifying edge (qualifying for a specific routing::CostFunction::CostFactor punishment),

     * instead of applying that factor directly, the algorithm saves a JunctionCostCapacitor on that edge charging

     * it up by one notch.

     *

     * Any edge following 'this' has its capacitor pre-charged by the predecesor. If it qualifies, it

     * charges the capacitor further and if it doesn't, it discharges it (one notch at a time).

     *

     * Whenever the capacitor reaches its capacity, it starts to give way, it starts to radiate the cost

     * (at a constant rate).

     *

     * The result is both subtle and powerful and it comes very useful for the rural/urban filter.

     * Suppose we need to make the rural/urban judgment solely based on the edge lengths, which _tend_ to

     * be longer in the countryside. Punishing shorter lengths demonstrably does not work as its effect

     * is too local. Doing so results in routes going around very small villages or finding refuge in

     * longer arteries inside cities.

     *

     * The slow-charge property of the capacitor has it ignore small villages and its slow-discharge causes

     * long city arteries to offer no refuge.

     */

One can clearly see, an unusually long I should add, capacitor warm-up phase shown below. Unusually long, because this section of Legnicka Street offers the very 'rural corridor' outliers i mentioned earlier and indeed encountered (which is why i test it here).

The important consequence of the capacitor's good charge is that, once hot, it should not seek refuge in occasional long segments and thus the route shouldn't react to slider wiggles:

Conversely, neither should it react to wiggles when entirely in the country-side:

Indeed, the initial, default state of zero may result in undefined/undesired behaviour until the capacitor works out its vicinity. This shouldn't be a problem as it would be cheap to arrange for an initial dry walk and charge it based on the nearby edges. The screen-shots above illustrate the capacitor's behaviour with the charge depth set to 8 - which means a barrage of 8 consecutive urban-length segments will heat it up enough to glow.