search

conveyal / r5

Developed to power Conveyal's web-based interface for scenario planning and land-use/transport accessibility analysis, R5 is our routing engine for multimodal (transit/bike/walk/car) networks with a particular focus on public transit
https://conveyal.com/learn
MIT License
285 stars 73 forks source link

Turn restrictions create islands #806

Open mattwigway opened 2 years ago

mattwigway commented 2 years ago

The TarjanIslandPruner has a comment that says:

 * One concern with this island remover is that it does not consider turn restrictions, so it theoretically would leave
 * a situation like this in the graph:
 *
 *  B - C
 *  |
 *  A
 *
 * Suppose all edges can be traversed by cars in both directions, but there is a no-right-turn restriction from AB to BC.
 * C is not part of a larger strong component because it cannot be reached due to the turn restriction. However, this
 * case is believed to be sufficiently rare not to worry about.

In developing turn restriction code for another piece of routing software (my favorite Sunday morning activity :wink:), I discovered there actually is an island created by turn restrictions just north of the Conveyal DC office where I probably wrote this comment. This way is a parking lot for the DC police district 4, and has both no-right-turn and no-left-turn restrictions from Georgia Ave. If a destination is snapped here, I think routing will fail. Still not sure it's worth addressing.

abyrd commented 1 year ago

Thanks for the report @mattwigway, I've added it to the list in meta-ticket #764. Although we may not be working on this in the immediate future, I do still hope to do a round of turn restriction improvements.

mattwigway commented 1 year ago

If/when you do, you may find the test suite in mattwigway/OpenStreetMapGraphBuilder.jl useful. I wanted to make sure that the turn restriction code was right even in weird (ahem) corner cases like this, so ended up creating a custom OSM file with a small self contained network with a bunch of unusual restrictions/situations, and test cases to go along with it. Feel free to borrow if it's helpful.