Yeah the big problem here is the multipoint route component. We do indeed use the low reachability candidate just in case we are routing inside of a disconnected island. The algorithm will also get a reachable candidate and both will be used for the route to that location. The problem though is that in the end only one of them can end up being used in the leg of route and so we compute the first leg and end up using the low reachability candidate (its closer to yoru input location than the reachable one). Then we fail the second leg because we have to start from that unreachable candidate. If we really want to preserve the behavior of routing within islands (dubious importance but should be considered) we would need to, after the second leg fails, remove the unreachable candidate, and re-run the first leg again and then continue with the second leg. This can be hell because you can imagine having to back track at every intermediate location on the multipoint route. Another option is to remove all low reachability candidates for intermediate locations and just say screw it, we wont worry about routing inside of disconnected islands on multipoint routes.

Another option is to remove all low reachability candidates for intermediate locations and just say screw it, we wont worry about routing inside of disconnected islands on multipoint routes.

Right, that was my first thought here. Especially if the waypoints are "far" apart, the odds of them belonging to the same isolated network component diminish.

What I'd ideally like to do here is have the reachability test output the set of edges reached - then before routing, we can look for intersection, and select the set of candidates that are either:

a. low reachability, but the reachable edge sets intersect, or
b. all have max reachability (i.e. belong to the large road network).

OSRM's approach to this is to return 1 or 2 candidates - a low reachability candidate if that's the closest thing, and then the nearest candidate with "max reachability", and nothing in between. If the "max reachability" candidate is closest, then it is returned alone.

Once these 2 options are returned for each waypoint, there's a routine that decides which ones to use - the low reachability candidates if they all touch the same subnetwork, otherwise use all the max reachability candidates.

IMO, OSRM's behaviour regarding this is quite nice - it almost always gives you roughly what you want (a route), even if you drop coarsely placed coordinates (e.g. geocoding centroid coordinates of administrative areas, landing you in the middle of major parks).

The two differences we have to figure out here are:

1. OSRM's reachability threshold is 1000 edges instead of 100.
2. OSRM has the ability to pre-calculate the strongly connected networks and number them, so calculating reachability test isn't expensive at query time, and testing for common connectivity of low reachability candidates is trivial.

I think (1) is not really an issue - 100 vs 1000 doesn't really change much. The road network is sprinkled with lots of very small (<10 edge) isolated components, and 100+ sweeps up most of them.

The tricky bit is (2) - determining if candidates share a common small network.

Deprecated by #2914