Endgame tools for a cyclist trying to bike down every street in a city?
June 13, 2013 9:03 AM Subscribe
For the past year I've been trying to bike down every street in St Louis. In the beginning this was easy and wide-open and fun. The middle has been less so. Now, sitting at ≈65% completion [map: zoomable | 1.5mb png | GPX] my current approach has become overwhelming and tedious, and is no longer working; I need to get way smarter about this. How would a programmer, a mathematician, or a GIS/transit specialist approach this endgame, and what tools/software would he/she use?
This is getting much harder, and my return on time spent has trended towards unsustainable. I gotta make some big changes. I need help with: 01) overall approach, and 02) tools/software that'd make it most easy. I'd give myself a budget of $200 for this (but would range up to twice that if there was an amazing/transcendent solution).
As you can tell by the map, I've pretty much hit up all the low-hanging fruit, in regards to easy, gridded streets. This leaves me with a maze of irregular streets and a daunting number of small missed streets.
To this point I've just made a simple cue sheet marking the boundaries of what I'd be doing that day. But as of late these cue sheets have become tedious and hyper-specific and a chore to make, and a bigger chore to follow.
If this were 6 years into the future, a great solution might be a Google Glass sort of deal that'd highlight unridden streets as green, or something... but I'm trying to finish this before winter.
Three notes framing the problem (feel free to ask if other info would be helpful):
This is getting much harder, and my return on time spent has trended towards unsustainable. I gotta make some big changes. I need help with: 01) overall approach, and 02) tools/software that'd make it most easy. I'd give myself a budget of $200 for this (but would range up to twice that if there was an amazing/transcendent solution).
As you can tell by the map, I've pretty much hit up all the low-hanging fruit, in regards to easy, gridded streets. This leaves me with a maze of irregular streets and a daunting number of small missed streets.
To this point I've just made a simple cue sheet marking the boundaries of what I'd be doing that day. But as of late these cue sheets have become tedious and hyper-specific and a chore to make, and a bigger chore to follow.
If this were 6 years into the future, a great solution might be a Google Glass sort of deal that'd highlight unridden streets as green, or something... but I'm trying to finish this before winter.
Three notes framing the problem (feel free to ask if other info would be helpful):
- I don't have a car, but have access to a robust transit system [map: 2.6mb PDF], and can take the bike on all buses and trains.
- I live in the centrally-located Shaw neighborhood.
- Preferred ride lengths are in the 20mi-30mi range 4×/week, and a 40mi-50mi ride 1-2×/week.
- Garmin Edge 500 GPS
- Android smartphone w/GPS
- Strava Pro account w/GPX export: [profile | GPX for all rides]
- GRASS, QGIS, Google Earth, etc, with "C-" skills at employing each.
- A 10-year-old and never-professionally-used Geography/GIS undergraduate degree. I bring this up to say that I can grok geospatial things well enough, but couldn't begin to develop tools, and shouldn't be trusted to be adept at their use.
There are libraries and services that do traveling-salesman type route calculations. It seems like you'd still have to do a lot of the organizing yourself (eg, selecting a set of streets for the day's trip) but they could be helpful. I don't think they do hybrid transit+bike route optimization, though.
posted by hattifattener at 9:43 AM on June 13, 2013
posted by hattifattener at 9:43 AM on June 13, 2013
The routing page on that openstreetmap wiki might be a good place to look for tools as well. There are a fair number of bicycling-oriented routing tools listed, some of them might let you specify roads you want to cover.
I think you're looking for the most efficient path through an edge-weighted directed graph that covers each of a specific set of edges. I don't know what that's called or how to find it.
posted by makeitso at 9:49 AM on June 13, 2013
I think you're looking for the most efficient path through an edge-weighted directed graph that covers each of a specific set of edges. I don't know what that's called or how to find it.
posted by makeitso at 9:49 AM on June 13, 2013
I don't have a fancy mathmatical way of doing this, but why not divide the city map into 1/2 mile squares. Then for each ride print out a map of a new square and then go there and ride each street in the square. The 1/2 mile area is small enough that you can remember if you've ridden each street that day as you come to them.
posted by monotreme at 10:02 AM on June 13, 2013
posted by monotreme at 10:02 AM on June 13, 2013
Google Maps lets you preplan a route, no matter how ridiculous, by clicking on the route and dragging to add a new destination.
You can print out the turn list, or email the humungous hard-link to your Android phone to view the turn list in your mobile browser. I was having trouble bringing up the interactive Maps interface with this large list of destinations using Chrome To Phone (where clicking on the chrome-to-phone button would open up the current Desktop browser map on your mobile Maps application), but maybe you'll have better luck. If you were able to do that, then you could use Navigation to walk you through it.
posted by dobi at 10:16 AM on June 13, 2013 [1 favorite]
You can print out the turn list, or email the humungous hard-link to your Android phone to view the turn list in your mobile browser. I was having trouble bringing up the interactive Maps interface with this large list of destinations using Chrome To Phone (where clicking on the chrome-to-phone button would open up the current Desktop browser map on your mobile Maps application), but maybe you'll have better luck. If you were able to do that, then you could use Navigation to walk you through it.
posted by dobi at 10:16 AM on June 13, 2013 [1 favorite]
I'd register and ask on help.openstreetmap.org about routing and solving the final streets. I'm sure someone would jump at the chance to help with solving the routing problem, especially if you offered to upload your tracks to the OSM server. Many of the streets in St Louis are from TIGER imports, and they are a bit off. Known-good tracks would be very helpful for local mappers.
The OSM newbies and Talk-us mailing lists might also be helpful.
posted by scruss at 11:19 AM on June 13, 2013 [2 favorites]
The OSM newbies and Talk-us mailing lists might also be helpful.
posted by scruss at 11:19 AM on June 13, 2013 [2 favorites]
A friend of mine rode and mapped all of San Francisco. I pointed him to your question and he sent the following response:
I use this tool to overlay all my rides and see what I have missed. I would either take a screenshot of the area I was heading into and then refer to it frequently (on Iphone) or I would map a route ahead of time with ridewithgps.com. In order to show others, I created a tumblr. Feel free to join this group on Strava too. So far we have SF and London…Good Luck!
posted by Kafkaesque at 11:31 AM on June 13, 2013 [3 favorites]
I use this tool to overlay all my rides and see what I have missed. I would either take a screenshot of the area I was heading into and then refer to it frequently (on Iphone) or I would map a route ahead of time with ridewithgps.com. In order to show others, I created a tumblr. Feel free to join this group on Strava too. So far we have SF and London…Good Luck!
posted by Kafkaesque at 11:31 AM on June 13, 2013 [3 favorites]
The OpenStreetMap crowd has been here, from mapping cities in totality to just finding un-ridden corners. Might want to ask Mike Maron Richard Fairhurst and so on.
Since OSM people are sometimes less than helpful with the exception of just-linked folks, here's one direction: an overlay of places you've been that covers up roads. Made this to make that possible
Disclosure: involved in everything way too much.
posted by tmcw at 11:32 AM on June 13, 2013 [1 favorite]
Since OSM people are sometimes less than helpful with the exception of just-linked folks, here's one direction: an overlay of places you've been that covers up roads. Made this to make that possible
Disclosure: involved in everything way too much.
posted by tmcw at 11:32 AM on June 13, 2013 [1 favorite]
1. Ask Siri to ask the NSA. No really, unless you are a hardcore math nut – this is not going to be fun. If you are a hardcore math nut – welcome to an awesome graph theory problem.
1. Ok so you are still set on optimization. I’ll set up the problem in terms of what how you want to view the data.
a. Nodes: Nodes are all intersections.
b. Vertices: Each vertices has
i. Node one
ii. Node two (optional – could be a 1 way street)
iii. Weight associated with it (which is the length of it)
1. You could – if a math masochist – set up two weights, one for each direction (hills, one way street, traffic conditions, traffic lights, etc). I’m assuming you are not a math masochist – despite the evidence on the contrary, given that you are a biking one.
iv. Status – Completed or Not
2. Next, set your completion mileage in a day. This is the mileage where once you hit you need to return home
3. Now you also need to know what the maximum mileage is that you can possibly ride – this is completion + however far you are from home. This will be used to eliminate routes that strand you too far away from home.
4. You need to make a table of *every* road in the city by their vertices. Why every road? Well, you want to plan the optimal path, so that may mean repeating some of the roads you’ve traveled on in order to get to a patch you haven’t traveled on. (Originally we discussed dropping off these routes, but we realized there was still a cost associated with them.)
5. Ok, so now you want to take that table into something like RapidMiner, learn vector machines and effectively simulate the model of your city, then you simulate a couple hundred thousand runs and hope the machine finds one that wins.
a. Terms of success:
i. Success is defined as all roads reach completion and you have not exceeded maximum mileage to do so.
ii. Once you achieve a solution, you should have the number of routes you need to bike, which vertices you need to take where, and that indicates the number of days it will take you.
iii. But wait – it isn’t optimized until you’ve continued your modeling to see whether you can start from scratch and if the next iteration is shorter.
1. Once a path exceeds the length of the completed solution, it can be considered invalid since it fails.
2. There is a slight possibility that you will have a shorter travel distance but more days vs. a longer travel distance with fewer days. I’m not sure which you would consider an optimal solution
This is honestly a pretty awesome problem which a few co-workers and I kicked around for the past 30 minutes or so.
posted by Nanukthedog at 12:17 PM on June 13, 2013 [3 favorites]
1. Ok so you are still set on optimization. I’ll set up the problem in terms of what how you want to view the data.
a. Nodes: Nodes are all intersections.
b. Vertices: Each vertices has
i. Node one
ii. Node two (optional – could be a 1 way street)
iii. Weight associated with it (which is the length of it)
1. You could – if a math masochist – set up two weights, one for each direction (hills, one way street, traffic conditions, traffic lights, etc). I’m assuming you are not a math masochist – despite the evidence on the contrary, given that you are a biking one.
iv. Status – Completed or Not
2. Next, set your completion mileage in a day. This is the mileage where once you hit you need to return home
3. Now you also need to know what the maximum mileage is that you can possibly ride – this is completion + however far you are from home. This will be used to eliminate routes that strand you too far away from home.
4. You need to make a table of *every* road in the city by their vertices. Why every road? Well, you want to plan the optimal path, so that may mean repeating some of the roads you’ve traveled on in order to get to a patch you haven’t traveled on. (Originally we discussed dropping off these routes, but we realized there was still a cost associated with them.)
5. Ok, so now you want to take that table into something like RapidMiner, learn vector machines and effectively simulate the model of your city, then you simulate a couple hundred thousand runs and hope the machine finds one that wins.
a. Terms of success:
i. Success is defined as all roads reach completion and you have not exceeded maximum mileage to do so.
ii. Once you achieve a solution, you should have the number of routes you need to bike, which vertices you need to take where, and that indicates the number of days it will take you.
iii. But wait – it isn’t optimized until you’ve continued your modeling to see whether you can start from scratch and if the next iteration is shorter.
1. Once a path exceeds the length of the completed solution, it can be considered invalid since it fails.
2. There is a slight possibility that you will have a shorter travel distance but more days vs. a longer travel distance with fewer days. I’m not sure which you would consider an optimal solution
This is honestly a pretty awesome problem which a few co-workers and I kicked around for the past 30 minutes or so.
posted by Nanukthedog at 12:17 PM on June 13, 2013 [3 favorites]
I am working on a similar project to run every road in Columbia, MO. Hello to a follow Missourian! I, too, have a geography/GIS degree. Given a bunch of points, ArcGIS will make me routes (of course, google will do that more neatly) and will let me add basically any impediment I want. There happens to be a lot of GIS data for CoMo so I can tell it "only roads with sidewalks" or "maximize unpaved roads" or whatever. For windy neighborhood roads, I think of them in terms of ladder-like puzzles that I run in elongated figure 8's.
In ASCII art, it would look like:
I--------I
I--------I
I--------I
I--------I
I--------I
I--------I
and I would run it in an S shape skipping every other cross street, then reverse direction and hit everything I missed the first.
posted by thewestinggame at 4:17 PM on June 13, 2013
In ASCII art, it would look like:
I--------I
I--------I
I--------I
I--------I
I--------I
I--------I
and I would run it in an S shape skipping every other cross street, then reverse direction and hit everything I missed the first.
posted by thewestinggame at 4:17 PM on June 13, 2013
This thread is closed to new comments.
Here are the city limits of St Louis City.
posted by jjjjjjjijjjjjjj at 9:09 AM on June 13, 2013