1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
pub mod emission {
use crate::transition::*;
/// 1 meter (1/10th of the 85th% GPS error)
const DEFAULT_EMISSION_ERROR: f64 = 1.0;
/// Calculates the emission cost of a candidate relative
/// to its source node.
///
/// ## Calculation
///
/// The emission cost is defined by the relative distance
/// from the source position, given some "free" zone, known
/// as the [`emission_error`](#field.emission_error). Within this error, any
/// candidate is considered a no-cost transition as the likelihood
/// the position is within the boundary is equal within this radius.
///
/// The relative calculation is given simply below, where `distance`
/// defines the haversine distancing function between two Lat/Lng positions.
///
/// ```math
/// relative(source, candidate) = err / distance(source, candidate)
/// ```
///
/// The cost derived is given as the square root of the reciprocal of
/// the relative distance.
///
/// ```math
/// cost(source, candidate) = sqrt(1 / relative(source, candidate))
/// ```
///
/// There exist values within the strategy
/// implementation which define how "aggressive" the falloff is.
/// These hyperparameters may need to be tuned in order to calculate for nodes
/// which have large error. Alternatively, providing your own emission error
/// is possible too.
pub struct DefaultEmissionCost {
/// The free radius around which emissions cost the same, to provide
/// equal opportunity to nodes within the expected GPS error.
///
/// Default: [`DEFAULT_EMISSION_ERROR`]
pub emission_error: f64,
}
impl Default for DefaultEmissionCost {
fn default() -> Self {
DefaultEmissionCost {
emission_error: DEFAULT_EMISSION_ERROR,
}
}
}
impl<'a> Strategy<EmissionContext<'a>> for DefaultEmissionCost {
type Cost = f64;
const ZETA: f64 = 0.5;
const BETA: f64 = -10.0; // TODO: Maybe allow dynamic parameters based on the GPS drift-?
#[inline(always)]
fn calculate(&self, context: EmissionContext<'a>) -> Option<Self::Cost> {
// Scale the physical distance by the road-class weight to penalise
// candidates on lower-quality roads (e.g. MotorwayLink = 2) relative
// to those on higher-quality roads at the same physical offset.
//
// The weight is capped at 2 before squaring (maximum multiplier = 4)
// to avoid cost overflow for high-weight urban roads (Secondary = 7,
// Residential = 10, etc.). Without the cap the exp() inside the decay
// formula overflows to u32::MAX for any GPS point > ~3 m from the road,
// making all secondary-road candidates indistinguishable and causing
// erratic matching on urban routes.
//
// With the cap:
// Motorway (w=1) → multiplier = 1 (baseline)
// MotorwayLink (w=2) → multiplier = 4 (must be ≤ ¼ distance of Motorway to win)
// Primary+ (w≥3) → multiplier = 4 (same cap; no run-away overflow)
//
// Zero-cost behaviour is preserved: distance = 0 → cost = 0.
let w = (context.weight as f64).min(2.0);
let weighted_distance = context.distance * w * w;
Some(weighted_distance.sqrt() * weighted_distance)
}
}
}
pub mod transition {
use crate::transition::*;
use routers_network::{Edge, Entry, Metadata, Network};
/// Calculates the transition cost between two candidates.
///
/// Involves the following "sub-heuristics" used to quantify
/// the trip "complexity" and travel "likelihood".
///
/// # Calculation
///
/// Using turn-costing, we calculate immediate and summative
/// angular rotation, and with deviance we determine a travel likelihood.
///
/// ## Turn Cost
/// We describe the summative angle, seen in the [`Trip::total_angle`]
/// function, as the total angular rotation exhibited by a trip.
/// We assume a high degree of rotation is not preferable, and trips
/// are assumed to take the most optimal path with the most reasonable
/// changes in trajectory, meaning many turns where few are possible
/// is discouraged.
///
/// We may then [amortize] this cost to calculate the immediately
/// exhibited angle. Or, alternatively expressed as the average angle
/// experienced
///
/// ```math
/// sum_angle(trip) = ∑(angles(trip))
/// imm_angle(trip) = sum_angle(trip) / len(trip)
///
/// turn_cost(trip) = imm_angle(trip)
/// ```
///
/// ## Deviance
/// Defines the variability between the trip length (in meters)
/// and the shortest great-circle distance between the two candidates.
///
/// This cost is low in segments which follow an optimal path, i.e. in
/// a highway, as it discourages alternate paths which may appear quicker
/// to traverse.
///
/// ```math
/// length(trip) = ∑(distance(segment))
/// deviance(trip, source, target) = length(trip) - distance(source, target)
/// ```
///
/// ### Total Cost
/// The total cost is combined as such.
///
/// ```math
/// cost(trip, s, t) = deviance(trip, s, t) + turn_cost(trip)
/// ```
///
/// [amortize]: https://en.wikipedia.org/wiki/Amortized_analysis
pub struct DefaultTransitionCost;
impl<'a, E, M, N> Strategy<TransitionContext<'a, E, M, N>> for DefaultTransitionCost
where
E: Entry,
M: Metadata,
N: Network<E, M>,
{
type Cost = f64;
const ZETA: f64 = 1.0;
const BETA: f64 = -1.0;
#[inline]
fn calculate(&self, context: TransitionContext<'a, E, M, N>) -> Option<Self::Cost> {
// Find the transition lengths (shortest path, trip length)
let lengths = context.lengths()?;
// Value in range [0, 1] (1=Low Cost, 0=High Cost)
let deviance = lengths.deviance();
// Road-class continuity: penalise transitions where the target candidate
// is on a lower-quality road than the source candidate.
// A motorway (weight=1) → motorway_link (weight=2) transition gives 0.5;
// an upgrade (motorway_link → motorway) gives 1.0 (no penalty).
let (source, target) = context.candidates();
let src_weight = source.edge.weight as f64;
let tgt_weight = target.edge.weight as f64;
let class_continuity = (src_weight / tgt_weight).min(1.0);
// We calculate by weight, not by distinction of edges since this
// would not uphold the invariants we intend. For example, that would
// penalise the use of slip-roads which contain different WayIDs, despite
// being the more-optimal path to take.
let avg_weight = {
let weights = context
.map_path
.windows(2)
.filter_map(|node| match node {
[a, b] if a.identifier() == b.identifier() => None,
[a, b] => context.routing_context.edge(a, b),
_ => None,
})
.map(|Edge { weight, .. }| weight as f64)
.collect::<Vec<_>>();
if weights.is_empty() {
// Distance-only transition (same edge): fall back to the
// better (lower-weight) of the two candidate edges to avoid
// a division-by-zero NaN propagating through the rest of the
// calculation. Choosing the minimum gives the most
// favourable distinct_cost for a same-edge transition, which
// is the correct baseline when the path has zero routing edges.
src_weight.min(tgt_weight)
} else {
weights.iter().sum::<f64>() / weights.len() as f64
}
};
// Value in range [0, 1] (1=Low Cost, 0=High Cost)
let distinct_cost = (1.0 / avg_weight).powi(2).clamp(0.0, 1.0);
// Value in range [0, 1] (1=Low Cost, 0=High Cost)
let turn_cost = context
.optimal_path
.angular_complexity(context.layer_width)
.clamp(0.0, 1.0);
// Value in range [0, 1] (1=Low Cost, 0=High Cost)
// Weighted: 25% Edge Distinction, 25% Class Continuity, 25% Turn Difficulty, 25% Distance Deviance
// Note: Weights must sum to 100%
let avg_cost = (0.25 * distinct_cost)
+ (0.25 * class_continuity)
+ (0.25 * turn_cost)
+ (0.25 * deviance);
// Take the inverse to "span" values
Some(avg_cost.recip())
}
}
}
pub mod costing {
use super::{DefaultEmissionCost, DefaultTransitionCost};
use crate::costing::{
Costing, EmissionContext, EmissionStrategy, TransitionContext, TransitionStrategy,
};
use core::marker::PhantomData;
use routers_network::{Entry, Metadata, Network};
pub struct CostingStrategies<Emmis, Trans, E, M, N>
where
E: Entry,
M: Metadata,
N: Network<E, M>,
Emmis: EmissionStrategy,
Trans: TransitionStrategy<E, M, N>,
{
pub emission: Emmis,
pub transition: Trans,
_phantom: core::marker::PhantomData<E>,
_phantom2: core::marker::PhantomData<M>,
_phantom3: core::marker::PhantomData<N>,
}
impl<Emmis, Trans, E, M, N> CostingStrategies<Emmis, Trans, E, M, N>
where
E: Entry,
M: Metadata,
N: Network<E, M>,
Emmis: EmissionStrategy,
Trans: TransitionStrategy<E, M, N>,
{
pub fn new(emission: Emmis, transition: Trans) -> Self {
Self {
emission,
transition,
_phantom: PhantomData,
_phantom2: PhantomData,
_phantom3: PhantomData,
}
}
}
impl<E, M, N> Default for CostingStrategies<DefaultEmissionCost, DefaultTransitionCost, E, M, N>
where
E: Entry,
M: Metadata,
N: Network<E, M>,
{
fn default() -> Self {
CostingStrategies::new(DefaultEmissionCost::default(), DefaultTransitionCost)
}
}
impl<Emmis, Trans, E, M, N> Costing<Emmis, Trans, E, M, N>
for CostingStrategies<Emmis, Trans, E, M, N>
where
E: Entry,
M: Metadata,
N: Network<E, M>,
Trans: TransitionStrategy<E, M, N>,
Emmis: EmissionStrategy,
{
#[inline(always)]
fn emission(&self, context: EmissionContext) -> u32 {
self.emission.cost(context)
}
#[inline(always)]
fn transition(&self, context: TransitionContext<E, M, N>) -> u32 {
self.transition.cost(context)
}
}
}
pub use costing::*;
pub use emission::*;
pub use transition::*;