Routing problems

From OpenStreetMap Wiki
Jump to: navigation, search

This page describes some routing scenarios that can't be solved using A* algorithm (but may be possible with another standard type)

Circular walk

Starting from point A, find a route that travels between x and x+dx miles along routes accessible by a (pedestrian|bike|mountain bike) and returning to the start point.

The question is when the algorithm is allowed to go back on its own route. If this is allowed too much, then it might just go back and forth along a road to make-up the distance. But sometimes it's necessary (e.g. figure-8 walk, or a P- shaped walk)

A possible solution could be a sort of modified distance-vector algorithm giving each street a "walk score" that is a combination of a user rating based on walkability (with 0 being preferred) and increases as distance from point x goes up. The walk score would increase once it is "used" in the path.

A basic implementation for a circular walk (running route) can be found at http://walks.io/

Find nearest

Standard algorithm for finding the nearest x, where x is usually a restaurant, pub, fuel station, metro station etc.

  • Dijkstra's algorithm, which finds the distance to all destinations (restaurants, pubs), might be a good candidate. --Elecnix 06:18, 30 December 2007 (UTC)
  • Traveling salesman uses Dijkstra here but modified. We route from target to start and if there are multiple targets we introduce a single, virtual target-point that has ways of metric (usually length) 0 to all the desired targets. This also works for a start-point that moves a bit while we calculate the route. --MarcusWolschon 06:17, 11 August 2008 (UTC)
Sometimes it's more useful to know how far off your current route you must go to get to a place. E.g., fuel station A is 1 mile ahead but 3 miles off the route, while fuel station B is 9 miles ahead but only 0.2 miles off the route.
Then you add the cost for the offroad-part to each destination before routing to the one start-location.

Go back by different route

Given the route that you took to get from A to B, find a route from B to A which prefers roads that you haven't visited yet

  • This is a simple modification of your metric (length, travel-time, fuel-efficiency, ...) used. Just give already visited way-sections a penalty. --MarcusWolschon 06:19, 11 August 2008 (UTC)

Survey

Attempt to visit as many roads as possible in an area, without repeating yourself

  • This seems to me like an extension of the Travelling Salesman Problem. --Geonick 19:13, 13 May 2009 (UTC)
  • Could do this using 80n's left-turn algorithm?