The purpose of the algorithm is to create n routes on a geographical map, where n is being given, whereas all routes take no longer than t time units by foot and end where they start, while trying to have as little overlap as possible, meaning the user walking the routes walks on as few streets twice or more often as possible.
The software is to calculate closed routes (starting point = ending point) while the length of the routes should equal the time t. Another restriction is that each street should be walked along as few times as possible to always explore new areas while walking for the same time period.
Example:
You are in New York City (google maps for an example map)
- You want to walk for 40 minutes.
- You want to be on new roads or paths as often as possible.
Picture having a thread. The thread has a length of velocity_walking * t in a smaller scale. Now you glue the end and start to a starting point on your map, lat and lon. Then you move the thread so it is only on streets/walking paths, without being on the same street twice.
Now you take another thread and glue the end and start to a starting point on your map, lat and lon. Now you do the same thing as above, trying to not put it over the other thread.
You repeat this n times, all in all, so given the first two threads, you repeat it n-2 times.
So the steps are
- Enter
n - Enter
t - Enter the starting point in
latandlon - Create
nroutes that takettime units to walk by foot, start and end inlat,lonand if possible don’t contain the same streets or parts of streets twice.
My idea:
Having a circle of radius equaling walking_velocity * t / 2. Plan routes from start to point on circle to start.
Disadvantages:
- Same streets to the circle’s circumference and back.
- Many streets are omitted.
What is the better algorithm to do this? Language does not matter, algorithm matters.
6
This might not be the most efficient, but it would be a good starting point. I think any better algorithm would be an optimization or simplification of this one.
Set up the problem
- Convert the geographical map into a graph. Intersections are nodes, streets or other footpaths are edges.
- Each edge has a cost which is the time required to traverse that edge.
- Each edge tracks the number of times it has been traversed.
- Pick a starting node.
- Choose a desired time (cost) at which a route terminates.
- The algorithm will have a running total of the cost accrued from traversing the previous nodes. This cost starts at zero.
Traversing the graph
- At any given node, evaluate the edges connected to it. If the cost of an edge plus the current accrued cost is greater than the terminating cost, that edge is removed from consideration. If the algorithm backtracked from an edge, remove that edge from consideration.
- If there are no edges to consider, backtrack and remove the cost of the backtracked edge. If the total cost is zero (i.e. at the start node with nothing traversed), the algorithm terminates.
- Of the remaining edges, pick one to traverse and repeat the algorithm.
Analysis
This is essentially a basic search tree algorithm which includes costs for each edge. Note that it also does not forbid traversing forward backwards, meaning going from node A to B and back to A without backtracking. That might actually increase the total amount of distance covered if B is a dead end and the cost is low compared to other edges.
6