Router chooses most similar route leg summary even when very dissimilar

[azarovalex]

If Directions API returned multiple routes during rerouting NavsDK uses this code to select the best route:

mapbox-navigation-ios/Sources/MapboxCoreNavigation/Router.swift

Lines 347 to 356 in 4a2c690

	extension Array where Element: MapboxDirections.Route {
	func index(mostSimilarTo route: Route) -> Int? {
	let target = route.description
	return enumerated().min { (left, right) -> Bool in
	let leftDistance = left.element.description.minimumEditDistance(to: target)
	let rightDistance = right.element.description.minimumEditDistance(to: target)
	return leftDistance < rightDistance
	}?.offset
	}
	}

It selects the route which name has the minimal Levenshtein distance with the name of the original route. The route name is essentially a concatenation of all the street names on the route.
This logic might not always select the best route, we should take ETA into consideration as well.

[1ec5]

This logic might not always select the best route, we should take ETA into consideration as well.

This is a feature: when the user selects a route other than the most optimal route initially, a reroute should not send them right back to the optimal route, ignoring their original selection. This is especially important in light of proactive rerouting, which occurs automatically without user intervention: #2740. See also the rationale at #818 (comment) for this specific heuristic versus one based on similarity to the original route geometry.

It’s conceivable that the user might reconsider their original selection at some point and actually want to take the optimal route. To accommodate that use case, perhaps we should show alternative routes on the map during turn-by-turn navigation, annotated by duration; the user could tap on an alternative route to cancel their original selection and choose a different route going forward: #3598.

It selects the route which name has the minimal Levenshtein distance with the name of the original route. The route name is essentially a concatenation of all the street names on the route.

Not all the street names, but rather the names of the streets that appear for the longest distances along the route. That way, it ends up being a very cheap proxy for the route geometry, but also more nuanced than the raw geometry because it can distinguish between two alternative routes that have similar geometry.

[1ec5]

A user reported that MCE, PIE was unexpectedly matched to PIE, Braddell Road when given the following three route leg summaries:

1. PIE, Upper Bukit Timah Road
2. PIE, Bukit Timah Road
3. PIE, Braddell Road

"PIE, Upper Bukit Timah Road".minimumEditDistance(to: "MCE, PIE") // 24
"PIE, Bukit Timah Road".minimumEditDistance(to: "MCE, PIE") // 18
"PIE, Braddell Road".minimumEditDistance(to: "MCE, PIE") // 15

A human would’ve considered the three routes to be a tie based on the summaries alone, then preferred the first route because of its optimality. They would’ve primarily compared the whole names and secondarily compared individual words, but they wouldn’t have compared individual characters as this application of the Levenshtein algorithm appears to. We could generalize the extension method to operate on a sequence instead of a string, then compare by name and by word.

At a certain point, the summary similarity becomes less relevant than the position in the response, allowing us to ignore the user selection and go with the most optimal route. In this case, the winning candidate was only 17% similar. The following code should only consider best matches above 50% – or even higher.

mapbox-navigation-ios/Sources/MapboxCoreNavigation/Router.swift

Lines 372 to 376 in 06f790b

	return enumerated().min { (left, right) -> Bool in
	let leftDistance = left.element.description.minimumEditDistance(to: target)
	let rightDistance = right.element.description.minimumEditDistance(to: target)
	return leftDistance < rightDistance
	}?.offset

It could look something like this, but cleaned up to avoid the possibility of division by zero:

guard let bestCandidate = map({
    ($0, $0.description.minimumEditDistance(to: target))
}).enumerated().min({ $0.element.1 < $1.element.1 }) else { return nil }

let score = bestCandidate.element.1 / bestCandidate.element.0.description.count
guard score > 0.5 else { return 0 }

return bestCandidate.offset

[1ec5]

We could generalize the extension method to operate on a sequence instead of a string, then compare by name and by word.

@kmadsen also looked into a deeper comparison of the step names, which seemed like a viable and possibly more reliable approach than just comparing the leg summaries: mapbox/mapbox-navigation-android#3116 (comment). However, the benefit of the leg summaries is that it’s biased toward the streets that form the majority of the route. We’d still need to weight the comparison by road length; currently, the iOS implementation relies on the server to perform that weighting for cross-platform consistency.